The Cryptographic Power of Random Selection

摘要

The principle of random selection and the principle of adding biased noise are new paradigms used in several recent papers for con structing 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 for ran dom selection and study its complexity. Given L secret linear func tions f_1,...,f_L : {0,1}~n → {0,1}~α, RandomSelect(L,n,α) denotes the problem of learning f_1,..., f_l from values (u, f_1 (u)), where the se cret indices l € {1, ...,L} and the inputs u G {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 equa tions 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.