UDC 519.7
1 National Technical University of Ukraine
“Igor Sikorsky Kyiv Polytechnic Institute,” Kyiv, Ukraine
 alex-dtn@ukr.net
|
2 National Technical University of Ukraine
“Igor Sikorsky Kyiv Polytechnic Institute,” Kyiv, Ukraine
alexm1710@ukr.net
|
ACHIEVABLE UPPER BOUND FOR THE SUP-NORM OF THE ELEMENTS’ PRODUCT IN
THE RING OF TRUNCATED POLYNOMIALS AND ITS APPLICATION TO THE ANALYSIS
OF NTRU-LIKE CRYPTOSYSTEMS
Abstract. The answer to the question posed in 2008 by V. Lyubashevsky
about an efficient algorithm for calculating the parameter
θ ( f ) that characterizes
the value of the sup-norm of the elements’ product in the ring of truncated polynomials
modulo a given mimic polynomial
f ( x ) with real coefficients is obtained.
The application of the obtained results to the estimation of decryption failure probability of messages in NTRU-like cryptosystems is considered.
Keywords: lattice-based cryptography, truncated polynomial ring, sup-norm of polynomials’ product, NTRU-like cryptosystem, decryption failure probability.
FULL TEXT
REFERENCES
- Albrecht M.R., Curtis B.R., Deo A., Davidson A., Player R., Postlethwaite E.W., Virdia F., Wunderer T. Estimate all the {LWE, NTRU} schemes! Cryptology ePrint Archive, Report 2018/331. URL: http://eprint.iacr.org/2018/331.
- Lyubashevsky V. Towards practical lattice-based cryptography, Ph.D, 2008. URL: https://escholarship/org/uc/item/0141w93p.
- Cartan A. Differential calculus. Differential forms [Russian translation]. Moscow: Mir, 1971. 392 p.
- Hoeffding W. Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 1963. Vol. 58, N 301. P. 13–30.
- Hirschhorn P., Hoffstein J., Howgrave-Graham N., Whyte W. Choosing NTRU parameters in light of combined lattice reduction and MITM approaches. Applied Cryptography and Network Security, LNCS. 2009. Vol. 5536. P. 437–455.
- Hoffstein J., Pipher J., Schanck J.M., Silverman J.H., Whyte W., Zhang Z. Choosing parameters for NTRUEncrypt. Cryptology ePrint Archive. Report 2015/708. URL: http://eprint.iacr.org/2015/708.
- Chen C., Hoffstein J., Whyte W., Zhang Z. NIST PQ Submission: NTRUEncrypt. A lattice based algorithm. URL: https://cscr.nist.gov/Projects/Post-Quantum-Cryptography, 2017.
- Lyubashevsky V., Seiler G. NTTRU: Truly fast NTRU using NTT. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2019. Vol. 3. P. 180–201.
- Matiyko О.А., Alekseychuk A.N. Bounds of decryption failure probability in NTRUEncrypt encryption scheme for a fixed key. Ukrainian Information Security Research Journal. 2018. Vol. 20, N 2. P. 89–94.
