Follow blockchain research across journals, conferences, and preprint repositories.
972 results · page 19 of 41
Sanjam Garg, Mohammad Hajiabadi, Mohammad Mahmoody, Ameer Mohammed
No abstract is available for this record.
Yael Tauman Kalai, Dakshita Khurana, Amit Sahai
No abstract is available for this record.
Seongseop Kim, David J. Wu
Non-interactive zero-knowledge (NIZK) proofs are fundamental to modern cryptography. Numerous NIZK constructions are known in both the random oracle and the common reference string (CRS) models. In the CRS model, there exist constructions from several classes of cryptographic assumptions such as trapdoor permutations, pairings, and indistinguishability obfuscation. However, at the time of the initial publication of this work, we did not have constructions of NIZKs from standard lattice assumptions. In this work, we take an initial step toward constructing multi-theorem NIZKs for general $$\mathsf {NP}$$ languages from standard lattice assumptions by considering a relaxation to the preprocessing model and a new model we call the designated-prover model. In the preprocessing model, a setup algorithm generates secret proving and verification keys for the prover and the verifier, respectively. In the designated-prover model, the proving key is secret, but the verification key is public. In both settings, the proving key is used to construct proofs and the verification key is used to check proofs. Finally, in the multi-theorem setting, both the proving and verification keys should be reusable for an unbounded number of theorems without compromising soundness or zero-knowledge. Previous constructions of NIZKs in the preprocessing model that rely on weaker assumptions like one-way functions or oblivious transfer are only secure in a single-theorem setting. Thus, constructing multi-theorem NIZKs in these relaxed models does not seem to be inherently easier than constructing them in the CRS model. In this work, we first construct a multi-theorem preprocessing NIZK argument from context-hiding homomorphic signatures. In fact, the construction is a designated-prover NIZK. We also show that using homomorphic commitments, we can get statistically sound proofs in the preprocessing and designated-prover models. Together with lattice-based instantiations of homomorphic signatures and commitments, we obtain the first multi-theorem NIZKs in the preprocessing and designated-prover models from standard lattice assumptions. Finally, we show how to generalize our construction to obtain a universally composable NIZK (UC-NIZK) in the preprocessing model from standard lattice assumptions. Our UC-NIZK relies on a simple preprocessing protocol based on a new primitive we call blind homomorphic signatures.
Ai Ishida, Yusuke Sakai, Keita Emura, Goichiro Hanaoka · 5 authors
No abstract is available for this record.
Fucai Luo, Kunpeng Wang
No abstract is available for this record.
Melissa Chase, Yevgeniy Dodis, Yuval Ishai, Daniel Kraschewski · 7 authors
We consider the problem of Non-Interactive Two-Party Secure Computation (NISC), where Rachel wishes to publish an encryption of her input x, in such a way that any other party, who holds an input y, can send her a single message which conveys to her the value f(x, y), and nothing more. We demand security against malicious parties. While such protocols are easy to construct using garbled circuits and general non-interactive zero-knowledge proofs, this approach inherently makes a non-black-box use of the underlying cryptographic primitives and is infeasible in practice.
Navid Alamati, Chris Peikert, Noah Stephens-Davidowitz
No abstract is available for this record.
Chloé Hébant, Duong Hieu Phan, David Pointcheval
Since the seminal paper on Fully Homomorphic Encryption (FHE) by Gentry in 2009, a lot of work and improvements have been proposed, with an amazing number of possible applications. It allows outsourcing any kind of computations on encrypted data, and thus without leaking any information to the provider who performs the computations. This is quite useful for many sensitive data (finance, medical, etc.).
Ben Berger, Zvika Brakerski
No abstract is available for this record.
Eli Ben‐Sasson, Alessandro Chiesa, Michael Riabzev, Nicholas Spooner · 6 authors
We design, implement, and evaluate a zero knowledge succinct non-interactive argument (SNARG) for Rank-1 Constraint Satisfaction (R1CS), a widely-deployed NP language undergoing standardization. Our SNARG has a transparent setup, is plausibly post-quantum secure, and uses lightweight cryptography. A proof attesting to the satisfiability of n constraints has size \(O(\log ^2 n)\); it can be produced with \(O(n \log n)\) field operations and verified with O(n). At 128 bits of security, proofs are less than \({250}\,\mathrm{kB}\) even for several million constraints, more than \(10{\times }\) shorter than prior SNARGs with similar features.
Chaya Ganesh, Yashvanth Kondi, Arpita Patra, Pratik Sarkar
No abstract is available for this record.
Jonathan Bootle, Jens Groth
No abstract is available for this record.
Fabrice Benhamouda, Olivier Blazy, Léo Ducas, Willy Quach
No abstract is available for this record.
Benoît Libert, San Ling, Khoa Nguyen, Huaxiong Wang
No abstract is available for this record.
Carsten Baum, Jonathan Bootle, Andrea Cerulli, Rafaël del Pino · 6 authors
No abstract is available for this record.
Nils Fleischhacker, Vipul Goyal, Abhishek Jain
We study the round complexity of zero-knowledge (ZK) proof systems. While five round ZK proofs for \({\mathsf {NP}}\) are known from standard assumptions [Goldreich-Kahan, J. Cryptology’96], Katz [TCC’08] proved that four rounds are insufficient for this task w.r.t. black-box simulation. In this work, we study the feasibility of ZK proofs using non-black-box simulation. Our main result is that three round private-coin ZK proofs for \({\mathsf {NP}}\) do not exist (even w.r.t. non-black-box simulation), under certain assumptions on program obfuscation. Our approach builds upon the recent work of Kalai et al. [Crypto’17] who ruled out constant round public-coin ZK proofs under the same assumptions as ours.
Jonathan Bootle, Andrea Cerulli, Jens Groth, S. Jakobsen · 5 authors
No abstract is available for this record.
Shashank Agrawal, Chaya Ganesh, Payman Mohassel
The two most common ways to design non-interactive zero-knowledge (NIZK) proofs are based on Sigma protocols and QAP-based SNARKs. The former is highly efficient for proving algebraic statements while the latter is superior for arithmetic representations.
Gregory Maxwell, Andrew Poelstra, Yannick Seurin, Pieter Wuille
We describe a new Schnorr-based multi-signature scheme (i.e., a protocol which allows a group of signers to produce a short, joint signature on a common message) called $$\mathsf {MuSig}$$ , provably secure under the Discrete Logarithm assumption and in the plain public-key model (meaning that signers are only required to have a public key, but do not have to prove knowledge of the private key corresponding to their public key to some certification authority or to other signers before engaging the protocol). $$\mathsf {MuSig}$$ improves over the state-of-art scheme of Bellare and Neven (ACM Conference on Computer and Communications Security-CCS 2006) and its variants by Bagherzandi et al. (ACM Conference on Computer and Communications Security-CCS 2008) and Ma et al. (Des Codes Cryptogr 54(2):121–133, 2010) in two respects: (i) it is simple and efficient, having the same key and signature size as standard Schnorr signatures; (ii) it allows key aggregation, which informally means that the joint signature can be verified exactly as a standard Schnorr signature with respect to a single “aggregated” public key which can be computed from the individual public keys of the signers. To the best of our knowledge, this is the first multi-signature scheme provably secure under the Discrete Logarithm assumption in the plain public-key model which allows key aggregation. As an application, we explain how our new multi-signature scheme could improve both performance and user privacy in Bitcoin.
Dan Boneh, Manu Drijvers, Gregory Neven
No abstract is available for this record.
Areej M. Abduldaim, Jumana Waleed, Arbah S. Abdul-Kareem, Maiada N. Mohmmedali
A zero knowledge proof is a type of authentication scheme, which gives no knowledge beyond the authenticity for identifying an entity. Ring theory plays an important role in designing of a novel algorithm for zero knowledge proof through using of a particular class of non-commutative rings. In this article, we employ the notion of nil 3-Armendariz rings to plan a new algorithm for zero knowledge proof. Our main approach is to build the algebraic structure of the zero knowledge proof depends on the stipulation in the definition of the nil 3-Armendariz rings. The proposed protocol is clarified via numerical simulation example, and its soundness and completeness are evidenced. Finally, we found that the proposed protocol satisfies the completeness, the soundness in the sense that, there is 50% chance of catching a cheating prove, and the proposed protocol has the property of zero knowledge.
Charles F. de Barros
In this paper, we propose a zero-knowledge proof for a special case of the hidden subset sum problem. This problem was presented by [Boyko et al. 1998] as the underlying problem of methods for generating random pairs of the form (x, gx (mod p)) using precomputations. The proof we propose is an adaptation of a zero-knowledge protocol for the subset sum problem presented by [Blocki 2009].
Joshua Lockhart, Carlos E. González-Guillén
We consider a problem we call StateIsomorphism: given two quantum states of n qubits, can one be obtained from the other by rearranging the qubit subsystems? Our main goal is to study the complexity of this problem, which is a natural quantum generalisation of the problem StringIsomorphism. We show that StateIsomorphism is at least as hard as GraphIsomorphism, and show that these problems have a similar structure by presenting evidence to suggest that StateIsomorphism is an intermediate problem for QCMA. In particular, we show that the complement of the problem, StateNonIsomorphism, has a two message quantum interactive proof system, and that this proof system can be made statistical zero-knowledge. We consider also StabilizerStateIsomorphism (SSI) and MixedStateIsomorphism (MSI), showing that the complement of SSI has a quantum interactive proof system that uses classical communication only, and that MSI is QSZK-hard.
Christian Badertscher, Sandro Coretti, Chen-Da Liu-Zhang, Ueli Maurer
Commitment schemes that admit zero-knowledge proofs for relations among committed values are known as commit-and-prove functionalities or notarized envelopes. An important role in this context play equality proofs among commitments. They appear in various contexts of multi-party computation, circuit satisfiability or inclusion proofs. Using commit- and-prove functionalities admitting equality, we investigate blackbox constructions of commit-and-prove functionalities admitting more complex relations. Typically, these constructions have to create commitments to additional values to achieve a certain level of soundness. An important efficiency measure is the number of such additional commitments. We prove that, for the natural and quite general class of 3-round public-coin zero-knowledge protocols, implementing the inequality relation, or any of the relations NAND, NOR, or XOR, essentially requires at least 2n additional commitments in order to achieve a soundness of 2-n. A folklore protocol shows that this bound is tight for inequality.