Open AccessQuantum Algorithms for the $$k$$-xor Problem
Author(s) -
Lorenzo Grassi,
María NayaPlasencia,
André Schrottenloher
Publication year - 2018
Publication title -
lecture notes in computer science
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 0.249
H-Index - 400
eISSN - 1611-3349
pISSN - 0302-9743
DOI - 10.1007/978-3-030-03326-2_18
Subject(s) - quantum algorithm , qubit , algorithm , cryptography , quantum , computer science , quantum computer , post quantum cryptography , logarithm , theoretical computer science , discrete mathematics , mathematics , quantum mechanics , physics , mathematical analysis
The \(k\)-xor (or generalized birthday) problem is a widely studied question with many applications in cryptography. It aims at finding k elements of n bits, drawn at random, such that the xor of all of them is 0. The algorithms proposed by Wagner more than fifteen years ago remain the best known classical algorithms for solving them, when disregarding logarithmic factors.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom