朗格朗日插值多項(xiàng)式在安全多方計(jì)算中的應(yīng)用研究

葛永

（銅陵市委黨校，安徽　銅陵　244000）

朗格朗日插值多項(xiàng)式在安全多方計(jì)算中的應(yīng)用研究

葛永

（銅陵市委黨校，安徽銅陵244000）

拉格朗日插值法是一種很實(shí)用的插值方法，在沒(méi)有涉及隱私保護(hù)的情況下，利用拉格朗日插值法求解插值多項(xiàng)式很容易，一但涉及到安全的隱私保護(hù)計(jì)算，求解朗格朗日插值多項(xiàng)式就會(huì)變得非常復(fù)雜，本文從安全多方計(jì)算的協(xié)議研究出發(fā)，在保護(hù)各方隱私信息的情況下，利用門(mén)限共享和同態(tài)加密技術(shù)給出了安全的求解朗格朗日插值多項(xiàng)式的協(xié)議.

門(mén)限共享；同態(tài)加密；安全多方計(jì)算；拉格朗日插值

安全多方計(jì)算（Secure Multi-party Computation，SMC）作為目前一個(gè)熱門(mén)研究方向，被廣泛的應(yīng)用于軍事領(lǐng)、經(jīng)濟(jì)領(lǐng)域、幾何計(jì)算的等領(lǐng)域.而作為數(shù)值計(jì)算之一的安全的拉格朗日插值計(jì)算，有著極其重要的研究目的與價(jià)值，被廣泛的應(yīng)用在現(xiàn)實(shí)生活的實(shí)用場(chǎng)景中.

1　安全多方計(jì)算模型與安全需求

1.1安全多方計(jì)算模型

安全多方計(jì)算可以抽象概括成如下數(shù)學(xué)模型：協(xié)議的n個(gè)參與方（）需要共同執(zhí)行函數(shù)，要求函數(shù)計(jì)算過(guò)程中，任意的參與者（i）只知道自己的輸入信息并且自己信息也不能透露給被其他參與方，計(jì)算結(jié)束后，每一方都知道函數(shù)的輸出結(jié)果.

安全多方計(jì)算模型一般分為兩種模型：半誠(chéng)實(shí)模型與惡意模型.

在惡意模型中設(shè)計(jì)安全多方計(jì)算協(xié)議比半誠(chéng)實(shí)模型下安全多方計(jì)算協(xié)議的設(shè)計(jì)困難的多，如果有惡意參與者參與協(xié)議的執(zhí)行中，大多數(shù)情況下的協(xié)議是不可能得到正確結(jié)果的.如要保證在惡意模型中多方計(jì)算協(xié)議能得到正確的結(jié)果，則需要使用較多、較復(fù)雜的密碼學(xué)技術(shù).因此本文研究設(shè)計(jì)安全多方計(jì)算協(xié)議是建立在半誠(chéng)實(shí)模型下的.

1.2安全多方計(jì)算的安全需求

1.2.1安全性：參與協(xié)議的任何一方除了知道自己的信息外，對(duì)其他各方的信息一無(wú)所知.只能從自己的輸入、中間結(jié)果及輸出中去推其他各方的信息.

1.2.2正確性：設(shè)計(jì)的協(xié)議要確保任意一方的輸出都是正確的，滿(mǎn)足需求.

2　保護(hù)私有信息的拉格朗日插值協(xié)議

拉格朗日插值法是一種很實(shí)用的插值方法，廣泛的應(yīng)用在在工業(yè)、商業(yè)、軍事、工程機(jī)械設(shè)計(jì)與制造領(lǐng)域，在動(dòng)態(tài)秘鑰生成方面都有著及其重要的應(yīng)用.在沒(méi)有涉及隱私保護(hù)的情況下，利用拉格朗日插值法求解插值多項(xiàng)式是很容易.但是已涉及隱私保護(hù)，問(wèn)題解決的難度就會(huì)隨之增加.本文提出了一個(gè)新問(wèn)題，即在保護(hù)各方私有信息的情況下，如何求解朗格朗日插值多項(xiàng)式問(wèn)題，并利用門(mén)限共享和同態(tài)加密給出了安全的解決方案.

2.1秘密共享

秘密共享是一種將秘密分割成若干份存儲(chǔ)的密碼技術(shù)，目的是防止秘密過(guò)于集中，以達(dá)到分散風(fēng)險(xiǎn)和保護(hù)信息安全的目的，是信息安全和數(shù)據(jù)保密中的一個(gè)重要手段，被廣泛的應(yīng)用在安全多方計(jì)算中.

秘密共享中最常見(jiàn)的就是門(mén)限共享方案.1979年Shamir提出一個(gè)稱(chēng)為（m，n）門(mén)限方案構(gòu)造方法.此方案是把一個(gè)信息分成n部分，每部分叫做它的“影子”或共享，它們中的任何m部分都能夠來(lái)重構(gòu)消息，這就叫（m，n）門(mén)限方案.

一種非常易于理解秘密共享（m，n）門(mén)限方案的是拉格朗日插值多項(xiàng)式方案.假設(shè)秘密k為n個(gè)人共享，且他們之中任意m個(gè)人可以相互協(xié)作獲取秘密k.可以通過(guò)如下方法來(lái)求解.首先生成比k大的隨機(jī)素?cái)?shù)p，然后生成m-1個(gè)隨機(jī)整數(shù)，，….，，每一個(gè)都比p小.定義在有限域上的多項(xiàng)式

F（x）=（）mod p

Step1：通過(guò)定義=F（）生成F的n個(gè)“影子”，這里每個(gè)都不同.

Step2：將[p，]交給n個(gè)秘密共享者的每一位，i對(duì)應(yīng)每個(gè)共享號(hào)碼.銷(xiāo)毀，，….，和k.

Step3：m個(gè)秘密共享者可以重構(gòu)秘密，秘密共享者構(gòu)造如下線(xiàn)性方程，=（）mod p，此線(xiàn)性方程組有m個(gè)未知數(shù)，，….，和k，所以m個(gè)秘密共享者可以通過(guò)構(gòu)造含有m個(gè)具有相同未知數(shù)的方程組來(lái)求解.

n個(gè)參與者中的任意m個(gè)參與者，出示他們的子秘密，從而得到m個(gè)點(diǎn)對(duì)，從而得到m個(gè)點(diǎn)對(duì)：（），（）…（）,這樣就可以重構(gòu)多項(xiàng)式F（x）和共享秘密k:；.

2.2同態(tài)加密

若存在明文空間一個(gè)二元運(yùn)算符⊕和密文空間一個(gè)二元運(yùn)算符·，滿(mǎn)足E(x⊕y)=E(x)·E(y)，稱(chēng)其為同態(tài)加密方案.其中，x和y表示被加密的信息.

如果E同時(shí)為加法同態(tài)、減法同態(tài)、乘法同態(tài)和除法同態(tài)則稱(chēng)其為算術(shù)同態(tài).

2.3問(wèn)題描述

n方有n個(gè)點(diǎn)（），（）…（），在保護(hù)各方隱私的情況下，秘密協(xié)作計(jì)算一個(gè)插值公式f(x)，使得所有的（）均滿(mǎn)足=f().

2.4保護(hù)私有信息的拉格朗日插值協(xié)議

協(xié)議執(zhí)行前，n方協(xié)商一個(gè)算術(shù)同態(tài)加密算法E和解密算法D.

Step1：方分別使用同態(tài)加密算法E，加密各自的（），并將加密后的E（）以廣播的形式發(fā)送給其他各方；

Step3:方計(jì)算=，并將計(jì)算結(jié)果以廣播的形式發(fā)送給其他各方.

Step4：方計(jì)算,f(x)=.

2.5協(xié)議分析

2.5.1安全性分析

因?yàn)閰f(xié)議的安全性是建立在算術(shù)同態(tài)加密的基礎(chǔ)之上的，方除了知道自己的私有信息外，不知道其他各方的任何信息，所以此協(xié)議是安全的.

2.5.2正確性分析

由門(mén)限共享方案可知，任何小于n方的參與者都不能計(jì)算出插值公式f(x)，使得所有的（）均滿(mǎn)足=f().由拉格朗日插值多項(xiàng)式公式知：，而通過(guò)協(xié)議計(jì)算的結(jié)果：f(x)=====，因此此協(xié)議是正確的.

2.5.3復(fù)雜性分析

此協(xié)議用了n次同態(tài)加密算法，時(shí)間復(fù)雜度為O(n2).

3　小結(jié)

本文設(shè)計(jì)的安全多方計(jì)算協(xié)議的不足之處均是建立在半誠(chéng)實(shí)模型下的研究，惡意模型下的方程求解協(xié)議設(shè)計(jì)研究比較復(fù)雜，將在后續(xù)的工作中進(jìn)行探討.

〔1〕Wenliang Du and Zhijun Zhan.A practical approach to solve secre multi-party computation problems[C].//Proceedings of the 2002 Workshop on New Secure Paradigms,Virginia Beach,Virginia,USA,2002:127-135.

〔2〕Blakley G R.Safeguarding cryptographic keys [C]//Proceedingsofthe nationalComputer Conference American Federation of Information Procession Societies.1979,48:313-317.

〔3〕石潤(rùn)華，仲紅，劉黃生.動(dòng)態(tài)的多重秘密共享方案[J].計(jì)算機(jī)工程，2008,34（9）:170-173.

〔4〕曹天杰，張永平，汪楚嬌.安全協(xié)議[M].北京：北京郵電大學(xué)出版社，2009.

〔5〕黃云清.數(shù)值計(jì)算方法[M].北京：科學(xué)出版社，2010.

TP309

A

1673-260X（2016）09-0015-02

2016-05-21