跳转到内容
← 返回计算理论
计算理论当代约 22 分钟阅读

Goldreich–Goldwasser–Micali 1986：长度翻倍发生器怎样铺成询问下仍像随机的函数

How to Construct Random Functions

Goldreich–Goldwasser–Micali伪随机函数GGM 树长度翻倍发生器计算不可区分JACM 1986

1986 年 10 月，《Journal of the ACM》第 33 卷第 4 期刊出奥德·戈德赖希（Oded Goldreich）、沙菲·戈德瓦塞尔（Shafi Goldwasser）与西尔维奥·米卡利（Silvio Micali）的《How to Construct Random Functions》，页码 792 至 807。DOI 为 10.1145/6490.6503。期刊把三位作者单位都印作麻省理工学院，剑桥，马萨诸塞。戈德赖希受魏茨曼博士后奖学金资助，现通讯地址印作海法以色列理工学院；戈德瓦塞尔与米卡利的现通讯地址印作麻省理工学院计算机科学实验室，技术广场 545 号。ACM 把正式上网日期记为 1986 年 8 月 10 日，封面期号仍是 10 月号。本页的对象是这份已印行的十六页期刊论文：从一台把种子长度翻倍的伪随机发生器出发，沿一棵深度为 $n$ 的二叉树铺出一整族多项式时间可评估的函数；多项式时间的观察者即使自己选定输入、反复询问函数值，仍然不能把这族函数与均匀随机函数分开。课堂所称「GGM 树」，封面钉在这份 JACM 文本上。它不是人物评传，也不是分组密码说明书。

封面是 1986 年这份十六页，不是 1984 年 10 月 24 日至 26 日在佛罗里达州辛格岛举行的第二十五届计算机科学基础年会（FOCS）会议录页码 464 至 479 的同名先行本。那一篇 DOI 为 10.1109/SFCS.1984.715949，十六页扩展摘要已经写出函数上的随机性与树形构造，却不是本页封面。更早的麻省理工学院计算机科学实验室技术备忘录 MIT/LCS/TM-244 印于 1983 年 11 月，标题相同，也不是期刊。把「一九八四年那篇随机函数」收成一句，会把会议摘要与期刊定义焊成一次页码。CRYPTO 1984 的《On the Cryptographic Applications of Random Functions》后来收进 LNCS 第 196 卷页码 276 至 288，对象是同一装置的应用邻居，封面仍停在 JACM。

它不是 1984 年 4 月《计算机与系统科学杂志》第 28 卷第 2 期页码 270 至 299 的戈德瓦塞尔–米卡利概率加密，DOI 为 10.1016/0022-0000(84)90070-9。那三十页问的是公钥密文在多项式观察者面前必须像随机对象；作者少了戈德赖希，对象是传消息，不是可询问的函数族。它也不是 1985 年 5 月普罗维登斯第十七届 STOC 页码 291 至 304 的戈德瓦塞尔–米卡利–拉科夫交互证明摘要。那十四页问的是证明对话泄露了多少额外知识，作者名单里多了查尔斯·拉科夫（Charles Rackoff）。把「戈德瓦塞尔与米卡利一九八四到八六」收成一句，会把概率加密、交互证明与伪随机函数焊成一次页码。它不是同年 11 月《SIAM Journal on Computing》第 13 卷第 4 期页码 850 至 864 的布卢姆–米卡利伪随机比特论文，也不是姚期智 1982 年芝加哥 FOCS 页码 80 至 91 的陷门函数论文。前一篇给出离散对数上的硬核与发生器，后一篇给出计算不可区分与任意单向置换上的发生器；本页把已经造好的长度翻倍发生器当成燃料，产品是函数，不是比特串。它更不是 1989 年西雅图 STOC 页码 12 至 24 的因帕利亚佐–列文–卢比论文，也不是同本会议录页码 25 至 32 的戈德赖希–列文内积硬核。那一组问的是一般单向函数怎样交出发生器与硬核；本页假定发生器已经在那儿。它也不是 1997 年《计算机与系统科学杂志》第 55 卷第 1 期页码 24 至 35 的拉兹博罗夫–鲁迪奇自然证明。那十二页把本页的函数族当成对象去挡电路下界手续，封面不是「怎样铺树」。本页不提供如何装配分组密码、如何抽取生产用的种子、如何去攻一台发生器的步骤。

它不是 密码学基础 总览，也不是 沙菲·戈德瓦塞尔 的人物页。总览与传记已经把伪随机函数收成地图上的一格；本页只抽出 1986 年这一枚钉子。它不是 随机算法 总览，也不是 计算复杂性 的 $P$ 对 $NP$ 地图。十六页里被钉住的是长度翻倍发生器、深度为 $n$ 的二叉树、根上的短种子，以及选定输入的多项式观察者为什么仍然分不开。

破除误解：伪随机函数不是已经造好的密钥流，询问权也不等于已经拆开

第一种最快的读法是：把戈德赖希–戈德瓦塞尔–米卡利听成 1984 年那三十页概率加密，或听成 1985 年那十四页交互证明。两人 1984 年合写的是传消息：密文不得让多项式旁观者多知道明文的任何可计算函数。三人 1985 年与拉科夫合写的是传证。三人 1986 年合写的是另一件东西：短种子决定的函数，在允许对方自己点名输入的多项式观察者面前，仍须与均匀随机函数不可区分。FOCS 先行本与期刊共享标题，页码与 DOI 却不是同一印刷。把四份封面收成一句，会把加密、零知识与函数族焊成一次页码。

第二层误解把标题听成已经造出真正的随机函数，或听成一份把密钥流焊进产品的分组密码。均匀随机函数的真值表大约需要 n⋅2nn\cdot 2^{n} 个比特才能写完；十六页交出的是 $k$ 比特种子索引的一小族，评估却必须落在多项式时间里。统计上这族函数的支撑集相对全部函数小得可以忽略。多项式观察者看不见整张表，只能按自己选定的输入要值。被证明的是计算不可区分，不是概率恒等式。后年把伪随机函数改写成伪随机置换的工作是邻居，不是页码 792 至 807。把「随机函数」听成一次性密码本或已部署的分组密码，会把一次复杂性陈述收成一次产品说明书。

第三层误解把「可以询问自己选定的输入」听成已经给出攻击日程，或听成只要自适应地点名，函数就会露出种子。原文的观察者模型本来就允许自适应：下一次问什么，可以依赖于已经看见的值。定义要挡住的，正是这一档最不利的多项式询问。归约把函数上的缝送到某一层发生器，证明策略存在，不等于一份对线上系统的检测步骤。概念证据到此为止，不是操作单，也不是课堂实验清单。

第四层误解把这里的发生器听成已经证明单向函数存在，或听成 1989 年那一组「任意单向函数交出发生器」的印刷。十六页是条件句：若存在把 $k$ 比特拉成 $2k$ 比特、并且对多项式测试者不可区分于真随机串的发生器，则树形铺开的函数族对多项式询问者不可区分于均匀随机函数。它没有构造发生器。布卢姆–米卡利把燃料钉在离散对数，姚期智把燃料写成任意单向置换，因帕利亚佐–列文–卢比才去掉「必须可逆」。本页停在「发生器已经在那儿」这一侧。拉兹博罗夫与鲁迪奇后来把这族函数当成对象去挡自然证明，那是后十一年的用法，不是本页封面。

长度翻倍发生器、深度为 n 的二叉树，以及根上的种子

装置从「什么样的随机函数」开始，而不是从一张密钥表开始。真随机函数把每一个输入独立地送到一个均匀随机的输出。要写下 $n$ 比特到 $n$ 比特的全部对应，表的长度对输入长度是指数。若要求看见输出之后关于种子的不确定性丝毫不减，短种子拉长之后在信息论上立刻破产。多项式时间的观察者没有这种全能。姚期智已经把「所有多项式时间统计测试都分不开」写成发生器输出与真随机串之间的计算不可区分；本页把同一口径从字符串搬到函数。观察者得到的不是一段写死的比特，而是一枚神谕：自己选定输入，收回函数值，再决定下一个输入。通过所有这样的多项式测试，被他们称作多项式随机的函数族。

燃料是一台长度翻倍的伪随机发生器。它把 $k$ 比特种子确定性、多项式时间地写成 $2k$ 比特；任何概率多项式时间的测试者，看见输出之后，仍不能把它与均匀随机的 $2k$ 比特串分开。把输出从中剖开，左边 $k$ 比特记作沿 $0$ 走的子种子，右边 $k$ 比特记作沿 $1$ 走的子种子。发生器本身不是本页构造的对象，而被当作已经存在的黑箱。布卢姆–米卡利与姚期智提供的是这类黑箱的先行文本；本页问的是黑箱够不够铺出一整张可随机访问的表。

树把发生器铺成函数。根上放种子。每一个内部结点把它的标签送进发生器，左右孩子分别拿到左右两半。输入是长度 $n$ 的比特串，从高位到低位决定每一步走左还是走右。走到深度 $n$ 的叶子，叶子上的标签就是这个输入上的函数值。课堂常取 $n=k$，于是定义域与值域都是 $k$ 比特串。整棵树有指数多个结点，没有人把它物化：评估一条输入只沿着一条长度为 $n$ 的路径走，发生器被调用 $n$ 次。短种子因此给出对一张指数大表的随机访问，而评估仍停在多项式时间里。函数族的基数是种子空间的大小，不是全部函数的数量。把「铺树」听成必须先写出全部叶子，会把一次路径评估收成一次指数表。

不可区分靠混合论证，而不是靠把树拆开给对手看。想象一串混合总体：第 $i$ 个混合里，深度不超过 $i$ 的结点标签改成真随机、但同一前缀保持一致，更深的结点仍用发生器往下长。一端是本页的函数族，另一端在被询问的那些点上已经是均匀随机函数。若多项式询问者仍能分开两端，相邻两个混合之间必有不可忽略的缝，而相邻混合只在某一层用了一次发生器。那条缝被送回长度翻倍发生器，与发生器假设矛盾。混合是存在性归约，说明函数上的优势可以翻译成字符串上的优势，不是一份按层询问去还原种子的日程。自适应询问已经含在观察者模型里。十六页证明翻译手续存在。本页不把混合改写成课堂实验。

效率写在模型自己的粒度上。评估代价与输入长度成正比，因为路径有多深，发生器就要走多远。后来寻求更少调用、更多并行的构造是邻居，不是页码 792 至 807。十六页也勾画了理论后果：共享一枚短种子，在多项式观察者面前可以像共享一张巨大的随机表。私钥加密、身份识别与报文完整性在原文里作为存在性邻居出现。这句话不是装配密钥流的步骤，也不是分组密码的设计图。路径长度回答的是这句定义有多贵。

它证明了什么，没有覆盖什么

它证明了：若存在长度翻倍、自身落在多项式时间里、并且对多项式测试者不可区分于真随机串的发生器，则存在多项式时间可评估的函数族，使任何概率多项式时间的观察者——即使自适应地选定输入并收回函数值——仍不能把族中均匀抽出的一员与均匀随机函数分开。它把「随机函数」从一张写不完的真值表改写成可高效评估的短种子对象，并把姚期智的不可区分口径从字符串搬到神谕。发生器负责一层孩子像随机，树负责一层一层走到叶子，混合负责把函数上的缝送回某一层发生器。短种子的函数族与全部函数在信息论上差得很远，计算上却可以分不开。

它没有证明单向函数存在，也没有构造发生器，更没有裁决 $P$ 对 $NP$。十六页是条件句：若这种字符串发生器在那儿，可询问的函数族就会跟着在那儿。它没有给出布卢姆–米卡利那种钉在离散对数上的硬核，也没有给出戈德赖希–列文那种对任意单向函数都成立的内积硬核，更没有从任意单向函数造出发生器——那是 1989 年西雅图的邻居。它没有覆盖拉兹博罗夫–鲁迪奇的自然证明：那十二页把本页的对象当成已经在那儿的伪随机函数，去挡一类电路下界手续。它没有给出伪随机置换，也没有把函数改写成分组密码。密钥流装配与线上区分器同样不在。限度还写在评估次数上：路径有多长，发生器就要调用多少次。对照属于 计算复杂性 地图与 密码学基础 总览。本页把铺树写成一次条件句。

跨域连接

  • 戈德瓦塞尔–米卡利一九八四年概率加密：那三十页把密文总体写成多项式不可区分，作者里没有戈德赖希，对象是传消息。本页把不可区分从密文搬到可询问的函数。两人重叠、年份相邻，封面却分别是公钥编码与短种子函数族。把 1986 年听成又一篇概率加密，会把神谕询问收成一次密文抽样。
  • 布卢姆–米卡利一九八四年论文：那十五页交出自身落在多项式时间里的比特发生器，燃料是离散对数上的左右半。本页不造发生器，只把长度翻倍的发生器铺成树。没有 1984 年的假硬币，1986 年少了燃料；没有本页的树，发生器仍停在字符串。把两篇听成一次印刷，会把比特源与函数族叠成一句。
  • 姚期智一九八二年陷门函数论文：芝加哥 FOCS 那十二页把计算不可区分写成密码学与发生器共用的装置，并给出任意单向置换上的发生器。本页继承「多项式测试者分不开」这一句，把测试者升级成选定输入的神谕。把两篇听成已经铺好树，会把字符串发生器与函数发生器焊成一次页码。
  • 戈德赖希–列文一九八九年论文：那八页证明任意单向函数填充后都有内积硬核。本页假定发生器已经在那儿，并不讨论如何从单向函数抽出一比特。把 1986 年听成已经给出通用硬核，会把一次铺树收成一次对所有单向函数的定理。
  • 因帕利亚佐–列文–卢比一九八九年论文：那十三页从足够一般的单向函数交出多项式时间发生器。本页的条件句因此在后三年获得更宽的燃料。把 1986 年听成已经从任意单向函数造出函数族，会把一次「若有发生器」收成一次「若有单向函数」。
  • 拉兹博罗夫–鲁迪奇一九九七年论文：那十二页把本页的树当成对象，说明一条又宽广又可判定的组合性质一旦强到能挡住一般电路，就会变成伪随机函数的统计检验。本页提供被使用的那族函数，并不讨论电路下界。把自然证明听成 GGM 的别名，会把一次分类收成一次铺树。
  • 密码学基础：总览需要单向函数、发生器与计算不可区分。本页提供 1986 年把发生器焊成可询问函数的那一次：发生器负责一层像随机，树负责指数大表可随机访问，混合负责优势被送回字符串。它没有把种子写成步骤。
  • 戈德瓦塞尔–米卡利–拉科夫一九八五年论文：零知识把不可区分从对象总体搬到证明对话的文本上。1985 年钉住的是传证，作者里同样有戈德瓦塞尔与米卡利，对象却不是函数神谕。把零知识听成又一条密钥流，会把传证问题收成传函数值问题。

参考文献

  • Oded Goldreich, Shafi Goldwasser & Silvio Micali, "How to Construct Random Functions", Journal of the ACM 33(4), October 1986, pp. 792–807. DOI: 10.1145/6490.6503. —— 本文对象。
  • Oded Goldreich, Shafi Goldwasser & Silvio Micali, "How to Construct Random Functions", Proceedings of the 25th Annual Symposium on Foundations of Computer Science, Singer Island, Florida, 24–26 October 1984, pp. 464–479. DOI: 10.1109/SFCS.1984.715949. —— 会议前身，不是本页封面。
  • Oded Goldreich, Shafi Goldwasser & Silvio Micali, "How to Construct Random Functions", MIT/LCS/TM-244, Laboratory for Computer Science, Massachusetts Institute of Technology, November 1983. —— 更早的技术备忘录，不是期刊。
  • Oded Goldreich, Shafi Goldwasser & Silvio Micali, "On the Cryptographic Applications of Random Functions", Advances in Cryptology: Proceedings of CRYPTO 84, LNCS 196, Springer, 1985, pp. 276–288. DOI: 10.1007/3-540-39568-7_22. —— 同一装置的应用邻居。
  • Andrew C. Yao, "Theory and Application of Trapdoor Functions", Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982, pp. 80–91. DOI: 10.1109/SFCS.1982.45. —— 不可区分语言与发生器的先行文本。
  • Manuel Blum & Silvio Micali, "How to Generate Cryptographically Strong Sequences of Pseudorandom Bits", SIAM Journal on Computing 13(4), November 1984, pp. 850–864. DOI: 10.1137/0213053. —— 发生器的数论先行文本，不是本页的树。
  • Shafi Goldwasser & Silvio Micali, "Probabilistic Encryption", Journal of Computer and System Sciences 28(2), April 1984, pp. 270–299. DOI: 10.1016/0022-0000(84)90070-9. —— 作者重叠的加密邻居。
  • Shafi Goldwasser, Silvio Micali & Charles Rackoff, "The Knowledge Complexity of Interactive Proof-Systems", Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985, pp. 291–304. DOI: 10.1145/22145.22178. —— 把不可区分搬到证明对话。
  • Oded Goldreich & Leonid A. Levin, "A Hard-Core Predicate for all One-Way Functions", Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989, pp. 25–32. DOI: 10.1145/73007.73010. —— 后年邻居：任意单向函数上的内积硬核。
  • Russell Impagliazzo, Leonid A. Levin & Michael Luby, "Pseudo-random Generation from One-way Functions", Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989, pp. 12–24. DOI: 10.1145/73007.73009. —— 后年邻居：一般单向函数上的发生器。
  • Alexander A. Razborov & Steven Rudich, "Natural Proofs", Journal of Computer and System Sciences 55(1), 1997, pp. 24–35. DOI: 10.1006/jcss.1997.1494. —— 后年用法：把本页函数族当成对象。

延伸阅读

正文中引用本条 · 6