Characterizing overstretched NTRU attacks

Abstract Overstretched NTRU is a variant of NTRU with a large modulus. Recent lattice subfield and subring attacks have broken suggested parameters for several schemes. There are a number of conflicting claims in the literature over which attack has the best performance. These claims are typically based on experiments more than analysis. In this paper, we argue that comparisons should focus on the lattice dimension used in the attack. We give evidence, both analytically and experimentally, that the subring attack finds shorter vectors and thus is expected to succeed with a smaller dimension lattice than the subfield attack for the same problem parameters, and also to succeed with a smaller modulus when the lattice dimension is fixed.

• Publication year

  2020

• Venue

  IACR Cryptology ePrint Archive

• Publication date

  2020-01-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1515/jmc-2015-0055
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Finite Fields

  2018influential reference
• Revisiting Lattice Attacks on Overstretched NTRU Parameters

  2017cited by this paper
• Choosing Parameters for the Subfield Lattice Attack Against Overstretched NTRU

  2017cited by this paper
• A Subfield Lattice Attack on Overstretched NTRU Assumptions - Cryptanalysis of Some FHE and Graded Encoding Schemes

  2016cited by this paper
• An algorithm for NTRU problems and cryptanalysis of the GGH multilinear map without a low-level encoding of zero

  2016cited by this paper
• NTRU Cryptosystem: Recent developments and emerging mathematical problems in finite polynomial rings

  2014cited by this paper
• Candidate Multilinear Maps from Ideal Lattices

  2013cited by this paper
• Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme

  2013cited by this paper
• On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption

  2012cited by this paper
• Making NTRU as Secure as Worst-Case Problems over Ideal Lattices

  2011cited by this paper
• Random Walk: A Modern Introduction

  2010cited by this paper
• On sublattice determinants in reduced bases

  2008cited by this paper
• Cryptanalysis of the Revised NTRU Signature Scheme

  2002cited by this paper
• Aeìêíëááae Áááìä Ëááaeaeìíêêë Íëáaeae Ìàà Aeìêí Ääììááá Èêêäáåáaeaeê Êêêì ¾ Èêáä ¾¸¾¼¼¾ Ââââêêê Àçççëììáae¸aeááã Àçïêêîî¹¹êêààå¸âáää Èáèààê¸âçëëèà Àº Ëáäîîêååae¸ïáääááå Ïààìì

  2002cited by this paper
• Distribution of inverses in polynomial rings

  2001cited by this paper
• Dimension Reduction Methods for Convolution Modular Lattices

  2001cited by this paper
• NTRU: A Ring-Based Public Key Cryptosystem

  1998cited by this paper
• Lattice Attacks on NTRU

  1997cited by this paper
• Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes

  1996cited by this paper
• A Hierarchy of Polynomial Time Lattice Basis Reduction Algorithms

  1987cited by this paper
• Uniform distribution of sequences

  1974cited by this paper
• Algebraic theory of numbers

  1971cited by this paper

• New design of NTRU key using QKD variants

  2024cites this paper
• On the quantum security of high-dimensional RSA protocol

  2024cites this paper
• An overview of number theory research unit variant development security

  2022cites this paper