Paper 2011/511

The Cryptographic Power of Random Selection

Matthias Krause and Matthias Hamann

Abstract

The principle of random selection and the principle of adding biased noise are new paradigms used in several recent papers for constructing lightweight RFID authentication protocols. The cryptographic power of adding biased noise can be characterized by the hardness of the intensively studied Learning Parity with Noise (LPN) Problem. In analogy to this, we identify a corresponding learning problem called RandomSelect for random selection and study its complexity. Given L secret linear functions f_1,...,f_L : {0,1}^n -> {0,1}^a, RandomSelect(L,n,a) denotes the problem of learning f_1,...,f_L from values (u,f_l(u)), where the secret indices l \in {1,...,L} and the inputs u \in {0,1}^n are randomly chosen by an oracle. We take an algebraic attack approach to design a nontrivial learning algorithm for this problem, where the running time is dominated by the time needed to solve full-rank systems of linear equations over O(n^L) unknowns. In addition to the mathematical findings relating correctness and average running time of the suggested algorithm, we also provide an experimental assessment of our results.

Note: Due to the page limit of 18 pages, some proofs had to be omitted in the LNCS version of the paper.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Full Post-Proceedings Version (Accepted to SAC 2011. Scheduled to be published in the LNCS series.)
Keywords
Lightweight CryptographyAlgebraic AttacksAlgorithmic LearningFoundations and Complexity Theory
Contact author(s)
hamann @ uni-mannheim de
History
2011-10-05: revised
2011-09-18: received
See all versions
Short URL
https://ia.cr/2011/511
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/511,
      author = {Matthias Krause and Matthias Hamann},
      title = {The Cryptographic Power of Random Selection},
      howpublished = {Cryptology ePrint Archive, Paper 2011/511},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/511}},
      url = {https://eprint.iacr.org/2011/511}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.