Quantum Information Set Decoding Algorithms

Ghazal Kachigar · Jean-Pierre Tillich

PQCrypto 2017

Time bound

2^{0.05869 n + o(n)}

Space bound

—

Source / version date

1 Mar 2017

Comparison variant

Quantum · full GV distance

Cost scale

2^{c n + o(n)}

Code alphabet

𝔽₂

Rate convention

Maximize over 0≤R≤1

Error weight

Full GV distance: n H₂⁻¹(1−R)

Computation model

Quantum Grover search and quantum walk; source setup/update/check costs

access

Source quantum list-memory/oracle model

reference

KT17

Assumptions and source notes

Introductory comparison table, full GV distance and maximum over rates. First arXiv date shown; two variants share this date. The more precise 2018 reanalysis (https://arxiv.org/pdf/1808.00714, Table 1) is corroborating analysis of the same time exponent, not a separate historical improvement; source-reported decimals are retained here.

Primary source ↗

@misc{paper-c95c0e507206,
  author = {Ghazal Kachigar and Jean-Pierre Tillich},
  title = {{Quantum Information Set Decoding Algorithms}},
  year = {2017},
  url = {https://arxiv.org/abs/1703.00263},
  cr_date = {2017-03-01},
  cr_status = {published},
  cr_venue = {PQCrypto 2017},
  cr_author_ids = {ghazal-kachigar; jean-pierre-tillich},
  howpublished = {Post-Quantum Cryptography 2017; arXiv:1703.00263}
}