What is the Knowledge Of Secret Key Assumption (KOSK)

From what I've read it seems to be where an entity must prove that they own the secret key. Which is done by signing a message M using said secret key.

Is this different than doing a Proof of knowledge for a secret key? Is this different than doing a zero knowledge proof for a secret key?

• I've never heard of a knowledge of secret key assumption, can you provide a reference to the paper where you read that? Jun 1 '19 at 10:10
• Page2 in this paper on general forking Lemma: cseweb.ucsd.edu/~mihir/papers/multisignatures-ccs.pdf Jun 1 '19 at 13:39

The security model makes the knowledge of secret key (KOSK) assumption. There is no dedicated key generation, but, when the adversary, mounting a rogue-key attack, provides a public key of its choice for a group member, it is required, in the model, to provide also a matching secret key. Of course “real” adversaries would not do any such thing, so what does this mean? It is explained by the authors as modeling the assumption that a user provides the certification authority (CA) with a proof of knowledge of its secret key before the CA certifies the corresponding public key.

What the above says is that the KOSK is not really an assumption in the cryptographic sense (like RSA, or discrete logarithm), but more like an hypothesis that is made about a specific security model. That is, KOSK is simply the hypothesis that when the adversary will mount an attack on the system, which is done by submitting some public key, he will also provide the matching secret key.

Now, let's explains why it matters here. Intuitively, there are situations in cryptography, such as this one, where we can prove that an attacker cannot break the security property of our scheme if he knows some specific piece of information, such as the secret key associated to the public key he submits. This might look strange at first, but it makes sense if you look at it the other way around: if the adversary is only allowed to submit public keys for which he knows the corresponding secret key, he is severely restricted in the type of attacks he can mount (e.g. he cannot provide a public key that he has stolen to some honest party, in an attempt to impersonate him).

Of course, there is a problem: in real life, no user will not provide the secret key together with the public key, that would completely break the system for them. The trick instead is to ask them to perform a zero-knowledge proof of knowledge (ZKPoK) of the secret key, which demonstrates that they know the secret key associated to the submitted public key, without leaking any further information.

Then, Bellare and Neuven go on with identifying the following problem: in real implementations of the protocol, this proof of knowledge is replaced by a signature, using the secret key as the signing key. Of course, intuitively being able to sign a document with the secret key shows that you know it. But it does not prove it, and that's all the issue. What does it mean to prove that an algorithm $$A$$ knows something? In cryptography, it means something very precise: it means that, given the code of $$A$$, it is possible to extract this value in polynomial time. This is possible by definition with a ZKPoK, but not with a signature. In the security analysis of the scheme, this extraction procedure is in general crucial: to show that the system is secure under some assumption, the security reduction will make use of the existence of an extractor that recovers this secret key, and use the extracted secret key in order to derive a contradiction to some security assumption from a successful adversary. If no such efficient extraction procedure exists, the security analysis breaks down.

Is this only a theoretical issue? This was probably the hope of the people who implemented the design. Arguably, it should be hard to mount an attack on a real-world system that uses signatures instead of ZKPoK, because a successful attack would require, at least, that the adversary somehow manages to find signatures on some documents without knowing the secret key. But can't he? Maybe the adversary can trick the real owner of the secret key into signing the document for him, mounting a man-in-the-middle attack. Or perhaps there is some more complex attack: I could easily design myself a (contrived) system which is provably secure using a ZKPoK, but which becomes completely insecure as soon as one replaces the ZKPoK bs a signature. The point is that without a security reduction, there is no way to be 100% sure that no such complete break exists.

A zero-knowledge proof for the secret key is a probabilistic challenge-response algorithm where the prover has probability 1 to get it right knowing the secret key, and some chance $$p < 1$$ if he does not know it. By repeatedly producing the right answer in a series of trials he can probablistically convince the opponent that he actually knows the key.

In signing by the secret key (say RSA 2048 bits) the prover has chance almost $$0$$ already to produce a correct result when not knowing the secret key. So the opponent can be probabilistically convinced by one try. No need for a zero-knowledge proof.

You do potentially leak more info on the secret key to the world in the second case.

• In the zk section, if the prover has probability 1 of getting it right, given that he has the key. Why does he need to repeat it? Jun 1 '19 at 13:40
• @WeCanBeFriends it could have been a coincidence. Jun 1 '19 at 14:05
• How can it be a coincidence, if the probability is equal to one? Or what is the probability that the prover gets it right on the first round, given that they do not have the secret key? Jun 1 '19 at 14:30
• @WeCanBeFriends in ZK typically a half. A coin toss. Jun 1 '19 at 14:37
• Ahh I see. Could you state how this relates to KOSK assumption? Jun 1 '19 at 15:56