知识卡片
二独立哈希可作一次性认证
双方秘密随机选取二独立哈希函数,对消息m发送标签h(m)。
攻击者即使看到一个消息与标签,替换成不同m′并猜其标签的成功率仍至多1/p;前提是密钥不泄露且只讨论单次伪造。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第11章 散列表 · 查看原书依据
Suppose that an adversary intercepts (m, t) en route and tries to fool Bob by replacing the pair (m, t) with a different pair (m′, t′). Argue that the probability that the adversary succeeds in fooling Bob into accepting (m′, t′) is at most 1/p, no matter how much computing power the adversary has, even if the adversary knows the family H of hash functions used.
参考来源
- 位置:《算法导论(第4版)》第11章《散列表》(OEBPS/chapter011.xhtml,文本字符[75000,80000))。
- 结论依据:问题 11-4(d) 给出二独立函数族、秘密函数、观察一对消息标签,并要求证明 1/p 伪造界;这个界是基于题设由成对独立性推得,并非原书在题目处已给证明。
- 原始内容:Suppose that an adversary intercepts ( m , t ) en route and tries to fool Bob by replacing the pair ( m , t ) with a different pair ( m ′, t ′). Argue that the probability that the adversary succeeds in fooling Bob into accepting ( m ′, t ′) is at most 1/ p , no matter how much computing power the adversary has, even if the adversary knows the family H of hash functions used.