R2n, for anyn≥2, andAan attacker that can solve DDH. Then:
AdvF1≤AdvA
.
We will not provide the proves of these theorems here, but a sketch can be found in the paper by Furukawa and Sako for the interested reader [13].
5.2 Protocol I
We will in this section first construct Protocol I, and then look at the security of the pro-tocol. Sequences(gi)and(gi0)are made public, and a sequence(ri)andAij is given as private input toP. The protocol proves that both (5.1) and (5.3) hold.
Construction
Apparently, this will leak information aboutAij. To prevent this, randomizersψ,(ψi), andσare added, and (5.5) and (5.6) are modified.
First, we add randomizersψand(ψi).Psendsα= (g0,(Fi), H)as commitments in
Further, we add randomizerσand (5.6) is modified to be:
This verification is computed over exponents in order the hide the values of(Fj+σrj), (H+σψ)andσ. This gives us the two verification equations:
gs0
The protocol is three move, illustrated in Figure 5.1. The output of the protocol is(α, β, γ), whereα = (w, g0,( ˆwi),w),ˆ β = (βi)andγ = (s0,(si)). The prover computesg0. We enumerate the following equation for convenience:
g0=gψ
Theorem 20. Protocol I is complete.
Completeness of the protocol can be proved with simple calculations.
Theorem 21. IfVaccepts Protocol I with non-negligible probability, thenP∗either knows both(ri)andAij that satisfy (5.1), or can generate non-trivial integers(ai)and a satis-fyinggaQn
i=1giai = 1with overwhelming probability.
Proof. First, we prove that ifVaccepts with non-negligible probability, thenP∗knows ri, Aij, ψand(ψi)that satisfy (5.3) and (5.9). Recall that (5.3) gives thatgi0=griQn
j=1gAjji. This can be proved with rewinding. The technique is described in detail in proof of Theorem 8. First, we start running the protocol andP∗outputsα= (w, g0,( ˆwi),w).ˆ Pis given challenge(βi,1), and outputsγ1= (s0,1, si,1). This gives us one accepted transcript (α, βi,1, γ1).
We perform rewindingntimes. Each time is P∗ is given challenge(βi,b),(βi,1) 6=
(βi,b), andP∗outputs the corresponding outputγb= (s0,b,(si,b))(b= 2, ..., n+ 1),
5.2 Protocol I
Public input:p,q,g, n,(gi),(g0i) (i= 1, ..., n) Private input toP:(ri),Aij(i, j= 1, ..., n)
Prover,P Verifier,V
ψ, ψi, σ←r Zq,(i= 1, ..., n) Compute:
w←gσ g0 ←gψQn
j=1gjψj ˆ
wi ←gPnj=12ψjAji+σri(i= 1, ..., n) ˆ
w←gPnj=1ψ2j+σψ
w,g0,( ˆwi)ni=1,wˆ
−−−−−−−−−−−−−→
βi←r Zq,(i= 1, ..., n)
(βi)ni=1
←−−−−−−−−
Compute: s0←Pn
j=1rjβj+ψmodq si←Pn
j=1Aijβj+ψimodq,(i= 1, ..., n)
s0,(si)ni=1
−−−−−−−−−−→
Verify if
(5.7)and(5.8)hold Figure 5.1:Protocol I.
(i= 1, ..., n). This gives us a total of(n+ 1)accepted transcripts: gives us the following system of equations:
The matrix to the left will be invertible except with negligible probability, when(βi)is chosen at random fromZq. Hence(r1, r2, ..., rn, ψ)can be extracted.
Further, we extract(Aij)by making use of the fact thatsi,b =Pn
j=1Aijβj,b+ψi. This gives us the following system of equations:
The matrix to the left will be invertible except with negligible probability, hence(Aij)and (ψi)can be extracted. IfVaccepts, the same(ri),Aij,ψand(ψi)are used to calculate g0 and(gi0)by (5.3) and (5.9) respectively. This provesP∗‘s knowledge of(ri),Aij,ψ and(ψi)such that (5.3) and (5.9) are satisfied. Next, we will prove that this knowledge implies that either (5.1) is satisfied, orP∗is able to find a non-trivial representation of1
5.2 Protocol I with overwhelming probability.
First, we look at (5.7), the first verification equation. Assume thatP∗knows(ri), Aij, ψ and(ψi)satisfying (5.3) and (5.9), and(ai)andasatisfying (5.7). We note that the fol-lowing gives a non-trivial representation of1:
gs0−Pnj=1rjβj+ψ non-trivial representation of1with overwhelming probability if (5.7) is satisfied.
Next, we look at (5.8) that is the other equation verified byV. Assume thatP∗knows (ri), Aij, ψ and(ψi)satisfying (5.3) and (5.9). If (5.8) is satisfied, then the following
It is clear that if (5.1) does not hold, the probability that (5.8) holds is negligible. This gives us that ifVaccepts either (5.1) holds, orP∗is able to find a non-trivial representation of 1. This completes our proof.
Remark that since (g1, ..., gn) originally are chosen by those who encrypt the messages, we cannot assure that the prover does not know the relation among(gi). Hence, we can not assure thatP∗is not able to construct(ai)andaand such thatgaQn
i=1gaii = 1. We
note that the protocol does not satisfy the ordinary soundness property.
Theorem 22. LetBbe an attacker that can distinguish if an accepted transcript(α, β, γ) was constructed by (P,V) in Protocol I or by a simulatorSfor Protocol I. We then have an attackerAagainst DDH such thatAdvB≤AvdA.
Proof. The proof is constructed as follows:
1. Construct a simulatorSfor Protocol I.
2. Construct an attackerF1that can distinguish between uniform instances fromEn+12 andR2n+1.
3. Describe how the attacker can act as a simulatorS0.
4. Prove thatS0perfectly simulates (P,V) whenI∈En+12 and thatS0perfectly simu-latesSwhenI∈R2n+1.
Construction of S: A simulatorSfor Protocol I is constructed in Figure 5.2. The simulator outputs (w,g0,( ˆwi),w,ˆ (βi),s0,(si)).
Input:p,q,g, n,(gi),(g0i) (i= 1, ..., n) Simulator,S s0, si, βi
←r Zq,(i= 1, ..., n) w,wˆi←r Gq,(i= 1, ..., n) Compute:
g0 ←gs0Qn
j=1gjsjg0j−βj ˆ
w←ws0gPnj=1(s2j−βj2)Qn j=1wˆ−βj j Figure 5.2:Construction of a simulator for Protocol I.
Construction of F1: We will construct an attacker F1 that can distinguish uniform in-stances fromEn+12 andR2n+1ifScannot simulate Protocol I. AssumeI= (x(1)1 , x(2)1 , ..., x(1)n+1, x(2)n+1), was chosen uniformly from eitherEn+12 orR2n+1.
We letg = x(1)1 . First, F1 generates (gi)as the constants used in Proof 1, and a permutation matrixAij. He computes(i= 1, ..., n):
g0i=x(1)i+1
n
Y
j=1
gjAji
5.2 Protocol I The attacker will now act as a simulatorS0, based on the values and the permutation matrix he has obtained.S0is constructed in Figure 5.3.
Input:p,q,g, n,(gi),(g0i) (i= 1, ..., n) Simulator,S0
s0, si, βi
←r Zq,(i= 1, ..., n) w←x(2)1
Compute:
g0←gs0Qn
j=1gsjjgj0−βj ψj←sj−Pn
k=1Ajkβk modq,(j= 1, ..., n) ˆ
wi←x(2)i+1Qn
j=1g2ψjAji,(i= 1, ..., n) ˆ
w←ws0gPnj=1(s2j−β2j)Qn j=1wˆ−βj j Figure 5.3:Construction of simulatorS0.
S0 outputs an accepted transcript (w,g0,( ˆwi),w,ˆ (βi),s0,(si)). We will now prove thatS0perfectly simulates (P,V) whenI ∈En+12 and thatS0 perfectly simulatesSwhen I∈R2n+1.
S0 perfectly simulates(P,V)whenI ∈ En+12 : We assumeI ∈ En+12 . S0 perfectly sim-ulates (P,V) if transcripts constructed byS0and (P,V) have the same distribution. The proof is similar to the proof of Theorem 4, but we will outline the main differences.
In protocol IPchoosesσ←r Zq. We now let:σ=logx(1) 1
x(2)1 . Remark that this will tamper the protocol, becauseσwill still be a random value. Pis given private input(ri) defined as follows:ri=logx(1)
1
x(1)i+1.
This gives us that(P,V)choosesψ,(ψi)and(βi)at random fromZq, andS0chooses s0,(si)and(βi)at random fromZq. It is clear thatS0 perfectly simulates (P,V) when I∈En+12 .
S0perfectly simulatesSwhenI∈R2n+1: We assumeI∈R2n+1. In this case(x(2)1 , ..., x(2)n+1) is chosen at random fromGq byS0. This gives us Table 5.1. It is clear that transcripts constructed bySandS0 gives the same distribution, henceS0 perfectly simulateSwhen I∈R2n+1.
Figure 5.4 illustrates what we have proven so far. Transitivity gives us that if we have an attacker Bthat is able to distinguish transcripts from (P,V) andS, then we have an attacker F1 that is able do distinguish uniform instances from E2n+1 andR2n+1. From Theorem 19 we know that if it is easy forF1to distinguish these instances, then it is easy
S S0 s0, si, βi
←r Zq(i= 1, ..., n) s0, si, βi
←r Zq,(i= 1, ..., n) w,wˆi
←r Gq(i= 1, ..., n) x(2)i ←r Gq(i= 1, ..., n+ 1)
Table 5.1:Outline of the randomness in transcripts constructed bySandS0.
forAto solve the DDH problem. Hence, if it is easy forBto distinguish the transcripts, it is easy forAto solve DDH. This completes the proof of the theorem.
(P,V) S0
I∈En+12
I∈En+12 I∈R2n+1 I∈R2n+1
S0 S
Transcript ≈ Transcript Transcript Transcript DDH
≈ ≈
Figure 5.4:An illustration of how the proof is constructed.
We note that as long as it is difficult to solve DDH,Bwill not be able to distinguish if an accepted transcript (α, β, γ) was constructed by (P,V) or byS. The protocol is computationally HVZK.