1
$\begingroup$

Recently, I have been wondering whether you can turn any PKE scheme into a signature scheme and, if so, how (is there a general construction, or is this scheme-specific?). I have found several posts that seem to suggest this is the case (e.g., this post, and this post); however, they don't really elaborate on how.

For some context:
I started wondering this (for some reason) when looking into Saber's PKE scheme. More precisely, I thought of the following. Suppose you keep the public key secret and publish the private key (so, the opposite of what you would normally do in the PKE scheme), could you then use the encryption algorithm to sign a message (i.e., what would normally be the ciphertext is now the signature) and verify the resulting 'signature' using the decryption algorithm (i.e., verification would be successful iff $m' = m$, where $m'$ results from the decryption and $m$ is the original message)? In the specific case of Saber's PKE scheme, this verification would then only succeed with probability $1-\delta$, corresponding to the correctness of the PKE scheme. Naturally, this is an extremely informal observation/intuition and probably does not work; nevertheless, I can't really find much information on this subject to move forward from (nor does my own reasoning bring me much further).

I hope someone could help me out by elaborating on some of this. My apologies if the post does not properly conform to all guidelines, this is my first time posting here. If anything is wrong with the post, let me know and I will change it.

Improve this question
$\endgroup$
5
  • $\begingroup$ We can make a signature scheme from a One Way function. Thus the question as asked in the title and first paragraph is moot. I think you want to ask if from a PKE scheme we can generically construct a signature scheme having the same key generation procedure (save perhaps for a swap of the keys), which is what the rest of the question seems to be about. AFAIK we have neither a theoretical construction nor a proof of impossibility, and all the examples we know that alow this do not need to swap public and private key (though some, like RSA with random public exponent, can do such swap). $\endgroup$
    – fgrieu ♦
    Sep 19, 2021 at 19:18
  • 1
    $\begingroup$ To add to the comment above, this is possible in theory: PKEs trivially imply one-way functions (e.g., just consider the key-generation algorithm of the PKE) which, in turn, imply signatures (this is a non-trivial result of Rompel). IBEs are known to imply signatures in the cleaner way @fgrieu alludes to: simply take its master key-generation algorithm (this observation is credited to Naor?). $\endgroup$
    – ckamath
    Sep 20, 2021 at 5:37
  • $\begingroup$ @fgrieu I was interested in both whether there exists such a general construction to create a signature scheme from a PKE scheme and, moreover, whether the observation I made holds any merit or comes close to something that could be done. Sorry if this was a bit unclear. Thanks for the provided insight, it's much appreciated! $\endgroup$
    – MM45
    Sep 20, 2021 at 12:48
  • $\begingroup$ @Occams_Trimmer I see, thanks for the additional comment. However, I am a bit confused by this. So, if I understand you correctly, a PKE scheme implies a one-way function; moreover, it does so through its key generation algorithm. By this, do you mean that the key generation algorithm is considered a one-way function? (This seems odd, since it takes no inputs, right?) Or do you mean that it is trivial to create a one-way function from the key generation algorithm? Or am I completely missing the point here? $\endgroup$
    – MM45
    Sep 20, 2021 at 13:01
  • $\begingroup$ The key generation algorithm is randomised. Now consider the OWF defined as the map that takes the key generation algorithm and simply outputs the public key. Why is this one way? Given any adversary that inverts it, one can re-run the key generation algorithm using the output to learn the secret key, which totally breaks the PKE. $\endgroup$
    – ckamath
    Sep 20, 2021 at 15:11

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.