5
$\begingroup$

I've been researching how to implement a post-quantum SSL-like connection authentication, especially correct identification&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&suggestions,

-exa

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ I think you need to define your attack scenario a bit more precisely. In particular, can the attacker impersonate B to A? If so, they can carry out a straightforward MITM attack by just using the real B as an oracle. If not, why do you even need an authentication protocol? $\endgroup$
    – Ilmari Karonen
    Commented Mar 30, 2013 at 16:32

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ whats this about fractal trees and hash based signatures ? $\endgroup$
    – imichaelmiers
    Commented Mar 31, 2013 at 3:23
  • $\begingroup$ Huh. $\:$ I'm pretty sure there's a paper on that, but I can't find it. $\:$ The idea is building a tree of ordinary $\hspace{.2 in}$ trees and having the signatures be a branch with the choices at each node (of the ordinary trees) $\hspace{.4 in}$ given by the message's hash, and using a pseudo-random function for all of the randomness to $\hspace{.4 in}$ make the signing algorithm (deterministic and) stateless. $\;\;$ $\endgroup$
    – user991
    Commented Mar 31, 2013 at 4:29
  • $\begingroup$ Thanks, these two ideas seem to capture where I needed to get pushed :) Thanks for CCA1 mention, I already have CCA2-resistant scheme (Fujisaki-Okamoto padded McEliece) so I guess that would work. $\endgroup$
    – exa
    Commented Mar 31, 2013 at 12:39
  • $\begingroup$ And comments: FMTSeq and similar hashes have support for unlimited signature numbers, but that either brings key schedule problems or makes the signatures terribly big (2^256-ops secure FMTSeq has 10KiB for one signature, for around 1M signature limit...) $\endgroup$
    – exa
    Commented Mar 31, 2013 at 12:41
  • $\begingroup$ Merkle signature is mature and is postquantum ... $\endgroup$
    – juaninf
    Commented Dec 3, 2013 at 15:18

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.