International Association
for Cryptologic Research

The ARX structure plays a crucial role in symmetric-key primitives, with differential-linear (DL) attacks being among the most effective cryptanalysis techniques against ARX ciphers. In this paper, we present a systematic re-decomposition technique for DL distinguishers of ARX ciphers and identify for the first time the hourglass(-like) structural commonalities among optimal DL distinguishers searched out by various deduction techniques, also supported through comprehensive experiments, which motivate us to develop an efficient and generalized approach to construct optimal hourglass(-like) structural DL distinguishers. Our method yields significant advances when applied to \speck, \alzette, and the underlying permutations of \siphash{} and \chaskey: (1) the first 11- to 14-round DL distinguishers of \alzette; (2) the first (valid) DL distinguishers for 11-round \speck32, 12-round \speck48, and 16-round \speck96; (3) deterministic (correlation $\pm1$) 3-round DL distinguishers for \siphash-2-4 and significantly improved 4-round ones. All these distinguishers are equipped with both theoretical and experimental verifications. We further analyze ARX-based Latin dance stream ciphers, achieving improved DL distinguishers for 7/7.25-round \chacha, 8-round \salsa, and 5.5-round \forro. Though some of the improvements are not significant, we have verified the effectiveness of our method across a broader range of instances. This work provides new insights for DL distinguisher construction and enhances understanding of the security of ARX ciphers.

We present Trout (Two-ROUnd Threshold), the \textit{first} distributed two-round ECDSA signing protocol for arbitrary thresholds. Trout has constant upload bandwidth per-party and processing time linear in the amount of participants. Moreover, Trout achieves the Identifiable Abort (IA) property, which means that if the protocol cannot terminate due to a failure, parties can attribute the failure to a specific party. We achieve this without a trusted setup.

Our protocol relies on linear-homomorphic encryptions and commitments over class groups. To obtain our result, we leverage the recent construction of an exponent-VRF (Boneh et al., Eurocrypt 2025) and a novel protocol to multiply an encrypted value with a committed value and simultaneously decrypt it, which we call "scaled decryption". We believe that this protocol may be of independent interest.

Our protocol has a very low communication cost of just 6.5 KB sent per party. Furthermore, we implemented our protocol in Rust and provide benchmarks for various configurations, showing its practicality even for 100 parties. Our implementation includes a constant-time variant which, to the best of our knowledge, is the first of its kind for class-group-based threshold ECDSA protocols.

Threshold public-key encryption (TPKE) allows $t$ out of $k$ parties to jointly decrypt, but any $t-1$ subset obtains no information on the underlying plaintext. The ongoing standardisation efforts on threshold primitives by NIST make it a pressing question to understand TPKE security notions, which, perhaps surprisingly, have remained varied.

We systematically develop what we view as minimal security properties for TPKE, formalise these into indistinguishability-based and simulation-based security notions, and establish implications and separations between different variants. One of our insights is that the common belief of maximal corruption implying the same security notion under fewer corruption is generally false, and the importance of partial decryptions on challenge ciphertexts is often neglected. Concretely, we design a (contrived) scheme which is CCA-simulation-secure under maximal corruptions, but not IND-CPA-secure under arbitrary corruptions. Our scheme is so that a random, initially hidden subset of $t-1$ parties can jointly decrypt and thus trivially insecure, but which can still be proven secure when partial decryption queries are disallowed.

To show that our security notions are achievable, we prove that threshold ElGamal (Desmedt-Frankel, 1989) achieves simulation-CPA-security under DDH, borrowing techniques from a concurrent work. We also revisit CPA-to-CCA transforms in the style of Naor and Yung (NY) and discover that, generically, NY does not upgrade CPA to CCA security for TPKE. We provide two alternatives: (1) We propose and construct a novel building block called non-interactive proofs of randomness (NIPoR) in the random oracle model, and show that NIPoR allows a generic CPA-to-CCA transform. (2) We show that assuming the stronger semi-malicious CPA security, NY-style techniques suffice to upgrade to CCA security.

Quantum cryptanalysis of block ciphers with Grover’s search requires synthesis of round function, where the non-linear S-boxes dominate the circuit cost. Efficient quantum implementations of these S-boxes are a bottleneck for cryptanalysis. In this work, we address this problem and present new generic strategy for synthesis of quantum circuit for large S-boxes that reduces the NISQ-era transpiled depth after decomposition into the hardware-oriented universal basis gate set u+cx. We introduce two-phase MILP-based, ancilla-aware synthesis framework for large S-boxes. Phase 1 determines which monomials will be synthesised globally, and how they are reused across outputs. This reduces redundancy and avoids high-degree terms that would lead to deep ladders. Phase 2 arranges the selected monomials into parallel layers. Here the solver explicitly accounts for ancilla usage, balancing the trade-off between fewer layers (smaller depth) and larger ancilla. MILP based synthesis show decisive, multi-fold reductions in transpiled depth in universal basis gate set u+cx. For SKINNY and ZUC S0 S-boxes, our synthesis reduces transpiled depth by factors of 18 and 9, respectively, with ancilla usage raised only to 10 and 13 qubits. For higher-degree S-boxes such as AES, SM4, and ZUC S1, we achieve 5 times reduction in transpiled depth by trading additional ancillas, increasing the budget from 5 to 22. To our knowledge, this is the first demonstration of ancilla-aware, globally optimised synthesis of 8-bit cryptographic S-boxes. By aligning primitive synthesis with transpiled cost, our method establishes a new baseline for depth-optimised resource estimation in the quantum cryptanalysis of symmetric primitives.

Incrementally verifiable computation (IVC) is a powerful cryptographic primitive, particularly suited for proving long-running machine computations. Previous work shows that IVC can be constructed by recursively composing SNARKs. Unfortunately, theoretical challenges limit the provable security of known IVC constructions. Recursive composition may quickly lead to a blowup in extraction time and may require arithmetic circuits to enforce constraints about random oracle calls. Furthermore, composition presents a practical challenge: proofs are often expressed in a form that is not friendly to the arithmetic circuits that produce them.

To mitigate the theoretical challenges, we present the Open-and-Sign Random Oracle Model (osROM) as an extension to the signed random oracle of Chiesa and Tromer (ICS '10). This model, while strictly harder to instantiate than the Random Oracle Model, allows the design of protocols that can efficiently verify calls to the oracle and support straight-line extractors. As a result, IVC constructions in the osROM can be shown to have provable security for polynomial depths of computation.

Under our new model, we construct a framework to build secure IVC schemes from simple non-interactive reductions of knowledge. Our construction natively supports cycles of elliptic curves in the style of Ben-Sasson et al. (CRYPTO '14), thus answering the practical challenge outlined above. Finally, we analyze the HyperNova (CRYPTO '24) IVC scheme in the osROM and show that it is secure over a two-cycle of elliptic curves, for polynomial depths of computation.

Distributed systems require robust, transparent mechanisms for verifiable temporal ordering to operate without trusted authorities or synchronized clocks. This paper introduces Affine One-Wayness (AOW), a new cryptographic primitive for post-quantum temporal verification based on iterative polynomial evaluation over finite fields. AOW provides strong temporal binding guarantees by reducing its security with a tight reduction to the hardness of the dis crete logarithm problem in high-genus hyperelliptic curves (HCDLP) and with a reduction to the Affine Iterated Inversion Problem (AIIP), which possesses dual foundations in multivariate quadratic algebra and the arithmetic of high-genus hyperelliptic curves. We present a con struction with transparent setup and prove formal security against both classical and quantum adversaries. Furthermore, we demonstrate efficient integration with STARK proof systems for zero-knowledge verification of sequential computation with logarithmic scaling. As the core reliability component of the Chaotic Affine Secure Hash (CASH) framework, AOW enables practical applications in Byzantine-resistant event ordering and distributed synchronization with provable security guarantees under standard cryptographic assumptions.