International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Adam Sealfon

Affiliation: MIT

Publications

Year
Venue
Title
2019
PKC
Towards Non-Interactive Zero-Knowledge for NP from LWE
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.
2019
CRYPTO
It Wasn’t Me! 📺
Sunoo Park Adam Sealfon
Ring signatures, introduced by [RST01], are a variant of digital signatures which certify that one among a particular set of parties has endorsed a message while hiding which party in the set was the signer. Ring signatures are designed to allow anyone to attach anyone else’s name to a signature, as long as the signer’s own name is also attached. But what guarantee do ring signatures provide if a purported signatory wishes to denounce a signed message—or alternatively, if a signatory wishes to later come forward and claim ownership of a signature? Prior security definitions for ring signatures do not give a conclusive answer to this question: under most existing definitions, the guarantees could go either way. That is, it is consistent with some standard definitions that a non-signer might be able to repudiate a signature that he did not produce, or that this might be impossible. Similarly, a signer might be able to later convincingly claim that a signature he produced is indeed his own, or not. Any of these guarantees might be desirable. For instance, a whistleblower might have reason to want to later claim an anonymously released signature, or a person falsely implicated in a crime associated with a ring signature might wish to denounce the signature that is framing them and damaging their reputation. In other circumstances, it might be desirable that even under duress, a member of a ring cannot produce proof that he did or did not sign a particular signature. In any case, a guarantee one way or the other seems highly desirable.In this work, we formalize definitions and give constructions of the new notions of repudiable, unrepudiable, claimable, and unclaimable ring signatures. Our repudiable construction is based on VRFs, which are implied by several number-theoretic assumptions (including strong RSA or bilinear maps); our claimable construction is a black-box transformation from any standard ring signature scheme to a claimable one; and our unclaimable construction is derived from the lattice-based ring signatures of [BK10], which rely on hardness of SIS. Our repudiable construction also provides a new construction of standard ring signatures.
2016
CRYPTO