自己的沙场:全同态加密研究分享 http://blog.sciencenet.cn/u/chzg99 不要对我说生命中无聊的事,不要对我说失败是命运的事。

博文

全同态加密释疑(五):为什么是电路观点

已有 5644 次阅读 2013-12-8 21:38 |个人分类:全同态|系统分类:科研笔记|关键词:安全性,落脚点,密码学,style,加密| style, 安全性, 密码学, 加密, 落脚点

全同态加密释疑(五):为什么是电路观点

陈智罡

 

这个问题是许多刚接触全同态加密研究者困惑的一个问题。

 

也许初学者以为密码学都是基于数论观点的,其实真正的密码学的灵魂落脚点是计算复杂度。密码学中的所有方案必须要依赖于一个数学难题,这是其安全性所在的根本。问题有多难?拿什么来衡量?答曰:计算复杂度。所以有一本很有名但是很枯涩难懂的一本著名密码学理论书:《Foundations of Cryptography》(Oded Goldreich著),里面深刻阐述了这一观点。

 

但是电路观点在密码学中的方案由来已久。例如,姚期智的论文“How to generate and exchange secrets”就是通过布尔电路观点构造安全函数计算,产生了著名的概念“garbled circuit”

 

强调一下,电路观点是一种计算复杂度的计算模型,用途是衡量解决问题所需要的资源,例如时间、存储量等。在电路计算模型下,有使用的gate的数量,电路的深度等。

 

为什么要使用电路观点来构造密码学中的方案?

   

采用电路计算模型的原因是电路模型需要“接触“到所有的输入数据,因而不会泄露任何信息,所以传统的安全计算都是采用电路模型的。尽管电路模型非常强大(等价于图灵机),但在某些方面图灵机计算模型要比电路模型的计算效率要高(例如折半查找)。例如在存储有n个数据项的数据库中,若使用标准的安全计算协议,首先把函数表示成电路进行计算,该协议的复杂度是Ω(n)。但是若使用图灵机计算模型下的二分查找,时间复杂度为О(logn)

电路模型下,算法的性能是用最坏情况下的性能来衡量的。其原因是图灵机算法转换成电路模型下的算法后,该算法工作在无循环的算法结构下,这使得电路模型要考虑所有出现的情况,也就是最坏情况下的运行时间。简单的说,如果一个算法在实践中绝大多数的实例都是运行在多项式时间下,但是对于极少数实例时运行在指数时间下,那么电路模型的计算时间就是指数时间。

 

所以任何东西,此消彼长,都要付出代价的。

 

对于所有的全同态加密、基于属性加密、通用函数的两方及多方安全计算协议、对于通用函数的函数加密,都是采用的电路观点。

 

能否对于电路模型下的密码学方案,让其享受图灵机模型下的时间而不是最坏情况下的时间呢?

 

好消息:Shafi Goldwasser等人在今年的美密会上“Howto Run Turing Machines on Encrypted Data “论文中,提出了将一个图灵机算法编译成一个工作在电路上的算法(该算法可以看成被加密了),该算法运行在密文下,该电路上的算法的计算时间是图灵机模型下的算法计算时间。针对全同态加密方案、基于属性的加密方案、函数加密方案都进行了这种形式的尝试。

 

坏消息:这个被加密的运行在电路上的算法,泄露了图灵机模型下的算法计算时间。而且这些方案都是概念上的证明,并不是真正的一个实在的方案。所以意义并不大。

 

 

 

 




http://blog.sciencenet.cn/blog-411071-748173.html

上一篇:全同态加密释疑(四):转折点:LWE上全同态加密的诞生
下一篇:英国访问学者答疑(1)—邀请函篇

3 孙爽 邱嘉文 杨渺

该博文允许注册用户评论 请点击登录 评论 (6 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备14006957 )

GMT+8, 2018-6-23 06:53

Powered by ScienceNet.cn

Copyright © 2007-2017 中国科学报社

返回顶部