iO(7)构造iO的最后一步

admin 2022年7月27日20:14:47安全闲碎评论0 views1949字阅读6分29秒阅读模式
有了Weakly Compact Sublinear FE 就可以构造iO了由于构造基于的是图灵机的Random Encodings,因此我们假设我们构造中涉及到的所有电路都是P一致电路(P一致电路是可以由图灵机多项式时间内生成的电路,这类电路可以和多项式运行时间的图灵机相互转化),事实上从实用角度出发也确实没有必要考虑那些存在但无法在多项式时间内构造出来的电路。

RE for TMs 的效率要求

我们考虑图灵机的RE,对于一个图灵机,图灵机的输入以及图灵机运行时间的上限,根据可以高效地计算得到。我们把生成的过程叫做Encode,根据得到的过程叫做Decode,Decode的时间复杂度应当是。图灵机RE的效率定义和FE的效率定义是类似的。

Compact

Encode的时间复杂度为

Sublinear Compact

Encode的时间复杂度为

Weakly Sublinear Compact

Encode的时间复杂度为,输出长度为

Succinct

Encode的时间复杂度为,其中是图灵机输出的长度。

RE的安全性要求

RE的安全性至少要求其至少能够保护输入的信息,亦即,再某些更强的安全性定义里面,还会要求保护图灵机的信息,即;我们只需要较弱的RE。

iO(7)构造iO的最后一步
构造路线

FE=>RE

假设我们有一个FE方案和一个通用电路。设(看上去这个算法没有使用到,但是的大小会影响这个计算过程的时间复杂度,输出长度等,这就好比FE的加密算法的复杂度往往会和FE所能支持的最大电路的大小挂钩),。因为直接调用了,因此这个FE=>RE的构造是没有效率损失的(对于功能一致的图灵机和电路,图灵机的运行时间和电路的大小是对应的,至多是关于的多项式,也至多是关于的多项式)。

由于我们已经有了Succinct FE和Weakly Sublinear Compact FE,通过这个构造,我们就能得到Succinct RE和Weakly Sublinear Compact RE。虽然这步构造用到了CRS,我们一会就将看到,最终的iO是不带CRS的(在介绍Split-FHE构造的时候,我们提到了Pass等人将原本构造中的RO改为了CRS,同样的,这一做法也不会导致最终得到的iO带有CRS)。

RE的组合

是Succinct RE,是Weakly Sublinear Compact RE,我们通过将它们进行组合构造一个Sublinear Compact RE。这个计算过程本身可以视为关于输入的一个图灵机,记为记为

由于是先后分别使用了,通过使用的时间复杂度,输出长度为(由Weakly Sublinear Compact 可得);接着调用时,由于此时输出长度由下降到了,因此时间复杂度为(由于Succinct的时间复杂性和输出长度相关),从而得到了Sublinear Compact RE。

Sublinear Compact RE=>iO

此处的构造依旧采用类似GGM的构造;假设电路的输入长度为,则GGM树的高度为,树的每个节点都是一个图灵机的RE,这个图灵机没有输入,我们用来表示这些图灵机,是一串01串,是输入的子串,长度为(根节点对应图灵机中的是空串,记为)。如果图灵机位于树的层,那么图灵机会输出;否则,图灵机会输出,由RE的安全性,这个构造的正确性是显然的。

下图展示了一个输入长度为2的简单电路的iO构造。

下面我们说明为什么至少需要Sublinear Compact的RE。我们可以采用反证,令GGM树中的每个图灵机的运行时间均不超过是一个多项式,是输入长度;假设GGM树种采用的RE不是Sublinear Compact的,即的时间复杂度至少为。由于父节点的图灵机的功能是生成两个子节点的图灵机的RE,因此父节点图灵机的运行时间是,根据的定义,我们有,移项得,一个多项式始终不大于一个常数是不可能的,因此至少需要Sublinear Compact的RE才能构造iO。

iO(7)构造iO的最后一步
构造iO的类GGM树

小结

至此,circularity-based iO的主要工作就大体介绍完毕了,LPN-based iO的相关工作的介绍将会在一段时间后更新。

参考文献

 Huijia Lin, Rafael Pass, Karn Seth, and Sidharth Telang. Output-compressing randomized encodings and applications. 2015.

 Romain Gay and Rafael Pass. Indistinguishability obfuscation from circular security. Cryptology ePrint Archive, Report 2020/1010, 2020.


原文始发于微信公众号(上海交大密码系统安全实验室):iO(7)构造iO的最后一步

特别标注: 本站(CN-SEC.COM)所有文章仅供技术研究,若将其信息做其他用途,由用户承担全部法律及连带责任,本站不承担任何法律及连带责任,请遵守中华人民共和国安全法.
  • 我的微信
  • 微信扫一扫
  • weinxin
  • 我的微信公众号
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2022年7月27日20:14:47
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                  iO(7)构造iO的最后一步 http://cn-sec.com/archives/1082873.html

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: