Pith. sign in

REVIEW 4 major objections 5 minor 23 references

Complexity of Post-Quantum Cryptography in Embedded Systems and Its Optimization Strategies

T0 review · 4 major / 5 minor · reviewed 2026-08-16 · deepseek-v4-flash

Pith's one-line read This paper claims that CRYSTALS-Kyber's smaller keys and lower FLOP costs make it better suited than McEliece for resource-constrained embedded systems, despite McEliece's smaller ciphertexts.

desk verdict Readable but largely expository survey whose central FLOP comparison is invalidated by a non-square matrix inversion and by counting ring operations as scalar FLOPs. read the letter →

arxiv 2504.13537 v1 pith:BNEHMHFR submitted 2025-04-18 cs.CR

classification cs.CR
keywords post-quantumcryptographyembeddedsystemsCRYSTALS-KyberMcEliecehardwarecomplexityFLOPanalysishigh-levelsynthesislattice-based
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tries to establish a practical ranking of post-quantum cryptography families for embedded systems, then works out a concrete comparison between the two NIST finalists CRYSTALS-Kyber and McEliece. It argues that Kyber's lattice-based design, with module rank $k = 2,3,4$ and polynomial degree $n = 256$, keeps public keys at 800–1568 bytes and key generation at $O(k^2 n)$, while McEliece's code-based design needs 261,120–1,044,480-byte keys and $O(n^3)$ key generation with $n$ in the thousands. If the paper is right, embedded designers should prefer Kyber whenever flash memory and compute are the bottleneck, keeping McEliece for settings where its 128–240-byte ciphertexts matter more than key storage. The paper also surveys optimization levers—pipelining, parallelization, high-level synthesis, modular reduction—that could shift these costs once implementations are tuned.

What carries the argument

The machinery that carries the argument is an asymptotic FLOP-count model built from the two schemes' defining algebraic operations. For Kyber the cost is driven by polynomial-matrix operations over $R_q = \mathbb{Z}_q[X]/(X^n+1)$: key generation and encryption are $O(k^2 n)$, decryption is $O(kn)$, with $n=256$ and $k=2,3,4$. For McEliece the cost is driven by binary Goppa-code matrix operations: key generation is $O(n^3)$, encryption $O(n^2)$, decryption $O(n^2)$, with code length $n$ in the thousands. The parameter tables and FLOP formulas turn those classes into concrete byte and FLOP figures, and Algorithm 1 packages the two schemes' key generation, encryption, decryption, and proposed optimizations into one implementation skeleton.

What would settle it

Run the same key generation, encryption, and decryption for Kyber512 and McEliece-348864 on an ARM Cortex-M4-class microcontroller with a fixed C implementation, counting cycles, flash, and energy; if McEliece's operations are not orders of magnitude costlier than Kyber's, or if the ranking reverses under memory-bound conditions, the paper's conclusion fails. A simpler check is mathematical: the displayed step $m = c'G^{-1}S^{-1}$ cannot be executed as written because $G$ is not square.

Watch

Extended reading notes

Core claim

The central claim is that, under the paper's complexity accounting, CRYSTALS-Kyber is the better fit for constrained devices: its public keys are orders of magnitude smaller and its key generation and decryption are cheaper by the stated FLOP model. Concretely, the paper reports Kyber512 with 800-byte keys and 2048 FLOPs for key generation, against McEliece-348864 with 261,120-byte keys and about $8.5\times 10^{10}$ FLOPs; Kyber encryption and decryption stay in the thousands of FLOPs, while McEliece's run into the millions or billions. McEliece's one clear advantage in the comparison is ciphertext size, 128–240 bytes versus 768–1568 bytes. The paper reads the balance as evidence that Kyber should be selected for memory- and computation-limited embedded targets, and it offers the family-level taxonomy—lattice, code, hash, multivariate, isogeny—as the decision structure for choosing among post-quantum schemes.

Load-bearing premise

The load-bearing premise is that the paper's FLOP model reflects what actually happens on embedded hardware, and that the McEliece decryption recipe can treat the $k \times n$ generator matrix $G$ as invertible even though $k<n$; if either premise gives way, the quantitative ranking is not trustworthy.

Editorial extensions

If this is right

  • For IoT and mobile targets with tight flash budgets, the paper's numbers imply Kyber should be chosen over McEliece at every security level.
  • Any deployment that adopts McEliece has to solve distribution of public keys hundreds of kilobytes long, which pushes the cost to storage and transport rather than computation.
  • McEliece's small ciphertexts remain a genuine advantage when the scarce resource is bandwidth, so the right choice depends on which resource is tighter.
  • The surveyed optimizations—pipelining, parallelization, high-level synthesis—are proposed as the way to bring the theoretical FLOP ranking closer to what real embedded hardware achieves.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Correcting the decryption sketch: Algorithm 1 writes the recovered McEliece message as $m = c'G^{-1}S^{-1}$, but the generator matrix $G$ is $k \times n$ with $k<n$ and is not invertible; a proper description would use syndrome decoding to recover the codeword before removing the scrambling matrix, and the paper's $O(n^2)$ decryption cost should be re-derived for that actual step.
  • A natural extension would turn the paper's category-level table into measured energy and memory figures by benchmarking representatives of each family on the same microcontroller, replacing asymptotic FLOPs with joules and bytes per operation.
  • One could combine the two schemes in a hybrid protocol: use Kyber to establish a session key and McEliece only for the final short message, so that memory-constrained devices get Kyber's small keys while the communication link still sends ciphertexts of only a few hundred bytes.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper surveys post-quantum cryptography (PQC) families for embedded systems, reviews optimization strategies such as pipelining, parallelization, and high-level synthesis, and then gives a complexity comparison between CRYSTALS-Kyber and McEliece. It claims that Kyber has significantly smaller key sizes and lower computational overhead, making it better suited to resource-constrained environments, while McEliece suffers from very large keys and expensive key generation. The paper supports this with parameter tables, FLOP-count figures, and a pseudocode description of both schemes.

Significance. If the quantitative claims were correct, the paper would provide a useful, accessible comparison for practitioners selecting among NIST finalists for embedded targets. The qualitative direction of the comparison—Kyber has far smaller keys and, on standard implementations, lower operating cost than Classic McEliece—is consistent with the broader literature, and the key-size and ciphertext-size tables in Section IV are straightforward and correct. However, the paper's novel quantitative contribution, the FLOP model and pseudocode in Sections III and IV, contains serious mathematical and modeling errors that invalidate the stated complexity figures. The taxonomy of PQC families and the list of optimization techniques are not novel and are presented without experimental validation.

major comments (4)
  1. [Section III-B and Algorithm 1 (Step 3)] The McEliece decryption procedure as written is mathematically invalid. In Algorithm 1, the message is recovered as m = c'·G^{-1}·S^{-1}, and Section III-B repeats this with m' = c'·G^{-1}. But the generator matrix G is k×n with k < n (for McEliece-348864, k is the code dimension and n=3488), so G is not square and has no inverse. The text even states this: G is a k×n matrix. The correct procedure is to decode y' to the codeword using the Goppa decoding algorithm, obtaining m·S, and then multiply by S^{-1}; no G^{-1} is involved. This error is load-bearing because the O(n^2) decryption complexity for McEliece is derived from the same invalid premise.
  2. [Section III-A and Figure 3] The FLOP model for CRYSTALS-Kyber is not representative of actual Kyber implementations. The paper counts key generation as 2k^2n FLOPs and encryption as 2k^2n FLOPs, treating multiplication in R_q = Z_q[X]/(X^n+1) as if it were a linear operation of cost O(n) per coefficient. In Kyber, polynomial multiplication is implemented with the number-theoretic transform (NTT) and costs Θ(n log n) modular multiplications, not O(n); in addition, key generation includes sampling from a centered binomial distribution, hashing, and compression steps that are not captured. Consequently, the specific comparison in Figure 3, e.g., Kyber-512 key generation at 2,048 FLOPs versus McEliece-348864 at 8.5×10^10 FLOPs, is computed from invalid formulas and cannot support the paper's central efficiency claim.
  3. [Section III-B and Table II] The claimed asymptotic complexities for McEliece are oversimplified to the point of being misleading. Key generation is modeled as a single matrix-matrix multiplication with complexity O(n^3), but producing the public key in Classic McEliece involves generating a Goppa code, constructing the corresponding generator matrix, and applying the scrambling and permutation matrices; the cost is not a single generic n×n multiplication. Similarly, decryption is not matrix inversion but Goppa decoding, typically performed via syndrome computation and Berlekamp-Massey or Patterson's algorithm. The table therefore does not give a meaningful comparison of the actual algorithms, and the text's assertion that decryption has O(n^2) cost needs a concrete algorithm citation or derivation.
  4. [Section II and Algorithm 1] The optimization section is presented as a contribution, but Algorithm 1 merely names techniques such as pipelining, HLS, modular reduction, and memory optimization in a loop; it does not specify how these techniques are applied to Kyber or McEliece, nor does the paper provide any synthesis, timing, or resource-utilization results. As written, the 'optimized' algorithm is a sketch without measurable effect, so the optimization claims are not supported.
minor comments (5)
  1. [Section III-C] The text states 'McEliece uses larger parameters, such as n = 1024,' which contradicts Table IV, where code lengths are n = 3488, 4608, and 6688. This inconsistency should be corrected.
  2. [Figure 3] The vertical axis is labeled 'FLOP Count' with tick values such as 10^2 and 10^10, but it is not clear whether the axis is logarithmic or whether the bars are drawn to scale; the caption should specify the scale and the exact formula used for each bar.
  3. [Figure 4 caption] The word 'cryptotext' should be 'ciphertext'.
  4. [Section II-C] The phrase 'Difference optimization strategies' appears to be a typo for 'Different optimization strategies.'
  5. [Reference [23]] The title 'A public-key cryptosystem based on algebraic' is incomplete and 'Coding Thv' is a typo; the reference should be given in full.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the complexity comparison is self-contained and rests on standard operation counts, not on fitted or self-cited premises.

full rationale

The paper's central comparison (Kyber vs McEliece complexity, Figs. 2-4) is derived from standard algorithm definitions: Kyber key generation is A·s+e modeled as O(k^2 n) with 2k^2 n FLOPs, and McEliece key generation is S·G·P modeled as O(n^3). These formulas are not fitted to the conclusion; they are stated complexity models for the actual NIST candidate algorithms, and the parameters are taken from standardized parameter tables. All external claims are cited to independent prior work, and no load-bearing reduction to a self-citation occurs. The paper does contain a mathematical error (McEliece decryption using G^{-1} for a non-square generator matrix) and the FLOP comparison omits some real implementation costs (e.g., NTT), but these are correctness or accuracy issues, not circularity: the comparison does not assume the conclusion it draws. Hence no circular steps.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper relies on standard complexity results for matrix operations, assumptions about the hardness of Module-LWE and Goppa decoding, and the NIST parameter sets. It introduces no free parameters fitted to data, but the FLOP model in Section III-A is an ad hoc simplification that ignores implementation overheads.

assumptions (5)
  • standard math Naive matrix-matrix and matrix-vector multiplication complexities O(n^3) and O(n^2) apply to McEliece operations.
    Used in Section III-B to derive key generation complexity O(n^3) and encryption/decryption complexity O(n^2).
  • domain assumption Binary Goppa codes admit an efficient decoding algorithm so that decryption complexity is O(n^2).
    Assumed in Section III-B to claim McEliece decryption is O(n^2); no specific decoder or implementation is given.
  • domain assumption The Module-LWE problem is hard for quantum computers.
    Basis for Kyber security stated in Section III-A; the paper provides no proof or new evidence.
  • ad hoc to paper The FLOP model for Kyber (2k^2 n FLOPs for matrix-vector multiplication over polynomial rings) captures practical complexity.
    Introduced in Section III-A for numerical comparison; ignores NTT, modular reduction, and sampling costs, so it is a simplifying choice, not a measured quantity.
  • domain assumption The NIST parameter sets in Tables III and IV represent comparable security levels.
    Used in Section IV to compare key sizes and FLOP counts across security levels.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Complexity of Post-Quantum Cryptography in Embedded Systems and Its Optimization Strategies." pith.science (2026). https://pith.science/paper/BNEHMHFR

@misc{pith2026250413537,
  author       = {Pith},
  title        = {Pith review of: Complexity of Post-Quantum Cryptography in Embedded Systems and Its Optimization Strategies},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BNEHMHFR}},
  note         = {Machine review of arXiv:2504.13537}
}
read the original abstract

With the rapid advancements in quantum computing, traditional cryptographic schemes like Rivest-Shamir-Adleman (RSA) and elliptic curve cryptography (ECC) are becoming vulnerable, necessitating the development of quantum-resistant algorithms. The National Institute of Standards and Technology (NIST) has initiated a standardization process for PQC algorithms, and several candidates, including CRYSTALS-Kyber and McEliece, have reached the final stages. This paper first provides a comprehensive analysis of the hardware complexity of post-quantum cryptography (PQC) in embedded systems, categorizing PQC algorithms into families based on their underlying mathematical problems: lattice-based, code-based, hash-based and multivariate / isogeny-based schemes. Each family presents distinct computational, memory, and energy profiles, making them suitable for different use cases. To address these challenges, this paper discusses optimization strategies such as pipelining, parallelization, and high-level synthesis (HLS), which can improve the performance and energy efficiency of PQC implementations. Finally, a detailed complexity analysis of CRYSTALS-Kyber and McEliece, comparing their key generation, encryption, and decryption processes in terms of computational complexity, has been conducted.

Figures

Figures reproduced from arXiv: 2504.13537 by the authors.

Figure 1
Figure 1. Optimization Strategies III. COMPLEXITY ANALYSIS A. CRYSTALS-Kyber CRYSTALS-Kyber is a lattice-based cryptosystem that relies on the module learning with errors (Module-LWE) problem. The security of Kyber is based on the difficulty of solving the Module-LWE problem, even for quantum computers, making it a strong candidate for post-quantum cryptography. The Kyber is a key encapsulation mechanism (KEM) that is part of… view at source ↗
Figure 2
Figure 2. compares the key sizes of CRYSTALS-Kyber and McEliece across different security levels (128-bit, 192-bit, 256-bit). The key size is a critical metric as it influences both the storage requirements and transmission overhead within cryptographic systems. CRYSTALS-Kyber has signifi￾cantly smaller key sizes compared to McEliece. For example, Kyber512 (128-bit security) has a key size of 800 bytes, while McEliece-348864 … view at source ↗
Figure 3
Figure 3. compares the computational complexity of CRYSTALS-Kyber and McEliece in terms of FLOP counts for key generation, encryption, and decryption. FLOP counts provide a measure of the computational effort required for each operation. CRYSTALS-Kyber has much lower FLOP counts for all operations compared to McEliece. For ex￾ample, Kyber-512 requires 2048 FLOPs for key generation, while McEliece-348864 requires 8.51010 FLOPs… view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: compares the ciphertext sizes of CRYSTALS-Kyber and McEliece at different security levels. The size of the cryptotext is important because it affects the amount of data that must be transmitted during encryption. CRYSTALS￾Kyber has larger ciphertext sizes compared to M…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 22 canonical work pages

  1. [1]

    Crystals-dilithium algorithm specificati ons and sup- porting documentation,

    L. Ducas, E. Kiltz, T. Lepoint, V . Lyubashevsky, P . Schwa be, G. Seiler, and D. Stehl´ e, “Crystals-dilithium algorithm specificati ons and sup- porting documentation,” 2017

  2. [2]

    p qm4: Benchmarking nist additional post-quantum signature sche mes on microcontrollers,

    M. J. Kannwischer, M. Krausz, R. Petri, and S.-Y . Y ang, “p qm4: Benchmarking nist additional post-quantum signature sche mes on microcontrollers,” Cryptology ePrint Archive , 2024

  3. [3]

    Classic mceliece on the arm corte x- m4,

    M.-S. Chen and T. Chou, “Classic mceliece on the arm corte x- m4,” IACR Transactions on Cryptographic Hardware and Embedded Systems, pp. 125–148, 2021

  4. [4]

    Xmss - a pract ical for- ward secure signature scheme based on minimal security assu mptions,

    J. A. Buchmann, E. Dahmen, and A. H¨ ulsing, “Xmss - a pract ical for- ward secure signature scheme based on minimal security assu mptions,” IACR Cryptol. ePrint Arch. , vol. 2011, p. 484, 2011

  5. [5]

    The sphincs+ signature framework,

    D. J. Bernstein, A. H¨ ulsing, S. K¨ olbl, R. Niederhagen,J. Rijneveld, and P . Schwabe, “The sphincs+ signature framework,” in Proceedings of the 2019 ACM SIGSAC conference on computer and communicatio ns security, 2019, pp. 2129–2146

  6. [6]

    Gimli: a cross-platform permutation,

    D. J. Bernstein, S. K¨ olbl, S. Lucks, P . M. C. Massolino, F . Mendel, K. Nawaz, T. Schneider, P . Schwabe, F.-X. Standaert, Y . Todo et al. , “Gimli: a cross-platform permutation,” in Cryptographic Hardware and Embedded Systems–CHES 2017: 19th International Confer ence, Taipei, Taiwan, September 25-28, 2017, Proceedings . Springer, 2017, pp. 299–320

  7. [7]

    Su- persingular isogeny key encapsulation,

    R. Azarderakhsh, M. Campagna, C. Costello, L. D. Feo, B. H ess, A. Jalali, D. Jao, B. Koziel, B. LaMacchia, P . Longa et al. , “Su- persingular isogeny key encapsulation,” Submission to the NIST Post- Quantum Standardization project , vol. 152, pp. 154–155, 2017

  8. [8]

    Po st- quantum cryptography on fpga based on isogenies on elliptic curves,

    B. Koziel, R. Azarderakhsh, M. M. Kermani, and D. Jao, “Po st- quantum cryptography on fpga based on isogenies on elliptic curves,” IEEE Transactions on Circuits and Systems I: Regular Papers , vol. 64, no. 1, pp. 86–99, 2016

Show all 23 references
  1. [9]

    Evaluati on of hardware and software implementations for nist finalist and fourth- round post-quantum cryptography kems,

    M. Bandaru, S. E. Mathe, and C. Wattanapanich, “Evaluati on of hardware and software implementations for nist finalist and fourth- round post-quantum cryptography kems,” Computers and Electrical Engineering, vol. 120, p. 109826, 2024

  2. [10]

    A compact and high-performance ha rdware architecture for crystals-dilithium,

    C. Zhao, N. Zhang, H. Wang, B. Y ang, W. Zhu, Z. Li, M. Zhu, S. Yin, S. Wei, and L. Liu, “A compact and high-performance ha rdware architecture for crystals-dilithium,” IACR Trans. Cryptogr . Hardw. Embed. Syst. , vol. 2022, pp. 270–295, 2021

  3. [11]

    High-performance hard ware implementation of mpcith and picnic3,

    G. Liu, K. Jia, P . Wei, and L. Ju, “High-performance hard ware implementation of mpcith and picnic3,” IACR Trans. Cryptogr . Hardw. Embed. Syst. , vol. 2024, pp. 190–214, 2024

  4. [12]

    Risq-v: Ti ghtly coupled risc-v accelerators for post-quantum cryptography,

    T. Fritzmann, G. Sigl, and M. J. Sep´ ulveda, “Risq-v: Ti ghtly coupled risc-v accelerators for post-quantum cryptography,” IACR Cryptol. ePrint Arch. , vol. 2020, p. 446, 2020

  5. [13]

    Cermet: Coding for energy red uction with multiple encryption techniques - it’s easy being green ,

    J. Woo, V . A. V asudevan, B. Z. Kim, A. Cohen, R. G. L. D’Oli veira, T. Stahlbuhk, and M. M’edard, “Cermet: Coding for energy red uction with multiple encryption techniques - it’s easy being green ,” ArXiv, vol. abs/2308.05063, 2023

  6. [14]

    Parallel quantum signal processing via polynomial factor ization,

    J. M. Martyn, Z. M. Rossi, K. Z. Cheng, Y . Liu, and I. Chuan g, “Parallel quantum signal processing via polynomial factor ization,” 2024

  7. [15]

    A high-level sy nthesis approach for precisely-timed, energy-efficient embedded s ystems,

    Y . Liao, T. Adegbija, and R. L. Lysecky, “A high-level sy nthesis approach for precisely-timed, energy-efficient embedded s ystems,” ArXiv, vol. abs/2404.14769, 2022

  8. [16]

    Hierarchical source -to-post- route qor prediction in high-level synthesis with gnns,

    M. Gao, J. Zhao, Z. Lin, and M. Guo, “Hierarchical source -to-post- route qor prediction in high-level synthesis with gnns,” 2024 Design, Automation & Test in Europe Conference & Exhibition (DATE) , pp. 1–6, 2024

  9. [17]

    Security and reliability evaluation of counterm easures im- plemented using high-level synthesis,

    A.-A. Koufopoulou, K. Xevgeni, A. Papadimitriou, M. Ps arakis, and D. H´ ely, “Security and reliability evaluation of counterm easures im- plemented using high-level synthesis,” 2022 IEEE 28th International Symposium on On-Line Testing and Robust System Design (IOLT S), pp. 1–8, 2022

  10. [18]

    Towards security recommendations for public-ke y infras- tructures for production environments in the post-quantum era,

    S. E. Y unakovsky, M. Kot, N. O. Pozhar, D. Nabokov, M. A. K udinov, A. Guglya, E. O. Kiktenko, E. Kolycheva, A. Borisov, and A. K. Fedorov, “Towards security recommendations for public-ke y infras- tructures for production environments in the post-quantum era,” EPJ Quantum Te...

  11. [19]

    Protecting quantum procra stinators with signature lifting: A case study in cryptocurrencies,

    O. Sattath and S. Wyborski, “Protecting quantum procra stinators with signature lifting: A case study in cryptocurrencies,” ArXiv, vol. abs/2303.06754, 2023

  12. [20]

    Quan tum mean- value approximator for hard integer-value problems,

    D. Joseph, A. J. Martinez, C. Ling, and F. Mintert, “Quan tum mean- value approximator for hard integer-value problems,” Physical Review A, 2021

  13. [21]

    Quantum binary field multiplication with optimized toffol i depth and extension to quantum inversion,

    K. B. Jang, W. Kim, S. Lim, Y . L. Kang, Y . Y ang, and H. Seo, “Quantum binary field multiplication with optimized toffol i depth and extension to quantum inversion,” Sensors (Basel, Switzerland) , vol. 23, 2023

  14. [22]

    En- hancing the security of classical communication with post- quantum authenticated-encryption schemes for the quantum key dist ribution,

    F. R. Ghashghaei, Y . Ahmed, N. Elmrabit, and M. Y ousefi, “ En- hancing the security of classical communication with post- quantum authenticated-encryption schemes for the quantum key dist ribution,” Comput., vol. 13, p. 163, 2024

  15. [23]

    A public-key cryptosystem based on alg ebraic,

    R. J. McEliece, “A public-key cryptosystem based on alg ebraic,” Coding Thv , vol. 4244, pp. 114–116, 1978

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.