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

Jinhyuck Jeong, Jung Hee Cheon, 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)

• Provably secure NTRUEncrypt over any cyclotomic field
• From Minicrypt to Obfustopia via Private-Key Functional Encryption
• A framework for cryptographic problems from linear algebra
• Public key encryption with equality test from generic assumptions in the random oracle model
• 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
• Multikey Fully Homomorphic Encryption and Applications
• Generalized Hardness Assumption for Self-bilinear Map with Auxiliary Information
• A trace map attack against special ring-LWE samples
• \textsc{Antrag}: annular NTRU trapdoor generation. Making \textsc{Mitaka} as secure as FALCON
• A Lattice Attack on Homomorphic NTRU with Non-invertible Public Keys
• Functional Encryption: Deterministic to Randomized Functions from Simple Assumptions
• 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
• Optimal broadcast encryption from pairings and LWE
• On the ideal shortest vector problem over random rational primes
• Algebraic Aspects of Solving Ring-LWE, Including Ring-Based Improvements in the Blum--Kalai--Wasserman Algorithm
• Combiners for functional encryption, unconditionally
• 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
• Digital Signatures Based on the Hardness of Ideal Lattice Problems in All Rings
• Provably Secure NTRU Instances over Prime Cyclotomic Rings
• Revisiting Lattice Attacks on Overstretched NTRU Parameters
• On the hardness of the NTRU problem
• FINAL: faster FHE instantiated with NTRU and LWE
• A Practical Post-Quantum Public-Key Cryptosystem Based on $$\textsf {spLWE}$$
• The Whole is Less Than the Sum of Its Parts: Constructing More Efficient Lattice-Based AKEs
• Cryptanalyses of Candidate Branching Program Obfuscators
• One-Shot Verifiable Encryption from Lattices
• 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)