A novel improved information set decoding algorithm via nearest neighbor search

Yu Li · Li-Ping Wang · Xiangyu Pan

Cybersecurity 2026

Time bound

2^{0.057866 n + o(n)}

Space bound

2^{0.026094 n + o(n)}

Source / version date

11 Jun 2026

Comparison variant

Quantum · R = 0.454 · full GV

Cost scale

2^{c n + o(n)}

R

0.454

relative_weight

0.125869

quantum_model

Source quantum subset-sum, nearest-neighbor and Grover model

Assumptions and source notes

Theorem 4 fixes R=0.454; no maximum-over-rates claim is inferred.

Source location

Theorem 4
Version: Published 2026-06-11

Primary source ↗

@misc{li-wang-pan2026,
  author = {Yu Li and Li-Ping Wang and Xiangyu Pan},
  title = {{A novel improved information set decoding algorithm via nearest neighbor search}},
  year = {2026},
  url = {https://link.springer.com/article/10.1186/s42400-025-00469-z},
  cr_date = {2026-06-11},
  cr_status = {published},
  cr_venue = {Cybersecurity 9, article 85},
  cr_author_ids = {yu-li; li-ping-wang; xiangyu-pan}
}