一种基于二次剩余的抛掷硬币方案

杨晓莉，左祥建

(陕西师范大学计算机科学学院，陕西西安 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

国家中央高校基本科研业务费专项资金项目(GK201504017);包头市科技计划项目(2014S2004-2-1-15)

杨晓莉(1989-)，女，硕士研究生，研究方向为密码学与信息安全。

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