Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.26258

CRT-Decomposed ΣΣΣ-Protocols for CSIDH

I. Dey, I. Cherkaoui

cs.CRcs.ITquant-phSubmitted Aug 13, 2026• Announced Aug 14, 2026
arXivHTMLPDF

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^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.

Related papers

A New CRT-based Fully Homomorphic Encryption

Anil Kumar Pradhan, Abhraneel Dutta, Hansraj Jangir +1 more

The idea of computing on encrypted data without decryption dates back to the notion of privacy homomorphisms introduced by Rivest, Adleman, and Dertouzos (1978). Their proposals built using the elegant structure of Chinese Remainder Theorem (CRT), were later shown to be insecure under simple known-plaintext attacks. Subsequent CRT-based fully homomorphic encryption (FHE) over the integers addresses this algebraic transparency by injecting noise and basing security on approximate common divisor–type assumptions, but the resulting designs are burdened by large public keys and costly ciphertext refresh procedures. In this work, we develop a new CRT-based FHE scheme whose security relies on the Ring-LWE (RLWE) hardness assumption. For this purpose, we introduce the CRT-RLWE problem. We show that the problem is at least as hard as the RLWE, thereby positioning our construction within the established post-quantum security landscape of RLWE-based cryptography. Our scheme retains an explicit CRT embedding, separating a message component modulo a prime-power plaintext modulus and an auxiliary CRT component, while using RLWE-style key and ring arithmetic for compactness and efficiency. Finally, we make it fully homomorphic by using a new bootstrapping procedure, that adopts the recryption paradigm for BGV/BFV schemes utilizing the linear transformation and digit extraction techniques.

IACR Communications in Cryptology•Aug 3, 2026•1 citation

Module Lattice Security (Part II): Module Lattice Reduction via Optimal Sign Selection

Ming-Xing Luo

We extend the CDPR's quantum attack from ideal lattices to module lattices over $2^k$-th cyclotomic rings. Using trace orthogonality of the power basis, we decompose a rank-$d$ module into mutually orthogonal rank-$1$ submodules, and apply CDPR's analysis to each independently and return the shortest candidate. The Hermite factor $\exp(\tilde{O}(\sqrt{n}))$ matches the ideal case, with a module reduction factor $α_d=O(1)$ independent of the rank, under a balance hypothesis (proved for Gaussian distribution) automatic for MLWE-distributed bases. To enable a bounded-precision implementation, we replace coordinate-wise rounding with Chinese Remainder Theorem-scaled rounding at totally split primes, reducing the Gram-Schmidt rounding radius from $n/2$ to $\le 1$ at cost $O(d^2 r n \log n)$. Finally, we reformulate the CDPR's sign-selection step as a mixed-integer linear program and prove its optimum is no more than 1/2 for all $k$ ($\approx 0.4407$ for all tested $k\le 12$, conjecturally universal). This replaces the previous heuristic discrepancy $Θ(\sqrt{nk})$. All results build on the class number condition $h_k^+=1$ established in Part I of this series.

cs.CRCross-listedarXiv:2604.22900•Apr 27, 2026•0 citations

Tanuki: New Frameworks for (Concurrently Secure) Blind Signatures from Post-Quantum Groups Actions.

Lucjan Hanzlik, Yi-Fu Lai, Marzio Mula +3 more

Blind signatures are fundamental cryptographic primitives enabling privacy-preserving authentication and have seen renewed interest in the post-quantum literature. Existing efficient constructions predominantly rely on Fischlin’s generic paradigm instantiated over lattice assumptions, while blinding techniques for Σ-protocol-based blind signatures remain sparse beyond lattices. Moreover, achieving provable concurrent security under polynomially many sessions has been a longstanding open challenge for this approach in the post-quantum literature as evidenced by the recent attacks in EC’24 and PKC’24. This work broadens the landscape of post-quantum blind signatures by introducing novel techniques and proposing four frameworks based on general cryptographic group actions, without requiring commutativity. Our constructions admit instantiations under diverse post-quantum assumptions, including CSIDH (isogeny-based), LESS (code-based, NIST round-two), and more. These frameworks offer flexible trade-offs in assumptions (from interactive one-more to the standard inversion problem) and key/signature sizes, and culminate in a construction that achieves security under polynomially many concurrent sessions. This enables the first efficient blind signatures from isogenies and codes with provable concurrent security with 4.5 and 64.7 KB respectively. We also outline several directions for optimization and further instantiations for future work.

•Jan 1, 2025•0 citations

Modular Construction and Analysis of Multi-Round Straightline Extractability Compilers

Jannis Wunderlich

This thesis investigates the feasibility of a generic, modular compiler that treats an existing three-move straight-line extractability compiler as a black-box building block and extends it to multi-round public-coin protocols. We introduce a recursive compiler that compresses an interactive multi-round protocol layer by layer and analyze how its security and efficiency properties propagate through this recursion. The analysis demonstrates that while the framework successfully preserves completeness, zero knowledge, and knowledge soundness, the modularity incurs a substantial cost. The repetition parameters required at each recursive level cause an exponential blowup in both runtime and communication complexity, restricting the compiler’s efficiency to protocols with a strictly constant number of rounds. Furthermore, preserving the zero-knowledge property requires the input protocol to satisfy 2-Stage special Honest Verifier Zero-Knowledge, a stronger form of special Honest-Verifier Zero-Knowledge introduced in this work. Ultimately, this thesis provides a clean theoretical framework for modular straight-line extractability, but exposes the asymptotic performance gap between our flexible black-box construction and specialized monolithic transformations.

•Jul 28, 2026•0 citations

Adaptively UC-Secure Oblivious Transfer from Group Actions

Olivier Blazy, Céline Chevalier, Saqib A. Kakvi +1 more

Oblivious Transfer (OT) is a fundamental building block for secure computation, in which a sender holds two messages and a receiver learns exactly one of them, without revealing which one was chosen and without learning the other. While generic constructions for Universally Composable (UC) OT exist, instantiating them from post-quantum assumptions remains challenging, particularly under adaptive corruption. In this work, we present the first adaptively UC-secure OT protocol based on Group Actions, specifically assuming weakly pseudorandom Effective Group Actions (EGA) like CSIDH. We adhere to the framework of [BC15], which derives an adaptively UC-secure OT protocol from SPHF-friendly extractable and equivocable ( ⋿ 2 ) commitment schemes. The central challenge in instantiating this construction from group actions is the lack of SPHF-friendly IND-CCA encryption. Classical CCA transformations such as Fujisaki-Okamoto destroy the algebraic structure required for building SPHFs over ciphertexts, while known group action-based schemes offer no native mechanism to prove ciphertext validity. To overcome this obstacle, we construct from group actions an IND-CCA encryption scheme with enough algebraic structure to efficiently recognize valid ciphertexts. Our contributions are threefold: (1) a verifiable chameleon hash function with perfect soundness in the standard model, (2) an SPHF-friendly, publicly verifiable IND-CCA encryption scheme in the random oracle model, and (3) we combine these to build an SPHF-friendly ⋿ 2 commitment scheme and derive a fully adaptively secure OT protocol in the UC framework. This is the first construction of its kind under group action assumptions, enabling post-quantum secure OT with adaptive security guarantees. These building blocks may also be of independent interest e.g., to obtain digital signatures, non-malleable commitment schemes, or verifiable encryption.

IACR Communications in Cryptology•Oct 26, 2026•0 citations

Classical Verification of Quantum Computation Beyond the Polynomial Hierarchy

Atul Mantri

It is not known whether a classical polynomial-time verifier can verify arbitrary polynomial-time quantum computations with an efficient quantum honest prover without computational assumptions. We show that, relative to a classical oracle, such verification is possible for a language beyond the polynomial hierarchy that is decided exactly in quantum polynomial time. The protocol is public-coin, with perfect completeness and soundness error at most 1/4. To our knowledge, no language with such a proof system was previously proved to lie outside AM relative to an oracle. For every unbounded polynomial-time computable function, the oracle can be chosen so that the message count and the oracle query counts of the quantum algorithm, verifier, and honest prover are bounded by this function of the input length. The message count is optimal up to a constant factor, since for a suitable oracle every interactive proof system for the language uses at least a constant fraction of the messages of our protocol on infinitely many lengths, with a constant depending on its verifier. The language is a variant of recursive Fourier sampling in which code tables encode secrets that address data tables. The tables are evaluated recursively, and the oracle stores only the leaves. The quantum algorithm recovers every secret exactly, and the verifier checks the prover's secrets recursively against random code entries. The recursion restricts the input in a correlated way, as the same secret fixes the code bits and chooses the free coordinate, so Håstad's switching lemma does not apply. We prove a switching theorem for these restrictions, which may be of independent interest. For instances of sufficient height, no constant-depth circuit of size $2^{\mathrm{poly}(n)}$ changes its output with probability above $2^{-Ω(n)}$ when the answer of a random instance is flipped by changing a single leaf.

quant-pharXiv:2610.37635•Oct 28, 2026•2 citations
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 (10410^4104 random instances, all passing), and report protocol-level simulations in the exponent model: Monte Carlo soundness rates matching the proven 2−t2^{-t}2−t bound within 95% confidence at every tested ttt, 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\sqrt{q}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 2128.62^{128.6}2128.6 to about 267.32^{67.3}267.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.
The idea of computing on encrypted data without decryption dates back to the notion of privacy homomorphisms introduced by Rivest, Adleman, and Dertouzos (1978). Their proposals built using the elegant structure of Chinese Remainder Theorem (CRT), were later shown to be insecure under simple known-plaintext attacks. Subsequent CRT-based fully homomorphic encryption (FHE) over the integers addresses this algebraic transparency by injecting noise and basing security on approximate common divisor–type assumptions, but the resulting designs are burdened by large public keys and costly ciphertext refresh procedures. In this work, we develop a new CRT-based FHE scheme whose security relies on the Ring-LWE (RLWE) hardness assumption. For this purpose, we introduce the CRT-RLWE problem. We show that the problem is at least as hard as the RLWE, thereby positioning our construction within the established post-quantum security landscape of RLWE-based cryptography. Our scheme retains an explicit CRT embedding, separating a message component modulo a prime-power plaintext modulus and an auxiliary CRT component, while using RLWE-style key and ring arithmetic for compactness and efficiency. Finally, we make it fully homomorphic by using a new bootstrapping procedure, that adopts the recryption paradigm for BGV/BFV schemes utilizing the linear transformation and digit extraction techniques.
We extend the CDPR's quantum attack from ideal lattices to module lattices over 2k2^k2k-th cyclotomic rings. Using trace orthogonality of the power basis, we decompose a rank-ddd module into mutually orthogonal rank-111 submodules, and apply CDPR's analysis to each independently and return the shortest candidate. The Hermite factor exp⁡(O~(n))\exp(\tilde{O}(\sqrt{n}))exp(O~(n​)) matches the ideal case, with a module reduction factor αd=O(1)α_d=O(1)αd​=O(1) independent of the rank, under a balance hypothesis (proved for Gaussian distribution) automatic for MLWE-distributed bases. To enable a bounded-precision implementation, we replace coordinate-wise rounding with Chinese Remainder Theorem-scaled rounding at totally split primes, reducing the Gram-Schmidt rounding radius from n/2n/2n/2 to ≤1\le 1≤1 at cost O(d2rnlog⁡n)O(d^2 r n \log n)O(d2rnlogn). Finally, we reformulate the CDPR's sign-selection step as a mixed-integer linear program and prove its optimum is no more than 1/2 for all kkk (≈0.4407\approx 0.4407≈0.4407 for all tested k≤12k\le 12k≤12, conjecturally universal). This replaces the previous heuristic discrepancy Θ(nk)Θ(\sqrt{nk})Θ(nk​). All results build on the class number condition hk+=1h_k^+=1hk+​=1 established in Part I of this series.
Blind signatures are fundamental cryptographic primitives enabling privacy-preserving authentication and have seen renewed interest in the post-quantum literature. Existing efficient constructions predominantly rely on Fischlin’s generic paradigm instantiated over lattice assumptions, while blinding techniques for Σ-protocol-based blind signatures remain sparse beyond lattices. Moreover, achieving provable concurrent security under polynomially many sessions has been a longstanding open challenge for this approach in the post-quantum literature as evidenced by the recent attacks in EC’24 and PKC’24. This work broadens the landscape of post-quantum blind signatures by introducing novel techniques and proposing four frameworks based on general cryptographic group actions, without requiring commutativity. Our constructions admit instantiations under diverse post-quantum assumptions, including CSIDH (isogeny-based), LESS (code-based, NIST round-two), and more. These frameworks offer flexible trade-offs in assumptions (from interactive one-more to the standard inversion problem) and key/signature sizes, and culminate in a construction that achieves security under polynomially many concurrent sessions. This enables the first efficient blind signatures from isogenies and codes with provable concurrent security with 4.5 and 64.7 KB respectively. We also outline several directions for optimization and further instantiations for future work.
This thesis investigates the feasibility of a generic, modular compiler that treats an existing three-move straight-line extractability compiler as a black-box building block and extends it to multi-round public-coin protocols. We introduce a recursive compiler that compresses an interactive multi-round protocol layer by layer and analyze how its security and efficiency properties propagate through this recursion. The analysis demonstrates that while the framework successfully preserves completeness, zero knowledge, and knowledge soundness, the modularity incurs a substantial cost. The repetition parameters required at each recursive level cause an exponential blowup in both runtime and communication complexity, restricting the compiler’s efficiency to protocols with a strictly constant number of rounds. Furthermore, preserving the zero-knowledge property requires the input protocol to satisfy 2-Stage special Honest Verifier Zero-Knowledge, a stronger form of special Honest-Verifier Zero-Knowledge introduced in this work. Ultimately, this thesis provides a clean theoretical framework for modular straight-line extractability, but exposes the asymptotic performance gap between our flexible black-box construction and specialized monolithic transformations.
Oblivious Transfer (OT) is a fundamental building block for secure computation, in which a sender holds two messages and a receiver learns exactly one of them, without revealing which one was chosen and without learning the other. While generic constructions for Universally Composable (UC) OT exist, instantiating them from post-quantum assumptions remains challenging, particularly under adaptive corruption. In this work, we present the first adaptively UC-secure OT protocol based on Group Actions, specifically assuming weakly pseudorandom Effective Group Actions (EGA) like CSIDH. We adhere to the framework of [BC15], which derives an adaptively UC-secure OT protocol from SPHF-friendly extractable and equivocable ( ⋿ 2 ) commitment schemes. The central challenge in instantiating this construction from group actions is the lack of SPHF-friendly IND-CCA encryption. Classical CCA transformations such as Fujisaki-Okamoto destroy the algebraic structure required for building SPHFs over ciphertexts, while known group action-based schemes offer no native mechanism to prove ciphertext validity. To overcome this obstacle, we construct from group actions an IND-CCA encryption scheme with enough algebraic structure to efficiently recognize valid ciphertexts. Our contributions are threefold: (1) a verifiable chameleon hash function with perfect soundness in the standard model, (2) an SPHF-friendly, publicly verifiable IND-CCA encryption scheme in the random oracle model, and (3) we combine these to build an SPHF-friendly ⋿ 2 commitment scheme and derive a fully adaptively secure OT protocol in the UC framework. This is the first construction of its kind under group action assumptions, enabling post-quantum secure OT with adaptive security guarantees. These building blocks may also be of independent interest e.g., to obtain digital signatures, non-malleable commitment schemes, or verifiable encryption.
It is not known whether a classical polynomial-time verifier can verify arbitrary polynomial-time quantum computations with an efficient quantum honest prover without computational assumptions. We show that, relative to a classical oracle, such verification is possible for a language beyond the polynomial hierarchy that is decided exactly in quantum polynomial time. The protocol is public-coin, with perfect completeness and soundness error at most 1/4. To our knowledge, no language with such a proof system was previously proved to lie outside AM relative to an oracle. For every unbounded polynomial-time computable function, the oracle can be chosen so that the message count and the oracle query counts of the quantum algorithm, verifier, and honest prover are bounded by this function of the input length. The message count is optimal up to a constant factor, since for a suitable oracle every interactive proof system for the language uses at least a constant fraction of the messages of our protocol on infinitely many lengths, with a constant depending on its verifier. The language is a variant of recursive Fourier sampling in which code tables encode secrets that address data tables. The tables are evaluated recursively, and the oracle stores only the leaves. The quantum algorithm recovers every secret exactly, and the verifier checks the prover's secrets recursively against random code entries. The recursion restricts the input in a correlated way, as the same secret fixes the code bits and chooses the free coordinate, so Håstad's switching lemma does not apply. We prove a switching theorem for these restrictions, which may be of independent interest. For instances of sufficient height, no constant-depth circuit of size 2poly(n)2^{\mathrm{poly}(n)}2poly(n) changes its output with probability above 2−Ω(n)2^{-Ω(n)}2−Ω(n) when the answer of a random instance is flipped by changing a single leaf.