Advertisement

On the Bit Security of NTRUEncrypt

  • Mats Näslund
  • Igor E. Shparlinski
  • William Whyte
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2567)

Abstract

We show that in certain natural computational models every bit of a message encrypted with the NtruEncrypt cryptosystem is as secure as the whole message.

Keywords

Secret Message Cyclic Shift Undesirable Property Encrypt Message Valid Message 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

References

  1. 1.
    W. Alexi, B. Chor, O. Goldreich and C.P. Schnorr, ‘RSA and Rabin functions: Certain parts are as hard as the whole’, SIAM Journal on Computing, 17 (1988), 194–209. 69Google Scholar
  2. 2.
    D. Boneh and I. E. Shparlinski, ‘On the unpredictability of bits of the elliptic curve Diffie–Hellman scheme’, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 2139 (2001), 201–212. 64MathSciNetGoogle Scholar
  3. 3.
    D. Boneh and R. Venkatesan, ‘Hardness of computing the most significant bits of secret keys in Diffie–Hellman and related schemes’, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 1109 (1996), 129–142. 64, 69Google Scholar
  4. 5.
    C. Gentry, ‘Key recovery and message attack on NTRU-composite’, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 2045 (2001), 182–194. 65MathSciNetGoogle Scholar
  5. 6.
    M. Goldman, M. Näslund and A. Russell, ‘Complexity bounds on general hardcore predicates’, J. Cryptology, 14 (2001), 177–195. 64MathSciNetGoogle Scholar
  6. 7.
    S. Goldwasser, S. Micali and P. Tong, ‘Why and how to establish a private code on a public network (Extended abstract)’, Proc. 23rd Annual IEEE Symp. on Foundations of Comp. Sci., 1982, 134–144. 69Google Scholar
  7. 8.
    M. I. González Vasco and M. Näslund, ‘A survey of hard core functions’, Proc. Workshop on Cryptography and Computational Number Theory, Singapore 1999, Birkhäuser, 2001, 227–256. 64Google Scholar
  8. 9.
    M. I. González Vasco and I.E. Shparlinski, ‘On the security of Diffie–Hellman bits’, Proc. Workshop on Cryptography and Computational Number Theory, Singapore 1999, Birkhäuser, 2001, 257–268. 64, 69Google Scholar
  9. 10.
    M. I. González Vasco and I.E. Shparlinski, ‘Security of the most significant bits of the Shamir message passing scheme’, Math. Comp., 71 (2002), 333–342. 64zbMATHCrossRefMathSciNetGoogle Scholar
  10. 11.
    J. H∢stad and M. Näslund, ‘The security of individual RSA and discrete log bits’, J. of the ACM, (to appear). 62, 63, 64, 69Google Scholar
  11. 12.
    J. Hoffstein, J. Pipher and J.H. Silverman, ‘NTRU: A ring based public key cryptosystem’, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 1433 (1998), 267–288. 62, 63, 64MathSciNetGoogle Scholar
  12. 13.
    J. Hoffstein and J.H. Silverman, ‘Optimizations for NTRU’, Proc. the Conf. on Public Key Cryptography and Computational Number Theory, Warsaw, 2000, Walter de Gruyter, 2001, 77–88. 63, 64Google Scholar
  13. 14.
    N. A. Howgrave-Graham, P. Q. Nguyen and I.E. Shparlinski, ‘Hidden number problem with hidden multipliers, timed-release crypto and noisy exponentiation’, Math. Comp., (to appear). 64Google Scholar
  14. 15.
    W.-C.W. Li, M. Näslund and I.E. Shparlinski, ‘The hidden number problem with the trace and bit security of XTR and LUC’, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 2442 (2002), 433–448. 64Google Scholar
  15. 16.
    P.Q. Nguyen and D. Pointcheval, ‘Analysis and improvements of NTRU encryption paddings’, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 2442 (2002, 210–225. 64MathSciNetGoogle Scholar
  16. 17.
    C. P. Schnorr, ‘Security of almost all discrete log bits’, Electronic Colloq. on Comp. Compl., Univ. of Trier, TR98-033 (1998), 1–13. 64Google Scholar
  17. 18.
    J.H. Silverman, ‘Invertibility in truncated polynomial rings’, NTRU Cryptosystem Tech. Report 9, 1998, 1–8. 63Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Mats Näslund
    • 1
  • Igor E. Shparlinski
    • 2
  • William Whyte
    • 3
  1. 1.Ericsson ResearchStockholmSweden
  2. 2.Department of ComputingMacquarie UniversitySydneyNSWAustralia
  3. 3.NTRU Cryptosystems Inc.BurlingtonUSA

Personalised recommendations