# Verifiable Rational Secret Sharing Scheme in Mobile Networks

Authors: En Zhang; Peiyan Yuan; Jiao Du
Journal: Mobile Information Systems
 (2015)

---

## Abstract

With the development of mobile network, lots of people now have access to mobile phones and the mobile networks give users ubiquitous connectivity. However, smart phones and tablets are poor in computational resources such as memory size, processor speed, and disk capacity. So far, all existing rational secret sharing schemes cannot be suitable for mobile networks. In this paper, we propose a verifiable rational secret sharing scheme in mobile networks. The scheme provides a noninteractively verifiable proof for the correctness of participants’ share and handshake protocol is not necessary; there is no need for certificate generation, propagation, and storage in the scheme, which is more suitable for devices with limited size and processing power; in the scheme, every participant uses her encryption on number of each round as the secret share and the dealer does not have to distribute any secret share; every participant cannot gain more by deviating the protocol, so rational participant has an incentive to abide by the protocol; finally, every participant can obtain the secret fairly (means that either everyone receives the secret, or else no one does) in mobile networks. The scheme is coalition-resilient and the security of our scheme relies on a computational assumption.


---

## Body

## 1. Introduction

### 1.1. Background

Secret sharing is playing a more and more important role in modern cryptography. In classical (t,n) secret sharing schemes [1, 2], a secret can be shared among n participants. At least t or more participants can reconstruct the secret, but t-1 or fewer participants cannot obtain anything about the secret. Recently, a series of secret sharing schemes were proposed in [3–6]. However, the works in [1–6] cannot prevent the dealer or players from cheating. For example, in Shamir’s scheme, we assume that one party does not broadcast his share, while exactly t-1 other players reveal their shares. He can still reconstruct the secret although his cheating can be detected by the scheme [7–9].Motivated by the desire to develop more realistic models, the cryptographic community has significant interest in exploring protocols for rational secret sharing. Halpern and Teague [10] firstly introduced the notion of rational secret sharing. They pointed out that there exist many Nash equilibriums which, in some sense, are unreasonable. Therefore, they focus on one particular refinement of Nash equilibrium that is determined by iterated deletion of weakly dominated strategies. However, their protocols cannot work for 2 out of 2 secret sharing and require the online dealer. Later, a series of rational secret sharing schemes [11–20] were proposed. However, none of them are fully satisfactory. The works in [11–13] rely on secure multiparty computation which is strong. Kol and Naor’s scheme [14] has information theoretic security. However, their scheme fails to resist against coalitions. The works in [15, 16] require the involvement of some trusted external parties during the reconstruction phase which is difficult to find. The solution in [17] constructs a rational scheme based on repeated games. However, every player has high probability to learn the secret in his last round. The works of Lepinski et al. [19, 20] and Izmalkov et al. [15, 18] can guarantee fairness, prevent coalitions, and eliminate side information. However, their solutions rely on physical assumption such as secure envelopes and ballot boxes. The works in [10–14, 17, 21–25] assume the existence of broadcast channel which is not realistic. The works in [11–13, 19–27] need to exchange public keys associated with certificate management, including revocation, storage and distribution, and the computational cost of certificate verification. Nowadays, with the development of mobile network, a large percent of the world’s population now has access to mobile phones and incredibly fast mobile networks give users ubiquitous connectivity. New devices like smart phones and tablets are providing users with a lot of applications and services and have fundamentally changed our lives. However, smart phones and tablets are poor in computational resources such as processor speed, memory size, and disk capacity. A drawback of public key infrastructure (PKI) is that they are computationally very intensive, which makes them less suitable mobile phones. From the discussion above, it seems clear that all of above schemes cannot work in a mobile system.


### 1.2. Our Results

In this paper, we propose a verifiable rational secret sharing scheme in mobile networks. The major contribution of this work is as follows. We present a new verifiable random function for multiparty case, which provides a noninteractively verifiable proof for the correctness of participants’ share and handshake protocol is not necessary; there is no need for certificate generation, propagation, and storage in the scheme, which is more suitable for devices with limited size and processing power; the public key in our approach is based on each participant’s identity (e.g., telephone number or email address), which can be very much shorter as compared to the 1024 bits public key in RSA cryptosystem; in the scheme, every participant uses her/his encryption on number of each round as the secret share and the dealer does not have to distribute any secret share, which reduce the computational consumption and communicational overhead; the participants do not know whether the current round is a test round or not, and every participant cannot gain more by cheating. Finally, every player can obtain the secret fairly (means that either everyone receives the secret, or else no one does) in mobile networks. To the best of our knowledge, we propose the first rational secret sharing scheme over mobile networks.


### 1.3. Overview

The rest of this paper is organized as follows. In Section2, the preliminary of game theory and cryptography for rational secret sharing are introduced. Section 3 introduces the rational secret scheme in mobile networks. In Section 4, we analyze the new scheme. Finally, we present our conclusions in Section 5.


## 1.1. Background

Secret sharing is playing a more and more important role in modern cryptography. In classical (t,n) secret sharing schemes [1, 2], a secret can be shared among n participants. At least t or more participants can reconstruct the secret, but t-1 or fewer participants cannot obtain anything about the secret. Recently, a series of secret sharing schemes were proposed in [3–6]. However, the works in [1–6] cannot prevent the dealer or players from cheating. For example, in Shamir’s scheme, we assume that one party does not broadcast his share, while exactly t-1 other players reveal their shares. He can still reconstruct the secret although his cheating can be detected by the scheme [7–9].Motivated by the desire to develop more realistic models, the cryptographic community has significant interest in exploring protocols for rational secret sharing. Halpern and Teague [10] firstly introduced the notion of rational secret sharing. They pointed out that there exist many Nash equilibriums which, in some sense, are unreasonable. Therefore, they focus on one particular refinement of Nash equilibrium that is determined by iterated deletion of weakly dominated strategies. However, their protocols cannot work for 2 out of 2 secret sharing and require the online dealer. Later, a series of rational secret sharing schemes [11–20] were proposed. However, none of them are fully satisfactory. The works in [11–13] rely on secure multiparty computation which is strong. Kol and Naor’s scheme [14] has information theoretic security. However, their scheme fails to resist against coalitions. The works in [15, 16] require the involvement of some trusted external parties during the reconstruction phase which is difficult to find. The solution in [17] constructs a rational scheme based on repeated games. However, every player has high probability to learn the secret in his last round. The works of Lepinski et al. [19, 20] and Izmalkov et al. [15, 18] can guarantee fairness, prevent coalitions, and eliminate side information. However, their solutions rely on physical assumption such as secure envelopes and ballot boxes. The works in [10–14, 17, 21–25] assume the existence of broadcast channel which is not realistic. The works in [11–13, 19–27] need to exchange public keys associated with certificate management, including revocation, storage and distribution, and the computational cost of certificate verification. Nowadays, with the development of mobile network, a large percent of the world’s population now has access to mobile phones and incredibly fast mobile networks give users ubiquitous connectivity. New devices like smart phones and tablets are providing users with a lot of applications and services and have fundamentally changed our lives. However, smart phones and tablets are poor in computational resources such as processor speed, memory size, and disk capacity. A drawback of public key infrastructure (PKI) is that they are computationally very intensive, which makes them less suitable mobile phones. From the discussion above, it seems clear that all of above schemes cannot work in a mobile system.


## 1.2. Our Results

In this paper, we propose a verifiable rational secret sharing scheme in mobile networks. The major contribution of this work is as follows. We present a new verifiable random function for multiparty case, which provides a noninteractively verifiable proof for the correctness of participants’ share and handshake protocol is not necessary; there is no need for certificate generation, propagation, and storage in the scheme, which is more suitable for devices with limited size and processing power; the public key in our approach is based on each participant’s identity (e.g., telephone number or email address), which can be very much shorter as compared to the 1024 bits public key in RSA cryptosystem; in the scheme, every participant uses her/his encryption on number of each round as the secret share and the dealer does not have to distribute any secret share, which reduce the computational consumption and communicational overhead; the participants do not know whether the current round is a test round or not, and every participant cannot gain more by cheating. Finally, every player can obtain the secret fairly (means that either everyone receives the secret, or else no one does) in mobile networks. To the best of our knowledge, we propose the first rational secret sharing scheme over mobile networks.


## 1.3. Overview

The rest of this paper is organized as follows. In Section2, the preliminary of game theory and cryptography for rational secret sharing are introduced. Section 3 introduces the rational secret scheme in mobile networks. In Section 4, we analyze the new scheme. Finally, we present our conclusions in Section 5.


## 2. Preliminaries

### 2.1. Basics of Game Theory

We begin by introducing some basic terminology of game theory in this section. For more details, please refer to [28].Game theory aims to help us understand situations in which decision-makers interact. A strategic game consists of three components: (a) a set of players; (b) a set of actions for each player; (c) for each player, preferences over the set of action profiles.Leta=(a1,…,an) be profile of players, ai denote the strategy employed by player Pi, a-i be a strategy profile of all players except for the player Pi, and (ai′,a-i)=(a1,…,ai-1,ai′,ai+1,…,an) denote the strategy vector a with Pi’s strategy changed to ai′; ui(a) represents Pi’s preferences, which rational players wish to maximize.Definition 1 (Nash equilibrium).
LetΓ=({Ai},{ui}i=1n) be a game presented in normal form. A strategy profile a=(a1,…,an)∈A is Nash equilibrium if, for all i and every ai′∈Ai, it holds that (1)uiai′,a-i≤uia.
Generally speaking, Nash equilibrium holds the idea that no rational party has an incentive to deviate from the protocol. Everyone is playing a best response to everyone else and no individual can do strictly better by moving away. The definition of Nash equilibrium is designed to model a steady state among experienced players. In a steady state, no player wishes to change her behavior, considering the other players’ behavior.
In a traditional secret sharing scheme, a player is thought as either honest or malicious. However, in a rational secret sharing scheme, it may make more sense to view the players, not as good or bad, but as rational individuals trying to maximize their own utility [10]. For any player Pi, assume that any rational player prefers to get the secret rather than miss it. And secondarily, prefer that as few as possible of the other players get it.Now, let we introduce the definition of computationalC-immune [13] in which utility functions take the security parameter k as input.Definition 2 (computationalC-immune).
Letσ be an efficient protocol for a computing game and C be a set of coalitions (subsets of players). Let Rt be the set of sequences of random tapes for the first t iterations that do not cause σ to end. A sequence r∈Rt is of the form r=(r1,…,rt) where rs=(r1s,…,rns) and rjs is the random tape used by player j in iteration s.
The protocolσ is computational C-immune if, for every coalition C∈C and every sequence of tapes r0=(r01,…,r0t)∈Rt used by the players in the first t round, there exists a negligible function ε(k) such that, for every player i∈C, every efficient (deviating) joint strategy σC′ for players in C, and every efficient joint strategy τ-C for players in N/C implementing σ-C, it holds that(2)Euiτ-Ck,σCk+εk≥Euiτ-Ck,σC′k.


### 2.2. Cryptographic Terminology

Definition 3 (bilinear pairing).
LetG1 and G2 be multiplicative groups of prime order p. g is the generator of G1. A bilinear pairings is a map e:G1×G1→G2 with the following properties.(1)
Bilinear: for allu,v∈G1 and all a,b∈Z, one has e(ua,vb)=e(u,v)ab.(2)
Nondegenerate:e(g,g)≠1.(3)
Computable: there is an efficient algorithm to computee(u,v) for all u and v∈G1.We describe decisional bilinear Diffie-Hellman inversion assumption below.
Given(g,gx,…,g(xq)) as input, to distinguish e(g,g)1/x from random. An algorithm A has advantage ε in solving the q-DBDHI problem if (3)
Pr
⁡
A
g
,
g
x
,
…
,
g
x
q
,
e
g
,
g
1
/
x
=
1
-
Pr
⁡
A
g
x
,
…
,
g
x
q
,
Γ
=
1
≤
ε
,where x∈Zp∗ and Γ∈G2.
We say that the(t,q,ε)-DBDHI assumption holds in G1, if no t-time algorithm A has advantage at least ε in solving the q-DBDHI problem in G1.


### 2.3. Verifiable Random Function from Identity-Based Key Encapsulation (IB-KEM)

Verifiable random function (VRF) was firstly introduced by Micali et al. [29]. A VRF is a pseudorandom function that provides a noninteractively verifiable proof for the correctness of its output, and the VRF has many useful applications. References [29–32], respectively, constructed a VRF. Next we briefly recall the VRF from a VRF-suitable IB-KEM [32].The IB-KEM Scheme. An identity-based key encapsulation mechanism (IB-KEM) scheme allows a sender and a receiver to agree on a random session key K. And it is defined by four algorithms: Setup(1k) takes a security parameter as input and outputs a master key pairs (mpk, msk); KeyDer(msk, ID) uses the master secret key to compute skID for identity ID; Encap(mpk,ID) computes a random session key K and a ciphertext C; Decap(C,skID) allows the receiver to decapsulate C to get back a session key K. An VRF-suitable IB-KEM scheme [33] is defined by the following algorithms.(i)
Setup(1k) is a probabilistic algorithm that takes in input a security parameter k and outputs a master public key mpk and a master secret key msk. Let G1,G2 be bilinear groups of prime order q. Additionally, let e: G1×G1→G2 denote the bilinear map. The description of G1 contains a generator g∈G1. Then the algorithm picks a random s←Zp∗, sets h=gs, and outputs a master key pairs (mpk=(g,h),msk=s).(ii)
KeyDer(msk, ID): the key derivation algorithm uses the master secret key to compute a secret keyskID=g1/(s+ID) for identity ID.(iii)
Encap(mpk, ID): the encapsulation algorithm picks a randomt←Zq and computes a random session key K=e(g,g)t using (mpk, ID). Moreover it uses (mpk, ID) to computes a ciphertext C=(gsgID)t encrypted under the identity ID.(iv)
Decap(C, skID) allows the possessor of skID to compute a session key K from a ciphertext C as follows: K=e(C,skID).The VRF (Gen, Func, and Ver) Construction Is as follows
(i)
G
e
n
(
1
k
) runs (mpk,msk)←Setup(1k), chooses an arbitrary identity ID0∈ID, where ID is the identity space, and computes C0←Encap(mpk,ID0). Then it sets vpk=(mpk,C0) and vsk=msk.
(ii)
F
u
n
c
v
s
k
(
x
) computes πx=(skx,auxx)=KeyDer(msk,x) and y=Decap(C0,πx). It returns (y,πx) where y is the output and πx is the proof.
(iii)
V
e
r
(
v
p
k
,
x
,
y
,
π
x
) first checks if πx is a valid proof for x by computing (C,K)=Encap(mpk,x,auxx) and checking if K=Decap(C,πx). Then it checks the validity of y by testing if Decap(C0,πx)=y. If both the tests are true, then the algorithm returns 1, otherwise it returns 0.With a modification, we extend the VRF from a VRF-suitable IB-KEM [32] to multiparty case, and this can be used in our rational secret sharing schemes. Let p1,…,pn be n participants, IDi∈ID(i=1,…,n) be the identity of pi, where ID is the identity space, and di be the private key of pi.(i)
Gen(1k) takes a security parameter k, returns mpki,mski and computes C0i←Encap(mpki,IDi). Then it sets vpki=(mpki,C0i) and di=mski.(ii)
Funcdi(x) computes πdi(x)=(skxi,auxxi)=KeyDer(mski,x) and Edi(x)=Decap(Ci,πx). It returns (Edi(x),πdi(x)) where the VRF output is Edi(x) and πdi(x) is the proof.(iii)
VER(vpki,x,Edi(x),πdi(x)) checks if πdi(x) is a valid proof by computing (Ci,Ki)=Encap(mpki,x,auxxi) and checking if Ki=Decap(Ci,πdi(x)). Then it checks the validity of y by testing if Decap(C0i,πdi(x))=Edi(x). If both the tests are true, then the algorithm returns 1, otherwise it returns 0.


### 2.4. The Model of Security

Init. The adversary declares the identity set φ=(ID1,ID2,…,IDn) that he wants to be challenged.Setup. The challenger runs the setup phase of the algorithm and tells the adversary the public parameter.Phase 1. The adversary is allowed to issue queries for private keys for many identities χi, where χi∩φ<t.Challenge. The adversary output a message x∗. The challenger flips a random coin b and obtains a session key Kb. If b=0, then Kb is a correct form, otherwise Kb is random. Finally, it sends Kb to the adversary.Phase 2. This goes exactly as phase 1.Guess. The adversary outputs a guess b′ of b. The adversary wins if b′=b.We define the advantage of an adversary in this game asPr[b′=b]-1/2.


## 2.1. Basics of Game Theory

We begin by introducing some basic terminology of game theory in this section. For more details, please refer to [28].Game theory aims to help us understand situations in which decision-makers interact. A strategic game consists of three components: (a) a set of players; (b) a set of actions for each player; (c) for each player, preferences over the set of action profiles.Leta=(a1,…,an) be profile of players, ai denote the strategy employed by player Pi, a-i be a strategy profile of all players except for the player Pi, and (ai′,a-i)=(a1,…,ai-1,ai′,ai+1,…,an) denote the strategy vector a with Pi’s strategy changed to ai′; ui(a) represents Pi’s preferences, which rational players wish to maximize.Definition 1 (Nash equilibrium).
LetΓ=({Ai},{ui}i=1n) be a game presented in normal form. A strategy profile a=(a1,…,an)∈A is Nash equilibrium if, for all i and every ai′∈Ai, it holds that (1)uiai′,a-i≤uia.
Generally speaking, Nash equilibrium holds the idea that no rational party has an incentive to deviate from the protocol. Everyone is playing a best response to everyone else and no individual can do strictly better by moving away. The definition of Nash equilibrium is designed to model a steady state among experienced players. In a steady state, no player wishes to change her behavior, considering the other players’ behavior.
In a traditional secret sharing scheme, a player is thought as either honest or malicious. However, in a rational secret sharing scheme, it may make more sense to view the players, not as good or bad, but as rational individuals trying to maximize their own utility [10]. For any player Pi, assume that any rational player prefers to get the secret rather than miss it. And secondarily, prefer that as few as possible of the other players get it.Now, let we introduce the definition of computationalC-immune [13] in which utility functions take the security parameter k as input.Definition 2 (computationalC-immune).
Letσ be an efficient protocol for a computing game and C be a set of coalitions (subsets of players). Let Rt be the set of sequences of random tapes for the first t iterations that do not cause σ to end. A sequence r∈Rt is of the form r=(r1,…,rt) where rs=(r1s,…,rns) and rjs is the random tape used by player j in iteration s.
The protocolσ is computational C-immune if, for every coalition C∈C and every sequence of tapes r0=(r01,…,r0t)∈Rt used by the players in the first t round, there exists a negligible function ε(k) such that, for every player i∈C, every efficient (deviating) joint strategy σC′ for players in C, and every efficient joint strategy τ-C for players in N/C implementing σ-C, it holds that(2)Euiτ-Ck,σCk+εk≥Euiτ-Ck,σC′k.


## 2.2. Cryptographic Terminology

Definition 3 (bilinear pairing).
LetG1 and G2 be multiplicative groups of prime order p. g is the generator of G1. A bilinear pairings is a map e:G1×G1→G2 with the following properties.(1)
Bilinear: for allu,v∈G1 and all a,b∈Z, one has e(ua,vb)=e(u,v)ab.(2)
Nondegenerate:e(g,g)≠1.(3)
Computable: there is an efficient algorithm to computee(u,v) for all u and v∈G1.We describe decisional bilinear Diffie-Hellman inversion assumption below.
Given(g,gx,…,g(xq)) as input, to distinguish e(g,g)1/x from random. An algorithm A has advantage ε in solving the q-DBDHI problem if (3)
Pr
⁡
A
g
,
g
x
,
…
,
g
x
q
,
e
g
,
g
1
/
x
=
1
-
Pr
⁡
A
g
x
,
…
,
g
x
q
,
Γ
=
1
≤
ε
,where x∈Zp∗ and Γ∈G2.
We say that the(t,q,ε)-DBDHI assumption holds in G1, if no t-time algorithm A has advantage at least ε in solving the q-DBDHI problem in G1.


## 2.3. Verifiable Random Function from Identity-Based Key Encapsulation (IB-KEM)

Verifiable random function (VRF) was firstly introduced by Micali et al. [29]. A VRF is a pseudorandom function that provides a noninteractively verifiable proof for the correctness of its output, and the VRF has many useful applications. References [29–32], respectively, constructed a VRF. Next we briefly recall the VRF from a VRF-suitable IB-KEM [32].The IB-KEM Scheme. An identity-based key encapsulation mechanism (IB-KEM) scheme allows a sender and a receiver to agree on a random session key K. And it is defined by four algorithms: Setup(1k) takes a security parameter as input and outputs a master key pairs (mpk, msk); KeyDer(msk, ID) uses the master secret key to compute skID for identity ID; Encap(mpk,ID) computes a random session key K and a ciphertext C; Decap(C,skID) allows the receiver to decapsulate C to get back a session key K. An VRF-suitable IB-KEM scheme [33] is defined by the following algorithms.(i)
Setup(1k) is a probabilistic algorithm that takes in input a security parameter k and outputs a master public key mpk and a master secret key msk. Let G1,G2 be bilinear groups of prime order q. Additionally, let e: G1×G1→G2 denote the bilinear map. The description of G1 contains a generator g∈G1. Then the algorithm picks a random s←Zp∗, sets h=gs, and outputs a master key pairs (mpk=(g,h),msk=s).(ii)
KeyDer(msk, ID): the key derivation algorithm uses the master secret key to compute a secret keyskID=g1/(s+ID) for identity ID.(iii)
Encap(mpk, ID): the encapsulation algorithm picks a randomt←Zq and computes a random session key K=e(g,g)t using (mpk, ID). Moreover it uses (mpk, ID) to computes a ciphertext C=(gsgID)t encrypted under the identity ID.(iv)
Decap(C, skID) allows the possessor of skID to compute a session key K from a ciphertext C as follows: K=e(C,skID).The VRF (Gen, Func, and Ver) Construction Is as follows
(i)
G
e
n
(
1
k
) runs (mpk,msk)←Setup(1k), chooses an arbitrary identity ID0∈ID, where ID is the identity space, and computes C0←Encap(mpk,ID0). Then it sets vpk=(mpk,C0) and vsk=msk.
(ii)
F
u
n
c
v
s
k
(
x
) computes πx=(skx,auxx)=KeyDer(msk,x) and y=Decap(C0,πx). It returns (y,πx) where y is the output and πx is the proof.
(iii)
V
e
r
(
v
p
k
,
x
,
y
,
π
x
) first checks if πx is a valid proof for x by computing (C,K)=Encap(mpk,x,auxx) and checking if K=Decap(C,πx). Then it checks the validity of y by testing if Decap(C0,πx)=y. If both the tests are true, then the algorithm returns 1, otherwise it returns 0.With a modification, we extend the VRF from a VRF-suitable IB-KEM [32] to multiparty case, and this can be used in our rational secret sharing schemes. Let p1,…,pn be n participants, IDi∈ID(i=1,…,n) be the identity of pi, where ID is the identity space, and di be the private key of pi.(i)
Gen(1k) takes a security parameter k, returns mpki,mski and computes C0i←Encap(mpki,IDi). Then it sets vpki=(mpki,C0i) and di=mski.(ii)
Funcdi(x) computes πdi(x)=(skxi,auxxi)=KeyDer(mski,x) and Edi(x)=Decap(Ci,πx). It returns (Edi(x),πdi(x)) where the VRF output is Edi(x) and πdi(x) is the proof.(iii)
VER(vpki,x,Edi(x),πdi(x)) checks if πdi(x) is a valid proof by computing (Ci,Ki)=Encap(mpki,x,auxxi) and checking if Ki=Decap(Ci,πdi(x)). Then it checks the validity of y by testing if Decap(C0i,πdi(x))=Edi(x). If both the tests are true, then the algorithm returns 1, otherwise it returns 0.


## 2.4. The Model of Security

Init. The adversary declares the identity set φ=(ID1,ID2,…,IDn) that he wants to be challenged.Setup. The challenger runs the setup phase of the algorithm and tells the adversary the public parameter.Phase 1. The adversary is allowed to issue queries for private keys for many identities χi, where χi∩φ<t.Challenge. The adversary output a message x∗. The challenger flips a random coin b and obtains a session key Kb. If b=0, then Kb is a correct form, otherwise Kb is random. Finally, it sends Kb to the adversary.Phase 2. This goes exactly as phase 1.Guess. The adversary outputs a guess b′ of b. The adversary wins if b′=b.We define the advantage of an adversary in this game asPr[b′=b]-1/2.


## 3. The Rational Secret Sharing Scheme

### 3.1. System Parameters

Letp1,…,pn be n participants and l be the secret. Assume IDi∈ID(i=1,…,n) is the identity of pi, where ID∈Zp∗ is the identity space and h:{0,1}∗→Zp∗ is a collision resistance hash function. Let di be the private key of pi.


### 3.2. Protocol for Sharing Phase

Step 1.
The dealer chooses an integerrreal∈Zp∗ according to a geometric distribution with parameter λ. We discuss how to set λ below. The dealer computes Gen(1k) and obtains di.Step 2.
Choose a primep and construct two (n-1) degree polynomials. One is W(x) with the knowledge of n pairs of (ID1∥rreal,Ed1(rreal)),…,(IDn∥rreal,Edn(rreal)) as (4). The other is W′(x) with the knowledge of n pairs of (ID1∥(rreal+1),Ed1(rreal+1)),…,IDn∥rreal+1,Ednrreal+1 as (5):(4)Wx=∑i=1nEdirreal·∏j=1,j≠inx-hIDj∥rrealhIDi∥rreal-hIDj∥rrealmod⁡p,(5)W′x=∑i=1nEdirreal+1·∏j=1,j≠inx-hIDj∥rreal+1hIDi∥rreal+1-hIDj∥rreal+1mod⁡p=a0rreal+1+a1rreal+1x+a2rreal+1x2+⋯+an-1rreal+1xn-1,(6)letMrreal=W0,(7)value=l⊕Mrreal.Step 3.
The dealer chooses then-t minimum integers m1,…,mn-t from [p,q-1]-(IDi∥r) for r=1,2,…,rreal and computes W(mk) and W′(mk) for k=1,2,…,n-t.Step 4.
The dealer publishes the values ((mk,W(mk),(mk,W′(mk)) for k=1,2,…,n-t, value and h(ajrreal+1) for j=0,1,…,n-1), and sends di to pi.


### 3.3. Protocols for Reconstruction Phase

LetT={pa1,pa2,…,pat} be the set of the t active participants and (Edai(r), πdai(r)) be the share of pai(1≤i≤t). In each iteration (r=0,1,…) the players execute the following steps.Step 1.
Whenr≡i(modt), each of the t active participants sends her share in the order pai+1,pai+2,…,pat,pa1,pa2,…,pai for 0≤i≤t-1.Step 2.
p
a
j
∈
T receives the share from pai∈T. If VER(vpki,r,Edai(r),πdai(r))=0, πdai(r) is an invalid proof of Edai(r), then, with the knowledge of t pairs of (IDa1∥(r-1),Eda1(r-1)),…,(IDat∥(r-1),Edat(r-1)) and n-t pairs of (m1,W(m1)),…,(mn-t,W(mn-t)), the (n-1) degree polynomial B(x) can be uniquely determined as follows:(8)Bx=∑i=1tEdair-1·∏j=1,j≠itx-hIDaj∥r-1hIDai∥r-1-hIDaj∥r-1·∏j=1n-tx-mihIDai∥r-1-mi+∑i=1n-tWmi·∏j=1,j≠in-tx-mjmi-mj∏j=1tx-hIDaj∥r-1mi-hIDaj∥r-1mod⁡p.We let Mr-1=B(0). The secret can be obtained as l′=value⊕Mr-1 and then output l′ and terminate the protocols. If VER(vpki,r,Edai(r),πdai(r))=1, πdai(r) is a valid proof of Edai(r), then the protocol continues.Step 3.
With the knowledge oft pairs of ((IDa1∥r),Eda1(r)),…,((IDat∥r),Edat(r)) and n-t pairs of (m1,W′(m1)),…,(mn-t,W′(mn-t)), the (n-1) degree polynomial B′(x) can be uniquely determined as follows:(9)B′x=∑i=1tEdair∏j=1,j≠itx-hIDaj∥rhIDai∥r-hIDaj∥r·∏j=1n-tx-mihIDai∥r-mi+∑i=1n-tW′mi·∏j=1,j≠in-tx-mjmi-mj∏j=1tx-hIDaj∥rdai-hIDaj∥rmod⁡p=b0r+b1rx+b2rx2+⋯+bn-1rxn-1.Step 4.
Ifh(bjr)≠h(ajrreal+1) for j=0,1,…,n-1 then the protocol goes to next iteration, else if h(bjr)=h(ajrreal+1), then r=rreal+1, with the knowledge of t pairs of ((IDa1∥rreal),Eda1(rreal)),…,((IDat∥rreal),Edat(rreal)) and n-t pairs of (m1,W(m1)),…,(mn-t,W(mn-t)), the (n-1) degree polynomial Breal(x) can be uniquely determined as follows:(10)Brealx=∑i=1tEdairreal·∏j=1,j≠itx-hIDaj∥rrealhIDai∥rreal-hIDaj∥rreal·∏j=1n-tx-mihIDai∥rreal-mi+∑i=1n-tWmi·∏j=1,j≠in-tx-mjmi-mj∏j=1tx-hIDaj∥rrealdai-hIDaj∥rrealmod⁡p.Let Mrreal=Breal(0). The secret can be obtained as l=value⊕Mrreal. Then output l and terminate the protocols.


## 3.1. System Parameters

Letp1,…,pn be n participants and l be the secret. Assume IDi∈ID(i=1,…,n) is the identity of pi, where ID∈Zp∗ is the identity space and h:{0,1}∗→Zp∗ is a collision resistance hash function. Let di be the private key of pi.


## 3.2. Protocol for Sharing Phase

Step 1.
The dealer chooses an integerrreal∈Zp∗ according to a geometric distribution with parameter λ. We discuss how to set λ below. The dealer computes Gen(1k) and obtains di.Step 2.
Choose a primep and construct two (n-1) degree polynomials. One is W(x) with the knowledge of n pairs of (ID1∥rreal,Ed1(rreal)),…,(IDn∥rreal,Edn(rreal)) as (4). The other is W′(x) with the knowledge of n pairs of (ID1∥(rreal+1),Ed1(rreal+1)),…,IDn∥rreal+1,Ednrreal+1 as (5):(4)Wx=∑i=1nEdirreal·∏j=1,j≠inx-hIDj∥rrealhIDi∥rreal-hIDj∥rrealmod⁡p,(5)W′x=∑i=1nEdirreal+1·∏j=1,j≠inx-hIDj∥rreal+1hIDi∥rreal+1-hIDj∥rreal+1mod⁡p=a0rreal+1+a1rreal+1x+a2rreal+1x2+⋯+an-1rreal+1xn-1,(6)letMrreal=W0,(7)value=l⊕Mrreal.Step 3.
The dealer chooses then-t minimum integers m1,…,mn-t from [p,q-1]-(IDi∥r) for r=1,2,…,rreal and computes W(mk) and W′(mk) for k=1,2,…,n-t.Step 4.
The dealer publishes the values ((mk,W(mk),(mk,W′(mk)) for k=1,2,…,n-t, value and h(ajrreal+1) for j=0,1,…,n-1), and sends di to pi.


## 3.3. Protocols for Reconstruction Phase

LetT={pa1,pa2,…,pat} be the set of the t active participants and (Edai(r), πdai(r)) be the share of pai(1≤i≤t). In each iteration (r=0,1,…) the players execute the following steps.Step 1.
Whenr≡i(modt), each of the t active participants sends her share in the order pai+1,pai+2,…,pat,pa1,pa2,…,pai for 0≤i≤t-1.Step 2.
p
a
j
∈
T receives the share from pai∈T. If VER(vpki,r,Edai(r),πdai(r))=0, πdai(r) is an invalid proof of Edai(r), then, with the knowledge of t pairs of (IDa1∥(r-1),Eda1(r-1)),…,(IDat∥(r-1),Edat(r-1)) and n-t pairs of (m1,W(m1)),…,(mn-t,W(mn-t)), the (n-1) degree polynomial B(x) can be uniquely determined as follows:(8)Bx=∑i=1tEdair-1·∏j=1,j≠itx-hIDaj∥r-1hIDai∥r-1-hIDaj∥r-1·∏j=1n-tx-mihIDai∥r-1-mi+∑i=1n-tWmi·∏j=1,j≠in-tx-mjmi-mj∏j=1tx-hIDaj∥r-1mi-hIDaj∥r-1mod⁡p.We let Mr-1=B(0). The secret can be obtained as l′=value⊕Mr-1 and then output l′ and terminate the protocols. If VER(vpki,r,Edai(r),πdai(r))=1, πdai(r) is a valid proof of Edai(r), then the protocol continues.Step 3.
With the knowledge oft pairs of ((IDa1∥r),Eda1(r)),…,((IDat∥r),Edat(r)) and n-t pairs of (m1,W′(m1)),…,(mn-t,W′(mn-t)), the (n-1) degree polynomial B′(x) can be uniquely determined as follows:(9)B′x=∑i=1tEdair∏j=1,j≠itx-hIDaj∥rhIDai∥r-hIDaj∥r·∏j=1n-tx-mihIDai∥r-mi+∑i=1n-tW′mi·∏j=1,j≠in-tx-mjmi-mj∏j=1tx-hIDaj∥rdai-hIDaj∥rmod⁡p=b0r+b1rx+b2rx2+⋯+bn-1rxn-1.Step 4.
Ifh(bjr)≠h(ajrreal+1) for j=0,1,…,n-1 then the protocol goes to next iteration, else if h(bjr)=h(ajrreal+1), then r=rreal+1, with the knowledge of t pairs of ((IDa1∥rreal),Eda1(rreal)),…,((IDat∥rreal),Edat(rreal)) and n-t pairs of (m1,W(m1)),…,(mn-t,W(mn-t)), the (n-1) degree polynomial Breal(x) can be uniquely determined as follows:(10)Brealx=∑i=1tEdairreal·∏j=1,j≠itx-hIDaj∥rrealhIDai∥rreal-hIDaj∥rreal·∏j=1n-tx-mihIDai∥rreal-mi+∑i=1n-tWmi·∏j=1,j≠in-tx-mjmi-mj∏j=1tx-hIDaj∥rrealdai-hIDaj∥rrealmod⁡p.Let Mrreal=Breal(0). The secret can be obtained as l=value⊕Mrreal. Then output l and terminate the protocols.


## 4. Proof of Security

In this section, the poof of the security is discussed.Theorem 4.
If an adversary can break our scheme, then one can build a simulator to solve theq-DBDHI assumption with a nonnegligible advantage.Proof.
We assume there exists an adversaryA that has nonnegligible advantage ε(k) into breaking the protocol. Then we can build a simulator B which is able to break the q-DBDHI assumption with nonnegligible advantage.
Input to the Reduction. Algorithm B receives a tuple (g,gα,…,g(αq),Γ)∈G1q+1×G2, and output 1 if Γ=e(g,g)1/α, or 0 otherwise.
Key Generation. Assume that A tries to guess the challenge message x0∈Zp∗. Let s=α-x0. Using the binomial theorem, it computes (g,gs,…,g(sq)). Then B define f(z)=∏w≠x0w∈zq(z+w)=∑i=0q-1cizi and compute the new base g′=gf(s)=∏i=0q-1gsici. Finally it computes h=(g′)s=∏i=1q-1gsici-1, picks a random t, and sets C0=(g′)t. Then it gives g′,h,C0 as the public key to A.
Phase 1. The adversary A is allowed to issue queries for private keys for many identities χi, where χi∩φ<t and φ=(ID1,ID2,…,IDn). Consider the ith query (1≤i<q) on message xi. If xi=x0, then B fails. Otherwise B can compute the secret key as follows. Firstly it defines fi(z)=f(z)/(z+xi)=∑i=0q-2ziνi. Then it computes skxi=(g′)1/(s+xi)=gfi(s)=∑i=0q-2gsivi and returns it to A as the private key of χi. With the knowledge of t pairs of ((IDa1∥r),Eda1(r)),…,((IDat∥r),Edat(r)) and n-t pairs of (m1,W′(m1)),…,(mn-t,W′(mn-t)), the simulator can construct the (n-1) degree polynomial B′(x) by using the Lagrange interpolation polynomial. However, the coefficient of the B′(x) is identical to that of the original scheme.
Challenge. The adversary A output a message x∗. If x∗≠x0, then B fails. Otherwise, the challenger can compute a session key Kb in the following way. Let f′(z)=f(z)/(z+x0)-γ/(z+x0)=∑i=0q-2ziγi and compute Z0=(∏i=0q-1∏j=0q-2e(gsi,gsj))(∏m=0q-2e(g,gsm)γγm)=e(g,g)(f(s)-γ2)/α. The simulator flips a random coin, b, and sets a session key Kb=(Zγ2·Z0)t, if b=0, then Z=e(g,g)1/α and Kb=e(g′,g′)t/(s+xi) is a correct form. Otherwise Z is a random, and so is Kb. Finally, it sends Kb to the adversary.
Phase 2. This goes exactly as phase 1.
Guess. The adversary A outputs a guess b′ of b. B returns b′ as its guess as well.
For the sake of contradiction, suppose there exists a probabilistic polynomial time attackerA can break the protocol with probability 1/2+ε(k). Then we can build a simulator B which is able to break the q-DBDHI assumption with probability 1/2+ε(k). (The output of B is the same as the output of A.) Because the q-DBDHI assumption is hard to be solved, there is no any adversary A that has nonnegligible advantage ε(k) into breaking the protocol. This completes the proof.Theorem 5.
The above rational secret sharing scheme is computationalC-immune, and rational participant has an incentive to abide by the protocol.Proof.
Given then-t public values W(mk),W′(mk), the two (n-1) degree polynomials W(x),W′(x) cannot be constructed by anyone. So, an adversary can learn nothing about the secret. Any t-1 or fewer participants cannot obtain the secret too. In the scheme, any rational participant can detect and determine who is cheating. Suppose that paj∈T receives the share from pai∈T. If VER(vpki,r,Edai(r),πdai(r))=0, πdai(r) is an invalid proof of Edai(r), and paj terminates the protocols. If VER(vpki,r,Edai(r),πdai(r))=1, πdai(r) is a valid proof of Edai(r), and paj continues the protocols. Assume that Pi who is the member of the collusion C does not know which round is rreal. He can only guess the secret and get Ui+ with probability β, if the collusion C does not participate in the scheme. On the contrary, he can guess a wrong secret and get Ui- with probability 1-β. So, when the collusion C does not participate in the protocols, the expected utility of Pi is as in(11)EUiguess=β∗Ui++1-β∗Ui-.The participant Pi will get utility Ui+, if the collusion C participates in the protocols and aborts in real round with probability λ. Otherwise, the participant Pi’s utility is E(Uiguess). Therefore, when the collusion C deviates, the expected utility of Pi is at most(12)λ∗Ui++1-λ∗EUiguess.When the collusion C abides by the protocol, the utility of the participant Pi is Ui. So, rational collusion C has an inventive not to deviate from the protocol if the protocol satisfies(13)Ui>λ∗Ui++1-λ∗EUiguess.We denote λ′ the probability that players in C can only have a negligible advantage over λ. There exists a negligible function ξ(k) such that for every k it holds that (14)λ′≤λ+ξk.We let U∗′ denote the utility when allowing for the computationally secure. Then (15)U∗′=λ′Ui++1-λ′∗EUiguess=λ′Ui+-EUiguess+EUiguess≤λ+ξkUi+-EUiguess+EUiguess≤λ∗Ui++1-λ∗EUiguess+ξkUi+-EUiguess<Ui+εk.That is for every iteration and for all C⊂[n] with C≤t-1, all i∈C, and any aC′∈Δ(AC), no information about the secret is revealed. So, the scheme is computational C-immune and rational player has an incentive to abide by the protocol.


## 5. Comparison

We compare the efficiency and security with previous rational secret sharing scheme as follows.The work of Halpern and Teague [10] assumes the existence of simultaneous broadcast channels (SBC). Their schemes fail to resist against coalitions and have expected round complexity O(5/α3). The works in [11–13] rely on secure multiparty computation which are inefficient. The works of Kol and Naor [14] have shown how to avoid simultaneous broadcast, at the cost of increasing the round complexity. In addition, the scheme is not collusion-free, and the round complexity is O(n/β) and the works in [15, 16] require the involvement of some trusted external parties during the reconstruction phase which is difficult to find. The round complexity of Maleka et al. [17] is O(n2). The works of Izmalkov et al. [18] and Lepinski et al. [19, 20] rely on a physical assumption such as secure envelopes and ballot boxes. The works in [10–14, 17, 21–25] assume the existence of broadcast channel which is not realistic. The works in [11–13, 19–27] need handshake protocol and exchange public keys associated with certificate management, including distribution, storage, revocation, and the computational cost of certificate verification, which are relatively expensive and limit their practical application to mobile networks. In contrast with prior schemes, the round complexity is O(1/λ) (the value of α, β, and λ is roughly the same) in our scheme, and we do not assume multiparty computations, physical assumption, or trust party, which is more practical; the scheme provides a noninteractively verifiable proof for the correctness of participants’ share and handshake protocol is not necessary; there is no need for certificate generation, propagation, and storage in the scheme, which is more suitable for devices with limited size and processing power; the public key in our approach is based on each participant’s identity which can be very much shorter as compared to the 1024 bits public key in RSA cryptosystem; in the scheme, every participant uses her encryption on number of each round as the secret share and the dealer does not have to distribute any secret share, which reduce the computational consumption and communicational overhead; the scheme can withstand the conspiracy attack and no player of the coalition C can do better, even if the whole coalition C cheats.


## 6. Conclusions

We propose a rational secret sharing scheme in mobile networks. The scheme, without needing to resort to broadcast channel, eliminates the online certificate authority and simplifies key management, which is more practical for devices of limited size and processing power, such as mobile phones. In addition, the scheme assumes neither the availability of a trusted party nor multiparty computations in the reconstruction phase. Moreover, the scheme can withstand the conspiracy attack and no player of the coalitionC can do better, even if the whole coalition C cheats. So, rational players have no incentive to cheat in the scheme, and, finally, every player can obtain the secret fairly in mobile networks.



---

*Source: 462345-2015-06-29.xml*