基于秘密共享的分布式廣義不經(jīng)意傳輸協(xié)議

解咪咪，廖曉峰，周 慶

?

基于秘密共享的分布式廣義不經(jīng)意傳輸協(xié)議

解咪咪，廖曉峰，周 慶

(重慶大學(xué)計(jì)算機(jī)學(xué)院，重慶 400044)

對(duì)不經(jīng)意傳輸進(jìn)行分布式設(shè)置可以更好地保障發(fā)送方的安全以及秘密消息的可達(dá)性。為此，提出一種基于秘密共享的分布式廣義不經(jīng)意傳輸協(xié)議，允許用戶(hù)按發(fā)送方設(shè)定的特殊規(guī)則選擇并獲取一個(gè)合法的秘密消息集合。應(yīng)用廣義秘密共享接入結(jié)構(gòu)的補(bǔ)集設(shè)置消息的檢索規(guī)則，通過(guò)對(duì)多項(xiàng)式的構(gòu)建以及重構(gòu)實(shí)現(xiàn)協(xié)議的分布式特性。發(fā)送者根據(jù)加密消息、密鑰以及校驗(yàn)值產(chǎn)生 3個(gè)對(duì)應(yīng)的多項(xiàng)式，并將多項(xiàng)式分配給多個(gè)服務(wù)器，用戶(hù)通過(guò)與一定數(shù)目的服務(wù)器通信獲取所需信息。分析結(jié)果表明，該協(xié)議易于實(shí)現(xiàn)、計(jì)算簡(jiǎn)單，同時(shí)具有較高的通信效率和安全性。

不經(jīng)意傳輸；秘密共享；分布式模型；廣義模型；檢索結(jié)構(gòu)；接入結(jié)構(gòu)

1 概述

不經(jīng)意傳輸[1]是一個(gè)雙方密碼學(xué)原語(yǔ)，被研究者應(yīng)用于密碼學(xué)協(xié)議的構(gòu)建中[2]，如比特檢驗(yàn)、零知識(shí)證明和多方計(jì)算協(xié)議等[3]。隨著網(wǎng)絡(luò)的發(fā)展，不經(jīng)意傳輸協(xié)議變得愈加重要，在實(shí)踐中被廣泛應(yīng)用[4]。不經(jīng)意傳輸受到越來(lái)越多研究者的關(guān)注，許多新的不經(jīng)意傳輸協(xié)議被提出[5-6]。

在文獻(xiàn)[1]協(xié)議中，Alice持有一條消息，她與Bob協(xié)商傳遞此消息。最終的結(jié)果是Bob或者獲得了這條消息或者沒(méi)有獲得。2個(gè)事件的概率相等，均為1/2，同時(shí)，Alice無(wú)法獲知Bob是否獲得了此消息。隨后，1取2、1取和取[7]的協(xié)議接連被提出。在取不經(jīng)意傳輸協(xié)議中，Alice持有個(gè)秘密消息，Bob只能從這個(gè)秘密消息中選取個(gè)秘密消息與Alice協(xié)商獲取。最終，Alice對(duì)于Bob的選擇毫不知情，而B(niǎo)ob只能獲得他要求的個(gè)消息。分布式不經(jīng)意傳輸協(xié)議將Alice的角色分發(fā)給幾個(gè)服務(wù)器，Bob通過(guò)與一定數(shù)目的服務(wù)器通信獲得需要的消息。分布式的模型使協(xié)議變得更加安全和靈活。比如在不經(jīng)意傳輸應(yīng)用中，假如發(fā)送者不在線，那么用戶(hù)就無(wú)法請(qǐng)求獲取信息。而如果發(fā)送者被攻擊成功的話(huà)，那么它持有的所有消息都會(huì)暴露。而在分布式模型下，只要服務(wù)器運(yùn)行，即使Alice不在線，協(xié)議也可以進(jìn)行。不經(jīng)意傳輸?shù)姆植际侥Ｐ徒夥帕税l(fā)送者。發(fā)送者無(wú)需保持在線，用戶(hù)只需與一定數(shù)目的在線服務(wù)器通信來(lái)獲取信息。與非分布式模型相比，在分布式的設(shè)置下，攻擊者需要攻擊多個(gè)服務(wù)器而不是單個(gè)發(fā)送者才能竊取信息，更好地保障了消息的安全。文獻(xiàn)[8]則實(shí)現(xiàn)了取的分布式不經(jīng)意傳輸協(xié)議。

在取不經(jīng)意傳輸協(xié)議被提出之后，文獻(xiàn)[9]提出了廣義不經(jīng)意傳輸協(xié)議，即Alice預(yù)先規(guī)定幾個(gè)消息子集，每個(gè)子集中的消息數(shù)量不等，Bob只能從這幾個(gè)子集中選擇一個(gè)子集請(qǐng)求獲取消息。廣義不經(jīng)意傳輸在現(xiàn)實(shí)中有很多重要的應(yīng)用。如在電子商務(wù)中，假如Alice想要從商店購(gòu)買(mǎi)一些物品，卻不愿透露自己所買(mǎi)的物品名稱(chēng)，而店主想要確認(rèn)Alice買(mǎi)的所有物品的總價(jià)格不超過(guò)一定數(shù)目。這種情況只需要將價(jià)格不超過(guò)一定數(shù)目的物品組合規(guī)定為合法消息子集，即可通過(guò)廣義不經(jīng)意傳輸模型簡(jiǎn)便實(shí)現(xiàn)。

本文研究廣義的分布式不經(jīng)意傳輸協(xié)議，基于廣義秘密共享模型實(shí)現(xiàn)廣義不經(jīng)意傳輸協(xié)議的分布式模型構(gòu)建，并通過(guò)分析證明該協(xié)議是安全、高效的。

2 相關(guān)概念

2.1 檢索結(jié)構(gòu)

2.2 接入結(jié)構(gòu)

2.3 廣義不經(jīng)意傳輸?shù)姆植际侥Ｐ?/h3>

廣義分布式不經(jīng)意傳輸將發(fā)送者的角色分配給了多個(gè)服務(wù)器，發(fā)送者根據(jù)所持有的消息確定一個(gè)檢索結(jié)構(gòu)，用戶(hù)通過(guò)與固定數(shù)目的服務(wù)器通信獲取檢索結(jié)構(gòu)中的一個(gè)消息集合。具體模型如圖1所示。

圖1 不經(jīng)意傳輸?shù)姆植际侥Ｐ?/p>

一個(gè)分布式不經(jīng)意傳輸協(xié)議包含3個(gè)參與方和2個(gè)階段。安全的分布式不經(jīng)意傳輸協(xié)議要滿(mǎn)足多個(gè)安全條件。

(1)參與方

(2)協(xié)議構(gòu)建

分布式協(xié)議包含構(gòu)建階段和傳遞階段：

1)構(gòu)建階段(發(fā)送者和服務(wù)器)：發(fā)送者按一定的方法將所持秘密消息份額分配給個(gè)服務(wù)器。

2)傳遞階段(服務(wù)器和用戶(hù))：用戶(hù)與固定數(shù)目的服務(wù)器通信來(lái)獲取持有消息的一個(gè)消息子集。

(3)安全屬性

分布式不經(jīng)意傳輸協(xié)議必須滿(mǎn)足一般不經(jīng)意傳輸協(xié)議的安全要求，同時(shí)由于其分布式設(shè)置也要滿(mǎn)足一些附加的安全條件：

1)正確性：如果用戶(hù)和個(gè)誠(chéng)實(shí)的服務(wù)器中的個(gè)通信并且正確履行協(xié)議，那么用戶(hù)可以正確獲取他所選集合的消息。

2)發(fā)送者的安全：如果服務(wù)器誠(chéng)實(shí)履行協(xié)議，那么用戶(hù)不能獲得所選消息之外的任何消息。另外，少于個(gè)服務(wù)器聯(lián)合攻擊不能重構(gòu)任何發(fā)送者持有的消息。

3)用戶(hù)的隱私：少于個(gè)服務(wù)器聯(lián)合攻擊也不能獲悉用戶(hù)對(duì)于秘密消息的選擇。因?yàn)榘l(fā)送者在整個(gè)協(xié)議的傳遞階段都沒(méi)有參與，所以發(fā)送者絕不可能獲取用戶(hù)對(duì)于秘密消息的選擇消息。

3 本文協(xié)議

3.1 協(xié)議原理

3.2 協(xié)議描述

然后設(shè)置：

(1)構(gòu)建階段(發(fā)送者和服務(wù)器)

1)生成3個(gè)多項(xiàng)式

2)多項(xiàng)式分配

(2)傳遞階段(用戶(hù)和服務(wù)器)

在協(xié)議的傳遞階段，用戶(hù)需要和服務(wù)器進(jìn)行2輪通信。

第1輪：

1)選擇消息和服務(wù)器

2)產(chǎn)生請(qǐng)求消息

第2輪：

1)恢復(fù)校驗(yàn)值

3)密鑰傳遞

4)恢復(fù)請(qǐng)求的消息

4 安全性和效率分析

4.1 協(xié)議安全性

從用戶(hù)、發(fā)送方2個(gè)方面討論本文協(xié)議的安全性。

1)在傳遞階段第1輪結(jié)束時(shí)，由于接入結(jié)構(gòu)的完美性，僅當(dāng)用戶(hù)按照協(xié)議選擇合法的消息集時(shí)才能重構(gòu)校驗(yàn)值。在第2輪中，僅當(dāng)校驗(yàn)值正確時(shí)，服務(wù)器才會(huì)返回密鑰。因此，當(dāng)用戶(hù)選擇的消息集不屬于檢索結(jié)構(gòu)時(shí)，用戶(hù)無(wú)法獲得密鑰，也無(wú)法恢復(fù)秘密消息。

4.2 協(xié)議效率

本節(jié)討論協(xié)議的存儲(chǔ)和通信效率。假設(shè)協(xié)議存在一個(gè)完美的秘密共享接入結(jié)構(gòu)，那么由這個(gè)秘密共享模型產(chǎn)生的共享份額和秘密消息的大小相同。

5 結(jié)束語(yǔ)

分布式不經(jīng)意傳輸在在線應(yīng)用中扮演著非常重要的角色，與傳統(tǒng)的不經(jīng)意傳輸相比，分布式的設(shè)置可以更好地保障發(fā)送方的安全以及秘密消息的可達(dá)性。本文提出廣義不經(jīng)意傳輸?shù)姆植际絽f(xié)議，將發(fā)送者的角色分配給多個(gè)服務(wù)器，只要一定數(shù)目的服務(wù)器在線，不經(jīng)意傳輸協(xié)議即可進(jìn)行。協(xié)議應(yīng)用廣義秘密共享模型和檢驗(yàn)值設(shè)置實(shí)現(xiàn)了檢索結(jié)構(gòu)的設(shè)計(jì)，又通過(guò)構(gòu)建和重構(gòu)多項(xiàng)式實(shí)現(xiàn)了發(fā)送者角色的分配以及用戶(hù)和服務(wù)器之間的不經(jīng)意傳輸。由于所用方法僅是多項(xiàng)式計(jì)算和多項(xiàng)式插值算法，因此協(xié)議計(jì)算量和通信負(fù)載都較低。同時(shí)，該協(xié)議建立在秘密共享模型的安全條件下，也能較好地保障發(fā)送方數(shù)據(jù)的安全以及用戶(hù)的隱私。

[1] Rabin M O. How to Exchange Secrets by Oblivious Transfer[R]. Aiken Computation Laboratory, Tech. Rep.: TR-81, 1981.

[2] Kilian J. Founding Cryptography on Oblivious Transfer[C]// Proc. of the 20th Annual ACM Symposium on Theory of Computing. New York, USA: ACM Press, 1988: 20-31.

[3] Yao A C. Protocols for Secure Computation[C]//Proc. of FOCS’82. [S. l.]: IEEE Press, 1982: 160-164.

[4] 張?jiān)弃Q, 朱艷琴. 基于價(jià)格不經(jīng)意傳輸?shù)碾[私保護(hù)交易方案[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2012, 29(5): 35-37.

[5] 王鳳和, 胡予濮, 劉振華. 格基不經(jīng)意傳輸協(xié)議[J]. 通信學(xué)報(bào), 2011, 32(3): 125-130.

[6] 謝 娟, 朱艷琴, 羅喜召. 基于ECC 簽名的接入控制不經(jīng)意傳輸方案[J]. 計(jì)算機(jī)工程, 2010, 36(16): 140-142.

[7] Naor M, Pinkas B. Efficient Oblivious Transfer Protocols[C]// Proc. of SODA’01. [S. l.]: ACM Press, 2001: 448-457.

[8] Nanor M, Pinkas B. Distributed Oblivious Transfer[C]//Proc. of ASIACRYPT’00. Heidelberg, Germany: Springer-Verlag, 2000: 205-219.

[9] Ishai Y, Kushilevitz E. Private Simultaneous Messages Pro- tocols with Applications[C]//Proc. of ISTCS’97. [S. l.]: IEEE Computer Society, 1997: 174-184.

[10] BeimelA, Ishai Y. On the Power of Nonlinear Secret- sharing[C]//Proc. of the 16th Annual Conference on Structure in Complexity Theory. Chicago, USA: IEEE Press, 2001: 188-202.

[11] Christian L F, Ghodosi C H.-out-of-Distributed Oblivious Transfer Protocols in Non-adaptive and Adaptive Settings[C]// Proc.of the 8th International Conference on Information Security Practice and Experience. [S. l.]: IEEE Press, 2012: 126-143.

[12] TamirT. Generalized Oblivious Transfer by Secret Sharing[J]. Designs, Codes and Cryptography, 2011, 58(1): 11-21.

編輯 金胡考

Generalized Oblivious Transfer Protocol in Distributed Setting Based on Secret Sharing

XIE Mi-mi, LIAO Xiao-feng, ZHOU Qing

(College of Computer Science, Chongqing University, Chongqing 400044, China)

For oblivious transfer, distributed settings can better protect the safety of the sender and the accessibility of secret message. So this paper presents a generalized oblivious transfer protocol in distributed setting based on secret sharing, which allows a user to select and retrieve a qualified subset of secret messages according to specific rules set by the sender. This protocol combines generalized secret sharing scheme and construction of polynomials, predefines the retrieve rules of messages by introducing the complement of secret sharing access structure and realizes the distributed setting with construction and reconstruction of polynomials. In the phase of construction, the sender builds three polynomials according to the encrypted messages, keys and verification value and sends the polynomials to the participating servers. The user obtains his requested messages by communicating with predefined number of servers. Analysis result indicates that this protocol is easy to implement with low computation complexity and ensures high efficiency and security as well.

oblivious transfer; secret sharing; distributed model; generalized model; retrieve structure; access structure

1000-3428(2014)03-0184-04

A

TP309

重慶市自然科學(xué)基金資助重點(diǎn)項(xiàng)目(2009BA2024)；輸配電裝備及系統(tǒng)安全與新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室自主研究基金資助項(xiàng)目(2007DA10512709207)。

解咪咪(1987－)，女，碩士研究生，主研方向：信息安全；廖曉峰，教授、博士；周 慶，副教授、博士。

2013-02-01

2013-03-09 E-mail：kaixinmier1106@163.com

10.3969/j.issn.1000-3428.2014.03.038