Blockchain Papers

Ning Ding

No abstract is available for this record.

Susumu Kiyoshima

We give a new proof of the existence of public-coin concurrent zero-knowledge arguments for NP in the plain model under standard assumptions (the existence of one-to-one one-way func-tions and collision-resistant hash functions), which was originally proven by Goyal (STOC’13). In the proof, we use a new variant of the non-black-box simulation technique of Barak (FOCS’01). An important property of our simulation technique is that the simulator runs in a straight-line manner in the fully concurrent setting. Compared with the simulation technique of Goyal, which also has such a property, the analysis of our simulation technique is (arguably) simpler. This article is a minor revision of the version that appears in the proceedings of TCC 2015. 1

Raza Ali Kazmi

In this thesis we present our contribution in the field of post-quantum cryptography. We introduce a new notion of weakly Random-Self-Reducible public-key cryptosystem and show how it can be used to implement secure Oblivious Transfer. We also show that two recent (Post-quantum) cryptosystems can be considered as weakly Random-Self-Reducible. We introduce a new problem called Isometric Lattice Problem and reduce graph isomorphism and linear code equivalence to this problem. We also show that this problem has a perfect zero-knowledge interactive proof with respect to a malicious verifier; this is the only hard problem in lattices that is known to have this property.

Goutam Paul

No abstract is available for this record.

Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti

In this work, we show how to use the positive results on succinct argument systems to prove impossibility results on leakage-resilient black-box zero knowledge. This recently proposed notion of zero knowledge deals with an adversary that can make leakage queries on the state of the prover. Our result holds for black-box simulation only and we also give some insights on the non-black-box case. Additionally, we show that, for several functionalities, leakage-resilient multi-party computation is impossible (regardless of the number of players and even if just one player is corrupted). More in details, we achieve the above results by extending a technique of [Nielsen, Venturi, Zottarel – PKC 13] to prove lower bounds for leakage-resilient security. Indeed, we use leakage queries to run an execution of a communication-efficient protocol in the head of the adversary. Moreover, to defeat the black-box simulator we connect the above technique for leakage resilience to security against reset attacks. Our results show that the open problem of [Ananth, Goyal, Pandey – Crypto 14] (i.e., continual leakage-resilient proofs without a common reference string) has a negative answer when security through black-box simulation is desired. Moreover our results close the open problem of [Boyle et al. – STOC 12] for the case of black-box simulation (i.e., the possibility of continual leakage-resilient secure computation without a leak-free interactive preprocessing).

Yusuke Sakai, Keita Emura, Jacob C. N. Schuldt, Goichiro Hanaoka · 5 authors

No abstract is available for this record.

Ruizhong Chen, Lihao Wei, Hong Zou, Meijie Zhai

Project development in a power enterprise always needs to authorize external devices access to the enterprise intranet for testing. In order to avoid an external device with a virus and pose a security risk to the power information system, external devices should have strict security assessment before access the enterprise intranet. But after the security assessment, the device user still be possible to change the platform configuration. Remote attestation is one of important measures when two sides need to communicate. It is concernful to attest the remote platform is trusty but not revealing the any private information of the platform. For this reason, we designed a novel remote anonymous attestation protocol based on TCM. The proposed protocol does not need extra zero knowledge proof and the involvement of the third trusted party and the composite signature scheme is proved secure against existential forgery on adaptively chosen message. So this protocol has better security and execution property.

Rémy Chrétien, Véronique Cortier, Stéphanie Delaune

No abstract is available for this record.

Ning Ding

No abstract is available for this record.

Michael Brenner, Nicolas Christin, Diana Johnson, Kurt Rohloff

No abstract is available for this record.

Shweta Agrawal, Yuval Ishai, Dakshita Khurana, Anat Paskin-Cherniavsky

No abstract is available for this record.

Yan Cao

As for the security of digital signature,this paper takes advantage of the discrete logarithm problem and zeroknowledge proof protocol,combines with( t,n) threshold signature scheme and the identity of the participants,and presents a digital signature scheme based on secret sharing. In the scheme,there is no trusted key distribution center,and the secret share of the participants is generated by the participants themselves and can be used repeatedly,furthermore,the identity of the participants is generated by their own secret share. Only the public information can be updated,which will not affect the participants' secret share. Anyone can detect whether the dealer is cheating the participants or whether there is cheating between participants. Only the authorized subset client can represent group to sign; the generation and verification of the partial signature and group signature are effective. The discrete logarithm problem and zero-knowledge proof protocol guarantees the security of information transmission,which further improves the security of the scheme. The analysis indicates that the scheme is safe and efficient.

David C. Parkes, C. Thorpe, Wei Li

Can an exchange be “dark,” so that orders are not displayed, while simultaneously trustworthy, so that the execution of trades and flow of information occur as promised? SEC actions against dark pools suggest cause for concern, and regulators seem to be moving towards requiring more disclosure. Yet there is a clear tension: trading order information is widely exploited. Therefore, institutional investors have a strong interest in keeping pre-trade information about large trades hidden. Secrecy-preserving proofs of correctness can be used to build trust without revealing unnecessary information. By performing operations on obfuscated representations of orders (perhaps encrypted or otherwise hidden), a zero knowledge proof can be provided, allowing anyone to verify correctness of trades. Crucially, this can be done without revealing any information beyond this correctness. This technology can be usefully applied to construct provably trustworthy dark pools. Additional practical protocols relax the definition of “zero knowledge" to reveal limited information, providing necessary transparency for efficient market operation while limiting information that can be exploited by observers. Coupled with Trusted Computing hardware, these protocols can provide an excellent balance of practicality with secrecy

Benny Applebaum, Yuval Ishai, Eyal Kushilevitz, Brent Waters

Randomized encodings of functions can be used to replace a “complex” function $f(x)$ by a “simpler” randomized mapping $\hat{f}(x;r)$ whose output distribution on an input $x$ encodes the value of $f(x)$ and hides any other information about $x$. One desirable feature of randomized encodings is low online complexity. That is, the goal is to obtain a randomized encoding $\hat{f}$ of $f$ in which most of the output can be precomputed and published before seeing the input $x$. When the input $x$ is available, it remains to publish only a short string $\hat{x}$, where the online complexity of computing $\hat{x}$ is independent of (and is typically much smaller than) the complexity of computing $f$. Yao's garbled circuit construction gives rise to such randomized encodings in which the online part $\hat{x}$ consists of $n$ encryption keys of length $\kappa$ each, where $n=|x|$ and $\kappa$ is a security parameter. Thus, the online rate $|\hat{x}|/|x|$ of this encoding is proportional to the security parameter $\kappa$. In this paper, we show that the online rate can be dramatically improved. Specifically, we show how to encode any polynomial-time computable function $f:\{0,1\}^n\to\{0,1\}^{m(n)}$ with online rate of $1+o(1)$ and with nearly linear online computation. More concretely, the online part $\hat{x}$ consists of an $n$-bit string and a single encryption key. These constructions can be based on the decisional Diffie--Hellman (DDH) assumption, the learning with errors (LWE) assumption, or the RSA assumption. We also present a variant of this result which applies to arithmetic formulas, where the encoding only makes use of arithmetic operations, as well as several negative results which complement our positive results. Our positive results can lead to efficiency improvements in most contexts where randomized encodings of functions are used. We demonstrate this by presenting several concrete applications. These include protocols for secure multiparty computation and for noninteractive verifiable computation in the preprocessing model which achieve, for the first time, an optimal online communication complexity, as well as noninteractive zero-knowledge proofs which simultaneously minimize the online communication and the prover's online computation.

Francisco Martín-Fernández, Pino Caballero‐Gil, Cándido Caballero‐Gil

No abstract is available for this record.

Pratish Datta, Ratna Dutta, Sourav Mukhopadhyay

Abstract. Functional encryption (FE) enables sophisticated control over decryption rights in a multi-user scenario, while functional signature (FS) allows to enforce complex constraints on sign-ing capabilities. This paper introduces the concept of functional signcryption (FSC) that aims to provide the functionalities of both FE and FS in an unified cost-effective primitive. FSC provides a solution to the problem of achieving confidentiality and authenticity simultaneously in digital communication and storage systems involving multiple users with better efficiency compared to a sequential implementation of FE and FS. We begin by providing formal definition of FSC and formu-lating its security requirements. Next, we present a generic construction of this challenging primitive that supports arbitrary polynomial-size signing and decryption functions from known cryptographic building blocks, namely, indistinguishability obfuscation (IO) and statistically simulation-sound non-interactive zero-knowledge proof of knowledge (SSS-NIZKPoK). Finally, we exhibit a number of rep-resentative applications of FSC: (I) We develop the first construction of attribute-based signcryption (ABSC) supporting signing and decryption policies representable by general polynomial-size circuits from FSC. (II) We show how FSC can serve as a tool for building SSS-NIZKPoK system and IO, a result which in conjunction with our generic FSC construction can also be interpreted as establishing an equivalence between FSC and the other two fundamental cryptographic primitives.

Ben Fisch, Daniel Freund, Moni Naor

Abstract. In a secure physical computation, a set of parties each have physical inputs and jointly compute a function of their inputs in a way that reveals no information to any party except for the output of the function. Recent work in CRYPTO’14 presented examples of physical zero-knowledge proofs of physical properties, a special case of secure physical two-party computation in which one party has a physical input and the second party verifies a boolean function of that input. While the work suggested a general framework for modeling and analyzing physi-cal zero-knowledge protocols, it did not provide a general theory of how to prove any physical property with zero-knowledge. This paper takes an orthogonal approach using disposable circuits (DC)—cheap hardware tokens that can be completely destroyed after a computation—an ex-tension of the familiar tamper-proof token model. In the DC model, we demonstrate that two parties can compute any function of their physical inputs in a way that leaks at most 1 bit of additional information to either party. Moreover, our result generalizes to any multi-party physical computation. Formally, our protocols achieve unconditional UC-security with input-dependent abort. 1

David Derler, Christian Hanser, Daniel Slamanig

No abstract is available for this record.

Nir Bitansky, Omer Paneth

The introduction of a non-black-box simulation technique by Barak (FOCS 2001) has been a major landmark in cryptography, breaking the previous barriers of black-box impossibility. Barak's technique has given rise to various powerful applications and is a key component in all known protocols with non-black-box simulation. We present the first non-black-box simulation technique that does not rely on Barak's technique (or on nonstandard assumptions). Invoking this technique, we obtain new and improved protocols resilient to various resetting attacks. These improvements include weaker computational assumptions and better round complexity. A prominent feature of our technique is its compatibility with rewinding techniques from classic black-box zero-knowledge protocols. The combination of rewinding with non-black-box simulation has proven instrumental in coping with challenging goals such as simultaneously resettable zero-knowledge, proofs of knowledge, and resettable security from one-way functions. While previous works required tailored modifications to Barak's technique, we give a general recipe for combining our technique with rewinding. This yields simplified resettable protocols in the above settings, as well as improvements in round complexity and required computational assumptions. The main ingredient in our technique is a new impossibility result for general program obfuscation. The results extend the impossibility result of Barak et al. (CRYPTO 2001) to the case of obfuscation with approximate functionality, thus settling a question left open by Barak et al. In the converse direction, we show a generic transformation from any resettably sound zero-knowledge protocol to a family of functions that cannot be obfuscated.

Sanjam Garg, Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky · 5 authors

No abstract is available for this record.

Ilias Giechaskiel

The Bitcoin cryptocurrency relies heavily on a variety of cryptographic functions and operations, which are currently assumed to be secure, but will inevitably be broken in the future. As Bitcoin tries to compete against traditional currencies, it remains to be seen how the Bitcoin protocol will need to change in response to weakened cryptography. To this end, this study systematically evaluates the effects of broken cryptographic primitives on the operation of the Bitcoin network, and the changes to the Bitcoin protocol that will be necessary in response. We conclude that a broken hash function only requires switching over to a new hash function, without the need to re-write the blockchain, and is well serviced by the “checkpoint” mechanisms already built into Bitcoin. However, a vulnerability of the signature scheme cannot be dealt with in the same manner without side-e.ects, as it may lead to lost or stolen coins, even if the process is gradual and is conducted before the cryptographic primitive is broken. We conclude that solving this problem either requires some degree of centralization, or the use of Zero-Knowledge Proofs along or on top of Bitcoin.

Benoît Libert, Thomas Peters, Marc Jóye, Moti Yung

No abstract is available for this record.

Phong Q. Nguyễn, Jiang Zhang, Zhenfeng Zhang

No abstract is available for this record.

Michele Ciampi, Giuseppe Persiano, Luisa Siniscalchi, Ivan Visconti

The Fiat-Shamir (FS) transform is a popular technique for obtaining practical zero-knowledge argument systems. The FS transform uses a hash function to generate, without any further over-head, non-interactive zero-knowledge (NIZK) argument systems from public-coin honest-verifier zero-knowledge (public-coin HVZK) proof systems. In the proof of zero knowledge, the hash function is modeled as a programmable random oracle (PRO). In TCC 2015, Lindell embarked on the challenging task of obtaining a similar transform with improved heuristic security. Lindell showed that, for several interesting and practical languages, there exists an efficient transform in the non-programmable random oracle (NPRO) model that also uses a common reference string (CRS). A major contribution of Lindell’s transform is that zero knowledge is proved without random oracles and this is an important step towards achieving efficient NIZK arguments in the CRS model without random oracles. In this work, we analyze the efficiency and generality of Lindell’s transform and notice a significant gap when compared with the FS transform. We then propose a new transform that aims at filling this gap. Indeed our transform is almost as efficient as the FS transform and can be applied to a broad class of public-coin HVZK proof systems. Our transform requires a CRS and an NPRO in the proof of soundness, similarly to Lindell’s transform. 1