# A Group Identification Protocol with Leakage Resilience of Secret Sharing Scheme

Authors: Ping Li; Shengjun Li; Hongyang Yan; Lishan Ke; Teng Huang; Alzubair Hassan
Journal: Complexity
 (2020)

---

## Abstract

Secret sharing has been study for many years and has had a number of real-word applications. There are several methods to construct the secret-sharing schemes. One of them is based on coding theory. In this work, we construct a secret-sharing scheme that realizes an access structure by using linear codes, in which any element of the access structure can reconstruct the secret key. We prove that our scheme is a multiprover zero-knowledge proof system in the random oracle model, which shows that a passive adversary gains no information about the secret key. Our scheme is also a leakage-resilient secret-sharing scheme (LRSS) in the bounded-leakage model, which remain provably secure even if the adversary learns a bounded amount of leakage information about their secret key. As an application, we propose a new group identification protocol (GID-scheme) from our LRSS. We prove that our GID-scheme is a leakage-resilient scheme. In our leakage-resilient GID-scheme, the verifier believes the validity of qualified group members and toleratesl bits of adversarial leakage in the distribution protocol, whereas for unqualified group members, the verifier cannot believe their valid identifications in the proof protocol.


---

## Body

## 1. Introduction

The secret-sharing scheme, originally and independently introduced by Shamir [1] and Blakley [2], is a method in which a dealer selects a secret and distributes it as shares among a set of parties in the distribution stage. Only the predefined subsets of parties can reconstruct the secret from their shares, while others learning nothing about the secret in the reconstruction stage. These subsets are called qualified, and the monotonic collection of qualified subsets is called an access structure of the secret-sharing scheme. As a basic primitive in cryptography, the secret-sharing scheme has been used widely in security applications and protocols, such as threshold cryptography [3], secure multiparty computation [4], cloud computing [5–7], oblivious transfer [8], and access control [9].In general, in the secret-sharing scheme (n parties and access structures are known in advance), there are two types of access structures: threshold and nonthreshold. In the threshold access structure, at least t=tn qualified parties can reconstruct the secret key. In [10], the authors constructed an evolving secret-sharing scheme for a dynamic threshold access structure. In their scheme, the size of the qualified set increases if the number of parties increases. However, in the nonthreshold access structure, the size of the qualified set is not limited, i.e., any collection of the qualified subsets can reconstruct the secret key. If the nonthreshold access structure (a small monotonic span program) can be described, then an efficient secret-sharing scheme is realized [11]. For instance, given the forbidden graph access structure, Beimel et al. [12] proposed a linear secret-sharing scheme for forbidden graph access structures.


### 1.1. Secret-Sharing Scheme from Linear Codes

There is a natural correspondence between linear codes and a secret-sharing scheme. McEliece and Sarwate noted the relationship between Shamir–Blakley’s secret-sharing scheme and Reed–Solomon codes in [13]. Since then, several secret-sharing schemes have been constructed in terms of linear error-correcting codes [14–16]. To construct a secret-sharing scheme from linear codes, Massey pointed out the relationship between the access structure and the minimal codewords of the dual code of the underlying code [17, 18]. Therefore, when designing a secret-sharing scheme based on linear codes, it is necessary to consider the open problem of how to determine the minimal codewords for certain linear codes. In this work, we assume that the codes and their dual codes are efficiently encodable and decodable, respectively. In this work, the relationship between secret-sharing scheme and linear codes is presented in Section 2.1.


### 1.2. Leakage-Resilient Secret-Sharing Scheme

In the application of secret-sharing scheme realizing the access structure, some parties exist that might cheat others by providing false secret keys under the sharing control, and the information about the secret key is leaked. To avoid this situation, it is necessary to consider the challenge of protecting the secret key of the dealer and the shares of parties againstinformation leakage, i.e., in previous work, most researchers generally used leakage-resilient cryptographic primitives [19–24] and leakage-resilient devices [25, 26] to protect the security of the secret key. The cryptographic primitives and computational devices are said to be leakage-resilient if it remains secure in the presence of bounded-leakage of an internal (secret) state. In the work presented in [27], the authors defined the assumption that only the computation leaks information. In other words, there is no leakage without computation. However, this assumption does not guarantee security in the model because cold-boot attacks [28] may work [29]. Therefore, motivated by the work of Dziembowski and Pietrzak [30], we describe the leakage assumptions considered in this work as follows:Independent leakage: the computation can be organized into rounds, and the leaks in each round are independentBounded leakage: in each round, the number of leakages are bound to some parameters,whereas the total leakage bit is bounded bylBounded domain: in fact, the leakage function takes as inputonly the secret state during the invocationFormally, in the bounded-leakage model, an attacker can repeatedly and adaptively access to aleakage oracle and learn information about the secret key, as long as the total number of information leaked is bounded by some parameter l. An attacker chooses a sequence of polynomial-time-computable leakage functions fi:0,1sk⟶0,1lii=1n and obtains fstate, where state is the party P’s secret state information at the end beginning of each round i and ∑ili≤1.


### 1.3. Our Contributions

In this work, we construct a secret-sharing scheme for a given access structure arising from linear correcting codes. According to the definitions of security models and attack models, we prove that our protocol is ann-prover zero-knowledge proof system in the random oracle model, which reveals that the secret key can be shared repeatedly without leaking any information in the case of a passive attacker. Additionally, our protocol is a leakage-resilient secret-sharing scheme (LRSS) in the bounded-leakage model, which shows that it is leakage-resilient against θ,n,l-BCP.In particular, as an application, our LRSS is a group identification scheme (GID-scheme); that is, all qualified parties can detect whether the dealer is cheating, and any verifier can detect whether unqualified parties are cheating. We also prove that our GID-scheme is leakage-resilient in the bounded-leakage model. The basic construction of our scheme relies on the following considerations:Assume that a private channel exists in the distribution protocol of our protocol between every party and the dealer and that all the parties have an individual broadcast channelGiven the public keypk and l bits of secret key sk leakage, our protocol is performed between any probabilistic polynomial-time adversarial verifier V∗ and an honest prover P, maintaining information-theoretic entropy and achieving security in the bounded-leakage modelFor any adversarial prover, the corresponding secret key of the emulated identity’s public key should be knownFor one public key, the probability of an algorithm to find two distinct secret keys is negligible


### 1.4. Organization

This paper is organized as follows. In Section2, we introduce some definitions and lemmas that are used in this work. We describe how to construct our protocol in Section 3 and provide several proofs of the properties of our protocol in Section 4. As an application, we propose a group identification protocol in Section 5. Finally, we provide the conclusions and future work on this topic in Section 6.


## 1.1. Secret-Sharing Scheme from Linear Codes

There is a natural correspondence between linear codes and a secret-sharing scheme. McEliece and Sarwate noted the relationship between Shamir–Blakley’s secret-sharing scheme and Reed–Solomon codes in [13]. Since then, several secret-sharing schemes have been constructed in terms of linear error-correcting codes [14–16]. To construct a secret-sharing scheme from linear codes, Massey pointed out the relationship between the access structure and the minimal codewords of the dual code of the underlying code [17, 18]. Therefore, when designing a secret-sharing scheme based on linear codes, it is necessary to consider the open problem of how to determine the minimal codewords for certain linear codes. In this work, we assume that the codes and their dual codes are efficiently encodable and decodable, respectively. In this work, the relationship between secret-sharing scheme and linear codes is presented in Section 2.1.


## 1.2. Leakage-Resilient Secret-Sharing Scheme

In the application of secret-sharing scheme realizing the access structure, some parties exist that might cheat others by providing false secret keys under the sharing control, and the information about the secret key is leaked. To avoid this situation, it is necessary to consider the challenge of protecting the secret key of the dealer and the shares of parties againstinformation leakage, i.e., in previous work, most researchers generally used leakage-resilient cryptographic primitives [19–24] and leakage-resilient devices [25, 26] to protect the security of the secret key. The cryptographic primitives and computational devices are said to be leakage-resilient if it remains secure in the presence of bounded-leakage of an internal (secret) state. In the work presented in [27], the authors defined the assumption that only the computation leaks information. In other words, there is no leakage without computation. However, this assumption does not guarantee security in the model because cold-boot attacks [28] may work [29]. Therefore, motivated by the work of Dziembowski and Pietrzak [30], we describe the leakage assumptions considered in this work as follows:Independent leakage: the computation can be organized into rounds, and the leaks in each round are independentBounded leakage: in each round, the number of leakages are bound to some parameters,whereas the total leakage bit is bounded bylBounded domain: in fact, the leakage function takes as inputonly the secret state during the invocationFormally, in the bounded-leakage model, an attacker can repeatedly and adaptively access to aleakage oracle and learn information about the secret key, as long as the total number of information leaked is bounded by some parameter l. An attacker chooses a sequence of polynomial-time-computable leakage functions fi:0,1sk⟶0,1lii=1n and obtains fstate, where state is the party P’s secret state information at the end beginning of each round i and ∑ili≤1.


## 1.3. Our Contributions

In this work, we construct a secret-sharing scheme for a given access structure arising from linear correcting codes. According to the definitions of security models and attack models, we prove that our protocol is ann-prover zero-knowledge proof system in the random oracle model, which reveals that the secret key can be shared repeatedly without leaking any information in the case of a passive attacker. Additionally, our protocol is a leakage-resilient secret-sharing scheme (LRSS) in the bounded-leakage model, which shows that it is leakage-resilient against θ,n,l-BCP.In particular, as an application, our LRSS is a group identification scheme (GID-scheme); that is, all qualified parties can detect whether the dealer is cheating, and any verifier can detect whether unqualified parties are cheating. We also prove that our GID-scheme is leakage-resilient in the bounded-leakage model. The basic construction of our scheme relies on the following considerations:Assume that a private channel exists in the distribution protocol of our protocol between every party and the dealer and that all the parties have an individual broadcast channelGiven the public keypk and l bits of secret key sk leakage, our protocol is performed between any probabilistic polynomial-time adversarial verifier V∗ and an honest prover P, maintaining information-theoretic entropy and achieving security in the bounded-leakage modelFor any adversarial prover, the corresponding secret key of the emulated identity’s public key should be knownFor one public key, the probability of an algorithm to find two distinct secret keys is negligible


## 1.4. Organization

This paper is organized as follows. In Section2, we introduce some definitions and lemmas that are used in this work. We describe how to construct our protocol in Section 3 and provide several proofs of the properties of our protocol in Section 4. As an application, we propose a group identification protocol in Section 5. Finally, we provide the conclusions and future work on this topic in Section 6.


## 2. Preliminaries

Here, we introduce the notations and basic definitions used throughout this work. Letℕ and ℝ be sets of natural numbers and real numbers, respectively. We write n to indicate the set 1,…,n of natural numbers n∈ℕ. Let x denote the binary length of x.


### 2.1. Secret-Sharing Scheme from Linear Codes and Security Definitions

LetFq denote a finite field where q is a prime. We write Fq∗ for the set of nonzero elements of Fq; then, Fq∗ is a multiplicative cyclic group with q−1 elements, and any element in Fq∗ has order dividing q−1. We use the symbol Fqn to refer to an n-dimensional linear vector space over Fq. Let “∥” denote the concatenation of finite vector (bold letter), i.e., x=x1,x2,…,xn=x1x2…xn=x1c∈Fqn, where c=x2,…,xn∈Fqn−1.Definition 1.
(linear codes). Ann,k code C is a k-dimensional linear subspace of Fqn, which means that the sum of the two codewords of C is a codeword and that the product of any codeword by a field element is a codeword.Definition 2.
(generator matrix).A matrix G=v0,v1,…,vnτ is called a generator matrix of an n+1,k code C, if for every codeword z in C is a linear combination of the rows of G, i.e., z=r0v0+⋯+rk−1vk−1=r0,…,rk−1G, where vi=gi0,…,gin,gij∈Fp for 0≤i≤k−1,0≤j≤n.
LetPn=P1,…,Pn be a set of n parties. The definition of the access structure (monotone) is given as follows.Definition 3.
(access structure [31, 32]). A set(1)AS=A⊆2PnA can reconstruct the secret,is called an access structure, if it satisfies the monotone property, i.e., for any A′∈AS and A′⊆A⊆2Pn, it holds A∈AS.
Any subsets inAS are called qualified (or authorized), and the subsets that do not belong to AS are called unqualified (or unauthorized).Definition 4.
(secret-sharing scheme,SSS). Let Share be any probabilistic algorithm that takes as input a secret s∈S and returns n shares s=s1,…,sn. Let Recon be a deterministic algorithm that takes as input the shares of a subset Λ and output a possible secret. Note that S is the domain of the secret key. We say that an n,t-secret-sharing schemeSSS=Share,Recon over field Fq for realizing an access structure AS, if it satisfies.Correctness: for every secret s∈S and every qualified set, Λ∈AS with Λ≥t, and it has the equation ReconsΛ,Λ=sSecurity: for every unqualified set,Λ∉AS with Λ<t, and two arbitrary distinct secrets s1,s2∈S, sΛ1 is identically distributed to sΛ2, where s⟶Shares and sΛ=sii∈\Λ are the completed shares of parties in ΛDefinition 5.
(linear secret-sharing scheme, LSSS). Ann,t-SSS=Share,Recon over field Fq is linear if the codomain of Share is the vector space Fqn, and Share is a Fq-linear mapping and Shares is uniformly probability distributed over Fqn for any s∈Fq.
Based on the work in [17], we use a linear codes to construct an SSS as follows. An n+1,k code C is a linear subspace of Fqn+1. Note that G=g0,g1,…,gn be the generator matrix for C, where gi∈Fqk is the column vector of G,0≤i≤n. In the SSS=Share,Recon constructed from C, the secret s is an element of Fq, n parties P1,P2,…,Pn and a dealer D are involved. To compute the shares s1,…,sn of secret s, D performs the algorithm Share as follows.
The dealerD chooses a random codeword u=u0,u1,…,uk−1∈Fqk satisfying s=ug0. Next, D computes the corresponding codeword by the following equation:(2)v=s0,s1,…,sn=uG.
Therefore,s0,s1,…,sn∈C with s0=ug0=s. Let s=s1,…,sn be the shares of s. Finally, D securely sends si to party Pi, for i=1,2,…,n.
To reconstruct the secrets, the algorithm Recon of SSS is performed as follows: recall the fact that the dual code C⊥ of C can be defined using the following formula:(3)C⊥=x∈Fqn+1xG=0.
Namely, a vectorx∈Fqn+1 belongs to C⊥ if and only if x is orthogonal to any codeword in C. If x=x0,x1,…,xn∈C⊥ with x0≠0, for any codeword s0,s1,…,sn∈C, then we have(4)s=∑i=1n−xix0si.
Using equation (1), the secret s can be reconstructed from the shares s1,s2,…,sn.Lemma 1.
Assume thatA=Pc1,…,Pcm⊆Pn,1≤c1<⋯<cm≤n; then, the members in A can reconstruct the secret s with their own shares sc1,…,scm if and only if the vector g0 is a linear combination of gc1,…,gcm.Proof.
“⇒” The necessity is quite obvious.
“⇐” Assume that g0 is a linear combination of gc1,…,gcm; then, there exists ac1,…,acm∈Fq such that(5)g0=∑i=1macigci.
Then, the secrets is reconstructed by calculating(6)s=ug0=u∑i=1macigci=∑i=1maciugci=∑i=1macisci.
The above mentionedSSS realizes that the access structure AS¯ is defined as follows:(7)AS¯=A⊆Png0∈spangiPi∈A,where “span” means the linear space spanned by the element of the giPi∈A set.
Based on Definition4 and the work of [19], we present the security definition of SSS and the adversarial model in the following.
In this work, to model adversarial leakage attacks on a secret keys, the adversary has an opportunity to adaptively access a leakage oracle and obtains information about the secret key s. The formal definition of leakage oracle is given as follows.Definition 6 (leakage oracle [20, 22]).
LetOskλ,l⋅ be a leakage oracle, which is parameterized by a prover’s secret key sk, a leakage parameter l, and a security parameter λ. A query to the leakage oracle is constituted by a leakage function fj:0,1sk⟶0,1ljj∈n, and the oracle responds with fjsk. The oracle Oskλ,l⋅ is restricted in the total number of l bits. For all queries received, Oskλ,l⋅ only responds to the kth leakage query and computes the function fjw for at most poly⋅ steps if ∑j=1klj≤l, where 1≤j≤k≤n. Otherwise, the oracle ignores the queries.Remark 1.
Note thatl=0 means that there is no information leaked to the simulator in an ideal setting, whereas l≈1 means that a malicious adversary (or verifier) learns nothing from the protocol other than obtaining the validity of the proven statement and obtaining the leakage information from an honest user (or prover).Definition 7 (l-bounded adversary).
LetΘ be a subset of n. We say that an adversary A is l-bounded, if the corruption set PΘ:=Pii∈Θ selected by A satisfies the following property; for each Pi∈PΘ, it holds that ∑i∈Θli≤l, where li denotes the length of the output of an arbitrary (leakage) function fi:0,1∗⟶0,1lii∈Θ.Definition 8.
(leakage-resilient secret sharing, LRSS). LetS be any secret key domain and AS be any access structure on parties P1,…,Pn. We say an SSS realizing AS is Θ,l,ε-leakage-resilient (or Θ,l,ε-LRSS), if for every leakage protocol Leak in θ,n,l-BCP, and for every pair of secrets s1,s2∈S, the following holds:(8)LeakΘ,fShares1:s⟵Shares1≈ϵLeakΘ,fShares2:s⟵Shares2,where Θ denotes the subset of n. That is, the distribution of transcript learned by A on sharing s1 is statistically closed to the distribution of transcript learned by A on sharing s2. In particular, an SSS=Share,Rec is said to be θ,l,ε-leakage-resilient (or θ,l,ε-LRSS) if it is Θ,l,ε-leakage-resilient for any subset Θ⊆n with Θ≤θ.
In our work, the notationθ,n,l-BCP) presented in Definition 4 is inspired by the work [33]. We give the program θ,n,l-bounded corrupted program (or θ,n,l-BCP) as follows. n parities P1,…,Pn and θ≤n, where θ is an upper bound on the number of parties corrupted by adversary A in any round. Let l be the leakage bound. Let f be leakage function family f=f1,…,fn, where fj:0,1∗⟶0,1lj and j∈n. We write fs=f1s1,…,fnsn for the total leakage seen by adversary on the shares s=s1,…,sn of secret s.θ,n,l-BCP ON INPUT s,Θ,n,lGENERATE sharess=s1,…,sn of secret s∈S, SEND si to Pi for i∈nLeak is empty at the begining of leakage-protocolLeak is appended with the leakage and Leak≤lCOMPUTELeak←LeakfsΘ in each round, where sΘ:=sii∈Θ and Θ⩽θOUTPUT final transcriptLeak as leakage


### 2.2. Zero-Knowledge

Definition 9.
(negligible functions). A functionμ:ℕ⟶ℝ is negligible if, for any positive polynomial poly⋅, there exists N∈ℕ such that, for all n>N,(9)μn<1polyn.Definition 10 (probability ensemble).
X denotes a countable set. An ensemble indexed by X indicates a sequence of random variables indexed by X. For instance, A=Aii∈X is an ensemble indexed by X, where each Ai is a random variable.Definition 11 (polynomial-time indistinguishability).
LetA=Ann∈n∗ and B=Bnn∈n∗ be two difference ensembles indexed by n∗. If(10)PrDAn,1n−PrDBn,1n<1polynholds for any probabilistic polynomial-time (PPT) algorithm D, any positive polynomial poly⋅, and any sufficiently large n, then we say that A and B are indistinguishable in polynomial time.
In the following context, we use the terminologycomputationally indistinguishable instead of indistinguishability in polynomial time.Definition 12.
Letλ be a security parameter and let X=Xλ and Y=Yλ be the ensemble sets. Let R be a witness relation associated with language L on X×Y, where L is defined as L=x:∃ys.t.x,y∈R. R is polynomially bounded (i.e., x,y∈R implies y⩽polyx) and recognized in polynomial time. Given x∈L, an element y∈Y such that x,y∈R is called a witness. Suppose that K is a PPT algorithm, which takes as input 1λ and outputs pairs x,y with x,y∈R.
We writeP and V to denote the prover and the verifier, respectively, where P and V are two interactive probabilistic polynomial turning machines.Definition 13 (interactive proof system, [34]).
A pair of interactive machinesP,V is called an interactive proof system for a language L if machine V is PPT and the following two conditions hold:Completeness: for everyx∈L, it holds that PrP,Vx=1≥2/3Soundness: for everyx∉L and every interactive machine M, it holds that PrM,Vx=1≤1/3
Now, we consider the interactive protocol consisting of infinitely powerfuln machines P1,…,Pn interacting with a PPT machine V.Definition 14 (multiprover interactive proof system [35]).
We say that the interactive turning machinesP1,…,Pn,V in the n-prover model are called multiprover interactive proof system for language L, if an interactive PPT Turning machine V exists and the following two properties are satisfied:Completeness: for everyx∈L, there is PrP1,…,Pn,Vx=1≥2/3Soundness: for everyx∉L and all interactive machines M1,…,Mn, there are PrM1,…,Mn,Vx=1≤1/3.Definition 15 (multiprover computational zero-knowledge [34]).
LetP1,…,Pn,V be a multiprover interactive proof system with some language L. We say that P1,…,Pn,V is computational zero-knowledge if, for every interactive PPT turning machine V∗, a PPT machine M exists such that, for all x∈L, ensemble ViewP1,…,Pn,V∗xx∈L and Mxx∈L are computationally indistinguishable.
In Definition15, the ensemble ViewP1,…,Pn,V∗xx∈L denotes the view (or output) of the interactive machine V∗ after interacting with n interactive machines P1,…,Pn on common input x (namely, the transcript about the sequence of messages exchanged between V∗ and P1,…,Pn). Mxx∈L denotes the output of M on input x. In this case, we call M is a simulator for the interaction of V∗ with P1,…,Pn. The existence of M means that V∗ does not gain any more knowledge than M. Indeed, M does not access P1,…,Pn and might not know whether P1,…,Pn exists. However, it is able to simulate the interaction of V∗ with P1,…,Pn.
Succinctly speaking, an interactive proof systemP1,…,Pn,V for language L is zero-knowledge if whatever can be efficiently computed by V after interacting with P1,…,Pn on common input x∈L can also be directly computed by the simulator with input x.


### 2.3. Identification Schemes and Security Definitions

In this section, we first recall the standard cryptographic concepts of∑-protocols presented in [36, 37] and identification schemes (ID-scheme) presented in [20]. Then, we present the formal security definitions of the ID-scheme. We write TR←Py,Vx to denote the transcript TR that was generated through an interactive protocol P,V, where y is the private input of P and x is the common input of P and V. The notation OutVz denotes the output of V with input z∈TR. V outputs OutVz=1 if he accepts the proof and OutVz=0 otherwise.Definition 16.
(∑−protocol [36, 37]). Let P,V be an interactive proof system for language L. The prover P takes as input x∈L and sends a witness y to verifier V. V takes as input the common input x and the received y, and it outputs 1 if y=polyx and x,y∈R.
A∑-protocol for the relation R is a 3-round interactive proof system P,V that can be described as follows:StepP1: P first sends a commitment α to V, i.e., α←Px,yStepV1: V responds with a challenge β based on α, i.e., β←Vx,αStepP2: P returns with γ based on β, i.e., γ←Px,y,α,βStepV2: V outputs a bit b∈0,1, i.e., b←OutVx,α,β,γ, where b=1 if he accepts the proof and b=0 otherwise
Here,TR:=α,β,γ. A ∑-protocol satisfies the following properties:Completeness: the verifierV outputs 1 with probability 1, i.e., Prx,y←K1λ;α←Px,y;β←Vx,α;γ←Px,y,α,β;1←OutVx,α,β,γ=1, where steps P1,V1,andP2 can be denoted by TR←Py,Vx.2-special soundness: sssume that an extractorExtor exists for every x∈L, given two valid transcripts α,β,γ and α,β′,γ′, where β≠β′ and γ≠γ′. The Extor takes as input α,β,γ,β′,γ′ and outputs a witness y for the relation R.Honest verifier zero-knowledge: for every PPT turning machineV∗, a probabilistic algorithm M exists such that the two ensembles ViewP,V∗xx∈L and Mxx∈L are computationally indistinguishable.Definition 17 (identification scheme [20]).
An identification scheme (ID-scheme) contains four PPT proceduresParGen,KeyGen,P,V. The concrete description is as follows:params←ParGen1λ: the parameter generation procedure takes as input security parameter λ and returns the system parameters of the identification scheme, denoted by params. params are common to all users and issued to KeyGen,P, and V as inputs.pk,sk←KeyGen(): the key generation procedure takes as input params and outputs the public key pk and secret key sk.Ppk,sk,VTR,pk: P denotes a prover and V denotes a verifier. V returns a judgement b∈0,1 about P after executing the protocol. If b=1, then V accepts P’s identity. b=0 otherwise.
To obtain a secure (group) ID-scheme, we define some security definitions and models.Definition 18.
We say that (group) ID-schemeParGen,KeyGen,P,V is secure if the following two conditions hold:Completeness: for each partyPi∈AS, the probability of acceptance is(11)Prparams←ParGen1λ;pk1,…,pkn,ski←KeyGen,TR←Pski,Vpk1,…,pkm:1←OutVTR=1.Soundness: for any partyPi∉AS and any PPT algorithm, the advantage of P′(12)Prparams←ParGen1λ;pk1,…,pkn←KeyGenTR←P′ϕ,Vpk1,…,pkn:1←OutVTR−12is negligible, where the private input ϕ of P′⋅ is an empty string and TR is defined in Definition 16 and i∈m.
Before we formally define of the leakage-resilient ID-scheme, we first consider two security games (illustrated in Table1), which are inspired by the work presented in [20]. The first game called pre-emulation leakage security is simulated by the attack game IDprelλA and allows the adversary A to send leakage queries before the emulation attack. The second game called arbitrary time leakage security is simulated by the attack game IDarblλA and allows the adversary A to adaptively execute leakage attacks at an arbitrary time during an emulation attack. The key generation phase and test phase are the same in the games IDprelλA and IDarblλA. The emulation phase is divided into two separate games according to the definitions of IDprelλA and IDarblλA, respectively.Table 1
Attack game for defining thepre-emulation leakage security and arbitrary time leakage security of IDprelλA and IDarblλA, respectively.
Attack GameIDprelλA
Attack GameIDarblλA
(1) Key generation phase: run two algorithmsparams←ParGen1λ, pk,sk←KeyGen() and give params,pk to the adversary A
(2) Test phase: the adversaryAOskλ,l⋅,Ppk,sk can access oracles Oskλ,l⋅ (the leakage oracle) and Ppk,sk (an honest prover oracle), where Oskλ,lf returns fsk
(3) Emulation phase: this phase is divided into two separate games
(i) For the gameIDprelλA: the adversary A is not allowed to access oracles Oskλ,l⋅ and honest prover oracle P. A performs an interactive protocol, denoted by A,Vpk with an honest verifier V
(ii) For the gameIDarblλA: the adversary A only gets access to the leakage oracle Oskλ,l⋅ and performs the interactive protocol, denoted by AOskλ,l⋅,Vpk with an honest verifier VDefinition 19 (leakage-resilient ID-scheme).
LetKeyGen,P,V be an ID-scheme, which is parameterized by security parameter λ and holds the property of completeness. We say that KeyGen,P,V is secure against the pre-emulation leakage l if the advantage of any PPT adversary A in the attack game IDprelλA is negligible in λ. Additionally, it is secure against the arbitrary time leakage l if the abovementioned adversary A for the attack game IDarblλA is negligible in λ.


## 2.1. Secret-Sharing Scheme from Linear Codes and Security Definitions

LetFq denote a finite field where q is a prime. We write Fq∗ for the set of nonzero elements of Fq; then, Fq∗ is a multiplicative cyclic group with q−1 elements, and any element in Fq∗ has order dividing q−1. We use the symbol Fqn to refer to an n-dimensional linear vector space over Fq. Let “∥” denote the concatenation of finite vector (bold letter), i.e., x=x1,x2,…,xn=x1x2…xn=x1c∈Fqn, where c=x2,…,xn∈Fqn−1.Definition 1.
(linear codes). Ann,k code C is a k-dimensional linear subspace of Fqn, which means that the sum of the two codewords of C is a codeword and that the product of any codeword by a field element is a codeword.Definition 2.
(generator matrix).A matrix G=v0,v1,…,vnτ is called a generator matrix of an n+1,k code C, if for every codeword z in C is a linear combination of the rows of G, i.e., z=r0v0+⋯+rk−1vk−1=r0,…,rk−1G, where vi=gi0,…,gin,gij∈Fp for 0≤i≤k−1,0≤j≤n.
LetPn=P1,…,Pn be a set of n parties. The definition of the access structure (monotone) is given as follows.Definition 3.
(access structure [31, 32]). A set(1)AS=A⊆2PnA can reconstruct the secret,is called an access structure, if it satisfies the monotone property, i.e., for any A′∈AS and A′⊆A⊆2Pn, it holds A∈AS.
Any subsets inAS are called qualified (or authorized), and the subsets that do not belong to AS are called unqualified (or unauthorized).Definition 4.
(secret-sharing scheme,SSS). Let Share be any probabilistic algorithm that takes as input a secret s∈S and returns n shares s=s1,…,sn. Let Recon be a deterministic algorithm that takes as input the shares of a subset Λ and output a possible secret. Note that S is the domain of the secret key. We say that an n,t-secret-sharing schemeSSS=Share,Recon over field Fq for realizing an access structure AS, if it satisfies.Correctness: for every secret s∈S and every qualified set, Λ∈AS with Λ≥t, and it has the equation ReconsΛ,Λ=sSecurity: for every unqualified set,Λ∉AS with Λ<t, and two arbitrary distinct secrets s1,s2∈S, sΛ1 is identically distributed to sΛ2, where s⟶Shares and sΛ=sii∈\Λ are the completed shares of parties in ΛDefinition 5.
(linear secret-sharing scheme, LSSS). Ann,t-SSS=Share,Recon over field Fq is linear if the codomain of Share is the vector space Fqn, and Share is a Fq-linear mapping and Shares is uniformly probability distributed over Fqn for any s∈Fq.
Based on the work in [17], we use a linear codes to construct an SSS as follows. An n+1,k code C is a linear subspace of Fqn+1. Note that G=g0,g1,…,gn be the generator matrix for C, where gi∈Fqk is the column vector of G,0≤i≤n. In the SSS=Share,Recon constructed from C, the secret s is an element of Fq, n parties P1,P2,…,Pn and a dealer D are involved. To compute the shares s1,…,sn of secret s, D performs the algorithm Share as follows.
The dealerD chooses a random codeword u=u0,u1,…,uk−1∈Fqk satisfying s=ug0. Next, D computes the corresponding codeword by the following equation:(2)v=s0,s1,…,sn=uG.
Therefore,s0,s1,…,sn∈C with s0=ug0=s. Let s=s1,…,sn be the shares of s. Finally, D securely sends si to party Pi, for i=1,2,…,n.
To reconstruct the secrets, the algorithm Recon of SSS is performed as follows: recall the fact that the dual code C⊥ of C can be defined using the following formula:(3)C⊥=x∈Fqn+1xG=0.
Namely, a vectorx∈Fqn+1 belongs to C⊥ if and only if x is orthogonal to any codeword in C. If x=x0,x1,…,xn∈C⊥ with x0≠0, for any codeword s0,s1,…,sn∈C, then we have(4)s=∑i=1n−xix0si.
Using equation (1), the secret s can be reconstructed from the shares s1,s2,…,sn.Lemma 1.
Assume thatA=Pc1,…,Pcm⊆Pn,1≤c1<⋯<cm≤n; then, the members in A can reconstruct the secret s with their own shares sc1,…,scm if and only if the vector g0 is a linear combination of gc1,…,gcm.Proof.
“⇒” The necessity is quite obvious.
“⇐” Assume that g0 is a linear combination of gc1,…,gcm; then, there exists ac1,…,acm∈Fq such that(5)g0=∑i=1macigci.
Then, the secrets is reconstructed by calculating(6)s=ug0=u∑i=1macigci=∑i=1maciugci=∑i=1macisci.
The above mentionedSSS realizes that the access structure AS¯ is defined as follows:(7)AS¯=A⊆Png0∈spangiPi∈A,where “span” means the linear space spanned by the element of the giPi∈A set.
Based on Definition4 and the work of [19], we present the security definition of SSS and the adversarial model in the following.
In this work, to model adversarial leakage attacks on a secret keys, the adversary has an opportunity to adaptively access a leakage oracle and obtains information about the secret key s. The formal definition of leakage oracle is given as follows.Definition 6 (leakage oracle [20, 22]).
LetOskλ,l⋅ be a leakage oracle, which is parameterized by a prover’s secret key sk, a leakage parameter l, and a security parameter λ. A query to the leakage oracle is constituted by a leakage function fj:0,1sk⟶0,1ljj∈n, and the oracle responds with fjsk. The oracle Oskλ,l⋅ is restricted in the total number of l bits. For all queries received, Oskλ,l⋅ only responds to the kth leakage query and computes the function fjw for at most poly⋅ steps if ∑j=1klj≤l, where 1≤j≤k≤n. Otherwise, the oracle ignores the queries.Remark 1.
Note thatl=0 means that there is no information leaked to the simulator in an ideal setting, whereas l≈1 means that a malicious adversary (or verifier) learns nothing from the protocol other than obtaining the validity of the proven statement and obtaining the leakage information from an honest user (or prover).Definition 7 (l-bounded adversary).
LetΘ be a subset of n. We say that an adversary A is l-bounded, if the corruption set PΘ:=Pii∈Θ selected by A satisfies the following property; for each Pi∈PΘ, it holds that ∑i∈Θli≤l, where li denotes the length of the output of an arbitrary (leakage) function fi:0,1∗⟶0,1lii∈Θ.Definition 8.
(leakage-resilient secret sharing, LRSS). LetS be any secret key domain and AS be any access structure on parties P1,…,Pn. We say an SSS realizing AS is Θ,l,ε-leakage-resilient (or Θ,l,ε-LRSS), if for every leakage protocol Leak in θ,n,l-BCP, and for every pair of secrets s1,s2∈S, the following holds:(8)LeakΘ,fShares1:s⟵Shares1≈ϵLeakΘ,fShares2:s⟵Shares2,where Θ denotes the subset of n. That is, the distribution of transcript learned by A on sharing s1 is statistically closed to the distribution of transcript learned by A on sharing s2. In particular, an SSS=Share,Rec is said to be θ,l,ε-leakage-resilient (or θ,l,ε-LRSS) if it is Θ,l,ε-leakage-resilient for any subset Θ⊆n with Θ≤θ.
In our work, the notationθ,n,l-BCP) presented in Definition 4 is inspired by the work [33]. We give the program θ,n,l-bounded corrupted program (or θ,n,l-BCP) as follows. n parities P1,…,Pn and θ≤n, where θ is an upper bound on the number of parties corrupted by adversary A in any round. Let l be the leakage bound. Let f be leakage function family f=f1,…,fn, where fj:0,1∗⟶0,1lj and j∈n. We write fs=f1s1,…,fnsn for the total leakage seen by adversary on the shares s=s1,…,sn of secret s.θ,n,l-BCP ON INPUT s,Θ,n,lGENERATE sharess=s1,…,sn of secret s∈S, SEND si to Pi for i∈nLeak is empty at the begining of leakage-protocolLeak is appended with the leakage and Leak≤lCOMPUTELeak←LeakfsΘ in each round, where sΘ:=sii∈Θ and Θ⩽θOUTPUT final transcriptLeak as leakage


## 2.2. Zero-Knowledge

Definition 9.
(negligible functions). A functionμ:ℕ⟶ℝ is negligible if, for any positive polynomial poly⋅, there exists N∈ℕ such that, for all n>N,(9)μn<1polyn.Definition 10 (probability ensemble).
X denotes a countable set. An ensemble indexed by X indicates a sequence of random variables indexed by X. For instance, A=Aii∈X is an ensemble indexed by X, where each Ai is a random variable.Definition 11 (polynomial-time indistinguishability).
LetA=Ann∈n∗ and B=Bnn∈n∗ be two difference ensembles indexed by n∗. If(10)PrDAn,1n−PrDBn,1n<1polynholds for any probabilistic polynomial-time (PPT) algorithm D, any positive polynomial poly⋅, and any sufficiently large n, then we say that A and B are indistinguishable in polynomial time.
In the following context, we use the terminologycomputationally indistinguishable instead of indistinguishability in polynomial time.Definition 12.
Letλ be a security parameter and let X=Xλ and Y=Yλ be the ensemble sets. Let R be a witness relation associated with language L on X×Y, where L is defined as L=x:∃ys.t.x,y∈R. R is polynomially bounded (i.e., x,y∈R implies y⩽polyx) and recognized in polynomial time. Given x∈L, an element y∈Y such that x,y∈R is called a witness. Suppose that K is a PPT algorithm, which takes as input 1λ and outputs pairs x,y with x,y∈R.
We writeP and V to denote the prover and the verifier, respectively, where P and V are two interactive probabilistic polynomial turning machines.Definition 13 (interactive proof system, [34]).
A pair of interactive machinesP,V is called an interactive proof system for a language L if machine V is PPT and the following two conditions hold:Completeness: for everyx∈L, it holds that PrP,Vx=1≥2/3Soundness: for everyx∉L and every interactive machine M, it holds that PrM,Vx=1≤1/3
Now, we consider the interactive protocol consisting of infinitely powerfuln machines P1,…,Pn interacting with a PPT machine V.Definition 14 (multiprover interactive proof system [35]).
We say that the interactive turning machinesP1,…,Pn,V in the n-prover model are called multiprover interactive proof system for language L, if an interactive PPT Turning machine V exists and the following two properties are satisfied:Completeness: for everyx∈L, there is PrP1,…,Pn,Vx=1≥2/3Soundness: for everyx∉L and all interactive machines M1,…,Mn, there are PrM1,…,Mn,Vx=1≤1/3.Definition 15 (multiprover computational zero-knowledge [34]).
LetP1,…,Pn,V be a multiprover interactive proof system with some language L. We say that P1,…,Pn,V is computational zero-knowledge if, for every interactive PPT turning machine V∗, a PPT machine M exists such that, for all x∈L, ensemble ViewP1,…,Pn,V∗xx∈L and Mxx∈L are computationally indistinguishable.
In Definition15, the ensemble ViewP1,…,Pn,V∗xx∈L denotes the view (or output) of the interactive machine V∗ after interacting with n interactive machines P1,…,Pn on common input x (namely, the transcript about the sequence of messages exchanged between V∗ and P1,…,Pn). Mxx∈L denotes the output of M on input x. In this case, we call M is a simulator for the interaction of V∗ with P1,…,Pn. The existence of M means that V∗ does not gain any more knowledge than M. Indeed, M does not access P1,…,Pn and might not know whether P1,…,Pn exists. However, it is able to simulate the interaction of V∗ with P1,…,Pn.
Succinctly speaking, an interactive proof systemP1,…,Pn,V for language L is zero-knowledge if whatever can be efficiently computed by V after interacting with P1,…,Pn on common input x∈L can also be directly computed by the simulator with input x.


## 2.3. Identification Schemes and Security Definitions

In this section, we first recall the standard cryptographic concepts of∑-protocols presented in [36, 37] and identification schemes (ID-scheme) presented in [20]. Then, we present the formal security definitions of the ID-scheme. We write TR←Py,Vx to denote the transcript TR that was generated through an interactive protocol P,V, where y is the private input of P and x is the common input of P and V. The notation OutVz denotes the output of V with input z∈TR. V outputs OutVz=1 if he accepts the proof and OutVz=0 otherwise.Definition 16.
(∑−protocol [36, 37]). Let P,V be an interactive proof system for language L. The prover P takes as input x∈L and sends a witness y to verifier V. V takes as input the common input x and the received y, and it outputs 1 if y=polyx and x,y∈R.
A∑-protocol for the relation R is a 3-round interactive proof system P,V that can be described as follows:StepP1: P first sends a commitment α to V, i.e., α←Px,yStepV1: V responds with a challenge β based on α, i.e., β←Vx,αStepP2: P returns with γ based on β, i.e., γ←Px,y,α,βStepV2: V outputs a bit b∈0,1, i.e., b←OutVx,α,β,γ, where b=1 if he accepts the proof and b=0 otherwise
Here,TR:=α,β,γ. A ∑-protocol satisfies the following properties:Completeness: the verifierV outputs 1 with probability 1, i.e., Prx,y←K1λ;α←Px,y;β←Vx,α;γ←Px,y,α,β;1←OutVx,α,β,γ=1, where steps P1,V1,andP2 can be denoted by TR←Py,Vx.2-special soundness: sssume that an extractorExtor exists for every x∈L, given two valid transcripts α,β,γ and α,β′,γ′, where β≠β′ and γ≠γ′. The Extor takes as input α,β,γ,β′,γ′ and outputs a witness y for the relation R.Honest verifier zero-knowledge: for every PPT turning machineV∗, a probabilistic algorithm M exists such that the two ensembles ViewP,V∗xx∈L and Mxx∈L are computationally indistinguishable.Definition 17 (identification scheme [20]).
An identification scheme (ID-scheme) contains four PPT proceduresParGen,KeyGen,P,V. The concrete description is as follows:params←ParGen1λ: the parameter generation procedure takes as input security parameter λ and returns the system parameters of the identification scheme, denoted by params. params are common to all users and issued to KeyGen,P, and V as inputs.pk,sk←KeyGen(): the key generation procedure takes as input params and outputs the public key pk and secret key sk.Ppk,sk,VTR,pk: P denotes a prover and V denotes a verifier. V returns a judgement b∈0,1 about P after executing the protocol. If b=1, then V accepts P’s identity. b=0 otherwise.
To obtain a secure (group) ID-scheme, we define some security definitions and models.Definition 18.
We say that (group) ID-schemeParGen,KeyGen,P,V is secure if the following two conditions hold:Completeness: for each partyPi∈AS, the probability of acceptance is(11)Prparams←ParGen1λ;pk1,…,pkn,ski←KeyGen,TR←Pski,Vpk1,…,pkm:1←OutVTR=1.Soundness: for any partyPi∉AS and any PPT algorithm, the advantage of P′(12)Prparams←ParGen1λ;pk1,…,pkn←KeyGenTR←P′ϕ,Vpk1,…,pkn:1←OutVTR−12is negligible, where the private input ϕ of P′⋅ is an empty string and TR is defined in Definition 16 and i∈m.
Before we formally define of the leakage-resilient ID-scheme, we first consider two security games (illustrated in Table1), which are inspired by the work presented in [20]. The first game called pre-emulation leakage security is simulated by the attack game IDprelλA and allows the adversary A to send leakage queries before the emulation attack. The second game called arbitrary time leakage security is simulated by the attack game IDarblλA and allows the adversary A to adaptively execute leakage attacks at an arbitrary time during an emulation attack. The key generation phase and test phase are the same in the games IDprelλA and IDarblλA. The emulation phase is divided into two separate games according to the definitions of IDprelλA and IDarblλA, respectively.Table 1
Attack game for defining thepre-emulation leakage security and arbitrary time leakage security of IDprelλA and IDarblλA, respectively.
Attack GameIDprelλA
Attack GameIDarblλA
(1) Key generation phase: run two algorithmsparams←ParGen1λ, pk,sk←KeyGen() and give params,pk to the adversary A
(2) Test phase: the adversaryAOskλ,l⋅,Ppk,sk can access oracles Oskλ,l⋅ (the leakage oracle) and Ppk,sk (an honest prover oracle), where Oskλ,lf returns fsk
(3) Emulation phase: this phase is divided into two separate games
(i) For the gameIDprelλA: the adversary A is not allowed to access oracles Oskλ,l⋅ and honest prover oracle P. A performs an interactive protocol, denoted by A,Vpk with an honest verifier V
(ii) For the gameIDarblλA: the adversary A only gets access to the leakage oracle Oskλ,l⋅ and performs the interactive protocol, denoted by AOskλ,l⋅,Vpk with an honest verifier VDefinition 19 (leakage-resilient ID-scheme).
LetKeyGen,P,V be an ID-scheme, which is parameterized by security parameter λ and holds the property of completeness. We say that KeyGen,P,V is secure against the pre-emulation leakage l if the advantage of any PPT adversary A in the attack game IDprelλA is negligible in λ. Additionally, it is secure against the arbitrary time leakage l if the abovementioned adversary A for the attack game IDarblλA is negligible in λ.


## 3. Our Protocol

### 3.1. Protocol 1: The Basic Leakproof Secret-Sharing Scheme

For self-containedness, we recall the leakproof secret-sharing scheme [38] as follows. Let D be a dealer, V be a verifier, and P1,…,Pn be n parties.Initialization. In this stage, all the system parameters are generated. The dealer D obtains a public key corresponding to the public key encryption scheme Enc. In addition, suppose that D holds a private channel with every party and that D and every party keep a broadcast channel.Distribution protocol. This protocol is divided into two steps:(1)
Distribution of the shares: this step is executed by the dealerD. First, for the master secret key s, D generates n shares s1,…,sn of s and sends them to P1,…,Pn through individual private channels. Second, D calculates Encs and publishes it by his broadcast channel.(2)
Verification of the shares: every partyPj verifies the validity of share sj received from D, where j=1,2,…,n. If the verification condition is not satisfied, we will say that the dealer fails, and the protocol is aborted.Proof protocol. This protocol is also divided into two steps:(1)
Proof of the secrets: let Λ be any qualified subset for parties P1,…,Pn. Each Pi∈Λ holds the secret share si∈sΛ. Parties in Λ run a multiprover zero-knowledge argument of knowledge with the verifier V prove that they indeed share the secret s. During this interactive proof process, Encs is a common input of parties in Λ between V.(2)
Verification of the secrets: to check whether every Pi∈Λ keeps a valid secret si, V verifies the following condition s=FsΛ, where F stands for some certain deterministic polynomial-time function.


### 3.2. Protocol 2: Secret-Sharing Scheme via Linear Codes

In this section, we begin to describe how our secret-sharing scheme is constructed using linear codes in detail. First, suppose that we have obtained an access structure realized by linear codesC and that G is the corresponding generator matrix.Initialization. Let λ be a security parameter and q be a large prime number, and p is a prime factor of q−1. Let Fq be a finite field. We write g to indicate a cyclic group generated by an element g∈Fq∗ with order g=p and g⊂Fq∗. Let C be a linear code over Fq with length n+1; its generator matrix G=gijk×n+1, where 0≤i≤k−1,0≤j≤n.LetD be a dealer and Pn=P1,P2,…,Pn be a party set. V denotes a verifier with V∉Pn. Assume that a private channel between the dealer D and each Pjj∈n and a public channel between Pj1 and Pj2 exist, where j1≠j2 and j1,j2∈n. In addition, the dealer D has a broadcast channel. We assume that the computing power of all individuals in this protocol is polynomial-time bound.The encryption algorithmEnc is defined as Encx=gxmod q, where x∈Fp.The dealerD randomly chooses s from Fp and p>maxs,n. The master private key sk=s and the public key pk=p,q,g.Distribution protocol. This protocol is divided into two steps:(1)
Distribution of shares:D defines s0=s and calculates and publishes B0=Encs0 by a broadcast channel. To distribute the master secret key s among n parties P1,…,Pn, D executes the algorithm Share of SSS=Share,Recon and gets s⟵Shares. More precisely, the algorithm Share is described by the following program of SECRET DISTRIBUTION:D’s SECRET DISTRIBUTION ON INPUT s0,pk,B0,G:CHOOSE randomu=u0,u1,…,uk−1∈Fpk such that uk−1=s0−∑i=0k−2uigi0/gk−1,0modp COMPUTE Bi=guimodq, where i∈k−1COMPUTEsj=∑i=0k−1uigijmodp and set skj=sj, where j∈n.PUBLISHBi, where i∈k−1.GET a sharess=s1,…,sn of secret s0=sThen,D sends s1,…,sn to P1,…,Pn, respectively.(2)
Verification of the shares: for eachPj∈Pn, let sj denote the private key skj. Each Pj∈Pn performs the following program of SECRET VERIFICATION to check the validity of his own share for j∈n:Pj’s SECRET VERIFICATION ON INPUT sj,pk,B0,Bi,G:GETsj from D. See if sj∈Fp; if not, halt.IFpkj=gsj=B0∏i=1k−1Bigijmodq, THENACCEPT the sharesjELSEREJECT the sharesj and repeat the programProof protocol. According to the abovementioned Distribution protocol, B0,p,q,g,andG are common inputs of parties in Pn between V. Every party Pj∈Pn has a secret input sj for j∈n. Let Pcm:=Pc1,…,Pcm be a size m subset of Pn, and every party Pci has valid secret input sci, where i∈m,1≤c1<⋯<cm≤n. To reconstruct the secret s, for all of Pc1,…,Pcm, they need to determine the existence and uniqueness of the solutions to the system g0=dc1gci+⋯+dcmgcm, where g0,gc1,…,gcm are the column vector of the generator matrix G of n+1,k code C. The calculation is presented in Lemma 1.This protocol is divided into two steps:(1)
Proof of the secrets: this step can be described as follows:StepP1: every party Pci∈Pcm chooses a random rci∈Fp, computes that xci=grcimodq, and sends xi to V, where i∈mStepV1: V chooses a random number z∈1,2 and then sends z to all parties Pc1,…,PcmStepP2: every party Pci∈Pcm computes yci=rci−zdciscimodp and then sends yci to V, where i∈m(2)
Verification of the secrets:StepV2: if it holds that gyc1+yc2+⋯+ycmB0z=∏i=1mxcimodq, then V believes that Pc1,…,Pcm share the secret s satisfying B0=gsmodq; otherwise, V rejects it.


## 3.1. Protocol 1: The Basic Leakproof Secret-Sharing Scheme

For self-containedness, we recall the leakproof secret-sharing scheme [38] as follows. Let D be a dealer, V be a verifier, and P1,…,Pn be n parties.Initialization. In this stage, all the system parameters are generated. The dealer D obtains a public key corresponding to the public key encryption scheme Enc. In addition, suppose that D holds a private channel with every party and that D and every party keep a broadcast channel.Distribution protocol. This protocol is divided into two steps:(1)
Distribution of the shares: this step is executed by the dealerD. First, for the master secret key s, D generates n shares s1,…,sn of s and sends them to P1,…,Pn through individual private channels. Second, D calculates Encs and publishes it by his broadcast channel.(2)
Verification of the shares: every partyPj verifies the validity of share sj received from D, where j=1,2,…,n. If the verification condition is not satisfied, we will say that the dealer fails, and the protocol is aborted.Proof protocol. This protocol is also divided into two steps:(1)
Proof of the secrets: let Λ be any qualified subset for parties P1,…,Pn. Each Pi∈Λ holds the secret share si∈sΛ. Parties in Λ run a multiprover zero-knowledge argument of knowledge with the verifier V prove that they indeed share the secret s. During this interactive proof process, Encs is a common input of parties in Λ between V.(2)
Verification of the secrets: to check whether every Pi∈Λ keeps a valid secret si, V verifies the following condition s=FsΛ, where F stands for some certain deterministic polynomial-time function.


## 3.2. Protocol 2: Secret-Sharing Scheme via Linear Codes

In this section, we begin to describe how our secret-sharing scheme is constructed using linear codes in detail. First, suppose that we have obtained an access structure realized by linear codesC and that G is the corresponding generator matrix.Initialization. Let λ be a security parameter and q be a large prime number, and p is a prime factor of q−1. Let Fq be a finite field. We write g to indicate a cyclic group generated by an element g∈Fq∗ with order g=p and g⊂Fq∗. Let C be a linear code over Fq with length n+1; its generator matrix G=gijk×n+1, where 0≤i≤k−1,0≤j≤n.LetD be a dealer and Pn=P1,P2,…,Pn be a party set. V denotes a verifier with V∉Pn. Assume that a private channel between the dealer D and each Pjj∈n and a public channel between Pj1 and Pj2 exist, where j1≠j2 and j1,j2∈n. In addition, the dealer D has a broadcast channel. We assume that the computing power of all individuals in this protocol is polynomial-time bound.The encryption algorithmEnc is defined as Encx=gxmod q, where x∈Fp.The dealerD randomly chooses s from Fp and p>maxs,n. The master private key sk=s and the public key pk=p,q,g.Distribution protocol. This protocol is divided into two steps:(1)
Distribution of shares:D defines s0=s and calculates and publishes B0=Encs0 by a broadcast channel. To distribute the master secret key s among n parties P1,…,Pn, D executes the algorithm Share of SSS=Share,Recon and gets s⟵Shares. More precisely, the algorithm Share is described by the following program of SECRET DISTRIBUTION:D’s SECRET DISTRIBUTION ON INPUT s0,pk,B0,G:CHOOSE randomu=u0,u1,…,uk−1∈Fpk such that uk−1=s0−∑i=0k−2uigi0/gk−1,0modp COMPUTE Bi=guimodq, where i∈k−1COMPUTEsj=∑i=0k−1uigijmodp and set skj=sj, where j∈n.PUBLISHBi, where i∈k−1.GET a sharess=s1,…,sn of secret s0=sThen,D sends s1,…,sn to P1,…,Pn, respectively.(2)
Verification of the shares: for eachPj∈Pn, let sj denote the private key skj. Each Pj∈Pn performs the following program of SECRET VERIFICATION to check the validity of his own share for j∈n:Pj’s SECRET VERIFICATION ON INPUT sj,pk,B0,Bi,G:GETsj from D. See if sj∈Fp; if not, halt.IFpkj=gsj=B0∏i=1k−1Bigijmodq, THENACCEPT the sharesjELSEREJECT the sharesj and repeat the programProof protocol. According to the abovementioned Distribution protocol, B0,p,q,g,andG are common inputs of parties in Pn between V. Every party Pj∈Pn has a secret input sj for j∈n. Let Pcm:=Pc1,…,Pcm be a size m subset of Pn, and every party Pci has valid secret input sci, where i∈m,1≤c1<⋯<cm≤n. To reconstruct the secret s, for all of Pc1,…,Pcm, they need to determine the existence and uniqueness of the solutions to the system g0=dc1gci+⋯+dcmgcm, where g0,gc1,…,gcm are the column vector of the generator matrix G of n+1,k code C. The calculation is presented in Lemma 1.This protocol is divided into two steps:(1)
Proof of the secrets: this step can be described as follows:StepP1: every party Pci∈Pcm chooses a random rci∈Fp, computes that xci=grcimodq, and sends xi to V, where i∈mStepV1: V chooses a random number z∈1,2 and then sends z to all parties Pc1,…,PcmStepP2: every party Pci∈Pcm computes yci=rci−zdciscimodp and then sends yci to V, where i∈m(2)
Verification of the secrets:StepV2: if it holds that gyc1+yc2+⋯+ycmB0z=∏i=1mxcimodq, then V believes that Pc1,…,Pcm share the secret s satisfying B0=gsmodq; otherwise, V rejects it.


## 4. Security Analysis of Protocol 2

In the following context, to illustrate and analyze the argument of our interactive protocol between partiesP1,…,Pn and verifier V, we use prover to replace party.


### 4.1. Properties from PROTOCOL 2 in Random Oracle Model

#### 4.1.1. Completeness

Assume thatPc1,…,Pcm is a subset of Pn=P1,…,Pn. Pc1,…,Pcm and V execute the abovementioned interactive protocol. V computes the following equation:(13)gyc1+yc2+⋯+ycmB0z=gyc1+yc2+⋯+ycmgsz=gyc1+yc2+⋯+ycmgz∑i=1mscidci=∏i=1mgyci+zdcisci=∏i=1mgrci=∏i=1mxcimodq.If the last equation in equation (13) is satisfied, then V believes that Pc1,…,Pcm share the secret s satisfying B0=gsmodq.


#### 4.1.2. Soundness

To prove the property of soundness, we consider the following three settings.In the first setting, for all of thePn=P1,…,Pn, let Pc0 be the only one prover corrupted by adversary A. Pco pretends to be an honest prover Pj∈Pn, where i∈n. After interacting with V in StepP1, he randomly selects ri∈Fp and computes xj=grjmodq; then, he sends xj to V. Next, V sends the challenge z to Pco, who randomly chooses yj∈Fp, because he does not know the secret sj (held by the honest prover Pj), where j∈n. Then, the success probability of equality(14)gy1+y2+⋯+ynB0z=∏j=1nxjmodqis 1/q. If the interactive protocol executed for K times, the success probability is 1/qK.In the second setting, the adversaryA chooses a subset of Θ⊆n with Θ=θ and get their shares. Let PΘ:=Pc1,…,Pcθ denote the subset of Pn, the adversary A chooses to corrupt in consecutive rounds. The honest parties are denoted by Pn\Θ. Assume that V knows the total number of all provers. Each Pci∈PΘ disguises himself as the honest provers Pj∈Pn\Θ to follow the interactive protocol with V, where i∈θ,j∈n\Θ. In StepP1, Pci chooses a random element rci∈Fp, calculates xci=grcimodq, and sends xci to V; in StepV1, V returns a challenge z∈1,2 to Pci; in StepP2, after receiving the challenge z, Pci randomly chooses yci from Fp, since he does not know the secret key sci of honest Pj; and in StepV2, V computes(15)gy1+y2+⋯+ynB0z=∏j=1nximodqwith probability 1/q. That is, the corrupted provers Pc1,…,Pcθ choose yc1,…,ycθ, respectively, such that(16)∑i=1θyci=∑i=1θrci−∑i=1θzdciscimodp,with probability 1/q. If Pn\Θ∪PΘ and V sequentially perform the PROTOCOL 2 for K times, then the success probability of the following equality(17)gy1+y2+⋯+ynB0z=∏j=1nxjmodqfalls to 1/qK.In the third setting, the verifierV is not certain of the number of all provers. In this case, θ corrupted provers pretend to be ν≠θ honest provers. Based on the proof of the second setting, we can prove that the prover set Pn\Θ∪Pc1,…,Pcν shares a secret s such that B0=gsmodq with the success probability 1/qK.In light of the foregoing, for all sufficiently largeK, the probability 1/qK is negligible. Consequently, the property of soundness is matched.


#### 4.1.3. Zero-Knowledge

To prove the property of zero-knowledge, we consider passive scenarios according to the power of the adversary.A passive verifierV does not randomly choose zη in the ηth time when running the protocol. Thus, he can use some 1,2-valued function f to compute zη in deterministic polynomial time [39]. Therefore, we define fp,q,g,B0,G,h,Vη−1,x1,η,…,xn,η=zη, where h is a secret input; Vη−1 denotes all data viewed when V executes the protocol in the η−1-th time; x1,η,…,xn,η denotes a message sent to V in StepP1 when running PROTOCOL 2 in the ηth time. Suppose that a simulator M has been constructed with the input p,q,g,h,B0,andG and has successfully simulated PROTOCOL 2 η−1 times, then M will simulate the ηth time according to the following program:DO FOREVERzη′:= a random number of 1,2yi,η:= a random number of Fp for i∈ndi,η:= a random number of Fp for i∈n−1si,η:= a random number of Fp for i∈n−1COMPUTEri,η:=yi,η+zη′di,ηsi,ηmodp, xi,η:=gri,ηmodqfori∈n−1, and xn,η=gy1,η+y2,η+⋯+yn,ηB0zη′/∏i=1n−1xi,ηmodqIFzη′=fp,q,g,h,B0,Vη−1,x1,η,…,xn,η THENOUTPUTx1,η,x2,η,…,xn,η,zη′,y1,η,y2,η,…,yn,η and HALTELSEGO back to the first step and repeat againEND DOLetP1,…,Pn,V be an interactive protocol performed among P1,…,Pn and V. Suppose that P1,…,Pn,V have been executed m times. According to the description of Vη−1, Vη is denoted by x1,1,⋯,xn,1,z1,y1,1,…,yn,1,…,x1,η,…,xn,η,zη,y1,η,…,yn,η, and the mth output is denoted by OutVm=ViewP1c1s1,…,Pncnsn,Vhp,q,g,B0,G=Vm (if m=0, OutV0 denotes an empty set). Suppose that the output of M for m times after the simulation is denoted by Mp,q,g,h,B0,G=x1,1,…,xn,1,z1′,y1,1,…,yn,1,…,x1,m,…,xn,m,zm′,y1,m,…,yn,m.According to Definition15, we can determine whether ensembles Mp,q,g,h,B0,G and ViewP1c1s1,…,Pncnsn,Vh are computational indistinguishability, and then the protocol which we constructed is zero-knowledge. Hence, to prove that Mp,q,g,h,B0,G and ViewP1c1s1,…,Pncnsn,Vhp,q,g,B0,G are computational indistinguishability, we use a mathematical induction method to perform the following steps:(1)
Let the probability ofOutVη be denoted by PℳV,η if OutVη⊆ℳp,q,g,B0,G and the probability of OutVη be denoted by PrP1,…,Pn,V,η if OutVη⊆ViewP1d1s1,…,Pndnsn,Vhp,q,g,B0,G.(2)
Whenη=0, in the initial state of interactive proof system P1,…,Pn,V there is PrℳV,0=PrP1,…,Pn,V,0 and PrℳV,0−PrP1,…,Pn,V,0<3F5, where ε>0 is an arbitrarily small constant.(3)
In theη−1th operation, we assume that PrℳV,η−1−PrP1,…,Pn,V,η−1<ε is satisfied for each η≥1.(4)
In theηth operation, we consider two models:(I)
In the real model, we considerP1,…,Pn,V. Assume that V chooses zη=1 with probability ϑ; then, V chooses zη=2 with probability 1−ϑ. Every prover Pi∈Pn selects ri∈Fp with probability 1/p for i∈n. Additionally, the probability of yi,η is 1/p since yi,η is computed from ri, where i∈n. Therefore, the probability of all messages that V viewed in the ηth time, i.e., x1,η,…,xn,η,zη,y1,η,…,yn,η is ϑ/pn when zη=1 and 1−ϑ/pn otherwise when zη=2.(II)
In the ideal model, we consider the simulatorM. In the ηth simulation, M takes as input p,q,g,h,B0,andG and chooses y1,η,y2,η,…,yn,η∈Fp with a probability of 1/pn. Later, V and M choose zη=1 and zη′=1 with a probability of ϑ/2, respectively. Meanwhile, V and M choose zη=2 and zη′=2 with the probability of 1−ϑ/2, respectively. Suppose that zη=zη′=1 or zη=zη′=2; then, M outputs the effective output x1,η,…,xn,η,tη′,y1,η,…,yn,η in the ηth time with probability 1/2. Hence, the probability of x1,η,…,xn,η,1,y1,η,…,yn,η as an effective output of M is(18)ϑpn⋅12+ϑpn⋅122+ϑpn⋅123+⋯=12⋅ϑpn1+12+⋯=ϑpn,and the probability ofx1,η,…,xn,η,2,y1,η,…,yn,η as an effective output of M is(19)1−ϑpn⋅12+1−ϑpn⋅122+1−ϑpn⋅123+⋯=12⋅1−ϑpn1+12+⋯=1−ϑpn.In fact,zη and zη′,y1,η,…,yn,η are selected randomly and independently, the case z=1 yields that PrP1,…,Prn,V,η=PP1,…,Pn,V,η−1⋅ϑ/pn, and z=2 results in PrP1,…,Prn,V,η=PrP1,…,Pn,V,η−1⋅1−ϑ/pn.Suppose in theη−1th time that PrMV,η−1−PrP1,P2,…,Pn,V,η−1<ε; then, in the ηth time, we have(20)PrMV,η−PrP1,…,Pn,V,η=PrP1,…,Pn,V,η−1⋅ϑpn−PrP1,…,Pn,V,η−1⋅1−ϑpn=PrMV,η−1−PrP1,…,Pn,V,η−1⋅maxϑ,1−ϑpn=ε⋅maxϑ,1−ϑpn.This is a negligible amount; thus, we know thatMp,q,g,h,B0,G and ViewP1d1s1,…,P1dnsn,Vhp,q,g,h,B0,G are computationally indistinguishable.


### 4.2. Theorems from PROTOCOL 2

Theorem 1.
PROTOCOL 2 is ann-prover computational zero-knowledge proof system.Proof.
According to the context of Section4.1 and Definition 15, PROTOCOL 2 satisfies completeness, soundness, and zero-knowledge. Consequently, PROTOCOL 2 is an n-prover computational zero-knowledge proof system.Theorem 2.
LetC⊂Fqn+1 be linear n+1,k code. An adversary A is l-bounded. The corruption parties chosen by A is PΘ:=Pc1,…,Pcθ, where Θ is a subset of n with Θ=θ. Let f denote the family of leakage functions f1,…,fn, where fi:Fq⟶0,1li with ∑i∈Θ≤l. Suppose l^:=maxlii∈Θ and constl^=2l^sinπ/2l^/qsinπ/q<1 (when 2l^<q). If li<l^, then add “0” on the left of the codeword fidi such that the length of codeword is equal to the length of l^. There is(21)fC≈ϵfUn+1,where Un+1 is the uniform distribution on Fqn+1 and ϵ=1/2qn+1−kl^k. That is,(22)fidii∈n:d0d⟵C≈ϵfidii∈n:d0d⟵Un+1.Proof.
Our secret-sharing scheme is a linear (also additive) secret-sharing scheme, and the detailed proof is similar to Theorem 4.5 in [24].Theorem 3.
Under the bounded-leakage model, PROTOCOL 2 is anθ,l,ϵ-LRSS.Proof.
LetC be an n+1,n linear code. The secret s∈Fq is shared into n shares s=s1,…,sn such that s=∑i=1nsi. Let f=f1,…,fn be family of leakage functions where fi:Fq⟶0,1li,l^:=maxi∈nli. For 0∈Fq, Share0 is uniformly distributed on C and sample z⟵Share0. Note that e=1,0,…,0 and compute s⋅e=s,0,…,0. Then, we can obtain the coset of Share0 for the distribution Shares. For any secret s∈Fq, there is(23)fShares=fShare0+se=f′Share0,where f′=f1′,f2′,…,fn′ with f1′x=f1z+s and fi′=fi, for i=2,…,n.
For the uniform distrubtionUn+1 over C,(24)fUn+1=f′Un+1−se.
Then, statistical distance betweenf′Share0 and f′Un+1−se is f′Share0−f′Un+1−seSD≤1/2ql^n. According to the triangle inequality A−B≤A−X+X−B and two secrets s1,s2∈Fq, there is(25)fShares1−fShares2SD≤fShares1−fUn+1SD+fUn+1−fShares2SD≤ql^n.
Let the leakage protocolLeak is denoted by LeakΘ,fs=sΘ,fsΘsn\Θ. Then,(26)LeakΘ,fs:s←Shares1≈εLeakΘ,fs:s⟵Shares2,where ε=1/2ql^n.


## 4.1. Properties from PROTOCOL 2 in Random Oracle Model

### 4.1.1. Completeness

Assume thatPc1,…,Pcm is a subset of Pn=P1,…,Pn. Pc1,…,Pcm and V execute the abovementioned interactive protocol. V computes the following equation:(13)gyc1+yc2+⋯+ycmB0z=gyc1+yc2+⋯+ycmgsz=gyc1+yc2+⋯+ycmgz∑i=1mscidci=∏i=1mgyci+zdcisci=∏i=1mgrci=∏i=1mxcimodq.If the last equation in equation (13) is satisfied, then V believes that Pc1,…,Pcm share the secret s satisfying B0=gsmodq.


### 4.1.2. Soundness

To prove the property of soundness, we consider the following three settings.In the first setting, for all of thePn=P1,…,Pn, let Pc0 be the only one prover corrupted by adversary A. Pco pretends to be an honest prover Pj∈Pn, where i∈n. After interacting with V in StepP1, he randomly selects ri∈Fp and computes xj=grjmodq; then, he sends xj to V. Next, V sends the challenge z to Pco, who randomly chooses yj∈Fp, because he does not know the secret sj (held by the honest prover Pj), where j∈n. Then, the success probability of equality(14)gy1+y2+⋯+ynB0z=∏j=1nxjmodqis 1/q. If the interactive protocol executed for K times, the success probability is 1/qK.In the second setting, the adversaryA chooses a subset of Θ⊆n with Θ=θ and get their shares. Let PΘ:=Pc1,…,Pcθ denote the subset of Pn, the adversary A chooses to corrupt in consecutive rounds. The honest parties are denoted by Pn\Θ. Assume that V knows the total number of all provers. Each Pci∈PΘ disguises himself as the honest provers Pj∈Pn\Θ to follow the interactive protocol with V, where i∈θ,j∈n\Θ. In StepP1, Pci chooses a random element rci∈Fp, calculates xci=grcimodq, and sends xci to V; in StepV1, V returns a challenge z∈1,2 to Pci; in StepP2, after receiving the challenge z, Pci randomly chooses yci from Fp, since he does not know the secret key sci of honest Pj; and in StepV2, V computes(15)gy1+y2+⋯+ynB0z=∏j=1nximodqwith probability 1/q. That is, the corrupted provers Pc1,…,Pcθ choose yc1,…,ycθ, respectively, such that(16)∑i=1θyci=∑i=1θrci−∑i=1θzdciscimodp,with probability 1/q. If Pn\Θ∪PΘ and V sequentially perform the PROTOCOL 2 for K times, then the success probability of the following equality(17)gy1+y2+⋯+ynB0z=∏j=1nxjmodqfalls to 1/qK.In the third setting, the verifierV is not certain of the number of all provers. In this case, θ corrupted provers pretend to be ν≠θ honest provers. Based on the proof of the second setting, we can prove that the prover set Pn\Θ∪Pc1,…,Pcν shares a secret s such that B0=gsmodq with the success probability 1/qK.In light of the foregoing, for all sufficiently largeK, the probability 1/qK is negligible. Consequently, the property of soundness is matched.


### 4.1.3. Zero-Knowledge

To prove the property of zero-knowledge, we consider passive scenarios according to the power of the adversary.A passive verifierV does not randomly choose zη in the ηth time when running the protocol. Thus, he can use some 1,2-valued function f to compute zη in deterministic polynomial time [39]. Therefore, we define fp,q,g,B0,G,h,Vη−1,x1,η,…,xn,η=zη, where h is a secret input; Vη−1 denotes all data viewed when V executes the protocol in the η−1-th time; x1,η,…,xn,η denotes a message sent to V in StepP1 when running PROTOCOL 2 in the ηth time. Suppose that a simulator M has been constructed with the input p,q,g,h,B0,andG and has successfully simulated PROTOCOL 2 η−1 times, then M will simulate the ηth time according to the following program:DO FOREVERzη′:= a random number of 1,2yi,η:= a random number of Fp for i∈ndi,η:= a random number of Fp for i∈n−1si,η:= a random number of Fp for i∈n−1COMPUTEri,η:=yi,η+zη′di,ηsi,ηmodp, xi,η:=gri,ηmodqfori∈n−1, and xn,η=gy1,η+y2,η+⋯+yn,ηB0zη′/∏i=1n−1xi,ηmodqIFzη′=fp,q,g,h,B0,Vη−1,x1,η,…,xn,η THENOUTPUTx1,η,x2,η,…,xn,η,zη′,y1,η,y2,η,…,yn,η and HALTELSEGO back to the first step and repeat againEND DOLetP1,…,Pn,V be an interactive protocol performed among P1,…,Pn and V. Suppose that P1,…,Pn,V have been executed m times. According to the description of Vη−1, Vη is denoted by x1,1,⋯,xn,1,z1,y1,1,…,yn,1,…,x1,η,…,xn,η,zη,y1,η,…,yn,η, and the mth output is denoted by OutVm=ViewP1c1s1,…,Pncnsn,Vhp,q,g,B0,G=Vm (if m=0, OutV0 denotes an empty set). Suppose that the output of M for m times after the simulation is denoted by Mp,q,g,h,B0,G=x1,1,…,xn,1,z1′,y1,1,…,yn,1,…,x1,m,…,xn,m,zm′,y1,m,…,yn,m.According to Definition15, we can determine whether ensembles Mp,q,g,h,B0,G and ViewP1c1s1,…,Pncnsn,Vh are computational indistinguishability, and then the protocol which we constructed is zero-knowledge. Hence, to prove that Mp,q,g,h,B0,G and ViewP1c1s1,…,Pncnsn,Vhp,q,g,B0,G are computational indistinguishability, we use a mathematical induction method to perform the following steps:(1)
Let the probability ofOutVη be denoted by PℳV,η if OutVη⊆ℳp,q,g,B0,G and the probability of OutVη be denoted by PrP1,…,Pn,V,η if OutVη⊆ViewP1d1s1,…,Pndnsn,Vhp,q,g,B0,G.(2)
Whenη=0, in the initial state of interactive proof system P1,…,Pn,V there is PrℳV,0=PrP1,…,Pn,V,0 and PrℳV,0−PrP1,…,Pn,V,0<3F5, where ε>0 is an arbitrarily small constant.(3)
In theη−1th operation, we assume that PrℳV,η−1−PrP1,…,Pn,V,η−1<ε is satisfied for each η≥1.(4)
In theηth operation, we consider two models:(I)
In the real model, we considerP1,…,Pn,V. Assume that V chooses zη=1 with probability ϑ; then, V chooses zη=2 with probability 1−ϑ. Every prover Pi∈Pn selects ri∈Fp with probability 1/p for i∈n. Additionally, the probability of yi,η is 1/p since yi,η is computed from ri, where i∈n. Therefore, the probability of all messages that V viewed in the ηth time, i.e., x1,η,…,xn,η,zη,y1,η,…,yn,η is ϑ/pn when zη=1 and 1−ϑ/pn otherwise when zη=2.(II)
In the ideal model, we consider the simulatorM. In the ηth simulation, M takes as input p,q,g,h,B0,andG and chooses y1,η,y2,η,…,yn,η∈Fp with a probability of 1/pn. Later, V and M choose zη=1 and zη′=1 with a probability of ϑ/2, respectively. Meanwhile, V and M choose zη=2 and zη′=2 with the probability of 1−ϑ/2, respectively. Suppose that zη=zη′=1 or zη=zη′=2; then, M outputs the effective output x1,η,…,xn,η,tη′,y1,η,…,yn,η in the ηth time with probability 1/2. Hence, the probability of x1,η,…,xn,η,1,y1,η,…,yn,η as an effective output of M is(18)ϑpn⋅12+ϑpn⋅122+ϑpn⋅123+⋯=12⋅ϑpn1+12+⋯=ϑpn,and the probability ofx1,η,…,xn,η,2,y1,η,…,yn,η as an effective output of M is(19)1−ϑpn⋅12+1−ϑpn⋅122+1−ϑpn⋅123+⋯=12⋅1−ϑpn1+12+⋯=1−ϑpn.In fact,zη and zη′,y1,η,…,yn,η are selected randomly and independently, the case z=1 yields that PrP1,…,Prn,V,η=PP1,…,Pn,V,η−1⋅ϑ/pn, and z=2 results in PrP1,…,Prn,V,η=PrP1,…,Pn,V,η−1⋅1−ϑ/pn.Suppose in theη−1th time that PrMV,η−1−PrP1,P2,…,Pn,V,η−1<ε; then, in the ηth time, we have(20)PrMV,η−PrP1,…,Pn,V,η=PrP1,…,Pn,V,η−1⋅ϑpn−PrP1,…,Pn,V,η−1⋅1−ϑpn=PrMV,η−1−PrP1,…,Pn,V,η−1⋅maxϑ,1−ϑpn=ε⋅maxϑ,1−ϑpn.This is a negligible amount; thus, we know thatMp,q,g,h,B0,G and ViewP1d1s1,…,P1dnsn,Vhp,q,g,h,B0,G are computationally indistinguishable.


## 4.1.1. Completeness

Assume thatPc1,…,Pcm is a subset of Pn=P1,…,Pn. Pc1,…,Pcm and V execute the abovementioned interactive protocol. V computes the following equation:(13)gyc1+yc2+⋯+ycmB0z=gyc1+yc2+⋯+ycmgsz=gyc1+yc2+⋯+ycmgz∑i=1mscidci=∏i=1mgyci+zdcisci=∏i=1mgrci=∏i=1mxcimodq.If the last equation in equation (13) is satisfied, then V believes that Pc1,…,Pcm share the secret s satisfying B0=gsmodq.


## 4.1.2. Soundness

To prove the property of soundness, we consider the following three settings.In the first setting, for all of thePn=P1,…,Pn, let Pc0 be the only one prover corrupted by adversary A. Pco pretends to be an honest prover Pj∈Pn, where i∈n. After interacting with V in StepP1, he randomly selects ri∈Fp and computes xj=grjmodq; then, he sends xj to V. Next, V sends the challenge z to Pco, who randomly chooses yj∈Fp, because he does not know the secret sj (held by the honest prover Pj), where j∈n. Then, the success probability of equality(14)gy1+y2+⋯+ynB0z=∏j=1nxjmodqis 1/q. If the interactive protocol executed for K times, the success probability is 1/qK.In the second setting, the adversaryA chooses a subset of Θ⊆n with Θ=θ and get their shares. Let PΘ:=Pc1,…,Pcθ denote the subset of Pn, the adversary A chooses to corrupt in consecutive rounds. The honest parties are denoted by Pn\Θ. Assume that V knows the total number of all provers. Each Pci∈PΘ disguises himself as the honest provers Pj∈Pn\Θ to follow the interactive protocol with V, where i∈θ,j∈n\Θ. In StepP1, Pci chooses a random element rci∈Fp, calculates xci=grcimodq, and sends xci to V; in StepV1, V returns a challenge z∈1,2 to Pci; in StepP2, after receiving the challenge z, Pci randomly chooses yci from Fp, since he does not know the secret key sci of honest Pj; and in StepV2, V computes(15)gy1+y2+⋯+ynB0z=∏j=1nximodqwith probability 1/q. That is, the corrupted provers Pc1,…,Pcθ choose yc1,…,ycθ, respectively, such that(16)∑i=1θyci=∑i=1θrci−∑i=1θzdciscimodp,with probability 1/q. If Pn\Θ∪PΘ and V sequentially perform the PROTOCOL 2 for K times, then the success probability of the following equality(17)gy1+y2+⋯+ynB0z=∏j=1nxjmodqfalls to 1/qK.In the third setting, the verifierV is not certain of the number of all provers. In this case, θ corrupted provers pretend to be ν≠θ honest provers. Based on the proof of the second setting, we can prove that the prover set Pn\Θ∪Pc1,…,Pcν shares a secret s such that B0=gsmodq with the success probability 1/qK.In light of the foregoing, for all sufficiently largeK, the probability 1/qK is negligible. Consequently, the property of soundness is matched.


## 4.1.3. Zero-Knowledge

To prove the property of zero-knowledge, we consider passive scenarios according to the power of the adversary.A passive verifierV does not randomly choose zη in the ηth time when running the protocol. Thus, he can use some 1,2-valued function f to compute zη in deterministic polynomial time [39]. Therefore, we define fp,q,g,B0,G,h,Vη−1,x1,η,…,xn,η=zη, where h is a secret input; Vη−1 denotes all data viewed when V executes the protocol in the η−1-th time; x1,η,…,xn,η denotes a message sent to V in StepP1 when running PROTOCOL 2 in the ηth time. Suppose that a simulator M has been constructed with the input p,q,g,h,B0,andG and has successfully simulated PROTOCOL 2 η−1 times, then M will simulate the ηth time according to the following program:DO FOREVERzη′:= a random number of 1,2yi,η:= a random number of Fp for i∈ndi,η:= a random number of Fp for i∈n−1si,η:= a random number of Fp for i∈n−1COMPUTEri,η:=yi,η+zη′di,ηsi,ηmodp, xi,η:=gri,ηmodqfori∈n−1, and xn,η=gy1,η+y2,η+⋯+yn,ηB0zη′/∏i=1n−1xi,ηmodqIFzη′=fp,q,g,h,B0,Vη−1,x1,η,…,xn,η THENOUTPUTx1,η,x2,η,…,xn,η,zη′,y1,η,y2,η,…,yn,η and HALTELSEGO back to the first step and repeat againEND DOLetP1,…,Pn,V be an interactive protocol performed among P1,…,Pn and V. Suppose that P1,…,Pn,V have been executed m times. According to the description of Vη−1, Vη is denoted by x1,1,⋯,xn,1,z1,y1,1,…,yn,1,…,x1,η,…,xn,η,zη,y1,η,…,yn,η, and the mth output is denoted by OutVm=ViewP1c1s1,…,Pncnsn,Vhp,q,g,B0,G=Vm (if m=0, OutV0 denotes an empty set). Suppose that the output of M for m times after the simulation is denoted by Mp,q,g,h,B0,G=x1,1,…,xn,1,z1′,y1,1,…,yn,1,…,x1,m,…,xn,m,zm′,y1,m,…,yn,m.According to Definition15, we can determine whether ensembles Mp,q,g,h,B0,G and ViewP1c1s1,…,Pncnsn,Vh are computational indistinguishability, and then the protocol which we constructed is zero-knowledge. Hence, to prove that Mp,q,g,h,B0,G and ViewP1c1s1,…,Pncnsn,Vhp,q,g,B0,G are computational indistinguishability, we use a mathematical induction method to perform the following steps:(1)
Let the probability ofOutVη be denoted by PℳV,η if OutVη⊆ℳp,q,g,B0,G and the probability of OutVη be denoted by PrP1,…,Pn,V,η if OutVη⊆ViewP1d1s1,…,Pndnsn,Vhp,q,g,B0,G.(2)
Whenη=0, in the initial state of interactive proof system P1,…,Pn,V there is PrℳV,0=PrP1,…,Pn,V,0 and PrℳV,0−PrP1,…,Pn,V,0<3F5, where ε>0 is an arbitrarily small constant.(3)
In theη−1th operation, we assume that PrℳV,η−1−PrP1,…,Pn,V,η−1<ε is satisfied for each η≥1.(4)
In theηth operation, we consider two models:(I)
In the real model, we considerP1,…,Pn,V. Assume that V chooses zη=1 with probability ϑ; then, V chooses zη=2 with probability 1−ϑ. Every prover Pi∈Pn selects ri∈Fp with probability 1/p for i∈n. Additionally, the probability of yi,η is 1/p since yi,η is computed from ri, where i∈n. Therefore, the probability of all messages that V viewed in the ηth time, i.e., x1,η,…,xn,η,zη,y1,η,…,yn,η is ϑ/pn when zη=1 and 1−ϑ/pn otherwise when zη=2.(II)
In the ideal model, we consider the simulatorM. In the ηth simulation, M takes as input p,q,g,h,B0,andG and chooses y1,η,y2,η,…,yn,η∈Fp with a probability of 1/pn. Later, V and M choose zη=1 and zη′=1 with a probability of ϑ/2, respectively. Meanwhile, V and M choose zη=2 and zη′=2 with the probability of 1−ϑ/2, respectively. Suppose that zη=zη′=1 or zη=zη′=2; then, M outputs the effective output x1,η,…,xn,η,tη′,y1,η,…,yn,η in the ηth time with probability 1/2. Hence, the probability of x1,η,…,xn,η,1,y1,η,…,yn,η as an effective output of M is(18)ϑpn⋅12+ϑpn⋅122+ϑpn⋅123+⋯=12⋅ϑpn1+12+⋯=ϑpn,and the probability ofx1,η,…,xn,η,2,y1,η,…,yn,η as an effective output of M is(19)1−ϑpn⋅12+1−ϑpn⋅122+1−ϑpn⋅123+⋯=12⋅1−ϑpn1+12+⋯=1−ϑpn.In fact,zη and zη′,y1,η,…,yn,η are selected randomly and independently, the case z=1 yields that PrP1,…,Prn,V,η=PP1,…,Pn,V,η−1⋅ϑ/pn, and z=2 results in PrP1,…,Prn,V,η=PrP1,…,Pn,V,η−1⋅1−ϑ/pn.Suppose in theη−1th time that PrMV,η−1−PrP1,P2,…,Pn,V,η−1<ε; then, in the ηth time, we have(20)PrMV,η−PrP1,…,Pn,V,η=PrP1,…,Pn,V,η−1⋅ϑpn−PrP1,…,Pn,V,η−1⋅1−ϑpn=PrMV,η−1−PrP1,…,Pn,V,η−1⋅maxϑ,1−ϑpn=ε⋅maxϑ,1−ϑpn.This is a negligible amount; thus, we know thatMp,q,g,h,B0,G and ViewP1d1s1,…,P1dnsn,Vhp,q,g,h,B0,G are computationally indistinguishable.


## 4.2. Theorems from PROTOCOL 2

Theorem 1.
PROTOCOL 2 is ann-prover computational zero-knowledge proof system.Proof.
According to the context of Section4.1 and Definition 15, PROTOCOL 2 satisfies completeness, soundness, and zero-knowledge. Consequently, PROTOCOL 2 is an n-prover computational zero-knowledge proof system.Theorem 2.
LetC⊂Fqn+1 be linear n+1,k code. An adversary A is l-bounded. The corruption parties chosen by A is PΘ:=Pc1,…,Pcθ, where Θ is a subset of n with Θ=θ. Let f denote the family of leakage functions f1,…,fn, where fi:Fq⟶0,1li with ∑i∈Θ≤l. Suppose l^:=maxlii∈Θ and constl^=2l^sinπ/2l^/qsinπ/q<1 (when 2l^<q). If li<l^, then add “0” on the left of the codeword fidi such that the length of codeword is equal to the length of l^. There is(21)fC≈ϵfUn+1,where Un+1 is the uniform distribution on Fqn+1 and ϵ=1/2qn+1−kl^k. That is,(22)fidii∈n:d0d⟵C≈ϵfidii∈n:d0d⟵Un+1.Proof.
Our secret-sharing scheme is a linear (also additive) secret-sharing scheme, and the detailed proof is similar to Theorem 4.5 in [24].Theorem 3.
Under the bounded-leakage model, PROTOCOL 2 is anθ,l,ϵ-LRSS.Proof.
LetC be an n+1,n linear code. The secret s∈Fq is shared into n shares s=s1,…,sn such that s=∑i=1nsi. Let f=f1,…,fn be family of leakage functions where fi:Fq⟶0,1li,l^:=maxi∈nli. For 0∈Fq, Share0 is uniformly distributed on C and sample z⟵Share0. Note that e=1,0,…,0 and compute s⋅e=s,0,…,0. Then, we can obtain the coset of Share0 for the distribution Shares. For any secret s∈Fq, there is(23)fShares=fShare0+se=f′Share0,where f′=f1′,f2′,…,fn′ with f1′x=f1z+s and fi′=fi, for i=2,…,n.
For the uniform distrubtionUn+1 over C,(24)fUn+1=f′Un+1−se.
Then, statistical distance betweenf′Share0 and f′Un+1−se is f′Share0−f′Un+1−seSD≤1/2ql^n. According to the triangle inequality A−B≤A−X+X−B and two secrets s1,s2∈Fq, there is(25)fShares1−fShares2SD≤fShares1−fUn+1SD+fUn+1−fShares2SD≤ql^n.
Let the leakage protocolLeak is denoted by LeakΘ,fs=sΘ,fsΘsn\Θ. Then,(26)LeakΘ,fs:s←Shares1≈εLeakΘ,fs:s⟵Shares2,where ε=1/2ql^n.


## 5. Group Identification via PROTOCOL 2

According to Def. 17 in Section2.3 and PROTOCOL 2, we can construct a group identification protocol GID-scheme with the following properties: the valid identities can be believed by the verifier only for the qualified group members, not the unqualified members; the verifier gains nothing other than believing that the qualified members have valid identities. Let Pn=P1,…,Pn be a group set, and let Pn,V be an n-prover interactive proof system. The GID-scheme ParGen,KeyGen,Pn,V can be constructed by Table 2.Table 2
Our GID-scheme.
–params⟵ParGen1λ: perform the Initialization of PROTOCOL 2 in Section 3, and set params=B0,p,q,g,G
(i)pk¯,sk¯⟵KeyGen: execute the distribution protocol of PROTOCOL 2 in Section 3, and set sk¯=s0∪sii=1n and pk¯=pk0∪pki=gskimodqi=1n, where sk=s=s0,pk0=gs0modq and ski=si for i∈n
(ii)P,V: the PPT turning machines P,V run the following protocol:
S
t
e
p
P
1: for i∈n, every Pi chooses ri∈Fq, and sends αi=grimodq to V
S
t
e
p
V
1: choose a random number βi∈1,2 and send the challenge βi to every Pi. Set βi=z, for any i,j∈n
S
t
e
p
P
2: for i∈n, every Pi computes γi=ri−zdiskimodp and sends γi to V
S
t
e
p
V
2: for i∈n, V accepts the identification of Pi if and only if the transcript αi,βi,γi is satisfied OutVαi,βi,γi=?1According to the work presented in [37, 40], our GID-scheme is secure against (classical) passive attacks.Theorem 4.
LetParGen,KeyGen,Pn,V be a GID-scheme and R=pk¯,sk¯sk¯=s0∪sii=1n,pk¯=pk0∪pki=gskimodqi=1n be a hard relation with key generator KeyGen. We write Pn,V to denote the prover set and the verifier in a ∑-protocol for R with 2-bit challenges. Suppose that the ∑-protocol is complete, 2-special sound, and honest verifier zero-knowledge. Then, our GID-scheme is secure against emulation under active attacks.Proof.
If we writepk¯,sk¯⟵KeyGen by the notation x,y⟵K1λ and the transcript xi,t,yi by the notation αi,βi,γi, then the ∑− protocol and our GID-scheme are equal, where i∈n. For details, see Theorem 5 of [41].
In the bounded-leakage model, we have the following theorem.Theorem 5.
Under the discrete logarithm assumption, our GID-scheme is actively secure under pre-emulation attacks with leakagel=n−1logq−λ⩾1−2/nsk bits. It is secure against an arbitrary time leakage attack with l∗=1/2l bits.Proof.
Through the contradiction assumption, in the pre-emulation leakage attack gameIDprelλA∗ there is an adversary A∗ with a nonnegligible advantage. Then, we need to detect two different secret keys sk¯ and sk¯∗ for a public key pk¯, for the randomly chosen params∗, since params is not known. In fact, in the test phase, M randomly chooses the pk¯,sk¯ key pair and utilizes sk¯ to model the leakage oracle Osk¯λ,l⋅ and an honest prover oracle P for the adversary A∗. Later, in the emulation phase, Mperforms A∗ twice (for attack games IDprelλA∗,IDarblλA∗), with two distinct randomly chosen challenges β,β∗. Because A∗ generates two valid transcripts α,β,γ,α,β∗,γ with a nonnegligible advantage, M can recover or find a secret key sk¯∗ by using these two transcripts, according to the 2-special soundness property of the ∑-protocol.
We now need to analyze the probability ofsk¯=sk¯∗. Table 3 presents three experiments that are performed by the adversary A∗. In experiment Ext0, A∗ obtains pk¯ and can access the oracle Osk¯λ,l⋅,Ppk¯,sk¯; in experiment Ext1, A∗ obtains pk¯ and only accesses the oracle Ppk¯,sk¯; in experiment Ext2, A∗ only obtains pk¯. According to the construction of Ext0,Ext1, and Ext2, we obtain the following inequality:(27)H˜∞sk¯Ext0≥H˜∞sk¯Ext1−l≥H˜∞sk¯Ext2−l=H˜∞sk¯pk¯−l≥n−1logq−l≥λ.where H∞X=−logmaxx∈XPrXx denotes the mini-entropy of a random variable X with probability distribution PrX over X, and H˜∞XExt=−logmaxAPrAExt⋅x denotes the (average-) conditional mini-entropy of a random variable X conditioned on experiment Ext. The detailed proof of equation (27) can be found in [20]. Due to the above mentioned equation, M outputs sk¯=sk¯∗ with the upper bound of probability 2−λ. Therefore, M generates two different secure keys sk¯andsk¯∗ with a nonnegligible advantage.
For an arbitrary time leakage gameIDarblλA, in the emulation phase, M can access the leakage oracle with l∗ bits. Based on two distinct challenges, M performs the emulation phase twice; thus, the leakage bit is 2l∗. Consequently, only l∗=1/2l bits of arbitrary time leakage can be handled.Table 3
Experiments performed by the adversaryA∗.
Ext
0
Ext
1
Ex
t
2
(i)A∗ holds the public key pk¯(ii) A∗ allows access to the leakage oracle Osk¯λ,l⋅ and an honest prover oracle Ppk¯,sk¯
(i)A∗ holds the public key pk¯(ii) A∗ only allows access to the honest prover oracle Ppk¯,sk¯
(i)A∗ only obtains access to the public key pk¯


### 5.1. Comparisons with Other Schemes

In this section, we compare our ID-scheme with several previous works. According to the construction of the GID-schemes, we summarize the main parameters in Table4. The first column presents the compared related works. The second column indicates the size of the public parameters shared by all parties. The third and fourth columns indicate the size of the public key and secret key, respectively. The fifth column denotes the size of each party’ s communication complexity. The last column shows the size of allowed leakage l, which was measured in bits.Table 4
Comparison of our scheme with other schemes.
Scheme
params
p
k
s
k
Comm.
Leakagel bits
Okamato
m
λ [42]
m
1
m
m
+
O
1
≈
1
−
1
/
m
s
k
[20]
DirProd
n
,
m
,
t
λ
m
1
m
n
O
t
m
≈
1
−
1
/
m
−
O
t
/
λ
s
k
ComDirProd
n
,
m
,
t
λ
m
1
m
n
m
+
O
1
≈
1
−
1
/
m
−
O
t
/
λ
s
k
LpSS [38]
n
1
n
O
n
log
p
=
0
Local LRLSS [24]
n
1
n
O
n
=
log
p
/
4
Our scheme
n
1
n
O
n
log
q
≈
1
−
2
/
n
s
kThe comparison of schemes in Table4 is summaried as follows:TheOkamatomλ scheme in [42] uses m generators and can tolerate the leakage bit l=1−1/msk, where λ denotes the security parameter. This scheme only provides an adequate method for relative leakage1−1/m, not for large absolute leakage l, and it does not provide a proportional increase in communication complexity.As an extension of theOkamatomλ scheme, the researchers in [20] propose two schemes (DirProdn,m,tλ and ComDirProdn,m,tλ), which add two additional parameters n (the number of Okamatomλ key pairs stored) and t (≈Omλ, the number of Okamatomλ keys used). DirProdn,m,tλ and ComDirProdn,m,tλ can tolerate leakage bits 1−1/m−Ot/λsk and 1−1/m−Ot/λsk, respectively.In [38], the authors constructed a leakproof SSS by using threshold SSS, and they also proved that the master secret s can be shared an arbitrary number of times. However, their schemes do not consider the security of the scenario where there is some information leaked.Local LRLSS [24] provides a local leakage-resilience of (additive or n,t-Shamir) SSS over field Fp (p is a large prime), which is secure under local leakage attacks when logp/4 bits are leaked from every share.Inspired by the work of [38], in our scheme, we construct a secret-sharing scheme by using linear codes for realizing a access structure, in which the master key can be shared as many times as designed in the random oracle model. Moreover, our scheme is θ,l,ϵ-LRSS under the bounded-leakage model. Based on our LRSS scheme, we construct a GID-scheme, which is proven to be leakage-resilient under the attacks IDprelλA and IDarblλA.


## 5.1. Comparisons with Other Schemes

In this section, we compare our ID-scheme with several previous works. According to the construction of the GID-schemes, we summarize the main parameters in Table4. The first column presents the compared related works. The second column indicates the size of the public parameters shared by all parties. The third and fourth columns indicate the size of the public key and secret key, respectively. The fifth column denotes the size of each party’ s communication complexity. The last column shows the size of allowed leakage l, which was measured in bits.Table 4
Comparison of our scheme with other schemes.
Scheme
params
p
k
s
k
Comm.
Leakagel bits
Okamato
m
λ [42]
m
1
m
m
+
O
1
≈
1
−
1
/
m
s
k
[20]
DirProd
n
,
m
,
t
λ
m
1
m
n
O
t
m
≈
1
−
1
/
m
−
O
t
/
λ
s
k
ComDirProd
n
,
m
,
t
λ
m
1
m
n
m
+
O
1
≈
1
−
1
/
m
−
O
t
/
λ
s
k
LpSS [38]
n
1
n
O
n
log
p
=
0
Local LRLSS [24]
n
1
n
O
n
=
log
p
/
4
Our scheme
n
1
n
O
n
log
q
≈
1
−
2
/
n
s
kThe comparison of schemes in Table4 is summaried as follows:TheOkamatomλ scheme in [42] uses m generators and can tolerate the leakage bit l=1−1/msk, where λ denotes the security parameter. This scheme only provides an adequate method for relative leakage1−1/m, not for large absolute leakage l, and it does not provide a proportional increase in communication complexity.As an extension of theOkamatomλ scheme, the researchers in [20] propose two schemes (DirProdn,m,tλ and ComDirProdn,m,tλ), which add two additional parameters n (the number of Okamatomλ key pairs stored) and t (≈Omλ, the number of Okamatomλ keys used). DirProdn,m,tλ and ComDirProdn,m,tλ can tolerate leakage bits 1−1/m−Ot/λsk and 1−1/m−Ot/λsk, respectively.In [38], the authors constructed a leakproof SSS by using threshold SSS, and they also proved that the master secret s can be shared an arbitrary number of times. However, their schemes do not consider the security of the scenario where there is some information leaked.Local LRLSS [24] provides a local leakage-resilience of (additive or n,t-Shamir) SSS over field Fp (p is a large prime), which is secure under local leakage attacks when logp/4 bits are leaked from every share.Inspired by the work of [38], in our scheme, we construct a secret-sharing scheme by using linear codes for realizing a access structure, in which the master key can be shared as many times as designed in the random oracle model. Moreover, our scheme is θ,l,ϵ-LRSS under the bounded-leakage model. Based on our LRSS scheme, we construct a GID-scheme, which is proven to be leakage-resilient under the attacks IDprelλA and IDarblλA.


## 6. Conclusions and Future Work

We proposed a secret-sharing scheme that realized access structure based on linear codes. According to the definitions of zero-knowledge proof system and security model, we proved that our protocol is a multiprover zero-knowledge proof system in the random oracle model. Our protocol is also leakage-resilient secret-sharing scheme (LRSS) in the bounded-leakage model. In our LRSS, the security is guaranteed even if the adversary learns leakage information is bounded byl bits.Moreover, we presented a GID-scheme from our LRSS scheme, and it is leakage-resilient under the leakage attacksIDprelλA and IDarblλA in the bounded-leakage model. In our leakage-resilient GID-scheme, any authorized party sets can prove to the verifier that they share the secret key without leaking any information about their individual shares to adversary and can guarantee security even though l bits are retrieved by the malicious adversary; any authorized parties can prove themselves to keep the corresponding valid secret share.In future work, we want to construct a practical dynamic secret-sharing scheme. In this dynamic secret-sharing scheme, there are more than one access structure, and we want to enable only one of them to be active to reconstruct the predefined secret.



---

*Source: 1784276-2020-03-13.xml*