International Association
for Cryptologic Research

We study auctions where two positions are sold to unit-demand bidders with private heterogeneous order preferences: some are specialists who value only the first position, while others are generalists indifferent between the two. First, we consider a first-price rule which allocates the first and second items to the highest and second-highest bidders, respectively. We show that no strategy profile ex-post implements the efficient allocation at every type profile, irrespective of payments, and provide a distribution-free equilibrium welfare guarantee of 1/2. To augment this result, we prove that for deterministic one-round auctions and discrete bids, the efficient allocation requires each bidder to communicate at least one bit more than its bid's binary representation. We next ask what the same bit accomplishes in winner-pays-bid formats where bidders can also specify specific item preferences. In particular, we show that this strengthens our distribution-free equilibrium welfare guarantee to 1-1/e. Finally, we discuss the applicability to priority service and blockchain transaction ordering.

Poseidon is an algebraic permutation designed for efficient use in proof systems. Its nonlinear layer consists of power-map S-boxes. In a full round, the S-box is applied to every state coordinate; in a partial round, it is applied to only one coordinate, reducing the arithmetization cost. Each round also applies an MDS linear layer to diffuse information across the state.

To study algebraic degree, we let the input depend on variables and follow the resulting family of states through the permutation. If the coordinate entering a partial-round S-box is constant across that family, the S-box adds no degree in the family variables. Directions with this property over several consecutive partial rounds form finite subspace trails. Such trails exist for every linear layer, but their existence does not by itself explain how a constrained family can pass through the preceding full rounds and enter them without first acquiring high degree.

We address this reachability problem by constructing a constrained input family and a round-constant-dependent MDS matrix together. The prescribed matrix images carry the family through the four initial full rounds and into a chosen finite trail. After an explicit change of variable, the state at the end of the full-round prefix is linear in the new root variable, so the prefix acts as a controlled reparametrization rather than as a source of degree growth. We call this effect \emph{full-round absorption}.

For the KoalaBear instance \((t,\alpha,R_F,R_P)=(16,3,8,20)\), we construct a two-parameter family whose first two input coordinates are zero. On this family, the four initial full rounds act as a reparametrization and deliver the variable directions into a two-dimensional trail, so those four rounds and the next fourteen partial S-boxes add no degree. For the exhibited control, the polynomials representing the first two output coordinates have exact degree \(3^{R_F+R_P-4-14}=3^{10}\), rather than the expected degree \(3^{R_F+R_P}=3^{28}\). We exhibit a common base-field root, yielding a complete CICO-2 solution for the full-round Poseidon instance.

The resulting matrices are MDS and satisfy the relevant matrix checks prescribed by the Poseidon designers, yet they make a finite trail reachable through the full-round prefix. We generalize the construction to CICO-\(k\), derive the corresponding trail-dimension and matrix-image bounds, and provide a concrete MDS matrix that meets the CICO-3 matrix-image bound with equality.

Large language model (LLM) is increasingly deployed as a remote service, where users rely on third-party servers to perform computation. However, such settings introduce critical integrity concerns, as an untrusted server may deviate from the prescribed computation, skip expensive operations, or return incorrect results, while users lack practical approaches to verify execution correctness. Ensuring the correctness of LLM inference under untrusted execution remains a fundamental challenge. Zero-knowledge proofs (ZKPs) provide a principled approach verifying computation correctness, but applying them to LLM inference remains challenging. Modern LLMs involve a large number of non-linear operations and require modeling real-valued computation in finite fields, introducing substantial computational and memory overhead and potential loss of numerical precision. Moreover, the large scale of LLMs makes end-to-end verification difficult to scale, limiting the practicality of existing approaches.

This paper presents OpenLLM, an efficient and modular system for verifiable LLM inference. Our key idea is to decompose large-scale LLM inference into a set of reusable atomic operators, each equipped with efficient ZKP protocols, enabling scalable verification at the operator level. Based on this abstraction, we design succinct non-interactive zero-knowledge proof constructions for representative non-linear functions, which can be composed into end-to-end inference pipelines independent of model architectures.

We further evaluate OpenLLM across operator-level performance, end-to-end inference, layer-wise scaling, larger models, and approximation accuracy. The results show that OpenLLM achieves smaller proof sizes, lower verification cost, and improved numerical fidelity while scaling from individual operators to full-model inference. Compared with state-of-the-art interactive protocols, OpenLLM eliminates communication overhead through a fully non-interactive design while maintaining competitive efficiency. Building on this operator-level efficiency, it further enables a scalable and modular framework for end-to-end verifiable LLM inference, outperforming prior end-to-end approaches.

Relying solely on encryption for privacy-preserving computations is prone to leakage-abuse/access-pattern attacks. TEEs, while cost-effective, are also vulnerable to side-channel attacks. Oblivious primitives, such as oblivious memory (ORAM) and data structures (ODS), are effective building blocks to mitigate these risks by concealing memory access patterns and side-channel information. Applications range from private contact discovery (Signal) to anonymous key transparency, encrypted email search, encrypted/oblivious databases, anonymous communication (Sparta/SP'25), private federated learning, LLM privacy (Compass/OSDI'25), and broader confidential computing efforts.

Tree-based ORAMs (EnigMap (USENIX'23), GraphOS (PVLDB'23), Oblix (SP'18)) offer low latency but limited parallelism. Partition-based solutions like Snoopy (SOSP'21) shard data across subORAMs (which build oblivious hashtables on incoming requests, then linearly scan them), achieving high throughput by trading off latency, theoretically enabling linear scalability. In practice, Snoopy’s performance hinges on how quickly each subORAM can build the oblivious hashtable and complete its linear scan before exceeding latency targets, constraining server utilization and throughput. While supporting a TB-scale dataset with Snoopy is theoretically feasible, we estimate it would require 1000+ servers.

In this work, we reconcile the fractured landscape between low-latency and high-throughput ORAM designs. We introduce SONIC: the first parallel/concurrent doubly-oblivious tree-based ORAM for TEEs. SONIC achieves 156K-3.3M req/s with a single server, tackling the core challenges of all tree-ORAM constructions: overcoming the sequential eviction bottleneck, enabling efficient batch evictions, and providing lock-free access/reshuffle/stash operations. SONIC achieves throughput 29-104$\times$ higher than EnigMap, and 158-560$\times$ higher than GraphOS, with lower latency. In the distributed, high-throughput setting, our SONIC-powered OMAP PMChain can replace Snoopy's subORAM, supporting higher throughput and $64\times$ larger datasets using the same hardware (reducing Snoopy's server requirements).

Background: The migration to post-quantum cryptography confronts resource-constrained Internet of Things (IoT) devices with a material performance cost. CRYSTALS-Dilithium, standardised as the Module-Lattice-Based Digital Signature Algorithm (ML-DSA) in FIPS 204, fixes the Keccak-based SHAKE functions as its only symmetric primitives, and profiling on embedded platforms identifies hashing as the largest single contributor to the scheme’s software cost. This review synthesises the performance evidence for ML-DSA on constrained platforms, classifies the optimisation strategies pursued in the literature, and tests whether any published work substitutes a standardised lightweight extendable-output function for SHAKE within the scheme. Methods: Following Kitchenham’s guidelines and the PRISMA 2020 statement, we searched IEEE Xplore, the ACM Digital Library, Scopus, and SpringerLink for peer-reviewed studies published from January 2020 onwards, complemented by backward and forward snowballing and by targeted update searches through July 2026. A protocol was prepared in advance of the search. From 115 database records and 22 records identified through other methods, 40 primary studies met the inclusion criteria. Results: On the ARM Cortex-M4, optimised software implementations of Dilithium3 require 10,667 kilocycles on average for signing and 2,321 kilocycles for verification; on the Cortex-M7, Dilithium-2 verification averages 1,429 kilocycles (6.6ms at 216MHz), with signing spanning 1,835 to 16,440 kilocycles due to rejection sampling. Optimisation efforts fall into four categories: hardware acceleration, platform-specific software optimisation, protocol-level adaptation, and optimisation of the incumbent Keccak primitive itself. Architecture-specific Keccak optimisation reduces hashing’s share of Dilithium’s runtime on the Cortex-M4 by only 2.46 to 5.03 percentage points, indicating that the bottleneck largely survives direct attack. Replacing Keccak with Ascon inside the sibling scheme Kyber yields a 24 to 25% cycle reduction and a 2 to 8% memory reduction on the Cortex-M4. No peer-reviewed study applies this substitution to ML-DSA. Conclusions: With FIPS 204 and NIST SP 800-232 both final, the cost of ML-DSA’s primitive choice on constrained platforms is a well-posed and unanswered question on both sides. We specify a per-call-site Dilithium–Ascon evaluation, including its security constraints and non conformance status, as the priority direction for software-only optimisation of post-quantum signatures on IoT devices. Keywords: post-quantum cryptography; ML-DSA; CRYSTALS-Dilithium; Ascon; lightweight cryptography; Internet of Things; systematic literature review

This note presents a new unconditional attack on the supersingular isogeny problem, with time and memory complexity $p^{2/5+o(1)}$. It builds on the approach by Eisenträger-Hallgren-Leonardi-Morrison-Park (2020) and Fuselier-Iezzi-Kozek-Morrison-Namoijam (2025), and is related to the recent heuristic attack with complexity $p^{1/3+o(1)}$ by Wesolowski (ePrint 2026/1486): all of these search for a separable isogeny from a curve to its Galois conjugate to form a non-scalar endomorphism.

Our attack is based on highly theoretical multivariate multipoint evaluation algorithms from Kedlaya-Umans (2008, 2011), Bhargava-Ghosh-Guo-Kumar-Umans (2022), and Ghosh-Harsha-Herdade-Kumar-Saptharishi (2023), and therefore does not threaten isogeny cryptosystems in practice; it is of theoretical interest.

Multi-signatures with key aggregation provide compact signatures verifiable under a single aggregated public key, but protect signer privacy only when public keys are used in a one-time manner. To address this limitation, recent privacy-preserving constructions provide stronger privacy guarantees under public-key reuse. However, they only guarantee privacy in the signature-only setting, where adversaries observe only the final aggregated public key and signature. In practical deployments, multi-signature protocols may be executed over public channels, where externally visible signing transcripts are exposed. These transcripts may link signing messages to public keys, thereby leaking signer identities and undermining existing privacy guarantees. In this paper, we formalize this gap by introducing transcript-aware privacy, a new framework that captures signer privacy in the presence of transcript exposure. Within this framework, we identify the strongest achievable privacy notion, in which signer identities remain hidden while the size of the signer set may be revealed. Our formulation departs from prior signature-only privacy models by explicitly modeling adversarial access to signing transcripts and allowing only inherent leakage such as the signer-set size. We present a new construction based on the MuSig2-H scheme of Tessaro and Zhu (EUROCRYPT'23). Our scheme achieves UNF-3 unforgeability in the AGM+ROM under the DL assumption and preserves full privacy in the signature-only setting. In the transcript-aware setting, it achieves weak set privacy in the ROM under the DDH assumption. In addition, we provide a concrete realization of the key-aggregation proof sharing procedure over public channels, eliminating the need for secure channels and improving practical deployability.

Since McEliece introduced the first code-based encryption scheme in 1978, most code-based cryptographic constructions have relied on hard problems related to decoding random linear codes (or variants thereof) or code equivalence. More recently, the use of the MPC-in-the-Head paradigm has enabled the construction of a new class of very competitive digital signature schemes relying on such assumptions, including the NIST submissions Mirath, PERK, RYDE, and SDitH, as well as a recent proposal based on the so-called Subfield Bilinear Collision problem by Huth and Joux (Crypto 2024).

In this work, we enrich the portfolio of code-based MPC-in-the-Head signature schemes by introducing a new hard problem to cryptography, referred to as the Non-Intersecting Codewords (NIC) problem. In this problem, one has to find two codewords of a given linear code such that their supports in the Hamming metric do not intersect. After discussing how to generate hard instances and studying several attacks on it, we show that the NIC problem can be used to construct a competitive MPC-in-the-Head signature scheme. Using generic constructions, we obtain smaller signature sizes than SDitH and PERK, attaining a signature size of 2~934~Bytes for NIST security level I.

Inspired by the concept of harmony, this work composes SHA-2 and SHA-3 into a unified hardware architecture, bringing them together as a single, efficient cryptographic ensemble. This need is driven in particular by Post-Quantum Cryptography (PQC), where different standardized schemes rely on either SHA-2 or SHA-3/SHAKE primitives. Rather than enforcing strict round-level unification, the proposed design applies selective sharing across the most area-critical components, including a shared 25 x 64-bit register bank, shared round-constant storage, and unified padding and control logic. A unified datapath organization reinterprets the same hardware as either a SHA-2 scheduler/compression engine or a KECCAK absorb/permutation state, while maintaining full compliance with FIPS 180-4 and FIPS 202. In addition, we introduce a duet execution mode that enables parallel processing of two independent SHA-224/256 streams by exploiting the otherwise underutilized upper half of the 64-bit datapath. This capability is particularly advantageous for Merkle-tree-based constructions in hash-based PQC, where independent node hashes can be evaluated concurrently. The design is implemented and synthesized on an Artix-7 FPGA, occupying 6,591 LUTs and 2,308 FFs. Experimental results show that SHARMONY achieves a throughput of 1,656,Mbps for SHA-256, representing improvements of 89%, 72%, and 50% over the SHA-256 engines of OpenTitan, Caliptra, SPHINCSLET and SLotH , respectively. At the same time, SHARMONY reduces LUT utilization by an average of 38% and FF utilization by an average of 62% compared to combined designs constructed from separate SHA-2 and SHA-3 implementations.

Verifiable computation systems often need to prove large matrix multiplication statements, but a direct SNARK arithmetization of a \(k \times k\) product requires \(\mathcal{O}(k^3)\) constraints. Freivalds' randomized check reduces the algebraic computation to vector-matrix products, but proving those products inside a SNARK still costs \(\mathcal{O}(k^2)\) constraints.

We present $\textsf{LAMP}$, a matrix-multiplication checking protocol that combines Freivalds' randomized check with proximity testing over linear error-correcting codes. The prover commits to encoded matrices and intermediate vectors before the sampled query positions are derived. The CP-SNARK circuit then checks only the sampled codeword positions and commits to the values used inside the circuit, while Merkle openings and CP-Link proofs ensure consistency between the in-circuit witnesses and the externally committed values. We prove soundness for this committed-input setting under the soundness of the SNARK backend, the binding of the commitments, the correctness of the CP-Link checks, and the distance of the code.

For a fixed number \(t\) of sampled positions, the main in-circuit SNARK relation has \(\mathcal{O}(tk)\) constraints, with additional \(\mathcal{O}(t\log n)+E_{\mathsf{link}}(k)\) backend work for Merkle openings and CP-Link checks. We implement $\textsf{LAMP}$ in Go and compare it with a Freivalds-based SNARK circuit. In the matrix benchmark at \(k=2^{12}\), $\textsf{LAMP}$ reduces the constraint count by \(30.3\times\) and shortens proof generation time by \(8.43\times\); verification stays at about \(0.06\) seconds across the measured matrix dimensions.

A party may participate in multiple threshold cryptosystems. For example, it may serve on multiple overlapping threshold committees in a proof-of-stake blockchain or a distributed oracle network, or act as a client of multiple cryptocurrency wallet services built on threshold cryptography. With conventional distributed key generation (DKG), each threshold system independently generates its key shares, imposing significant key-management overhead on such a repeating party. In contrast, modern key-management practice favors deriving all cryptographic material deterministically from a single master key, raising a fundamental question: Can DKG be reconciled with key derivation while preserving security and compatibility with legacy threshold systems?

We present Anchor-DKG, a new DKG protocol that allows up to $t^{\mathsf{rec}}$ (the reconstruction threshold) parties to deterministically fix their secret key shares while retaining standard security guarantees. Anchor-DKG supports concurrent executions with overlapping participants across multiple DKG instances and remains fully compatible with legacy threshold schemes, including ECDSA, BLS, Schnorr, and ElGamal.

At the core of Anchor DKG lies a new technique: fixed-point distributed polynomial sampling (FpDpS). FpDpS allows parties to jointly sample a random $(t^{\mathsf{rec}}-1)$-degree polynomial $f$ such that $f(i) = s_i$ at designated points $i$, where each $s_i$ can be a private input, e.g., a key derived from a master secret. The final secret key remains $f(0)$, ensuring compatibility with existing discrete-log-based threshold systems. We provide an efficient construction of Anchor DKG under standard cryptographic assumptions, which, compared to classical constructions such as Gennaro et al. (J.Cryptol. 2007), only incurs one more point-to-point round and marginal computation. Experimental results show that, for a network size of $n=128$, our protocol incurs a per-party computation cost of $1.59$ s, compared to $1.36$ s for GJKR.

We study SIMD packing for the lattice-based homomorphic secret sharing scheme of Boyle-Kohl-Scholl (BKS) over dimension-$N$ cyclotomic rings. A trace construction with alternating tensor encodings matches the $\Theta(\sqrt N)$ packing of SIMD-HSS by Kim et al. (ePrint 2026/485). Its addition-closed mode uses $O(\log N)$ authenticated automorphisms, two BKS multiplications, and two constant multiplications; an alternating fast path roughly halves these costs. A second construction uses a three-term-progression-free slot set $A$: homomorphic traces isolate the product coefficients at $2a$ for $a\in A$, and a halving automorphism returns them to $a$. For fixed $k$ and conductor primes, with balanced prime-power factors, this packs $N^{1-o(1)}$ slots with one BKS multiplication, $O(kN^{1/(2k)})$ authenticated automorphisms, and $O(kN^{1/k})$ constant multiplications. Both constructions support standard (non-entropic) secrets. Two-party executions at 162 and 495 slots confirm the algebra and exact call counts.

Trust-minimized bridges on Bitcoin move SNARK verification off chain by evaluating the verifier as a garbled circuit. The bridge's on-chain spending condition obliges the Garbler to reveal the labels for one input without enabling the Evaluator to derive labels for any other input. Existing designs commit to each input bit with a Lamport signature which is costlier on chain, or with adaptors where there is no guarantee that the spend actually reveals the labels. We present Antichain Winternitz, a parametrized hash-chain construction whose admissible codewords form a constant-sum antichain. The on-chain locking script accepts an opening witness only if it encodes a valid codeword consistent with the committed chain terminals. Every accepted opening witness yields a valid codeword while the public off-chain table, verified during setup, maps every admissible codeword to its garbled-circuit labels, so any observer can recover them. Depending on the parameter set, we can obtain up to a 52.9% saving over Lamport signatures with only added off-chain storage of 43.8 kB per message bit.

Online attribute checking (e.g. proving age, residency) is increasingly common, yet standard implementations reveal far more personal information than necessary (e.g. all ID contents). Privacy-preserving alternatives exist but require digital inputs: anonymous-credentials or zero-knowledge (ZK) proofs of signature possession over a bitstring. However, it is challenging to gain integrity guarantees on the bitstring itself.

C2PA offers a partial solution: C2PA-enabled cameras cryptographically attest to image origins with an embedded signing key, so a smartphone could provide a signed image of an ID barcode. However, since C2PA signs the image rather than the bitstring of the decoded barcode, the prover must additionally prove correct execution of the PDF417 barcode decoding algorithm on the signed image. Two barriers block this approach: images are large, yielding large proofs and long prover runtimes, and the PDF417 barcode decoding algorithm is highly data-dependent, making compilation into a ZK-friendly constraint systems non-trivial.

We present an end-to-end ZK proof system for PDF417 barcode decoding, built on an adaptation of zkSNARK system Dorian (itself based on Spartan) with modifications: (1) adjusting Dorian's polynomial commitment to validate C2PA signatures more efficiently while cheaply checking consistency with the main Dorian proof, and (2) incorporating additional technical gadgets for set disjointness, data-dependent processing in R1CS, and state machines for greater efficiency. Implementing the PDF417 decoding algorithm as R1CS constraints is also nontrivial, as the algorithm is highly data-dependent and requires modifications to ensure soundness.

Our system is the first to enable efficient barcode decoding in ZK. The best previous option was a zkVM, requiring prohibitively high computation and memory. We demonstrate that our system is significantly faster and uses far less memory. Furthermore, we suggest changes to the C2PA framework that would make future private verifiable image processing tasks more efficient. Though not yet ready for practical deployment, our system presents an alternative approach to private online attribute verification and demonstrates techniques of independent interest for data-dependent ZK computation.

Recently, zero-knowledge proof protocols have gained much popularity due to the adoption in blockchain applications, e.g., zero-knowledge virtual machines. However, using the current standardized hash functions inside the generation of zero-knowledge proofs would incur much overhead in proof size, as well as prover and verifier’s runtime. In the past few years, various circuit-friendly hash functions has been proposed. Skyscraper-v2 is one example of such hash functions applying the split-and-lookup approach for better performance. In this paper, we expand the linear approximation definitions by extending it with circular shifts embedded in the approximation. Specifically, we consider the rotation of bits at both the input and output sides. We demonstrate it with Skyscraper-v2 Sbox. It allows us to better capture the recurring sequence in nonlinear Skyscraper-v2 SBox.

Consider a cryptocurrency exchange that secures the bulk of its reserves under a small set of keys, each of which is only used to transfer cryptocurrency once a year; or the backup codes for an account login or a password manager, which are again rarely used but provide access to crucial systems or information. Securing such infrequently-used high-value secrets is crucial, but existing solutions, such as threshold wallets and 'cold' (offline) wallets, are unsatisfactory.

In this work, we envision a system that allows users to conveniently back up their rarely-used, high-value keys. This new setting necessitates a novel set of design requirements. Specifically:

- We allow user keys to be threshold secret-shared among a large number of custodians where each custodian wallet comprises of a hot (i.e., online) and a cold (i.e., offline) portion. The cold part of the wallet is not touched during the backup process (thus, it is independent of the number of system users) but must be accessed for recovery. - We provide a mechanism to continually assure users that their keys are safely stored. This feature is critical because our system is not designed for frequent key use. We also enable proactive key refresh. - Finally, in our approach, restoring a backed-up key is equivalent to generating a signature. Thus, signatures made by users of this system should look the same as "normal" signatures to avoid exposing holders of high-value keys to targeted attacks.

Based on these requirements, we develop new security definitions and a UC-secure protocol that implements threshold BLS signatures in our new model. Our protocol is practically efficient for the envisioned large numbers of custodians: for a 67-out-of-100 threshold configuration, creating a new backup takes 10s, while recovery takes less than 2ms.

Bilinear groups, also known as pairing groups, are a versatile tool that enables many efficient cryptographic constructions. Among bilinear groups, those with a composite order (N = p · q for two large, secret primes p, q) offer an additional algebraic structure which is advantageous in many applications. They are however dramatically less efficient than their prime-order counterparts, so multiple translation frameworks for constructions from composite- to prime-order groups have been introduced in the literature.

Motivated by the recent construction of Batch Arguments for NP (BARGs) with linear-size CRS by Chen, Elias and Wu [Asiacrypt ’25], based on composite-order groups, we notice that these previous frameworks fail to transfer their scheme to the prime-order setting. In this work, we identify and close this gap by introducing a new translation framework based on a new abstraction called dual encodings. The crucial feature of these objects is a security property called indistinguishability that allows embedding hidden subgroups, emulating composite-order groups more faithfully and thus enabling more powerful translations. Then, we realize dual encodings using functional encryption for function-hiding inner products. Finally, we apply our framework to build the first BARG with linear-size CRS from prime-order groups, while preserving the (statistical) somewhere extractability of previous constructions. Our result represents a significant step toward practically efficient BARGs and showcases a surprising application of functional encryption which we find of independent interest.

Conditional linear cryptanalysis represents an extension of linear cryptanalysis and has been applied to DES and AES. Notably, it enables the construction of a linear distinguisher for 4-round AES, which is considered unattainable through standard linear cryptanalysis. The underlying principle is that the correlation of a linear approximation can be improved when the data is restricted to a specific subspace or subset, thereby allowing more effective linear cryptanalysis. The critical challenge in conditional linear cryptanalysis lies in identifying appropriate conditions to impose on the data; however, previous methods rely on ad hoc strategies that depend heavily on expert intuition, which limits their generalization and application.

In this paper, we propose a generalized framework for conditional linear cryptanalysis. The core tool is the conditional linear approximation table (CLAT), which quantifies linear correlations within constrained data subspaces. We further define a metric termed conditional linear weight, which balances the gain in correlation against the overhead of data filtering, thereby offering a quantitative measure of resistance against conditional linear cryptanalysis. Based on the CLAT and conditional linear weight, we develop an MILP-based automatic search model for conditional linear trails and devise systematic approaches for mounting distinguishing and key recovery attacks using these trails. Applying our framework to AES, Rijndael-256, ARIA, LED, Midori-128, and SKINNY-128, we demonstrate that conventional full-space bounds do not guarantee resistance against conditional linear cryptanalysis, and we propose improved linear attacks.

Our framework provides systematic approaches and automatic tools for conditional linear cryptanalysis. It enables cryptanalysts to gain deeper insights into the statistical linear properties of cryptographic primitives and serves as a useful evaluation technique for new designs.

Modern zero-knowledge (ZK), fully homomorphic encryption (FHE) and Multi-party Computation (MPC) protocols have motivated research interest in Arithmetization-Oriented (AO) cryptographic primitives. The use of these protocols on embedded platforms requires consideration for protection against side-channel analysis (SCA), including timing and power attacks. Compared to traditional bit-oriented block ciphers, the design of side-channel countermeasures for AO-based ciphers poses unique challenges due to their different mathematical properties and computation requirements.

In this work, we perform side-channel analysis of MiMC, a well-known AO block cipher. We first consider its constant-time implementation over the BN254 prime field for both x86 and ARM-v7 targets. Next, we demonstrate both profiled (SASCA) and unprofiled (linear regression) power analysis of our implementation on the ARM Cortex-M4 microcontroller, showing that a DPA adversary can reduce the key-guessing space to just \(2^{30}\) candidates using only \(\approx\) 32000 power measurements, and the profiling adversary can perform full key recovery in as few as 100 measurements.

Hence, we consider and compare two side-channel countermeasures: a classical ISW masking approach, and the redundant number representation (RNR) adapted for large prime fields. For the RNR countermeasure, we show that \(\approx 64\) bits of redundancy are sufficient to reduce the information leakage enough to make DPA attacks impractical. Our claim is supported both by a standard fixed-vs-random leakage assessment with 10 million collected traces and by quantitative analysis via SASCA attacks. Finally, we compare the performance of the RNR countermeasure with first-order masking. While masking incurs in a \(\approx 8.3\times \) overhead on a Cortex-M4 MCU and in an \(\approx 81\times \) overhead on an x86-64 CPU, the RNR approach only introduces a \(\approx 50\%\) overhead on both targets.

Brakedown (CRYPTO 2023) is a transparent polynomial commitment scheme with fast proving. Its reliance on codes with small minimum distance forces the protocol to sample more columns to achieve soundness, resulting in larger proof sizes. Replacing the underlying code with Reed-Solomon codes yields better distance properties and should reduce the number of required queries. However, the standard row-wise RS protocol cannot exploit proximity results beyond the unique-decoding radius, such as the Johnson bound (JACM 2023). The bottleneck is structural: the protocol performs two independent checks—proximity testing and evaluation binding. Increasing the proximity radius reduces queries for the first check but increases queries for the second, leaving the overall proof size unchanged.

Diamond and Posen (CIC 2024) consolidate these checks when the evaluation point is chosen randomly by the verifier. For predetermined or application-specified points, existing approaches introduce a sumcheck reduction that adds logarithmic rounds and prover overhead.

We present DeepBrake, a Reed-Solomon polynomial commitment that consolidates the two checks for arbitrary evaluation points without sumcheck. By fixing row evaluations before the verifier samples the random fold, the protocol uses a single proximity test to verify both properties simultaneously. This enables DeepBrake to exploit stronger proximity bounds and reduce the number of queries.

At $n=2^{20}$ and rate $1/2$ over Ft255, DeepBrake's opening phase is $3.5\times$ faster than the Diamond-Posen baseline with sumcheck, with $16.5\%$ lower total prover time and $2.7\%$ larger proof size.

We further introduce BrakeWHIR, which replaces the explicit proof elements with succinct polynomial commitment openings using WHIR (EUROCRYPT 2025). BrakeWHIR achieves $2.6\times$ faster verification and $1.9\times$ smaller proofs than DeepBrake.