拋擲硬幣方案研究

馬 麗，竇家維，吳艷梅

(陜西師范大學 數學與信息科學學院，陜西 西安 710119)

拋擲硬幣方案研究

馬 麗，竇家維，吳艷梅

(陜西師范大學 數學與信息科學學院，陜西 西安 710119)

拋擲硬幣是多方保密計算的一個重要模塊，而且在現實生活中也有重要應用。網絡中，拋擲硬幣的雙方往往不在同一個地點，但仍需要公平地決定一件事情，因而拋擲硬幣的公平性是一個重要的研究方向。可見，無論是計算機及網絡保密，還是日常生活，都需要研究和解決拋擲硬幣的不公平問題。為此，在應用單向函數構建一個公平的拋擲硬幣方案，并驗證其有效性的基礎上，采用二次剩余法和勒讓德符號設計了一個不公平的拋擲硬幣方案，正面朝上的概率為0.25，反面朝上則為0.75。在網絡通信前提下,對兩種方案的安全性和復雜性分別進行了對比分析研究。分析結果表明，所設計的兩種拋擲硬幣方案將單向函數與拋擲硬幣協議有機結合，相關協議簡單易行，具有較好的應用價值。

密碼學；多方保密計算；硬幣拋擲；離散對數假設

1 概 述

隨著網絡信息技術的發展，網絡不僅給人們的日常生活帶來許多便捷，同時也存在諸多隱患。有些網絡用戶可能出于經濟目的、政治目的或者個人目的等，利用網絡中的漏洞對其實施攻擊，造成網絡信譽下降、喪失機密等網絡安全事故，嚴重地可能造成國家政治、社會、經濟的混亂；因此，信息安全問題是當今社會急需解決的課題之一[1-5]。文中主要以拋擲硬幣問題為主，設計一種簡單、可行、有效的安全協議。

拋擲硬幣方案是密碼學中一個重要的研究方向。Blum在1982年利用調制解調器提出拋擲公平硬幣問題[6]，利用位比特協議解決兩個人拋擲硬幣問題；Ben等在1990年提出了硬幣拋擲問題[7]；佘堃在2003年提出了公平硬幣拋擲協議[8]，隨后許多學者對拋擲硬幣方案進行了研究[9-13]。

在信息化時代，人們仍需要用拋硬幣的方法公平地決定某件事，比如：足球比賽前，主裁判在場地中央拋擲硬幣，決定哪一方先發球。但是如果在網絡活動中，兩個人需要通過拋硬幣的方法決定一件事就困難了，因為他們處在世界的不同角落，不可能因為拋硬幣走在一起。而如果其中一個人拋硬幣，假設選擇由Alice拋硬幣，Bob擔心兩件事：一是Alice選擇硬幣可能是不均勻的，可能出現正面的情況多，或者出現反面的情況多；二是即使Alice選擇的硬幣是均勻的，但是Alice可能不報告拋擲的正確結果，而選擇一個對自己有利的結果。在密碼學中，甲乙拋擲硬幣，結果揭示之前，雙方都不想讓對方知道自己的結果，這是多方保密計算的重要模型之一。歷史上許多學者進行了拋硬幣實驗，并且推動了硬幣實驗在密碼學和信息安全中的重要應用，但是仍然存在許多不足。生活中有這樣的事情:兩個人為一件小事爭執不休，他們用拋擲硬幣的方式解決，他們不能親眼見證拋擲結果，只能相互告知。

文中利用單向函數設計了一個公平的拋擲硬幣方案，使得正面向上的概率為0.25，反面向上的概率為0.75，并分析了兩種方案的安全性。

2 預備知識

2.1 二次剩余

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

定義2：設p是素數，定義勒讓德符號(Legender)如下[14]：

(1)

2.2 離散對數假設

αx≡βmodp

(2)

(3)

2.3 設計原則

在設計拋擲硬幣協議的過程中需滿足以下性質：

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

(2)在聽到Bob的猜測后，Alice不能再拋擲硬幣。

(3)Bob在猜測之前不能知道硬幣是怎么落地的。

2.4 基于公開密鑰密碼術的拋幣協議

協議設計原理：該協議可以與公開密鑰系統又可與對稱密碼系統一起工作。其唯一要求就是滿足交換律。一般對對稱算法這個特性不滿足，但對某些公開密鑰算法是正確的。

協議1：基于公開密鑰密碼術的拋幣協議[14]。

(1)Alice和Bob都產生一個公開密鑰/私人密鑰對。

(2)Alice產生兩個消息，其一指示正面，另一個指示反面。這些消息中包含有某個唯一的隨機串，以便以后能夠驗證其在協議中的真實性。Alice用她的公開密鑰加密兩個消息，并以隨機的順序把他們發給Bob：EA(M1),EA(M2)。

(3)Bob由于不能讀懂其中任意一條消息，于是隨機選擇一條，用他的公開密鑰加密并回送給Alice：EB(EA(M))(M為M1或M2)。

(4)Alice由于不能讀懂送回給她的消息，就用她的私人密鑰解密并發送給Bob：DA(EB(EA(M)=EB(M1)(M=M1)或EB(M2)(M=M2)。

(5)Bob用他的私人密鑰解密消息，得到硬幣的結果。將解密后的消息發給Alice：DB(EB(M1))=M1或DB(EB(M2))=M2。

(6)Alice得到拋硬幣結果，并驗證隨機串的正確性。

(7)Alice和Bob出示他們的密鑰對以便雙方能驗證對方沒有欺騙。

安全性分析如下：

這個協議是自我實施的。任意一方都能即時檢測對方的欺詐，不需要可信的第三方介入實際的協議和協議完成后的仲裁。如果試圖欺詐，看看協議是如何工作的。

如果Alice想欺騙，強制為正面，她有三種可能的方法影響結果。首先，可以在步驟(2)中加密兩個“正面”的消息。在步驟(7)Alice出示她的密鑰時，Bob就可以發現這種欺騙。第二種方法，Alice在步驟(4)用一些其他的密鑰解密消息，將產生一些亂七八糟的無用消息，Alice可在步驟(5)中發現。第三種方法，Alice可在步驟(6)中否認消息的有效性，當在步驟(7)中Alice不能證明消息無效，Bob就可以發現。當然，Alice可以在任何一步拒絕參與協議，那樣，Alice欺騙Bob的企圖就顯而易見了。

如果Bob想欺騙并強制為“反面”，他的選擇性不大。他可以在步驟(3)中不正確地加密一條消息，但Alice在步驟(6)查看最終的消息時就可以發現；他可以在步驟(5)中進行不適當的操作，但這會導致亂七八糟的無用信息，Alice可在步驟(6)中發現；他可以聲稱由于Alice那方的欺詐使他不能適當地完成步驟(5)的操作，但這種形式的欺詐能在步驟(7)中發現；最后，他可能在步驟(5)中給Alice一個“反面”的消息，而不管他解密獲得的消息是什么，但Alice能在步驟(6)中立即檢驗消息的真實性。

3 問題與解決方案

3.1 基于離散對數的公平拋擲硬幣協議

協議設計原理：Alice和Bob一致選擇y≡axmodp作為協議中的單向函數，利用x的奇偶性，可以實現公平的拋擲硬幣的方案。

協議2：Alice和Bob一致選擇y≡axmodp作為協議中的單向函數。

(1)Alice選擇一個非零的隨機數x，并計算y≡axmodp。

(2)Alice將y發送給Bob。

(3)Bob猜測x是奇數還是偶數，并將猜測結果發送給Alice。

(4)如果Bob的猜測結果正確，則拋硬幣的結果為正面；如果Bob的猜測結果錯誤，則拋硬幣的結果為反面。Alice公布此次拋硬幣的結果，并將x發送給Bob。

(5)Bob驗證y≡axmodp。

安全性分析如下：

在拋擲硬幣的過程中，只有Alice可能進行欺騙，因為在協議過程中，Bob只是猜測。

如果Alice在步驟(2)進行欺騙，發送y′(y′≠y)給Bob，Bob在步驟(5)計算y≡axmodp，可檢驗Alice是否進行欺騙。

如果Alice在步驟(4)進行欺騙，發送x′(x≠x′)給Bob，Bob在步驟(5)計算y≡axmodp，可檢驗Alice是否進行欺騙。

3.2 基于二次剩余的不公平拋擲硬幣協議

協議設計原理：Alice和Bob利用二次剩余的原理，以及勒讓德符號，實現了不公平的拋擲硬幣方案。

協議3：Alice和Bob拋擲硬幣，猜測值為a。

(1)Alice選擇兩個不同的大素數p,q，并計算n=pq，將n發送給Bob。

(3)Alice將步驟(2)的驗證結果告訴Bob，并將p,q發送給Bob。

(4)Bob驗證p,q是否為兩個不同的大素數，且驗證n=pq是否成立。

安全性分析如下：

在拋擲硬幣的過程中，只有Alice可進行欺騙，因為Bob是一個驗證者的身份。假設Alice進行欺騙。

Alice在步驟(1)進行欺騙，Bob在步驟(6)對n=pq進行驗證，根據因子分解原理，可得到Alice是否進行欺騙。

Alice在步驟(3)進行欺騙，將錯誤結果和p,q發給Bob，Bob在步驟(6)對n=pq進行驗證，根據因子分解原理，可得到Alice是否進行欺騙。

4 性能分析

協議1為基于公開密鑰密碼術的拋硬幣協議，但只適合于某些公開密鑰算法，如相同模數的RSA算法；協議2為基于單向函數的拋硬幣協議，彌補了協議1的不足；協議3為基于二次剩余的拋硬幣協議，突破了一般的公平拋硬幣協議，使得正面的概率為0.25，反面的概率為0.75。現對這三種協議的計算復雜性和通信復雜性進行分析。

4.1 計算復雜性

在利用公鑰密碼系統構建的協議中，模指數運算的次數是決定協議效率的主要因素，因此協議的計算復雜性由模指數運算的次數衡量。如果一個協議中進行模指數運算的次數越多，其計算復雜性越高，所以把模指數運算作為對這三種協議進行計算復雜性分析的主要方面。協議2需要進行2次模運算，而協議1和協議3無需模指數運算，協議3實現了不公平的拋擲硬幣。

4.2 通信復雜性

協議的通信復雜性是傳遞數據的次數或者傳送數據的比特數。傳遞的次數越多，則協議的通信復雜性越高。協議1中，通過4次傳遞完成了數據的交互過程。協議2中，通過3次傳遞完成了數據的交互過程。協議3中，通過2次傳遞完成了數據的交互過程。很明顯，協議3的計算復雜性較低。

5 結束語

文中提出了兩種新的拋硬幣協議，基于單向函數的方案和基于二次剩余的方案。協議2簡單易行；協議3突破了傳統的公平拋硬幣協議，使得正面的概率為0.25，反面的概率為0.75。對協議2和協議3的安 全性和復雜性進行了分析，并與協議1進行了對比。

在滿足拋硬幣協議設計原則的基礎上，如何設計出簡單公平的拋硬幣協議是今后主要研究的對象。

[1] Beimel A,Omri E, Orlov I.Protocols for multiparty coin toss with a dishones majority[J].Journal of Cryptology,2015,28(3):551-600.

[2] Moran T,Naor M,Segev G.An optimally fair coin toss[J].Journal of Cryptology,2016,29(3):491-513.

[3] Diaconis P,Holmes S,Montgomery R.Dynamical bias in the coin toss[J].SIAM Review,2007,49(2):211-235.

[4] Turner B J,Hecht F M.Improving on a coin toss to predict patient adherence to medications[J].Annals of Internal Medicine,2001,134(10):1004-1006.

[5] Cho A.Breakthrough lost in coin toss[J].Science,2014,346(6205):22-23.

[6] Blum M.Coin flipping by telephone:a protocol for solving impossible problems[C]//Proceedings of the 24th IEEE computer conference.[s.l.]:IEEE,1982:133-137.

[7] Benor M,Linial N.Collective coin flipping[J].Randomness and Computation,1990,5:91-115.

[8] 佘 堃,沈 仟,周明天.背包問題在硬幣拋擲協議上的研究[J].電子科技大學學報,2003,32(4):417-419.

[9] Heath D,Kinderlehrer D,Kowalczyk M.Discrete and continuous ratchets:from coin toss to molecular motor[J].Discrete and Continuous Dynamical Systems Series B,2002,2(2):153-168.

[10] Wagner D.Technical perspective:fairness and the coin flip[J].Communications of the ACM,2016,59(4):75.

[11] Zarkhin V,Sarwal M M.The coin toss of B cells in rejection and tolerance:danger versus defense[C]//Seminars in immunology.[s.l.]:Academic Press,2012:86-91.

[12] Larue D V.System and method for playing a game based on a coin toss:U.S.,8648710[P].2014-02-11.

[13] Ibsen-Jensen R, Miltersen P B. Solving simple stochastic games with few coin toss positions[C]//Algorithms-ESA 2012.[s.l.]:[s.n.],2012:636-647.

[14] Schneier B.應用密碼學[M].吳世忠，祝世雄， 張文政,等,譯.北京:機械工業出版社,2014.

Investigation on Tossing Coin Scheme

MA Li,DOU Jia-wei,WU Yan-mei

(College of Mathematics and Information Science,Shaanxi Normal University,Xi’an 710119,China)

A coin toss is an important module of secure multi-party computation,and also has important application in real life.In network，the two sides of the coin toss are often not in the same place,but it still needs to be a fair decision.The fair coin toss is an important investigation direction.So both computer and network security,or everyday life,unfair issues with the coin toss need to be investigated and solved.Therefore,an unfair coin toss scheme has been designed with two-residual method and Legendre symbol after a fair coin toss scheme is constructed with one-way function and its effectiveness is verified,in which the probability for upward of the positive surface coin tossing is 0.25 while that of the opposite surface is 0.75.In network communication comparison and analysis on security and complexity of these two schemes have been conducted respectively.Analysis results show that the designs of two coin toss schemes in network communication are integratively merged with the combination of one-way function and coin tossing protocol and that the relevant protocols are simple and easy for implementation and convenient to be applied with vast prospective for actual application.

cryptography;secure multi-party computation;coin toss;discrete logarithm assumption

2016-05-26

2016-09-13

時間：2017-03-07

國家自然科學基金資助項目(61272435)；包頭市科技局項目(2014S2004-2-1-15)

馬 麗(1983-)，女，碩士研究生，研究方向為密碼學與信息安全；竇家維，副教授，碩士生導師，研究方向為密碼學與信息安全。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170307.0921.054.html

TP31

A

1673-629X(2017)04-0117-03

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