International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Yvo Desmedt

Publications

Year
Venue
Title
2014
EPRINT
2012
JOFC
Graph Coloring Applied to Secure Computation in Non-Abelian Groups
We study the natural problem of secure n-party computation (in the computationally unbounded attack model) of circuits over an arbitrary finite non-Abelian group (G,⋅), which we call G-circuits. Besides its intrinsic interest, this problem is also motivating by a completeness result of Barrington, stating that such protocols can be applied for general secure computation of arbitrary functions. For flexibility, we are interested in protocols which only require black-box access to the group G (i.e. the only computations performed by players in the protocol are a group operation, a group inverse, or sampling a uniformly random group element). Our investigations focus on the passive adversarial model, where up to t of the n participating parties are corrupted.Our results are as follows. We initiate a novel approach for the construction of black-box protocols for G-circuits based on k-of-k threshold secret-sharing schemes, which are efficiently implementable over any black-box (non-Abelian) group G. We reduce the problem of constructing such protocols to a combinatorial coloring problem in planar graphs. We then give three constructions for such colorings. Our first approach leads to a protocol with optimal resilience t<n/2, but it requires exponential communication complexity $O({\binom{2 t+1}{t}}^{2} \cdot N_{g})$ group elements and round complexity $O(\binom{2 t + 1}{t} \cdot N_{g})$, for a G-circuit of size Ng. Nonetheless, using this coloring recursively, we obtain another protocol to t-privately compute G-circuits with communication complexity $\mathcal{P}\mathit{oly}(n)\cdot N_{g}$ for any t∈O(n1−ϵ) where ϵ is any positive constant. For our third protocol, there is a probability δ (which can be made arbitrarily small) for the coloring to be flawed in term of security, in contrast to the first two techniques, where the colorings are always secure (we call this protocol probabilistic, and those earlier protocols deterministic). This third protocol achieves optimal resilience t<n/2. It has communication complexity O(n5.056(n+log δ−1)2⋅Ng) and the number of rounds is O(n2.528⋅(n+log δ−1)⋅Ng).
2011
ASIACRYPT
2010
JOFC
2010
ASIACRYPT
2007
ASIACRYPT
2007
CRYPTO
2006
EPRINT
A Tree-based Model of Unicast Stream Authentication
Goce Jakimoski Yvo Desmedt
When proving the security of a message authentication scheme, the messages are considered to be atomic objects. Straightforward application of such schemes to some information resources may introduce security flaws. Gennaro and Rohatgi (Crypto '97) identified the streams of data as an important class of information resources that can not be considered to be message-like, and they proposed a solution to the problem of stream signing when the stream is not known in advance. The disadvantage of digital signing streams of data is that it is not efficient when non-repudiation is not important, as in the case of point-to-point communications. We present several schemes and also a family of schemes for stream authentication in a unicast setting. Since many authentication schemes have been broken, we will prove our solutions.
2006
EPRINT
Scalable Authenticated Tree Based Group Key Exchange for Ad-Hoc Groups
Task-specific groups are often formed in an ad-hoc manner within big structures, like companies. Take the following typical scenario: A high rank manager decides that a task force group for some project needs to be built. This order is passed down the hierarchy where it finally reaches a manager who calls some employees to form a group. The members should communicate in a secure way and for efficiency reasons symmetric systems are the common choice. To establish joint secret keys for groups, group key exchange (GKE) protocols were developed. If the users are part of e.g. a Public Key Infrastructure (PKI), which is usually the case within a company or a small network, it is possible to achieve authenticated GKE by modifying the protocol and particularly by including signatures. In this paper we recall a GKE due to Burmester and Desmedt which needs only $O(\log n)$ communication and computation complexity per user, rather than $O(n)$ as in the more well-known Burmester-Desmedt protocol, and runs in a constant number of rounds. To achieve authenticated GKE one can apply compilers, however, the existing ones would need $O(n)$ computation and communication thereby mitigating the advantages of the faster protocol. Our contribution is to extend an existing compiler so that it preserves the computation and communication complexity of the non-authenticated protocol. This is particularly important for tree based protocols.
2005
EPRINT
On Resistance of DES to Related-Key Differential Cryptanalysis
Goce Jakimoski Yvo Desmedt
The key schedule of the Data Encryption Standard is analyzed, and it is shown that the properties of the permuted choice PC-2 transformation and the number of bits that are left shifted during the key generation are critical for the security of the algorithm. More precisely, we were able to mount a low complexity related-key attack on DES with slightly modified key schedule although no related-key attack is known for the original algorithm.
2004
CRYPTO
2002
EUROCRYPT
2002
EPRINT
Perfectly Secure Message Transmission Revisited
Yvo Desmedt Yongge Wang
Achieving secure communications in networks has been one of the most important problems in information technology. Dolev, Dwork, Waarts, and Yung have studied secure message transmission in one-way or two-way channels. They only consider the case when all channels are two-way or all channels are one-way. Goldreich, Goldwasser, and Linial, Franklin and Yung, Franklin and Wright, and Wang and Desmedt have studied secure communication and secure computation in multi-recipient (multicast) models. In a ``multicast channel'' (such as Ethernet), one processor can send the same message---simultaneously and privately---to a fixed subset of processors. In this paper, we shall study necessary and sufficient conditions for achieving secure communications against active adversaries in mixed one-way and two-way channels. We also discuss multicast channels and neighbor network channels.
2001
PKC
2001
JOFC
2000
EUROCRYPT
2000
PKC
1999
ASIACRYPT
1999
ASIACRYPT
1999
EUROCRYPT
1999
JOFC
1998
ASIACRYPT
1998
ASIACRYPT
1998
ASIACRYPT
1998
EUROCRYPT
1996
EUROCRYPT
1995
EUROCRYPT
1994
ASIACRYPT
1994
EUROCRYPT
1992
AUSCRYPT
1992
AUSCRYPT
1992
CRYPTO
1992
EUROCRYPT
1992
EUROCRYPT
1991
ASIACRYPT
1991
CRYPTO
1991
EUROCRYPT
1991
EUROCRYPT
1991
JOFC
1990
CRYPTO
1990
CRYPTO
1990
EUROCRYPT
1989
CRYPTO
1989
CRYPTO
1989
EUROCRYPT
1989
EUROCRYPT
1988
CRYPTO
1988
EUROCRYPT
1988
EUROCRYPT
1987
CRYPTO
1987
CRYPTO
1986
CRYPTO
1986
CRYPTO
1986
EUROCRYPT
1986
EUROCRYPT
1985
CRYPTO
1985
CRYPTO
1985
CRYPTO
1984
CRYPTO
1984
CRYPTO
1984
CRYPTO
1984
EUROCRYPT
1984
EUROCRYPT
1983
CRYPTO

Program Committees

PKC 2016
PKC 2007
Asiacrypt 2006
PKC 2005
PKC 2004
PKC 2003 (Program chair)
PKC 2002
PKC 2001
Asiacrypt 2000
PKC 2000
PKC 1999
Eurocrypt 1998
Asiacrypt 1994
Eurocrypt 1994
Crypto 1994 (Program chair)
Eurocrypt 1993
Auscrypt 1992
Eurocrypt 1992
Asiacrypt 1991
Crypto 1990
Eurocrypt 1989