CRT-Decomposed Σ-Protocols for CSIDH

Abstract

We construct a zero-knowledge proof of knowledge for the CSIDH group action that exploits the Chinese Remainder Theorem (CRT) structure of the ideal class group, available whenever the group structure is known exactly, as for CSIDH-512. We prove perfect completeness, perfect special honest-verifier zero-knowledge, and 2-special soundness, in which the secret is recovered from two accepting transcripts by one subtraction and one modular inversion per CRT component; no rewinding loop, lattice reduction, or heuristic sampling appears in the extractor. Because each round admits exactly two responses, Unruh's transform yields a non-interactive proof with straight-line extraction in the quantum random oracle model (QROM), removing the multiplicative forking-lemma loss. We instantiate the scheme on the CSIDH-512 class group, verify the algebraic layer by machine over the exact 258-bit modulus (10⁴ random instances, all passing), and report protocol-level simulations in the exponent model: Monte Carlo soundness rates matching the proven 2^−t bound within 95\% confidence at every tested t, serialized signature sizes within 1.6\% of the formulas, instrumented action counts, and a scaled meet-in-the-middle attack whose measured cost follows the predicted √q law. We further prove two delimiting results: CRT decomposition cannot enlarge the per-round challenge space, and publishing the CRT hop curves lowers classical key-recovery cost from about 2^128.6 to about 2^67.3 group action evaluations. The construction is therefore correct and structurally complete today, but quantitatively secure only on future parameters whose class number has large prime factors. We compare against CSI-FiSh, CSI-Otter, and Tanuki; a tightly secure blind signature from this proof of knowledge is left to future work.

DELUGE: Decomposed Entropy-coded Live Unstructured Geometry Exchange for Real-time Particle Streaming
Hikari Yanagawa, Yuichi Hiroi, Takefumi Hiraki
arXiv17 Sep 2026PreprintarXiv licenceFull textGeneral mathematicsarXiv
Domain-decomposed Evolutional Deep Neural Network with Random Features for Transient Pressure Diffusion with Discontinuous and High-Contrast Coefficients
Peiqi Li, Jie Chen, Hui Zhang +1
arXiv17 Sep 2026PreprintarXiv licenceFull textMathematical physics Numerical analysis & scientific computingarXiv
Measurement-angle control of a continuously monitored quantum oscillator: purification limits and optimal protocols
Ralph Sabbagh, Olga Movilla Miangolarra, Andrew N. Jordan +1
arXiv1 Nov 2026PreprintarXiv licenceFull textOptimisation & control Quantum physics & quantum informationarXiv
Can We Trust Evaluations of AI Weather Forecasts for Extremes? How Evaluation Protocols Shape Model Rankings
Tobias Biegert, Sam Allen, Zhongwei Zhang +1
arXiv22 Oct 2026PreprintarXiv licenceFull textAtmospheric science & meteorology StatisticsarXiv
Do Machine Learning-Guided Proactive Full Capacity Protocols Mitigate Emergency Department Overcrowding? A Simulation-Based Evaluation
Khalid Aram, Orhun Vural, Bunyamin Ozaydin +2
arXiv1 Oct 2026PreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeX RIS

BibTeX

@misc{dey2026crtdecomposed,
  title = {{CRT-Decomposed $Σ$-Protocols for CSIDH}},
  author = {I. Dey and I. Cherkaoui},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.26258},
  eprint = {2609.26258},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.26258},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - CRT-Decomposed Σ-Protocols for CSIDH
AU  - I. Dey
AU  - I. Cherkaoui
PY  - 2026
DA  - 2026/09/01
PB  - arXiv
DO  - 10.48550/arxiv.2609.26258
UR  - https://arxiv.org/abs/2609.26258
AB  - We construct a zero-knowledge proof of knowledge for the CSIDH group action that exploits the Chinese Remainder Theorem (CRT) structure of the ideal class group, available whenever the group structure is known exactly, as for CSIDH-512. We prove perfect completeness, perfect special honest-verifier zero-knowledge, and 2-special soundness, in which the secret is recovered from two accepting transcripts by one subtraction and one modular inversion per CRT component; no rewinding loop, lattice reduction, or heuristic sampling appears in the extractor. Because each round admits exactly two responses, Unruh's transform yields a non-interactive proof with straight-line extraction in the quantum random oracle model (QROM), removing the multiplicative forking-lemma loss. We instantiate the scheme on the CSIDH-512 class group, verify the algebraic layer by machine over the exact 258-bit modulus (10^4 random instances, all passing), and report protocol-level simulations in the exponent model: Monte Carlo soundness rates matching the proven 2^−t bound within 95\% confidence at every tested t, serialized signature sizes within 1.6\% of the formulas, instrumented action counts, and a scaled meet-in-the-middle attack whose measured cost follows the predicted √q law. We further prove two delimiting results: CRT decomposition cannot enlarge the per-round challenge space, and publishing the CRT hop curves lowers classical key-recovery cost from about 2^128.6 to about 2^67.3 group action evaluations. The construction is therefore correct and structurally complete today, but quantitatively secure only on future parameters whose class number has large prime factors. We compare against CSI-FiSh, CSI-Otter, and Tanuki; a tightly secure blind signature from this proof of knowledge is left to future work.
ER  -

Abstract

Related

Cite