A Generalized Birthday Problem

By David A. Wagner. Annual International Cryptology Conference, 2002

696 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Discrete Mathematics and Combinatorics, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/3ce6544a379e240be41a9ddb8c52597ac5e48e8b

How researchers see this paper

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

In Artificial Intelligence

In Discrete Mathematics and Combinatorics

In Electrical and Electronic Engineering

Citations in the corpus

Better Key Sizes (and Attacks) for LWE-Based Encryption (2011, background): “2 There are also purely combinatorial attacks on LWE [12, 38 ] that may perform asymp-”
Hardness of SIS and LWE with Small Parameters (2013, background): “, [11, 8]), only find solutions with bounded `2 norm, whereas combinatorial attacks such as [5, 25] (see also [20]) or theoretical lattice attacks [9] that can guarantee an `∞ bound are much more costly in practice, and also require exponential space.”
ID-Based Blind Signature and Ring Signature from Pairings (2002, background): “At Crypto2002, D. Wagner [ 28 ] claimed that he can break ROS-problem with subexponential time.”
A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks (2018, methodology): “In the ZCash network, the Equihash scheme [75] is adopted based on the generalized birthday problem [108].”
The monty hall problem : the remarkable story of math's most contentious brainteaser (2009, background): “These facts are rather difficult to prove, however, and I will refer you to [57] for the full details.”
Parallel random numbers: As easy as 1, 2, 3 (2011, neutral): “2The probability of overlapping substreams is a “birthday problem” [31].”
Lattice-Based Cryptography (2006, methodology): “The best combinatorial methods to find short vectors in q-ary lattices are variants of the algorithms presented [9, 79], e.”
Five Practical Attacks for "Optimistic Mixing for Exit-Polls" (2003, methodology): “This is stated as a theorem by Wagner [31], and appears as a lemma in Golle et al.”
SWIFFT: A Modest Proposal for FFT Hashing (2008, methodology): “Finding one vector from each list such that the sum is 0 is essentially the k-list problem that was studied by Wagner [28], and is also related to the technique used by Blum, Kalai, and Wassserman [5] for solving the parity problem in the presence of noise.”
Noise-tolerant learning, the parity problem, and the statistical query model (2000, background): “2001] and its length [Kumar and Sivakumar 2001], to cryptanalysis [Wagner 2002], and to various other analyses of statistical queries [Jackson 2000].”
Decoding Random Binary Linear Codes in 2n/20: How 1+1=0 Improves Information Set Decoding (2012, methodology): “This is realized by a three-level divide-and-conquer algorithm that is similar to Wagner’s generalized birthday algorithm [31].”
Simple Schnorr multi-signatures with applications to Bitcoin (2019, methodology): “The attacker can then use Wagner’s algorithm [47] to find n − 1 integers y2, .”
Evaluating the viability of process replication reliability for exascale systems (2011, background): “Equation 1, from [24, 19], shows how to calculate this version of the birthday problem.”
PCG : A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation (2014, methodology): “Although exact solutions to the generalized birthday problem exist [36], for simplicity we can use elementary statistics to model and approximate the solution.”