Complete Classification of Bilinear Hard-Core Functions
Complete Classification of Bilinear Hard-Core Functions
复制标题
双线性硬核函数的完整分类
DOI：
10.1007/978-3-540-28628-8_5
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Johan Sjödin
中科院分区：
文献类型：
--
作者：
Thomas Holenstein;U. Maurer;Johan Sjödin
令 f:{0,1} n →{0,1} l 为单向函数。函数 h: {0,1} n → {0,1} m 被称为 f 的硬核函数，如果当给定从 {0,1} n 均匀提取的（秘密） x 的 f(x) 时，在计算上无法区分 h(x) 和均匀随机的 m 位字符串。一个（随机）函数 h: {0,1} n × {0,1} k →{0,1} m 是一个一般的硬核函数，如果它对于每个单向函数 f:{0,1} n →{0,1} l 都是硬核函数，其中 h 的第二个输入是 k 位均匀随机字符串 r。硬核函数是密码学中的重要工具，特别是用于从任何单向函数构造伪随机生成器和伪随机函数。
Let f:{0,1} n →{0,1} l be a one-way function. A function h: {0,1} n → {0,1} m is called a hard-core function for f if, when given f(x) for a (secret) x drawn uniformly from {0,1} n , it is computationally infeasible to distinguish h(x) from a uniformly random m-bit string. A (randomized) function h: {0,1} n × {0,1} k →{0,1} m is a general hard-core function if it is hard-core for every one-way function f:{0,1} n →{0,1} l , where the second input to h is a k-bit uniform random string r. Hard-core functions are a crucial tool in cryptography, in particular for the construction of pseudo-random generators and pseudo-random functions from any one-way function.