Follow blockchain research across journals, conferences, and preprint repositories.
8,503 results · page 273 of 355
Jan Camenisch, Maria Dubovitskaya, Alfredo Rial
No abstract is available for this record.
Jean Lancrenon, Marjan Škrobot, Qiang Tang
Recently, the password-authenticated key exchange protocol J-PAKE of Hao and Ryan (Workshop on Security Protocols 2008) was formally proven secure in the algebraic adversary model by Abdalla et al. (IEEE S&P 2015). In this paper, we propose and examine two variants of J-PAKE - which we call RO-J-PAKE and CRS-J-PAKE - that each makes the use of two less zero-knowledge proofs than the original protocol. We show that they are provably secure following a similar strategy to that of Abdalla et al. We also study their efficiency as compared to J-PAKE’s, also taking into account how the groups are chosen. Namely, we treat the cases of subgroups of finite fields and elliptic curves. Our work reveals that, for subgroups of finite fields, CRS-J-PAKE is indeed more efficient than J-PAKE, while RO-J-PAKE is much less efficient. On the other hand, when instantiated with elliptic curves, both RO-J-PAKE and CRS-J-PAKE are more efficient than J-PAKE, with CRS-J-PAKE being the best of the three. Regardless of implementation, we note that RO-J-PAKE enjoys a looser security reduction than both J-PAKE and CRS-J-PAKE. CRS-J-PAKE has the tightest security proof, but relies on an additional trust assumption at setup time.
Ai Ishida, Keita Emura, Goichiro Hanaoka, Yusuke Sakai · 5 authors
Group signatures are a class of digital signatures with enhanced privacy. By using this type of signature, a user can sign a message on behalf of a specific group without revealing his identity, but in the case of a dispute, an authority can expose the identity of the signer. However, it is not always the case that we need to know the specific identity of a signature. In this paper, we propose the notion of deniable group signatures, where the authority can issue a proof showing that the specified user is NOT the signer of a signature, without revealing the actual signer. We point out that existing efficient non-interactive zero-knowledge proof systems cannot be straightforwardly applied to prove such a statement. We circumvent this problem by giving a fairly practical construction through extending the Groth group signature scheme (ASIACRYPT 2007). In particular, a denial proof in our scheme consists of 96 group elements, which is about twice the size of a signature in the Groth scheme. The proposed scheme is provably secure under the same assumptions as those of the Groth scheme.
Yuval Ishai, Eyal Kushilevitz, Manoj Prabhakaran, Amit Sahai · 5 authors
In the rich literature of secure multi-party computation MPC, several important results rely on whereby protocols from one model of MPC are transformed to protocols from another model. Motivated by the goal of simplifying and unifying results in the area of MPC, we formalize a general notion of black-box protocol transformations that captures previous transformations from the literature as special cases, and present several new transformations. We motivate our study of protocol transformations by presenting the following applications. Simplifying feasibility results:Easily rederive a result in Goldreich's book 2004, on MPC with full in the presence of an honest majority, from an earlier result in the book, on MPC that offers security with abort.Rederive the classical result of Rabin and Ben-Or 1989 by applying a transformation to the simpler protocols of Ben-Or et al. or Chaum et al. 1988.Efficiency improvements:The first constant-rate MPC protocol for a constant number of parties that offers full information-theoretic with an optimal threshold, improving over the protocol of Rabin and Ben-Or;A fully secure MPC protocol with optimal threshold that improves over a previous protocol of Ben-Sasson et al. 2012 in the case of deep and narrow computations;A fully secure MPC protocol with near-optimal threshold that improves over a previous protocol of Damgard et al. 2010 by improving the dependence on the parameter from linear to polylogarithmic;An efficient new transformation from passive-secure two-party computation in the OT-hybrid and OLE-hybrid model to zero-knowledge proofs, improving over a recent similar transformation of Hazay and Venkitasubramaniam 2016 for the case of static zero-knowledge, which is restricted to the OT-hybrid model and requires a large number of commitments. Finally, we prove the impossibility of two simple types of black-box protocol transformations, including an unconditional variant of a previous negative result of Rosulek 2012 that relied on the existence of one-way functions.
SCN 2016 Amalfi, Vassilis Zikas
No abstract is available for this record.
Eiichiro Fujisaki, Keita Xagawa
No abstract is available for this record.
Antonio Faonio, Daniele Venturi
We revisit the question of constructing public-key encryption and signature schemes with security in the presence of bounded leakage and tampering memory attacks. For signatures we obtain the first construction in the standard model; for public-key encryption we obtain the first construction free of pairing (avoiding non-interactive zero-knowledge proofs). Our constructions are based on generic building blocks, and, as we show, also admit efficient instantiations under fairly standard number-theoretic assumptions.
Philipp Locher, Rolf Haenni, Reto E. Koenig
No abstract is available for this record.
Carsten Baum, Ivan Damgård, Tomas Toft, Rasmus Winther Zakarias
We present techniques and protocols for the preprocessing of secure multiparty computation (MPC), focusing on the so-called SPDZ MPC scheme [19] and its derivatives [16,18,1]. These MPC schemes consist of a so-called preprocessing or offline phase where correlated randomness is generated that is independent of the inputs and the evaluated function, and an online phase where such correlated randomness is consumed to securely and efficiently evaluate circuits. In the recent years, it has been shown that such protocols (such as [4,31,27] ) turn out to be very efficient in practice. While much research has been conducted towards optimizing the online phase of the MPC protocols, there seems to have been less focus on the offline phase of such protocols (except for [16]). With this work, we want to close this gap and give a toolbox of techniques that aim at optimizing the preprocessing. We support both instantiations over small fields and large rings using somewhat homomorphic encryption and the Paillier cryptosystem [34], respectively. In the case of small fields, we show how the preprocessing overhead can basically be made independent of the field characteristic and present a more efficient (amortized) zero-knowledge proof of plaintext knowledge. In the case of large rings, we present a protocol based on the Paillier cryptosystem which has a lower message complexity than previous protocols and employs more efficient zero-knowledge proofs that, to the best of our knowledge, were not presented in previous work.
Geoffroy Couteau, Thomas Peters, David Pointcheval
Committing integers and proving relations between them is an essential ingredient in many cryptographic protocols. Among them, range proofs have shown to be fundamental. They consist in proving that a committed integer lies in a public interval, which can be seen as a particular case of the more general Diophantine relations: for the committed vector of integers x, there exists a vector of integers w such that P (x,w) = 0, where P is a polynomial. In this paper, we revisit the security strength of the statistically hiding commitment scheme over the integers due to Damgard-Fujisaki, and the zero-knowledge proofs of knowledge of openings. Our first main contribution shows how to remove the Strong RSA assumption and replace it by the standard RSA assumption in the security proofs. This improvement naturally extends to generalized commitments and more complex proofs without modifying the original protocols. As a second contribution, we design an interactive technique turning commitment scheme over the integers into commitment scheme modulo a prime p. Still under the RSA assumption, this results in more efficient proofs of relations between committed values. Our methods thus improve upon existing proof systems for Diophantine relations both in terms of performance and security. We illustrate that with more efficient range proofs under the sole RSA assumption.
Andrew Miller
The past several years have seen the surprising and rapid rise of Bitcoin and other “cryptocurrencies.” These are decentralized peer-to-peer networks that allow users to transmit money, tocompose financial instruments, and to enforce contracts between mutually distrusting peers, andthat show great promise as a foundation for financial infrastructure that is more robust, efficientand equitable than ours today. However, it is difficult to reason about the security of cryptocurrencies. Bitcoin is a complex system, comprising many intricate and subtly-interacting protocol layers. At each layer it features design innovations that (prior to our work) have not undergone any rigorous analysis. Compounding the challenge, Bitcoin is but one of hundreds of competing cryptocurrencies in an ecosystem that is constantly evolving. The goal of this thesis is to formally reason about the security of cryptocurrencies, reining in their complexity, and providing well-defined and justified statements of their guarantees. We provide a formal specification and construction for each layer of an abstract cryptocurrency protocol, and prove that our constructions satisfy their specifications. The contributions of this thesis are centered around two new abstractions: “scratch-off puzzles,” and the “blockchain functionality” model. Scratch-off puzzles are a generalization of the Bitcoin “mining” algorithm, its most iconic and novel design feature. We show how to provide secure upgrades to a cryptocurrency by instantiating the protocol with alternative puzzle schemes. We construct secure puzzles that address important and well-known challenges facing Bitcoin today, including wasted energy and dangerous coalitions. The blockchain functionality is a general-purpose model of a cryptocurrency rooted in the “Universal Composability” cryptography theory. We use this model to express a wide range of applications, including transparent “smart contracts” (like those featured in Bitcoin and Ethereum), and also privacy-preserving applications like sealed-bid auctions. We also construct a new protocol compiler, called Hawk, which translates user-provided specifications into privacy-preserving protocols based on zero-knowledge proofs.
Nils Fleischhacker, Johannes Krupp, Giulio Malavolta, Jonas Schneider · 6 authors
A sanitizable signature scheme is a malleable signature scheme where a designated third party has the permission to modify certain parts of the message and adapt the signature accordingly. This primitive was introduced by Ateniese et al . (ESORICS 2005) and Brzuska et al . (PKC 2009) formalized the initially suggested five security properties. In the subsequent year, Brzuska et al . (PKC 2010) introduced a notion called unlinkability where the basic idea is that linking message‐signature pairs of the same document should be infeasible. Brzuska et al . formalized this notion and suggested a generic instantiation based on group signatures with a special structure. Unfortunately, the most efficient instantiations of group signatures do not have this property. In this work, we present the first efficient construction of unlinkable sanitizable signatures based on a novel type of signature schemes with re‐randomizable keys. This property allows one to re‐randomize both the signing and the verification key separately but consistently. Given a signature scheme with re‐randomizable keys, we obtain a sanitizable signature scheme by signing the message with a re‐randomized key and proving in zero‐knowledge that the derived key originates from either the signer or the sanitizer. To obtain an efficient instantiation, we instantiate this generic idea with Schnorr signatures and efficient ‐protocols that we turn into a non‐interactive zero‐knowledge proof via the Fiat‐Shamir transformation. In this work, we present an optimized version that is more efficient than the construction we suggested in the extended abstract of this work at PKC 2016.
Olivier Blazy, David Derler, Daniel Slamanig, Raphael Spreitzer
No abstract is available for this record.
Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, Malika Izabachène
No abstract is available for this record.
Carsten Baum, Ivan Damgård, Kasper Green Larsen, Michael B. Nielsen
No abstract is available for this record.
Benny Applebaum, Pavel Raykov
No abstract is available for this record.
M. Albrecht, Lorenzo Grassi, Christian Rechberger, Arnab Roy · 5 authors
No abstract is available for this record.
Yong Yu, Yannan Li, Man Ho Au, Willy Susilo · 6 authors
No abstract is available for this record.
Helger Lipmaa
Succinct non-interactive zero-knowledge arguments of knowledge (Zk-SNARKs) are needed in many applications. Unfortunately, all previous zk-SNARKs for interesting languages are either inefficient for the prover, or are non-adaptive and based on a commitment scheme that depends both on the prover's input and on the language, i.e., they are not commit-and-prove (CaP) SNARKs. We propose a proof-friendly extractable commitment scheme, and use it to construct prover-efficient adaptive CaP succinct zk-SNARKs for different languages, that can all reuse committed data. In new zk-SNARKs, the prover computation is dominated by a linear number of cryptographic operations. We use batch-verification to decrease the verifier's computation; importantly, batch-verification can be used also in QAP-based zk-SNARKs.
Eli Ben‐Sasson, Alessandro Chiesa, Michael A. Forbes, Ariel Gabizon · 6 authors
We study the problem of constructing proof systems that achieve both soundness and zero knowledge unconditionally (without relying on intractability assumptions). Known techniques for this goal are primarily combinatorial, despite the fact that constructions of interactive proofs (IPs) and probabilistically checkable proofs (PCPs) heavily rely on algebraic techniques to achieve their properties.
Carsten Baum, Ivan Damgård, Vadim Lyubashevsky, Sabine Oechsner · 5 authors
We present a practical construction of an additively homomorphic commitment scheme based on structured lattice assumptions, together with a zero-knowledge proof of opening knowledge. Our scheme is a design improvement over the previous work of Benhamouda et al. in that it is not restricted to being statistically binding. While it is possible to instantiate our scheme to be statistically binding or statistically hiding, it is most efficient when both hiding and binding properties are only computational. This results in approximately a factor of 4 reduction in the size of the proof and a factor of 6 reduction in the size of the commitment over the aforementioned scheme.
Esha Ghosh, Olga Ohrimenko, Dimitrios Papadopoulos, Roberto Tamassia · 5 authors
Cryptographic accumulators allow to succinctly represent a set by an accumulation value with respect to which short non-membership proofs about the set can be efficiently constructed and verified. Traditionally, their security captures soundness but offers no privacy: Convincing proofs reliably encode set membership, but they may well leak information about the accumulated set. In this paper we put forward a strong privacy-preserving enhancement by introducing and devising zero-knowledge accumulators that additionally provide hiding guarantees: Accumulation values and proofs leak nothing about a dynamic set that evolves via element insertions/deletions. We formalize the new property using the standard real-ideal paradigm, namely demanding that an adaptive adversary with access to query/update oracles, cannot tell whether he interacts with honest protocol executions or a simulator fully ignorant of the set even of the type of updates on it. We rigorously compare the new primitive to existing ones for privacy-preserving verification of set membership or other relations and derive interesting implications among related security definitions, showing that zero-knowledge accumulators offer stronger privacy than recent related works by Naor et al. [TCCi¾?2015] and Derler et al. [CT-RSAi¾?2015]. We construct the first dynamic universal zero-knowledge accumulator that we show to be perfect zero-knowledge and secure under the q-Strong Bilinear Diffie-Hellman assumption. Finally, we extend our new privacy notion and our new construction to provide privacy-preserving proofs also for an authenticated dynamic set collection--a primitive for efficiently verifying more elaborate set operations, beyond set-membership. We introduce a primitive that supports a zero-knowledge verifiable set algebra: Succinct proofs for union, intersection and set difference queries over a dynamically evolving collection of sets can be efficiently constructed and optimally verified, while--for the first time--they leak nothing about the collection beyond the query result.
Benoît Libert, San Ling, Fabrice Mouhartem, Khoa Nguyen · 5 authors
Abstract Group encryption ( GE ) is the natural encryption analogue of group signatures in that it allows verifiably encrypting messages for some anonymous member of a group while providing evidence that the receiver is a properly certified group member. Should the need arise, an opening authority is capable of identifying the receiver of any ciphertext. As introduced by Kiayias, Tsiounis and Yung (Asiacrypt'07), GE is motivated by applications in the context of oblivious retriever storage systems, anonymous third parties and hierarchical group signatures. This paper provides the first realization of group encryption under lattice assumptions. Our construction is proved secure in the standard model (assuming interaction in the proving phase) under the Learning-With-Errors ( LWE ) and Short-Integer-Solution ( SIS ) assumptions. As a crucial component of our system, we describe a new zero-knowledge argument system allowing to demonstrate that a given ciphertext is a valid encryption under some hidden but certified public key, which incurs to prove quadratic statements about LWE relations. Specifically, our protocol allows arguing knowledge of witnesses consisting of X ∈ Z q m × n , s ∈ Z q n and a small-norm e ∈ Z m which underlie a public vector b = X ⋅ s + e ∈ Z q m while simultaneously proving that the matrix X ∈ Z q m × n has been correctly certified. We believe our proof system to be useful in other applications involving zero-knowledge proofs in the lattice setting.
Jens Groth
No abstract is available for this record.