Blockchain Papers

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

No abstract is available for this record.

David Derler, Henrich C. Pöhls, Kai Samelin, Daniel Slamanig

Abstract. A redactable signature scheme (RSS) allows removing parts of a signed message by any party without invalidating the respective signa-ture. State-of-the-art constructions thereby focus on messages represented by one specific data-structure, e.g., lists, sets or trees, and adjust the secu-rity model accordingly. To overcome the necessity for this myriad of models, we present a general framework covering arbitrary data-structures and even more sophisticated possibilities. For example, we cover fixed elements which must not be redactable and dependencies between elements. Moreover, we introduce the notion of designated redactors, i.e., the signer can give some extra information to selected entities which become redactors. In practice, this often allows to obtain more efficient schemes. We then present two RSSs; one for sets and one for lists, both constructed from any EUF-CMA secure signature scheme and indistinguishable cryptographic accumulators in a black-box way and show how the concept of designated redactors can be used to increase the efficiency of these schemes. Finally, we present a black-box construction of a designated redactor RSS by combining an RSS for sets with non-interactive zero-knowledge proof systems. All the three constructions presented in this paper provide transparency, which is an im-portant property, but quite hard to achieve, as we also conceal the length of the original message and the positions of the redactions. 1

Vinod Vaikuntanathan, Prashant Nalini Vasudevan

We show a general connection between various types of statistical zero-knowledge (SZK) proof systems and (unconditionally secure) secret sharing schemes. Viewed through the SZK lens, we obtain several new results on secret-sharing: Characterizations: We obtain an almost-characterization of access structures for which there are secret-sharing schemes with an ecient sharing algorithm (but not necessarily ecient reconstruction). In particular, we show that for every language L2 SZKL (the class of languages that have statistical zero knowledge proofs with log-space veriers and simulators), a (monotonized) access structure associated with L has such a secretsharing scheme. Conversely, we show that such secret-sharing schemes can only exist for languages in SZK. Constructions: We show new constructions of secret-sharing schemes with ecient sharing and reconstruction for access structures that are in P, but are not known to be in NC, namely Bounded-Degree Graph Isomorphism and constant-dimensional lattice problems. In particular, this gives us the rst combinatorial access structure that is conjectured to be outside NC but has an ecient secret-sharing scheme. Previous such constructions (Beimel and Ishai; CCC 2001) were algebraic and number-theoretic in nature. Limitations: We show that universally-ecie nt secret-sharing schemes, where the complexity of computing the shares is a polynomial independent of the complexity of deciding the access structure, cannot exist for all (monotone languages in) P, unless there is a polynomial q such that P DSPACE(q(n)).

Berry Schoenmakers, Meilof Veeningen

Abstract. Multiparty computation can be used for privacy-friendly out-sourcing of computations on private inputs of multiple parties. A com-putation is outsourced to several computation parties; if not too many are corrupted (e.g., no more than half), then they cannot determine the inputs or produce an incorrect output. However, in many cases, these guarantees are not enough: we need correctness even if all computation parties may be corrupted; and we need that correctness can be verified even by parties that did not participate in the computation. Protocols satisfying these additional properties are called “universally verifiable”. In this paper, we propose a new security model for universally verifi-able multiparty computation, and we present a practical construction, based on a threshold homomorphic cryptosystem. We also develop a multiparty protocol for jointly producing non-interactive zero-knowledge proofs, which may be of independent interest.

Eike Kiltz, Hoeteck Wee

Non-interactive zero-knowledge (NIZK) proofs for algebraic relations in a group, such as the GrothSahai proofs, are an extremely powerful tool in pairing-based cryptography. A series of recent works focused on obtaining very efficient NIZK proofs for linear spaces in a weaker quasi-adaptive model. We revisit recent quasiadaptive NIZK constructions, providing clean, simple, and improved constructions via a conceptually different approach inspired by recent developments in identity-based encryption. We then extend our techniques also to linearly homomorphic structure-preserving signatures, an object both of independent interest and with many applications.

Esha Ghosh, Olga Ohrimenko, Roberto Tamassia

No abstract is available for this record.

Vinod Vaikuntanathan, Prashant Nalini Vasudevan

We show a general connection between various types of statistical zero-knowledge (SZK) proof systems and (unconditionally secure) secret sharing schemes. Viewed through the SZK lens, we obtain several new results on secret-sharing: • Characterizations: We obtain an almost-characterization of access structures for which there are secret-sharing schemes with an efficient sharing algorithm (but not necessarily efficient reconstruction). In particular, we show that for every language L ∈ SZKL (the class of languages that have statistical zero knowledge proofs with log-space verifiers and simulators), a (monotonized) access structure associated with L has such a secret-sharing scheme. Conversely, we show that such secret-sharing schemes can only exist for languages in SZK. • Constructions: We show new constructions of secret-sharing schemes with both ef-ficient sharing and efficient reconstruction for access structures associated with lan-guages that are in P, but are not known to be in NC, namely Bounded-Degree Graph Isomorphism and constant-dimensional lattice problems. In particular, this gives us the first combinatorial access structure that is conjectured to be outside NC but has an efficient secret-sharing scheme. Previous such constructions (Beimel and Ishai; CCC 2001) were algebraic and number-theoretic in nature. • Limitations: We also show that universally-efficient secret-sharing schemes, where the complexity of computing the shares is a polynomial independent of the complexity of deciding the access structure, cannot exist for all (monotone languages in) P, unless there is a polynomial q such that P ⊆ DSPACE(q(n)). 1

Claude Crépeau, Raza Ali Kazmi

In this work we introduce a new hard problem in lattices called Isometric Lattice Problem (ILP) and reduce Linear Code Equivalence over prime fields and Graph Isomorphism to this problem. We also show that this problem has an (efficient prover) perfect zero-knowledge interactive proof; this is the only hard problem in lattices that is known to have this property (with respect to malicious verifiers). Under the assumption that the polynomial hierarchy does not collapse, we also show that ILP cannot be NP-complete. We finally introduce a variant of ILP over the rationals radicands and provide similar results for this new problem.

Tore Kasper Frederiksen, Jesper Buus Nielsen, Claudio Orlandi

No abstract is available for this record.

Zhangxiang Hu, Payman Mohassel, Mike Rosulek

We describe a zero-knowledge proof system in which a prover holds a large dataset M and can repeatedly prove NP relations about that dataset. That is, for any (public) relation R and x, the prover can prove that ∃w: R(M,x,w) = 1. After an initial setup phase (which depends only on M), each proof requires only a constant number of rounds and has communication/computation cost proportional to that of a random-access machine (RAM) implementation of R, up to poly-logarithmic factors. In particular, the cost per proof in many applications is sublinear in |M |. Additionally, the storage requirement between proofs for the verifier is constant. 1

Ranjit Kumaresan, Iddo Bentov

We study a model of incentivizing correct computations in a variety of cryptographic tasks. For each of these tasks we propose a formal model and design protocols satisfying our model's constraints in a hybrid model where parties have access to special ideal functionalities that enable monetary transactions. We summarize our results:

Zhi Yi Shao, Bo Yang

Shao et al. proposed a novel method for computing private set intersection based on searchable encryption. Compared with the traditional protocols, their technique requires much less computation for the client to obtain the intersection. Concretely, the client only computes m (the cardinality of the client’s input set) multiplications, m hashes, and one modular exponentiation. However, their protocol only satisfies security against semi-honest behaviors. In this paper, we aim to promote the security of Shao et al.’s protocol. Our solution woks in the CRS model, and is based on the non-interactive zero knowledge proof and the succinct non-interactive argument. The proposed protocol satisfies security against malicious adversaries and needs only one round interaction.

Melissa Chase, Markulf Kohlweiss, Anna Lysyanskaya, Sarah Meiklejohn

A signature scheme is malleable if, on input a message and a signature, it is possible to efficiently compute a signature on a related message, for a transformation that is allowed with respect to this signature scheme. In this paper, we first provide new definitions for malleable signatures that allow us to capture a broader range of transformations than was previously possible. We then give a generic construction based on malleable zero-knowledge proofs that allows us to construct malleable signatures for a wide range of transformation classes, with security properties that are stronger than those that have been achieved previously. Finally, we construct delegatable anonymous credentials from signatures that are malleable with respect to an appropriate class of transformations (that we show our malleable signature supports). The resulting instantiation satisfies a stronger security notion than previous schemes while also scaling linearly with the number of delegations.

Fuchun Guo, Yi Mu, Willy Susilo

In this paper, we propose a novel cryptographic notion called subset membership encryption (SME), and provide a very efficient SME scheme. Given a system parameter generated by an encryptor (Alice), a decryptor (Bob) generates a randomized privacy-preserved attribute token P(G) from a set of attributes G. A message is encrypted using an attribute set A chosen by Alice and P(G) provided by Bob. It requires that A is a subset of G for Bob to decrypt the message. We propose a very efficient SME scheme, where both the size of P(G) and ciphertext are short and independent of G and A. In particular, it has three useful and practical applications to oblivious transfer as follows. 1) k-Out-of-n Oblivious Transfer (OT): SME can be naturally applied to a two-round OT, which features a great communication efficiency especially for the receiver, where the receiver only sends two group elements to the message sender. 2) Priced Oblivious Transfer (POT): Our POT protocol allows a buyer to purchase any number of items in each transaction and hide selected items, price and balance from the vendor. In comparison with previous POT protocols, our protocol is more flexible and eliminates the restriction that a buyer can only purchase one item in a transaction. Our POT scheme is very efficient since it does not require any zero-knowledge proof or homomorphic encryption. 3) Restricted Priced Oblivious Transfer (RPOT): We introduce a novel POT named RPOT where a vendor can set restrictions on items or prices in POT. For example, a seller could offer a discounted price to those buyers who have purchased some specific items previously from the same seller.

Craig Gentry, Jens Groth, Yuval Ishai, Chris Peikert · 6 authors

No abstract is available for this record.

Andrew Mastin, Patrick Jaillet, Sang Chin

The minmax regret problem for combinatorial optimization under uncertainty\ncan be viewed as a zero-sum game played between an optimizing player and an\nadversary, where the optimizing player selects a solution and the adversary\nselects costs with the intention of maximizing the regret of the player. The\nexisting minmax regret model considers only deterministic solutions/strategies,\nand minmax regret versions of most polynomial solvable problems are NP-hard. In\nthis paper, we consider a randomized model where the optimizing player selects\na probability distribution (corresponding to a mixed strategy) over solutions\nand the adversary selects costs with knowledge of the player's distribution,\nbut not its realization. We show that under this randomized model, the minmax\nregret version of any polynomial solvable combinatorial problem becomes\npolynomial solvable. This holds true for both the interval and discrete\nscenario representations of uncertainty. Using the randomized model, we show\nnew proofs of existing approximation algorithms for the deterministic model\nbased on primal-dual approaches. Finally, we prove that minmax regret problems\nare NP-hard under general convex uncertainty.\n

Thomas Peters

Technology is linking the slightest of our actions to the virtual world. In such connected environments, cryptography aims at building schemes with provable security in order to mathematically protect the users' security in electronic exchanges. Relying on the existence of pairings in bilinear groups wherein the discrete logarithm problem is hard, this thesis puts forth mechanisms to efficiently enhance the privacy in three of the most fundamental cryptographic primitives, namely, digital signatures, encryption schemes and zero-knowledge proofs. Furthermore, these mechanisms support public verifiability so as to force the honesty of all participants in the standard model. We first focus on group signatures, a primitive proposed some 20 years ago, for which we propose the first efficient revocation mechanisms, overcoming the main obstacle to the deployment of this primitive in practical applications. We then focus on P-homomorphic signatures that make it possible to modify a signed message in a controlled way. In particular, we propose new mechanisms providing structure-preserving linearly homomorphic signatures, from which we build the first constant-size non-malleable commitments compatible with standard proof systems, as well as a generalization of this construction into a generic transformation. Finally we further investigate the unexpected applications of this kind of malleable signatures to non-malleable cryptography. This leads us to new proof systems for linear languages which in turn provide the most efficient publicly verifiable CCA-secure threshold encryption to date, and other new extensions.

Yi Deng

Abstract. We construct O(log 1+ɛ n)-round public-coin concurrent zero knowledge arguments for NP from standard (against any polynomial-time adversary) collision-resistant hash functions for arbitrarily small constant ɛ. Our construction is straight-line simulatable. This is the first public-coin concurrent zero knowledge protocol based on standard/long-studied assumption that (almost) achieves the best known round-complexity of its private-coin counterpart [Prabhakaran et al., FOCS 02]. Previously, such publiccoin constructions require either polynomial number of rounds [Goyal, STOC 13], newly-introduced assumptions [Chung et al., FOCS 13], or stronger model [Canetti et al., TCC 13]. This result has strong consequences: it yields the first (almost) logarithmic round simultaneously resettable arguments for NP and the first (almost) logarithmic round concurrent multi-party computation in the single input setting. These results significantly improve over the polynomial round-complexity of the best known protocols based on standard assumptions in both cases. Our technical contribution is two-fold. First, we introduce a simulation strategy called clearance that yields a simulation tree of very special combinatorial structure and enables us to instantiate Barak’s protocol [Barak, FOCS 01] using the recent Ben-Sasson et al.’s quasi-linear construction of PCP system [Ben-Sasson et al., STOC 13] to obtain logarithmic round-complexity; secondly, we show how to modify Barak’s protocol such that the soundness of overall construction does not rely on the (implicit/explicit) proof of knowledge property of the underlying universal argument/PCP system, which in turn allows us to benefit from progress on short PCP system of more general types without assuming stronger/superpolynomial hardness. 1

Nir Bitansky, Omer Paneth

We present new constructions of two-message and one-message witness-indistinguishable proofs (ZAPs and NIWIs). This includes: • ZAPs (or, equivalently, non-interactive zero-knowledge in the common random string model) from indistinguishability obfuscation and one-way functions. • NIWIs from indistinguishability obfuscation and one-way permutations. The previous construction of ZAPs [Dwork and Naor, FOCS 00] was based on trapdoor permutations. The two previous NIWI constructions were based either on ZAPs and a derandomization-type complexity assumption [Barak, Ong, and Vadhan CRYPTO 03], or on a specific number theoretic assumption in bilinear groups [Groth, Sahai, and Ostrovsky, CRYPTO 06]. ∗MIT. Email: nirbitan@csail.mit.edu. Part of this work was done while at Tel Aviv University. †Boston University. Email: omer@bu.edu. Supported by the Simons award for graduate students in theoretical computer science and an NSF Algorithmic foundations grant 1218461.

Hongda Li, Qihua Niu, Guifang Huang

Abstract. Garg, Jain, and Sahai first consider zero knowledge proofs in the presence of leakage on the local state of the prover, and present a leakage-resilient-zero-knowledge proof system for HC (Hamiltonian Cycle) problem. Their construction is called (1 + ε)-leakage-resilient zero-knowledge, for any constant ε> 0, because the total length of the leakage the simulator needs is (1 + ε) times as large as that of the leakage received by the verifier. In recent, Pandey provides a constant-round leakage-resilient zero-knowledge argument satisfying the ideal requirement of ε = 0. Whether there exist constant round leakage-resilient zero-knowledge arguments of knowledge for all NP languages is an interesting problem. This paper focuses on this problem and presents a constant-round construction of leakage-resilient zero-knowledge arguments of knowledge for the HC problem. Key word: zero-knowledge proofs, proofs of knowledge, leakage-resilient, non-black-box simulation, constant-round. 1

Shashank Agrawal, Shweta Agrawal, Shweta Agrawal, Shweta Agrawal · 5 authors

We provide a new framework of cryptographic agents that unifies various modern “cryp- tographic objects” — identity-based encryption, fully-homomorphic encryption, functional encryption, and various forms of obfuscation – similar to how the Universal Composition framework unifies various multi-party computation tasks like commitment, coin-tossing and zero-knowledge proofs. These cryptographic objects can all be cleanly modeled as “schemata” in our framework. Highlights of our framework include the following: • We use a new indistinguishability preserving (IND-PRE) definition of security that in- terpolates indistinguishability and simulation style definitions, which (often) sidesteps the known impossibilities for the latter. IND-PRE-security is parameterized by the choice of the “test” family, such that by choosing different test families, one can obtain different levels of security for the same primitive (including various standard definitions in the literature). • We present a notion of reduction from one schema to another and a powerful composition theorem with respect to IND-PRE security. We show that obfuscation is a “complete” schema under this notion, under standard cryptographic assumptions. We also provide a stricter notion of reduction (∆-reduction) that composes even when security is only with respect to certain restricted test families of importance. • Last but not the least, our framework can be used to model abstractions like the generic group model and the random oracle model, letting one translate a general class of constructions in these heuristic models to constructions based on standard model assumptions. We also illustrate how our framework can be applied to specific primitives like obfus- cation and functional encryption. We relate our definitions to existing definitions and also give new constructions and reductions between different primitives. ∗University of Illinois, Urbana-Champaign. Email: sagrawl2@illinois.edu. †Indian Institute of Technology, Delhi. Email: shweta.a@gmail.com. ‡University of Illinois, Urbana-Champaign. Email: mmp@illinois.edu.

Handan Kılınç, Alptekın Küpçü

Secure two-party computation cannot be fair against malicious adversaries, unless a trusted third party (TTP) or a gradual-release type super-constant round protocol is employed. Existing optimistic fair two-party computation protocols with constant rounds are either too costly to arbitrate (e.g., the TTP may need to re-do almost the whole computation), or require the use of electronic payments. Furthermore, most of the existing solutions were proven secure and fair via a partial simulation, which, we show, may lead to insecurity overall. We propose a new framework for fair and secure two-party computation that can be applied on top of any secure two party computation protocol based on Yao’s garbled circuits and zero-knowledge proofs. We show that our fairness overhead is minimal, compared to all known existing work. Furthermore, our protocol is fair even in terms of the work performed by Alice and Bob. We also prove our protocol is fair and secure simultaneously, through one simulator, which guarantees that our fairness extensions do not leak any private information. Lastly, we ensure that the TTP never learns the inputs or outputs of the computation. Therefore, even if the TTP becomes malicious and causes unfairness by colluding with one party, the security of the underlying protocol is still preserved.

Masayuki Abe, Jan Camenisch, Rafael Dowsley, Maria Dubovitskaya

No abstract is available for this record.

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

To gain strong confidence in the security of a public-key scheme, it is most desirable for the security proof to feature a tight reduction between the adversary and the algorithm solving the underlying hard problem. Recently, Chen and Wee (Crypto’13) described the first Identity-Based Encryption scheme with almost tight security under a standard assumption. Here, “almost tight” means that the security reduction only loses a factor O(λ) —where λ is the security parameter— instead of a factor proportional to the number of adversarial queries. Chen and Wee also gave the shortest signatures whose security almost tightly relates to a simple assumption in the standard model. Also recently, Hofheinz and Jager (Crypto ’12) constructed the first CCA-secure public-key encryption scheme in the multi-user setting with tight security. These constructions give schemes that are significantly less efficient in length (and thus, processing) when compared with the earlier schemes with loose reductions in their proof of security. Hofheinz and Jager’s scheme has a ciphertext of a few hundreds of group elements, and they left open the problem of finding truly efficient constructions. Likewise, Chen and Wee’s signatures and IBE schemes are somewhat less efficient than previous constructions with loose reductions from the same assumptions. In this paper, we consider space-efficient schemes with security almost tightly related to standard assumptions. We construct an efficient CCA-secure public-key encryption scheme whose chosen-ciphertext security in the multi-challenge, multi-user setting almost tightly relates to the DLIN assumption (in the standard model). Quite remarkably, the ciphertext size decreases to 69 group elements under the DLIN assumption whereas the best previous solution required about 400 group elements. Our scheme is obtained by taking advantage of a new almost tightly secure signature scheme (in the standard model) which is based on the recent concise proofs of linear subspace membership in the quasi-adaptive non-interactive zero-knowledge setting (QA-NIZK) defined by Jutla and Roy (Asiacrypt’13). Our signature scheme reduces the length of the previous such signatures (by Chen and Wee) by 37% under the Decision Linear assumption, by almost 50% under the K-LIN assumption, and it becomes only 3 group elements long under the Symmetric eXternal Diffie-Hellman assumption. Our signatures are obtained by carefully combining the proof technique of Chen and Wee and the above mentioned QA-NIZK proofs.