Σ-Protocols provide a well-understood basis for secure algorithmics. Compressed Σ-protocol theory (CRYPTO 2020) was introduced as a strengthening yielding protocols with low communication complexity. It is built around basic Σ-protocols for proving that a compactly committed (long) vector satisfies a linear constraint. The communication complexity of these protocols is first compressed, from linear down to logarithmic, using a recursive ``folding-technique'' adapted from Bulletproofs (Bootle et al., EUROCRYPT 2016, and Bünz et al., S&P 2018), at the expense of logarithmic rounds. Proving in ZK that the secret vector satisfies a given constraint -- captured by a (non-linear) circuit -- is then by (blackbox) reduction to the linear case, via arithmetic secret-sharing techniques adapted from MPC.
This abstract modular theory has been instantiated from a variety of cryptographic hardness assumptions, i.e., the discrete-logarithm, strong-RSA, knowledge-of-exponent assumption. In two separate works, it has also been generalized to a bilinear circuit model and instantiated from the ring-SIS assumption. Thus for all these platforms compressed Σ-protocol theory yields circuit zero-knowledge protocols with (poly)-logarithmic communication.
All in all, our theory should more generally be useful for modular (``plug-&-play'') design of practical cryptographic protocols; this is further evidenced by our separate work on proofs of partial knowledge.
Joint work with: Ronald Cramer, Serge Fehr, Lisa Kohl and Matthieu Rambaud
Thomas Attema is a researcher at the applied research institute TNO in The Netherlands, where he works on (applied) multi-party computation, zero-knowledge proof systems and post-quantum cryptography. Moreover, he is pursuing a part-time PhD in the Cryptology group of CWI under the supervision of Ronald Cramer.
We present an algorithm solving the ROS (Random inhomogeneities in a Overdetermined Solvable system of linear equations) problem in polynomial time for $\ell > \log p$ dimensions. Our algorithm can be combined with Wagner’s attack, and leads to a sub-exponential solution for any dimension $\ell$ with best complexity known so far. When concurrent executions are allowed, our algorithm leads to practical attacks against unforgeability of blind signature schemes such as Schnorr and Okamoto–Schnorr blind signatures, threshold signatures such as GJKR and the original version of FROST, multisignatures such as CoSI and the two-round version of MuSig, partially blind signatures such as Abe–Okamoto, and conditional blind signatures such as ZGP17.
This is joint work with Fabrice Benhamouda, Tancrede Lépoint, Julian Loss, Mariana Raykova.
Michele is a postdoc at UC Berkeley under the supervision of Alessandro Chiesa.
Prior to that, he was a PhD student at École Normale Supérieure, under the supervision of Georg Fuchsbauer. He is interested in the intersection between authentication and anonymity.
In the past, he contributed to Python, Debian, and Tor.
The Fiat-Shamir transform is a general method for reducing interaction in public-coin protocols by replacing the random verifier messages with deterministic hashes of the protocol transcript. The soundness of this transformation is usually heuristic and lacks a formal security proof. Instead, to argue security, one can rely on the random oracle methodology, which informally states that whenever a random oracle soundly instantiates Fiat-Shamir, a hash function that is ``sufficiently unstructured'' (such as fixed-length SHA-2) should suffice. Finally, for some special interactive protocols, it is known how to (1) isolate a concrete security property of a hash function that suffices to instantiate Fiat-Shamir and (2) build a hash function satisfying this property under a cryptographic assumption such as Learning with Errors.
In this work, we abandon this methodology and ask whether Fiat-Shamir truly requires a cryptographic hash function. Perhaps surprisingly, we show that in two of its most common applications --- building signature schemes as well as (general-purpose) non-interactive zero-knowledge arguments --- there are sound Fiat-Shamir instantiations using extremely simple and non-cryptographic hash functions such as sum-mod-$p$ or bit decomposition. In some cases, we make idealized assumptions (i.e., we invoke the generic group model), while in others, we prove soundness in the plain model.
On the negative side, we also identify important cases in which a cryptographic hash function is provably necessary to instantiate Fiat-Shamir. We hope this work leads to an improved understanding of the precise role of the hash function in the Fiat-Shamir transformation.
Joint work with Yilei Chen, Alex Lombardi and Fermi Ma. Eprint: https://eprint.iacr.org/2020/915
Willy Quach is a 5th year PhD student at Northeastern University advised by Daniel Wichs.
Σ-Protocols provide a well-understood basis for secure algorithmics. Compressed Σ-protocol theory (CRYPTO 2020) was introduced as a strengthening yielding protocols with low communication complexity. It is built around basic Σ-protocols for proving that a compactly committed (long) vector satisfies a linear constraint. The communication complexity of these protocols is first compressed, from linear down to logarithmic, using a recursive ``folding-technique'' adapted from Bulletproofs (Bootle et al., EUROCRYPT 2016, and Bünz et al., S&P 2018), at the expense of logarithmic rounds. Proving in ZK that the secret vector satisfies a given constraint -- captured by a (non-linear) circuit -- is then by (blackbox) reduction to the linear case, via arithmetic secret-sharing techniques adapted from MPC.
This abstract modular theory has been instantiated from a variety of cryptographic hardness assumptions, i.e., the discrete-logarithm, strong-RSA, knowledge-of-exponent assumption. In two separate works, it has also been generalized to a bilinear circuit model and instantiated from the ring-SIS assumption. Thus for all these platforms compressed Σ-protocol theory yields circuit zero-knowledge protocols with (poly)-logarithmic communication.
All in all, our theory should more generally be useful for modular (``plug-&-play'') design of practical cryptographic protocols; this is further evidenced by our separate work on proofs of partial knowledge.
Joint work with: Ronald Cramer, Serge Fehr, Lisa Kohl and Matthieu Rambaud
Thomas Attema is a researcher at the applied research institute TNO in The Netherlands, where he works on (applied) multi-party computation, zero-knowledge proof systems and post-quantum cryptography. Moreover, he is pursuing a part-time PhD in the Cryptology group of CWI under the supervision of Ronald Cramer.
In this talk, we study the passive security model of approximate homomorphic encryption schemes. We present new passive security definitions for homomorphic encryption in the approximate computation setting, by naturally extending the traditional notion of IND-CPA security. We propose both indistinguishability-based and simulation-based variants, as well as restricted versions of the definitions that limit the order and number of adversarial queries (as may be enforced by some applications). We prove implications and separations among different definitional variants, showing a hierarchy of approximate homomorphic encryption schemes. Our models provide a solid theoretical basis for the security evaluation of approximate homomorphic encryption schemes (against passive attacks).
As the main application of our passive security models, we present passive attacks against CKKS, the homomorphic encryption scheme for arithmetic on approximate numbers presented at Asiacrypt 2017. The attack is both theoretically efficient (running in expected polynomial time) and very practical, leading to complete key recovery with high probability and very modest running times. We implemented and tested the attack against major open source homomorphic encryption libraries, including HEAAN, SEAL, HElib, PALISADE and Lattigo, and when computing several functions that often arise in applications of the CKKS scheme to privacy-preserving machine learning. Our attack shows that the traditional formulation of IND-CPA security (or indistinguishability against chosen plaintext attacks) achieved by CKKS does not adequately capture security against passive adversaries when applied to approximate encryption schemes, and that a different, stronger definition is required to evaluate the security of such schemes.
We further discuss possible modifications to CKKS that may serve as countermeasures to our attacks, and we also discuss open problems of efficiently achieving provable security under our new definitions.
This talk is based on the joint work with Daniele Micciancio.
Baiyu Li graduated with a Ph.D. degree from UCSD in 2021, advised by Daniele Micciancio. His research interests include formal methods for secure computation protocol design and analysis, as well as lattice-based cryptography. Previously he received his Master's and Bachelor's degrees in CS and Pure Math from the University of Waterloo.
In this talk we will give a quantum reduction from finding short codewords in a random linear code to decoding for the Hamming metric. This is the first time such a reduction (classical or quantum) has been obtained. Our reduction adapts to linear codes Stehlé-Steinfield-Tanaka-Xagawa’ re-interpretation of Regev’s quantum reduction from finding short lattice vectors to solving the Closest Vector Problem. The Hamming metric is a much coarser metric than the Euclidean metric and this adaptation has needed several new ingredients to make it work. For instance, in order to have a meaningful reduction it is necessary in the Hamming metric to choose a very large decoding radius and this needs in many cases to go beyond the radius where decoding is unique. Another crucial step for the analysis of the reduction is the choice of the errors that are being fed to the decoding algorithm. For lattices, errors are usually sampled according to a Gaussian distribution. However, it turns out that the Bernoulli distribution (the analogue for codes of the Gaussian) is too much spread out and can not be used for the reduction with codes. Instead we choose here the uniform distribution over errors of a fixed weight and bring in orthogonal polynomials tools to perform the analysis and an additional amplitude amplification step to obtain the aforementioned result.
The seminar will be at 13:00 UK time, 14:00 FR time
Thomas Debris-Alazard is a research scientist (chargé de recherche) at Inria in the Grace project-team. He was previously a postdoctoral research assistant in the Information Security Group under the supervision of Martin R. Albrecht. He received his PhD from Inria under the supervision of Jean-Pierre Tillich.