International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Josef Pieprzyk

Publications

Year
Venue
Title
2015
FSE
2015
EUROCRYPT
2014
ASIACRYPT
2014
CHES
2013
FSE
2012
PKC
2012
FSE
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).
2009
PKC
2009
FSE
2008
FSE
2007
CRYPTO
2007
FSE
2006
ASIACRYPT
2006
PKC
2005
PKC
2004
ASIACRYPT
2004
FSE
2004
PKC
2003
ASIACRYPT
2003
ASIACRYPT
2002
ASIACRYPT
2000
PKC
1994
ASIACRYPT
1994
EUROCRYPT
1992
AUSCRYPT
1992
AUSCRYPT
1992
EUROCRYPT
1991
ASIACRYPT
1991
ASIACRYPT
1991
ASIACRYPT
1991
ASIACRYPT
1991
ASIACRYPT
1991
ASIACRYPT
1991
EUROCRYPT
1991
EUROCRYPT
1991
EUROCRYPT
1990
AUSCRYPT
1990
AUSCRYPT
1990
EUROCRYPT
1989
EUROCRYPT
1985
EUROCRYPT
1984
EUROCRYPT

Program Committees

Eurocrypt 2022
Asiacrypt 2020
Eurocrypt 2016
Crypto 2015
Asiacrypt 2015
FSE 2014
FSE 2010
Asiacrypt 2009
FSE 2008
Asiacrypt 2008 (Program chair)
FSE 2007
PKC 2005
Eurocrypt 2003
PKC 2001
PKC 2000
Eurocrypt 1997
Crypto 1995
Asiacrypt 1994 (Program chair)
Auscrypt 1992
Crypto 1991
Auscrypt 1990 (Program chair)