Masayuki Abe, Jan Camenisch, Maria Dubovitskaya, Ryo Nishimaki
In this paper, we provide the first scheme that realises an attribute-based access control system for static resources that offers maximal privacy and is secure in the universal composability framework (UC). More precisely, we offer a protocol for adaptive oblivious transfer, where the sender can enforce an attribute-based access control policy for each record and nevertheless learns neither which record a user retrieves nor which attributes a user has. As additional results we provide a new structure-preserving signature scheme from the SXDH assumption and a new universally composable adaptive oblivious transfer protocol that is secure under two DDH-like assumptions and is the most efficient one secure under ``non $q$-type'' assumptions. We believe the new signature scheme to be of independent interest as a building block that is compatible with Groth-Sahai non-interactive zero-knowledge proofs.
George Danezis, Cédric Fournet, Markulf Kohlweiss, Bryan Parno
Bitcoin is the first widely adopted distributed e-cash system and Zerocoin is a recent proposal to extend Bitcoin with anonymous transactions. The original Zerocoin protocol relies heavily on the Strong RSA assumption and double-discrete logarithm proofs, long-standing techniques with known performance restrictions. We show a variant of the Zerocoin protocol using instead elliptic curves and bilinear pairings. The proof system makes use of modern techniques based on quadratic arithmetic programs resulting in smaller proofs and quicker verification. We remark on several extensions to Zerocoin that are enabled by the general-purpose nature of these techniques.
We present a constant-round concurrent zero-knowledge protocol for NP. Our protocol relies on the existence of families of collision-resistant hash functions, and a new, but in our eyes, natural complexity-theoretic assumption: the existence of P-certificates-that is, "succinct" non-interactive proofs/arguments for P. As far as we know, our results yield the first constant-round concurrent zero-knowledge protocol for NP with an explicit zero-knowledge simulator based on any assumption.
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.
Maryam Rajabzadeh Asaar, Ali Vardasbi, Mahmoud Salmasizadeh
Strong designated verifier signature (SDVS) is characterized by two properties; namely the non-transferability and the privacy of the signer's identity (PSI). Non-transferability prevents anyone else other than the designated verifier to verify the signature, while PSI prevents a third party to distinguish between two different signers. In this paper, we propose a non-delegatable SDVS which uses a trusted third party for the key generation. Our signature scheme does not use bilinear pairings which makes it suitable for the resource constraint applications. Using one-way homomorphic functions, our scheme is presented at an abstract level, the unification of which was noticed by Maurer in the context of zero knowledge proofs of knowledge in Africacrypt 2009. The security of the proposed scheme is proved in the random oracle model, provided that the homomorphism one-wayness and the gap Diffie-Hellman assumptions hold. When a Schnorr-like homomorphism is used to construct our scheme, six exponentiations are needed in the signing step and seven for the verification step. This means a meaningful gap between the performance of our scheme and that of its predecessors which use pairings in their signing and/or verification steps.
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.
Abstract. Verifiably encrypted signatures (VES) are signatures encrypted by a public key of a trusted third party and we can verify their validity without decryption. This paper proposes a new VES scheme which is secure under the decisional linear (DLIN) assumption in the standard model. We also propose new obfuscators for encrypted signatures (ES) and encrypted VES (EVES) which are secure under the DLIN assump-tion. All previous efficient VES schemes in the standard model are either secure under standard assumptions (such as the computational Diffie-Hellman assumption) with large verification (or secret) keys or secure under (non-standard) dynamic q-type assumptions (such as the q-strong Diffie-Hellman extraction assumption) with short verification keys. Our construction is the first efficient VES scheme with short verification (and secret) keys secure under a standard assumption (DLIN). As by-products of our VES scheme, we construct new obfuscators for ES/EVES based on our new VES scheme. They are more efficient than previous obfuscators with respect to the public key size. Previous ob-fuscators for EVES are secure under non-standard assumption and use zero-knowledge (ZK) proof systems and Fiat-Shamir heuristics to obtain non-interactive ZK, i.e., its security is considered in the random oracle model. Thus, our construction also has an advantage with respect to as-sumptions and security models. Our new obfuscator for ES is obtained from our new obfuscator for EVES.
Abstract. We present a set of new, efficient, universally composable two-party protocols for evaluating reactive arithmetic circuits modulo n, where n is a safe RSA modulus of unknown factorization. Our protocols are based on a homomorphic encryption scheme with message space Zn, zero-knowledge proofs of existence, and a novel “mixed ” trapdoor commitment scheme. Our protocols are proven secure against adaptive corruptions (assuming secure erasures) under standard assumptions in the CRS model (without random oracles). Our protocols appear to be the most efficient ones that satisfy these security requirements. In contrast to prior protocols, we provide facilities that allow for the use of our protocols as building blocks of higher-level protocols. An additional contribution of this paper is a universally composable construction of the variant of the Dodis-Yampolskiy oblivious pseudorandom function in a group of order n as originally proposed by Jarecki and Liu.
Abstract. Consider a joint distribution (X,A) on a set X ×{0, 1}ℓ. We show that for any family F of distinguishers f: X × {0, 1}ℓ → {0, 1}, there exists a simulator h: X → {0, 1}ℓ such that 1. no function in F can distinguish (X,A) from (X,h(X)) with advantage ǫ, 2. h is only O(23ℓǫ−2) times less efficient than the functions in F. For the most interesting settings of the parameters (in particular, the cryptographic case where X has superlogarithmic min-entropy, ǫ> 0 is negligible and F consists of circuits of polynomial size), we can make the simulator h deterministic. As an illustrative application of this theorem, we give a new security proof for the leakage-resilient stream-cipher from Eurocrypt’09. Our proof is simpler and quantitatively much better than the original proof using the dense model theorem, giving meaningful security guarantees if instantiated with a standard blockcipher like AES. Subsequent to this work, Chung, Lui and Pass gave an interactive variant of our main theorem, and used it to investigate weak notions of Zero-Knowledge. Vadhan and Zheng give a more constructive version of our theorem using their new uniform min-max theorem. 1
Melissa Chase, Markulf Kohlweiss, Anna Lysyanskaya, Sarah Meiklejohn
A signature scheme is malleable if, on input a message m and a signature σ, it is possible to efficiently compute a signature σ ′ on a related message m ′ = T (m), for a transformation T that is allowable with respect to this signature scheme. Previous work considered various useful flavors of allowable transformations, such as quoting and sanitizing messages. In this paper, we explore a connection between malleable signatures and anonymous credentials, and give the following contributions: • We define and construct malleable signatures for a broad category of allowable transformation classes, with security properties that are stronger than those that have been achieved previously. Our construction of malleable signatures is generically based on malleable zero-knowledge proofs, and we show how to instantiate it under the Decision Linear assumption. • We construct delegatable anonymous credentials from signatures that are malleable with respect to an appropriate class of transformations; we also show that our construction of malleable signatures works for this class of transformations. The resulting concrete instantiation is the first to achieve security under a standard assumption (Decision Linear) while also scaling linearly with the number of delegations. 1
The notion of zero-knowledge [GMR85] is formalized by requiring that for every malicious efficient verifier V ∗ , there exists an efficient simulator S that can reconstruct the view of V ∗ in a true interaction with the prover, in a way that is indistinguishable to every polynomialtime distinguisher. Weak zero-knowledge weakens this notions by switching the order of the quantifiers and only requires that for every distinguisher D, there exists a (potentially different) simulator SD. In this paper we consider various notions of zero-knowledge, and investigate whether their weak variants are equivalent to their strong variants. Although we show (under complexity assumption) that for the standard notion of zero-knowledge, its weak and strong counterparts are not equivalent, for meaningful variants of the standard notion, the weak and strong counterparts are indeed equivalent. Towards showing these equivalences, we introduce new non-black-box simulation techniques permitting us, for instance, to demonstrate that the classical 2-round graph non-isomorphism protocol of Goldreich-Micali-Wigderson [GMW91] satisfies a “distributional” variant of zero-knowledge. Our equivalence theorem has other applications beyond the notion of zero-knowledge. For instance, it directly implies the dense model theorem of Reingold et al (STOC ’08), and the leakage lemma of Gentry-Wichs (STOC ’11), and provides a modular and arguably simpler proof of these results (while at the same time recasting these result in the language of zeroknowledge). 0 1
As recent studies show, the notions of program obfuscation and zero knowledge are intimately connected. In this work, we explore this connection further, and prove the following general result. If there exists differing input obfuscation (diO) for the class of all polynomial time Turing machines, then there exists a four message, fully concurrent zero-knowledge proof system for all languages in NP with negligible soundness error. This result is constructive: given diO, our reduction yields an explicit protocol along with an explicit simulator that is “straight line” and runs in strict polynomial time. Our reduction relies on a new non-black-box simulation technique which does not use the PCP theorem. In addition to assuming diO, our reduction also assumes (standard and polynomial time) cryptographic assumptions such as collision-resistant hash functions. The round complexity of our protocol also sheds new light on the exact round complexity of concurrent zero-knowledge. It shows, for the first time, that in the realm of non-black-box simulation, concurrent zero-knowledge may not necessarily require more rounds than stand alone zero-knowledge!
We define a novel notion of quasi-adaptive non-interactive zero knowledge (NIZK) proofs for probability distributions on parametrized languages. It is quasi-adaptive in the sense that the common reference string (CRS) generator can generate the CRS depending on the parameters defining the language. However, the simulation is required to be uniform, i.e., a single efficient simulator should work for the whole class of parametrized languages. For distributions on languages that are linear subspaces of vector spaces over bilinear groups, we give quasi-adaptive NIZKs that are shorter and more efficient than Groth-Sahai NIZKs. For many cryptographic applications quasi-adaptiveNIZKs suffice, and our constructionscan lead to significant improvements in the standard model. Our construction can be based on any k-linear assumption, and in particular under the Symmetric eXternal Diffie Hellman (SXDH) assumption our proofs are even competitive with Random-Oracle based Σ-protocol NIZK proofs. We also show that our system can be extended to include integer tags in the defining equations, where the tags are provided adaptively by the adversary. This leads to applicability of our system to many applications that use tags, e.g. applications using Cramer-Shoup projective
Marcin Andrychowicz, Stefan Dziembowski, Daniel Malinowski, Łukasz Mazurek
Abstract. We show how the Bitcoin currency system (with a small modification) can be used to obtain fairness in any two-party secure computation protocol in the following sense: if one party aborts the protocol after learning the output then the other party gets a financial compensation (in bitcoins). One possible application of such protocols is the fair contract signing: each party is forced to complete the protocol, or to pay to the other one a fine. We also show how to link the output of this protocol to the Bitcoin currency. More precisely: we show a method to design secure two-party protocols for functionalities that result in a “forced ” financial transfer from one party to the other. Our protocols build upon the ideas of our recent paper “Secure Multiparty Computations on Bitcoin ” (Cryptology ePrint Archive, Report 2013/784). Compared to that paper, our results are more general, since our protocols allow to compute any function, while in the previous paper we concentrated only on some specific tasks (commitment schemes and lotteries). On the other hand, as opposed to “Secure Multiparty Computations on Bitcoin”, to obtain security we need to modify the Bitcoin specification so that the transactions are “non-malleable ” (we discuss this concept in more detail in the paper). 1