CryptoDB
Josef Pieprzyk
Publications and invited talks
Year
Venue
Title
2025
ASIACRYPT
Lattice-Based Group Signatures in the Standard Model, Revisited
Abstract
The study of lattice-based group signatures has been a prominent research direction since 2010. While recent advances in the field have yielded schemes in the random oracle model with strong security properties and nearly practical efficiency, the current state of affairs for lattice-based group signatures in the standard model is still much less satisfactory. Existing schemes, proposed by Katsumata and Yamada (EUROCRYPT’19) or implied by generic non-interactive zero-knowledge proofs for NP (by Peikert and Shiehian at CRYPTO’19 and by Waters at STOC’24), either only fulfil a weak notion of anonymity called selfless anonymity, or require a strong lattice assumption, or suffer from extremely large signatures and/or public keys.
This work aims to enhance the state of affairs for lattice-based group signatures in the standard model. We provide improved constructions that simultaneously achieves: (i) signature and public key sizes significantly smaller than those of known schemes; (ii) full anonymity in the CPA and CCA senses; (iii) security based on standard SIS and LWE assumptions with polynomial approximation factors regarding worst-case lattice problems (in general lattices). Our design approach slightly departs from that of existing pairing-based and lattice-based constructions. In the design process, we adapt and develop several lattice-based cryptographic ingredients that may be of independent interest. At the heart of our constructions is a reasonably efficient non-interactive zero-knowledge proof system for relations typically appearing in advanced
privacy-preserving lattice-based cryptographic protocols. These relations are addressed by a trapdoor Σ-protocol with an inverse polynomial soundness error, which is made non-interactive via the standard-model Fiat-Shamir transform of Canetti et al. (STOC’19) and a compiler by Libert et al. (ASIACRYPT’20).
2015
EUROCRYPT
2012
JOFC
Graph Coloring Applied to Secure Computation in Non-Abelian Groups
Abstract
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).
2004
PKC
1992
EUROCRYPT
1991
ASIACRYPT
1991
ASIACRYPT
Service
- Asiacrypt 2023 Program committee
- Eurocrypt 2022 Program committee
- Asiacrypt 2020 Program committee
- Asiacrypt 2018 General chair
- IACR Board: Asiacrypt general chair 2017 - 2018
- Eurocrypt 2016 Program committee
- Crypto 2015 Program committee
- Asiacrypt 2015 Program committee
- FSE 2014 Program committee
- FSE 2010 Program committee
- Asiacrypt 2009 Program committee
- FSE 2008 Program committee
- Asiacrypt 2008 Program chair
- FSE 2007 Program committee
- PKC 2005 Program committee
- Eurocrypt 2003 Program committee
- PKC 2001 Program committee
- PKC 2000 Program committee
- Eurocrypt 1997 Program committee
- Crypto 1995 Program committee
- Asiacrypt 1994 Program chair
- Auscrypt 1992 Program committee
- Crypto 1991 Program committee
- Auscrypt 1990 Program chair
Coauthors
- Olivier Billet (1)
- Alex Biryukov (1)
- Lawrence Brown (2)
- Laurence Bull (1)
- Chris Charnes (3)
- Joo Yeon Cho (1)
- Scott Contini (3)
- Nicolas Courtois (1)
- Yvo Desmedt (2)
- Itai Dinur (1)
- Sareh Emami (1)
- Kris Gaj (1)
- Praveen Gauravaram (1)
- Hossein Ghodosi (1)
- Jian Guo (2)
- Thomas Hardjono (1)
- Ekawat Homsirikamol (1)
- Dmitry Khovratovich (2)
- Matthew Kwan (2)
- San Ling (5)
- Dongxi Liu (1)
- Krystian Matusiewicz (4)
- Dariusz Michatek (1)
- Pawel Morawiecki (3)
- Khoa Nguyen (1)
- Ivica Nikolić (3)
- Luke O'Connor (1)
- Jaroslaw Pastuszak (1)
- Thomas Peyrin (2)
- Josef Pieprzyk (44)
- Marcin Rogawski (1)
- Babak Sadeghiyan (5)
- Reihaneh Safavi-Naini (2)
- Jennifer Seberry (4)
- Przemyslaw Sokolowski (2)
- Marian Srebrny (3)
- Ron Steinfeld (11)
- Michal Straus (1)
- Xiaoming Sun (1)
- Willy Susilo (1)
- Christophe Tartary (2)
- Nam Tran (1)
- Huaxiong Wang (14)
- Lei Wei (1)
- Marcin Wójcik (1)
- Andrew Chi-Chih Yao (1)
- Xian-Mo Zhang (1)
- Yuliang Zheng (4)