CryptoRecords.info
Binary decoding

Decoding random binary codes

Decode a random binary linear code at a specified rate and error weight.

Quantum · full GV distance

Quantum ISD for random binary codes at full GV distance; maximum over rates

7 results · 4 papers
QuantumSource analysisRandom binary linear codes2c n + o(n)
Results
Compare historyJSONCSV
#PUBLICATION / AUTHORSDATETIME BOUNDSPACE BOUNDEVIDENCE
1From Subset-Sum to Decoding: Improved Classical and Quantum Algorithms via Ternary Representation TechniqueYang LiInformation 2025SourceBibTeX / detailsheuristic exponential qubits12 Oct 202520.058326 n + o(n)—PublishedSource checked
2Quantum Information Set Decoding AlgorithmsGhazal Kachigar · Jean-Pierre TillichPQCrypto 2017SourceBibTeX / detailsquantum ISD binary random codes full GV distance maximum over rates quantum walks1 Mar 201720.05869 n + o(n)—PublishedSource checked
3Improved Quantum Information Set DecodingElena KirshanovaPQCrypto 2018SourceBibTeX / details2 Aug 201820.059037 n + o(n)20.01502 n + o(n)PublishedSource checked
4Improved Quantum Information Set DecodingElena KirshanovaPQCrypto 2018SourceBibTeX / details2 Aug 201820.05945 n + o(n)20.00808 n + o(n)PublishedSource checked
5Quantum Information Set Decoding AlgorithmsGhazal Kachigar · Jean-Pierre TillichPQCrypto 2017SourceBibTeX / detailsquantum ISD binary random codes full GV distance maximum over rates quantum walks1 Mar 201720.05970 n + o(n)—PublishedSource checked
6Improved Quantum Information Set DecodingElena KirshanovaPQCrypto 2018SourceBibTeX / details2 Aug 201820.059922 n + o(n)20.00897 n + o(n)PublishedSource checked
7Grover vs. McElieceDaniel J. BernsteinPost-Quantum Cryptography 2010SourceBibTeX / detailsquantum ISD binary random codes full GV distance maximum over rates quantum walks23 Nov 200920.06035 n + o(n)—PublishedSource checked
1–7 of 7 entriesIncludes relevant non-record results. Dates refer to the specific bound.
Comparison definition & assumptions
Regime
Quantum ISD for random binary codes at full GV distance; maximum over rates
Computation
Quantum
Rigor
Source analysis
Instances
Random binary linear codes
Cost scale
2^{c n + o(n)}
Parameter
n
Description
Quantum full-distance ISD with the source memory and oracle model attached.
Comparison rules
Use random binary linear codes of rate R=k/n, error weight n H₂⁻¹(1−R), and maximize the exponent over 0≤R≤1. The parameter n is code length. Keep half-distance and fixed-rate bounds separate. Historical coefficients are rounded as in their cited sources; they are upper bounds, not claimed optimal values. Quantum-walk entries charge the setup/update/check model of the source. These are not claims for a memory-free quantum circuit model.
Tags
quantum, ISD, binary, random codes, full GV distance, maximum over rates, quantum walks