一種基于二次剩余的拋擲硬幣方案

楊曉莉，左祥建

(陜西師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，陜西西安 710119)

一種基于二次剩余的拋擲硬幣方案

楊曉莉，左祥建

(陜西師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，陜西西安 710119)

硬幣拋擲在密碼學(xué)和現(xiàn)實(shí)生活中都有重要的應(yīng)用。比如籃球比賽或足球比賽，裁判用硬幣拋擲的正反來決定哪邊先開球。然后裁判拋擲硬幣，如果硬幣是正面，那么甲方從左往右攻;反之，乙方從左往右攻。這個(gè)實(shí)驗(yàn)就是一種簡單的硬幣拋擲協(xié)議。然而，對于不在同一地方的兩人來說，如何公平地拋擲硬幣，就是一個(gè)有待研究的問題了。研究了兩方拋擲硬幣的一個(gè)推廣問題—多方拋擲硬幣問題，構(gòu)造了這個(gè)問題的解決方案。該方案基于Goldwasser-Micali概率加密算法的異或同態(tài)性和因子分子的困難性，對多人拋擲硬幣的結(jié)果進(jìn)行異或運(yùn)算，實(shí)現(xiàn)了安全多方計(jì)算，保證了多人拋擲硬幣的安全性和公平性。并對該方案進(jìn)行了安全性分析和復(fù)雜度分析。

密碼學(xué);安全多方計(jì)算;硬幣拋擲;概率加密;異或同態(tài)性

0 引言

隨著互聯(lián)網(wǎng)的發(fā)展，不僅給人們的生活提供了便利，同時(shí)也帶來了不少麻煩，比如說個(gè)人信息泄漏、信息破壞、信息污染，這些都是信息安全問題［1-2］。信息安全問題是當(dāng)今社會談?wù)摰臒狳c(diǎn)問題之一。因此，解決信息安全問題是學(xué)者研究的重要問題。

密碼學(xué)中會遇到兩方比較猜測結(jié)果的問題，可是雙方都不想讓對方知道自己的信息，這就是密碼學(xué)和信息安全中的多方保密計(jì)算［3］，拋擲硬幣方案是安全多方計(jì)算的一個(gè)應(yīng)用特例。Blum在1982年通過調(diào)制解調(diào)器引入拋擲公平硬幣問題［4］，利用位比特協(xié)議解決了兩個(gè)人拋擲硬幣問題;Ben等在1990年提出了硬幣拋擲問題［5］;Lindell等在2003年提出兩方安全拋擲硬幣問題［6］;余堃也在2003年提出了公平硬幣拋擲協(xié)議［7］。但是這些協(xié)議僅限于兩方，沒有解決多方參與拋擲硬幣問題。

文中提出一種多方參與拋擲硬幣方案，此方案與兩方參與拋硬幣方案相比，具有普遍適用性，增加了游戲的趣味性，保證了多方參與拋擲硬幣的安全性。

全同態(tài)加密是指在2009年IBM公司的克雷格·金特里(Craig Gentry)發(fā)表了一篇文章［8］，公布了一項(xiàng)關(guān)于密碼學(xué)的全新發(fā)現(xiàn):一項(xiàng)真正的突破。他發(fā)現(xiàn)，對加密的數(shù)據(jù)進(jìn)行處理得到一個(gè)輸出，將這一輸出進(jìn)行解密，其結(jié)果與用同一方法處理未加密的原始數(shù)據(jù)得到的輸出結(jié)果是一樣的。這樣不影響明文數(shù)據(jù)的機(jī)密性，同態(tài)加密方法在多方保密計(jì)算中發(fā)揮了重要的作用。文中運(yùn)用了Goldwasser概率加密的異或同態(tài)性，在不暴露明文的情況下，對密文進(jìn)行異或得出的結(jié)果與對明文異或得出的結(jié)果相同，高效地解決了多方拋擲硬幣問題。

1 預(yù)備知識

1.1 二次剩余

定義1:設(shè)n是正整數(shù)，若同余式x2≡a(modn)，(a，n)=1有解，則a叫模n的二次剩余;否則a叫模n的非二次剩余［9］。

定義 2:設(shè) p是素?cái)?shù)，定義勒讓德符號(Legender)［10］:

1.2 Goldwasser公鑰加密系統(tǒng)

1984年，S.Goldwasser與S.Micali提出了一種新的概率加密體制［11］，首次將隨機(jī)比特的概率思想運(yùn)用到公鑰密碼體制。每次加密是針對每個(gè)明文選取一個(gè)隨機(jī)數(shù)計(jì)算出相應(yīng)的密文。該加密體制對同一明文進(jìn)行兩次加密時(shí)得到的密文不同，Goldwasser-Micali算法主要是對0，1進(jìn)行加密，解決了RSA算法的缺陷，即因RSA算法的不足而提出。該體制的加密利用合數(shù)模二次剩余逐次加密，是第一個(gè)具有語義安全性的類同態(tài)加密方案。

Goldwasser-Micali公鑰加密系統(tǒng)是基于二次剩余的比特承諾協(xié)議，包含以下算法:

密鑰生成:隨機(jī)選取大素?cái)?shù)p，q，計(jì)算n=pq，隨機(jī)選取一個(gè)正整數(shù)t滿足勒讓德符號:==-1，即t是模p，q的二次非剩余。公開密鑰是( n ，t)，私鑰是 ( p ，q )。

加密:設(shè)有待加密的二進(jìn)制表示的明文:m= m1m2…mn。對每個(gè)明文比特mi，隨機(jī)選擇整數(shù)ri:1 ≤ri≤n-1，計(jì)算:

得到密文E(m)=(E(m1)，E(m2)，…，E(mn))。

解密:設(shè) 密 文 E(m)=(E(m1)，E(m2)，…，E(mn))。對每個(gè)密文E(mi)，先計(jì)算出勒讓德符號的值，然后令

得到解密出的明文為m=m1m2…mn。

1.3 同態(tài)加密

異或同態(tài)性:給定明文m1，m2，E(m1)×E(m2)=，由此可知Goldwasser加密系統(tǒng)滿足異或同態(tài)性，支持任意多次異或同態(tài)操作，即對任意的消息m1，m2，…，mn有:

E(m1)×E(m2)×…×E(mn)=E(m1⊕m2⊕…

⊕mn)

即Goldwasser加密系統(tǒng)的同態(tài)性僅適用于異或操作。

例如:

2 問題與解決方案

2.1 兩人參與拋擲硬幣方案的協(xié)議

協(xié)議1:兩方參與拋擲硬幣的一般步驟:

(1)Alice必須在Bob猜測之前拋幣。

(2)Bob猜測后，Alice不能再拋幣。

(3)Bob猜測前不能知道硬幣怎樣落地。

協(xié)議2:Alice和Bob在玩一個(gè)拋擲硬幣游戲，下面提出了兩個(gè)人的游戲過程協(xié)議［12］:

(1)由Alice發(fā)送一對大素?cái)?shù)p，q的乘積n=pq給Bob。

(2)Bob在Zn*中隨機(jī)選取一個(gè)小于的r，然后發(fā)送a=r2modn給Alice。

(4)Bob收到0或1后將第2步選擇的r發(fā)送給Alice。

(5)Alice驗(yàn)證r∈Zn*∧ { r1，r2}，Alice根據(jù)第3步和接收到的r可以知道她的猜測是否正確，將p，q值傳送給Bob。

(6)Bob檢驗(yàn)p，q是否為兩個(gè)不同的素?cái)?shù)，且驗(yàn)證n=pq是否成立。根據(jù)r2≡amodn，計(jì)算出 { r1，r2}，Bob知道他和Alice的游戲最后誰勝利了。

2.2 多方參與拋擲硬幣協(xié)議

2.2.1 方案的基本思想一

n個(gè)參與者P1，P2，…，Pn每人產(chǎn)生1比特信息，并對各自的1比特信息m1，m2，…，mn分別加密，通過對各自的猜測值的密文進(jìn)行保密的異或運(yùn)算產(chǎn)生一個(gè)隨機(jī)數(shù)m0，利用Goldwasser概率加密算法的異或同態(tài)性。這個(gè)隨機(jī)數(shù)m0就是硬幣拋擲的結(jié)果。

協(xié)議3:多方保密確定硬幣結(jié)果。

輸入:n個(gè)參與者P1，P2，…，Pn的猜測值分別是m1，m2，…，mn。

輸出:硬幣結(jié)果m0。

(1)P1，P2，…，Pn用Goldwasser-Micali概率加密算法分別對m1，m2，…，mn進(jìn)行加密，得到

(2)P1將加密結(jié)果E(m1)發(fā)送給P2，P2做運(yùn)算E(m1)×E(m2)，并把結(jié)果發(fā)送給 P3，P3做運(yùn)算E(m1)×E(m2)×E(m3)，并把結(jié)果發(fā)送給P4，依次類推，Pn-1做運(yùn)算E(m1)×E(m2)×…×E(mn-1)，并把結(jié)果發(fā)送給Pn，Pn做運(yùn)算E(m1)×E(m2)×… × E(mn-1)×E(mn)，并把結(jié)果發(fā)送給P1。

(3)P1由Goldwasser概率加密的異或同態(tài)性得出E(m1)×E(m2)×… ×E(mn)=E(m1⊕m2⊕…⊕mn)，P1對Pn發(fā)來的結(jié)果用勒讓德判斷是否為二次剩余，如果是，那么硬幣結(jié)果為m0=0，否則，硬幣結(jié)果為m0=1，并將m0公布給其他參與者。

(4)P1公布p，q的值，其他參與者驗(yàn)證P1公布結(jié)果的正確性。

2.2.2 方案的基本思想二

n個(gè)參與者P1，P2，…，Pn每人產(chǎn)生n比特信息，并對各自的n比特信息m1，m2，…，mn分別加密，通過對各自的猜測值的密文進(jìn)行保密的異或運(yùn)算產(chǎn)生n比特信息m0，利用Goldwasser概率加密算法的異或同態(tài)性，這個(gè)n比特m0就是硬幣拋擲的結(jié)果。此方法與上述運(yùn)算方法相同。

2.3 實(shí)例驗(yàn)證

(1)設(shè)有4個(gè)參與者P1，P2，P3，P4的猜測值是m1=1，m2=0，m3=0，m4=1，P1，P2，P3，P4對各自的猜測結(jié)果分別加密為E(m1)=modn，E(m2)=modn，E(m3)=modn，E()=modn。

(2)P1將加密結(jié)果E(m1)=modn發(fā)送給，計(jì)算E()×E(=modn，并把結(jié)果發(fā)送給，計(jì)算E(m)×E(m)×E(m)=modn，并123把結(jié)果發(fā)送給，計(jì)算E(m1)×E(m2)×E(m3)× E(m) =modn，則 由 異 或 同 態(tài) 性 得4E( m⊕m⊕…⊕m)=modn，并把結(jié)果發(fā)12n送給P1。

(3)P1判斷勒讓德符號

(4)P1公布p，q的值，其他參與者驗(yàn)證P1公布結(jié)果的正確性。

3 性能分析

3.1 安全性分析

在數(shù)論中，對于n的任意二次剩余r，求r使得r2≡amodn的困難性相當(dāng)于對n進(jìn)行因子分解的困難性，特別是當(dāng)n為10200量級且滿足n≡1mod8時(shí)，求解二次剩余是難題，協(xié)議3是基于二次剩余的，該協(xié)議的安全性依賴于大整數(shù)分解這個(gè)困難性問題［13］。

協(xié)議3是多方參與確定硬幣的結(jié)果，參與者通過對猜測值進(jìn)行異或運(yùn)算得出硬幣結(jié)果，這個(gè)結(jié)果是一個(gè)隨機(jī)數(shù)，參與者不確定隨機(jī)數(shù)是0還是1，也沒必要故意看別人的猜測值，所以該方案在對猜測值進(jìn)行加密并傳遞的過程是安全的。P1用私鑰解密并把結(jié)果和私鑰公布，在這個(gè)環(huán)節(jié)，其他參與者如果不相信P1公布的結(jié)果，可以用私鑰驗(yàn)證。

綜上所述，協(xié)議3的整個(gè)過程都是安全的。

3.2 復(fù)雜度分析

計(jì)算復(fù)雜度:協(xié)議2需要Bob計(jì)算r2≡amodn，進(jìn)行一次模n運(yùn)算得到a，Alice通過兩次勒讓德符號驗(yàn)證a是模n的二次剩余，再做一次模n運(yùn)算，Bob最終驗(yàn)證結(jié)果需要做一次r2≡amodn運(yùn)算，所以協(xié)議2的計(jì)算復(fù)雜度是O(3)。協(xié)議3每人平均對自己的猜測結(jié)果用Goldwasser加密算法［14］加密一次，然后除P1外都要做一次乘法運(yùn)算，Pn把運(yùn)算結(jié)果發(fā)送給P1，并判斷一次勒讓德符號，得出一個(gè)異或結(jié)果m0，并將m0公布給其他參與者，協(xié)議3的計(jì)算復(fù)雜度是O(2)，協(xié)議3比協(xié)議2的計(jì)算復(fù)雜度低。

通信復(fù)雜度:衡量通信復(fù)雜度的指標(biāo)是協(xié)議交換信息的比特?cái)?shù)或者通信輪數(shù)，在多方保密計(jì)算研究中通常用輪數(shù)。協(xié)議2中Alice和Bob的通信輪數(shù)為5，協(xié)議3中n個(gè)人的通信輪數(shù)為n+1，但是協(xié)議3是多方拋擲硬幣，通信復(fù)雜度必然會高，總體來說協(xié)議3比協(xié)議2通信復(fù)雜性低。

4 結(jié)束語

公平拋擲硬幣協(xié)議是一種模擬拋擲硬幣協(xié)議，一般采用單向函數(shù)的拋擲協(xié)議和公開密鑰密碼學(xué)的協(xié)議，但是這些協(xié)議均僅限于兩方，對多方?jīng)]有普遍適用性。文中研究了多方拋擲硬幣的多方保密計(jì)算，提出了一種新的解決方案。該方案運(yùn)用了Goldwasser概率加密因子分解的困難假設(shè)和異或同態(tài)性，并對其進(jìn)行了安全性分析和復(fù)雜性分析，滿足多方保密的安全性需求。

［1］ Bulgurcu B，Cavusoglu H，Benbasat I.Information security policy compliance:an empirical study of rationality-based beliefs and information security awareness［J］.MIS Quarterly，2010，34(3):523-548.

［2］ Siponen M，Mahmood M A，Pahnila S.Employees’adherence to information security policies:an exploratory field study［J］. Information＆Management，2014，51(2):217-224.

［3］ Du W，Atallah M J.Secure multi-party computation problems and their applications:a review and open problems［C］// Raskin V，Greenwald S J，Timmerman B，et al.Proceedings of new security paradigms workshop 2001.New York:ACM Press，2001:13-22.

［4］ Blum M.Coin flipping by telephone:a protocal for solving impossible problems［C］//Proceedings of the 24th IEEE computer conference.［s.l.］:IEEE，1982:133-137.

［5］ Ben-Or M，Linial N.Collective coin flipping［M］//Randomness and computation.New York:Academic Press，1990:91-115.

［6］ Lindell Y.Parallel coin-tossing and constant-round secure two -party computation［J］.Journal of Cryptology，2003，16(3): 143-184.

［7］ 余 堃，沈 仟，周明天.背包問題在硬幣拋擲協(xié)議上的研究［J］.電子科技大學(xué)學(xué)報(bào)，2003，32(4):417-419.

［8］ Brakerski Z，Vaikuntanathan V.Efficient fully homomorphic encryption from(standard)LWE［J］.SIAM Journal on Computing，2014，43(2):831-871.

［9］ 陳恭亮.信息安全數(shù)學(xué)基礎(chǔ)［M］.北京:清華大學(xué)出版社，2004:82-83.

［10］Koblitz N.A course in number theory and cryptography［M］. ［s.l.］:Springer Science and Business Media，1994.

［11］Goldwasser S，Micali S.Probabilistic encryption［J］.Journal of Computer and System Sciences，1984，28(2):270-299.

［12］Schneier B，吳世忠，祝世雄，等.應(yīng)用密碼學(xué):協(xié)議、算法與C源程序［M］.北京:機(jī)械工業(yè)出版社，2000:387-388.

［13］李子臣，戴一奇.二次剩余密碼體制的安全性分析［J］.清華大學(xué)學(xué)報(bào):自然科學(xué)版，2001，41(7):80-82.

［14］ Goldwasser S.Multi party computations:past and present ［C］//Proceedings of the sixteenth annual ACM symposium on principles of distributed computing.［s.l.］:ACM，1997:1-6.

A Coin Toss Protocol Based on Quadratic Residue

YANG Xiao-li，ZUO Xiang-jian
(School of Computer Science，Shaanxi Normal University，Xi’an 710119，China)

The coin toss has important applications in both cryptography and information security.For example，in a basketball match or a football match，the referee decides which team to play first by the result of a coin toss，then judges the toss of a coin.If a coin is positive，the party A attacks from left to right;conversely，party B does from left to right.This experiment is a kind of simple coin drop agreement. However，for two people not in the same place，how to fairly toss a coin is a problem to be researched.Studies an extended problem of a coin toss:multi-party coin toss protocol，and constructs a solution to it.This scheme is based on the XOR homomorphism of Goldwasser -Micali probabilistic encryption algorithm and difficulty of factor molecules，and is exclusive or operation to the results of many people toss of a coin，guaranteeing the security and fairness in secure multiparty coin toss.It proves that these protocols are analyzed in security and complexity.

cryptography;secure multi-party computation;coin toss;probabilistic encryption;XOR homomorphism

TP309

A

1673-629X(2016)09-0139-04

10.3969/j.issn.1673-629X.2016.09.031

2015-08-18

2016-01-06< class="emphasis_bold">網(wǎng)絡(luò)出版時(shí)間:

時(shí)間:2016-08-23

國家中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金項(xiàng)目(GK201504017);包頭市科技計(jì)劃項(xiàng)目(2014S2004-2-1-15)

楊曉莉(1989-)，女，碩士研究生，研究方向?yàn)槊艽a學(xué)與信息安全。

http://www.cnki.net/kcms/detail/61.1450.TP.20160823.1343.028.html