On solving L P N using B K W and variants
| Autor: | Serge Vaudenay, Florian Tramèr, Sonia Bogos |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
Theoretical computer science
Computer Networks and Communications Computer science business.industry Applied Mathematics media_common.quotation_subject 020206 networking & telecommunications Cryptography 0102 computer and information sciences 02 engineering and technology 01 natural sciences Noise Computational Theory and Mathematics 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Simplicity business Computer Science::Cryptography and Security media_common |
| Zdroj: | Cryptography and Communications. 8:331-369 |
| ISSN: | 1936-2455 1936-2447 |
| DOI: | 10.1007/s12095-015-0149-2 |
| Popis: | The Learning Parity with Noise problem (L P N) is appealing in cryptography as it is considered to remain hard in the post-quantum world. It is also a good candidate for lightweight devices due to its simplicity. In this paper we provide a comprehensive analysis of the existing L P N solving algorithms, both for the general case and for the sparse secret scenario. In practice, the L P N-based cryptographic constructions use as a reference the security parameters proposed by Levieil and Fouque. But, for these parameters, there remains a gap between the theoretical analysis and the practical complexities of the algorithms we consider. The new theoretical analysis in this paper provides tighter bounds on the complexity of L P N solving algorithms and narrows this gap between theory and practice. We show that for a sparse secret there is another algorithm that outperforms B K W and its variants. Following from our results, we further propose practical parameters for different security levels. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink