An algorithm for NTRU problems and cryptanalysis of the GGH multilinear map without a low-level encoding of zero

DOI10.1112/S1461157016000371zbMATH Open1404.94053MaRDI QIDQ2971014FDOQ2971014

Authors: Jung Hee Cheon, Jinhyuck Jeong, C.-M. Lee 

Publication date: 4 April 2017

Published in: LMS Journal of Computation and Mathematics (Search for Journal in Brave)

Recommendations

• Cryptanalysis of NTRU where the private polynomial has one or more consecutive zero coefficients
• More efficient algorithms for the NTRU key generation using the field norm
• A Subfield Lattice Attack on Overstretched NTRU Assumptions
• NTRU algorithm: N\textsuperscript{th} degree truncated polynomial ring units
• Vulnerable public keys in NTRU cryptosystem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Cryptography (94A60) Number-theoretic algorithms; complexity (11Y16)

Cites Work

• Lattice signatures and bimodal Gaussians
• Practical multilinear maps over the integers
• Candidate Multilinear Maps from Ideal Lattices
• Cryptanalysis of GGH map
• New Multilinear Maps Over the Integers
• Cryptanalysis of GGH15 multilinear maps
• A Subfield Lattice Attack on Overstretched NTRU Assumptions
• Cryptanalysis of the new CLT multilinear map over the integers
• GGHLite: more efficient multilinear maps from ideal lattices
• Implementing candidate graded encoding schemes from ideal lattices

Cited In (41)

• A lattice attack on homomorphic NTRU with non-invertible public keys
• Generalized hardness assumption for self-bilinear map with auxiliary information
• Provably secure NTRUEncrypt over any cyclotomic field
• Algebraic aspects of solving ring-LWE, including ring-based improvements in the Blum-Kalai-Wasserman algorithm
• Provably secure NTRU instances over prime cyclotomic rings
• A framework for cryptographic problems from linear algebra
• Public key encryption with equality test from generic assumptions in the random oracle model
• One-shot verifiable encryption from lattices
• Ideal-SVP is hard for small-norm uniform prime ideals
• NTRU Fatigue: How Stretched is Overstretched?
• The MMap strikes back: obfuscation and new multilinear maps immune to CLT13 zeroizing attacks
• A trace map attack against special ring-LWE samples
• \textsc{Antrag}: annular NTRU trapdoor generation. Making \textsc{Mitaka} as secure as FALCON
• From Minicrypt to Obfustopia via private-key functional encryption
• Characterizing overstretched NTRU attacks
• Collusion resistant traitor tracing from learning with errors
• From minicrypt to obfustopia via private-key functional encryption
• Constrained pseudorandom functions for Turing machines revisited: how to achieve verifiability and key delegation
• Can PPAD hardness be based on standard cryptographic assumptions?
• Annihilation Attacks for Multilinear Maps: Cryptanalysis of Indistinguishability Obfuscation over GGH13
• A Subfield Lattice Attack on Overstretched NTRU Assumptions
• Attribute based encryption for deterministic finite automata from DLIN
• Functional encryption: deterministic to randomized functions from simple assumptions
• Optimal broadcast encryption from pairings and LWE
• On the ideal shortest vector problem over random rational primes
• Combiners for functional encryption, unconditionally
• A practical post-quantum public-key cryptosystem based on spLWE
• From FE combiners to secure MPC and back
• A thorough treatment of highly-efficient NTRU instantiations
• Message recovery attack on NTRU using a lattice independent from the public key
• The whole is less than the sum of its parts: constructing more efficient lattice-based AKEs
• Multikey fully homomorphic encryption and applications
• Digital Signatures Based on the Hardness of Ideal Lattice Problems in All Rings
• Revisiting Lattice Attacks on Overstretched NTRU Parameters
• On the hardness of the NTRU problem
• FINAL: faster FHE instantiated with NTRU and LWE
• Cryptanalyses of Candidate Branching Program Obfuscators
• Fast reduction of algebraic lattices over cyclotomic fields
• A polynomial time algorithm for breaking NTRU encryption with multiple keys
• Multi-key fully homomorphic encryption from NTRU and (R)LWE with faster bootstrapping
• Quantum lightning never strikes the same state twice. Or: quantum money from cryptographic assumptions

Uses Software

• NTRU
• NTRUSign

This page was built for publication: An algorithm for NTRU problems and cryptanalysis of the GGH multilinear map without a low-level encoding of zero

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2971014)