Follow blockchain research across journals, conferences, and preprint repositories.
370 results · page 10 of 16
Veronika Kuchta, Gaurav Sharma, Rajeev Anand Sahu, Olivier Markowitch
No abstract is available for this record.
Iddo Bentov, Ranjit Kumaresan, Andrew Miller
We present efficient protocols for amortized secure multiparty computation with penalties and secure cash distribution, of which poker is a prime example. Our protocols have an initial phase where the parties interact with a cryptocurrency network, that then enables them to interact only among themselves over the course of playing many poker games in which money changes hands. The high efficiency of our protocols is achieved by harnessing the power of stateful contracts. Compared to the limited expressive power of Bitcoin scripts, stateful contracts enable richer forms of interaction between standard secure computation and a cryptocurrency. We formalize the stateful contract model and the security notions that our protocols accomplish, and provide proofs using the simulation paradigm. Moreover, we provide a reference implementation in Ethereum/Solidity for the stateful contracts that our protocols are based on. We also adopt our off-chain cash distribution protocols to the special case of stateful duplex micropayment channels, which are of independent interest. In comparison to Bitcoin based payment channels, our duplex channel implementation is more efficient and has additional features.
Itay Berman, Ron D. Rothblum, Vinod Vaikuntanathan
© Itay Berman, Ron D. Rothblum and Vinod Vaikuntanathan. Interactive proofs of proximity (IPPs) are interactive proofs in which the verifier runs in time sub-linear in the input length. Since the verifier cannot even read the entire input, following the property testing literature, we only require that the verifier reject inputs that are far from the language (and, as usual, accept inputs that are in the language). In this work, we initiate the study of zero-knowledge proofs of proximity (ZKPP). A ZKPP convinces a sub-linear time verifier that the input is close to the language (similarly to an IPP) while simultaneously guaranteeing a natural zero-knowledge property. Specifically, the verifier learns nothing beyond (1) the fact that the input is in the language, and (2) what it could additionally infer by reading a few bits of the input. Our main focus is the setting of statistical zero-knowledge where we show that the following hold unconditionally (where N denotes the input length): Statistical ZKPPs can be sub-exponentially more efficient than property testers (or even non-interactive IPPs): We show a natural property which has a statistical ZKPP with a polylog(N) time verifier, but requires (N) queries (and hence also runtime) for every property tester. Statistical ZKPPs can be sub-exponentially less efficient than IPPs: We show a property which has an IPP with a polylog(N) time verifier, but cannot have a statistical ZKPP with even an No(1) time verifier. Statistical ZKPPs for some graph-based properties such as promise versions of expansion and bipartiteness, in the bounded degree graph model, with polylog(N) time verifiers exist. Lastly, we also consider the computational setting where we show that: Assuming the existence of one-way functions, every language computable either in (logspace uniform) NC or in SC, has a computational ZKPP with a (roughly) N time verifier. Assuming the existence of collision-resistant hash functions, every language in NP has a statistical zero-knowledge argument of proximity with a polylog(N) time verifier.
Ronald Cramer, Ivan Damgård, Chaoping Xing, Chen Yuan
No abstract is available for this record.
Jonathan Bootle, Andrea Cerulli, Essam Ghadafi, Jens Groth · 6 authors
No abstract is available for this record.
Yasser Shoukry, Konstantinos Gatsis, Amr Alanwar, George J. Pappas · 7 authors
We consider a problem where multiple agents participate in solving a quadratic optimization problem subject to linear inequality constraints in a privacy-preserving manner. Several variables of the objective function as well as the constraints are privacy-sensitive and are known to different agents. We propose a privacy-preserving protocol based on partially homomorphic encryption where each agent encrypts its own information before sending it to an untrusted cloud computing infrastructure. To find the optimal solution the cloud applies a gradient descent algorithm on the encrypted data without the ability to decrypt it. The privacy of the proposed protocol against coalitions of colluding agents is analyzed using the cryptography notion of zero knowledge proofs.
Eli Ben‐Sasson, Alessandro Chiesa, Michael A. Forbes, Ariel Gabizon · 6 authors
We present the first constructions of single-prover proof systems that achieve perfect zero knowledge (PZK) for languages beyond NP, under no intractability assumptions: 1. The complexity class #P has PZK proofs in the model of Interactive PCPs (IPCPs) [KR08], where the verifier first receives from the prover a PCP and then engages with the prover in an Interactive Proof (IP). 2. The complexity class NEXP has PZK proofs in the model of Interactive Oracle Proofs (IOPs) [BCS16,RRR16], where the verifier, in every round of interaction, receives a PCP from the prover. Our constructions rely on succinct simulators that enable us to "simulate beyond NP", achieving exponential savings in efficiency over [BCGV16]. These simulators crucially rely on solving a problem that lies at the intersection of coding theory, linear algebra, and computational complexity, which we call the succinct constraint detection problem, and consists of detecting dual constraints with polynomial support size for codes of exponential block length. Our two results rely on solutions to this problem for fundamental classes of linear codes: * An algorithm to detect constraints for Reed--Muller codes of exponential length. * An algorithm to detect constraints for PCPs of Proximity of Reed--Solomon codes [BS08] of exponential degree. The first algorithm exploits the Raz--Shpilka [RS05] deterministic polynomial identity testing algorithm, and shows, to our knowledge, a first connection of algebraic complexity theory with zero knowledge. Along the way, we give a perfect zero knowledge analogue of the celebrated sumcheck protocol [LFKN92], by leveraging both succinct constraint detection and low-degree testing. The second algorithm exploits the recursive structure of the PCPs of Proximity to show that small-support constraints are "locally" spanned by a small number of small-support constraints.
Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler · 5 authors
We examine the power of statistical zero knowledge proofs (captured by the complexity class SZK) and their variants. First, we give the strongest known relativized evidence that SZK contains hard problems, by exhibiting an oracle relative to which SZK (indeed, even NISZK) is not contained in the class UPP, containing those problems solvable by randomized algorithms with unbounded error. This answers an open question of Watrous from 2002 [Aar]. Second, we "lift" this oracle separation to the setting of communication complexity, thereby answering a question of Göös et al. (ICALP 2016). Third, we give relativized evidence that perfect zero knowledge proofs (captured by the class PZK) are weaker than general zero knowledge proofs. Specifically, we exhibit oracles relative to which SZK is not contained in PZK, NISZK is not contained in NIPZK, and PZK is not equal to coPZK. The first of these results answers a question raised in 1991 by Aiello and Håstad (Information and Computation), and the second answers a question of Lovett and Zhang (2016). We also describe additional applications of these results outside of structural complexity. The technical core of our results is a stronger hardness amplification theorem for approximate degree, which roughly says that composing the gapped-majority function with any function of high approximate degree yields a function with high threshold degree.
David Bernhard, Marc Fischlin, Bogdan Warinschi
The authors define a notion of adaptive proofs of knowledge (PoKs) in the random oracle model (ROM). These are proofs where the malicious prover can adaptively issue multiple statements and proofs, and where the extractor is supposed to extract a witness for each statement. They begin by studying the traditional notion of zero‐knowledge PoKs in the ROM and then show how to extend it to the case of adaptive adversaries and to simulation soundness, where the adversary can also learn simulated proofs. The authors’ first main result is negative. Under common assumptions, they can show that the well‐known Fiat–Shamir–Schnorr proof system is not adaptively secure. As for the second result, they prove that an existing construction due to Fischlin (Crypto 2005) yields adaptively secure simulation‐sound PoKs in the ROM. Since the purpose of this work is to motivate and introduce adaptive proofs, they only briefly discuss some applications to other areas, for example that adaptive proofs seem to be exactly what one requires to construct chosen‐ciphertext attack‐secure public‐key encryption from indistinguishability under chosen plaintext attack secure schemes.
Alonso González, Alejandro Hevia
Yao et al. (A note on the feasibility of generalized universal composability. Theory and Applications of Models of Computation pp. 474–485, 2007; A note on the feasibility of generalised universal composability. Mathematical Structures in Computer Science , 19 (1), pp. 193–205) claimed a potential limitation on the class of protocols that could be securely implemented in the generalized universal composability (GUC) framework proposed by Canetti et al. (Universally composable security with global setup. Lecture Notes in Computer Science , pp. 61–85, 2007). Specifically, Yao et al. presented a concrete attack on a GUC Zero Knowledge (GUCZK) protocol, a natural adaptation Blum's ZK proof for Directed Hamiltonicity using the general GUC feasibility of Canetti et al. (Universally composable security with global setup. Lecture Notes in Computer Science , pp. 61–85, 2007). Interestingly, the attack was not analysed in the GUC model in Yao et al. (A note on the feasibility of generalised universal composability. Mathematical Structures in Computer Science 19 (1), pp. 193–205, 2009) but in the FUC model , a new UC-like framework proposed in the same work. Nonetheless, Yao et al. (A note on the feasibility of generalised universal composability. Mathematical Structures in Computer Science 19 (1), pp. 193–205, 2009) argued that, in light of this attack, GUC would lose its concurrent general composability and proof of knowledge properties. Concretely, they argue that GUC composability would now be with respect to some adversaries with limited access to external arbitrary protocols. In this work, we show that the claimed attack from Yao et al. is indeed harmless and does not contradict the security of the mentioned GUCZK protocol, thus restoring the general feasibility for GUC.
Girish, Uma, Mittal, Kunal, Raz, Ran, Zhan, Wei
We prove that for every 3-player (3-prover) game G with value less than one, whose query distribution has the support S = {(1,0,0), (0,1,0), (0,0,1)} of Hamming weight one vectors, the value of the n-fold parallel repetition G^{⊗n} decays polynomially fast to zero; that is, there is a constant c = c(G) > 0 such that the value of the game G^{⊗n} is at most n^{-c}. Following the recent work of Girish, Holmgren, Mittal, Raz and Zhan (STOC 2022), our result is the missing piece that implies a similar bound for a much more general class of multiplayer games: For every 3-player game G over binary questions and arbitrary answer lengths, with value less than 1, there is a constant c = c(G) > 0 such that the value of the game G^{⊗n} is at most n^{-c}. Our proof technique is new and requires many new ideas. For example, we make use of the Level-k inequalities from Boolean Fourier Analysis, which, to the best of our knowledge, have not been explored in this context prior to our work.
Wojciech Wodo, Lucjan Hanzlik, Kamil Kluczniak
In this paper we investigate the concept of cancelable biometrics and propose a new scheme for user authorisation providing anonymity based on privacy-preserving computations on sets. We define a problem called (t;n) -Threshold Subset Problem and apply it to a biometric-based security system. Our solution implements biometric template protection based on one-way transformations and Bloom filters. Users authentication data is stored in form of a whitelist and the authorisation process is based on a zero-knowledge proof approach. Using oblivious polynomial evaluation (OPE) a legitimate user is able to recreate a secret polynomial and answer the challenge send by a verifier. We assume that biometric data can be acquired and digitized to the form of a vector representation.
Aggelos Kiayias, Hong-Sheng Zhou, Vassilis Zikas
No abstract is available for this record.
Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler · 5 authors
In both query and communication complexity, we give separations between the class NISZK, containing those problems with non-interactive statistical zero knowledge proof systems, and the class UPP, containing those problems with randomized algorithms with unbounded error. These results significantly improve on earlier query separations of Vereschagin [Ver95] and Aaronson [Aar12] and earlier communication complexity separations of Klauck [Kla11] and Razborov and Sherstov [RS10]. In addition, our results imply an oracle relative to which the class NISZK is not contained in PP. This answers an open question of Watrous from 2002 [Aar]. The technical core of our result is a stronger hardness amplification theorem for approximate degree, which roughly says that composing the gapped-majority function with any function of high approximate degree yields a function with high threshold degree. Using our techniques, we also give oracles relative to which the following two separations hold: perfect zero knowledge (PZK) is not contained in its complement (coPZK), and SZK (indeed, even NISZK) is not contained in PZK (indeed, even HVPZK). Along the way, we show that HVPZK is contained in PP in a relativizing manner. We prove a number of implications of these results, which may be of independent interest outside of structural complexity. Specifically, our oracle separation implies that certain parameters of the Polarization Lemma of Sahai and Vadhan [SV03] cannot be much improved in a black-box manner. Additionally, it implies new lower bounds for property testing algorithms with error probability arbitrarily close to 1/2. Finally, our results imply that two-message protocols in the streaming interactive proofs model of Cormode et al. [CTY11] are surprisingly powerful in the sense that, with just logarithmic cost, they can compute functions outside of UPP^CC.
Silvio Biagioni, Daniel Masny, Daniele Venturi
Abstract The Naor–Yung paradigm [63] allows to generically boost security under chosen-plaintext attacks (CPA) to security against chosen-ciphertext attacks (CCA) for public-key encryption (PKE) schemes. The main idea is to encrypt the plaintext twice (under independent public keys), and to append a non-interactive zero-knowledge (NIZK) proof that the two ciphertexts indeed encrypt the same message. Later work by Camenisch, Chandran, and Shoup [32] and Naor and Segev [ 28 , 30 ] established that the very same technique can also be used in the settings of key-dependent message (KDM) and key-leakage attacks (respectively). In this paper we study the conditions under which the two ciphertexts in the Naor–Yung construction can share the same random coins. We find that this is possible, provided that the underlying PKE scheme meets an additional simple property. The motivation for re-using the same random coins is that this allows to design much more efficient NIZK proofs. We showcase such an improvement in the random oracle model, under standard complexity assumptions including Decisional Diffie–Hellman, Quadratic Residuosity, and Subset Sum. The length of the resulting ciphertexts is reduced by 50%, yielding truly efficient PKE schemes achieving CCA security under KDM and key-leakage attacks. As an additional contribution, we design the first PKE scheme whose CPA security under KDM attacks can be directly reduced to (low-density instances of) the Subset Sum assumption. Our PKE scheme supports key-dependent messages computed via any affine function of the secret key.
Sebastiaan de Hoogh, Berry Schoenmakers, Meilof Veeningen
For many applications of secure multiparty computation it is natural to demand that the output of the protocol is verifiable. Verifiability should ensure that incorrect outputs are always rejected, even if all parties executing the secure computation collude. Since the inputs to a secure computation are private, and potentially the outputs are private as well, adding verifiability is in general hard and costly. In this paper we focus on privacy-preserving linear programming as a typical and practically relevant case for verifiable secure multiparty computation. We introduce certificate validation as an effective technique for achieving verifiable linear programming. Rather than verifying the computation proper, which involves many iterations of the simplex algorithm, we extend the output of the secure computation with a certificate. The certificate allows for efficient and direct validation of the correctness of the output. The overhead incurred by the computation of the certificate is marginal. For the validation of a certificate we design particularly efficient distributed-prover zero-knowledge proofs, fully exploiting the fact that we can use ElGamal encryption for this purpose, hence avoiding the use of more elaborate cryptosystems such as Paillier encryption. We also formulate appropriate security definitions for our approach, and prove security for our protocols in this model, paying special attention to ensuring properties such as input independence. By means of several experiments performed in a real multi-cloud-provider environment, we show that the overall performance for verifiable linear programming is very competitive, incurring minimal overhead compared to protocols providing no correctness guarantees at all.
Somindu C. Ramanna
We propose new constructions for inner product encryption – Open image in new window and Open image in new window , both secure under the eXternal Diffie-Hellman assumption (SXDH) in asymmetric pairing groups. The first scheme has constant-size ciphertexts whereas the second one is weakly attribute hiding. Open image in new window is derived from the identity-based encryption scheme of Jutla Roy (Asiacrypt 2013), that was extended from tag-based quasi-adaptive non-interactive zero-knowledge (QA-NIZK) proofs for linear subspaces of vector spaces over bilinear groups. The verifier common reference string (CRS) in these tag-based systems are split into two parts, that are combined during verification. We consider an alternate form of the tag-based QA-NIZK proof with a single verifier CRS that already includes a tag, different from the one defining the language. The verification succeeds as long as the two tags are unequal. Essentially, we embed a two-equation revocation mechanism in the verification. The new QA-NIZK proof system leads to Open image in new window , a constant-sized ciphertext IPE scheme with very short ciphertexts. Both the IPE schemes are obtained by applying the n-equation revocation technique of Attrapadung and Libert (PKC 2010) to the corresponding identity based encryption schemes and proved secure under SXDH assumption. As an application, we show how our schemes can be specialised to obtain the first fully secure identity-based broadcast encryption based on SXDH with a trade-off among the public parameters, ciphertext and key sizes, all of them being sub-linear in the maximum number of recipients of a broadcast.
Olivier Blazy, David Derler, Daniel Slamanig, Raphael Spreitzer
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.
Rosario Gennaro, Steven Goldfeder, Arvind Narayanan
No abstract is available for this record.
Benny Applebaum, Pavel Raykov
No abstract is available for this record.
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.
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.
Benoît Libert
This habilitation thesis deals with cryptographic primitives that preserve the algebraic structure of underlying objects (messages, keys, etc) and their applications to the design of non-interactive zero-knowledge proofs and privacy-enhancing cryptographic primitives.In 2008, Groth and Sahai showed how to make these proof systems relatively efficient in abelian groups endowed with a bilinear map. These techniques, however, require to work with lower-level primitives where handled objects all live in a cyclic abelian group. Among other things, we need to sign messages without destroying their algebraic structure (in particular, without hashing them first) so as to be able to efficiently prove properties about hidden signed messages. The first part of this thesis describes a structure-preserving signature scheme which was the first efficient realization under previously studied algorithmic assumptions. These tools are also utilized in the design of a novel revocation mechanism for group signatures, which allow users to anonymously sign messages on behalf of a population they belong to. The second part of this thesis considers structure-preserving signatures endowed with homomorphic properties. We show how to use them in the design of non-malleable cryptographic primitives. Using linearly homomorphic structurepreserving signatures, we notably obtain non-malleable commitments to group elements and non-interactive zero-knowledge proofs, as well as public-key encryption schemes that resist chosen-ciphertext attacks.