Public-Key Cryptographic Primitives Provably as Secure as Subset Sum

DOI10.1007/978-3-642-11799-2_23zbMath1274.94096OpenAlexW2158911464MaRDI QIDQ3408206

Adriana Palacio, Vadim Lyubashevsky, Gil Segev

Publication date: 24 February 2010

Published in: Theory of Cryptography (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-11799-2_23

Mathematics Subject Classification ID

Cryptography (94A60)

Related Items

An Improved BKW Algorithm for LWE with Applications to Cryptography and Lattices ⋮ Fully leakage-resilient signatures ⋮ The Modular Subset-Sum Problem and the size of deletion correcting codes ⋮ Naor-Yung paradigm with shared randomness and applications ⋮ A black-box construction of fully-simulatable, round-optimal oblivious transfer from strongly uniform key agreement ⋮ Breaking the \(O(\sqrt{n})\)-bit barrier: Byzantine agreement with polylog bits per party ⋮ Algebraic algorithms for variants of subset sum ⋮ Zero-knowledge protocols for the subset sum problem from MPC-in-the-head with rejection ⋮ Efficient reductions and algorithms for subset product ⋮ Improved broadcast attacks against subset sum problems via lattice oracle ⋮ Improved classical and quantum algorithms for subset-sum ⋮ Subset Sum Quantumly in 1.17 n . ⋮ Fully leakage-resilient signatures revisited: graceful degradation, noisy leakage, and construction in the bounded-retrieval model ⋮ Better Key Sizes (and Attacks) for LWE-Based Encryption ⋮ Low weight discrete logarithm and subset sum in \(2^{0.65n}\) with polynomial memory ⋮ The Geometry of Lattice Cryptography ⋮ Naor-Yung Paradigm with Shared Randomness and Applications ⋮ Public-Key Cryptographic Primitives Provably as Secure as Subset Sum ⋮ Tightly secure signature schemes from the LWE and subset sum assumptions

Cites Work

• Unnamed Item
• Unnamed Item
• More on average case vs approximation complexity
• Efficient cryptographic schemes provably as secure as subset sum
• On Bounded Distance Decoding, Unique Shortest Vectors, and the Minimum Distance Problem
• Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems
• Public-Key Cryptographic Primitives Provably as Secure as Subset Sum
• Lossy trapdoor functions and their applications
• Trapdoors for hard lattices and new cryptographic constructions
• New lattice based cryptographic constructions
• A Framework for Efficient and Composable Oblivious Transfer
• Simultaneous Hardcore Bits and Cryptography against Memory Attacks
• Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data
• On the Lagarias-Odlyzko Algorithm for the Subset Sum Problem
• Solving low-density subset sum problems
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Foundations of Cryptography
• Public-key cryptosystems from the worst-case shortest vector problem
• Probability Inequalities for Sums of Bounded Random Variables
• An Improved Multi-set Algorithm for the Dense Subset Sum Problem
• Semi-honest to Malicious Oblivious Transfer—The Black-Box Way
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• STACS 2005
• Public-Key Cryptosystems Resilient to Key Leakage
• On lattices, learning with errors, random linear codes, and cryptography

This page was built for publication: Public-Key Cryptographic Primitives Provably as Secure as Subset Sum