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 →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
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.
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
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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)
- [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.
- [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.
- [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.
- [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)
- [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.
- [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.
- [Figure 4 caption] The word 'cryptotext' should be 'ciphertext'.
- [Section II-C] The phrase 'Difference optimization strategies' appears to be a typo for 'Different optimization strategies.'
- [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
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
assumptions (5)
- standard math Naive matrix-matrix and matrix-vector multiplication complexities O(n^3) and O(n^2) apply to McEliece operations.
- domain assumption Binary Goppa codes admit an efficient decoding algorithm so that decryption complexity is O(n^2).
- domain assumption The Module-LWE problem is hard for quantum computers.
- ad hoc to paper The FLOP model for Kyber (2k^2 n FLOPs for matrix-vector multiplication over polynomial rings) captures practical complexity.
- domain assumption The NIST parameter sets in Tables III and IV represent comparable security levels.
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 from the paper (1 more)
Reference graph
Works this paper leans on
-
[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
work page 2017
-
[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
work page 2024
-
[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
work page 2021
-
[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
work page 2011
-
[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
work page 2019
-
[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
work page 2017
-
[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
work page 2017
-
[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
work page 2016
Show all 23 references
-
[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
2024
-
[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
2022
-
[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
2024
-
[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
2020
-
[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
2023 arXiv
-
[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
2024
-
[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
2022 arXiv
-
[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
2024
-
[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
2022
-
[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...
2021
-
[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
2023 arXiv
-
[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
2021
-
[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
2023
-
[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
2024
-
[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
1978
Reviewed August 16, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.