24小时热门版块排行榜    

查看: 486  |  回复: 1
本帖产生 1 个 博学EPI ,点击这里进行查看

whiteman99

金虫 (正式写手)

[求助] 求解/求证随机变换族问题

假设有P0,P1,P2三个随机变换族(PRF)
小写的表示PRP,取自对应的PRF
设:
变换p=p0 。p1。p2
变换p'=p0' 。p1。p2'
|dom(p0)|=|dom(p2)|<<|dom(p1)|
假设分析者已经知道p0,p0';p2,p2'
是否存在与log(|dom(p0)|)为多项式复杂度的算法,可以分辨p和p' ??

» 猜你喜欢

» 本主题相关价值贴推荐,对您同样有帮助:

已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

computersim

至尊木虫 (知名作家)

【答案】应助回帖

★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ...
whiteman99: 金币+80, 博学EPI+1, ★★★很有帮助, 很有帮助,按你的思路试试先 2014-06-30 18:26:19
whiteman99: 金币+90, ★★★★★最佳答案 2014-07-02 00:30:45
用两个Game试一试,首先假设有这样的算法A
A-->Game1-->Simulator(b)-->Game2-->Oracle

Simulator(b)
b=0
p0 。p1。p2
p0' 。p1。p2
b=1
p0 。p1。p2'
p0' 。p1。p2'

如果能够算出类似(1/2+e)/2之类的概率就有希望

另外你好像遗漏了一个前提条件,就是某些P是否可分辨。
2楼2014-06-29 22:37:00
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 whiteman99 的主题更新
信息提示
请填处理意见