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

楊曉莉，左祥建

(陜西師范大學計算機科學學院，陜西西安 710119)

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

楊曉莉，左祥建

(陜西師范大學計算機科學學院，陜西西安 710119)

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

密碼學;安全多方計算;硬幣拋擲;概率加密;異或同態性

0 引言

隨著互聯網的發展，不僅給人們的生活提供了便利，同時也帶來了不少麻煩，比如說個人信息泄漏、信息破壞、信息污染，這些都是信息安全問題［1-2］。信息安全問題是當今社會談論的熱點問題之一。因此，解決信息安全問題是學者研究的重要問題。

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

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

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

1 預備知識

1.1 二次剩余

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

定義 2:設 p是素數，定義勒讓德符號(Legender)［10］:

1.2 Goldwasser公鑰加密系統

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

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

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

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

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

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

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

1.3 同態加密

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

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

⊕mn)

即Goldwasser加密系統的同態性僅適用于異或操作。

例如:

2 問題與解決方案

2.1 兩人參與拋擲硬幣方案的協議

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

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

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

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

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

(1)由Alice發送一對大素數p，q的乘積n=pq給Bob。

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

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

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

(6)Bob檢驗p，q是否為兩個不同的素數，且驗證n=pq是否成立。根據r2≡amodn，計算出 { r1，r2}，Bob知道他和Alice的游戲最后誰勝利了。

2.2 多方參與拋擲硬幣協議

2.2.1 方案的基本思想一

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

協議3:多方保密確定硬幣結果。

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

輸出:硬幣結果m0。

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

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

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

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

2.2.2 方案的基本思想二

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

2.3 實例驗證

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

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

(3)P1判斷勒讓德符號

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

3 性能分析

3.1 安全性分析

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

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

綜上所述，協議3的整個過程都是安全的。

3.2 復雜度分析

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

通信復雜度:衡量通信復雜度的指標是協議交換信息的比特數或者通信輪數，在多方保密計算研究中通常用輪數。協議2中Alice和Bob的通信輪數為5，協議3中n個人的通信輪數為n+1，但是協議3是多方拋擲硬幣，通信復雜度必然會高，總體來說協議3比協議2通信復雜性低。

4 結束語

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

［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］ 余 堃，沈 仟，周明天.背包問題在硬幣拋擲協議上的研究［J］.電子科技大學學報，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］ 陳恭亮.信息安全數學基礎［M］.北京:清華大學出版社，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，吳世忠，祝世雄，等.應用密碼學:協議、算法與C源程序［M］.北京:機械工業出版社，2000:387-388.

［13］李子臣，戴一奇.二次剩余密碼體制的安全性分析［J］.清華大學學報:自然科學版，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">網絡出版時間:

時間:2016-08-23

國家中央高?；究蒲袠I務費專項資金項目(GK201504017);包頭市科技計劃項目(2014S2004-2-1-15)

楊曉莉(1989-)，女，碩士研究生，研究方向為密碼學與信息安全。

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