Decoding Linear Codes with High Error Rate and Its Impact for LPN Security
作者： Leif Both , Alexander May
DOI: 10.1007/978-3-319-79063-3_2
关键词:
摘要: We propose a new algorithm for the decoding of random binary linear codes dimension n that is superior to previous algorithms high error rates. In case Full Distance decoding, best known bound \(2^{0.0953n}\) currently achieved via BJMM-algorithm Becker, Joux, May and Meurer. Our significantly improves this down \(2^{0.0885n}\).
springer.com
sci-hub.se 参考文章(11)
Alexander May, Alexander Meurer, Enrico Thomae, Decoding random linear codes in Õ(2 0.054 n ) international conference on the theory and application of cryptology and information security. pp. 107- 124 ,(2011) , 10.1007/978-3-642-25385-0_6
Anja Becker, Antoine Joux, Alexander May, Alexander Meurer, Decoding Random Binary Linear Codes in 2 n/20: How 1 + 1 = 0 Improves Information Set Decoding Advances in Cryptology – EUROCRYPT 2012. pp. 520- 536 ,(2012) , 10.1007/978-3-642-29011-4_31
Alexander May, Ilya Ozerov, On Computing Nearest Neighbors with Applications to Decoding of Binary Linear Codes theory and application of cryptographic techniques. pp. 203- 228 ,(2015) , 10.1007/978-3-662-46800-5_9
Jacques Stern, A method for finding codewords of small weight Proceedings of the third international colloquium on Coding theory and applications. pp. 106- 113 ,(1989) , 10.1007/BFB0019850
Daniel J. Bernstein, Tanja Lange, Christiane Peters, Smaller decoding exponents: ball-collision decoding international cryptology conference. ,vol. 2010, pp. 743- 760 ,(2011) , 10.1007/978-3-642-22792-9_42
Qian Guo, Thomas Johansson, Carl Löndahl, Solving LPN Using Covering Codes Lecture Notes in Computer Science. ,vol. 8873, pp. 1- 20 ,(2014) , 10.1007/978-3-662-45611-8_1
Oded Regev, On lattices, learning with errors, random linear codes, and cryptography Proceedings of the thirty-seventh annual ACM symposium on Theory of computing - STOC '05. pp. 84- 93 ,(2005) , 10.1145/1060590.1060603
E. Prange, The use of information sets in decoding cyclic codes IEEE Transactions on Information Theory. ,vol. 8, pp. 5- 9 ,(1962) , 10.1109/TIT.1962.1057777
Daniel J. Bernstein, Tanja Lange, Christiane Peters, Attacking and Defending the McEliece Cryptosystem PQCrypto '08 Proceedings of the 2nd International Workshop on Post-Quantum Cryptography. pp. 31- 46 ,(2008) , 10.1007/978-3-540-88403-3_3
M. Alekhnovich, More on average case vs approximation complexity foundations of computer science. pp. 298- 307 ,(2003) , 10.1109/SFCS.2003.1238204