Why not Z_q*?
Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Ex. 11-4 Lossy Encryption: choice of r from Z_q
tl;dr I am wondering whether the [m]Enc[/m] algorithm given in ex. 11-4 should actually choose [m]r[/m] from [m]Z_q*[/m] and not [m]Z_q[/m].
Namely, if [m]r = 0[/m] (the additive neutral element in Z_q) is chosen in [m]Enc[/m], then the ciphertext will be [m](1, 1)[/m] ([m]1[/m] is the neutral element in [m]QR_p[/m], the multiplicative subgroup of [m]Z_p*[/m]). Hence, any information about the message [m]m[/m] is lost.
I can see that I need multiplicative invertibility of [m]r[/m] in my proof of the correctness of the scheme, which was omitted from the official solutions.
Furthermore, in the official solution it is claimed that one could apply the supposedly distribution-preserving “substitution” [m]r’ = alpha * r[/m]. Note that [m]alpha ~ U(Z_p*)[/m]. (If [m]alpha = 0[/m], so would [m]g_1 = g_0^{alpha} = e[/m], which is not a generator.) Also note that [m]r ~ U(Z_p)[/m] by definition of [m]Enc[/m]. Now I doubt that [m]r’ ~ U(Z_p)[/m], which would allow that substitution. Namely, we have
Wrong (!) Lemma: Let p be an odd prime. Let [m]alpha ~ U(Z_p*)[/m] and [m]r ~ U(Z_p)[/m], then [m]alpha * r ~ U(Z_p)[/m].
If I am not mistaken, we have for a fixed [m]y in Z_p[/m]:
Pr[alpha x = y] = 0.25 Pr[alpha = y x^{-1} | y != 0, x != 0]
+ 0.25 Pr[alpha = y x^{-1}] | y = 0, x != 0]
+ 0.5 Pr[alpha x = y | x = 0]
= 0.25 1/(|Z_p*|) + 0 + 0.5 1/(|Z_p|)
= 0.25/(p-1) + 0.5/p
!= 1/|Z_p| // which would be required for alpha * r ~ U(Z_p)So let us assume we instead chose [m]r ~ U(Z_p*)[/m]. Then since [m]alpha ~ U(Z_p*)[/m], we can conclude by the lemma from the lecture that [m]alpha * r ~ U(Z_p*)[/m], hence the substitution is distribution-preserving.
As far as I can see, choosing [m]x_0, x_1[/m] uniformly at random st. [m]x_0 != x_1[/m] is still fine and unaffected by the remarks above.
OK, I agree with you.
Just to be 100% sure (I do not want to update that sheet more than once now):
Sampling [m]r[/m] from [m]Z_p^*[/m] in the ENC Algorithm should be enough to fix this?
EDIT:
Or shouldn’t sampling [m]r[/m] from [m]Z_p[/m] with the limitation of [m]r != 0[/m] also work?
Yes, sorry, I did say [m]Gen[/m] needed fixing as well in my first post, but that was wrong. (Now corrected in the first post.)
Since [m]p[/m] is prime, we have [m]Z_p* = Z_p{0}[/m] – read as an equation over sets. Hence, it’s equivalent. (From a personal perspective, I find writing [m]Z_p*[/m] nicer since its semantics are more immediate - we want invertibility.)
1 „Gefällt mir“
Oh yeah I overlooked that, I’ll gonna fix that today and reupload hw11_ and hw11_solution.
Thanks for your help here!