@inproceedings{80482092731f40cf9746e9512245818a,
title = "On the Robustness of learning parity with noise",
abstract = "The Learning Parity with Noise (LPN) problem is well understood in learning theory and cryptography and has been found quite useful in constructing various lightweight cryptographic primitives. There exists non-trivial evidence that the problem is robust on highentropy secrets (and even given hard-to-invert leakages), and the justified results by Dodis, Kalai and Lovett (STOC 2009) were established under non-standard hard learning assumptions. The recent progress by Suttichaya and Bhattarakosol (Information Processing Letters, Volume 113, Issues 14–16) claimed that LPN remains provably secure (reducible from the LPN assumption itself) as long as the secret is sampled from any linear min-entropy source, and thereby resolves the long-standing open problem. In the paper, we point out that their proof is flawed and their understanding about LPN is erroneous. We further offer a remedy with some slight adaption to the setting of Suttichaya and Bhattarakosol.",
keywords = "High-entropy secrets, Learning parity with noise, Leftover hash lemma, Provable security",
author = "Nan Yao and Yu Yu and Xiangxue Li and Dawu Gu",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2016.; 18th International Conference on Information and Communications Security, ICICS 2016 ; Conference date: 29-11-2016 Through 02-12-2016",
year = "2016",
doi = "10.1007/978-3-319-50011-9\_8",
language = "英语",
isbn = "9783319500102",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "99--106",
editor = "Kwok-Yan Lam and Sihan Qing and Chi-Hung Chi",
booktitle = "Information and Communications Security - 18th International Conference, ICICS 2016, Proceedings",
address = "德国",
}