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. 12-4: (g ← ???) should be (g ← generator of ???)
In the Gen’ algorithm in ex. 12-4 [m]g[/m] is chosen uniformly at random from ???, where ??? is a group of prime order. However, in the case that [m]g=e[/m] gets chosen, signing does not respect the message [m]m’[/m] anymore and simply outputs [m]sigma’ = <Sig_{sk}(g^{rx}, r>[/m] for r being uniformly chosen at random from [m]Z_q[/m]. However, in that case we have [m]Verfy’_{pk’}(m’, sigma’)[/m] for every [m]m’[/m]. Hence, in that case arbitrary messages can be signed (by the same signature even).
So I think it should be [m]g ← generator of ???[/m] or equivalently [m]g ← ???{e}[/m] since ??? is of prime order.
I am interested in whether having [m]g ← ???[/m] makes the proof of security in ex. 12-4-b) fail actually. How is [m]q[/m], the order of ???, related to [m]lambda[/m]?
Say [m]q = 2^lambda[/m], then my remarks above do not matter since choosing [m]g = e[/m] happens with negligible probability anyway.
[quote=Marcel[Inf]:1580739018]
So I think it should be [m]g ← generator of ???[/m] or equivalently [m]g ← ???{e}[/m] since ??? is of prime order.
[/quote]
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/hw3.pdf
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 [m] sign(m) = (r, sign_{pi}(g^m * g^{xr}) ) = (r, sign_{pi}(g^{m+xr} )) [/m] 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 …
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 non-negligible 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 
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!