Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

ACM Asia Conference on Computer and Communications Security (ASIA CCS)

NTRUReEncrypt

David Núñez, Isaac Agudo, Javier López

Published Apr 3, 2015• 45 citations
Publisher

Abstract

The use of alternative foundations for constructing more secure and efficient cryptographic schemes is a topic worth exploring. In the case of proxy re-encryption, the vast majority of schemes are based on number theoretic problems such as the discrete logarithm. In this paper we present NTRUReEncrypt, a new bidirectional and multihop proxy re-encryption scheme based on NTRU, a widely known lattice-based cryptosystem. We provide two versions of our scheme: the first one is based on the conventional NTRU encryption scheme and, although it lacks a security proof, remains as efficient as its predecessor; the second one is based on a variant of NTRU proposed by Stehlé and Steinfeld, which is proven CPA-secure under the hardness of the Ring-LWE problem. To the best of our knowledge, our proposals are the first proxy re-encryption schemes to be based on the NTRU primitive. In addition, we provide experimental results to show the efficiency of our proposal, as well as a comparison with previous proxy re-encryption schemes, which confirms that our first scheme outperforms the rest by an order of magnitude.

DOI
10.1145/2714576.2714585

Related papers

Collusion-resistant unidirectional proxy re-encryption scheme from lattices

Kee Sung Kim, Ik Rae Jeong

Most of the previous proxy re-encryption schemes rely on the average-case hardness problems such as the integer factorization problems and the discrete logarithm problems. Therefore, they cannot guarantee its security under quantum analysis, since there exist quantum algorithms efficiently solving the factorization and logarithm problems. In the paper, we propose the first proxy re-encryption scheme based on the hard worst-case lattice problems. Our scheme has many useful properties as follows: Unidirectional, collusion-resistant, noninteractive, proxy invisible, key optimal, and nontransitive. We also provided the formal security proof of the proposed scheme in the random oracle model.

Journal of Communications and Networks•Feb 1, 2016•14 citations

Identity Based Proxy Re-encryption Scheme under LWE

Wei Yin, Qiaoyan Wen, Wenmin Li +2 more

The proxy re-encryption allows an intermediate proxy to convert a ciphertext for Alice into a ciphertext for Bob without seeing the original message and leaking out relevant information.Unlike many prior identity based proxy re-encryption schemes which are based on the number theoretic assumptions such as large integer factorization and discrete logarithm problem.In this paper, we first propose a novel identity based proxy re-encryption scheme which is based on the hardness of standard Learning With Error(LWE) problem and is CPA secure in the standard model.This scheme can be reduced to the worst-case lattice hard problem that is able to resist attacks from quantum algorithm.The key step in our construction is that the challenger how to answer the private query under a known trapdoor matrix.Our scheme enjoys properties of the non-interactivity, unidirectionality, anonymous and so on.In this paper, we utilize primitives include G-trapdoor for lattice and sample algorithms to realize simple and efficient re-encryption.

KSII Transactions on Internet and Information Systems•Dec 31, 2017•6 citations

A provably secure variant of NTRU cryptosystem

Danilo Ciaffi

In 1996 Hoffstein, Pipher ad Silverman presented NTRUEncrypt, which is to date the fastest known lattice-based encryption scheme. Its moderate key-sizes, excellent asymptotic performance and conjectured resistance to quantum attacks make it a perfect candidate to succeed where factorization and discrete log fail. Unfortunately, no security proof has been produced for NTRUEncrypt nor for its signature counterpart NTRUSign. In 2013 Stehle and Steinfield proposed to apply some mild modification to the encryption and signature scheme to make them provably secure, under the assumed quantum hardness of standard worst-case lattice problems, restricted to a family of lattices related to some cyclotomic fields. In particular they showed that if the secret key polynomials of the encryption scheme are chosen from discrete Gaussians, then the public key, i.e their ratio, is statistically indistinguishable from uniform. The security will then follow from the hardness of the R-LWE problem.The aim of this thesis is to present Stehle's and Steinfield's work in a slightly more accessi-ble form, providing some more background and details in some points.

•Oct 12, 2018•0 citations

On the Semantic Security of NTRU -- with a gentle introduction to cryptography

Liam Peet-Pare

This paper provides an explanation of NTRU, a post quantum encryption scheme, while also providing a gentle introduction to cryptography. NTRU is a very efficient lattice based cryptosystem that appears to be safe against attacks by quantum computers. NTRU's efficiency suggests that it is a strong candidate as an alternative to RSA, ElGamal, and ECC for the post quantum world. The paper begins with an introduction to cryptography and security proofs for cryptographic schemes before explaining the NTRU cryptosystem and culminating with a proof that the original presentation of NTRU is not IND-CPA secure. We will conclude by mentioning padding schemes to NTRU that are provably IND-CCA2 secure in the random oracle model. The paper is designed to be accessible to anyone with minimal background in abstract algebra and number theory - no previous knowledge of cryptography is assumed. Given the author's lack of familiarity with the subject, this paper aims to be an expository work rather than to provide new insights to the subject matter.

arXiv:2503.07790•Mar 10, 2025•0 citations

Collusion resistant identity-based proxy re-encryption scheme on lattice

Xiaohong Deng, Hua Xie, Weizhi Xiong

Proxy re-encryption plays an important role for data security in cloud computing and big data, but the traditional re-encryption scheme based on the classical number theory problem cannot resist quantum attack, and the lattice-based cryptosystem has been proved to have the ability to resist quantum attack, so the lattice-based re-encryption scheme has always been a research hotspot. In view of the problem that collusion-resistance and multi-hop cannot be satisfied at the same time in existing schemes, this paper proposes a new identity-based proxy re-encryption scheme on lattice. Firstly, the scheme uses trapdoors as private keys to achieve one-way anti-collusion. In addition, we construct a variant of Learning with Errors (LWE), which uses a convert algorithm to transform the user matrix and replace the vector with a uniform matrix, so that the scheme can meet the requirements of multi-hop and encrypt multiple bits of messages at one time. Theoretical analysis and experimental simulation prove that the security of the new scheme can be reduced to a decision LWE problem, which can reach the IND-sID-CPA security in the standard model and can improve the encryption efficiency while ensuring the security.

International Conference on Computer Information Science and Application Technology (CISAT)•Oct 11, 2023•1 citation

Lattice‐based multi‐use unidirectional proxy re‐encryption

Mingming Jiang, Yupu Hu, B. C. Wang +2 more

Abstract Proxy re‐encryption (PRE) is a cryptographic primitive that allows a proxy to turn an Alice's ciphertext into a Bob's ciphertext on the same plaintext. At present, there are many different PRE schemes that have been proposed with different properties. However, all of them are based on the logarithm assumption and the large integer factorization assumption except for a bidirectional PRE scheme over lattices. In this paper, we construct the first multi‐use unidirectional PRE scheme based on lattices. In addition, the generation of the PRE key does not interact with two users, and the scheme can resist collusion attacks. Moreover, it is proved chosen plaintext attack secure in the standard model based on the Learning With Errors assumption. Finally, an identity‐based PRE is obtained from the basic construction. Copyright © 2015 John Wiley & Sons, Ltd.

Security and Communication Networks•Jun 29, 2015•26 citations
The use of alternative foundations for constructing more secure and efficient cryptographic schemes is a topic worth exploring. In the case of proxy re-encryption, the vast majority of schemes are based on number theoretic problems such as the discrete logarithm. In this paper we present NTRUReEncrypt, a new bidirectional and multihop proxy re-encryption scheme based on NTRU, a widely known lattice-based cryptosystem. We provide two versions of our scheme: the first one is based on the conventional NTRU encryption scheme and, although it lacks a security proof, remains as efficient as its predecessor; the second one is based on a variant of NTRU proposed by Stehlé and Steinfeld, which is proven CPA-secure under the hardness of the Ring-LWE problem. To the best of our knowledge, our proposals are the first proxy re-encryption schemes to be based on the NTRU primitive. In addition, we provide experimental results to show the efficiency of our proposal, as well as a comparison with previous proxy re-encryption schemes, which confirms that our first scheme outperforms the rest by an order of magnitude.
Most of the previous proxy re-encryption schemes rely on the average-case hardness problems such as the integer factorization problems and the discrete logarithm problems. Therefore, they cannot guarantee its security under quantum analysis, since there exist quantum algorithms efficiently solving the factorization and logarithm problems. In the paper, we propose the first proxy re-encryption scheme based on the hard worst-case lattice problems. Our scheme has many useful properties as follows: Unidirectional, collusion-resistant, noninteractive, proxy invisible, key optimal, and nontransitive. We also provided the formal security proof of the proposed scheme in the random oracle model.
The proxy re-encryption allows an intermediate proxy to convert a ciphertext for Alice into a ciphertext for Bob without seeing the original message and leaking out relevant information.Unlike many prior identity based proxy re-encryption schemes which are based on the number theoretic assumptions such as large integer factorization and discrete logarithm problem.In this paper, we first propose a novel identity based proxy re-encryption scheme which is based on the hardness of standard Learning With Error(LWE) problem and is CPA secure in the standard model.This scheme can be reduced to the worst-case lattice hard problem that is able to resist attacks from quantum algorithm.The key step in our construction is that the challenger how to answer the private query under a known trapdoor matrix.Our scheme enjoys properties of the non-interactivity, unidirectionality, anonymous and so on.In this paper, we utilize primitives include G-trapdoor for lattice and sample algorithms to realize simple and efficient re-encryption.
In 1996 Hoffstein, Pipher ad Silverman presented NTRUEncrypt, which is to date the fastest known lattice-based encryption scheme. Its moderate key-sizes, excellent asymptotic performance and conjectured resistance to quantum attacks make it a perfect candidate to succeed where factorization and discrete log fail. Unfortunately, no security proof has been produced for NTRUEncrypt nor for its signature counterpart NTRUSign. In 2013 Stehle and Steinfield proposed to apply some mild modification to the encryption and signature scheme to make them provably secure, under the assumed quantum hardness of standard worst-case lattice problems, restricted to a family of lattices related to some cyclotomic fields. In particular they showed that if the secret key polynomials of the encryption scheme are chosen from discrete Gaussians, then the public key, i.e their ratio, is statistically indistinguishable from uniform. The security will then follow from the hardness of the R-LWE problem.The aim of this thesis is to present Stehle's and Steinfield's work in a slightly more accessi-ble form, providing some more background and details in some points.
This paper provides an explanation of NTRU, a post quantum encryption scheme, while also providing a gentle introduction to cryptography. NTRU is a very efficient lattice based cryptosystem that appears to be safe against attacks by quantum computers. NTRU's efficiency suggests that it is a strong candidate as an alternative to RSA, ElGamal, and ECC for the post quantum world. The paper begins with an introduction to cryptography and security proofs for cryptographic schemes before explaining the NTRU cryptosystem and culminating with a proof that the original presentation of NTRU is not IND-CPA secure. We will conclude by mentioning padding schemes to NTRU that are provably IND-CCA2 secure in the random oracle model. The paper is designed to be accessible to anyone with minimal background in abstract algebra and number theory - no previous knowledge of cryptography is assumed. Given the author's lack of familiarity with the subject, this paper aims to be an expository work rather than to provide new insights to the subject matter.
Proxy re-encryption plays an important role for data security in cloud computing and big data, but the traditional re-encryption scheme based on the classical number theory problem cannot resist quantum attack, and the lattice-based cryptosystem has been proved to have the ability to resist quantum attack, so the lattice-based re-encryption scheme has always been a research hotspot. In view of the problem that collusion-resistance and multi-hop cannot be satisfied at the same time in existing schemes, this paper proposes a new identity-based proxy re-encryption scheme on lattice. Firstly, the scheme uses trapdoors as private keys to achieve one-way anti-collusion. In addition, we construct a variant of Learning with Errors (LWE), which uses a convert algorithm to transform the user matrix and replace the vector with a uniform matrix, so that the scheme can meet the requirements of multi-hop and encrypt multiple bits of messages at one time. Theoretical analysis and experimental simulation prove that the security of the new scheme can be reduced to a decision LWE problem, which can reach the IND-sID-CPA security in the standard model and can improve the encryption efficiency while ensuring the security.
Abstract Proxy re‐encryption (PRE) is a cryptographic primitive that allows a proxy to turn an Alice's ciphertext into a Bob's ciphertext on the same plaintext. At present, there are many different PRE schemes that have been proposed with different properties. However, all of them are based on the logarithm assumption and the large integer factorization assumption except for a bidirectional PRE scheme over lattices. In this paper, we construct the first multi‐use unidirectional PRE scheme based on lattices. In addition, the generation of the PRE key does not interact with two users, and the scheme can resist collusion attacks. Moreover, it is proved chosen plaintext attack secure in the standard model based on the Learning With Errors assumption. Finally, an identity‐based PRE is obtained from the basic construction. Copyright © 2015 John Wiley & Sons, Ltd.