@inproceedings{3b86dd52744844be8e6dbd17f03ce05f,
title = "On the hardness of sparsely learning parity with noise",
abstract = "Learning Parity with Noise (LPN) represents the average-case analogue of the NP-Complete problem “decoding random linear codes”, and it has been extensively studied in learning theory and cryptography with applications to quantum-resistant cryptographic schemes. In this paper, we study a sparse variant of the LPN whose public matrix consists of sparse vectors (or alternatively each element of the matrix follows the Bernoulli distribution), of which the variant considered by Benny, Boaz and Avi (STOC 2010) falls into a (extreme) special case. We show a win-win argument that at least one of the following is true: (1) either the hardness of sparse LPN is implied by that of the standard LPN under the same noise rate; (2) there exist new black-box constructions of public-key encryption (PKE) schemes and oblivious transfer (OT) protocols from the standard LPN.",
author = "Hanlin Liu and Di Yan and Yu Yu and Shuoyao Zhao",
note = "Publisher Copyright: {\textcopyright} 2017, Springer International Publishing AG.; 11th International Conference on Provable Security, ProvSec 2017 ; Conference date: 23-10-2017 Through 25-10-2017",
year = "2017",
doi = "10.1007/978-3-319-68637-0\_16",
language = "英语",
isbn = "9783319686363",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "261--267",
editor = "Tatsuaki Okamoto and Yong Yu and Au, \{Man Ho\} and Yannan Li",
booktitle = "Provable Security - 11th International Conference, ProvSec 2017, Proceedings",
address = "德国",
}