1
$\begingroup$

I'm a newbie in studying and learning how SIDH works. I have a simple doubt. So my question is in the SIKE submission present in this link (https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Round-1-Submissions), once you download and unzip the SIKE folder, you get supporting documentation, a .pdf file. In that .pdf file, Section 5.1, 5.2 (Chapter 5), in Table 5.1, they mention that SIKE503 has a quantum security level of 64 bits and SIKE 751 has a quantum security level of 96, right? The doubt that I have is SIDH or SIKE is not a block cipher, isn't it? Can we still use Grover's algorithm to get it quantum security level ? or am I missing something here. Any explanation will be highly appreciated. Thank you so much for your patience! Looking forward to some help

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
5
$\begingroup$

Block cipher is a concept from symmetric cryptography. Here we're talking about public key cryptography. SIKE is a public key encryption (PKE), and a key encapsulation mechanism (KEM).

Of course Grover's algorithm applies to any public key cryptosystem, but there is not a single system where we don't know a better algorithm than Grover's. SIKE is no exception.

The quantum security of SIKE is (roughly) obtained by dividing the bit-size of the prime p by 6. For example SIKE503 has about 80 qubits of security, but NIST security categories come by large increments (64, 96, 128 qubits), the closest one being 64 qubits.

There is currently debate on whether the divide by 6 rule is too pessimistic.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Hello Sir, so this dividing by 6 comes from your paper "TOWARDS QUANTUM-RESISTANT CRYPTOSYSTEMS FROM SUPERSINGULAR ELLIPTIC CURVE ISOGENIES" right? where the complexity is O(p^{1/6}) ? I would ask for another small clarification, I understand SIDH consists of a lot of computations, but the basic ideology is a Diffie-Hellman Key exchange. In normal ECDH, can we apply Grover's algorithm and say that ECDH using 256 bits prime is 64 bits quantum security? or with 384 bits prime has 96 bits of quantum security? $\endgroup$
    – ChanBan
    Apr 12, 2018 at 22:54
  • 1
    $\begingroup$ For normal ECDH, or any other system based on discrete logarithms, you would apply Shor's algorithm, not Grover's. Shor's algorithm takes polynomial time: ECDH has essentially ZERO quantum security. $\endgroup$
    – Luca De Feo
    Apr 13, 2018 at 18:55
  • $\begingroup$ I see. Actually in this paper I see (arxiv.org/pdf/1706.06752.pdf) that 256 bits modulus in ECDLP, corresponds to 2330 qubits (Table 2, Section 5). I suppose that is for 128 bits classical security right? And now using SIKE its mentioned corresponding to 128 bits of classical security, we have 80 qubits(or better said 64 bits ) quantum security level. I'm little confused how come that for post quantum cryptoscheme its 80 qubits and for ECDLP its 2330 qubits? Is it because when we mention as number of bit security levels then 2330 changes to log(2330)/log(2) that is 11 bits? $\endgroup$
    – ChanBan
    Apr 13, 2018 at 20:29
  • 1
    $\begingroup$ Yes, you got it mostly right: n qubits of security means that you need to evaluate 2^n elementary quantum gates to break the system. The paper you cite is saying something completely different: it is saying that to break ECDH you would need a quantum computer with 2330 qubits of storage (and something like 10^11 quantum gate evaluations). $\endgroup$
    – Luca De Feo
    Apr 14, 2018 at 22:15

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.