拋擲硬幣方案研究

馬 麗，竇家維，吳艷梅

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

拋擲硬幣方案研究

馬 麗，竇家維，吳艷梅

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

拋擲硬幣是多方保密計算的一個重要模塊，而且在現(xiàn)實(shí)生活中也有重要應(yīng)用。網(wǎng)絡(luò)中，拋擲硬幣的雙方往往不在同一個地點(diǎn)，但仍需要公平地決定一件事情，因而拋擲硬幣的公平性是一個重要的研究方向?？梢姡瑹o論是計算機(jī)及網(wǎng)絡(luò)保密，還是日常生活，都需要研究和解決拋擲硬幣的不公平問題。為此，在應(yīng)用單向函數(shù)構(gòu)建一個公平的拋擲硬幣方案，并驗證其有效性的基礎(chǔ)上，采用二次剩余法和勒讓德符號設(shè)計了一個不公平的拋擲硬幣方案，正面朝上的概率為0.25，反面朝上則為0.75。在網(wǎng)絡(luò)通信前提下,對兩種方案的安全性和復(fù)雜性分別進(jìn)行了對比分析研究。分析結(jié)果表明，所設(shè)計的兩種拋擲硬幣方案將單向函數(shù)與拋擲硬幣協(xié)議有機(jī)結(jié)合，相關(guān)協(xié)議簡單易行，具有較好的應(yīng)用價值。

密碼學(xué)；多方保密計算；硬幣拋擲；離散對數(shù)假設(shè)

1 概 述

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

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

在信息化時代，人們?nèi)孕枰脪佊矌诺姆椒ü降貨Q定某件事，比如：足球比賽前，主裁判在場地中央拋擲硬幣，決定哪一方先發(fā)球。但是如果在網(wǎng)絡(luò)活動中，兩個人需要通過拋硬幣的方法決定一件事就困難了，因為他們處在世界的不同角落，不可能因為拋硬幣走在一起。而如果其中一個人拋硬幣，假設(shè)選擇由Alice拋硬幣，Bob擔(dān)心兩件事：一是Alice選擇硬幣可能是不均勻的，可能出現(xiàn)正面的情況多，或者出現(xiàn)反面的情況多；二是即使Alice選擇的硬幣是均勻的，但是Alice可能不報告拋擲的正確結(jié)果，而選擇一個對自己有利的結(jié)果。在密碼學(xué)中，甲乙拋擲硬幣，結(jié)果揭示之前，雙方都不想讓對方知道自己的結(jié)果，這是多方保密計算的重要模型之一。歷史上許多學(xué)者進(jìn)行了拋硬幣實(shí)驗，并且推動了硬幣實(shí)驗在密碼學(xué)和信息安全中的重要應(yīng)用，但是仍然存在許多不足。生活中有這樣的事情:兩個人為一件小事爭執(zhí)不休，他們用拋擲硬幣的方式解決，他們不能親眼見證拋擲結(jié)果，只能相互告知。

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

2 預(yù)備知識

2.1 二次剩余

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

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

(1)

2.2 離散對數(shù)假設(shè)

αx≡βmodp

(2)

(3)

2.3 設(shè)計原則

在設(shè)計拋擲硬幣協(xié)議的過程中需滿足以下性質(zhì)：

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

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

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

2.4 基于公開密鑰密碼術(shù)的拋幣協(xié)議

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

協(xié)議1：基于公開密鑰密碼術(shù)的拋幣協(xié)議[14]。

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

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

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

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

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

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

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

安全性分析如下：

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

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

如果Bob想欺騙并強(qiáng)制為“反面”，他的選擇性不大。他可以在步驟(3)中不正確地加密一條消息，但Alice在步驟(6)查看最終的消息時就可以發(fā)現(xiàn)；他可以在步驟(5)中進(jìn)行不適當(dāng)?shù)牟僮?，但這會導(dǎo)致亂七八糟的無用信息，Alice可在步驟(6)中發(fā)現(xiàn)；他可以聲稱由于Alice那方的欺詐使他不能適當(dāng)?shù)赝瓿刹襟E(5)的操作，但這種形式的欺詐能在步驟(7)中發(fā)現(xiàn)；最后，他可能在步驟(5)中給Alice一個“反面”的消息，而不管他解密獲得的消息是什么，但Alice能在步驟(6)中立即檢驗消息的真實(shí)性。

3 問題與解決方案

3.1 基于離散對數(shù)的公平拋擲硬幣協(xié)議

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

協(xié)議2：Alice和Bob一致選擇y≡axmodp作為協(xié)議中的單向函數(shù)。

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

(2)Alice將y發(fā)送給Bob。

(3)Bob猜測x是奇數(shù)還是偶數(shù)，并將猜測結(jié)果發(fā)送給Alice。

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

(5)Bob驗證y≡axmodp。

安全性分析如下：

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

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

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

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

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

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

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

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

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

安全性分析如下：

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

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

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

4 性能分析

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

4.1 計算復(fù)雜性

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

4.2 通信復(fù)雜性

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

5 結(jié)束語

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

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

[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] 佘 堃,沈 仟,周明天.背包問題在硬幣拋擲協(xié)議上的研究[J].電子科技大學(xué)學(xué)報,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.應(yīng)用密碼學(xué)[M].吳世忠，祝世雄， 張文政,等,譯.北京:機(jī)械工業(yè)出版社,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

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

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

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