An algebraic approach to NTRU (q = 2^n) via Witt vectors and overdetermined systems of nonlinear equations.

Nigel Smart, Fre Vercauteren, Joe Silverman

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

Abstract

We use the theory of Witt vectors to develop an algebraic approach for studying the NTRU primitive with $q$~parameter equal to a power of two. This results in a system of nonlinear algebraic equations over~$\FF_2$ having many symmetries, which is reminiscent of the approach of Courtois, Murphy, Pieprzyk, Robshaw and others for studying the structure of block ciphers such as the~AES. We study whether this approach to NTRU provides any immediate security threat and conclude that under the most favourable assumptions, the method is of asymptotic interest but is completely impractical at current or likely future parameter sizes.
Translated title of the contributionAn algebraic approach to NTRU (q = 2^n) via Witt vectors and overdetermined systems of nonlinear equations.
Original languageEnglish
Title of host publicationSecurity and Cryptography for Networks - SCN 2006
PublisherSpringer Berlin Heidelberg
Pages278 - 298
Number of pages20
Volume3352
ISBN (Print)3540243011
Publication statusPublished - Jan 2005

Bibliographical note

Conference Proceedings/Title of Journal: Security in Communication Networks (SCN 2004)

Fingerprint Dive into the research topics of 'An algebraic approach to NTRU (q = 2^n) via Witt vectors and overdetermined systems of nonlinear equations.'. Together they form a unique fingerprint.

  • Cite this

    Smart, N., Vercauteren, F., & Silverman, J. (2005). An algebraic approach to NTRU (q = 2^n) via Witt vectors and overdetermined systems of nonlinear equations. In Security and Cryptography for Networks - SCN 2006 (Vol. 3352, pp. 278 - 298). Springer Berlin Heidelberg. http://www.cs.bris.ac.uk/Publications/pub_info.jsp?id=2000193