For any pair $(X,Z)$ of correlated random variables we can think of $Z$ as a randomized function of $X$. Provided that $Z$ is short, one can make this function computationally efficient by allowing it to be only approximately correct. In folklore this problem is known as \emph{simulating auxiliary inputs}. This idea of simulating auxiliary information turns out to be a powerful tool in computer science, finding applications in complexity theory, cryptography, pseudorandomness and zero-knowledge. In this paper we revisit this problem, achieving the following results: \begin{enumerate}[(a)] We discuss and compare efficiency of known results, finding the flaw in the best known bound claimed in the TCC'14 paper "How to Fake Auxiliary Inputs". We present a novel boosting algorithm for constructing the simulator. Our technique essentially fixes the flaw. This boosting proof is of independent interest, as it shows how to handle "negative mass" issues when constructing probability measures in descent algorithms. Our bounds are much better than bounds known so far. To make the simulator $(s,ε)$-indistinguishable we need the complexity $O\left(s\cdot 2^{5\ell}ε^{-2}\right)$ in time/circuit size, which is better by a factor $ε^{-2}$ compared to previous bounds. In particular, with our technique we (finally) get meaningful provable security for the EUROCRYPT'09 leakage-resilient stream cipher instantiated with a standard 256-bit block cipher, like $\mathsf{AES256}$.
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.
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.
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
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.
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.
Nico Döttling, Daniel Kraschewski, Jörn Müller‐Quade, Tobias Nilges
Universally composable secure computation was assumed to require trusted setups, until it was realized that parties exchanging (untrusted) tamper-proof hardware tokens allow an alternative approach (Katz; EUROCRYPT 2007). This discovery initialized a line of research dealing with two different types of tokens. Using only a single stateful token, one can implement general statistically secure two-party computation (Dottling, Kraschewski, Muller-Quade; TCC 2011); though all security is lost if an adversarial token receiver manages to physically reset and rerun the token. Stateless tokens, which are secure by definition against any such resetting-attacks, however, do provably not suffice for statistically secure computation in general (Goyal, Ishai, Mahmoody, Sahai; CRYPTO 2010). We investigate the natural question of what is possible if an adversary can reset a token at most a bounded number of times (e.g., because each resetting attempt imposes a significant risk to trigger a self-destruction mechanism of the token). Somewhat surprisingly, our results come close to the known positive results with respect to non-resettable stateful tokens. In particular, we construct polynomially many instances of statistically secure and universally composable oblivious transfer, using only a constant number of tokens. Our techniques have some abstract similarities to previous solutions, which we grasp by defining a new security property for protocols that use oracle access. Additionally, we apply our techniques to zero-knowledge proofs and obtain a protocol that achieves the same properties as bounded-query zero-knowledge PCPs (Kilian, Petrank, Tardos; STOC 1997), even if a malicious prover may issue stateful PCP oracles.
Ivan Damgård, Bernardo David, Irene Giacomelli, Jesper Buus Nielsen
We present a new compact verifiable secret sharing scheme, based on this we present the first construction of a homomorphic UC commitment scheme that requires only cheap symmetric cryptography, except for a small number of seed OTs. To commit to a k -bit string, the amortized communication cost is O ( k ) bits. Assuming a sufficiently efficient pseudorandom generator, the computational complexity is O ( k ) for the verifier and O ( k 1 + ε ) for the committer (where ε < 1 is a constant). In an alternative variant of the construction, all complexities are O ( k · polylog ( k )). Our commitment scheme extends to vectors over any finite field and is additively homomorphic. By sending one extra message, the prover can allow the verifier to also check multiplicative relations on committed strings, as well as verifying that committed vectors a , b satisfy a = φ ( b ) for a linear function φ . These properties allow us to non-interactively implement any one-sided functionality where only one party has input (this includes UC secure zero-knowledge proofs of knowledge). We also present a perfectly secure implementation of any multiparty functionality, based directly on our VSS. The communication required is proportional to a circuit implementing the functionality, up to a logarithmic factor. For a large natural class of circuits the overhead is even constant. We also improve earlier results by Ranellucci et al. on the amount of correlated randomness required for string commitments with individual opening of bits. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
Abstract. In this work, we first formalize the notion of dynamic group signatures with distributed traceability, where the capability to trace signatures is distributed among nmanagers without requiring any interaction. This ensures that only the participation of all tracing managers permits tracing a signature, which reduces the trust placed in a single tracing manager. The threshold variant follows easily from our definitions and constructions. Our model offers strong security requirements. Our second contribution is a generic construction for the notion which has a concurrent join protocol, meets strong security requirements, and offers efficient traceability, i.e. without requiring tracing managers to produce expensive zero-knowledge proofs for tracing correctness. To dispense with the expensive zero-knowledge proofs required in the tracing, we deploy a distributed tag-based encryption with public verifiability. Finally, we provide some concrete instantiations, which, to the best of our knowledge, are the first efficient provably secure realizations in the standard model simultaneously offering all the aforementioned properties. To realize our constructions efficiently, we construct an efficient distributed (and threshold) tag-based encryption scheme that works in the efficient Type-III asymmetric bilinear groups. Our distributed tag-based encryption scheme yields short ciphertexts (only 1280 bits at 128-bit security), and is secure under an existing variant of the standard decisional linear assumption. Our tag-based encryption scheme is of independent interest and is useful for many applications beyond the scope of this paper. As a special case of our distributed tag-based encryption scheme, we get an efficient tag-based encryption scheme in Type-III asymmetric bilinear groups that is secure in the standard model.
In the last few years the efficiency of secure multi-party computation (MPC) increased in several orders of magnitudes. However, this alone might not be enough if we want MPC protocols to be used in practice. A crucial property that is needed in many applications is that everyone can check that a given (secure) computation was performed correctly – even in the extreme case where all the parties involved in the computation are corrupted, and even if the party who wants to verify the result was not participating. This is especially relevant in the clients-servers setting, where many clients provide input to a secure computation performed by a few servers. An obvious example of this is electronic voting, but also in many types of auctions one may want independent verification of the result. Traditionally, this is achieved by using non-interactive zero-knowledge proofs during the computation. A recent trend in MPC protocols is to have a more expensive preprocessing phase followed by a very efficient online phase, e.g., the recent so-called SPDZ protocol by Damgard et al. Applications such as voting and some auctions are perfect use-case for these protocols, as the parties usually know well in advance when the computation will take place, and using those protocols allows us to use only cheap information-theoretic primitives in the actual computation. Unfortunately no protocol of the SPDZ type supports an audit phase. In this paper, we show how to achieve efficient MPC with a public audit. We formalize the concept of publicly auditable secure computation and provide an enhanced version of the SPDZ protocol where, even if all the servers are corrupted, anyone with access to the transcript of the protocol can check that the output is indeed correct. Most importantly, we do so without significantly compromising the performance of SPDZ i.e. our online phase has complexity approximately twice that of SPDZ.
The notion of Zero Knowledge introduced by Goldwasser, Micali and Rackoff in STOC 1985 is fundamental in Cryptography. Motivated by conceptual and practical reasons, this notion has been explored under stronger definitions. We will consider the following two main strengthened notions. Statistical Zero Knowledge: here the zero-knowledge property will last forever, even in case in future the adversary will have unlimited power. Concurrent Non-Malleable Zero Knowledge: here the zero-knowledge property is combined with non-transferability and the adversary fails in mounting a concurrent man-inthe-middle attack aiming at transferring zero-knowledge proofs/arguments. Besides the well-known importance of both notions, it is still unknown whether one can design a zero-knowledge protocol that satisfies both notions simultaneously. In this work we shed light on this question in a very strong sense. We show a statistical concurrent non-malleable zero-knowledge argument system for N P with a black-box simulatorextractor. 1
Zero knowledge proof system which has received extensive attention since it was proposed is an important branch of cryptography and computational complexity theory. Thereinto, noninteractive zero knowledge proof system contains only one message sent by the prover to the verifier. It is widely used in the construction of various types of cryptographic protocols and cryptographic algorithms because of its good privacy, authentication, and lower interactive complexity. This paper reviews and analyzes the basic principles of noninteractive zero knowledge proof system, and summarizes the research progress achieved by noninteractive zero knowledge proof system on the following aspects: the definition and related models of noninteractive zero knowledge proof system, noninteractive zero knowledge proof system of NP problems, noninteractive statistical and perfect zero knowledge, the connection between noninteractive zero knowledge proof system, interactive zero knowledge proof system, and zap, and the specific applications of noninteractive zero knowledge proof system. This paper also points out the future research directions.
Fabrice Benhamouda, Stephan Krenn, Vadim Lyubashevsky, Krzysztof Pietrzak
Abstract. We design an efficient commitment scheme, and companion zero-knowledge proofs of knowledge, based on the learning with errors over rings (RLWE) problem. In particular, for rings in which almost all elements have inverses, we construct a perfectly binding commitment scheme whose hiding property relies on the RLWE assumption. Our scheme maps elements from the ring (or equivalently, n elements from Fq) to a small constant number of ring elements. We then construct Σ-protocols for proving, in a zero-knowledge manner, knowledge of the message contained in a commitment. We are able to further extend our basic protocol to allow us to prove additive and multiplicative relations among committed values. Our protocols have a communication complexity of O(Mn log q) and achieve a negligible knowledge error in one run. Here M is the constant from a rejection sampling technique that we employ, and can be set close to 1 by adjusting other parameters. Previously known Σ-protocols for LWE-related languages either relied on “smudging ” out the error (which necessitates working over large fields, resulting in poor efficiency) or only achieved a noticeable or even constant knowledge error (thus requiring many repetitions of the protocol).
Marcin Andrychowicz, Stefan Dziembowski, Daniel Malinowski, Łukasz Mazurek
BitCoin transactions are malleable in a sense that given a transaction an adversary can easily construct an equivalent transaction which has a different hash. This can pose a serious problem in some BitCoin distributed contracts in which changing a transaction's hash may result in the protocol disruption and a financial loss. The problem mostly concerns protocols, which use a "refund" transaction to withdraw a deposit in a case of the protocol interruption. In this short note, we show a general technique for creating malleability-resilient "refund" transactions, which does not require any modification of the BitCoin protocol. Applying our technique to our previous paper "Fair Two-Party Computations via the BitCoin Deposits" (Cryptology ePrint Archive, 2013) allows to achieve fairness in any Two-Party Computation using the BitCoin protocol in its current version.
Consider a practical scenario: an untrusted gate-way is required to verify all the incoming information en-crypted via an encryption scheme, while the sender does not want to reveal any information about the plaintext and the privileged user to the gateway. That is, the gateway distributes the information to a predefined group of users and only the privileged user can open the message. To solve this problem, we need an access control mechanism to allow certain specification of the access control policies while protecting the users' privacy. With this scenario in mind, we propose the notion of verifiable and anonymous encryption where a verification function is added to the ciphertext, which captures the security requirements of the confidentiality of the plaintext and the anonymity of the privileged user. We present two specific constructions of our framework under the setting of asymmetric bilinear pairings in this paper. Our first scheme is proven confidential and anonymous under a weaker security model in the random oracle model, and our second one is built on the basis of a zero knowledge proof of knowledge under a strong security game.
Kai-Min Chung, Daniel Dadush, Feng-Hao Liu, Chris Peikert
The smoothing parameter $η_ε(\mathcal{L})$ of a Euclidean lattice $\mathcal{L}$, introduced by Micciancio and Regev (FOCS'04; SICOMP'07), is (informally) the smallest amount of Gaussian noise that "smooths out" the discrete structure of $\mathcal{L}$ (up to error $ε$). It plays a central role in the best known worst-case/average-case reductions for lattice problems, a wealth of lattice-based cryptographic constructions, and (implicitly) the tightest known transference theorems for fundamental lattice quantities. In this work we initiate a study of the complexity of approximating the smoothing parameter to within a factor $γ$, denoted $γ$-${\rm GapSPP}$. We show that (for $ε= 1/{\rm poly}(n)$): $(2+o(1))$-${\rm GapSPP} \in {\rm AM}$, via a Gaussian analogue of the classic Goldreich-Goldwasser protocol (STOC'98); $(1+o(1))$-${\rm GapSPP} \in {\rm coAM}$, via a careful application of the Goldwasser-Sipser (STOC'86) set size lower bound protocol to thin spherical shells; $(2+o(1))$-${\rm GapSPP} \in {\rm SZK} \subseteq {\rm AM} \cap {\rm coAM}$ (where ${\rm SZK}$ is the class of problems having statistical zero-knowledge proofs), by constructing a suitable instance-dependent commitment scheme (for a slightly worse $o(1)$-term); $(1+o(1))$-${\rm GapSPP}$ can be solved in deterministic $2^{O(n)} {\rm polylog}(1/ε)$ time and $2^{O(n)}$ space. As an application, we demonstrate a tighter worst-case to average-case reduction for basing cryptography on the worst-case hardness of the ${\rm GapSPP}$ problem, with $\tilde{O}(\sqrt{n})$ smaller approximation factor than the ${\rm GapSVP}$ problem. Central to our results are two novel, and nearly tight, characterizations of the magnitude of discrete Gaussian sums.
In this thesis, we construct an implementation of succinct non-interactive zero knowledge argument system. A non-interactive zero knowledge argument system is a protocol for a party (usually known as Prover) to provide a proof of knowledge to the solution of a statement to other parties (usually known as Verifier). The argument system will be able to provide such proof without leaking any other information regarding the solution. The non-interactivity allows such argument system to be done without requiring interaction between the parties involved. The statement that is proven in this work is the circuit satisfiability problem. The circuit satisfiability problem is a problem of deciding whether there exists an input that can make the final output of a circuit to be true. The argument system is based on Lipmaa's work \\cite{eprint2013:Lipmaa:NIZKSPECC} which uses span programs and linear error-correcting codes in its construction. We also try to give a very general explanation on zero knowledge argument system along the way in order to provide a simple concept to people encountering the notion for the first time. The argument system we attempt to construct is the non-adaptive version of the argument system. This version is useful for verifiable computation as pointed out by \\cite{Pinnochio2013:Parno} apart from its zero knowledge behavior. We begin by giving an overview on non-interactive zero knowledge, followed by span programs. We then proceed to describe on how to represent the circuit satisfiability problem using the mentioned tool. We present our implementation afterwards, listing out the libraries and implementation details that matters. We conclude by providing a speed measurement and possible future improvements of this work.