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

Luby–Rackoff 1988：伪随机函数怎样三轮费斯托变成询问下仍像随机的置换

How to Construct Pseudorandom Permutations from Pseudorandom Functions

Luby–Rackoff伪随机置换费斯托网络伪随机函数超伪随机SIAM 1988

1988 年 4 月，《SIAM Journal on Computing》第 17 卷第 2 期刊出迈克尔·卢比（Michael Luby）与查尔斯·拉科夫（Charles Rackoff）的《How to Construct Pseudorandom Permutations from Pseudorandom Functions》，页码 373 至 386。DOI 为 10.1137/0217022。期刊把两位作者单位都印作多伦多大学。本页的对象是这份已印行的十四页期刊论文：从一族多项式时间可评估、对选定输入的多项式观察者仍像均匀随机函数的函数出发，用三轮独立的费斯托（Feistel）变换交出一族可逆置换；观察者即使自适应地点名输入、收回输出，仍然不能把它与均匀随机置换分开。四轮则挡住同时拿到逆映射的观察者。课堂所称「Luby–Rackoff」，封面钉在这份 SIAM 文本上。它不是人物评传，也不是分组密码说明书。

封面是 1988 年这份十四页，不是 1986 年 5 月 28 日至 30 日在加州伯克利举行的第十八届 ACM 计算理论年会（STOC）会议录页码 356 至 363 的先行本。那一篇标题是《Pseudo-random Permutation Generators and Cryptographic Composition》，DOI 为 10.1145/12130.12167，ISBN 为 0-89791-193-8。八页摘要已经写出从函数发生器到可逆置换发生器的费斯托合成，并另证部分安全的置换发生器在密码学合成下会更安全；期刊却把标题收到「怎样从伪随机函数构造伪随机置换」。把「一九八六年那篇伪随机置换」收成一句，会把会议摘要与期刊定义焊成一次页码。

它不是 1986 年 10 月《Journal of the ACM》第 33 卷第 4 期页码 792 至 807 的戈德赖希–戈德瓦塞尔–米卡利随机函数论文，DOI 为 10.1145/6490.6503。那十六页问的是长度翻倍发生器怎样铺成可询问的函数族；产品是函数，不必可逆。本页把已经造好的伪随机函数当成燃料，产品是置换。把两篇听成一次印刷，会把树与轮焊成一句。它也不是 1985 年 5 月普罗维登斯第十七届 STOC 页码 291 至 304 的戈德瓦塞尔–米卡利–拉科夫交互证明摘要。那十四页问的是证明对话泄露了多少额外知识，作者名单里同样有拉科夫，对象却是传证，不是把函数改写成置换。它不是 1984 年 4 月《计算机与系统科学杂志》第 28 卷第 2 期页码 270 至 299 的戈德瓦塞尔–米卡利概率加密，也不是同年 11 月《SIAM Journal on Computing》第 13 卷第 4 期页码 850 至 864 的布卢姆–米卡利伪随机比特论文，更不是姚期智 1982 年芝加哥 FOCS 页码 80 至 91 的陷门函数论文。前两篇谈密文与假硬币，后一篇谈计算不可区分与发生器；本页假定函数族已经在那儿。它更不是 1989 年西雅图 STOC 页码 12 至 24 的因帕利亚佐–列文–卢比论文。那十三页问的是一般单向函数怎样交出发生器，作者名单里同样有卢比，封面却不是三轮费斯托。本页不提供如何装配分组密码、如何选取轮密钥、如何去攻一台已部署密码的步骤。

它不是 密码学基础 总览，也不是 加密基础 的产品地图。总览已经把伪随机置换收成一格；本页只抽出 1988 年这一枚钉子。它不是数据加密标准或高级加密标准的规格书。十六轮、替换盒、密钥编制表都不在这十四页里。它不是 随机算法 总览，也不是 计算复杂性 的 $P$ 对 $NP$ 地图。十四页里被钉住的是左右半、三轮对四轮，以及只问正向与连逆映射一起问的两种观察者。

破除误解：伪随机置换不是已经造好的分组密码，三轮也不等于已经给出选择密文

第一种最快的读法是：把卢比–拉科夫听成 1986 年那十六页随机函数，或听成 1985 年那十四页交互证明。戈德赖希、戈德瓦塞尔与米卡利 1986 年合写的是函数：短种子决定的对应，在允许对方自己点名输入的多项式观察者面前，仍须与均匀随机函数不可区分。戈德瓦塞尔、米卡利与拉科夫 1985 年合写的是传证。卢比与拉科夫 1988 年合写的是另一件东西：已经像随机的函数，经过有限轮左右对调与异或，交出已经像随机的可逆置换。STOC 先行本与期刊共享作者与装置，标题、页码与 DOI 却不是同一印刷。把三份封面收成一句，会把函数、零知识与置换焊成一次页码。

第二层误解把标题听成已经造出真正的随机置换，或听成一份把费斯托焊进产品的分组密码。均匀随机置换的真值表对输入长度是指数。十四页交出的是短密钥索引的一小族，正向与逆向评估都必须落在多项式时间里。统计上这族置换的支撑集相对全部置换小得可以忽略。多项式观察者看不见整张表，只能按自己选定的输入要值。被证明的是计算不可区分，不是概率恒等式。数据加密标准用十六轮费斯托与固定替换盒；高级加密标准用替换–置换网络，不是费斯托。把本页听成其中任何一份规格，会把一次复杂性陈述收成一次产品说明书。

第三层误解把「三轮足够」听成已经挡住所有观察者，或听成只要再加一轮就得到一份可部署的密码。原文把观察者分成两档。第一档只拿到正向神谕，自适应地点名输入、收回输出；三轮独立轮函数已经足够，使多项式观察者分不开这族置换与均匀随机置换。第二档同时拿到逆向神谕，相当于选择密文风格的询问；三轮不够，四轮才够。两轮在第一档里就已经失败：左右半之间还留着一条多项式观察者能写下的代数关系。轮数是观察者模型上的阈值，不是密钥长度表，也不是对线上系统的检测步骤。

第四层误解把这里的函数听成已经证明单向函数存在，或听成 1989 年那一组「任意单向函数交出发生器」的印刷。十四页是条件句：若存在对多项式询问者不可区分于均匀随机函数的函数族，则三轮费斯托交出对多项式正向询问者不可区分于均匀随机置换的可逆置换族。它没有构造函数族。戈德赖希–戈德瓦塞尔–米卡利把函数钉在长度翻倍发生器上，布卢姆–米卡利与姚期智把发生器钉在硬核与单向置换上，因帕利亚佐–列文–卢比才把发生器收到一般单向函数。本页停在「函数已经在那儿」这一侧。它也没有把合成定理写成封面：先行本另证部分安全的置换发生器在合成下更安全，期刊标题却把钉子钉在函数变置换。

左右半、费斯托轮，以及三轮与四轮

装置从「什么样的随机置换」开始，而不是从一张密钥编制表开始。真随机置换把每一个长度为 $2n$ 的比特串一对一地送到另一个同样长度的串，正向与逆向都均匀。要写下全部对应，表的长度对 $n$ 是指数。多项式时间的观察者没有这种全能。姚期智已经把「所有多项式时间统计测试都分不开」写成字符串上的计算不可区分；戈德赖希、戈德瓦塞尔与米卡利把同一口径搬到可询问的函数。本页再搬一次：观察者得到的不是一段写死的比特，而是一枚置换神谕。自己选定输入，收回输出，再决定下一个输入。通过所有这样的多项式测试，被他们称作伪随机的可逆置换族。

燃料是一族伪随机函数。每一枚密钥决定一个从 $n$ 比特到 $n$ 比特的函数，评估落在多项式时间里；任何概率多项式时间的观察者，即使自适应地点名输入，仍不能把这族函数与均匀随机函数分开。函数本身不是本页构造的对象，而被当作已经存在的黑箱。戈德赖希–戈德瓦塞尔–米卡利提供的是这类黑箱的先行文本；本页问的是黑箱够不够铺出一整族可逆置换。

一轮费斯托把长度为 $2n$ 的串从中剖开。左半 $n$ 比特记作 $L$，右半 $n$ 比特记作 $R$。一轮之后，新的左半是旧的右半，新的右半是旧的左半与轮函数在旧右半上取值的按位异或。轮函数不需要自己可逆。异或是对合，左右对调可以退回去，所以每一轮都是置换，整串轮次也是置换。给定轮函数，逆向评估只是把轮次倒过来走。没有人需要先写出 22n2^{2n} 张表：评估一条输入只调用与轮数相同次数的函数。把「铺成置换」听成必须先写出全部对应，会把一次路径评估收成一次指数表。

两轮不够。若两个输入的右半相同，两轮之后输出左半的异或等于输入左半的异或。均匀随机置换几乎不会把这条关系交出来。多项式观察者因此能把两轮与随机置换分开。这句话是定义上的反例，说明「像函数」加两次左右对调仍可能留下可见的代数缝，不是一份按查询还原密钥的日程。

三轮挡住只问正向的多项式观察者。证明分两步，都是存在性归约。第一步把三枚独立的伪随机轮函数换成三枚真随机函数：若观察者仍能分开，缝被送回某一枚伪随机函数，与燃料假设矛盾。第二步证明，三枚真随机轮函数驱动的费斯托，与均匀随机置换对多项式多次正向询问仍不可区分。缝出现在右半相撞的那些询问上，次数对 $n$ 是可忽略的。混合说明置换上的优势可以翻译成函数上的优势，不是一份按轮询问去还原种子的日程。自适应询问已经含在观察者模型里。十四页证明翻译手续存在。本页不把混合改写成课堂实验。

四轮挡住同时问逆向的观察者。原文把这一档称作超伪随机：神谕里既有正向门，也有逆向门。三轮在这一档里失败。观察者若既能送入明文风格的输入，又能送入密文风格的输入并收回原像，三轮仍留下可检验的关系。第四轮把这条缝盖住。选择明文风格对应第一档，选择密文风格对应第二档。两种说法都是观察者模型上的标签，不是装配密钥流的步骤，也不是分组密码的设计图。

效率写在模型自己的粒度上。评估代价与轮数成正比，因为每多一轮就多调用一次函数。三轮与四轮回答的是这句定义有多贵，不是一份生产用的轮数表。十四页也勾画了理论后果：共享一枚短密钥，在多项式观察者面前可以像共享一张巨大的随机置换表。私钥分组加密在原文里作为存在性邻居出现，并标明相同明文块会交出相同密文块这一条可见的重复。这句话不是装配密码的步骤。

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

它证明了：若存在多项式时间可评估、并且对自适应多项式询问者不可区分于均匀随机函数的函数族，则三轮独立费斯托交出多项式时间可逆的置换族，使任何只拿到正向神谕的概率多项式时间观察者，仍不能把族中均匀抽出的一员与均匀随机置换分开。四轮独立费斯托进一步挡住同时拿到逆向神谕的观察者。它把「随机置换」从一张写不完的真值表改写成可高效评估、可高效求逆的短密钥对象，并把函数上的不可区分口径搬到置换上。函数负责每一轮的右半像随机，费斯托负责左右对调交出置换，混合负责把置换上的缝送回某一轮函数。短密钥的置换族与全部置换在信息论上差得很远，计算上却可以分不开。

它没有证明单向函数存在，也没有构造伪随机函数，更没有裁决 $P$ 对 $NP$。十四页是条件句：若这种函数族在那儿，可询问的置换族就会跟着在那儿。它没有给出戈德赖希–戈德瓦塞尔–米卡利那种把发生器铺成树的手续，也没有给出布卢姆–米卡利那种钉在离散对数上的硬核，更没有从任意单向函数造出发生器——那是 1989 年西雅图的邻居。它没有覆盖数据加密标准或高级加密标准的轮函数、替换盒与密钥编制。十六轮产品与四轮定理不是同一对象。它没有给出对已部署密码的区分步骤，也没有把超伪随机写成一份选择密文攻击日程。限度还写在轮数上：两轮在正向询问下已经失败，三轮在逆向询问下仍然失败。对照属于 计算复杂性 地图与 密码学基础 总览。本页把三轮与四轮写成一次条件句。

跨域连接

  • 戈德赖希–戈德瓦塞尔–米卡利一九八六年论文：那十六页把长度翻倍发生器铺成可询问的函数族，产品不必可逆。本页不造函数，只把已经像随机的函数送进三轮费斯托。没有 1986 年的树，1988 年少了燃料；没有本页的轮，函数仍停在不必可逆的一侧。把两篇听成一次印刷，会把树与轮叠成一句。
  • 戈德瓦塞尔–米卡利–拉科夫一九八五年论文：零知识把不可区分从对象总体搬到证明对话的文本上。1985 年钉住的是传证，作者里同样有拉科夫，对象却不是置换神谕。把零知识听成又一条密钥流，会把传证问题收成传置换值问题。
  • 因帕利亚佐–列文–卢比一九八九年论文：那十三页从足够一般的单向函数交出多项式时间发生器，作者名单里同样有卢比。本页假定函数已经在那儿，并不讨论如何从单向函数抽出发生器。把 1988 年听成已经从任意单向函数造出置换族，会把一次「若有函数」收成一次「若有单向函数」。
  • 姚期智一九八二年陷门函数论文：芝加哥 FOCS 那十二页把计算不可区分写成密码学与发生器共用的装置。本页继承「多项式测试者分不开」这一句，把测试者升级成选定输入的置换神谕，并再分成只问正向与连逆向一起问的两档。把两篇听成已经铺好轮，会把字符串发生器与置换发生器焊成一次页码。
  • 戈德瓦塞尔–米卡利一九八四年概率加密：那三十页把密文总体写成多项式不可区分，对象是传消息。本页把不可区分从密文搬到可询问、可求逆的置换。年份相邻，封面却分别是公钥编码与短密钥置换族。把 1988 年听成又一篇概率加密，会把神谕询问收成一次密文抽样。
  • 布卢姆–米卡利一九八四年论文：那十五页交出自身落在多项式时间里的比特发生器，燃料是离散对数上的左右半。本页的左右半是费斯托的剖分，不是硬核迭代。没有 1984 年的假硬币，函数族少了一级燃料；没有本页的轮，发生器仍停在字符串。
  • 密码学基础：总览需要单向函数、发生器、伪随机函数与计算不可区分。本页提供 1988 年把函数焊成可询问置换的那一次：函数负责一轮像随机，费斯托负责指数大表可随机访问且可逆，混合负责优势被送回函数。它没有把轮密钥写成步骤。
  • 加密基础：基础页把分组密码写成产品地图上的一格。本页提供的是「像随机置换」这句定义在观察者模型里要几轮才站住，不是一份已造好的密码。把三轮听成已经可以替换数据加密标准，会把一次条件句收成一次规格对照。

参考文献

  1. Michael Luby & Charles Rackoff, "How to Construct Pseudorandom Permutations from Pseudorandom Functions", SIAM Journal on Computing 17(2), April 1988, pp. 373–386. DOI: 10.1137/0217022. —— 本文对象。
  2. Michael Luby & Charles Rackoff, "Pseudo-random Permutation Generators and Cryptographic Composition", Proceedings of the 18th Annual ACM Symposium on Theory of Computing, Berkeley, California, 28–30 May 1986, pp. 356–363. DOI: 10.1145/12130.12167. ISBN: 0-89791-193-8. —— 会议前身，不是本页封面。
  3. 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. —— 伪随机函数的先行文本，本页的燃料，不是置换。
  4. 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. —— 不可区分语言与发生器的先行文本。
  5. 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. —— 发生器的数论先行文本，不是本页的轮。
  6. 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. —— 密文上的不可区分邻居。
  7. 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. —— 作者重叠的零知识邻居，不是费斯托。
  8. 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. —— 后年邻居：一般单向函数上的发生器。
  9. 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. —— 后年邻居：任意单向函数上的内积硬核。

延伸阅读

正文中引用本条 · 3