294 Y. Chen and Z. Zhang / Publicly evaluable pseudorandom functions and their applications
We let N denote the positive integers. The natural security parameter throughout the paper is λ,and
all other quantities as well as all algorithms (including the adversary) are implicitly functions of λ.We
write
poly(λ) to denote an arbitrary polynomial function in λ. We write negl(λ) to denote an arbitrary
negligible function in λ, which vanishes faster than the inverse of any polynomial. We say a proba-
bility is overwhelming if it is 1 −
negl(λ), and said to be noticeable if it is 1/poly(λ). A probabilistic
polynomial-time (PPT) algorithm is a randomized algorithm that runs in time
poly(λ).IfA is a ran-
domized algorithm, we write z ←
A(x
1
,...,x
n
; r) to indicate that A outputs z on inputs (x
1
,...,x
n
)
and randomness r. We will omit r and write z ←
A(x
1
,...,x
n
). In addition, we assume an algorithm
always outputs ⊥ when its input is ⊥.
The statistical distance between two random variables X and Y having a common domain S is
[X, Y ]=
1
2
s∈S
| Pr[X = s]−Pr[Y = s]|. We write ≈
c
as shorthand for computationally indis-
tinguishable.
2.2. Languages and relations
Cryptographic hard problems are usually given by a set of instances, which we denote by X. We call
a subset L of X as a language, in which all its elements meet some property. Typically, a language L can
be associated with a binary relation
R
L
⊆ X × W , i.e., x ∈ L ⇔∃w ∈ W s.t. (x, w) ∈ R
L
. The only
restriction is that if (x, w) ∈
R
L
,then|w| poly(|x|). We call w ∈ W a witness for the membership of
x ∈ L. We recall some properties of relations as below.
(1) Easy to sample a tuple: There exists a PPT algorithm
SampRel that on input a public descrip-
tion pp for
R
L
and fresh random coins r, outputs a random tuple (x, w) ∈ R
L
. We can further
decompose
SampRel to SampLan and SampWit. The former on input pp and r outputs x ∈ L,
while the latter on input pp and r outputs w ∈ W .
4
Hereafter, let R be the random coins space
of
SampRel, SampLan,andSampWit. We require that for any r ∈ R, it holds that (SampLan(r),
SampWit(r)) ∈ R
L
.
(2) Hard to find a witness:Givenx where (x, w) ←
SampRel(pp; r), no PPT algorithm can compute
w
such that (x, w
) ∈ R
L
with non-negligible probability.
(3) Easy to verify a tuple:
R
L
is polynomially-verifiable (i.e., R
L
∈ P).
We say a relation
R
L
is hard or one-way if it satisfies the first two properties. We say a relation R
L
is
polynomially bounded if it satisfies the third property. Polynomially bounded relations define the usual
NP language.
Definition 2.1 (Subset membership problem). Let L ⊂ X be a language, and both L and X\L allow
efficiently uniform sampling (let
SampYes and SampNo be the sampling algorithms respectively
5
). We
say subset membership problem w.r.t. (X, L) is hard if:
U
X\L
≈
c
U
L
.
4
When the context is clear, we usually omit pp from the input of SampRel.
5
Without loss of generality, we assume SampYes and SampLan induce identical distribution over L.
剩余31页未读，继续阅读
weixin_38501206
- 粉丝: 6
- 资源: 889
我的内容管理
展开
最新资源
- 解决本地连接丢失无法上网的问题
- BIOS报警声音解析：故障原因与解决方法
- 广义均值移动跟踪算法在视频目标跟踪中的应用研究
- C++Builder快捷键大全：高效编程的秘密武器
- 网页制作入门：常用代码详解
- TX2440A开发板网络远程监控系统移植教程：易搭建与通用解决方案
- WebLogic10虚拟内存配置详解与优化技巧
- C#网络编程深度解析：Socket基础与应用
- 掌握Struts1：Java MVC轻量级框架详解
- 20个必备CSS代码段提升Web开发效率
- CSS样式大全：字体、文本、列表样式详解
- Proteus元件库大全：从基础到高级组件
- 74HC08芯片：高速CMOS四输入与门详细资料
- C#获取当前路径的多种方法详解
- 修复MySQL乱码问题：设置字符集为GB2312
- C语言的诞生与演进：从汇编到系统编程的革命
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
