Name
Abstract | ||
|---|---|---|
We introduce a unifying framework for proving that predicate P is hard-core for a one-way function f, and apply it to a broad family of functions and predicates, reproving old results in an entirely different way as well as showing new hard-core predicates for well known one-way function cadidates.Our framework extends the list-coding method of Goldreich and Levin for showing hard-core predicates. Namely, a predicate will correspond to some error correcting code, predicting a predicate will correspond to access to a corrupted codeword, and the task of inverting one-way functions will correspond to the task of list decoding a corrupted codeword.A characteristic of the error correcting codes which emerge and are addressed by our framework, is that codewords can be approximated by a small number of heavy coefficients in their Fourier representation. Moreover, as long as corrupted words are close enough to legal codewords, they will share a heavy Fourier coefficient. We list decodes, by devising a learning algorithm applied to corrupted codewords for learning heavy Fourier coefficients.For codes defined over {0, 1}n domain, a learning algorithm by Kushilevitz and Mansour already exists. For codes defined over ZN, which are the codes which emerge for predicates based on number theoretic one-way functions such as the RSA and Exponentiation modulo primes, we develop a new learning algorithm. This latter algorithm may be of independent interest outside the realm of hard-core predicates. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1109/SFCS.2003.1238189 | FOCS |
Keywords | Field | DocType |
one-way function,proving hard-core,hard-core predicate,corrupted word,corrupted codeword,heavy fourier coefficient,new hard-core predicate,list decoding,number theoretic one-way function,corrupted codewords,new learning algorithm,latter algorithm,learning artificial intelligence,fourier coefficient,boolean functions,error correction code,computational complexity,one way function,cryptography,decoding | Boolean function,Discrete mathematics,Combinatorics,Computer science,Modulo,Error detection and correction,Code word,Decoding methods,List decoding,Exponentiation,Computational complexity theory | Conference |
ISSN | ISBN | Citations |
0272-5428 | 0-7695-2040-5 | 55 |
PageRank | References | Authors |
2.16 | 7 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Adi Akavia | 1 | 395 | 15.47 |
| Shafi Goldwasser | 2 | 9935 | 2069.05 |
| Samuel Safra | 3 | 55 | 2.16 |