An improved method of generating trapdoor on ideal lattice was proposed by a stronger regularity bound theorem,then with R-LWE encryption algorithm and strongly unforgeable one-time signature tool from ideal lattice,an adaptive chosen-ciphertext attack(CCA) secure PKE scheme under the standard model was designed.The new PKE scheme supported public ciphertext integrity verification,could achieve block encryption and had a high encryption/decryption speed and a low encryption blowup factor,whose security proved reduced to decisional R-LWE assumption tightly.The construction is the first CCA-secure PKE cryptosystem completely based on hard problems from ideal lattice.
An improved method of generating trapdoor on ideal lattice was proposed by a stronger regularity bound theorem,then with R-LWE encryption algorithm and strongly unforgeable one-time signature tool from ideal lattice,an adaptive chosen-ciphertext attack(CCA) secure PKE scheme under the standard model was designed.The new PKE scheme supported public ciphertext integrity verification,could achieve block encryption and had a high encryption/decryption speed and a low encryption blowup factor,whose security proved reduced to decisional R-LWE assumption tightly.The construction is the first CCA-secure PKE cryptosystem completely based on hard problems from ideal lattice.
Under the standard model, an IND-sID-CPA secure IBE (Identity Based Encryption) scheme is proposed, which is based on an improved trapdoor generation function over ring and decisional R-LWE (ring-learning with errors) assumption, thus the hardness of recovering system master key can be reduced to solve the Ideal-SIS (small integer solution) problem, and the attack to the ciphertext is equivalent to solving the SVP (the shortest vector problem) in the worst case on ideal lattice to within a fixed poly( n ) factor. Moreover, the proposed scheme has advantages of high encryption and decryption speed and low encryption blowup factor compared with all known IBE scheme from the standard lattice under the standard model.
Abstract: Using the Bonsai trees primitive and Gentry’s CPA-secure (chosen-plaintext attack) public-key encryption (PKE) scheme, we propose an efficient chosen-ciphtertext secure PKE scheme over lattice. If the decision variant of the learning with errors (LWE) problem is hard and the one-time signature used in this scheme is strong unforgeable, the proposed PKE scheme is indistinguishable against the adaptive chosen-ciphtertext attack (IND-CCA2). One of the characters for this scheme is that, before any encryption operation, the encryption algorithm uses a new choice rule to fix the public parameter matrixes used in the encryption operation. With the help of this new choice rule, we can achieve the chosen-ciphtertext security with much shorter the public key size in contrast to the lattice-based encryption scheme proposed in STOC’09 by Peikert. Moreover, as a CCA-secure PKE scheme, the message-tociphtertext expanse factor of this scheme which is controlled efficiently is nearly closed to the message-to-ciphtertext expanse factor of Gentry’s scheme which is CPA secure. Due to the quantum intractability of the LWE problem on which the scheme is based, the proposed PKE scheme is secure even in quantum-era.
Design efficient lattice-based cryptosystem secure against adaptive chosen ciphertext attack (IND-CCA2) is a challenge problem. To the date, full CCA2-security of all proposed lattice-based PKE schemes achieved by using a generic transformations such as either strongly unforgeable one-time signature schemes (SU-OT-SS), or a message authentication code (MAC) and weak form of commitment. The drawback of these schemes is that encryption requires "separate encryption". Therefore, the resulting encryption scheme is not sufficiently efficient to be used in practice and it is inappropriate for many applications such as small ubiquitous computing devices with limited resources such as smart cards, active RFID tags, wireless sensor networks and other embedded devices. In this work, for the first time, we introduce an efficient universal random data padding (URDP) scheme, and show how it can be used to construct a "direct" CCA2-secure encryption scheme from "any" worst-case hardness problems in (ideal) lattice in the standard model, resolving a problem that has remained open till date. This novel approach is a "black-box" construction and leads to the elimination of separate encryption, as it avoids using general transformation from CPA-secure scheme to a CCA2-secure one. IND-CCA2 security of this scheme can be tightly reduced in the standard model to the assumption that the underlying primitive is an one-way trapdoor function.
The Learning with Errors (LWE) problem is a special average-case lattice problem, which has proved to be as hard as worst-case lattice problems. By this property, it has become the cornerstones for a series of cryptographic applications under the security assumption of worst-case lattice problems. However, the efficiency of these applications are not high. Therefore, how to improve the efficiency of cryptographic applications based on LWE is an urgent problem to be solved. In this paper, a new variant of LWE is proposed. By using trapdoor composed by lattice-based matrix and its dual orthogonal matrix, we construct a more efficient public key encryption (PKE) scheme based on the variant. Furthermore, by the hardness of the variant problem, we prove the new PKE scheme is chosen plaintext attack (CPA) secure. At last, we analyze the homomorphism property of the new PKE scheme.
Key encapsulation mechanism (KEM) is an important key distribution mechanism that not only allows both sender and receiver to safely share a random session key, but also can be mainly applied to construct a hybrid public key encryption scheme. In this paper, we give an positive answer to the question of if it is possible to build an efficient KEM over lattices. More precisely, we design an efficient KEM scheme in standard model based on ideal lattices. We prove that the proposed scheme captures indistinguishability against active chosen ciphertext attacks (IND-CCA) under the ring learning with errors problem, or more formally, IND-CCA security. Compared with the current CCA secure KEM schemes based on lattices in the standard model, our scheme has shorter public key, secret key and encapsulation ciphertext. In addition, our KEM scheme realizes IND-CCA security in the standard model.
In a selective-opening, chosen-ciphertext attack (SO-CCA) against a public key encryption scheme (PKE scheme), a probabilistic polynomial time (PPT) adversary obtains a vector of challenge ciphertexts, has access to a decryption oracle, adaptively selects to open some of the challenge ciphertexts and sees the corresponding messages together with the random coins. The simulation-based, selective-opening security against chosen-ciphertext attacks (SIM-SO-CCA security) protects the security of the unopened messages in a semantic way, i.e. it requires that the output of the adversary can be simulated by a simulator who sees only the opened messages. In particular, all information that the adversary can get from the unopened messages can also be simulated from the opened messages alone by the simulator. All security proofs of the available PKEs achieving SIM-SO-CCA security are not tight, and the security loss depends either on the number of challenge ciphertexts or on the number of decryption queries. In this work, we present the first PKE scheme which achieves SIM-SO-CCA security with a tight reduction to standard assumptions. This partially solves the open problem proposed by Hofheinz in EuroCrypt 2012.