Efficient Lattice-Based Zero-Knowledge Arguments with Standard Soundness: Construction and Applications 📺
We provide new zero-knowledge argument of knowledge systems that work directly for a wide class of language, namely, ones involving the satisfiability of matrix-vector relations and integer relations commonly found in constructions of lattice-based cryptography. Prior to this work, practical arguments for lattice-based relations either have a constant soundness error $$(2/3)$$, or consider a weaker form of soundness, namely, extraction only guarantees that the prover is in possession of a witness that “approximates” the actual witness. Our systems do not suffer from these limitations.The core of our new argument systems is an efficient zero-knowledge argument of knowledge of a solution to a system of linear equations, where variables of this solution satisfy a set of quadratic constraints. This argument enjoys standard soundness, a small soundness error $$(1/poly)$$, and a complexity linear in the size of the solution. Using our core argument system, we construct highly efficient argument systems for a variety of statements relevant to lattices, including linear equations with short solutions and matrix-vector relations with hidden matrices.Based on our argument systems, we present several new constructions of common privacy-preserving primitives in the standard lattice setting, including a group signature, a ring signature, an electronic cash system, and a range proof protocol. Our new constructions are one to three orders of magnitude more efficient than the state of the art (in standard lattice). This illustrates the efficiency and expressiveness of our argument system.
Fully Homomorphic Encryption from the Finite Field Isomorphism Problem
If q is a prime and n is a positive integer then any two finite fields of order $$q^n$$qn are isomorphic. Elements of these fields can be thought of as polynomials with coefficients chosen modulo q, and a notion of length can be associated to these polynomials. A non-trivial isomorphism between the fields, in general, does not preserve this length, and a short element in one field will usually have an image in the other field with coefficients appearing to be randomly and uniformly distributed modulo q. This key feature allows us to create a new family of cryptographic constructions based on the difficulty of recovering a secret isomorphism between two finite fields. In this paper we describe a fully homomorphic encryption scheme based on this new hard problem.
IEEE P1363.1 Draft 10: Draft Standard for Public Key Cryptographic Techniques Based on Hard Problems over Lattices
Engineering specifications and security considerations for NTRUEncrypt, secure against the lattice attacks presented at Crypto 2007
Choosing Parameter Sets for NTRUEncrypt with NAEP and SVES-3
We present, for the first time, an algorithm to choose parameter sets for NTRUEncrypt that give a desired level of security. Note: This is an expanded version of a paper presented at CT-RSA 2005.
On estimating the lattice security of NTRU
This report explicitly refutes the analysis behind a recent claim that NTRUEncrypt has a bit security of at most 74 bits. We also sum up some existing literature on NTRU and lattices, in order to help explain what should and what should not be classed as an improved attack against the hard problem underlying NTRUEncrypt. We also show a connection between Schnorr's RSR technique and exhaustively searching the NTRU lattice.
Performance Improvements and a Baseline Parameter Generation Algorithm for NTRUSign
The original presentation of the NTRUSign signature scheme gave a set of parameters that were claimed to give 80 bits of security, but did not give a general recipe for generating parameter sets to a specific level of security. In line with recent research on NTRUEncrypt, this paper presents an outline of such a recipe for NTRUSign. We also present certain technical advances upon which we intend to build in subsequent papers.
Modified Parameter Attacks: Practical Attacks against CCA2 Secure Cryptosystems and Countermeasures
We introduce the concept of Modified Parameter Attacks, a natural extension of the idea of Adapative Chosen Ciphertext Attacks (CCA2) under which some CCA2 secure systems can be shown to be insecure. These insecurities can be addressed at the application level, but can also be addressed when cryptographic schemes are being designed. We survey some existing CCA2 secure systems which are vulnerable to this attack and suggest practical countermeasures.
NAEP: Provable Security in the Presence of Decryption Failures
We consider the impact of the possibility of decryption failures in proofs of security for padding schemes, where these failures are both message and key dependent. We explain that an average case failure analysis is not necessarily sufficient to achieve provable security with existing CCA2-secure schemes. On a positive note, we introduce NAEP, an efficient padding scheme similar to PSS-E designed especially for the NTRU one-way function. We show that with this padding scheme we can prove security in the presence of decryption failures, under certain explicitly stated assumptions. We also discuss the applicability of proofs of security to instantiated cryptosystems in general, introducing a more practical notion of cost to describe the power of an adversary.
- Man Ho Au (1)
- Yarkin Doröz (1)
- Phil Hirschhorn (1)
- Jeffrey Hoffstein (7)
- Nick Howgrave-Graham (7)
- Mats Näslund (1)
- Phong Q. Nguyen (1)
- Jill Pipher (7)
- David Pointcheval (1)
- John Proos (1)
- John M. Schanck (4)
- Igor E. Shparlinski (1)
- Joseph H. Silverman (10)
- Ari Singer (3)
- Berk Sunar (1)
- Qiuliang Xu (1)
- Rupeng Yang (1)
- Zuoxia Yu (1)
- Zhenfei Zhang (5)