“把 $n\to n+1$ 生成器放大为 $n\to2n$ 后,可以作为GGM 树构造的分支器,从短密钥得到可自适应查询的函数。伸长证明本身只讨论一个输出串,没有自动证明指数多次查询安全。”
形式陈述
设
GGM 定理断言,
单次求值运行
直觉
把密钥看成二叉树根上的状态。向左走就取
整棵树确有
例子与边界
用一棵小树核对求值顺序
以下二位状态只演示执行,不作为安全生成器。把状态视为
根密钥取
故输出二进制
故输出
这种小型代数规则很容易被区分;GGM 的安全结论依赖输入的
逐层混合如何连接到随机函数
构造
从第
最多
每层至多
统一 PPT 的渐近证明不能免费硬连一个随
因此其绝对优势为端点优势除以
为什么不能展开整棵树作为归约
直接把每一个潜在节点都替换,表面上也能从真树走到随机树,但会出现
按需展开改变的是证明与模拟的工作量,不是函数本身。对于所有可能输入,
推论与应用
一条求值路径的外层状态占
GGM 输出是任意函数,不保证置换或可逆。要构造分组密码模型中的可逆置换,还需例如Feistel/Luby–Rackoff 构造。相反,用 PRF 作为固定长度消息的认证标签,也还需把消息编码、密钥复用与完整安全实验说明白。
参考资料
-
[1] Oded Goldreich, Shafi Goldwasser, Silvio Micali, How to Construct Random Functions, JACM 33(4), 1986, pp. 792–807。
-
[2] Ben Lynn, The Goldreich–Goldwasser–Micali Construction, Stanford 密码学笔记:树构造与混合分布的定义。本文按首次访问节点展开自适应查询的模拟,并区分具体损失与统一算法的抽样步骤。
-
[3] Dan Boneh and Victor Shoup, A Graduate Course in Applied Cryptography, version 0.6, 2023,§4.6,Theorem 4.10:树构造、逐层游戏与查询预算。