This work proposes a concrete VRS construction based on random quantum circuit sampling (RCS) executable on today's quantum computing devices and model the construction and prove its security within the constructive cryptography (CC) framework, thereby ensuring composability with other cryptographic protocols.
Abstract
Verifiable random functions (VRF) underpin a wide range of applications that require publicly verifiable evaluations of a pseudorandom function on a given input. However, once the public key is published, the induced function is fixed and is a deterministic function of the input. This determinism can enable collusion and grinding-style attacks in which adversaries precompute and selectively exploit favorable input-output pairs. To address these limitations, we introduce the formal notion of verifiable random sampling (VRS). We propose a concrete VRS construction based on random quantum circuit sampling (RCS) executable on today's quantum computing devices. VRS supports multiparty protocols in which the verifier's final output is a sample that is statistically close to a specified target distribution, while remaining publicly verifiable. We model the construction and prove its security within the constructive cryptography (CC) framework, thereby ensuring composability with other cryptographic protocols. Overall, our results provide a mechanism for verifiable random sampling that simultaneously guarantees sample freshness and public verifiability, enabling applications that require unpredictable, fresh randomness while preserving fairness through public verifiability.
Masking is a widely adopted countermeasure to protect cryptographic implementations from side-channel attacks. Subsequent research has focused on designing masking schemes and formally proving their security, notably through the development of automated tools, within models abstracting the reality of a sidechannel analysis. These designs rely on an external source of randomness; however, there is currently no consensus on the choice of (pseudo-)random number generators for masking. To the best of our knowledge, existing formal proofs for masking security do not consider particular choices of random number generators, but rather assume that they yield uniformly distributed and independent random variables. In that context, we introduce the first verification framework that jointly analyzes a pseudorandom number generator— specifically, but not limited to, a linear feedback shift register—and a masking scheme, in the d-probing model. Our framework relies on the Walsh-Hadamard transform by drawing on techniques from linear cryptanalysis, which we extend to the robust probing model. We demonstrate our method on 4-bit and 8-bit S-boxes, provide a detailed analysis of the formal verification outcomes, and corroborate the findings with practical evaluations on an FPGA.
Anna Guinet, J. Schoone, Niklas Höher et al.· IACR Transactions on Cryptog...· 0 citations
Quantum error mitigation (QEM) is an essential tool for mitigating hardware noise without incurring space overhead. Yet, its reliability depends on modeling, calibration, and implementation, leaving end-to-end security on untrusted quantum hardware unresolved. We address this problem by introducing verifiable blind probabilistic error cancellation (VBPEC), the first secure verification protocol against a fully malicious adversary that integrates QEM. VBPEC brings probabilistic error cancellation (PEC), a widely studied QEM technique, within the scope of composable security by formalizing delegated mitigation as a cryptographic resource in the abstract cryptography framework. The protocol performs PEC with perfect blindness and an exponentially small security error. VBPEC retains the absence of quantum-space overhead from recent statistically-secure verified quantum computation protocols and from PEC. The only overhead takes the form of additional repetitions due to the QEM procedure. To achieve this, we extend trap-based verification from deterministic pass/fail checks to statistical tests that benefit from QEM and develop a new proof technique that integrates the corresponding additional deviation sources. Rather than merely tolerating honest noise below a fixed threshold, VBPEC actively cancels it, enabling correctly mitigated estimates to be accepted with high probability without compromising security. Our framework thus establishes an essential route towards secure, reliable, and practical delegated quantum computation on near-future quantum hardware: VBPEC fundamentally improves the practicality of verification.
Bo Yang, Elham Kashefi, Harold Ollivier· 0 citations
Oblivious pseudorandom functions (OPRFs) allow a client to evaluate a keyed pseudorandom function on a private input without revealing that input to the server. In a threshold OPRF, the secret key is distributed among (n) servers so that any qualified set of at least (t) servers can complete an evaluation, while fewer than (t) shares reveal no information about the key. Existing isogeny-based threshold OPRFs, however, are primarily designed for static corruption models. If the same shares remain valid throughout the lifetime of the service, a mobile adversary can compromise different servers over time, accumulate (t) shares from the same sharing state, and eventually recover the master key. We introduce PIVOT (Proactive Isogeny-based Verifiable Oblivious Threshold PRF), a dealerless threshold VOPRF framework based on effective isogeny group actions. PIVOT periodically refreshes the server shares without changing the master key, public key, or previously generated OPRF outputs. The construction combines Shamir secret sharing, additively homomorphic coefficient commitments, sequential Lagrange-weighted group actions, and joint zero-knowledge relations that link certified shares to their corresponding isogeny actions. It also supports coordinated epoch transitions, publicly verifiable blame, secure erasure, and committee resharing under a possibly different threshold. We formalize the functionality of a long-lived proactive threshold VOPRF, prove the correctness of distributed key generation, threshold evaluation, proactive refresh, and committee resharing, and provide a simulation-based security analysis under the vectorization and one-more hidden-group- action assumptions. As an application, we describe a distributed private lookup service whose encrypted database remains valid across repeated share renewals and committee migrations.
Icy-DVRF is presented, a protocol that improves DVRFwCP by employing a preprocessing scheme similar to FROST to reduce the number of interaction rounds among participants and lowering the additional communication cost, ensuring that verification costs remain low, regardless of the set of participants.
Ahmet Ramazan Agirtas, Arda Buğra Özer, Zülfükar Saygı et al.· IEEE Access· 0 citations
Cryptographic hardware implementations often leak secret information through side channels. This can allow attackers to learn secret data, such as a cryptographic key, without any vulnerability in the cryptographic algorithm itself. A popular countermeasure to such attacks is masking, which ensures that processed data is independent of the secrets by splitting them into multiple independent shares, often at the cost of significant overhead in terms of required area, latency, and randomness. The composable PINI notion in the glitch-extended probing model ensures some degree of security against such side-channel analysis attacks, and guarantees that the circuit may be arbitrarily composed with other PINI circuits while maintaining the same security level. This allows for the secure implementation of arbitrary circuits using trivial composition, replacing elementary gates with “gadgets” realizing the same functionality in a PINI-secure manner. Up to now, PINI gadgets at arbitrary security order are limited to quadratic functions, i.e., 2-input gates, with the best known as HPC3.X realizing a 2-input multiplier in one clock cycle.In this work, we present HPCC, the first low-latency 3-input multiplication gadget for arbitrary fields that maintains a constant latency of one cycle, independent of the number of shares. HPCC additionally allows for the computation of any number of multiplications in a single cycle with relatively little overhead when two of the three operands are identical. When instantiated with two shares and for F2, HPCC halves the previous record for lowest number of fresh masks required at comparable area cost. With more shares, HPCC is the only single-cycle gadget realizing 3- input multiplications in arbitrary fields. We leverage HPCC to implement the first composable AES S-Box with two cycles of latency with an arbitrary number of shares. This S-Box design significantly outperforms the previous record in terms of area and randomness when instantiated with three shares and stands as the only two-cycle solution for more shares.
Frederik Reiter, Amir Moradi· IACR Transactions on Cryptog...· 0 citations
Combining secure multi-party computation (MPC) with differential privacy (DP) enables multiple parties to release aggregate statistics without a trusted curator, and the core primitive is the protocol to sample noise from a continuous distribution under finite-precision arithmetic. In this paper, we revisit the continuous noise sampling protocols and present several improvements in both security and efficiency. We start by identifying a vulnerability in widely used sample-and-scale constructions. We demonstrate that the scaling operation in arithmetic circuits confines the noise to a sparse, publicly known set of values, so that an adversary can observe the released noisy queries and decide which dataset produced them. As concrete demonstrations, we instantiate attacks on two systems employing such ``flawed''sampling protocols: Orchard (OSDI'20) for DP secure aggregation and DP-BREM$^+$ (USENIX Sec'25) for DP federated learning. We report a near-$100\%$ attack success rate on both systems, under any noise scaler $s\geq 2$ used in practice. The leakage we reveal is intrinsic to the scaling operation, and direct repairs either substantially sacrifice utility or add significant precision bits to make the sampling more expensive. To address the security and efficiency issues together, we turn to discrete sampling at the granularity of individual biased bits. We make several optimizations to the sampler and prove its security. Our implementation achieves $4\times \sim 612\times$ speedup over existing secure discrete samplers and orders-of-magnitude speedup over the insecure sample-and-scale paradigm, with negligible utility loss compared to the ideal continuous mechanism.