Multiplication Proof

In this section we describe a protocol that non-interactively proves that a shared value is the product of two other shared values. For simplicity, we will only consider the case of a threshold adversary who corruptst < n/3 of the parties, so the adversary structure ∆ will in this section consist of all set of cardinality at most t. In Section 5.3.4 we describe a generalization to all Q3 adversary structures.

We will need a tool from [29], called Pseudorandom Zero Sharing (PRZS).

This protocol assumes that for all B∈∆⁺, parties not inB have been givent random seedsr¹_B, . . . , r_B^t and a primep > nis agreed in advance. Based on this, the protocol generates (by local computation only) a pseudorandom polynomial f over Zp of degree at most 2t such that f(0) = 0 and each party Pi knows f(i). The protocol is a simple generalization of the share conversion technique.

For eachB ∈T_t,n⁺ consider the following set,

F_B={f |deg(f)≤2t, f(0) = 0, j /∈B ⇒f(j) = 0}.

Let F denote the set of all polynomials of degree at most 2t. Consider F as a vector space, thenFB is a subspace of F of dimension t. For each B ∈T_t,n⁺ choose once and for allf_B¹, . . . , f_B^t to be a basis forFBand use it in the following protocol.

Protocol Pseudorandom Zero-Sharing (PRZS) It is assumed that Random_{r¹

B,...,r_B^t}(Tt,n) has been run, where t is the threshold. Furthermore, they all have a common valuea.

1. For = 1, . . . , n partyP_i lets

s_i = X

B∈T_t,n⁺ ,Pi∈B t

X

j=1

ϕ_rj B

(a)f_B^j(i)

Note 5.4. It follows from straight forward verification, that the shares from the above protocol are consistent with a polynomial f0 of degree at most 2t and f0(0) = 0.

We will choose a fixed primep, such p >2(4|∆⁺|+ 2)²2^2(l+k). Protocol MultProof_{rB,r¹

B,...,r^t_B}(a, b, c)

1. The dealer Dexecutes Random_{rB,r¹

B,...,r^t_B}(∆⁺).

2. D executesShare_{rB}(a), Share_{rB}(b) and Share_{rB}(c).

3. The parties use Proposition 5.2 to locally convert the RISS sharings we now have of a, b, c to Shamir sharings of amodp,bmodp and cmodp, consistent with polynomialsfa, f_b andfc of degree at most t, t and 2t respectively. The parties use PRZS to generate shares in a polynomialf of degree at most 2t withf(0) = 0.

4. D uses his knowledge of all seeds to compute the polynomial h = f +fafb−fcand broadcasts h.

5. Each partyP_iverifies thath(i) =f(i) +f_a(i)f_b(i)−f_c(i). If the veri-fication fails thenPibroadcast “Accusation” and opens all encrypted values r_B, r¹_B, .., r^t_B known by him.

6. The proof is rejected if one of the following situations happen: one of the Shareprotocols in Step 2 was rejected, the broadcasted poly-nomialhis not of degree at most 2t,h(0)6= 0, or broadcasted values by a party are consistent with the encrypted values but inconsistent with the broadcasted values byD.

Theorem 5.5. When based on a secure PKENO scheme and PRF, then the protocol MultProof_{r

B,r¹_B,...,r^t_B}(a, b, c) securely implementsF_ab=c, for any thres-hold-t adversary structure where t < n/3.

Proof. We construct a simulator S that works as follows:

1. S generates the keyspk,{(pk_B, sk_B)} followingT’s algorithm, and sends all public keys to A, along with secret keys for corrupted parties.

2. S now acts whenever required, as follows:

• When A does a proof on behalf of a corrupt dealer, S can simply decrypt everything sent by the adversary, and decide if the proof would be accepted in the real process. If so, it reconstructs values a, b and c and sends them to the ideal functionality. Otherwise, it sends ⊥ to the ideal functionality and uses the honest parties’

algorithm to compute the messages (complaints) they would send to corrupt parties, and sends these toA.

• When an honest dealer does a proof, S will generate a simulated proof by simply following the prover’s algorithm, usinga=b=c= 0.

• When A does an opening on behalf of a corrupted party, then just follow the protocol.

• When receiving (Value, c) and let B denote the set of corrupted parties, then generate the shares of the honest parties using v = ϕ_rB(a)−c instead of ϕ_rB(a) in the conversion to the Shamir poly-nomialfc. Otherwise follow the protocol and open the value.

To see that this simulation works as required, note first that the simulation of the set-up phase and proofs by corrupt dealers is perfect. This is because the simulator follows the honest parties algorithm to compute their reaction to the proof, so we just need to check that when the proof is accepted, the simulator can send a correct witness to the functionality. By Lemma 5.4, the values a, b, c that the simulator reconstructs from the proof will be in the interval [−(2|∆⁺|+ 2)2^l+k. . .(2|∆⁺|+ 2)2^l+k], so we know that |ab|,|c| are less than p/2. Now, from Step 5, we know that h agrees withf +faf_b−fc in all points owned by honest parties, of which there are at least 2t+ 1. This implies that h=f+fafb−fc, and therefore thatab=cmodp. However, ifab6=c, it would have to be the case that|ab−c| ≥p, while on the other hand we already know that|ab−c| ≤ |ab|+|c|< p. So indeedab=c.

It remains to show that the simulation of an honest dealer’s proof shown to the adversary is indistinguishable from a real proof. For this, consider the real processReal, and assume the worst case where the adversary has corrupted a maximal setB of parties. This means that when an honest dealer does a proof, the keyskB is the only secret key the adversary does not know. We then define a new “hybrid” processHyb₁, where we replace the broadcasted encryptions of r_B, r¹_B, . . . , r_B^t (under pk_B) by encryptions of independent random values. By an argument similar to the proof of Theorem 5.2,Realis indistinguishable from Hyb₁ if the underlying PKENO scheme is secure. Note that in Hyb₁, we can replace evaluations of the PRF using seeds r_B, r_B¹, . . . , r_B^t by oracle access to the PRF with the same seeds, and all messages sent will remain unchanged. We defineHyb₂ by replacing the PRF oracles by oracles for truly random functions.

By security of the PRF,Hyb₂ is indistinguishable fromHyb₁. Finally, we define Hyb3 as follows: we first replace the dealer’s inputs (a, b, c) to theShare{r_B} (·)-protocols by random values in the legal interval, and second, we choose the polynomialhto broadcast as a uniformly random polynomial, subject toh(0) = 0, deg(h) ≤ 2t, and that h(i) agrees with the adversary’s information for all corrupt parties P_i. Now, Hyb₃ is statistically indistinguishable from Hyb₂: consider, for instance, the execution of Share_{rB}(a) in Hyb₂. If we subtract the randomness that the adversary already knows, we see that he can compute R+a, whereRis a truly random value inIr = [−2^l+k..2^l+k]. This is statistically indistinguishable fromR+r wherer is a random value inI_s= [−2^l..2^l], which is what the adversary would see in Hyb3. The polynomial h is easily seen to have exactly the same distribution inHyb2 and Hyb3. It follows that Real is indistinguishable fromHyb₃.

Note, that in the argument we just gave, we did not use anything special about the inputs a, b, c, other than ab = c. Therefore, essentially the same argument shows that the ideal process is also indistinguishable fromHyb₃ since the simulator uses a = b = c = 0 and otherwise follows the protocol. The argument now follows from transitivity of indistinguishability.

When a value of a corrupted party is opened, then it happens exactly like in the real process, hence, the simulation is perfect.

Finally, we need to argue, that when opening honest shared values, the simulation is indistinguishable. First note, that for the corrupted set of parties B, the valuev=ϕ_rB(a)−cis in the same range asϕ_rB(a) with all but negligible probability. Using v instead of ϕrB(a) will in the conversion generate a set of Shamir shares for the valuec, since we now have,

r−v− X

A⊆P,|A|=t,A6=B

ϕrA(a) =c, see, e.g., Example 5.1.

Finally, we need to argue that the published polynomialh in step 4 in the MultProof protocol is consistent with the published shares off_c. We have that the adversary knows the polynomial fcand,

h(i) =f(i) +fa(i)f_b(i) +fc(i),

for all i ∈ B, where f is the polynomial from the PRZS protocol. In the following we will argue, that even if the adversary knowsf_a,f_b andf_c, thenf could be generated such that it is consistent withh.

Assume without loss of generality that|B|=t. Then note, that even before the f_c polynomial is opened, the adversary knowst points on all polynomials h, f, fa, fb and fc. That is, there are only t unknown points to the adversary on in thef polynomial.

The valuesr_B¹, . . . , r^t_B are unknown to the adversary, and F_B is given by, F_B ={f |deg(f)≤2t, f(0) = 0, j /∈B⇒f(j) = 0}.

That is,FB is a subspace ofF, the set of all polynomials of degree at most 2t, which spans the subspace of f which is unknown by the adversary. FB has basisf_B¹, . . . , f_B^t, and for any given set of tpoints{β_j |P_j ∈/ B}, there exists a linear combination α1, . . . , αt, such that f⁰ =f+Pt

i=1αif_Bⁱ has the following property, that f⁰(0) = 0, f⁰(i) =si for all Pi ∈ B, where si is the share of Pi, and f⁰(j) =β_j for tparties P_j ∈/ B.

By similar arguments as above, the ϕ_r¹

B(a), . . . , ϕ_r^t

B(a) values used in the PRZS protocol, can be exchanged to a random values. Hence, the polynomial f could be chosen to fit an arbitrary set of points, as described above. Hence, the indistinguishability follows.

5.3.4 RISS-based protocols for General Adversary Structures