I want to prove the EUF-CMA-security of a signature scheme. It is a variation on an established scheme, therefore I would ideally like to reduce the new-scheme-security to the old-scheme-security.

the (very abstract) construction

Let the old scheme be called S and let k denote a number. In S, k is fixed, say k=5. Imagine the new scheme N is identical, only with k becoming random and secret (because it is now related to the key material). So, k=5 is in theory still possible but may just as well be 1,2,3, .. and k=5 is just as likely as k = any other number.

One needs to know k to verify the signature, and k acts similar to a symmetric key. The setting is a group where you want to identify an individual sender but still share symmetric keys.

the reduction attempt

An adversary may query oracles for different values of k and the challenger can simply draw them randomly. However, in the challenge setting, it may obviously not know k, which is secret. Now, it would be easy to reduce the security of one scheme to the other if the adversary were to be tricked into outputting a signature for k=5. Then the security of N can be reduced to the security of S.

The adversary can not tell from the key material or the signatures or the verification equation that k=5 (because everything still appears random), except if it can break the DLog assumption.

So the questions are:

  1. An adversary can easily check whether k=5 or k!=5 in the challenge setting by attempting to verify a signature using k=5. Would an adversary realize that it is not interacting with the scheme but with a "simulation" if it finds out that k=5 in the challenge setting? (In which case, as far as I understand, it would not output a signature but break off the game.) Or is 5 a good a number as any, from the perspective of the adversary?
  2. I can not play the game differently for different adversaries, depending on whether they compute k or not, because I know nothing about how A works - correct? (See Katz, Lindell, Introduction to Modern Cryptography, pg.59) Or could I play differently for "DLog-Breakers" and "DLog-Ignorants"?
  • $\begingroup$ "Imagine the new scheme N is identical, only with k becoming random and secret (because it is now related to the key material)." "One needs to know k to verify the signature"; if $k$ is effectively part of the private key, how can it be used during signature verification? For the security of signatures, we assume that the adversary knows everything the honest verifier does... $\endgroup$
    – poncho
    Commented Sep 8, 2020 at 19:39
  • $\begingroup$ They could be thinking this would be a system along the lines of HMAC. At least, that's what I think when I read this. $\endgroup$
    – Serpent27
    Commented Sep 8, 2020 at 19:49
  • $\begingroup$ @Serpent27: I suspect so as well; however, if they are talking about a MAC based on DLog, first off, they should say so, and second off, well, "why, given that there are far more efficient symmetric constructions?" $\endgroup$
    – poncho
    Commented Sep 8, 2020 at 19:55
  • $\begingroup$ I have no idea why.. But it sorta sounds like this is for a video game? or not? "would not output a signature but break off the game." A secure signature scheme doesn't need a game or a simulation so I can only assume they mean the kind you play for fun. $\endgroup$
    – Serpent27
    Commented Sep 8, 2020 at 20:05
  • $\begingroup$ Well, k is not part of the private key, because there are really two: an asymmetric key and a symmetric key. The symmetric key is k. The idea is: There is a group sharing a key k. All individual participants have an asymmetric key pair as well. The scheme aims to unite the group authentication with the individual authentication, so a group member will know how to verify the signature (namely, using k) and thereby verify two things: that the communication partner is who they say they are as an individuum and that they are part of the group. $\endgroup$
    – phi.nm
    Commented Sep 9, 2020 at 16:20

1 Answer 1


Would an adversary realize that it is not interacting with the scheme but with a "simulation" if it finds out that k=5 in the challenge setting?

This is commonly stated as Kerckhoff's Principal, which I prefer to cite as Shannon's Maxim (they both stated it, and Shannon's Maxim sounds better). The idea is, the adversary should be assumed to know everything about a secure system, except the key, if it is to be considered secure at all. As such, the adversary must be assumed to know that you could lie to them about the value of $k$.

Also, a signature scheme could not be considered secure if it involves an oracle capable of lying about what signatures are valid or invalid. As such, if the system is to be secure at all, it must behave the same for an attacker as if they were a legitimate verifier.

  • $\begingroup$ Thank you, I think I understand the second part and why my concept of proving the scheme secure against an outside attacker who is not even part of the group (please see my above comment) is not the way to go. And about Kerckhoff's Principle: I would not be lying, though. The value would really be k=5. Leaving aside the problem that this probably only proves that the system is secure for k=5, I was wondering whether the attacker would wise up to this being a simulation if it found out that k=5 in the challenge epoch, because it would be such a coincidence. $\endgroup$
    – phi.nm
    Commented Sep 9, 2020 at 16:32
  • $\begingroup$ In that case, while your system may be secure, only someone knowing $k$ could verify a signature. This would be equivalent to signing the message, the encrypting the signature under a normal scheme; or signing only an HMAC hash of the message. The unclear detail here is the challenger doesn't draw any oracles. The oracles simply verify (if $k$ is correct) whether a message is valid. For an incorrect $k$ it would always say the signature is invalid (barring collisions, of course). $\endgroup$
    – Serpent27
    Commented Sep 9, 2020 at 16:56
  • $\begingroup$ With all the lack of clarity with this question, your assumption is correct; that for an attacker knowing $k$ the scheme has the same security s the old scheme $S$; and for an attacker not knowing $k$ the scheme is at least as secure as $S$: it has more security than $S$ if the attacker has difficulty finding $k$, or the same security as $S$ if the attacker can reasonably find $k$. $\endgroup$
    – Serpent27
    Commented Sep 9, 2020 at 17:03
  • $\begingroup$ Although I might ask, why you're attempting to create signatures only certain people can verify... That kind of seems rather clique-y to me, but I guess you don't want the adversary proving you signed something? That could provide a certain level of plausible-deniability, I guess. $\endgroup$
    – Serpent27
    Commented Sep 9, 2020 at 17:04
  • $\begingroup$ It is supposed to be clique-y; not necessarily for security reasons, but because I'm trying to analyze whether that would be more efficient in some aspects. $\endgroup$
    – phi.nm
    Commented Sep 11, 2020 at 13:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.