安全多方計(jì)算之GMW協(xié)議

一、背景

?????? 論文原文《How to play any mental game》。作者：Micali S, Goldreich O, Wigderson A. ?發(fā)表在：Proceedings of the Nineteenth ACM Symp on Theory of Computing, STOC.

?????? GMW協(xié)議可以同時(shí)適用在布爾電路和算術(shù)電路，支持n個(gè)參與方參與計(jì)算。GMW協(xié)議基于秘密共享技術(shù)對電路中的導(dǎo)線進(jìn)行秘密共享。

二、背景技術(shù)

XOR秘密共享屬于（n,n）門限秘密共享。假設(shè)一個(gè)秘密值為s，則選擇n-1個(gè)同比特長的隨機(jī)數(shù),計(jì)算。到就是秘密值的分享。恢復(fù)秘密值s只需計(jì)算即可。

1-out-of-4 OT協(xié)議，參與方之間需要執(zhí)行4選1OT協(xié)議，接收方從四個(gè)密文中選擇需要的密文，而發(fā)送方不知道接收方選擇了哪一個(gè)密文。

三、協(xié)議內(nèi)容

?????? GMW可以對三種運(yùn)算——NOT，XOR和AND運(yùn)算進(jìn)行evaluate。

兩個(gè)數(shù)據(jù)持有方對數(shù)據(jù)a，b進(jìn)行比特級秘密共享：，。將,分別發(fā)送給計(jì)算方。

對于NOT和XOR運(yùn)算，每個(gè)計(jì)算方只需在本地進(jìn)行計(jì)算即可。NOT運(yùn)算輸出的分享值為：；XOR運(yùn)算輸出的分享值為：。

對于AND運(yùn)算則需要兩兩計(jì)算方進(jìn)行交互。計(jì)算：

注意：這里的求和符號代表的是異或求和。根據(jù)上述公式，每一個(gè)計(jì)算方可以在本地計(jì)算。然后對于任意兩個(gè)計(jì)算方，，需要交互計(jì)算：。此時(shí)，需要執(zhí)行一個(gè)1-out-of-4 OT協(xié)議：

假設(shè)為OT協(xié)議發(fā)送方，為OT協(xié)議接收方。定義函數(shù)S：

選擇一個(gè)隨機(jī)數(shù)r，然后計(jì)算一個(gè)OT協(xié)議的秘密表:

于是，AND運(yùn)算的結(jié)果。根據(jù)自己的秘密分享值選擇表中相應(yīng)的值作為自己的輸出秘密分享值，保留r作為自己的輸出秘密分享值。這樣，在這一小輪中，得到的秘密分享值為r，得到的秘密分享值為。每個(gè)計(jì)算方兩兩交互后將得到的所有的值進(jìn)行異或求和就可以得到的值。然后每一個(gè)計(jì)算方就可以得到自己的秘密份額：。

總結(jié)

以上是生活随笔為你收集整理的安全多方计算之GMW协议的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。