Pith. sign in

REVIEW 1 minor 30 references

Two code-based schemes turn restricted-error decoding and code equivalence into post-quantum digital signatures.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.3

2026-07-01 04:48 UTC pith:SVU3XD5D

load-bearing objection This is a clear expository overview of CROSS and LESS with no new technical results or analyses.

arxiv 2606.31601 v1 pith:SVU3XD5D submitted 2026-06-30 cs.CR cs.ITmath.IT

Digital signature schemes based on code equivalence and syndrome decoding from restricted errors

Sarah Arpin , Jason T. LeGrow , Hiram H. L\'opez , Gretchen L. Matthews This is my paper
classification cs.CR cs.ITmath.IT
keywords code-based cryptographydigital signaturespost-quantum securitysyndrome decodingcode equivalencesigma protocolsFiat-Shamir transform
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper reviews two signature schemes built on error-correcting codes. One rests on the hardness of syndrome decoding when errors are confined to a restricted set of positions. The other rests on the hardness of deciding whether two linear codes are equivalent under permutation of coordinates. It walks through the construction of sigma protocols for each problem and their conversion into non-interactive signatures. A sympathetic reader would care because these constructions supply code-based options for proving authenticity if quantum computers arrive.

Core claim

The Fiat-Shamir transform applied to sigma protocols for the syndrome decoding problem with restricted errors and for the code equivalence problem produces digital signature schemes believed to remain secure against quantum adversaries.

What carries the argument

Sigma protocols for syndrome decoding from restricted errors and for code equivalence, converted to signatures by the Fiat-Shamir transform.

Load-bearing premise

The problems of syndrome decoding from restricted errors and of deciding code equivalence stay computationally hard for both classical and quantum algorithms.

What would settle it

An efficient algorithm, classical or quantum, that solves the restricted-error syndrome decoding problem or the code equivalence problem for the parameter sizes used in the schemes would falsify their security.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • The signatures can be used wherever data authenticity must survive quantum attacks.
  • The two schemes rest on distinct hardness assumptions from many other post-quantum methods.
  • The explicit reduction from the underlying problems to signature forgery supplies a clear security argument.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar sigma-protocol constructions could be attempted on other variants of coding-theory problems to produce additional signature families.
  • Concrete efficiency measurements of signature size and verification time for these schemes would clarify their practical trade-offs relative to other post-quantum options.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 1 minor

Summary. The manuscript is an expository overview of two NIST second-round post-quantum signature candidates, CROSS and LESS. It describes the underlying problems (syndrome decoding from restricted errors and code equivalence), reviews sigma protocols, explains the Fiat-Shamir transform, and states that the resulting signatures are believed to be post-quantum secure on the basis of those pre-existing hardness assumptions. No new constructions, reductions, or parameter analyses are claimed.

Significance. As a review paper the work has moderate significance: it supplies a structured account of existing schemes and explicitly ties security to standard assumptions rather than new derivations. This may aid accessibility for researchers following the NIST process. No machine-checked proofs, reproducible code, or falsifiable predictions are provided.

minor comments (1)
  1. [Abstract] Abstract: the phrasing 'explain how this procedure yields code-based digital signatures believed to be post-quantum secure' could be tightened to make clearer that security rests entirely on prior hardness assumptions for the two problems, with no new analysis supplied in the manuscript.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive recommendation to accept the manuscript. The review correctly identifies the paper as an expository overview of the CROSS and LESS schemes, their underlying hardness assumptions, and the sigma-protocol plus Fiat-Shamir construction, without claiming new results.

Circularity Check

0 steps flagged

No significant circularity; expository review without derivations

full rationale

The manuscript is an overview of the existing CROSS and LESS signature schemes. It describes the syndrome decoding and code equivalence problems, sigma protocols, and the Fiat-Shamir transform, but introduces no new equations, predictions, security reductions, or parameter derivations. The claim of post-quantum security is attributed solely to the pre-existing hardness assumptions on those problems rather than any internal derivation chain. No load-bearing steps reduce to self-definition, fitted inputs, or self-citations.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No new axioms, parameters, or entities are introduced; the paper restates existing cryptographic assumptions from the cited schemes.

pith-pipeline@v0.9.1-grok · 5671 in / 949 out tokens · 28933 ms · 2026-07-01T04:48:46.266893+00:00 · methodology

0 comments
read the original abstract

Digital signature schemes are an important cryptographic tool to ensure data authenticity and integrity in many applications that must be resilient to attacks, including those facilitated by quantum computers. We consider the two digital signature schemes based on error-correcting codes that are second-round candidates in NIST's call for Additional Signature Schemes, which is part of the Post-Quantum Cryptography Standardization Process. Specifically, we provide an overview of the Codes and Restricted Objects Signature Scheme (CROSS) and the Linear Equivalence Signature Scheme (LESS). We describe their underlying problems of syndrome decoding from restricted errors and code equivalence. We review sigma protocols and how they can be transformed into digital signature schemes via the Fiat-Shamir transform. Finally, we explain how this procedure yields code-based digital signatures believed to be post-quantum secure.

Figures

Figures reproduced from arXiv: 2606.31601 by Gretchen L. Matthews, Hiram H. L\'opez, Jason T. LeGrow, Sarah Arpin.

Figure 1
Figure 1. Figure 1: Examples of digital signature schemes. and Technology (NIST) recommends transitioning by 2030 and requires it by 2035 [22]. Most current digital signatures are created using classical pro￾tocols such as those shown in [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Signing and verification with forgery attempt; valid signatures verify and forgeries fail. [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Sigma-protocol depicting Alice using skA to generate commitment comm, followed by Bob sharing a challenge chal, after which Alice provides a response respchal using skA that Bob can then verify using Alice’s public key pkA leading to acceptance or rejection. Round 1 Additional Signatures incorporate the Fiat￾Shamir transform, including CROSS and LESS, the code-based schemes discussed in this article. The F… view at source ↗
Figure 4
Figure 4. Figure 4: The Fiat-Shamir transform reduces the in [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Two equivalent linear codes over F3. In blue, the code C0 is generated by (1, 0, 0) and (0, 1, 1). In red, the code C1 is generated by (0, 1, 0) and (1, 0, 1). These codes are equivalent: C1 is obtained from C0 by exchanging the first and second coordi￾nates. Points in purple are common to both codes. Two kinds of linear maps that preserve this weight are Scaling coordinates: For λ = (λ1, . . . , λn), x = … view at source ↗
Figure 6
Figure 6. Figure 6: The sigma protocol incorporating multiple [PITH_FULL_IMAGE:figures/full_fig_p010_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: The modified verification procedure exploit [PITH_FULL_IMAGE:figures/full_fig_p010_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Signing time in Mcycles. Level I Level III Level V 0 0.5 1 1.5 ·105 CROSS LESS MEDS [PITH_FULL_IMAGE:figures/full_fig_p011_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Public key + signature size in bytes. All three code-based digital signatures are based on novel underlying assumptions and feature a variety of performant parameter sets for varied use cases. The concrete security of the underlying problems remains an important direction for future research. REFERENCES [1] M. R. Albrecht, D. J. Bernstein, T. Chou, C. Cid, J. Gilcher, T. Lange, V. Maram, I. von Maurich, R.… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages

  1. [1]

    M. R. Albrecht, D. J. Bernstein, T. Chou, C. Cid, J. Gilcher, T. Lange, V . Maram, I. von Maurich, R. Mis- oczki, R. Niederhagen, K. G. Paterson, E. Persichetti, C. Peters, P. Schwabe, N. Sendrier, J. Szefer, C. J. Tjhai, M. Tomlinson, and W. Wang. Classic McEliece, 2020. NIST PQC Round 3 submission

    work page 2020

  2. [2]

    Aragon, P

    N. Aragon, P. Barreto, W. Beullens, P. Gaborit, A. Joux, S.-Y . Lau, E. Persichetti, C. Peters, and J.-P. Tillich. BIKE: Bit flipping key encapsulation, 2020. NIST PQC Round 3 submission

    work page 2020

  3. [3]

    Attema and S

    T. Attema and S. Fehr. Parallel repetition of (k1, . . . , kµ)- special-sound multi-round interactive proofs. In Y . Dodis and T. Shrimpton, editors, Advances in Cryptology – 11 CRYPTO 2022, volume 13507 of Lecture Notes in Com- puter Science, pages 415–443. Springer, 2022

    work page 2022

  4. [4]

    L. Babai. Graph isomorphism in quasipolynomial time. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC) , pages 684–697. ACM, 2016

    work page 2016

  5. [5]

    Baldi, A

    M. Baldi, A. Barenghi, M. Battagliola, S. Bitzer, M. Gi- anvecchio, P. Karl, F. Manganiello, A. Pavoni, G. Pelosi, F. Pintore, P. Santini, J. Schupp, E. Signorini, F. Slaugh- ter, A. Wachter-Zeh, and V . Weger. CROSS: Codes and restricted objects signature scheme, 2023. NIST PQC Additional Digital Signature Schemes submission

    work page 2023

  6. [6]

    Berlekamp, R

    E. Berlekamp, R. McEliece, and H. van Tilborg. On the inherent intractability of certain coding problems (corresp.). IEEE Transactions on Information Theory , 24(3):384–386, 1978

    work page 1978

  7. [7]

    Biasse, G

    J.-F. Biasse, G. Micheli, E. Persichetti, and P. Santini. LESS is more: Code-based signatures without syndromes. In A. Nitaj and A. M. Youssef, editors, AFRICACRYPT 2020, volume 12174 of LNCS, pages 45–65. Springer, Cham, July 2020

    work page 2020

  8. [8]

    Bitzer, A

    S. Bitzer, A. Pavoni, V . Weger, P. Santini, M. Baldi, and A. Wachter-Zeh. Generic Decoding of Restricted Errors. In Proceedings of the 2023 IEEE International Symposium on Information Theory (ISIT) , pages 246– 251, Taipei, Taiwan, 2023. IEEE

    work page 2023

  9. [9]

    Bogart, D

    K. Bogart, D. Goldberg, and J. Gordon. An elementary proof of the MacWilliams theorem on equivalence of codes. Information and Control , 37(1):19–22, 1978

    work page 1978

  10. [10]

    Cayrel, P

    P.-L. Cayrel, P. V ´eron, and S. M. El Yousfi Alaoui. A zero-knowledge identification scheme based on the q-ary syndrome decoding problem. In A. Biryukov, G. Gong, and D. R. Stinson, editors, Selected Areas in Cryptogra- phy, pages 171–186. Springer Berlin Heidelberg, 2011

    work page 2011

  11. [11]

    T. Chou, R. Niederhagen, E. Persichetti, T. H. Ran- drianarisoa, K. Reijnders, S. Samardjiska, and M. Tri- moska. Take your MEDS: Digital signatures from ma- trix code equivalence. In N. El Mrabet, L. De Feo, and S. Duquesne, editors, AFRICACRYPT 2023, volume 14064 of LNCS, pages 28–52. Springer, Cham, July 2023

    work page 2023

  12. [12]

    Diffie and M

    W. Diffie and M. Hellman. New directions in cryp- tography. IEEE Transactions on Information Theory , 22(6):644–654, 1976

    work page 1976

  13. [13]

    Ducas, E

    L. Ducas, E. Kiltz, T. Lepoint, V . Lyubashevsky, P. Schwabe, G. Seiler, and D. Stehl ´e. CRYSTALS- Dilithium: A lattice-based digital signature scheme. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2018(1):238–268, 2018

    work page 2018

  14. [14]

    Fiat and A

    A. Fiat and A. Shamir. How to prove yourself: Practical solutions to identification and signature problems. In A. M. Odlyzko, editor, CRYPTO ’86, pages 186–194. Springer Berlin Heidelberg, 1987

    work page 1987

  15. [15]

    M. J. E. Golay. Notes on Digital Coding. Proceedings of the IRE , 37(6):657, 1949

    work page 1949

  16. [16]

    Gorla and F

    E. Gorla and F. Salizzoni. MacWilliams’ extension theorem for rank-metric codes. Journal of Symbolic Computation, 122:102263, 2024

    work page 2024

  17. [17]

    L. K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty- Eighth Annual ACM Symposium on Theory of Computing, STOC ’96, page 212–219, New York, NY , USA, 1996. Association for Computing Machinery

    work page 1996

  18. [18]

    R. W. Hamming. Error detecting and error correcting codes. The Bell System Technical Journal , 29(2):147– 160, 1950

    work page 1950

  19. [19]

    F. J. MacWilliams. Combinatorial Problems of Ele- mentary Abelian Groups . PhD dissertation, Harvard University, 1962

    work page 1962

  20. [20]

    R. J. McEliece. A public-key cryptosystem based on algebraic coding theory. Deep Space Network Progress Report, 44:114–116, Jan. 1978

    work page 1978

  21. [21]

    C. A. Melchor, N. Aragon, S. Bettaieb, L. Bidoux, O. Blazy, J. Bos, J. Deneuville, A. Dion, P. Gaborit, J. La- can, E. Persichetti, J. Robert, P. V ´eron, and G. Z ´emor. HQC: Hamming quasi-cyclic. NIST PQC Submission, 2025

    work page 2025

  22. [22]

    Moody, R

    D. Moody, R. Perlner, A. Regenscheid, A. Robinson, and D. Cooper. Transition to post-quantum cryptography standards. Technical Report NIST IR 8547 IPD, National Institute of Standards and Technology, Nov. 2024. Initial Public Draft

    work page 2024

  23. [23]

    Post-quantum cryptography standardization

    National Institute of Standards and Technology. Post-quantum cryptography standardization. https://csrc.nist.gov/projects/post-quantum-cryptography/ post-quantum-cryptography-standardization, 2017. Updated December 2025

    work page 2017

  24. [24]

    Status report on the first round of the additional digital signature schemes for the NIST post-quantum cryptography stan- dardization process

    National Institute of Standards and Technology. Status report on the first round of the additional digital signature schemes for the NIST post-quantum cryptography stan- dardization process. Technical Report NIST IR 8528, National Institute of Standards and Technology, Oct. 2024

    work page 2024

  25. [25]

    Niederreiter

    H. Niederreiter. Knapsack-type cryptosystems and alge- braic coding theory. Problems of Control and Information Theory, 15(2):157–166, 1986

    work page 1986

  26. [26]

    Petrank and R

    E. Petrank and R. M. Roth. Is code equivalence easy to decide? IEEE Transactions on Information Theory , 43(5):1602–1604, 1997

    work page 1997

  27. [27]

    Prest, P

    T. Prest, P. Fouque, L. Ducas, J. Tillich, M. M. Szydlo, and P. Gaborit. Falcon: Fast-Fourier lattice-based com- pact signatures over NTRU. IACR Transactions on Cryp- tographic Hardware and Embedded Systems , 2019(1):1– 42, 2019

    work page 2019

  28. [28]

    R. L. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public-key cryptosys- tems. Commun. ACM, 21(2):120–126, Feb. 1978

    work page 1978

  29. [29]

    C.-P. Schnorr. Efficient signature generation by smart cards. Journal of Cryptology , 4(3):161–174, Jan. 1991

    work page 1991

  30. [30]

    P. Shor. Algorithms for quantum computation: Discrete logarithms and factoring. In Proceedings 35th Annual Symposium on Foundations of Computer Science , pages 124–134, 1994. 12 SHORT BIOS Sarah Arpin (sarpin@vt.edu) is an Assistant Professor in the Department of Mathematics at Virginia Tech. She earned an M.A. in Pure Mathematics from CUNY Hunter College...

    work page 1994