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 paper, we present novel constructions of chosen-ciphertext secure (CCA secure) key encapsulation mechanism (KEM) from chosen-plaintext secure (CPA secure) KEM in the standard model. It is already known that CCA secure public key encryption (PKE) can be generically constructed from CPA secure PKE and ((simulation-sound) non-interactive zero-knowledge proof) via the Naor-Yung or Dolev-Dwork-Naor transforms. Thus, one can also immediately construct CCA secure PKE from CPA secure KEM by converting CPA secure KEM into CPA secure PKE and transforming it to be CCA secure PKE. However, such a construction seems redundant since in general PKE is less efficient than KEM and it would be more efficient if we can directly construct CCA secure KEM from CPA secure KEM without intermediating CPA secure PKE. In this work, we propose new variants of the Naor-Yung and Dolev-Dwork-Naor transforms that directly convert CPA secure KEM into CCA secure KEM, and show that our proposed schemes are more efficient than the above straightforward constructions. For example, when instantiating from the decision linear assumption, ciphertext size of our Naor-Yung variant consists of 34 group elements while that of the straightforward construction consists of 47 group elements. Furthermore, we also propose another variant of the Dolev-Dwork-Naor transform from multiple KEM and show that a KEM which is obtained from Wee's extractable hash proof system can also be considered as an efficient construction of multiple KEM.
In a recent paper at Asiacrypt'2012, Jain et al point out that Veron code-based identification scheme is not perfect zero-knowledge. In particular, this creates a gap in security arguments of proof of plaintext knowledge (PPK) and verifiable encryption for the McEliece public key encryption (PKE) proposed by Morozov and Takagi at ACISP'2012. We fix the latter result by showing that PPK for the code-based Niederreiter and McEliece PKE's can be constructed using Stern zero-knowledge identification scheme, which is unaffected by the above mentioned problem. Since code-based verifiable encryption uses PPK as a main ingredient, our proposal presents a fix for the McEliece verifiable encryption as well. In addition, we present the Niederreiter verifiable encryption.
This thesis proposes several protocols for achieving secure com- putation under concurrent and physical attacks. Secure computation allows many parties to compute a joint function of their inputs, while keeping the privacy of their input preserved. It is required that the pri- vacy one party's input is preserved even if other parties participating in the protocol collude or deviate from the protocol. In this thesis we focus on concurrent and physical attacks, where adversarial parties try to break the privacy of honest parties by ex- ploiting the network connection or physical weaknesses of the honest parties' machine. In the rst part of the thesis we discuss how to construct proto- cols that are Universally Composable (UC for short) based on physical setup assumptions. We explore the use of Physically Uncloneable Func- tions (PUFs) as setup assumption for achieving UC-secure computa- tions. PUF are physical noisy source of randomness. The use of PUFs in the UC-framework has been proposed already in [14]. However, this work assumes that all PUFs in the system are trusted. This means that, each party has to trust the PUFs generated by the other parties. In this thesis we focus on reducing the trust involved in the use of such PUFs and we introduce the Malicious PUFs model in which only PUFs generated by honest parties are assumed to be trusted. Thus the secu- rity of each party relies on its own PUF only and holds regardless of the goodness of the PUFs generated/used by the adversary. We are able to show that, under this more realistic assumption, one can achieve UC- secure computation, under computational assumptions. Moreover, we show how to achieve unconditional UC-secure commitments with (ma- licious) PUFs and with stateless tamper-proof hardware tokens. We discuss our contribution on this matter in Part I. These results are contained in papers [80] and [28]. In the second part of the thesis we focus on the concurrent setting, and we investigate on protocols achieving round optimality and black- box access to a cryptographic primitive. We study two fundamental functionalities: commitment scheme and zero knowledge, and we focus on some of the round-optimal constructions and lower bounds con- cerning both functionalities. We nd that such constructions present subtle issues. Hence, we provide new protocols that actually achieve the security guarantee promised by previous results. Concerning physical attacks, we consider adversaries able to re- set the machine of the honest party. In a reset attack a machine is forced to run a protocol several times using the same randomness. In this thesis we provide the rst construction of a witness indistinguish- able argument system that is simultaneous resettable and argument of knowledge. We discuss about this contribution in Part III, which is the content of the paper. [edited by Author]
Open access
Cryptography and Data Security
Physical Unclonable Functions (PUFs) and Hardware Security
The main aim of cryptography is to provide the frameworks and solutions for information security. The fundamental weapons to protect information are interactions and private randomness. Since the breakthrough result, zero-knowledge proof system, by Goldwasser, Micali, and Rackoff in mid 80s, the cryptography community has endeavored to propose the new notions of information security and the relative solutions which more closely reflect the modern computing environment. Concurrent security first introduced by Dwork, Naor, and Sahai was suggested to capture the information security in the modern internet environment. That is, the adversary may interact with a honest parties in many concurrent executions of a protocol where the messages are scheduled in any adversarial way.Resettable security was first introduced by Canetti, Goldreich, Goldwasser, and Micali, which models the security issues in which parties have a limited source of private randomness. In other words, an adversary might interact with honest parties in many executions of a protocol while the honest parties are only allowed to use the polynomially bounded number of (hard-wired) randomness.An important question is: "How much efficient protocol can we construct to achieve the above security in terms of round complexity?" Unfortunately, it has been showed that the best possible round complexity for such protocols is poly-logarithmic in the security parameter based on black-box simulation without help of external set-up assumptions. Thus, the question is now to minimize the round complexity of protocols with a minimal set-up assumption.In this thesis, we positively answer the above question with help of set-up assumptions. Specifically, we consider two set-up assumptions, the Bare Public Key (BPK) model and the Cross-Domain (CD) model. The BPK model was first introduced by Canetti, Goldreich, Goldwasser, and Micali. In the BPK model, each party is required to register their public keys before the start of interacting with each other. The CD model is a newly proposed model in this work. In the CD model, we have domains which models key certification authorities in the real world and each party belongs to one of the domains.In the BPK model, we show a constructions of constant-round simultaneously resettable zero-knowledge argument of knowledge with a standard cryptographic assumptions. As a main building block for this result, we show a construction of constant-round simultaneously resettable witness-indistinguishable argument of knowledge.In the CD model, we show a construction of constant-round concurrently secure multi-party computation protocol with the fixed number of domains. On the other hand, we prove that if the number of domains is not fixed, such a constant-round protocol does not exist.
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.
Sherman S. M. Chow, Matthew Franklin, Haibin Zhang
Abstract. We reformalize and recast dual-receiver encryption (DRE) proposed in CCS â04, a public-key encryption (PKE) scheme for encrypting to two independent recipients in one shot. We start by defining the crucial soundness property for DRE, which ensures that two recipients will get the same decryption result. While conceptually simple, DRE with soundness turns out to be a powerful primitive for various goals for PKE, such as complete non-malleability (CNM) and plaintext-awareness (PA). We then construct practical DRE schemes without random oracles under the Bilinear Decisional Diffie-Hellman assumption, while prior approaches rely on random oracles or inefficient non-interactive zero-knowledge proofs. Finally, we investigate further applications or extensions of DRE, including DRE with CNM, combined use of DRE and PKE, strengthening two types of PKE schemes with plaintext equality test, off-the-record messaging with a stronger notion of deniability, etc.
Katz and Vaikuntanathan recently improved smooth projective hash functions in order to build oneround password-authenticated key exchange protocols (PAKE). To achieve security in the UC framework they allowed the simulator to extract the hashing key, which required simulation-sound non-interactive zero-knowledge proofs that are unfortunately inefficient. We improve the way the latter extractability is obtained by introducing the notion of trapdoor smooth projective hash function (TSPHF). A TSPHF is an SPHF with a trapdoor, which may not allow to recover the complete hashing key, but which still allows to compute the hash value, which is enough for an application to PAKE with UC-security against static corruptions. We additionally show that TSPHFs yield zero-knowledge proofs in two flows, with straight-line extractability. Besides those quite interesting applications of TSPHF, we also show how to generically build them on languages of ciphertexts, using any ElGamal-like encryption. Our concrete instantiations lead to efficient one-round UC-secure PAKE, extractable zero-knowledge arguments, and verifiable encryption of Waters signatures. In the case of the PAKE, our construction is the most efficient one-round UC-secure PAKE to date.
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
We consider a class of two-party function evaluation protocols in which the parties are allowed to<br/>use ideal functionalities as well as a set of powerful primitives, namely commitments, homomorphic<br/>encryption, and certain zero-knowledge proofs. We illustrate that with these it is possible to capture<br/>protocols for oblivious transfer, coin- ipping, and generation of multiplication-triple.<br/>We show how any protocol in our class can be compiled to a symbolic representation expressed<br/>as a process in an abstract process calculus, and prove a general computational soundness theorem<br/>implying that if the protocol realises a given ideal functionality in the symbolic setting, then the<br/>original version also realises the ideal functionality in the standard computational UC setting. In<br/>other words, the theorem allows us to transfer a proof in the abstract symbolic setting to a proof in<br/>the standard UC model.<br/>Finally, we show that the symbolic interpretation is simple enough in a number of cases for the<br/>symbolic proof to be partly automated using ProVerif
Henry Corrigan-Gibbs, Wendy Mu, Dan Boneh, Bryan Ford
The security of any cryptosystem relies on the secrecy of the system's secret keys. Yet, recent experimental work demonstrates that tens of thousands of devices on the Internet use RSA and DSA secrets drawn from a small pool of candidate values. As a result, an adversary can derive the device's secret keys without breaking the underlying cryptosystem. We introduce a new threat model, under which there is a systemic solution to such randomness flaws. In our model, when a device generates a cryptographic key, it incorporates some random values from an "entropy authority" into its cryptographic secrets and then proves to the authority, using zero-knowledge-proof techniques, that it performed this operation correctly. By presenting an entropy-authority-signed public key certificate to a third party (like a certificate authority or SSH client), the device can demonstrate that its public key incorporates randomness from the authority and is therefore drawn from a large pool of candidate values. Where possible, our protocol protects against eavesdroppers, entropy authority misbehavior, and devices attempting to discredit the entropy authority. To demonstrate the practicality of our protocol, we have implemented and evaluated its performance on a commodity wireless home router. When running on a home router, our protocol incurs a $1.7\times$ slowdown over conventional RSA key generation and it incurs a $3.6\times$ slowdown over conventional EC-DSA key generation.
Eli BenâSasson, Alessandro Chiesa, Eran Tromer, Madars Virza
We design and build a system that enables clients to verify the outputs of programs executed by untrusted servers. A server provides a succinct non-interactive zero-knowledge proof (also known as a zk-SNARK), which the client verifies to ascertain correct execution. The system has two components: a cryptographic proof system for verifying satisfiability of arithmetic circuits, and a circuit generator to translate program executions to such circuits. Our design of both components improves in functionality and efficiency over previous work, as follows. Our circuit generator is the first to be universal: it does not need to know the program, but only a bound on its running time. It is also the first to support programs expressed as code for a von Neumann RISC random-access memory architecture, where programs may use just-in-time compilation and selfmodifying code. Moreover, the dependence on program size is additive (instead of multiplicative as in prior works), allowing efficient verification of large programs. The cryptographic proof system significantly improves proving and verification times, using a new pairing-based cryptographic library tailored to the protocol. We evaluated our system for programs with up to 10,000 instructions, running for up to 32,000 machine steps, each of which can arbitrarily access random-access memory; and demonstrated it executing programs that use just-in-time compilation. Our proofs are 230 bytes long at 80 bits of security, or 288 bytes long at 128 bits of security. Typical verification time is 5 ms, regardless of the original programâs running time.
Abstract Crypto-computing is a set of well-known techniques for com-puting with encrypted data. The security of the corresponding proto-cols are usually proven in the semi-honest model. In this work, we pro-pose a new class of zero-knowledge proofs, which are tailored for crypto-computing protocols. First, these proofs directly employ properties of the underlying crypto systems and thus many facts have more concise proofs compared to generic solutions. Second, we show how to achieve univer-sal composability in the trusted set-up model where all zero-knowledge proofs share the same system-wide parameters. Third, we derive a new protocol for multiplicative relations and show how to combine it with several crypto-computing frameworks.
Abstract Password-authenticated key exchange (PAKE) protocols allow two players to agree on a shared high entropy secret key, that depends on their own passwords only. Following the Gennaro and Lindellâs approach, with a new kind of smooth-projective hash functions (SPHFs), Katz and Vaikuntanathan recently came up with the first concrete one-round PAKE protocols, where the two players just have to send simultaneous flows to each other. The first one is secure in the Bellare-Pointcheval-Rogaway (BPR) model and the second one in the Canettiâs UC framework, but at the cost of simulation-sound non-interactive zero-knowledge (SS-NIZK) proofs (one for the BPR-secure protocol and two for the UC-secure one), which make the overall constructions not really efficient. This paper follows their path with, first, a new efficient instantiation of SPHF on Cramer-Shoup ciphertexts, which allows to get rid of the SS-NIZK proof and leads to the design of the most efficient one-round PAKE known so far, in the BPR model, and in addition without pairings. In the UC framework, the security proof required the simulator to be able to extract the hashing key of the SPHF, hence the additional SS-NIZK proof. We improve the way the latter extractability is obtained by introducing the notion of trapdoor smooth projective hash functions (TSPHFs). Our concrete instantiation leads to the most efficient one-round PAKE UC-secure against static corruptions to date. We additionally show how these SPHFs and TSPHFs can be used for blind signatures and zero-knowledge proofs with straight-line extractability. 1
Zero-knowledge proofs are proofs that are both convincing and yet yield nothing beyond the validity of the assertion being proved. Their direct applications in cryptography are numerous, where they are typically used to force malicious parties to behave according to a predetermined protocol. In addition, zero-knowledge proofs serve as an excellent bench-mark for the study of various problems regarding cryptographic protocols.
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!
Abstract. Groth-Sahai proofs are efficient non-interactive zero-knowledge proofs that have found widespread use in pairingbased cryptography. We propose efficiency improvements of Groth-Sahai proofs in the SXDH setting, which is the one that yields the most efficient non-interactive zero-knowledge proofs. â We replace some of the commitments with ElGamal encryptions, which reduces the proverâs computation and for some types of equations reduces the proof size. â Groth-Sahai proofs are zero-knowledge when no public elements are paired to each other. We observe that they are also zero-knowledge when base elements for the groups are paired to public constants. â The proverâs computation can be reduced by letting her pick her own common reference string. By giving a proof she has picked a valid common reference string this does not compromise soundness. â We define a type-based commit-and-prove scheme, which allows commitments to be reused in many different proofs.
Authentication is a process by which an entity, which could be a person or intended computer, establishes its identity to another entity. In private and public computer networks including the Internet, authentication is commonly done through the use of logon passwords. Knowledge of the password is assumed to guarantee that the user is authentic. Internet business and many other transactions require a more stringent authentication process. The aim of this paper is to propose two authentication schemes based on general non-commutative rings. The key idea of the schemes is that for a given non-commutative ring; one can build polynomials on additive structure and takes them as underlying work structure. By doing so, one can implement authentication schemes, one of them being zero-knowledge interactive proofs of knowledge, on multiplicative structure of the ring. The security of the schemes is based on the intractability of the polynomial symmetrical decomposition problem over the given non-commutative ring.
Kai-Min Chung, Edward Lui, Mohammad Mahmoody, Rafael Pass
Goldreich and Oren (JoCâ94) show that only trivial languages have 2-message zero-knowledge arguments. In this note we consider weaker, super-polynomial-time simulation (SPS), notions of zero-knowledge. We present barriers to using black-box reductions for demonstrating soundness of 2-message protocols with efficient prover strategies satisfying SPS zero-knowledge. More precisely, we show that assuming the existence of poly(T (n))-hard one-way functions, the following holds: âą For sub-exponential (or smaller) T (·), polynomial-time black-box reductions cannot be used to prove soundness of 2-message T (·)-simulatable arguments based on any polynomialtime intractability assumption. This matches known 2-message quasi-polynomial-time simulatable arguments using a quasi-polynomial-time reduction (Passâ03), and 2-message exponential-time simulatable proofs using a polynomial-time reduction (Dwork-Naorâ00, Passâ03). âą poly(T (·))-time black-box reductions cannot be used to prove soundness of 2-message strong T (·)-simulatable (efficient prover) arguments based on any poly(T (·))-time intractability assumption; strong T (·)-simulatability means that the output of the simulator is indistinguishable also for poly(T (·))-size circuits. This matches known 3-message strong quasi-polynomial-time simulatable proofs (Blumâ86, Canetti et al â 00).
The simulation paradigm, introduced by Goldwasser, Micali and Racko , is of fundamental importance to modern cryptography. In a breakthrough work from 2001, Barak (FOCS'01) introduced a novel non-black-box simulation technique. This technique enabled the construction of new cryptographic primitives, such as resettably-sound zero-knowledge arguments, that cannot be proven secure using just black-box simulation techniques. The work of Barak and its follow-ups, however, all require stronger cryptographic hardness assumptions than the minimal assumption of one-way functions: the work of Barak requires the existence of collision-resistant hash functions, and a very recent result by Bitansky and Paneth (FOCS'12) instead requires the existence of an Oblivious Transfer protocol. In this work, we show how to perform non-black-box simulation assuming just the existence of one-way functions. In particular, we demonstrate the existence of a constant-round resettably-sound zero-knowledge argument based only on the existence of one-way functions. Using this technique, we determine necessary and su cient assumptions for several other notions of resettable security of zero-knowledge proofs. An additional bene t of our approach is that it seemingly makes practical implementations of non-black-box zero-knowledge viable.
Chengdong Meng, Zhengyong Zhang, Rong Hu, Yongxiang Yang
DAA (Direct Anonymous Attestation) schemes are generally employed with the hardware of TPM to realize anonymous authentication. Basically, DAA schemes are based on group signatures. We propose a new DAA scheme based on a short group signature without encryption which departs from the traditional sign-encrypt-prove paradigm, only adopts an anonymous signature and non-interactive zero knowledge(NIZK) proofs. Compared to other DAA schemes at present, our scheme is approximately the most efficient and computational cost-saving with shorter signature length and easier signature generation. Our scheme also satisfies anonymity, trace ability and non-frame ability requirements.