Efficient cryptographic schemes provably as secure as subset sum

By Russell Impagliazzo, Moni Naor. 1989

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Prio: Private, Robust, and Scalable Computation of Aggregate Statistics (2017, methodology): “We optimistically estimate that each hash computation requires only 300 multiplication gates, using a subset-sum hash function [2, 17, 67, 77], and we ignore the cost of computing the Valid circuit in the SNARK.”
Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions (2002, background): “) there is theoretical evidence [17] that subset-sum can indeed be a good candidate starting problem, at least from an asymptotic point of view.”
Public-Key Cryptosystems Resilient to Key Leakage (2009, methodology): “Our approach was also used by Lyubashevsky, Palacio and Segev [62] who constructed a leakageresilient public-key encryption scheme based on the hardness of the subset-sum problem [49], and by Brakerski and Goldwasser [17] who constructed a leakage-resilient public-key encryption scheme based on the ”
Lattice Signatures Without Trapdoors (2012, methodology): “[22, 29] If d is polynomial in n, then there is a polynomial-time reduction from the SISq,n,m,d search problem to the SISq,n,m,d decision problem.”
New lattice based cryptographic constructions (2003, background): “This function already appeared in previous papers; for example, one of the results in [11] is an average-case to average-case reduction for the function.”
Foundations of Cryptography: Volume 1, Basic Tools (2001, unknown): “Other authors have suggested basing one-way functions on the believed intractability of decoding random linear codes [29, 108] and on the subset-sum problem [132].”
Cryptography from Anonymity (2006, unknown): “(8)A somewhat simpler variant of the problem we consider here wa s implicitly considered in the context of constructing pseu dorandom generators based on subset sum [32].”
Handbook of Applied Cryptography (2018, methodology): “Impagliazzo and Naor [569] devised efficient constructions for a CSPRBG and for a universal one-way hash function which are provably as secure as the subset sum problem.”