Comparative Complexity Analysis of MLKEM & HQC
Authors
Werge, Julie Timmermann ; Byrjalsen, Stine
Term
4. semester
Education
Publication year
2025
Abstract
Dette speciale sammenligner de asymptotiske tids-, plads- og bit-kompleksiteter for de post-kvante nøgleindkapslingsmekanismer ML-KEM og HQC med fokus på egnethed til ressourcebegrænsede enheder. Metoden er en analytisk udledning af kompleksitetsudtryk og en evaluering af skalering på tværs af tre sikkerhedskategorier under varierende inputparametre. Resultaterne viser, at ML-KEM har langsommere og mere forudsigelig vækst på alle mål, mens HQC udviser stejle stigninger—særligt i dekapsuleringstiden, som skalerer kvadratisk og medfører operationsantal flere størrelsesordener over ML-KEM. HQC producerer desuden markant større chiffertekster og kræver to til fire størrelsesordener mere hukommelse som følge af større parameterstørrelser. Konklusionen er, at ML-KEM tilbyder mere gunstig kompleksitetsskalering og derfor er bedre egnet til latensfølsomme, hukommelsesbegrænsede og båndbreddebegrænsede enheder.
This thesis compares the asymptotic time, space, and bit complexities of the post-quantum key encapsulation mechanisms ML-KEM and HQC, with an emphasis on suitability for resource-constrained devices. The method is an analytical derivation of complexity expressions and an evaluation of their scaling across three security categories under varying input parameters. The results indicate that ML-KEM exhibits slower, more predictable growth on all metrics, whereas HQC shows steep increases—especially in decapsulation time, which scales quadratically and yields operation counts orders of magnitude higher than ML-KEM. HQC also produces significantly larger ciphertexts and requires two to four orders of magnitude more memory due to larger parameter sizes. The conclusion is that ML-KEM offers more favorable complexity scaling and is therefore better suited to latency-sensitive, memory-limited, and bandwidth-constrained devices.
[This summary has been generated with the help of AI directly from the project (PDF)]
Documents