International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Yvo Desmedt

Publications

Year
Venue
Title
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
2004
CRYPTO
2002
EUROCRYPT
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

Service

PKC 2016 Program committee
PKC 2007 Program committee
Asiacrypt 2006 Program committee
IACR Board: Director 2006 - 2008
PKC 2005 Program committee
PKC 2004 Program committee
PKC 2003 Program chair
PKC 2002 Program committee
PKC 2001 Program committee
IACR Board: Director 2001 - 2003
PKC 2000 Program committee
Asiacrypt 2000 Program committee
PKC 1999 Program committee
Eurocrypt 1998 Program committee
Crypto 1994 Program chair
Eurocrypt 1994 Program committee
Asiacrypt 1994 Program committee
Eurocrypt 1993 Program committee
Eurocrypt 1992 Program committee
Auscrypt 1992 Program committee
Asiacrypt 1991 Program committee
Crypto 1990 Program committee
Eurocrypt 1989 Program committee