Abstract. In all existing efficient proofs of knowledge of a solution to the infinity norm Inhomogeneous Small Integer Solution (ISIS ∞ ) problem, the knowledge extractor outputs a solution vector that is only guaranteed to be Õ(n) times longer than the witness possessed by the prover. As a consequence, in many cryptographic schemes that use these proof systems as building blocks, there exists a gap between the hardness of solving the underlying ISIS ∞ problem and the hardness underlying the security reductions. In this paper, we generalize Stern’s protocol to obtain two statistical zero-knowledge proofs of knowledge for the ISIS ∞ problem that remove this gap. Our result yields the potential of relying on weaker security assumptions for various lattice-based cryptographic constructions. As applications of our proof system, we introduce a concurrently secure identity-based identification scheme based on the worst-case hardness of the SIVPÕ(n1.5) problem (in the ℓ2 norm) in general lattices in the random oracle model, and an efficient statistical zero-knowledge proof of plaintext knowledge with small constant gap factor for Regev’s encryption scheme.
Abstract. In all existing efficient proofs of knowledge of a solution to the infinity norm Inhomogeneous Small Integer Solution (ISIS ∞ ) problem, the knowledge extractor outputs a solution vector that is only guaranteed to be Õ(n) times longer than the witness possessed by the prover. As a consequence, in many cryptographic schemes that use these proof systems as building blocks, there exists a gap between the hardness of solving the underlying ISIS ∞ problem and the hardness underlying the security reductions. In this paper, we generalize Stern’s protocol to obtain two statistical zero-knowledge proofs of knowledge for the ISIS ∞ problem that remove this gap. Our result yields the potential of relying on weaker security assumptions for various lattice-based cryptographic constructions. As applications of our proof system, we introduce a concurrently secure identity-based identification scheme based on the worst-case hardness of the SIVPÕ(n1.5) problem (in the ℓ2 norm) in general lattices in the random oracle model, and an efficient statistical zero-knowledge proof of plaintext knowledge with small constant gap factor for Regev’s encryption scheme.
Lattice-based cryptography is one of the most active research topics in cryptography in recent years. In many cryptographic constructions based on lattice assumptions, the building block is a proof of knowledge of a solution to an instance of the Inhomogeneous Small Integer Solution (ISIS) problem. However, all known such proof \n \nsystems have relatively weak security guarantees: Breaking each of these protocols is potentially easier than solving the underlying instance of the ISIS problem. As a consequence, cryptographic constructions relying on these proof systems typically inherit the sub-optimal security guarantees. Therefore, proof systems with stronger security guarantees are highly desirable. Such protocols are not only interesting from a theoretical point of view, but they also lead to lattice-based cryptographic constructions relying on weaker hardness assumptions than the contemporary schemes. \n \n \n \nIn this thesis, we construct a series of zero-knowledge proofs of knowledge with strong security guarantees and reasonable communication costs, that can find various applications in lattice-based cryptography. Our constructions rely on a simple, yet versatile and effective technique, called Decomposition-Extension. When adapting this technique to the Stern-KTX proof system (Stern ‘96 - Kawachi, Tanaka, Xagawa ‘08), we obtain a zero-knowledge proof of knowledge for the ISIS problem (in the infinity norm) with a very strong security guarantee: Breaking the protocol is as least as hard as solving the underlying ISIS instance. We then develop our technique to design the following lattice-based cryptographic constructions: \n \n \n \n- Efficient zero-knowledge proofs of plaintext knowledge with strong security guarantees \n \nfor 4 encryption schemes based on the Learning with Errors problem: Regev’s scheme (Regev ‘05); the Dual-Regev scheme (Gentry, Peikert, Vaikuntanathan ‘08); the PVW scheme (Peikert, Vaikuntanathan, Waters ‘08); and the GHV scheme (Gentry, Halevi, Vaikuntanathan ‘10). Our results immediately yield 4 lattice-based interactive encryption protocols that are secure under chosen ciphertext attacks. Previously, only zero-knowledge proofs of plaintext knowledge for Regev’s scheme were known, and they are relatively inefficient with rather weak security guarantees. \n \n \n \n- A lattice-based identity-based identification scheme relying on a weaker hardness assumption than in the previous works. Furthermore, we introduce an identity-based ring identification scheme based on the worst-case hardness of lattice problems. To the best of our knowledge, this is the first such scheme. \n \n \n \n- An improved lattice-based group signature scheme relying on relatively weak hardness assumptions, in which the signature size is logarithmic in the number of group users. Earlier lattice-based group signature schemes, which were published before 2013, rely on relatively weak hardness assumptions but have the undesirable property that the size of the signature is linear in the number of group users. A recent scheme (Laguillaumie, Langlois, Libert, Stehlé ‘13) achieves logarithmic signature size but it has to rely on relatively strong hardness assumptions. Our construction, thus, simultaneously achieves the good features of the existing schemes.
Abstract. We present a variant of Regev’s cryptosystem first presented in [Reg05], but with a new choice of parameters. By a recent classical re-duction by Peikert we prove the scheme semantically secure based on the worst-case lattice problem GapSVP. From this we construct a threshold cryptosystem which has a very efficient and non-interactive decryption protocol. We prove the threshold cryptosystem secure against passive adversaries corrupting all but one of the players, and againts active ad-versaries corrupting less than one third of the players. We also describe how one can build a distributed key generation protocol. In the final part of the paper we show how one can, in zero-knowledge- prove knowledge of the plaintext contained in a given ciphertext from Regev’s original cryptosystem or our variant. The proof is of size only a constant times the size of the public key. 1
We introduce the notion of Resettable Zero-Knowledge (rZK), a new security measure for cryptographic protocols which strengthens the classical notion of zero-knowledge.In essence, an rZK protocol is one that remains zero knowledge even if an adversary can interact with the prover many times, each time resetting the prover to its initial state and forcing it to use the same random tape.All known examples of zero-knowledge proofs and arguments are trivially breakable in this setting.Moreover, by definition, all zero-knowledge proofs of knowledge are breakable in this setting.Under general complexity assumptions, which hold for example if the Discrete Logarithm Problem is hard, we construct: • Resettable Zero-Knowledge proof-systems for NP with non-constant number of rounds.* Five-round Resettable Witness-Indistinguishable proofsystems for NP. e Four-round Resettabie Zero-Knowledge arguments for NP in the public key model: where verifiers have fixed, public keys associated with them.In addition to shedding new light on what makes zero knowledge possible (by constructing ZK protocols that use randomness in a dramatically weaker way than before), rZK has great relevance to applications.Firstly, rZK protocols are closed under parallel and concurrent execution and thus are guaranteed to be secure when implemented in fully asynchronous networks, even if an adversary schedules the arrival of every message sent so as to foil security.Secondly, rZK protocols enlarge the range of physical ways in which provers of ZK protocols can be securely implemented, including devices which cannot reliably toss coins on line, nor keep state *A subset of this work is included in patent application [21].
We present a hash proof systems (HPS)based on hard lattice problems including learning with error (LWE) and inhomogeneous small integer solution (ISIS). Different from the HPS in past, ours is with error. That is to say, the deterministic private evaluation algorithm is not always equivalent to the deterministic public evaluation algorithm. The difference between them is one or zero. We also show how to construct a public-key encryption scheme which is semantically secure against key-leakage attacks in the standard model using our HPS based on lattice. Compared with previous cryptosystem based on lattice, our construction needs bigger public key space but fewer operations during encryption, and can resist quantum attacks because of the assumption on lattice problem.
One essential quest in cryptography is the search for hard instances of a given computational problem that is known to be hard in the worst-case. In lattice cryptography we are in the unique situation that we have found a way of picking random instances which are at least as hard as well-studied lattice problems in the worst-case. At the same time, no attack running in subexponential time is known to break these problems, even for an adversary using quantum computers. Virtually all public-key schemes in use today are subject to such attacks, and the development of quantum computers is actively pursued, so it is prudent to investigate lattice-based alternatives. There are two fundamental open problems in lattice cryptography today and this thesis contributes to solving them. First, there exists a widely used efficiency improvement that allows for trapdoors whose asymptotic keysize and evaluation time are both quasilinear in the dimension of an associated lattice. This is accomplished by restricting oneself to lattices with special structure, so-called ideal lattices. This entails the use of newer security assumptions, but these have not been analyzed thoroughly so far. We start this work by comparing the class of ideal lattice problems with its general counterpart in terms of size. Affirming folklore, we find the number of restricted instances among all instances to be asymptotically negligible for those classes of lattices suggested for practical use. The second open problem is that while the connection to worst-case problems is well understood, the practical hardness of the related average-case problems is not. Specifically, there have been parameters suggested for practical usage, where current lattice basis reduction algorithms can solve these worst-case problems, but the related average-case problems, which these are reduced to and which represent the basis of practical security of the cryptosystems, are completely infeasible. In most cases, this lack of understanding has lead either to a very conservative choice of parameters, or none at all. This in turn makes it impossible for the resulting lattice schemes to compete with their counterparts based on other paradigms. We further the understanding of this practical security and at the same time improve the efficiency of several common related cryptographic schemes. Among other things, we find that for the SWIFFT compression function, solving certain problems closely related to finding collisions is easier than previously thought and we suggest efficient replacement parameters. We propose a novel zero-knowledge identification scheme that, to our knowledge, beats all competing post-quantum schemes, even those based on other paradigms. Possibly most important, we help to tighten the efficiency gap between lattice encryption schemes that are provably secure and the acclaimed ad-hoc encryption scheme NTRU. This is done by unifying many recent developments into a new provably secure design and providing a comprehensive analysis of practical security, which together results in a great leap of efficiency.
We introduce the notion of Resettable Zero-Knowledge (rZK), a new security measure for cryptographic protocols which strengthens the classical notion of zero-knowledge. In essence, an rZK protocol is one that remains zero knowledge even if an adversary can interact with the prover many times, each time resetting the prover to its initial state and forcing it to use the same random tape. Under general complexity assumptions, which hold for example if the Discrete Logarithm Problem is hard, we construct (non-constant round) Resettable Zero-Knowledge proof-systems for NP constant-round Resettable Witness-Indistinguishable proof-systems for NP constant-round Resettable Zero-Knowledge arguments for NP in the public key model: where veriers have fixed, public keys associated with them. In addition to shedding new light on what makes zero knowledge possible (by constructing ZK protocols that use randomness in a dramatically weaker way than before), rZK has great relevance to applications. Firstly, we show that rZK protocols are closed under parallel and