On the security of Goldreich’s one-way function |
| |
Authors: | Andrej Bogdanov Youming Qiao |
| |
Affiliation: | 1. Department of CSE and ITCSC, Chinese University of Hong Kong, Shatin, N.T., Hong Kong 2. ITCS, Tsinghua University, Beijing, 100084, China
|
| |
Abstract: | Goldreich (ECCC 2000) suggested a simple construction of a candidate one-way function f : {0, 1}
n
→ {0, 1}
m
where each bit of output is a fixed predicate P of a constant number d of (random) input bits. We investigate the security of this construction in the regime m = Dn, where D(d) is a sufficiently large constant. We prove that for any predicate P that correlates with either one or two of its inputs, f can be inverted with high probability. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|