Blockchain Papers

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.

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.

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.

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.

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.

Irene Giacomelli, Jesper Madsen, Claudio Orlandi

In this paper we describe ZKBoo ¹, a proposal for practically efficient zero-knowledge arguments especially tailored for Boolean circuits and report on a proof-of-concept implementation. As an highlight, we can generate (resp. verify) a non-interactive proof for the SHA-1 circuit in approximately 13ms (resp. 5ms), with a proof size of 444KB. Our techniques are based on the “MPC-in-the-head” approach to zero-knowledge of Ishai et al. (IKOS), which has been successfully used to achieve significant asymptotic improvements. Our contributions include: ◦ A thorough analysis of the different variants of IKOS, which highlights their pros and cons for practically relevant soundness parameters; ◦ A generalization and simplification of their approach, which leads to faster Σ-protocols (that can be made non-interactive using the Fiat-Shamir heuristic) for statements of the form “I know x such that y = φ(x)” (where φ is a circuit and y a public value); ◦ A case study, where we provide explicit protocols, implementations and benchmarking of zero-knowledge protocols for the SHA-1 and SHA-256 circuits.

Benoît Libert, San Ling, Khoa Nguyen, Huaxiong Wang

Abstract An accumulator is a function that hashes a set of inputs into a short, constant-size string while preserving the ability to efficiently prove the inclusion of a specific input element in the hashed set. It has proved useful in the design of numerous privacy-enhancing protocols, in order to handle revocation or simply prove set membership. In the lattice setting, currently known instantiations of the primitive are based on Merkle trees, which do not interact well with zero-knowledge proofs. In order to efficiently prove the membership of some element in a zero-knowledge manner, the prover has to demonstrate knowledge of a hash chain without revealing it, which is not known to be efficiently possible under well-studied hardness assumptions. In this paper, we provide an efficient method of proving such statements using involved extensions of Stern’s protocol. Under the Small Integer Solution assumption, we provide zero-knowledge arguments showing possession of a hash chain. As an application, we describe new lattice-based group and ring signatures in the random oracle model. In particular, we obtain: (i) the first lattice-based ring signatures with logarithmic size in the cardinality of the ring and (ii) the first lattice-based group signature that does not require any GPV trapdoor and thus allows for a much more efficient choice of parameters.

Xavier Bultel, Jannik Dreier, Jean‐Guillaume Dumas, Pascal Lafourcade

Akari, Takuzu, Kakuro and KenKen are logic games similar to Sudoku. In Akari, a labyrinth on a grid has to be lit by placing lanterns, respecting various constraints. In Takuzu a grid has to be filled with 0's and 1's, while respecting certain constraints. In Kakuro a grid has to be filled with numbers such that the sums per row and column match given values; similarly in KenKen a grid has to be filled with numbers such that in given areas the product, sum, difference or quotient equals a given value. We give physical algorithms to realize zero-knowledge proofs for these games which allow a player to show that he knows a solution without revealing it. These interactive proofs can be realized with simple office material as they only rely on cards and envelopes. Moreover, we formalize our algorithms and prove their security.

Broadbent Anne, Zhengfeng Ji, Song Fang, Watrous John

Prior work has established that all problems in NP admit classical zero-knowledge proof systems, and under reasonable hardness assumptions for quantum computations, these proof systems can be made secure against quantum attacks. We prove a result representing a further quantum generalization of this fact, which is that every problem in the complexity class QMA has a quantum zero-knowledge proof system. More specifically, assuming the existence of an unconditionally binding and quantum computationally concealing commitment scheme, we prove that every problem in the complexity class QMA has a quantum interactive proof system that is zero-knowledge with respect to efficient quantum computations. Our QMA proof system is sound against arbitrary quantum provers, but only requires an honest prover to perform polynomial-time quantum computations, provided that it holds a quantum witness for a given instance of the QMA problem under consideration. The proof system relies on a new variant of the QMA-complete local Hamiltonian problem in which the local terms are described by Clifford operations and standard basis measurements. We believe that the QMA-completeness of this problem may have other uses in quantum complexity.

Benny Applebaum, Pavel Raykov

No abstract is available for this record.

M. Albrecht, Pooya Farshim, Shuai Han, Dennis Hofheinz · 6 authors

Abstract We provide constructions of multilinear groups equipped with natural hard problems from indistinguishability obfuscation, homomorphic encryption, and NIZKs. This complements known results on the constructions of indistinguishability obfuscators from multilinear maps in the reverse direction. We provide two distinct, but closely related constructions and show that multilinear analogues of the $${\text {DDH}} $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mtext>DDH</mml:mtext></mml:math> assumption hold for them. Our first construction is symmetric and comes with a $$\kappa $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>κ</mml:mi></mml:math> -linear map $$\mathbf{e }: {{\mathbb {G}}}^\kappa \longrightarrow {\mathbb {G}}_T$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>e</mml:mi><mml:mo>:</mml:mo><mml:msup><mml:mrow><mml:mi>G</mml:mi></mml:mrow><mml:mi>κ</mml:mi></mml:msup><mml:mo>⟶</mml:mo><mml:msub><mml:mi>G</mml:mi><mml:mi>T</mml:mi></mml:msub></mml:mrow></mml:math> for prime-order groups $${\mathbb {G}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>G</mml:mi></mml:math> and $${\mathbb {G}}_T$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>G</mml:mi><mml:mi>T</mml:mi></mml:msub></mml:math> . To establish the hardness of the $$\kappa $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>κ</mml:mi></mml:math> -linear $${\text {DDH}} $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mtext>DDH</mml:mtext></mml:math> problem, we rely on the existence of a base group for which the $$\kappa $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>κ</mml:mi></mml:math> -strong $${\text {DDH}} $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mtext>DDH</mml:mtext></mml:math> assumption holds. Our second construction is for the asymmetric setting, where $$\mathbf{e }: {\mathbb {G}}_1 \times \cdots \times {\mathbb {G}}_{\kappa } \longrightarrow {\mathbb {G}}_T$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>e</mml:mi><mml:mo>:</mml:mo><mml:msub><mml:mi>G</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>×</mml:mo><mml:mo>⋯</mml:mo><mml:mo>×</mml:mo><mml:msub><mml:mi>G</mml:mi><mml:mi>κ</mml:mi></mml:msub><mml:mo>⟶</mml:mo><mml:msub><mml:mi>G</mml:mi><mml:mi>T</mml:mi></mml:msub></mml:mrow></mml:math> for a collection of $$\kappa +1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>κ</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math> prime-order groups $${\mathbb {G}}_i$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>G</mml:mi><mml:mi>i</mml:mi></mml:msub></mml:math> and $${\mathbb {G}}_T$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>G</mml:mi><mml:mi>T</mml:mi></mml:msub></mml:math> , and relies only on the 1-strong $${\text {DDH}} $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mtext>DDH</mml:mtext></mml:math> assumption in its base group. In both constructions, the linearity $$\kappa $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>κ</mml:mi></mml:math> can be set to any arbitrary but a priori fixed polynomial value in the security parameter. We rely on a number of powerful tools in our constructions: probabilistic indistinguishability obfuscation, dual-mode NIZK proof systems (with perfect soundness, witness-indistinguishability, and zero knowledge), and additively homomorphic encryption for the group $$\mathbb {Z}_N^{+}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msubsup><mml:mi>Z</mml:mi><mml:mi>N</mml:mi><mml:mo>+</mml:mo></mml:msubsup></mml:math> . At a high level, we enable “bootstrapping” multilinear assumptions from their simpler counterparts in standard cryptographic groups and show the equivalence of PIO and multilinear maps under the existence of the aforementioned primitives.

Alexandre Marques Albano da Silveira

SILVEIRA, Alexandre Marques Albano da. Prova de conhecimento nulo baseada em isomorfismo de subgrafos. 2016. 71 f. - Dissertação - Universidade Federal do Ceará, Programa de Pós-Graduação em Engenharia Elétrica e da Computação, Sobral, 2016.

Seetha Ranganathan, R. Saravanan

&lt;p&gt;The password which is a more secure and valuable data should be highly protected from eavesdropper. This paper presents how password required for authentication of members of group communication is securely delivered by the source or initiator of the group. The password delivery uses zero knowledge proof and sent to the group member in an encrypted format using cipher block mode encryption. The password delivered is a One Time Password which can be used for certain amount of time in order to ensure a highly secure communication environment among the group.&lt;/p&gt;

Jürgen Angst, Guillaume Poly

We investigate the mean number of real zeros over an interval $[a,b]$ of a random trigonometric polynomial of the form $\sum_{k=1}^n a_k \cos(kt)+b_k \sin(kt)$ where the coefficients are i.i.d. random variables. Under mild assumptions on the law of the entries, we prove that this mean number is asymptotically equivalent to $\frac{n(b-a)}{π\sqrt{3}}$ as $n$ goes to infinity, as in the known case of standard Gaussian coefficients. Our principal requirement is a new Cramer type condition on the characteristic function of the entries which does not only hold for all continuous distributions but also for discrete ones in a generic sense. To our knowledge, this constitutes the first universality result concerning the mean number of zeros of random trigonometric polynomials. Besides, this is also the first time that one makes use of the celebrated Kac-Rice formula not only for continuous random variables as it was the case so far, but also for discrete ones. Beyond the proof of a non asymptotic version of Kac-Rice formula, our strategy consists in using suitable small ball estimates and Edgeworth expansions for the Kolmogorov metric under our new weak Cramer condition, which both constitute important byproducts of our approach.

Mohsen Toorani

Abstract This paper considers security analysis of the YAK, a public key‐based authenticated key agreement protocol. The YAK protocol is a variant of the two‐pass HMQV protocol but uses zero‐knowledge proofs for proving knowledge of ephemeral values. In this paper, we show that the YAK protocol lacks joint key control and perfect forward secrecy attributes and is vulnerable to some attacks including unknown key‐share and key‐replication attacks. This invalidates the semantic security of the protocol in several security models. There are also other considerations regarding the impersonation and small subgroup attacks. Copyright © 2015 John Wiley &amp; Sons, Ltd.

Marcos Portnoi, Chien-Chung Shen

We introduce LOCATHE (Location-Enhanced Authenticated Key Exchange), a generic protocol that pools location, user attributes, access policy and desired services into a multi-factor authentication, allowing two peers to establish a secure, encrypted session and perform mutual authentication with pre-shared keys, passwords and other authentication factors. LOCATHE contributes to: (1) forward secrecy through ephemeral session keys; (2) security through zero-knowledge password proofs (ZKPP), such that no passwords can be learned from the exchange; (3) the ability to use not only location, but also multiple authentication factors from a user to a service; (4) providing a two-tiered privacy authentication scheme, in which a user may be authenticated either based on her attributes (hiding her unique identification), or with a full individual authentication; (5) employing the expressiveness and flexibility of Decentralized or Multi-Authority Ciphertext-Policy Attribute-Based Encryption, allowing multiple service providers to control their respective key generation and attributes.

Liang-Ao Zhang, Xingming Sun, Zhihua Xia, Qiuju Ji

Attribute-Based Encryption (ABE) is a promising cryptographic primitive to implement access control for secure data storage in the cloud. Since the data owner may frequently change the access policies defined in the ciphertext, it is significant to provide the capacity for dynamic policy updating. However the cloud should also authenticate the owner because the adversary may modify the access policies of the files in the cloud to prevent the legal users from accessing them. In this paper, we focus on the owner's authentication in the ABE systems and propose a novel scheme which enables access control with authenticated dynamic policy updating in the cloud. We adapt the Pedersen commitment and Zero Knowledge Proof of Knowledge (ZKPK) to realize the anonymous authentication of the owner's policy updating key without increasing any secret information to the owner side. The analysis shows that our scheme is authentic and efficient as well as adaptive to different types of access policies.

Edward Lui

Enormous amounts of data are collected by hospitals, social networking systems, government agencies, and other organizations. There are huge social benefits in analyzing this data, but we must protect the privacy of the individuals in the data. The current standard definition of data privacy is differential privacy [22, 19]. In this thesis, we introduce new definitions of data privacy that can be better than differential privacy in certain ways. We first argue that differential privacy might not be strong enough in social network settings. We then introduce a zero-knowledge based definition of privacy called zero-knowledge privacy, which is strictly stronger than differential privacy and is particularly attractive when modeling privacy in social networks. Both differential privacy and zero-knowledge privacy provide strong privacy guarantees. However, for certain tasks, mechanisms satisfying these privacy definitions have to add a lot of "noise", thus lowering the utility of the released data. Thus, we introduce a new definition of privacy called crowd-blending privacy that strictly relaxes the notion of differential privacy. We demonstrate crowd-blending private mechanisms for histograms and for releasing synthetic data points, achieving strictly better utility than what is possible using differentially private mechanisms. Differential privacy guarantees the same level of privacy protection for all individuals. However, we demonstrate that some individuals may need more privacy than others. Thus, we introduce a generalization of differential privacy called tai- lored differential privacy, where an individual's privacy parameter is "tailored" for the individual based on the individual's data and the data set. We focus on a natural instance of tailored differential privacy, which we call outlier privacy: an individual's privacy parameter is determined by how much of an "outlier " the individual is. In this thesis, we also study the problem of strategy-proof voting, which is plagued by impossibility results. We take a bounded-rationality approach to this problem and consider a setting where voters have "coarse" beliefs (a notion that has gained popularity in the behavioral economics literature). In particular, we construct good voting rules that satisfy a notion of strategy-proofness with respect to coarse i.i.d. beliefs, thus circumventing the existing impossibility results.

Matt Miyasato, Joseph Impllitti, Pascal Amar

The I-710 and CA-60 highways are key transportation corridors in the Southern California region that are heavily used on a daily basis by heavy duty drayage trucks that transport the cargo from the ports to the inland transportation terminals. These terminals, which include store/warehouses, inland-railways, are anywhere from 5 to 50 miles in distance from the ports. The concentrated operation of these drayage vehicles in these corridors has had and will continue to have a significant impact on the air quality in this region whereby significantly impacting the quality of life in the communities surrounding these corridors. To reduce these negative impacts it is critical that zero and near-zero emission technologies be developed and deployed in the region. A potential local market size of up to 46,000 trucks exists in the South Coast Air Basin, based on near- dock drayage trucks and trucks operating on the I-710 freeway. The South Coast Air Quality Management District (SCAQMD), California Air Resources Board (CARB) and Southern California Association of Governments (SCAG) — the agencies responsible for preparing the State Implementation Plan required under the federal Clean Air Act — have stated that to attain federal air quality standards the region will need to transition to broad use of zero and near zero emission energy sources in cars, trucks and other equipment (Southern California Association of Governments et al, 2011). SCAQMD partnered with Volvo Trucks to develop, build and demonstrate a prototype Class 8 heavy-duty plug-in hybrid drayage truck with significantly reduced emissions and fuel use. Volvo’s approach leveraged the group’s global knowledge and experience in designing and deploying electromobility products. The proprietary hybrid driveline selected for this proof of concept was integrated with multiple enhancements to the complete vehicle in order to maximize the emission and energy impact of electrification. A detailed review of all technologies included in the demonstrator is presented in this report. The project was completed in July 2015 with a final demonstration of the concept vehicle on a simulated drayage route around Volvo’s North American headquarters in Greensboro, NC. The route included all traffic conditions typical of drayage operation in Southern California as well as geofences defined to showcase the zero emission capabilities of the truck. The demonstrator successfully completed four consecutive trips with a gross combined vehicle weight of 44,000 lb., covering approximately 2 miles out of a total distance of 9 miles per trip in the Zero Emission (ZE) geofence. This vehicle is expected to use approximately 30% less fuel than a typical drayage truck in daily operation, and it is designed to allow full electric operation whenever operating in a marine terminal in the ports of Los Angeles / Long Beach. A paper study on the feasibility of expanding the capabilities of the plug-in hybrid concept developed as part of this project was also delivered as an addendum to the regular progress reports.

Clémentine Gritti, Willy Susilo, Thomas Plantard

Ring signatures enable a user to anonymously sign a message on behalf of group of users. In this study, the authors propose the first ring signature scheme whose size is O (log 2 N ), where N is the number of users in the ring. They achieve this result by improving Chandran et al .’s ring signature scheme presented at the International Colloquium on Automata, Languages and Programming 2007. Their scheme uses a common reference string and non‐interactive zero‐knowledge proofs. The security of their scheme is proven without requiring random oracles.

Sebastian E. Schmittner

A homomorphic public key crypto-scheme based on the Boolean Satisfiability Problem is proposed. The public key is a SAT formula satisfied by the private key. Probabilistic encryption generates functions implied to be false by the public key XOR the message bits. A zero-knowledge proof is used to provide signatures.