Abstract | ||
---|---|---|
We propose a new authentication protocol that is provably secure based on a ring variant of the learning parity with noise (LPN) problem. The protocol follows the design principle of the LPN-based protocol from Eurocrypt'11 (Kiltz et al.), and like it, is a two round protocol secure against active attacks. Moreover, our protocol has small communication complexity and a very small footprint which makes it applicable in scenarios that involve low-cost, resource-constrained devices. Performance-wise, our protocol is more efficient than previous LPN-based schemes, such as the many variants of the Hopper-Blum (HB) protocol and the aforementioned protocol from Eurocrypt'11. Our implementation results show that it is even comparable to the standard challenge-and-response protocols based on the AES block-cipher. Our basic protocol is roughly 20 times slower than AES, but with the advantage of having 10 times smaller code size. Furthermore, if a few hundred bytes of non-volatile memory are available to allow the storage of some off-line pre-computations, then the online phase of our protocols is only twice as slow as AES. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1007/978-3-642-34047-5_20 | FSE |
Keywords | Field | DocType |
small footprint,small communication complexity,lpn-based protocol,basic protocol,efficient authentication protocol,round protocol,previous lpn-based scheme,aes block-cipher,aforementioned protocol,standard challenge-and-response protocol,new authentication protocol | Byte,Code size,Computer science,Computer network,Otway–Rees protocol,Communication complexity,Authentication protocol,Universal composability | Conference |
Volume | ISSN | Citations |
7549 | 0302-9743 | 8 |
PageRank | References | Authors |
0.50 | 22 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Stefan Heyse | 1 | 149 | 9.27 |
Eike Kiltz | 2 | 2872 | 117.46 |
Vadim Lyubashevsky | 3 | 1174 | 59.91 |
Christof Paar | 4 | 3794 | 442.62 |
Krzysztof Pietrzak | 5 | 1513 | 72.60 |