||
从噪音、参数及性能、安全性三个方面对BGV方案进行分析。
噪音问题:假设密文的噪音是E,对应的模是qj,则两个密文相加后噪音增长为2E,乘积后噪音增长近似为E2。然后进行密钥交换,噪音增长一个小的加法因子eswitch,噪音为E2+eswitch,再经过模交换噪音变为 (qj-1∕qj)•( E2 + eswitch) + escale。上述的每一步都要保证噪音小于界限,从而密文可以正确解密。例如加法、乘法和密钥交换后,噪音要小于qj∕2,模交换后噪音要小于qj-1∕2 。根据噪音的增长形势,可以设置各级模的大小以管理噪音。如果取qj∕qj-1≈E,则(qj-1∕qj)•( E2 + eswitch) + escale≈E,那么每次模交换后噪音被拉回到原来的大小。因此对于深度为L的电路,如果密文初始噪音是B(取自于错误高斯分布),则令最大的模qL≈BL+1,最小的模q0 > B(略大于B就可以),qj≈qj-1•B,那么该方案就可以执行深度为L的电路。这比以往只能执行次数为d 的电路来说,是极大地提升。
参数及性能:BGV方案的参数重点是设置阶梯模的大小,而模的大小与深度L和安全参数相关,同时还要满足上述的噪音条件约束,即每一次密文计算后,密文的噪音要小于其界限。阶梯模可以取为qj≈
。另外使用模交换技术要求密钥必须是短的,所以密钥必须取自错误高斯分布[47],对于LWE问题也有同样的结果[53]。性能方面,整个电路计算复杂度为
。密文的长度为
。如果最后额外再进行一次维数约减,可以进一步约减密文的大小,最终密文的长度可以与Regev05方案的密文长度相同,但是不能再进行同态计算了。如果上述层次全同态加密方案,再使用启动技术即可获得“纯”的全同态方案,电路的计算复杂度为
。
安全性:其安全性建立在理想格上的最短向量(SVP)问题,该问题可以量子规约到R-LWE问题。近似因子为: qL/B =。
1/1 | 闂傚倸鍊搁崐鎼佸磹閹间礁纾归柟闂寸绾惧湱鈧懓瀚崳纾嬨亹閹烘垹鍊炲銈嗗笒椤︿即寮查鍫熲拺闁告繂瀚埢澶愭煕濡灝浜圭紒顔肩墦瀹曞ジ鎮㈢粙鍨紟婵犳鍠楅〃鍛涘Δ鍛闁挎洖鍊归悡銉︾節闂堟稒锛嶆俊鎻掓憸缁辨帡鎮╅悜妯煎涧婵烇絽娲ら敃顏呬繆閸洖妞介柛鎰ㄦ櫆閺嗕即姊绘担鍛婃儓闁归攱鍨圭槐鐐存媴閸撳弶缍庨梺鎯х箺椤鐣锋径鎰厪濠电偛鐏濋崝婊堟煟濠靛嫬鐏叉慨濠冩そ閹兘寮堕幐搴敤闂備胶鎳撻崵鏍箯閿燂拷:1 | 濠电姷鏁告慨鐑藉极閸涘﹥鍙忛柣鎴濐潟閳ь剙鍊块幐濠冪珶閳哄绉€规洏鍔戝鍫曞箣閻欏懐骞㈤梻鍌欐祰椤鐣峰Ο琛℃灃婵炴垶纰嶉浠嬫煏閸繃鍟掗柡鍐ㄧ墛閺呮煡鏌涘☉鍗炲箺婵炲牊鐓″铏圭矙濞嗘儳鍓板銈嗗灥椤﹂潧顕f繝姘櫜闁告稑鍊婚崰搴ㄥ煝鎼淬劌绠氱憸搴敊閸曨垱鐓涘璺烘濞呭棛绱掔拠鑼妞ゎ偄绻橀幖鍦喆閸曨偆锛忛梻渚€娼ф灙闁稿孩鐓¢幃鐢稿閵堝棌鎷洪梺鑽ゅ枑濠㈡ê鈻撻埡鍛厵闁告垯鍊栫€氾拷 | 濠电姷鏁告慨鐑藉极閸涘﹥鍙忛柣鎴f閺嬩線鏌熼梻瀵割槮缁炬儳顭烽弻锝夊箛椤掍焦鍎撻梺鎼炲妼閸婂潡寮诲☉銏╂晝闁挎繂妫涢ˇ銉х磽娴e搫小闁告濞婂濠氭偄閸忓皷鎷婚柣搴f暩鏋┑鈥茬矙濮婃椽宕崟顒€娅ょ紓浣筋嚙閻楁挸顕f繝姘╅柕澶堝灪閺傗偓闂備胶纭堕崜婵嬫晪缂備焦鍔栭惄顖氼潖濞差亜宸濆┑鐘插閻g兘鎮楅崗澶婁壕闂佸綊妫跨粈浣虹不閺嶃劋绻嗛柕鍫濆€告禍楣冩⒑鐎圭姵顥夋い锔诲灦閸┿垹顓奸崱妯肩Ф闂侀潧臎閸涱垰甯掔紓鍌氬€风粈渚€宕愰崫銉х煋闁圭虎鍠撻崑鎴澝归崗鍏肩稇闂佸崬娲弻锝夊棘閹稿孩鍎撻悗娈垮枟婵炲﹤顫忕紒妯诲闁惧繒鎳撶粭鈥斥攽閻愭彃绾ч柣妤冨Т閻g兘骞囬弶鎸庡祶濡炪倖鎸荤粙鎴炵閻愵剚鍙忔俊顖滃帶娴滈箖鎮楀鐐 | 濠电姷鏁告慨鐑藉极閸涘﹥鍙忛柣鎴f閺嬩線鏌熼梻瀵割槮缁炬儳顭烽弻锝夊箛椤掍焦鍎撻梺鎼炲妼閸婂潡寮诲☉銏╂晝闁挎繂妫涢ˇ銉х磽娴e搫小闁告濞婂濠氭偄閸忓皷鎷婚柣搴$仛閻℃洜绮eΔ鍛拺閺夌偞澹嗛ˇ锕傛倵濮橆偄宓嗙€殿喛顕ч埥澶愬閻樻彃绁梻渚€娼ф灙闁稿氦浜划缁樼節濮橆厸鎷洪梺鍛婄☉楗潙鈻撻弴鐘亾閸忓浜鹃梺褰掓?缁€浣虹不閺嶃劋绻嗛柕鍫濆€告禍楣冩⒑鐎圭姵顥夋い锔诲灦閸┿垹顓奸崱妯肩Ф闂侀潧臎閸涱垰甯掔紓鍌氬€风粈渚€宕愰崫銉х煋闁圭虎鍠撻崑鎴澝归崗鍏肩稇闂佸崬娲弻锝夊棘閹稿孩鍎撻悗娈垮枟婵炲﹤顫忕紒妯诲闁惧繒鎳撶粭鈥斥攽閻愭彃绾ч柣妤冨Т閻g兘骞囬弶鎸庡祶濡炪倖鎸荤粙鎴炵閻愵剚鍙忔俊顖滃帶娴滈箖鎮楀鐐 | 闂傚倸鍊搁崐鎼佸磹閹间礁纾归柟闂寸绾剧懓顪冪€n亝鎹i柣顓炴閵嗘帒顫濋敐鍛婵°倗濮烽崑鐐烘偋閻樻眹鈧線寮撮姀鈩冩珕闂佽姤锚椤︻喚绱旈弴鐔虹瘈闁汇垽娼у瓭闂佹寧娲忛崐婵嬪箖瑜斿畷鍗炩枎韫囷絾顥¢梺鑽ゅТ濞诧妇绮婇幘顔肩哗濞寸姴顑嗛悡鐔镐繆椤栨碍鎯堢紒鐙欏洦鐓欓柛蹇曞帶婵牊绻涢懝閭﹀殭闁宠鍨归埀顒婄秵閸嬧偓闁归攱妞介弻锝夋偐閸忓懓鍩呴梺鍛婃煥閼活垶鍩㈠澶婄疀闁绘鐗忛崢鐢告⒑閸涘﹤鐏熼柛濠冪墱閳ь剚鐔幏锟� | 闂傚倸鍊搁崐鎼佸磹閹间礁纾圭€瑰嫭鍣磋ぐ鎺戠倞鐟滃繘寮抽敃鍌涚厱妞ゎ厽鍨垫禍婵嬫煕濞嗗繒绠婚柡宀€鍠撶槐鎺楀閻樺磭浜紓鍌欒兌婵箖锝炴径鎰﹂柛鏇ㄥ灠缁犳盯鏌涢锝嗙妞ゅ骸绉瑰铏圭矙濞嗘儳鍓炬繛瀛樼矤娴滎亜顕g拠娴嬫闁靛繒濮堥妸锔轰簻闁哄倸鐏濈紞鏍ㄦ叏鐟欏嫷娈滈柟顔煎槻楗即宕ㄩ褎姣夐梺姹囧焺閸ㄩ亶銆冩繝鍌ゅ殨闁哄被鍎辩粻鐟懊归敐鍛础闁告瑥妫濆铏圭磼濡崵顦ラ梺绋匡工濠€閬嶅焵椤掍胶鍟查柟鍑ゆ嫹 |
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2025-3-18 18:47
Powered by ScienceNet.cn
Copyright © 2007-2025 中国科学报社