5
$\begingroup$

I was considering using Microsoft's SIDH implementation for post-quantum public-key encryption because of its relatively small key size. I realized however, thanks to Issue #4, that it might not be as ideal as I had hoped:

SIKE is IND-CCA2 secure, which means that it's ok to reuse the key pair generated [...] whereas SIDH is insecure with re-used keys [...]

So here we go:

  1. Is SIDH actually insecure when keys are reused?

  2. Is SIKE actually secure even when keys are reused?

  3. If so, why? How can SIDH actually be broken? Can you demonstrate an attack?

  4. What prevents an attacker from encrypting many messages with a SIDH public key and breaking it that way?

  5. What's the difference between the two that makes it so one can securely use reused keypairs and one can't?

Improve this question
$\endgroup$
1
  • $\begingroup$ I'd guess the reuse includes the sender's key. So to turn it into reusable encryption you could simply use ephemeral sender keys. $\endgroup$
    – CodesInChaos
    Feb 1, 2018 at 20:37

1 Answer 1

Reset to default
8
$\begingroup$
  • Is SIDH actually insecure when keys are reused?
  • If so, why? How can SIDH actually be broken? Can you demonstrate an attack?

Yes it is. There is a well known adaptative attack, described here https://eprint.iacr.org/2016/859

Is SIKE actually secure even when keys are reused?

Yes it is. There is a security proof, assuming the number-theoretic hardness assumptions SIDH is based upon are true.

What prevents an attacker from encrypting many messages with a SIDH public key and breaking it that way?

That's the definition of CPA security. SIDH is proven CPA secure.

The CCA attack works by generating faulty ciphertexts (not plaintexts) and sending them to a decryption oracle. The attacker learns something on the key by observing whether decryption succeeds or not.

What's the difference between the two that makes it so one can securely use reused keypairs and one can't?

SIKE uses a generic transformation meant to turn a CPA secure protocol into a CCA secure one. Essentially, it amounts to recomputing Bob's public data to check that he did not cheat in computing the ciphertext. This thwarts the attack, and indeed also any other potential CCA attack.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Note that v3.0 of the MS library implements SIKE, and, for only a small running time penalty, you get exactly the same key sizes as SIDH. You may want to think twice before ditching good old elliptic curves for SIDH, though: we're still in the early stages of the PQ competition $\endgroup$
    – Luca De Feo
    Feb 2, 2018 at 0:39

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.

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