Improved attacks on knapsack problem with their variants and a knapsack type ID-scheme

DOI10.3934/AMC.2018026MaRDI QIDQ1784985zbMATH OpenOpenAlexFDO

Authors Konstantinos A. Draziotis, Anastasia Papadopoulou

Publication date 27 September 2018

Published in Advances in Mathematics of Communications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3934/amc.2018026

zbMATH Keywords

latticecryptographysubset sum problemBKZ reductioncompact knapsack problemid-scheme

Mathematics Subject Classification ID

Cryptography (94A60) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71)

Recommendations

• Solutions of hard knapsack problems using extreme pruning
• New generic algorithms for hard knapsacks
• A knapsack-based probabilistic encryption scheme
• Quadratic compact knapsack public-key cryptosystem
• scientific article; zbMATH DE number 691485

Cites work

• scientific article; zbMATH DE number 4074814 (Why is no real title available?)
• scientific article; zbMATH DE number 1187155 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1775383 (Why is no real title available?)
• scientific article; zbMATH DE number 2120513 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
• A knapsack-based probabilistic encryption scheme
• Analyzing blockwise lattice algorithms using dynamical systems
• Balanced integer solutions of linear equations
• Cryptanalysis of a knapsack-based probabilistic encryption scheme
• Efficient cryptographic schemes provably as secure as subset sum
• Efficient signature generation by smart cards
• Factoring polynomials with rational coefficients
• Improved Generic Algorithms for Hard Knapsacks
• Improved cryptanalysis of a knapsack-based probabilistic encryption scheme
• Improved low-density subset sum algorithms
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• Lattice enumeration using extreme pruning
• Lattice-Based Identification Schemes Secure Under Active Attacks
• Lattice-based Cryptography
• Mathematics of public key cryptography.
• New generic algorithms for hard knapsacks
• On the Lagarias-Odlyzko Algorithm for the Subset Sum Problem
• Predicting Lattice Reduction
• Quantum communication attacks on classical cryptographic protocols. (Invited talk)
• Solving Linear Equations Modulo Divisors: On Factoring Given Any Bits
• Solving low-density subset sum problems
• The LLL algorithm and integer programming

Cited in

(1)

• Adapting Density Attacks to Low-Weight Knapsacks

Describes a project that uses

Uses Software

• GitHub
• fpylll
• fpLLL
• SageMath

This page was built for publication: Improved attacks on knapsack problem with their variants and a knapsack type ID-scheme

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