International Association
for Cryptologic Research

Fully homomorphic encryption (FHE) enables privacy-preserving neural network inference but suffers from high overhead from homomorphic convolutions, polynomial activation approximations, and CKKS bootstrapping. This paper presents BootNet, a unified framework that fuses all three operations into a single bootstrapping invocation per CNN layer, achieving convolution, ReLU, and noise refresh simultaneously.

Prior works are able to fuse convolution into bootstrapping using CinS encoding (NeuJeans, CCS 2024) or ReLU into functional bootstrapping (RBOOT, USENIX Security 2026), but combining both for end-to-end ImageNet inference introduces numerous undocumented challenges. BootNet resolves these through a suite of co‑design techniques and optimizations, including four representative solutions: (1) a split‑and‑merge bootstrapping schedule that halves bootstrapping calls for ResNet shortcuts; (2) an improved RBOOT configuration paired with a model quantization method that complete the activation function with fewer multiplication depth; (3) a fusion of NeuJeans' masking layer with RBOOT's arcsin step that yields additional depth reduction; (4) tailoring EvalRound+ (IEEE Access 2025) to fit slim bootstrapping and RBOOT for further depth reduction.

We evaluate BootNet on multiple ResNet models on the ImageNet dataset. Compared to the state-of-the-art Orion (ASPLOS 2025), BootNet reduces end-to-end latency by 67-73% and storage by 76-90% while preserving plaintext accuracy. We also introduce BootNet-mini, enabling full ImageNet inference at ring degree $N=2^{15}$ (with over $120$-bit security via sparse-secret encapsulation) for the first time, while all previous works have to use $N=2^{16}$ or larger. BootNet-mini performs similarly in latency but reduces 30-55% storage requirement than BootNet, making it potentially more friendly for hardware acceleration.

We study transparent public generation of hard supersingular curves: a public, seeded, rerunnable algorithm outputs a supersingular curve while exposing the seed, verification transcript, and all algebraic information reconstructible from the implementation. This setting is distinct from trusted or distributed ceremonies, where a witness may be hidden, erased, or zero-knowledge protected. We define a transcript-security model for this setting and develop barriers for several modeled algebraic generation routes. For modular-conjugacy samplers, we analyze loci of supersingular invariants admitting an isogeny to their Frobenius conjugate; small public parameters give efficiently recognizable sparse support, while extractable high-parameter witnesses yield non-scalar endomorphisms by Frobenius composition. We extend this leakage principle to bounded correspondence witnesses, including kernel, rational-map, Hecke--Brandt, and elliptic-return detour traces. For direct samplers, we separate predicate-only search, local-neighbor exploration, bounded-relation witnesses, low-formal-degree ambient algebraic maps, and degree-one indexed maps from \(\F_p\) to \(\F_{p^2}\). The resulting theorems are deliberately model-bounded: they do not rule out hidden-witness ceremonies, higher-degree indexed maps, compact high-degree root indexing, endpoint-only mechanisms, or nonlocal aggregate sampling. Full proofs are deferred to the appendices.

What is the round complexity of MPC over point-to-point channels that is secure with unanimous/identifiable abort in the dishonest-majority setting?

Even after four decades of research, the answer to this question remains unclear. Although two-round MPC protocols exist in the broadcast-channel model, and, further, broadcast protocols with expected-constant rounds exist facing any constant fraction of corruptions, a naïve combination of the two yields MPC with expected $O(\log{n})$ rounds, where $n$ is the number of parties. The reason for this gap is the need to preserve the expected round complexity under parallel composition, yet existing techniques for the composition of broadcast protocols inherently rely on an honest majority of parties.

Further, when considering MPC with abort, one can also consider \emph{broadcast with abort}. However, existing lower bounds on the round complexity of broadcast do not translate to this relaxed notion of broadcast, with the end result that the existing lower bounds for MPC and broadcast do not apply to the question above.

In this work, we initiate the systematic study of this question and present the following positive and negative results for MPC over point-to-point channels:

- First, we prove the impossibility of (strict) constant-round MPC with unanimous abort. In fact, we show that any broadcast protocol with unanimous abort that is secure against super-constant corruptions requires super-constant rounds.

- Second, we present a round-preserving and black-box parallel composition construction of broadcast with unanimous abort, which leads to our main result: Assuming oblivious transfer (OT) and verifiable random functions (VRFs), MPC with unanimous abort and expected constant rounds is possible in the PKI model for signatures and VRFs, in the presence of any constant fraction of corruptions.

- Finally, we show that in the presence of slightly more corruptions---i.e., $n-o(n)$ corruptions---there is no expected-constant-round broadcast (and thus MPC) with identifiable abort.

Modern, deployed key transparency systems rely on auditors to ensure that updates to the set of keys are well-structured, allowing clients to efficiently monitor their own keys. In practice, the server's consistency proofs are very large, requiring computationally powerful auditors; as a result, real-world deployments have very few auditors.

We propose a new key transparency system based on a new data structure called Forget-me-not trees, which is a careful composition of Merkle trees and Bloom filters. The resulting system reduces the size of audit proofs by $\approx500\times$, from 15MB-30MB down to only 30KB-60KB. Our construction is the first mass-scale auditable key transparency system that relies only on hash functions.

The Duplex construction, introduced by Bertoni et al. (SAC 2011), is the Swiss Army knife of permutation-based cryptography. It can be used to realise a variety of cryptographic objects—ranging from hash functions and MACs, to authenticated encryption and symmetric ratchets. Testament to this is the STROBE protocol framework which is a software cryptographic library based solely on the Duplex combined with a rich set of function calls. While prior works have typically focused their attention on specific uses of the Duplex, our focus here is its indifferentiability. More specifically, we consider the indifferentiability of the Duplex construction from an online random oracle—an idealisation which shares its same interface. As one of our main results we establish the indifferentiability of the Duplex from an online random oracle. However indifferentiability only holds for the standard Duplex construction and we show that the full-state variant of the Duplex cannot meet this notion. Our indifferentiability theorem provides the theoretical justification for the security of the Duplex in a variety of scenarios, amongst others, its use as a general-purpose cryptographic primitive in the STROBE framework. Next we move our attention to AEAD schemes based on the Duplex, namely SpongeWrap, which is the basis for NIST's Lightweight Cryptography standard Ascon. We harness the power of indifferentiability by establishing that SpongeWrap offers security against key-dependent message inputs, related-key attacks, and is also committing.

As the transition to post-quantum cryptography accelerates, security protocols must evolve to resist quantum threats while remaining practical, particularly on constrained devices where memory, bandwidth, and performance are limited. We consider the NIST Personal Identity Verification (PIV) system, where smart cards rely on digital signatures for authentication. Since post-quantum signatures introduce substantial computational and memory overhead, whereas post-quantum Key Encapsulation Mechanisms (KEMs) are generally lighter, we investigate KEM-based alternatives for authentication and assess the migration of secure messaging to post-quantum primitives. We propose post-quantum variants of the PIV authentication and secure messaging protocols and implement both signature-based and KEM-based approaches on a real smart card platform. We evaluate their computational and communication costs in a realistic embedded setting and present detailed performance metrics that enable assessing the impact of post-quantum migration across different hardware and communication configurations. Our results show that KEM-based authentication significantly reduces execution time and transmitted data compared to post-quantum signature-based designs, while KEM-based post-quantum secure messaging incurs moderate overhead compared to its classical counterpart. These findings highlight KEM-based authentication as a practical migration strategy for post-quantum secure embedded systems.

Client-specific preprocessing PIR supports sublinear online private queries after a linear-time offline phase that prepares client-specific hints. The relevant lower bound is tight: any scheme with $S$ bits of client storage and online cost $T$ must satisfy $S \cdot T = \Omega(n)$. Most practical random-set schemes fall short by a $\kappa$ factor in client storage, while the known constant-factor-optimal schemes, WR-PIR (Eurocrypt 2025) and Balanced PIR (S&P 2026), rely on complex hint-management machinery and incur high concrete costs.

We present Multi-level PIR, a preprocessing PIR scheme that matches this tight space-time tradeoff using only simple random-set components. The main idea is a multi-level composition: early levels are allowed to fail with noticeable probability, and later levels are invoked only when these query-independent failures occur. This 'waterfall' structure drives the overall failure probability down to negligible while keeping expected online cost and client storage at $O(\sqrt{n})$.

Our implementation shows that this simpler structure gives competitive concrete performance. Compared with Piano and S3PIR, two prior state-of-the-art practical schemes, \name achieves a $9$-$20\times$ client space reduction; compared with Balanced PIR, it reduces preprocessing time by about $8$-$45\times$ and online communication by about $5$-$67\times$ in our evaluated settings, while remaining competitive in other online metrics.

As an additional theoretical result, we give a more involved variant with $O(n^{1/4})$ online communication, the first constant-factor-optimal preprocessing PIR scheme with sub-$\sqrt{n}$ online communication.

We improve the performance of the lattice-based cryptosystem Dilithium on AVX2 and NEON by deeply exploiting its algorithmic properties, such as small coefficient bounds and high sparsity, with the distinct instruction-level profiles of the underlying architectures. On AVX2, we deploy a single-modulus 16-bit NTT for $c \cdot \mathbf{s}_i$ and a multi-moduli 16-bit NTT coupled with a vectorized CRT reconstruction for $c \cdot \mathbf{t}_0$. These instruction-level optimizations accelerate the respective computations by $2.4$--$2.5\times$ and $1.2$--$1.3\times$ over official AVX2 baselines, ultimately reducing the overall Dilithium signature generation time by $7\%$ to $8\%$. Conversely, On ARMv8-A NEON, we retain the efficient 16-bit NTT for $c \cdot \mathbf{s}_i$, while proposing a Fast Sparse Polynomial Multiplication (Fast-SPM) method for $c \cdot \mathbf{t}_0$. By exploiting the extreme sparsity of the challenge polynomial, Fast-SPM entirely bypasses the NTT and converts the computation into highly efficient index-shifted additions. Across the tested NEON platforms (Cortex-A72 and Apple M1 Pro), this hybrid approach achieves a $1.9$--$2.1\times$ speedup for $c \cdot \mathbf{s}_i$ alongside a $1.1$--$1.9\times$ acceleration for $c \cdot \mathbf{t}_0$, which translates into a $10\%$ to $13\%$ reduction in the overall signature generation time.

Cryptographic compression functions are a core component of vector commitment schemes, including Merkle tree commitments, which are widely used in modern ZK-SNARK and STARK frameworks. Arithmetization-Oriented (AO) compression functions minimize multiplicative complexity over the framework's native field F_p, making them significantly more efficient than bit-oriented designs in algebraic circuits. To date, AO compression functions have been almost exclusively constructed by applying the Sponge mode to an AO permutation.

In this work, we introduce two novel approaches for building permutation-based AO compression modes: the PA family, based on a Permutation with feedforward Addition, and PAX, as an eXtension of the PA family. We formally establish that, in contrast to the Sponge construction, our modes achieve optimal collision and preimage resistance. We also prove that PAX is indifferentiable from a random oracle, further strengthening its security and composability guarantees. We further show that variable-input-length hash functions can be safely instantiated from the PA(X) modes by applying appropriate domain extenders.

Beyond their strong security guarantees, our modes provide a framework that unifies and extends the description of several recently proposed modes that have been studied via cryptanalysis but do not come with provable security guarantees, including Jive and Trunc, as used in the AO designs Anemoi and Poseidon2.

Finally, through extensive experimental evaluation, we compare the concrete efficiency improvement that our modes offer compared to the Sponge approach over two popular AO permutation designs, Poseidon permutation and Rescue. For 128 bits of collision resistance, our modes can achieve up to a 2x speed-up over Sponge for equivalent compression rates in a software implementation. When considering R1CS arithmetization in the Groth16 framework, the PA(X) preimage-verification circuit can be 10% faster than Sponge. In the Plonky2 framework, PA(X) can achieve up to a 60% speed-up

Secure multiparty computation (MPC) allows $n$ parties to compute a function of their private inputs, so that nothing beyond the output of the function is revealed. In the sub-optimal honest majority setting in which the number of corrupted parties $t<(1/2-\varepsilon)n$, the works of Goyal et al. (CRYPTO'21 and CRYPTO'22), achieved $O(|C|)$ communication even against active adversaries, but with $\Omega(n\cdot|C|)$ computation, where $C$ is the arithmetic circuit computed by the MPC. Recent work by Garg et al. (CRYPTO'24) showed that both $O(|C|)$ communication and computation can be achieved in this regime, however, only against passive adversaries. In this work, we achieve the best-of-both-worlds by obtaining MPC with $O(|C|)$ communication and computation against active corruption of $t<(1/2-\varepsilon)n$ parties. To do this, we introduce novel techniques for actively-secure MPC constructed from Chinese Remainder Theorem based secret sharing.

Consensus protocols form the core of blockchains and other replicated state machines, ensuring that all correct nodes process the same totally ordered log of input transactions. In fault-free executions, performance is driven by the good-case transaction latency -- the time between a transaction becoming known to all nodes and its confirmation by the consensus protocol -- which depends on both how frequently proposals are made and, once made, how quickly they are confirmed. While prior work has established tight lower bounds on confirmation latency that modern protocols already achieve, it remains open whether the inter-proposal time can be further reduced below the state-of-the-art of one network delay.

We introduce Gatling, an atomic broadcast protocol that achieves arbitrarily small inter-proposal times under rotating leader schedules; in particular, smaller than the network delay. Gatling runs multiple parallel instances of a black-box atomic broadcast protocol and staggers their proposal schedules to generate proposals in faster succession than state-of-the-art protocols. A deterministic interleaving rule merges the outputs of these instances into a single global log. We analyze the effects of head-of-line blocking caused by crashed leaders, and derive Gatling's optimal number of parallel instances. We further study the impact of Gatling on predictable validity and present two variants that retain this property. Finally, our experiments confirm that Gatling can be used with off-the-shelf component protocols to achieve low latency without fine-tuning the component protocol for minimum latency.

We initiate the study of multi-authority traitor tracing (MA-TT), a decentralized variant of traitor tracing in which tracing capabilities are distributed across multiple independent authorities rather than concentrated in a single trusted entity. Ciphertexts are associated with tracing policies over a collection of authorities, specifying which subsets of authorities are authorized to jointly accuse a user of contributing to a pirate decoder. This enables fine-grained control over tracing capabilities, prevents unilateral accusations, and reduces the surveillance risks inherent in centralized tracing systems. Our scheme naturally supports conjunction, disjunction, threshold, and more general monotone tracing policies.

We further introduce multi-authority attribute-based traitor tracing (MA-AB-TT), which combines distributed tracing in MA-TT with decentralized access control from multi-authority attribute-based encryption (MA-ABE). Ciphertexts are therefore equipped with two orthogonal policies: an attribute policy governing decryption and a tracing policy governing which tracing authorities may jointly identify traitors.

Our main contribution is a construction of MA-AB-TT for arbitrary monotone access structures from the standard matrix decisional Diffie-Hellman (MDDH) assumption in prime-order pairing groups. Our construction achieves adaptive security under static corruption of authorities in the random oracle model. All system parameters are independent of the number of authorities and users in the system, while ciphertexts grow linearly with the size of the associated policies. Our framework also yields a publicly traceable variant, in which tracing can be performed using only the authorities' public keys, albeit with weaker asymptotic efficiency guarantees.

Technically, we extend the blueprint for pairing-based traitor tracing based on private linear broadcast encryption (PLBE) [Boneh et al., Eurocrypt 2006] to the multi-authority setting. The key technical ingredient is a new multi-authority PLBE construction, which we instantiate from slotted inner-product function encryption (sIPFE) [Lin and Luo, Eurocrypt 2020]. As an intermediate step, we provide a new attribute-based sIPFE scheme supporting arithmetic branching programs, which may be of independent interest.

Our techniques also yield a new modular construction of adaptively secure MA-ABE under static corruptions from sIPFE, improving on a prior construction by Ambrona and Gay [PKC 2023]. Finally, when specialized to a single authority, our framework gives the first ciphertext-policy attribute-based traitor tracing scheme with asymptotically optimal parameters and exponentially large user spaces.

Existing encrypted search and private set intersection (PSI) protocols struggle to reconcile post-quantum security with practical efficiency, often leaking search and access patterns or requiring prohibitively deep fully homomorphic encryption (FHE) circuits. We address these limitations by introducing a new Homomorphic Bloom Filters (HBF) framework, a quantum-resilient framework that embeds length-$m$ Bloom filters directly into the plaintext space of an RLWE-based FHE scheme, enabling shallow homomorphic evaluation and matching without structural leakage. Building on HBF, we construct a searchable encryption (SE) scheme and a private set intersection (PSI) protocol, both based on a depth-1 homomorphic missing-bit circuit. The SE scheme requires no rotations or bootstrapping at server side and incurs no additional computational cost as the number of query keywords increases. The PSI protocol reduces each packed Bloom-filter comparison to a single ciphertext--plaintext multiplication, with cost depending on the Bloom-filter length rather than direct element-wise comparisons with the responder's set. This framework confines leakage to benign dataset dimensions, tunable false-positive rates, and other public metadata, thereby eliminating explicit pattern leakage.

This paper presents the first practical end-to-end fault injection attacks on the post-quantum signature scheme PERK, based on the MPC-in-the-Head paradigm and relies on GGM tree expansions for efficient randomness generation. While GGM trees reduce memory requirements, they introduce implementation-level deviations from the theoretical model. We show that these implementation choices fundamentally alter the fault surface and enable new attack vectors that are not captured by the original security assumptions. We propose two attacks targeting distinct stages of the GGM tree construction. The first attack fixes the root seed, resulting in deterministic tree generation and enabling full reconstruction of all leaf labels. The second attack induces reuse of GGM roots via an instruction skip, allowing recovery of hidden leaf values across consecutive rounds. Both attacks require only a single fault to recover the secret key.

We demonstrate both attacks end-to-end on the pqm4 reference implementation compiled with optimization levels -O3 as well as -Os for ARM Cortex-M4 microcontrollers. Our evaluation is performed on two hardware platforms (ChipWhisperer-Lite with STM32F303 and Nucleo-L4R5ZI-P) using clock glitching and electromagnetic fault injection (EMFI). We achieve success probabilities of 100% and 85% for the two attacks, respectively. Finally, we propose countermeasures for both attacks.

Due to the complexity of modern cryptographic algorithms, especially in the area of Post-Quantum Cryptography (PQC), conceptualizing optimal hardware designs in relation to some target performance metric is increasingly time-consuming and error-prone, particularly when combined with the need for secure side-channel protection mechanisms. To solve this, Buschkowski et al. presented the HADES framework at CHES 2025 that efficiently automates the pre-synthesis Design Space Exploration (DSE) process and combines it with automated arbitrary-order masking capabilities. However, as their work focuses only on Boolean masking, PQC schemes that rely heavily on finite field arithmetic incur a significant overhead in latency and area, as demonstrated in their MLKEM (Kyber) case study.

In order to improve the performance of such primitives in hardware, we present a framework built upon HADES that supports both Boolean and arithmetic masking domains and can seamlessly and automatically convert between both types of secret sharing within the design hierarchy, while retaining the efficient DSE capabilities, extended by additional performance metrics. Even though the theoretical foundations of arithmetic masking are well-studied, some highly relevant implementation aspects, like the generation of non-power-of-2 masking randomness, are left largely unexplored. To help close this gap, we extensively analyze and systematically explore the cost associated with the secure and efficient generation of uniform randomness in hardware.

As an initial case study to highlight the capabilities of our modified HADES tool, we present a highly configurable and optionally fully-masked ML-KEM hardware design that improves upon state-of-the-art masked implementations by up to two orders of magnitude while also being competitive with unmasked designs from literature. To validate its practical security, we are the first to conduct practical leakage assessment measurements on the complete decapsulation algorithm, showing no signs of side-channel leakage after 500000 traces.

The CKKS fully homomorphic encryption scheme has traditionally been viewed as suitable only for approximate arithmetic. However, recent work (Alexandru et al., Crypto 2025) has introduced functional bootstrapping techniques that enable accurate lookup tables (LUTs) evaluation in CKKS. Nevertheless, to deal with the high precision problem, the state-of-the-art scheme (Dumezy et al., TCHES 2026) requires reshaping the LUTs into a matrix, which incurs $O(P)$ multiplications for a size-$P$ table and dominates runtime.

We first observe that LUT matrices for many practical functions are often highly structured, with exact or numerical rank much smaller than matrix dimension. We then develop a spectral framework for the LUT evaluation problem, which characterizes the relationship between function classes and the singular value decomposition. This framework yields exact rank bounds for structured function classes such as separable functions, and establishes exponential decay of singular values (implying low numerical rank) for smooth analytic functions. Building on this framework, we propose Low Rank Multiplexer Tree Functional Bootstrapping (LRMT-FBT), which evaluates the LUT via the singular values and singular vectors instead of direct matrix multiplication. This reduces the homomorphic multiplication cost from $O(P)$ to $O(r\sqrt{P})$, where $r$ denotes the rank of matrix, while also supporting extensions to multi-value and multi-input settings.

We implement LRMT-FBT in OpenFHE and evaluate it across different spectral classes. We also introduce implementation optimizations to improve the bootstrapping efficiency. At high precision, LRMT-FBT provides substantial performance improvements for common low rank functions compared with Dumezy et al. Typically, for $P = 2^{20}$, our method accelerates the LUT evaluation step by \(196.9\times\) for Step (\(r=1\)) and \(99.6\times\) for ReLU (\(r=3\)), yielding functional bootstrapping speedups of \(5.3\times\) and \(5.1\times\), respectively.

As machine-learning-as-a-service (MLaaS) becomes ubiquitous, protecting model queries via private inference is increasingly critical. Existing homomorphic encryption (HE)-based protocols for Private Decision Tree Evaluation (PDTE) have server complexity that scales at least as $O(2^D)$ in the tree depth $D$, so the cost of evaluating each tree grows exponentially with depth; in gradient boosted decision tree (GBDT) ensembles, where predictions aggregate the outputs of many trees, this per-tree cost is directly amplified.

In this paper, we present a non-interactive HE-based PDTE protocol built on the CKKS scheme with an end-to-end complexity of $O(p\sqrt{2^D})$, where $p$ is the input bit-length. To the best of our knowledge, this is the first HE-based PDTE scheme that asymptotically improves over the $O(2^D)$ dependence on $D$ while remaining non-interactive. We address two depth-driven sources of $O(2^D)$ dependence in existing protocols: we use the One-Branch-Only (OBO) paradigm from PROBONITE for comparisons, and we design the Baby-Step Giant-Step based Branch Selection algorithm for traversal. To further exploit the structure of GBDT ensembles, we deploy the batched bootstrapping technique by applying level-major tree evaluation.

Our experimental results show that, at depth $D=12$, our protocol reduces communication by $8.38\times$ and runtime by $7.74\times$ compared to FASTER, which is the fastest prior HE-based non-interactive PDTE baseline in our amortized setting, and the advantage increases as $D$ grows. These results suggest that our design provides a practical path toward depth-scalable HE-based PDTE for large boosted ensembles.

Satellite communication systems, as critical long-lifecycle infrastructure, face a dual security challenge in the coming decades: the threat of quantum computers and the operational rigidity of traditional Public Key Infrastructure (PKI). While migrating to Post-Quantum Cryptography (PQC) addresses the former, it fails to solve the inefficiency of certificate management, where in-orbit policy updates require a prohibitively slow and complex multi-party re-issuance process. To address these challenges, we introduce the concept of a Post-Quantum Sanitizable Multi-Signature ($\texttt{PQ-SMS}$), a novel primitive that enables controlled certificate adaptation across hierarchical trust while preserving the integrity of the root of trust. Building on this, we present $\texttt{Sat-APCS} $($\textbf{Sat}$ellite $\textbf{A}$daptable $\textbf{P}$ost-quantum $\textbf{C}$ertificate $\textbf{S}$cheme), which cryptographically decouple a certificate's immutable, multi-signed identity from its dynamic operational policies. This allows a delegated entity to perform lightweight, in-orbit policy updates while the foundational signature from the original consortium of authorities remains unchanged and valid.

We instantiate $\texttt{PQ-SMS}$ based on the NIST-standard CRYSTALS-Dilithium signature and a ISIS-based chameleon hash, and prove its security under standard lattice assumptions. Furthermore, Performance evaluation demonstrates that $\texttt{PQ-SMS}$ bypasses the interactive re-signing loop of traditional PKI, achieving an order-of-magnitude reduction in update bandwidth.

Asynchronous multi-party computation (AMPC) en- ables a set of mutually distrustful parties to securely compute any joint function on their private inputs under arbitrary network delays. The guaranteed output delivery (i.e., G.O.D.) property is essential for availability, but can be very challenging to achieve in practice. HoneyBadgerMPC (CCS 2019), the first practical AMPC protocol, follows Beaver’s paradigm that generates Beaver triples offline to simplify online computation. One of the underlying building blocks, the random double sharing protocol that generates random double shares, how- ever, implicitly assumes a synchronous network. DumboMPC (Usenix Sec 2025) overcomes the issue by adopting a two-phase workflow where the underlying consensus protocol has to be executed twice, and thus incurs high latency. Velox (CCS 2025) achieves lower latency and weaker cryptographic assumptions at the cost of sacrificing G.O.D. It remains an open question whether there exists a more practical AMPC protocol with the G.O.D. property. In this paper, we present RondoMPC, a practical AMPC protocol with G.O.D. with only one phase of consensus. To achieve this goal, we build a practical asynchronous and complete random double sharing (ACRDS) protocol. Our ACRDS protocol supports batching, so a batch of random double shares can be generated simultaneously. Furthermore, ACRDS supports efficient verification of aggregated secret shares, allowing the random double shares to be used for Beaver triple generation using only one phase of consensus. Our experimentation results show that RondoMPC is highly practical, achieving both higher throughput and lower latency for Beaver triple generation compared to existing protocols.

We present TruthTable, a verifiable database engine that allows a prover to produce a succinct proof that convinces a verifier of the correct execution of the verifier's SQL query over the prover's committed database.

TruthTable supports a large subset of SQL, enabling it to prove 17 out of 22 queries in the standard TPC-H benchmark. To our knowledge, this is the widest support out of all prior work. Moreover, TruthTable's proofs are small, and fast to generate and verify: on the TPC-H benchmark with a database of a million rows, TruthTable's average proving time is $55$ seconds, average verification time is $32$ ms, and average proof size is $24$ kB. Compared to prior work, TruthTable's proving times are between $6.3\times$-$63\times$ better, while the verification times and proof sizes are competitive.

TruthTable achieves these properties via a codesign of cryptography and database techniques. On the cryptographic front, we propose a new polynomial representation of database tables, and design new subprotocols for proving the correct execution of various relational operators on these representations. On the database front, we propose a query planner that optimizes queries for minimal proving time, as opposed to minimal execution time. We also design new optimizations for this planner that reduce proving time by up to $2 \times$.