Blockchain Papers

Joan Boyar, René Peralta

No abstract is available for this record.

Yacov Yacobi, Zahava Shmuely

No abstract is available for this record.

Adi Shamir

No abstract is available for this record.

Mihir Bellare, Shafi Goldwasser

No abstract is available for this record.

Jens Groth, Steve Lu

No abstract is available for this record.

Charles Rackoff, Daniel Simón

No abstract is available for this record.

Toshiya Itoh, Yuji Ohta, Hiroki Shizuya

No abstract is available for this record.

Jens Groth, Rafail Ostrovsky

No abstract is available for this record.

Kazuo Ohta, Tatsuaki Okamoto, Atsushi Fujioka

No abstract is available for this record.

Ivan Damgård

No abstract is available for this record.

Ivan Damgård

No abstract is available for this record.

Tatsuaki Okamoto, David Chaum, Kazuo Ohta

No abstract is available for this record.

Iftach Haitner, Omer Reingold

Interactive hashing, introduced by Naor, Ostrovsky, Venkatesan, and Yung (J. Cryptol. 11(2):87–108, 1998 ), plays an important role in many cryptographic protocols. In particular, interactive hashing is a major component in all known constructions of statistically hiding commitment schemes and of statistical zero-knowledge arguments based on general one-way permutations/functions. Interactive hashing with respect to a one-way function f is a two-party protocol that enables a sender who knows y = f ( x ) to transfer a random hash z = h ( y ) to a receiver such that the sender is committed to y : the sender cannot come up with x and x ′ such that f ( x )≠ f ( x ′), but h ( f ( x ))= h ( f ( x ′))= z . Specifically, if f is a permutation and h is a two-to-one hash function, then the receiver does not learn which of the two preimages { y , y ′}= h −1 ( z ) is the one the sender can invert with respect to f . This paper reexamines the notion of interactive hashing, and proves the security of a variant of the Naor et al. protocol, which yields a more versatile interactive hashing theorem. When applying our new proof to (an equivalent variant of) the Naor et al. protocol, we get an alternative proof for this protocol that seems simpler and more intuitive than the original one, and achieves better parameters (in terms of how security preserving the reduction is).

Hoeteck Wee

No abstract is available for this record.

Hirotada Kobayashi

This paper studies the complexity classes QZK and HVQZK of problems having a quantum computational zero-knowledge proof system and an honest-verifier quantum computational zero-knowledge proof system, respectively. The results proved in this paper include: (a) HVQZK = QZK, (b) any problem in QZK has a public-coin quantum computational zero-knowledge proof system, (c) any problem in QZK has a quantum computational zero-knowledge proof system of perfect completeness, and (d) any problem in QZK has a three-message public-coin quantum computational zero-knowledge proof system of perfect completeness with arbitrarily small constant error in soundness. All the results above are unconditional and do not rely any computational assumptions. For the classes QPZK, HVQPZK, and QSZK of problems having a quantum perfect zero-knowledge proof system, an honest-verifier quantum perfect zero-knowledge proof system, and a quantum statistical zero-knowledge proof system, respectively, the following new properties are proved: (e) HVQPZK = QPZK, (f) any problem in QPZK has a public-coin quantum perfect zero-knowledge proof system, (g) any problem in QSZK has a quantum statistical zero-knowledge proof system of perfect completeness, and (h) any problem in QSZK has a three-message public-coin quantum statistical zero-knowledge proof system of perfect completeness with arbitrarily small constant error in soundness. It is stressed that our proofs are direct and do not use complete promise problems or those equivalents. This gives a unified framework that works well for all of quantum perfect, statistical, and computational zero-knowledge proofs, and enables us to prove properties even on the computational and perfect zero-knowledge proofs for which no complete promise problems are known.

Gilles Brassard, Claude Crépeau

A zero-knowledge interactive proof is a protocol by which Alice can convince a polynomially-bounded Bob of the truth of some theorem without giving him any hint as to how the proof might proceed. Under cryptographic assumptions, we give a general technique for achieving this goal for every problem in NP. This extends to a presumably larger class, which combines the powers of non-determinism and randomness. Our protocol is powerful enough to allow Alice to convince Bob of theorems for which she does not even have a proof: it is enough for Alice to convince herself probabilistically of a theorem, perhaps thanks to her knowledge of some trap-door information, in order for her to be able to convince Bob as well, without compromising the trap-door in any way. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Dario Catalano, Ivan Visconti

No abstract is available for this record.

Gerald V. Post

The current political climate has almost ruled out the use of Internet voting.Many politicians, led by vocal computer scientists, are pushing for voter verified paper receipts; which is likely to push us even further away from even electronic voting systems.On the other hand, cryptographers have created homomorphic encryption and non-interactive zero-knowledge proofs with features that can support Internet voting.Adding a few more protocols, including an extended voting period and repeat voting can solve the remaining problems need to make Internet voting at least as secure as existing systems.

Amitabh Saxena

In this paper, we study the opacity property of verifiably encrypted signatures (VES) of Boneh et al. (proposed in Eurocrypt 2003). Informally, opacity implies that although some given aggregate signatures can verified, no useful information about the individual signatures is leaked. However, the very fact that an aggregate signature can be verified leaks certain information- that the individual signature is indeed well-formed. Apart from this, is there any other information leaked? In this paper, we show that there is absolutely no other information leaked about the individual signatures when the aggregation contains only two signatures. In more formal terms, we show that VES are Zero-Knowledge (ZK). We then extend the ZK property of VES to propose efficient Additive Non-Interactive Witness-Indistinguishable (A-NIWI) proofs. Intuitively an A-NIWI proof can be considered as a Proof of Knowledge (PoK) of another A-NIWI proof. 1

José Cláudio do Nascimento, Rubens Viana Ramos

Zero-knowledge proof system is an important protocol that can be used as a basic block for construction of other more complex cryptographic protocols. An intrinsic characteristic of a zero-knowledge systems is the assumption that is impossible for the verifier to show to a third part that he has interacted with the prover. However, it has been shown that using quantum correlations the impossibility of transferring proofs can be successfully attacked. In this work we show two new protocols for proof transference, being the first one based on teleportation and the second one without using entangled states.

Shien Jin Ong, Salil Vadhan

No abstract is available for this record.

Ivan Damgård, Rune Thorbek

We present two universally composable and practical protocols by which a dealer can, verifiably and non-interactively, secret-share an integer among a set of players. Moreover, at small extra cost and using a distributed verifier proof, it can be shown in zero-knowledge that three shared integers a, b, c satisfy ab = c. This implies by known reductions non-interactive zero-knowledge proofs that a shared integer is in a given interval, or that one secret integer is larger than another. Such primitives are useful, e.g., for supplying inputs to a multiparty computation protocol, such as an auction or an election. The protocols use various set-up assumptions, but do not require the random oracle model.

Yehuda Lindell, Benny Pinkas

Abstract. We show an efficient secure two-party protocol, based on Yao’s construction, which provides security against malicious adversaries. Yao’s original protocol is only secure in the presence of semi-honest adversaries. Security against malicious adversaries can be obtained by applying the compiler of Goldreich, Micali and Wigderson (the “GMW compiler”). However, this approach does not seem to be very practical as it requires using generic zero-knowledge proofs. Our construction is based on applying cut-and-choose techniques to the original circuit and inputs. Security is proved according to the ideal/real simulation paradigm, and the proof is in the standard model (with no random oracle model or common reference string assumptions). The resulting protocol is computationally efficient: the only usage of asymmetric cryptography is for running O(1) oblivious transfers for each input bit (or for each bit of a statistical security parameter, whichever is larger). Our protocol combines techniques from folklore (like cut-and-choose) along with new techniques for efficiently proving consistency of inputs. We remark that a naive implementation of the cut-and-choose technique with Yao’s protocol does not yield a secure protocol. This is the first paper to show how to properly implement these techniques, and to provide a full proof of security. Our protocol can also be interpreted as a constant-round black-box reduction of secure two-party com-putation to oblivious transfer and perfectly-hiding commitments, or a black-box reduction of secure two-party computation to oblivious transfer alone, with a number of rounds which is linear in a sta-tistical security parameter. These two reductions are comparable to Kilian’s reduction, which uses OT alone but incurs a number of rounds which is linear in the depth of the circuit [18]. 1

Ivan Damgård, Jesper Buus Nielsen, Daniel Wichs

We introduce a new notion called `-isolated proofs of knowledge (`-IPoK). These are proofs of knowledge where a cheating prover is allowed to exchange up to ` bits of communication with some external adversarial environment during the run of the proof. Without any additional setup assumptions, no witness hiding protocol can be an `-IPoK for unbounded values of `. However, for any pre-defined threshold `, and any relation in NP and we construct an `-IPoK protocol for that relation. The resulting protocols are zero knowledge (ZK) in the standard sense, i.e., w.r.t. a verifier that communicates only with the prover during the proof. The cost of having a large threshold ` is a large communication complexity of the constructed protocol. We analyze these costs and present a solution that is asymptotically optimal. If a cheating verifier is allowed to communicate arbitrarily with an external environment, it is not possible to construct an `-IPoK that is also ZK with respect to such a verifier. As another new notion, we define `-isolated zero knowledge (`-IZK) where the verifier is `-isolated. For every relation in NP and every `, we construct an `-IPoK protocol that is also `-IZK. We describe several applications of `-IPoK protocols under the physical assumption that one can `isolate a prover for the duration of the proof phase. Firstly, we can use a witness indistinguishable (WI) `-IPoK to prevent “man-in-the-middle” attacks on identification schemes. Prior results for this scenario required all verifiers to register keys under a PKI, or the ability to fully isolate the prover. Secondly, a partially isolated prover can register a public key and use a WI `-IPoK to prove knowledge of the corresponding secret key to another party acting as a verifier. This allows us to set up a PKI where the key registrant does not need to trust the Certificate Authority. The PKI is not perfect since the proof is only witness indistinguishable and not zero knowledge. In a companion paper, we show how to set up such a PKI and use it to implement arbitrary multiparty computation securely in the UC framework without relying on any trusted third parties.