Member since Nov 2015
457 posts

20200203, 15:10 #1
Subject: Ex. 124: (g < 𝔾) should be (g < generator of 𝔾)
In the Gen' algorithm in ex. 124 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. 124b) 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. 
Member since Oct 2014
113 posts

20200206, 11:08 #2
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
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* = (mxr), sign(m*) = (2r, sign_{pi}(g^{mxr+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 CookieClicker
This post was edited 3 times, last on 20200206, 11:41 by tyr.

Member since Nov 2015
457 posts

20200206, 17:59 #3
I second you in both points. 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 nonnegligible wrt. lambda without further assumptions on q. I haven't yet looked at the official solutions, so I can't comment on that 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! 
Datenschutz 
Kontakt
Powered by the Unclassified NewsBoard software, 20150713dev,
© 20032011 by Yves Goergen