Efficient cryptographic schemes provably as secure as subset sum

zbMath0862.94015MaRDI QIDQ2563542

Russell Impagliazzo, Moni Naor

Publication date: 26 January 1997

Published in: Journal of Cryptology (Search for Journal in Brave)

zbMATH Keywords

signature schemespseudorandom generatorencryptionhash functionsubset-sum problem

Mathematics Subject Classification ID

Shift register sequences and sequences over finite alphabets in information and communication theory (94A55) Cryptography (94A60) Random number generation in numerical analysis (65C10)

Related Items (42)

Scheduling lower bounds via AND subset sum ⋮ Tightly secure signatures from lossy identification schemes ⋮ More efficient DDH pseudorandom generators ⋮ Naor-Yung paradigm with shared randomness and applications ⋮ Obfuscated fuzzy Hamming distance and conjunctions from subset product problems ⋮ A pseudorandom number generator based on worst-case lattice problems ⋮ Asymptotically efficient lattice-based digital signatures ⋮ Breaking the \(O(\sqrt{n})\)-bit barrier: Byzantine agreement with polylog bits per party ⋮ Fixed points of the subset sum pseudorandom number generators ⋮ Zero-knowledge protocols for the subset sum problem from MPC-in-the-head with rejection ⋮ Improved broadcast attacks against subset sum problems via lattice oracle ⋮ Cryptographic group actions and applications ⋮ Unnamed Item ⋮ Computational indistinguishability between quantum states and its cryptographic application ⋮ On treewidth, separators and Yao's garbling ⋮ On the uniformity of distribution of the RSA pairs ⋮ Revisiting the Security Proof of QUAD Stream Cipher: Some Corrections and Tighter Bounds ⋮ On the tightness of forward-secure signature reductions ⋮ An Improved Multi-set Algorithm for the Dense Subset Sum Problem ⋮ A low-memory algorithm for finding short product representations in finite groups. ⋮ Cryptanalysis of the Knapsack Generator ⋮ Pseudo-free families of finite computational elementary abelian \(p\)-groups ⋮ Tighter Reductions for Forward-Secure Signature Schemes ⋮ Unnamed Item ⋮ Natural proofs ⋮ QUAD: A Practical Stream Cipher with Provable Security ⋮ Improved attacks on knapsack problem with their variants and a knapsack type ID-scheme ⋮ Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems ⋮ Random knapsack in expected polynomial time ⋮ QUAD: A multivariate stream cipher with provable security ⋮ Fine-grained cryptography revisited ⋮ Sampling Lower Bounds: Boolean Average-Case and Permutations ⋮ Low weight discrete logarithm and subset sum in \(2^{0.65n}\) with polynomial memory ⋮ Unnamed Item ⋮ Naor-Yung Paradigm with Shared Randomness and Applications ⋮ Cryptography with constant input locality ⋮ Public-Key Cryptographic Primitives Provably as Secure as Subset Sum ⋮ Synthesizers and their application to the parallel construction of pseudo-random functions ⋮ Tightly secure signature schemes from the LWE and subset sum assumptions ⋮ Multiparty generation of an RSA modulus ⋮ The discrete logarithm modulo a composite hides \(O(n)\) bits ⋮ On the distribution of the Diffie-Hellman pairs

This page was built for publication: Efficient cryptographic schemes provably as secure as subset sum