1
$\begingroup$

I have been looking into error-correcting codes in lattice, I am specifically hoping to find some information on hardware implementations for the NIST PQ PKE/KEM finalists (Saber, CRYSTALS-Kyber, NTRU).

I was reading this article on Timing Attacks on Error Correcting Codes in Post-Quantum Schemes and it mentions:

Kyber [31] and Saber [11] choose their parameters so that their failure probability is small enough without need for ECC. NTRU [36] and NTRU prime [6] even eliminate all decryption failures without using any ECC. These schemes are therefore not vulnerable to side-channel analysis on ECC and do not need the extra protection against these types of attacks.

I also understand the Lattice codes are also referred to as "Sphere packing". Something I have read about conceptually, although I am not sure how it works practically.

However, I have also seen a few articles (such a this) that have been published recently about RLWE (Ring-Learning with Error) that tackle error correction and fault detection in that space, however none of the finalists use RLWE (as far as I can tell?)

My question is somewhat broad: I want to investigate ECC/fault detection in hardware (or more accurately their lattice counterparts), specifically with one of the NIST finalists. Does anyone have any insights into this sector of Lattice Cryptography? I am very new to this field (I'm a student, looking to define a thesis topic) but any insights would be appreciated.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

I want to investigate ECC/fault detection in hardware (or more accurately their lattice counterparts), specifically with one of the NIST finalists. Does anyone have any insights into this sector of Lattice Cryptography?

Actually, none on the NIST Lattice finalists (Kyber, NTRU, Saber) use error correction; for that matter, neither do the NIST Lattice alternates (Frodo, NTRUPrime). Hence, that wouldn't be a promising avenue to research. Several round 2 candidates (LAC, Round5, probably others) did, however they didn't make the cut.

As for fault detection, well, that's always a possible concern. Glancing through the paper you cited, it would appear that they are concerned mostly about deterministic faults (e.g. a gate within the hardware breaks), and less about deliberate fault attacks (e.g. the attacker glitches the power supply at just the right time to cause a single value to be miscomputed). You might consider investigating that (possibly starting with figuring out how out would perform a fault attack on the reference implementation, and using that to form a generalized concept about how a fault attack would work; then, you form a defense against that (assuming some limit on how powerful the attacker is; obviously, if he can fault things arbitrarily, he can make the hardware do anything...)

however none of the finalists use RLWE (as far as I can tell?)

No, but as ideal lattices, they aren't that different; of course, as a part of your thesis, you would need to explore them in detail...

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you for your response, most of this makes sense to me. However, I am confused as to why error-correction would not be used? If an attacker is able to change some value to be miscomputed, would we not want a way of controlling this error? Or do we just rely on a fault detection and re-submission of data? $\endgroup$
    – Daftyler
    Commented Apr 20, 2021 at 18:48
  • 2
    $\begingroup$ @Daftyler: error correction in lattice systems is there to address a different problem; most lattice systems have a small probability of failure; that is, the decrypted value doesn't exactly match the value that was encrypted (even if an adversary didn't tweak something in the middle). This error is likely to affect a small number of bits, hence some systems put in error correction after the lattice computations in an attempt to reduce this probability; however (as noted) none of the finalists or alternates make this design decision $\endgroup$
    – poncho
    Commented Apr 20, 2021 at 19:07
  • 2
    $\begingroup$ @Daftyler: if we are concerned about attackers sending us tweaked (or carefully crafted) encrypted packets (called the CCA scenario), we use a different defense; most commonly the Fujisaki-Okamoto transform (where the decryptor, after decryption, attempts to recreate the ciphertext based on the decrypted plaintext message and seed, and if he didn't recreate it exactly, he rejects the ciphertext as invalid. All lattice candidates have some defense against this (although the details vary) $\endgroup$
    – poncho
    Commented Apr 20, 2021 at 19:13
  • $\begingroup$ Ah, ok I see what you mean. My area of study leans more towards the hardware side of cryptography, with an interest in speed/reliability of specific hardware. So maybe looking at different error-correcting codes may still provide some use. I will also spend some more time looking at CCA. Thank you for your insights. Its difficult to research during COVID without collogues! $\endgroup$
    – Daftyler
    Commented Apr 20, 2021 at 19:54

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.