Efficient identity-based signature over NTRU lattice

Jia XIE; Yu-pu HU; Jun-tao GAO; Wen GAO

doi:10.1631/FITEE.1500197

Your Location：

Home >

Browse articles >

Efficient identity-based signature over NTRU lattice

Regular Papers | Updated：2022-05-19

- Efficient identity-based signature over NTRU lattice
- NTRU格上基于身份签名的高效方案
- Frontiers of Information Technology & Electronic Engineering Vol. 17, Issue 2, Pages: 135-142(2016)
- Affiliations：
  
  1School of Telecommunications Engineering, Xidian University, Xi'an 710071, China
  2The State Key Laboratory of Integrated Services Network, Xi'an 710071, China
- Author bio：
  
  E-mail:xiejia199325@163.com
- Funds：
- DOI：10.1631/FITEE.1500197
  CLC： TP309.7
- Received：21 June 2015，
  
  Accepted：12 October 2015，
  
  Published：2016-02
- Accepted：
Scan QR Code
Jia XIE, Yu-pu HU, Jun-tao GAO, et al. Efficient identity-based signature over NTRU lattice[J]. Frontiers of Information Technology & Electronic Engineering, 2016, 17(2): 135-142.
DOI：

Jia XIE, Yu-pu HU, Jun-tao GAO, et al. Efficient identity-based signature over NTRU lattice[J]. Frontiers of Information Technology & Electronic Engineering, 2016, 17(2): 135-142. DOI： 10.1631/FITEE.1500197.

摘要

目的

众所周知，普通格上的基于身份的签名体制的公钥尺寸较大并且签名效率不甚令人满意，为提高格上的签名效率并且降低其公钥尺寸，本文设计了NTRU格上的基于身份的签名方案。

创新点

将抛弃采样技术扩展到NTRU格上，并利用NTRU格上的SIS问题构造了NTRU格上的首个可证安全的基于身份的签名方案，使得签名效率显著提高，并很大程度地降低了公钥尺寸。

方法

首先，明确NTRU格的定义，提出NTRU格上的小整数解问题（SIS），即定义5，指出该困难问题在量子计算环境下是安全的。然后，将抛弃采样技术扩展到NTRU格上(算法6)，利用扩展后的抛弃采样技术构造NTRU格上的基于身份的签名方案，详见算法4-7。该方案的安全性依赖于所提出的NTRU格上的SIS问题，因而该方案在量子计算环境下仍然是安全的，并且其通信复杂度较低（详见表1-2）。

结论

将抛弃采样技术扩展到NTRU格上，并构造了NTRU格上首个基于身份的签名方案，该签名方案与普通格上的基于身份的签名方案相比，效率更高，公钥尺寸更小。

Abstract

Identity-based signature has become an important technique for lightweight authentication as soon as it was proposed in 1984. Thereafter

identity-based signature schemes based on the integer factorization problem and discrete logarithm problem were proposed one after another. Nevertheless

the rapid development of quantum computers makes them insecure. Recently

many efforts have been made to construct identity-based signatures over lattice assumptions against attacks in the quantum era. However

their efficiency is not very satisfactory. In this study

an efficient identity-based signature scheme is presented over the number theory research unit (NTRU) lattice assumption. The new scheme is more efficient than other lattice- and identity-based signature schemes. The new scheme proves to be unforgeable against the adaptively chosen message attack in the random oracle model under the hardness of the -shortest vector problem on the NTRU lattice.

关键词

Keywords

references

L Babai . . On Lovsz' lattice reduction and the nearest lattice point problem . . Combinatorica , , 1986 . . 6 ( ( 1 ): ): 1 - - 13 . . DOI: 10.1007/BF02579403 http://doi.org/10.1007/BF02579403 . .

P.S.L.M Barreto , , , B Libert , , , N McCullagh , , , 等 . . Efficient and provably-secure identity-based signatures and signcryption from bilinear maps . . 2005 . . 11th Int. Conf. on the Theory and Application of Cryptology and Information Security . . 515 - - 532 . . DOI: 10.1007/11593447_28 http://doi.org/10.1007/11593447_28 . .

D.J Bernstein . . Introduction to post-quantum cryptography. In: Bernstein, D.J., Buchmann, J., Dahmen, E. (Eds.), Post-Quantum Cryptography , , 2009 . . : : Berlin Springer-Verlag , , 1 - - 14 . . DOI: 10.1007/978-3-540-88702-7_1 http://doi.org/10.1007/978-3-540-88702-7_1 . .

D Boneh , , , M Franklin . . Identity based encryption from the Weil pairing . . 2001 . . 21st Annual Int. Cryptology Conf. . . 213 - - 229 . . DOI: 10.1007/3-540-44647-8_13 http://doi.org/10.1007/3-540-44647-8_13 . .

Y Desmedt , , , J.J Quisquater . . Public-key systems based on the difficulty of tampering (Is there a difference between DES and RSA?) . . LNCS , , 1987 . . 263 111 - - 117 . . DOI: 10.1007/3-540-47721-7_9 http://doi.org/10.1007/3-540-47721-7_9 . .

L Ducas , , , V Lyubashevsky , , , T Prest . . Efficient identity-based encryption over NTRU lattice . . 2014 . . 20th Int. Conf. on the Theory and Application of Cryptology and Information Security . . 22 - - 41 . . DOI: 10.1007/978-3-662-45608-8_2 http://doi.org/10.1007/978-3-662-45608-8_2 . .

C Gentry , , , C Peikert , , , V Vaikuntanathan . . Trapdoors for hard lattices and new cryptographic constructions . . 2008 . . 40th Annual ACM Symp. on Theory of Computing . . 197 - - 206 . . DOI: 10.1145/1374376.1374407 http://doi.org/10.1145/1374376.1374407 . .

F Hess . . Efficient identity based signature schemes based on pairings . . 2003 . . 9th Annual Int. Workshop on Selected Areas in Cryptography . . 310 - - 324 . . DOI: 10.1007/3-540-36492-7_20 http://doi.org/10.1007/3-540-36492-7_20 . .

M Krenn , , , M Huber , , , R Fickler , , , 等 . . Generation and confirmation of a (100100)-dimensional entangled quantum system . . PNAS , , 2014 . . 111 ( ( 17 ): ): 6243 - - 6247 . . DOI: 10.1073/pnas.1402365111 http://doi.org/10.1073/pnas.1402365111 . .

F.G Li , , , F.T.B Muhaya , , , M.K Khan , , , 等 . . Latticebased signcryption . . Concurr. Comput. Pract. Exp. , , 2012 . . 25 ( ( 14 ): ): 2112 - - 2122 . . DOI: 10.1002/cpe.2826 http://doi.org/10.1002/cpe.2826 . .

Z.H Liu , , , Y.P Hu , , , X.S Zhang , , , 等 . . Efficient and strongly unforgeable identity-based signature scheme from lattices in the standard model . . Secur. Commun. Network. , , 2013 . . 6 ( ( 1 ): ): 69 - - 77 . . DOI: 10.1002/sec.531 http://doi.org/10.1002/sec.531 . .

V Lyubashevsky . . Lattice signatures without trapdoors . . 2012 . . 31st Annual Int. Conf. on the Theory and Applications of Cryptographic Techniques . . 738 - - 755 . . DOI: 10.1007/978-3-642-29011-4_43 http://doi.org/10.1007/978-3-642-29011-4_43 . .

U.M Maurer , , , Y Yacobi . . Non-interactive public-key cryptography . . 1991 . . Workshop on the Theory and Application of Cryptographic Techniques . . 498 - - 507 . . DOI: 10.1007/3-540-46416-6_43 http://doi.org/10.1007/3-540-46416-6_43 . .

D Micciancio , , , O Regev . . Lattice-based cryptography. In: Bernstein, D.J., Buchmann, J., Dahmen, E. (Eds.), Post-Quantum Cryptography , , 2009 . . : : Berlin Springer-Verlag , , 147 - - 191 . . DOI: 10.1007/978-3-540-88702-7_5 http://doi.org/10.1007/978-3-540-88702-7_5 . .

P.Q Nguyen , , , O Regev . . Learning a parallelepiped: cryptanalysis of GGH and NTRU signatures . . 2006 . . 24th Annual Int. Conf. on the Theory and Applications of Cryptographic Techniques . . 271 - - 288 . . DOI: 10.1007/11761679_17 http://doi.org/10.1007/11761679_17 . .

K.G Paterson , , , J.C.N Schuldt . . Efficient identity-based signatures secure in the standard model . . 2006 . . 11th Australasian Conf. on Information Security and Privacy . . 207 - - 222 . . DOI: 10.1007/11780656_18 http://doi.org/10.1007/11780656_18 . .

M Rckert . . Strongly unforgeable signatures and hierarchical identity-based signatures from lattices without random oracles . . 2010 . . Proc. 3rd Int. Workshop on PQCrypto . . 182 - - 200 . . DOI: 10.1007/978-3-642-12929-2_14 http://doi.org/10.1007/978-3-642-12929-2_14 . .

A Shamir . . Identity-based cryptosystems and signature schemes . . 1984 . . Proc. CRYPTO . . 47 - - 53 . . DOI: 10.1007/3-540-39568-7_5 http://doi.org/10.1007/3-540-39568-7_5 . .

P.W Shor . . Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer . . SIAM J. Comput. , , 1997 . . 26 ( ( 5 ): ): 1484 - - 1509 . . DOI: 10.1137/S0097539795293172 http://doi.org/10.1137/S0097539795293172 . .

D Stehl , , , R Steinfeld . . Making NTRUEncrypt and NTRUSign as secure as standard worst-case problems over ideal lattices Cryptology ePrint Archive 2013/004 , , 2013 . . Available from: http://eprint.iacr.org/2013/004 http://eprint.iacr.org/2013/004 . .

H Tanaka . . A realization scheme for the identity-based cryptosystem . . 1987 . . CRYPTO . . 341 - - 349 . . DOI: 10.1007/3-540-48184-2_29 http://doi.org/10.1007/3-540-48184-2_29 . .

M.M Tian , , , L.S Huang . . Efficient identity-based signature from lattices . . 2014 . . Proc. 29th IFIP TC 11 Int. Conf. . . 321 - - 329 . . DOI: 10.1007/978-3-642-55415-5_26 http://doi.org/10.1007/978-3-642-55415-5_26 . .

M.M Tian , , , L.S Huang , , , W Yang . . Efficient hierachical identity-based signatures from lattices . . Int. J. Electron. Secur. Dig. Forens. , , 2013 . . 5 ( ( 1 ): ): 1 - - 10 . . DOI: 10.1504/IJESDF.2013.054403 http://doi.org/10.1504/IJESDF.2013.054403 . .

S Tsuji , , , T Itoh . . An ID-based cryptosystem based on the discrete logarithm problem . . IEEE J. Sel. Areas Commun. , , 1989 . . 7 ( ( 4 ): ): 467 - - 473 . . DOI: 10.1109/49.17709 http://doi.org/10.1109/49.17709 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰