IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
28 November 2023
Gilles Macario-Rat, Jacques Patarin, Benoit Cogliati, Jean-Charles Faugère, Pierre-Alain Fouque, Louis Gouin, Robin Larrieu, Brice Minaud
In this note, we explain the attack in the specific case of VOX, we detail the complexity, and show that as Furue and Ikematsu indicated, the attack can be completely avoided by adding one more constraint on the parameter selection. Finally, we show that this constraint does not increase the sizes of the public keys or signature.
27 November 2023
Aleksei Udovenko
Nils Fleischhacker, Gottfried Herold, Mark Simkin, Zhenfei Zhang
In this work, we consider multi-signatures in the synchronized setting, where the signing algorithm takes an additional time parameter as input and it is only required that signatures for the same time step are aggregatable. The synchronized setting is simpler than the general multi-signature setting, but is sufficient for most blockchain related applications, as signers are naturally synchronized by the length of the chain.
We present Chipmunk, a concretely efficient lattice-based multi-signature scheme in the synchronized setting that allows for signing an a-priori bounded number of messages. Chipmunk allows for non-interactive aggregation of signatures and is secure against rogue-key attacks. The construction is plausibly secure against quantum adversaries as our security relies on the assumed hardness of the short integer solution problem.
We significantly improve upon the previously best known construction in this setting by Fleischhacker, Simkin, and Zhang (CCS 2022). Our aggregate signature size is $5.6 \times$ smaller and for $112$ bits of security our construction allows for compressing 8192 individual signatures into a multi-signature of size around $136$ KB. We provide a full implementation of Chipmunk and provide extensive benchmarks studying our construction's efficiency.
Carmit Hazay, Muthuramakrishnan Venkitasubramaniam, Mor Weiss
In this work, we extend the MPC-in-the-Head paradigm to game-based cryptographic primitives supporting homomorphic computations (e.g., fully-homomorphic encryption, functional encryption, randomized encodings, homomorphic secret sharing, and more). Specifically, we present a simple yet generic compiler from these primitives to ZKPs which use the underlying primitive as a black box. We also generalize our paradigm to capture commit-and-prove protocols, and use it to devise tight black-box compilers from Interactive (Oracle) Proofs to ZKPs, assuming One-Way Functions (OWFs).
We use our paradigm to obtain several new ZKP constructions:
1. The first ZKPs for NP relations $\mathcal{R}$ computable in (polynomial-time uniform) $NC^1$, whose round complexity is bounded by a fixed constant (independent of the depth of $\mathcal{R}$'s verification circuit), with communication approaching witness length (specifically, $n\cdot poly\left(\kappa\right)$, where $n$ is the witness length, and $\kappa$ is a security parameter), assuming DCR. Alternatively, if we allow the round complexity to scale with the depth of the verification circuit, our ZKPs can make black-box use of OWFs.
2. Constant-round ZKPs for NP relations computable in bounded polynomial space, with $O\left(n\right)+o\left(m\right)\cdot poly\left(\kappa\right)$ communication assuming OWFs, where $m$ is the instance length. This gives a black-box alternative to a recent non-black-box construction of Nassar and Rothblum (CRYPTO`22).
3. ZKPs for NP relations computable by a logspace-uniform family of depth-$d\left(m\right)$ circuits, with $n\cdot poly\left(\kappa,d\left(m\right)\right)$ communication assuming OWFs. This gives a black-box alternative to a result of Goldwasser, Kalai and Rothblum (JACM).
Romain Gay, Bogdan Ursu
Julien Jainsky, David Naccache, Bassem Ouni, Ofer Yifrach-Stav
We combine several existing technologies to achieve the stated goal. The building-blocks used are inherent physical randomness generated during the packaging process, artificial vision, short digital signatures and QR-codes.
Tianjian Liu, Dawei Zhang, Wei Wang
Neil Thanawala, Hamid Nejatollahi, Nikil Dutt
Ahmad Khoureich Ka
In this paper, we propose a non-monotone CP-ABE scheme that has no restrictions on the size of attribute sets and policies, allows fast decryption and is adaptively secure under the CBDH-3 assumption. To achieve this, we approached the problem from a new angle, namely using a set membership relation for access structure. We have implemented our scheme using the Java Pairing-Based Cryptography Library (JPBC) and the source code is available on GitHub.
25 November 2023
University of Waterloo, Department of Combinatorics & Optimization; Waterloo, Canada
The Department of Combinatorics and Optimization in the Faculty of Mathematics at the University of Waterloo invites applications for three tenure-track faculty positions at the rank of Assistant Professor. Appointments at the level of Associate or Full Professor with tenure will be considered in special cases that substantially enhance the reputation of the department. Stellar candidates in the research areas of algebraic combinatorics, continuous optimization, cryptography, discrete optimization, and graph theory, who can greatly enhance the research and teaching profile of the department, are welcome to apply. Cryptography and optimization are the focus areas for these positions, and within optimization, continuous optimization is a priority area.
A Ph.D. degree and evidence of excellence in research and teaching are required. Successful applicants are expected to maintain an active program of research, to attract and supervise graduate students, and to participate in undergraduate and graduate teaching.
The salary range for the position is $105,000 to $155,000. Negotiations beyond this salary range will be considered for exceptionally qualified candidates. The anticipated start date is July 1, 2024. Interested individuals should apply using the MathJobs site (https://www.mathjobs.org/jobs/list/23241). Applications should include a curriculum vitae, research and teaching statements, and up to three reprints/preprints. In addition, at least three reference letters should be submitted.
The deadline for applications is December 4, 2023. Applications received by December 4, will be given full consideration. However, applications will continue to be reviewed until the position is filled.
Closing date for applications:
Contact: Chaitanya Swamy, Chair, Department of Combinatorics and Optimization
More information: https://www.mathjobs.org/jobs/list/23241
24 November 2023
Julian Loss, Jesper Buus Nielsen
Sahil Sharma
Kathrin Hövelmanns, Christian Majenz
The proof in [HHM22] involves a new correctness notion for the encryption scheme that is used to encapsulate the keys. This allows in principle for a smaller additive security related to decryption failures, but requires to analyze this new notion for the encryption scheme on which a concrete KEM at hand is based.
This note offers a trade-off between [HHM22] and its predecessors: it offers a bound for both rejection variants, being mostly based on [HHM22], but uses a more established correctness notion.
Julia Kastner, Ky Nguyen, Michael Reichle
Alex Biryukov, Marius Lombard-Platet
Yuchao Chen, Tingting Guo, Lei Hu, Lina Shang, Shuping Mao, Peng Wang
Nishat Koti, Varsha Bhat Kukkala, Arpita Patra, Bhavish Raj Gopal
Xudong Zhu, Xuyang Song, Yi Deng
In this study, We proposed the first publicly verifiable non-uniform ZK zk-SNARK scheme in the BPK model maintaining comparable efficiency with its conventional counterpart, which can also be compatible with the well-known transformation proposed by Bitansky et al. in TCC 2013 to obtain an efficient designated-verifier zk-SNARK. We achieve this goal by only adding a constant number of elements into the CRS, and using an unconventional but natural method to transform Groth’s zkSNARK in EUROCRYPT 2016. In addition, we propose a new speed-up technique that provides a trade-off. Specifically, if a logarithmic number of elements are added into the CRS, according to different circuits, the CRS verification time in our construction could be approximately 9%-23% shorter than that in the conventional counterpart.
Hien Chu, Khue Do, Lucjan Hanzlik
Marian Dietz, Stefano Tessaro
This problem was recently considered by Colombo et al. (USENIX '23), who proposed solutions secure under the assumption that the database is committed to honestly. Here, we close this gap, and present a solution that tolerates fully malicious servers that provide potentially malformed commitments. Our scheme has communication and client computational complexity $\mathcal{O}_{\lambda}(\sqrt{N})$, solely relies on the DDH assumption, and does not introduce heavy machinery (e.g., generic succinct proofs). Privacy with abort holds provided the server succeeds in correctly answering $\lambda$ validation queries, which, from its perspective, are computationally indistinguishable from regular PIR queries. In fact, server side, our scheme is exactly the DDH-based scheme by Colombo et al.