A polynomial-time algorithm for solving the hidden subset sum problem

DOI10.1007/978-3-030-56880-1_1MaRDI QIDQ2096513zbMATH OpenOpenAlexFDO

Authors Jean-Sébastien Coron, Agnese Gini

Publication date 9 November 2022

Full work available at URL https://doi.org/10.1007/978-3-030-56880-1_1

zbMATH Keywords

lattice based algorithmNguyen-Stern algorithm

Mathematics Subject Classification ID

Cryptography (94A60)

Recommendations

• scientific article; zbMATH DE number 4074814
• Improved low-density subset sum algorithms
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• Solving low-density subset sum problems
• STACS 2005

Cites work

• A hierarchy of polynomial time lattice basis reduction algorithms
• A polynomial-time algorithm for solving the hidden subset sum problem
• Advances in Cryptology - EUROCRYPT 2004
• An LLL algorithm with quadratic complexity
• Analyzing blockwise lattice algorithms using dynamical systems
• BKZ 2.0: Better lattice security estimates
• Cryptanalysis of CLT13 multilinear maps with independent slots
• Cryptanalysis of the co-ACD assumption
• Efficient algorithms for solving overdefined systems of multivariate polynomial equations
• Factoring polynomials with rational coefficients
• Fault attacks against EMV signatures
• Fully homomorphic encryption over the integers
• scientific article; zbMATH DE number 1302807 (Why is no real title available?)
• scientific article; zbMATH DE number 1302849 (Why is no real title available?)
• scientific article; zbMATH DE number 1303125 (Why is no real title available?)
• scientific article; zbMATH DE number 1088235 (Why is no real title available?)
• scientific article; zbMATH DE number 1418285 (Why is no real title available?)
• Improved low-density subset sum algorithms
• On Kilian's randomization of multilinear map encodings
• On Lovász' lattice reduction and the nearest lattice point problem
• Practical multilinear maps over the integers
• Solving low-density subset sum problems
• Using Algebraic Geometry

Cited in

(4)

• A polynomial-time algorithm for solving the hidden subset sum problem
• Deterministic algorithms for the hidden subgroup problem
• scientific article; zbMATH DE number 1418285 (Why is no real title available?)
• Channel allocation revisited through 1-extendability of graphs

Describes a project that uses

Uses Software

• fpLLL
• SageMath
• BKZ
• NTL

This page was built for publication: A polynomial-time algorithm for solving the hidden subset sum problem

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