VSS using Integer Commitments

3. For any accusation from P_ψ(i), each party verifies that any o_i received is indeed the value thatcidecrypts to. If this is not the case this o_i is discarded.

4. Each party looks at all (non-discarded) o_i-values he knows. If any such o_i is inconsistent with C_i, then he rejects. Otherwise he accepts.

We need the following protocol to open a verifiable secret shared value.

Protocol Open(C)

All parties know commitments R1 =C, R2, . . . , Re, and for i= 1, . . . , d partyP_ψ(i) has openingoi = (si, ri) to commitment,

compk(si, ri) =Ci =

e

Y

j=1

R^m_j ^ij,

wheremij is defined byM = [mij].

1. Fori= 1, . . . , dparty P_ψ(i) broadcastso_i.

2. Upon receivingoi = (si, ri), check whether com_pk(si, ri) = Ci, if it holds addo_i to an initially empty collection O.

3. When O consists of share components of a qualified set of parties A ∈ Γ, then take the corresponding reconstruction vector λ = (λ1, . . . , λd)^T and let s=Pd

i=1λisi.

Note 5.2. The reconstruction vectorλused in step 3 in the aboveOpenprotocol only has non-zero entries for the entries corresponding to the accepted openings inO.

Theorem 5.2. Given a secure PKENO and a binding commitment scheme, then the protocols Share_pk(s) and Open(C) securely implement F_VSS, assuming anyQ2 access structureΓ.

Proof. To show that Share_pk(s) securely implements F_VSS, we are given an ad-versaryAand an environmentZ, and we need to construct a simulatorS. The simulator interacts with A to simulate its view of attacking the protocol, and on the other hand interacts withF_VSS on behalf of corrupt parties. This game is called the ideal process. This is compared to the real process, where Z and A are interacting with a real instance of the protocol. In both processes, Z andA may communicate at any time. The goal is now to show thatZ cannot distinguish the real from the ideal process. Our simulator works as follows:

1. The simulator generates the keys pk = (N, g, h),{(pk_j, skj)} following T’s algorithm, and sends all public keys to A, along with secret keys for corrupted parties.

2. The simulatorS now acts whenever required, as follows:

• IfA sends C and a proofπ to the broadcast functionality on behalf of corrupt dealer Dj, the simulator does the following: using its se-cret keys, it can decrypt ciphertext in π intended for honest parties and follow their algorithm to compute what they would send in the second round. This also lets it decide if the proof would be accepted.

If not, the simulator sends ⊥toF_VSS. If the proof is acceptable, ob-serve first that since Γ isQ2, the set of honest parties,A, is qualified, and that every honest party can open his commitment to si. Let λ be a reconstruction vector for A, that is, hs,λi = s and λ_A{ = 0, i.e., if λ= (λ₁, . . . , λ_d)^T then

d

X

i=1

λisi =

d

X

i=1

λi e

X

j=1

mijρj =ρ1 =s,

where λj = 0 for ψ(j)∈/ A. Hence, the above equation implies that Pd

i=1λimij =δ1j, whereδij = 1 ifi=j and 0 otherwise. Therefore, by the homomorphic property, the simulator can open commitment C⁰ =Qd

i=1C_i^λi tos⁰ =Pd

i=1λ_is_i. Now, since C⁰=

d

Y

i=1

C_i^λi =

d

Y

i=1





e

Y

j=1

R^m_j ^ij





λi

=

e

Y

j=1

R

P

iλimij

j =R₁=C,

we see that the simulator can extract from the proof a way to open commitment C to a value s. The simulator sends (Input, sid, s) to F_VSS on behalf of A.

• On input (Input, Dj) from F_VSS, where Dj is honest, the simulator simulates what D_j would send in the protocol, as follows: First, create a commitment to 0, i.e., C =com_pk(0, r). SinceS generated pk = (N, g, h) it follows that S knows ord(g) and ord(h), and a b such thatg=h^bmodN. The simulator S can at a later point open C to any value, simply by noting that,

com_pk(0, r) =com_pk(s, r−bs).

We therefore proceed, assuming implicitly thatC“contains”s. Now, let A be the set of corrupted parties. Then there exists a sweeping vectorκ such that MAκ=0 and hκ,εi= 1. Let ρ₀ = (r1, . . . , re)^T be a random distribution vector such that hρ₀,εi = 0, i.e., a dis-tribution vector to a random sharing of 0. Construct R⁰₁, . . . , R⁰_e as random commitments of r1, . . . , re, respectively, with the exception that R⁰₁ = 1 (or the commitment of r1 = 0 using randomness 0).

Then, by the homomorphic property of the commitment scheme, compute commitments

C_i⁰ =

e

Y

j=1

R⁰_j^mij,

to sharess_i, which determines the secret 0. Now, given the commit-mentCfor the secrets, we modify the commitments so they become consistent with s: Compute the public commitments R_i = R_i⁰C^κi where κ = (κ₁, . . . , κ_e)^T is the sweeping vector for A. Note that R1 =R₁⁰C^κ1 = 1C¹ =C as required, since hκ,εi= 1 (i.e., κ1 = 1).

The commitments to the shares inswill be as follows:

C_i=

e

Y

j=1

R^m_j ^ij =

e

Y

j=1

(R⁰_jC^κj)^mij =

e

Y

j=1

R⁰_j^mijC^κjmij.

For the parties inA we have that,

e

Y

j=1

C^κjmij =C

P

jκjmij =C⁰ = 1,

since the inner product ofκand a row inM that is owned by a party inA is 0. So for a corruptP_ψ(i) we haveC_i⁰ =Ci, and we know how to open these commitments. The simulated proof therefore consists of the commitments R1, . . . , Re, encryptions of correct opening in-formation for Ci when P_ψ(i) is corrupt, and encryptions of random values for honest parties.

• On input (Value, s) from F_VSS, where the value comes from an hon-est party, the simulator calculates an opening to commitment C = com_pk(0, r) from the input phase, such thatC=com_pk(s, r⁰), which can be done since S generated the commitment scheme and knows the factorization. The simulator calculates the openingoi for all,

Ci=

e

Y

j=1

R^m_j ^ij =

e

Y

j=1

(R⁰_jC^κj)^mij =

e

Y

j=1

R⁰_j^mijC^κjmij,

owned by an honest party by using the opening information fromC.

Finally, S broadcasts the opening o_i on behalf on the honest party P_ψ(i).

• On input (Value, s) fromF_VSS, where the value comes from a corrupt party, then just follow the opening protocol.

• If a corrupt party chooses to open her commitment, then send (Open, sid) to F_VSS on behalf of the corrupted party.

To see that this simulation works, note the following: First, the simulation of the initial set-up stage and of the case where a corrupt dealer gives a proof is perfect. In particular, when a corrupt dealer does a Share that would be accepted in the real protocol, the simulator can always extract the correct secret, and honest parties will therefore output accept also in the ideal process.

In the case where an honest dealer does aShare, this will in the ideal process simply mean that it sends integerstoF_VSS. The functionality will send accept to everyone, so all honest parties output accept. This is also the case in the real protocol: correct opening information for each C_i is uniquely determined

from the ciphertext c_i, hence no honest party will accuse D and every other accusation will be rejected by the honest parties.

When the honest parties open a shared value by a corrupt party, the sim-ulation is perfect. On the other hand, if the corrupted party opens the shared value s by himself, we need to argue, that he cannot open it another value s⁰ 6=s without being rejected. Let Pr denote the probability that A opens to s⁰ 6=s. If Pr is non-negligible, thenA can distinguish between the real and the ideal process, since in the real process she will open to s⁰, whereas in the ideal process the functionality F_VSS will ensure that it is opened to s. Let Adv⁰ de-note such an adversary, then the goal is to show that we can break the binding property of the commitment scheme. However, we cannot argue that the sys-tem Adv⁰, Z,F_VSS, S can break the binding property, since S has generated the commitment scheme and knows the factorization ofN, the modulo used in the commitment. Instead we make a system Adv⁰, Z, S⁰, where we have removed the functionalityF_VSS. The idea is, thatS⁰ receives a public key (N, g, h) of the commitment scheme generated by some oracle. The environment Z is wired with S⁰ instead ofF_VSS, i.e.,S⁰ will receives the values to be shared by honest parties. Hence,S⁰ can generate a view that is the same as the real process, and therefore Adv⁰ will still break the binding property with the same probability Pr. However, ifAdv⁰breaks the binding, thenS⁰ will have two distinct openings to the commitment and can feed them to the oracle, hence breaking the binding property of the commitment scheme.

When an honest party opens a shared value, or more precisely, when the simulator receives a (Value, s) message from theF_VSSfunctionality, the simulator uses the knowledge from the generation of the commitment scheme to make an opening to s. This leads to the final thing to argue, which is the distribution of commitments and encryptions.

Hence the only possible difference between the ideal and real process is in the simulated commitmentCand proofπ that is shown toA. By the statistical hiding property of the commitment scheme and privacy of the LISS scheme, it follows that the opening information sent to corrupt parties, as well as the commitmentsR₁, . . . , R_e have distribution statistically close to the one seen in the real protocol. So the only difference is the fact that the ciphertexts intended for honest parties are random in the simulation, and contain valid openings of commitments in the real protocol.

We cannot argue that the two sets of encryptions are indistinguishable based directly on the ideal process because S knows all secret keys. Instead, we con-struct a machineS⁰ that acts as an adversary breaking the underlying PKENO scheme. S⁰ will run the algorithms of Z, Adv and S, with the following mod-ifications to S: S⁰ receives public keys for the honest parties from an oracle.

Whenever S needs to decrypt a ciphertext sent to an honest party with tag t (see Section 5.2.3), S⁰ will ask the oracle for the secret key for that tag, and can then decrypt. When S wants to create ciphertext for honest parties in a simulated proof, S⁰ will ask the oracle to encrypt either 1) random data or 2) genuine opening information for the relevant commitments. The latter is possi-ble because S⁰ also runsZ and therefore knows each secret that is shared, this allows it to create the commitment C as a genuine commitment containing the

right value, and from this it can compute how to open all the other commit-ments in thatShare. In the case 1), we produce exactly what we get in the ideal process, in case 2) we produce something statistically close to what we get in the real process. Hence, if Z could distinguish the two processes, S⁰ can use the output fromZ to break the underlying IND-CCPA security in the PKENO scheme.

In document Linear Integer Secret Sharing (Sider 66-71)