Using encryption schemes for identification I've been researching how to implement a post-quantum SSL-like connection authentication, especially correct identification&amp;authentization of the server/client. Because good post-quantum digital signature algorithms are generally unavailable (McEliece-based CFS is slow, NTRUsign is impractical, MQ schemes are generally broken and hash-based schemes have limited number of signatures which doesn't go very well with automated on-demand signing), I've been trying to find a good scheme that would not produce signatures, but would just verify whether there really is the holder of the given private key on the other side of connection.

There are several approaches to such identification (Stern's scheme etc.), but because we already have good post-quantum encryption schemes, I've been wondering whether one could use them like in following scheme:


A has some kind of data connection to B. A wants to know if B is really the guy identified by public key PubB, therefore A wants to determine whether B can do operations that depend on key PrivB. (PubB and PrivB is the keypair of some asymmetric encryption scheme)
A generates a random string S, encrypts it with PubB, and sends it to B.
B decrypts the message to S', and sends it back to A
A compares received S' with S, if they are equal, B was able to use PrivB and therefore it is (cryptographically) indeed B.


Questions:


Is there any good reason why this would not work? (consider the connection somehow secured against MITM-like disruption, as this is not the purpose of the question and the solution is relatively simple)
Is there any problem with sending decrypted plaintext S' back? Especially for fighting the fact that in this case B would simply act as a decryption oracle for PrivB for anyone connected, would it help if B was sending back only H(S'), where H is some cryptographic one-way (possibly hash) function?


Thanks for any thoughts&amp;suggestions,

-exa
Well, that would work, but identification is not enough for SSL.

You would need to make the PKE scheme one-way against CCA1 attacks. $\:$ (On the

other hand, it wouldn't need any semantic security.) $\:$ Sending back H(S') would change

the required security notion to one that's even farther from what's been studied.

You could use a tag-based PKE scheme that is one-way against tag respecting CCA2 adversaries to allow the private key holder to also authenticate data to the verifier, which would be enough for SSL. $\:$ (Although it would take 2 messages from the server and 1 from the client, rather than just 1 each.) $\:$ Also, hash-based signature schemes using fractal trees don't necessarily have a limited number of signatures.