Join Log in
Score:1
MM45 avatar Crypto

Can a PKE scheme be turned into a signature scheme?

dj flag
MM45

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.

78
0 + 0
fgrieu avatar
ng flag
fgrieu
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).
0
Reply
ckamath avatar
ag flag
ckamath
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](https://www.cs.princeton.edu/courses/archive/spring08/cos598D/Rompel.pdf)). 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?).
1
Reply
MM45 avatar
dj flag
MM45
@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!
0
Reply
MM45 avatar
dj flag
MM45
@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?
0
Reply
ckamath avatar
ag flag
ckamath
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.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.