# May an adversary be fooled by a random-looking input that in reality is fixed?

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"?
• "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... Commented Sep 8, 2020 at 19:39
• 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. Commented Sep 8, 2020 at 19:49
• @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?" Commented Sep 8, 2020 at 19:55
• 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. Commented Sep 8, 2020 at 20:05
• 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. Commented Sep 9, 2020 at 16:20

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$$.
• 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). Commented Sep 9, 2020 at 16:56
• 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$. Commented Sep 9, 2020 at 17:03