Not logged in. · Lost password · Register #faui2k15, GTI-Tutor a. D. Member since Nov 2015 521 posts 2020-02-03, 14:10   #1   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' = 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. Member since Oct 2014 125 posts 2020-02-06, 10:08   #2   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. #faui2k15, GTI-Tutor a. D. Member since Nov 2015 521 posts 2020-02-06, 16:59   #3   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: Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys:
Special characters:
Go to forum
Datenschutz | Kontakt