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.
Chapter PDF
Similar content being viewed by others
Keywords
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
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. 69
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. 64
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, 69
C. Gentry, ‘Key recovery and message attack on NTRU-composite’, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 2045 (2001), 182–194. 65
M. Goldman, M. Näslund and A. Russell, ‘Complexity bounds on general hardcore predicates’, J. Cryptology, 14 (2001), 177–195. 64
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. 69
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. 64
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, 69
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. 64
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, 69
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, 64
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, 64
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). 64
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. 64
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. 64
C. P. Schnorr, ‘Security of almost all discrete log bits’, Electronic Colloq. on Comp. Compl., Univ. of Trier, TR98-033 (1998), 1–13. 64
J.H. Silverman, ‘Invertibility in truncated polynomial rings’, NTRU Cryptosystem Tech. Report 9, 1998, 1–8. 63
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Näslund, M., Shparlinski, I.E., Whyte, W. (2003). On the Bit Security of NTRUEncrypt. In: Desmedt, Y.G. (eds) Public Key Cryptography — PKC 2003. PKC 2003. Lecture Notes in Computer Science, vol 2567. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36288-6_5
Download citation
DOI: https://doi.org/10.1007/3-540-36288-6_5
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00324-3
Online ISBN: 978-3-540-36288-3
eBook Packages: Springer Book Archive