@ARTICLE{bmt78, author={Berlekamp, E. and McEliece, R. and van Tilborg, H.}, journal={IEEE Transactions on Information Theory}, title={On the inherent intractability of certain coding problems (Corresp.)}, year={1978}, volume={24}, number={3}, pages={384-386}, doi={10.1109/TIT.1978.1055873}} @InProceedings{gp18, author = {Paul W. Goldberg and Christos H. Papadimitriou}, title = {{Towards a Unified Complexity Theory of Total Functions}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {37:1--37:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-060-6}, ISSN = {1868-8969}, year = {2018}, volume = {94}, editor = {Anna R. Karlin}, publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}, address = {Dagstuhl, Germany}, URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8340}, URN = {urn:nbn:de:0030-drops-83403}, doi = {10.4230/LIPIcs.ITCS.2018.37}, annote = {Keywords: Computational complexity, first-order logic, proof system, NP search functions, TFNP} } @InProceedings{lb88, author="Lee, P. J. and Brickell, E. F.", editor="Barstow, D. and Brauer, W. and Brinch Hansen, P. and Gries, D. and Luckham, D. and Moler, C. and Pnueli, A. and Seegm{\"u}ller, G. and Stoer, J. and Wirth, N. and G{\"u}nther, Christoph G.", title="An Observation on the Security of McEliece's Public-Key Cryptosystem", booktitle="Advances in Cryptology --- EUROCRYPT '88", year="1988", publisher="Springer Berlin Heidelberg", address="Berlin, Heidelberg", pages="275--280", abstract="The best known cryptanalytic attack on McEliece's public-key cryptosystem based on algebraic coding theory is to repeatedly select k bits at random from an n-bit ciphertext vector, which is corrupted by at most t errors, in hope that none of the selected k bits are in error until the cryptanalyst recovers the correct message. The method of determining whether the recovered message is the correct one has not been throughly investigated. In this paper, we suggest a systematic method of checking, and describe a generalized version of the cryptanalytic attack which reduces the work factor significantly (factor of 211 for the commonly used example of n=1024 Goppa code case). Some more improvements are also given. We also note that these cryptanalytic algorithms can be viewed as generalized probabilistic decoding algorithms for any linear error correcting codes.", isbn="978-3-540-45961-3" } @software{rust-bitvec, author = {Payne, Alexander and others}, title = {bitvec}, url = {https://github.com/bitvecto-rs/bitvec}, version = {1.0.0} } @software{rust-rand, author = {Hardy, Diggory and others}, title = "rand", url = "https://github.com/rust-random/rand", version = "0.8.5" }