专栏首页包罗万想GCAC21 6.4 Prefix-free PRFs for long messages

GCAC21 6.4 Prefix-free PRFs for long messages

6.4 Prefix-free PRFs for long messages长消息的无前缀PRF

在上一节中,我们看到任何安全的PRF也是安全的MAC。但是,第4章中的PRF的具体示例仅使用简短的输入,因此只能用于为非常短的消息提供完整性。例如,将AES视为PRF可提供用于128位消息的MAC。显然,我们希望为更长的消息构建MAC。本章中的所有MAC构造都遵循相同的范例:它们从用于短输入(如AES)的PRF开始,并产生PRF,从而产生用于更长输入的MAC。因此,本章其余部分的目标如下

给定短输入的安全PRF构造长输入的安全PRF

我们分三个步骤解决此问题

:•首先,在本节中,我们为长输入构建无前缀的安全PRF。更精确地,给定对单个块(例如128位)输入进行操作的安全PRF,我们构造对块的可变长度序列进行操作的无前缀的安全PRF。回想一下,无前缀的安全PRF(定义4.5)仅在有限的意义上是安全的:我们仅要求无前缀的对手不能将PRF与随机函数区分开。无前缀的PRF对手发出的查询是非空的块序列,并且任何查询都不能成为另一个适当的前缀。

•其次,在接下来的几节中,我们将介绍如何将长输入的无前缀安全PRF转换为长输入的完全安全PRF。因此,在这些部分的结尾,我们将有几个安全的PRF,因此也有安全的MAC,它们可以在长输入上运行。

•第三,在第6.8节中,我们说明如何将对块字符串进行操作的PRF转换为对比特字符串进行操作的PRF

例如,如果无前缀对手发出对序列(a1,a2,a3)的查询,则它不能对(a1)或(a1,a2)发出查询

Prefix-free PRFs.

We begin with two classic constructions for prefix-free secure PRFs. The CBC construction is shown in Fig. 6.3a. The cascade construction is shown in Fig. 6.3b. We show that when the underlying F is a secure PRF, both CBC and cascade are prefix-free secure PRFs.

6.4.1 The CBC prefix-free secure PRF

这个证明思路已经见多了。

game0 是PRF的 attack game

game1 是真随机的

game2 是用了诚实的侏儒

game3 是用了健忘的侏儒

然后game2和game3利用一个差分引理。

把每一步得到的式子联立,得证目标。

最后在算一下term,当然term不是我们的重点。

这个X集合是节点的路径。

本文分享自微信公众号 - 包罗万想(An-mind),作者:安包

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-31

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • GCAC13 5.4.2 Randomized counter mode

    在本节中,我们描述了多种构建密码的方法,这些密码是CPA安全的。 我们在5.4.1节中以通用构造开始,该构造将任何语义安全的密码与伪随机函数(PRF)相结合。...

    安包
  • GCAC59 作业9答案

    仅是我的答案,不是标准答案,结合助教给的答案,修改过很多次,应该没什么问题了,供大家参考。如果发现错误请评论区留言,谢谢。

    安包
  • 密码学可证明安全:CPA<=PRF+SS

    今年做了助教,帮负责一下tutorial的部分内容讲解。也是一次温故知新的过程。这是这周讲过的内容。整本书的最核心也是最简单的一个密码学方案证明。去年记录的笔记...

    安包
  • 一个API调用27个NLP预训练模型:BERT、GPT-2全囊括,像导入NumPy一样容易

    只需一个API,就能调用BERT、XLM等多种语言模型,逆天的GPT-2也一样轻松到碗里来,这样的模型库你是否期待?

    量子位
  • GitHub超9千星:一个API调用27个NLP预训练模型:BERT、GPT-2全囊括

    只需一个API,就能调用BERT、XLM等多种语言模型,逆天的GPT-2也一样轻松到碗里来,这样的模型库你是否期待?

    数说君
  • Pytorch 0.3.0 发布:新增张量函数,支持模型移植

    根据官方文档的介绍,此次增加了多个函数和功能,多方面的性能均实现提升。 重大变更 0.3 版本中删掉了 Variable.reinforce() 等随机函数,因...

    BestSDK
  • 机器学习——信用卡反欺诈案例

    py3study
  • Python 3 入门,看这篇就够了

    链接:https://shockerli.net/post/python-study-note/

    华章科技
  • Pytorch 0.3发布:实现多方面提速,增加对ONNX支持 | 快讯

    2017 年初,Facebook 在机器学习和科学计算工具 Torch 的基础上,针对 Python 语言发布了一个全新的机器学习工具包 PyTorch。一经发...

    AI研习社
  • Python基础语法-内置数据结构之列表

    列表特性总结 列表的一些特点: 列表是最常用的线性数据结构 list是一系列元素的有序组合 list是可变的 列表的操作, 增:append、extend、in...

    1846122963

扫码关注云+社区

领取腾讯云代金券