Not logged in. · Lost password · Register

Marcel[Inf]
#faui2k15, GTI-Tutor a. D.
Member since Nov 2015
485 posts
Subject: Ex. 12-4: (g <- 𝔾) should be (g <- generator of 𝔾)
In the Gen' algorithm in ex. 12-4 g is chosen uniformly at random from 𝔾, where 𝔾  is a group of prime order. However, in the case that g=e gets chosen, signing does not respect the message m' anymore and simply outputs sigma' = <Sig_{sk}(g^{rx}, r> for r being uniformly chosen at random from Z_q. However, in that case we have Verfy'_{pk'}(m', sigma') for every m'. Hence, in that case arbitrary messages can be signed (by the same signature even).

So I think it should be g <- generator of 𝔾 or equivalently g <- 𝔾\{e} since 𝔾 is of prime order.

I am interested in whether having g <- 𝔾 makes the proof of security in ex. 12-4-b) fail actually. How is q, the order of 𝔾, related to lambda?

Say q = 2^lambda, then my remarks above do not matter since choosing g = e happens with negligible probability anyway.
tyr
Avatar
Member since Oct 2014
120 posts
Quote by Marcel[Inf:
:1580739018]
So I think it should be g <- generator of 𝔾 or equivalently g <- 𝔾\{e} since 𝔾 is of prime order.

After discussing that, we came to the same conclusion as you, g cannot be 1. I believe that this exercise is from a pool of interesting crypto challenges that is used by multiple lectures out there. See for example 5b) at https://crypto.stanford.edu/~dabo/courses/cs255_winter07/h…
We think that most of the authors of such tasks just brush over this issue, since every g in G is a generator (except the identity) => they see it as obvious and therefore do not state that explicitly

I am interested in whether having g <- 𝔾 makes the proof of security in ex. 12-4-b) fail actually. How is q, the order of 𝔾, related to lambda?

Say q = 2^lambda, then my remarks above do not matter since choosing g = e happens with negligible probability anyway.

Counter question: I think right now that in the proof, if an adversary against \Pi' hopes to get g = 1, the probability of that would be 1/q. Shouldn't guessing x from Z_q have basically the same prob? (I edited that part a lot, sorry)

EDIT: Why would guessing x break \pi'?This lead to the Collision event Coll from the proof. Example: query for m, get sign(m) = (r,  sign_{pi}(g^m * g^{xr}) ) = (r, sign_{pi}(g^{m+xr} )) and then use your knowlegde to calculate the forgery m* = (m-xr), sign(m*) = (2r, sign_{pi}(g^{m-xr+x2r}) = (2r, sign_{pi}(g^{m+xr})  = sign(m)

To be honest I am not 100% sure about this, so please tell me whether this helped you :)


I think that stating any relation between lambda and q is not the general approach here, one basically tries be vague in stating "let G be a group of prime order q where discrete logarithm is hard". That is not satisfying, I know ...
"Debugging is like doing surgery by randomly squeezing stuff in a patient's body and going like 'lmao tell me when this guy stops breathing'." -- Orteil, Creator of Cookie-Clicker
This post was edited 3 times, last on 2020-02-06, 10:41 by tyr.
Marcel[Inf]
#faui2k15, GTI-Tutor a. D.
Member since Nov 2015
485 posts
Quote by tyr:
Counter question: I think right now that in the proof, if an adversary against \Pi' hopes to get g = 1, the probability of that would be 1/q. Shouldn't guessing x from Z_q have basically the same prob? (I edited that part a lot, sorry)
I second you in both points.

Quote by tyr:
I think that stating any relation between lambda and q is not the general approach here, one basically tries be vague in stating "let G be a group of prime order q where discrete logarithm is hard". That is not satisfying, I know ...
Ah, that I approach I didn't know. But given that approach, we definitely must *not* allow g = 1 since 1/q could very well be non-negligible wrt. lambda without further assumptions on q.



Quote by tyr:
EDIT: Why would guessing x break \pi'?This lead to the Collision event Coll from the proof. Example: query for m, get sign(m) = (r,  sign_{pi}(g^m * g^{xr}) ) = (r, sign_{pi}(g^{m+xr} )) and then use your knowlegde to calculate the forgery m* = (m-xr), sign(m*) = (2r, sign_{pi}(g^{m-xr+x2r}) = (2r, sign_{pi}(g^{m+xr})  = sign(m)
I haven't yet looked at the official solutions, so I can't comment on that :)

Quote by tyr:
To be honest I am not 100% sure about this, so please tell me whether this helped you :)
It did, in particular that part with what q is supposed to be.

Sometimes I dream of all this being fully formalized (say in Coq) such that I could track dependencies myself in proofs :P Then again, I think the kind of probability juggling we do in ModCrypt is indeed a challenge to formalize. (But then again, advance mathematics has probably much more such juggling.)

Happy semester break!
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen