Refinements of the k-tree Algorithm for the Generalized Birthday Problem

DOI10.1007/978-3-662-48800-3_28MaRDI QIDQ2795995zbMATH OpenOpenAlexFDO

Authors Ivica Nikolić, Yu Sasaki

Publication date 23 March 2016

Published in Advances in Cryptology – ASIACRYPT 2015 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-48800-3_28

zbMATH Keywords

\(k\)-List problem\(k\)-tree algorithmgeneralized birthday problemtime-memory tradeoff

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Cryptography (94A60)

Recommendations

• An algorithmic framework for the generalized birthday problem
• An O(n log n) algorithm for the generalized birthday problem
• On the birthday problem: Some generalizations and applications
• The generalized birthday problem
• The analysis of singletons in generalized birthday problems
• Non-uniform birthday problem revisited: refined analysis and applications to discrete logarithms
• A birthday repetition theorem and complexity of approximating dense CSPs
• New branch-and-bound algorithms for k-cardinality tree problems

Cited in

(19)

• Quantum algorithms for the \(k\)-XOR problem
• An algorithmic framework for the generalized birthday problem
• Blind Schnorr signatures and signed ElGamal encryption in the algebraic group model
• Optimal merging in quantum k-xor and k-sum algorithms
• Adventures in crypto dark matter: attacks, fixes and analysis for weak pseudorandom functions
• On the security of ECDSA with additive key derivation and presignatures
• Refined cryptanalysis of the GPRS ciphers GEA-1 and GEA-2
• Efficient and extensive search for precise linear approximations with high correlations of full SNOW-V
• A new algorithm for the unbalanced meet-in-the-middle problem
• The extended \(k\)-tree algorithm
• scientific article; zbMATH DE number 1942427 (Why is no real title available?)
• The extended \(k\)-tree algorithm
• New time-memory trade-offs for subset sum -- improving ISD in theory and practice
• Improved quantum algorithms for the k-XOR problem
• \(k\)-SUM in the sparse regime: complexity and applications
• On Wagner's k-tree algorithm over integers
• Fine-grained complexity in a world without cryptography
• A novel algorithm for the k-XOR problem
• Fine-grained cryptanalysis: tight conditional bounds for dense \(k\)-SUM and \(k\)-XOR

This page was built for publication: Refinements of the k-tree Algorithm for the Generalized Birthday Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2795995)