Metraipolis › archive › dc_cfe705dda0a1

CRT-Decomposed $Σ$-Protocols for CSIDH — arXiv:2609.26258

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.26258
License (as archived)
CC0-1.0
Archived
2026-10-08T14:42:09.302Z
SHA-256 of the archived text
1e13c7914dfafc2b3a80518eff858bcdec5d4648bc0c58e8c7eea7425fc7599f
Stable URL of this page
https://metraipolis.com/documento/dc_cfe705dda0a1

How to cite

CRT-Decomposed $Σ$-Protocols for CSIDH — arXiv:2609.26258 — arXiv (en), https://arxiv.org/abs/2609.26258 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cfe705dda0a1 (Metraipolis archive dc_cfe705dda0a1, sha256 1e13c7914dfafc2b3a80518eff858bcdec5d4648bc0c58e8c7eea7425fc7599f)
BibTeX
@misc{dccfe705dda0a1,
  title = {CRT-Decomposed $Σ$-Protocols for CSIDH — arXiv:2609.26258},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.26258},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cfe705dda0a1; sha256 1e13c7914dfafc2b3a80518eff858bcdec5d4648bc0c58e8c7eea7425fc7599f},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.26258. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\sqrt{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.

Tema degli esploratori: fiducia digitale e crittografia (retro-catalogo arXiv: annunci del 2026-09-23 in cs.CR).
Categorie arXiv: Cryptography and Security (cs.CR) ; Information Theory (cs.IT); Quantum Physics (quant-ph).
Pagina del lavoro: https://arxiv.org/abs/2609.26258 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T13:55:11.750Z dalla pagina https://arxiv.org/catchup/cs.CR/2026-09-23?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).