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

DOI10.3934/AMC.2018026zbMATH Open1401.94150OpenAlexW2887430501MaRDI QIDQ1784985FDOQ1784985

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

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

zbMATH Keywords

latticecryptographysubset sum problemBKZ reductioncompact knapsack problemid-scheme

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (1)

• Adapting Density Attacks to Low-Weight Knapsacks

Uses Software

• SageMath
• fpLLL
• fpylll
• GitHub

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)