International Association for Cryptologic Research

International Association
for Cryptologic Research


Katerina Sotiraki


Sumcheck Arguments and their Applications 📺
We introduce a class of interactive protocols, which we call *sumcheck arguments*, that establishes a novel connection between the sumcheck protocol (Lund et al. JACM 1992) and folding techniques for Pedersen commitments (Bootle et al. EUROCRYPT 2016). Informally, we consider a general notion of bilinear commitment over modules, and show that the sumcheck protocol applied to a certain polynomial associated with the commitment scheme yields a succinct argument of knowledge for openings of the commitment. Building on this, we additionally obtain succinct arguments for the NP-complete language R1CS over certain rings. Sumcheck arguments enable us to recover as a special case numerous prior works in disparate cryptographic settings (such as discrete logarithms, pairings, RSA groups, lattices), providing one abstract framework to understand them all. Further, we answer open questions raised in prior works, such as obtaining a lattice-based succinct argument from the SIS assumption for satisfiability problems over rings.
Limits on the Efficiency of (Ring) LWE Based Non-interactive Key Exchange 📺
Siyao Guo Pritish Kamath Alon Rosen Katerina Sotiraki
$$mathsf {LWE}$$ based key-exchange protocols lie at the heart of post-quantum public-key cryptography. However, all existing protocols either lack the non-interactive nature of Diffie-Hellman key-exchange or polynomial $$mathsf {LWE}$$ -modulus, resulting in unwanted efficiency overhead. We study the possibility of designing non-interactive $$mathsf {LWE}$$ -based protocols with polynomial $$mathsf {LWE}$$ -modulus. To this end, We identify and formalize simple non-interactive and polynomial $$mathsf {LWE}$$ -modulus variants of existing protocols, where Alice and Bob simultaneously exchange one or more (ring) $$mathsf {LWE}$$ samples with polynomial $$mathsf {LWE}$$ -modulus and then run individual key reconciliation functions to obtain the shared key. We point out central barriers and show that such non-interactive key-exchange protocols are impossible if: (1) the reconciliation functions first compute the inner product of the received $$mathsf {LWE}$$ sample with their private $$mathsf {LWE}$$ secret. This impossibility is information theoretic. (2) One of the reconciliation functions does not depend on the error of the transmitted $$mathsf {LWE}$$ sample. This impossibility assumes hardness of $$mathsf {LWE}$$ . We give further evidence that progress in either direction, of giving an $$mathsf {LWE}$$ -based $$mathrm {NIKE}$$ protocol or proving impossibility of one will lead to progress on some other well-studied questions in cryptography. Overall, our results show possibilities and challenges in designing simple (ring) $$mathsf {LWE}$$ -based non-interactive key exchange protocols.
Towards Non-Interactive Zero-Knowledge for NP from LWE
Ron D. Rothblum Adam Sealfon Katerina Sotiraki
Non-interactive zero-knowledge ( $$\mathsf {NIZK}$$ ) is a fundamental primitive that is widely used in the construction of cryptographic schemes and protocols. Despite this, general purpose constructions of $$\mathsf {NIZK}$$ proof systems are only known under a rather limited set of assumptions that are either number-theoretic (and can be broken by a quantum computer) or are not sufficiently well understood, such as obfuscation. Thus, a basic question that has drawn much attention is whether it is possible to construct general-purpose $$\mathsf {NIZK}$$ proof systems based on the learning with errors ( $$\mathsf {LWE}$$ ) assumption.Our main result is a reduction from constructing $$\mathsf {NIZK}$$ proof systems for all of $$\mathbf {NP}$$ based on $$\mathsf {LWE}$$ , to constructing a $$\mathsf {NIZK}$$ proof system for a particular computational problem on lattices, namely a decisional variant of the Bounded Distance Decoding ( $$\mathsf {BDD}$$ ) problem. That is, we show that assuming $$\mathsf {LWE}$$ , every language $$L \in \mathbf {NP}$$ has a $$\mathsf {NIZK}$$ proof system if (and only if) the decisional $$\mathsf {BDD}$$ problem has a $$\mathsf {NIZK}$$ proof system. This (almost) confirms a conjecture of Peikert and Vaikuntanathan (CRYPTO, 2008).To construct our $$\mathsf {NIZK}$$ proof system, we introduce a new notion that we call prover-assisted oblivious ciphertext sampling ( $$\mathsf {POCS}$$ ), which we believe to be of independent interest. This notion extends the idea of oblivious ciphertext sampling, which allows one to sample ciphertexts without knowing the underlying plaintext. Specifically, we augment the oblivious ciphertext sampler with access to an (untrusted) prover to help it accomplish this task. We show that the existence of encryption schemes with a $$\mathsf {POCS}$$ procedure, as well as some additional natural requirements, suffices for obtaining $$\mathsf {NIZK}$$ proofs for $$\mathbf {NP}$$ . We further show that such encryption schemes can be instantiated based on $$\mathsf {LWE}$$ , assuming the existence of a $$\mathsf {NIZK}$$ proof system for the decisional $$\mathsf {BDD}$$ problem.