Cryptography from learning parity with noise Conference Paper


Author(s): Pietrzak, Krzysztof
Title: Cryptography from learning parity with noise
Title Series: LNCS
Affiliation IST Austria
Abstract: The Learning Parity with Noise (LPN) problem has recently found many applications in cryptography as the hardness assumption underlying the constructions of "provably secure" cryptographic schemes like encryption or authentication protocols. Being provably secure means that the scheme comes with a proof showing that the existence of an efficient adversary against the scheme implies that the underlying hardness assumption is wrong. LPN based schemes are appealing for theoretical and practical reasons. On the theoretical side, LPN based schemes offer a very strong security guarantee. The LPN problem is equivalent to the problem of decoding random linear codes, a problem that has been extensively studied in the last half century. The fastest known algorithms run in exponential time and unlike most number-theoretic problems used in cryptography, the LPN problem does not succumb to known quantum algorithms. On the practical side, LPN based schemes are often extremely simple and efficient in terms of code-size as well as time and space requirements. This makes them prime candidates for light-weight devices like RFID tags, which are too weak to implement standard cryptographic primitives like the AES block-cipher. This talk will be a gentle introduction to provable security using simple LPN based schemes as examples. Starting from pseudorandom generators and symmetric key encryption, over secret-key authentication protocols, and, if time admits, touching on recent constructions of public-key identification, commitments and zero-knowledge proofs.
Keywords: QUANTUM THEORY; Algorithms; Authentication protocols; Cryptographic primitives; Cryptographic schemes; Exponential time; Learning parity with noise; Light weight; Provable security; Provably secure; Pseudorandom generators; Public keys; Quantum algorithms; Random linear codes; RF-ID tags; Space requirements; Symmetric key encryption; Zero knowledge proof; Authentication; Codes (symbols); Computer science; Hardness; Radio navigation
Conference Title: SOFSEM: Current Trends in Theory and Practice of Computer Science
Volume: 7147
Conference Dates: January 21-27, 2012
Conference Location: Špindleruv Mlýn, Czech Republic
ISBN: 978-3-642-27659-0
Publisher: Springer  
Date Published: 2012-02-19
Start Page: 99
End Page: 114
DOI: 10.1007/978-3-642-27660-6_9
Open access: no
IST Austria Authors
Related IST Austria Work