International Association
for Cryptologic Research

Copy-protection is one of the main applications of quantum information in cryptography. In copy-protection, we encode a functionality in a reusable quantum state so that it cannot be split into two states (called freeloader adversaries) that remain simultaneously useful. Despite a long line of research, previous works have only been able to show security with respect to independently sampled challenges in the plain-model. However, arguably a more natural security notion considers the two freeloader adversaries receiving the same challenge. This so-called identical-challenge security notion is also connected to other fundamental quantum cryptographic primitives such as unclonable bits (i.e. unclonable encryption) and copy-protection of point functions.

In this work, first we make progress on the definitional foundations of these primitives, and then prove security in the plain model for our new stronger definitions, in particular also resolving the question of copy-protection with identical challenges and copy-protection of point functions. In more detail, we obtain the following results.

-- Copy-protecting decryption keys (Single-decryptor encryption).} We define a new natural security notion for single-decryptor encryption (SDE) called {correlated challenge security}, and show that implies all previous security definitions for SDE, including identical-challenge security. Then, we prove that, assuming indistinguishability obfuscation (iO) and one-way functions, the SDE construction of Kitagawa and Yamakawa (TCC'25) satisfies correlated challenge security. We also provide an almost complete characterization of the relationship among previous SDE security notions.

--Copy-Protecting General Functionalities with Correlated Challenges. We define correlated challenge unclonable puncturable obfuscation (UPO), allowing arbitrary correlations among challenge points and puncturing bits, plus auxiliary information before and after splitting. Security requires only conditionally uniform bits and $\lambda^c$ average conditional min-entropy in each point separately, for any constant $c>0$; thus, in particular the challenge points may be identical. Assuming polynomially secure post-quantum iO and quantum-hard LWE, we construct correlated UPO for arbitrary polynomial-size keyed circuits with input length at least $\lambda^c$, answering the open question of Ananth, Behera, Huang, Kitagawa, Yamakawa (EUROCRYPT'26) and Çakan-Goyal (EUROCRYPT'26).

--Applications Our results yield the first plain-model copy protection for point functions, $k$-point functions, and compute-and-compare programs under natural security definitions, and identical-challenge copy protection for general puncturable functionalities.

The technical core of our results is a new decisional monogamy theorem for coset states, which both simplifies the proofs and generalizes the results of existing copy-protection constructions, which may be of independent interest.

Rijndael-256 (R256), the 256-bit block variant of the Rijndael family, is practically relevant in ongoing NIST draft discussions on wider-block standardization and in several NIST post-quantum signature candidates. Relative to AES, R256 combines a wider $4\times8$ state with non-standard ShiftRows offsets $(0,1,3,4)$, invalidating key assumptions behind many AES-oriented optimizations. We study how these mismatches manifest on three targets and develop three corresponding adaptation strategies: wider classical bitslicing on Cortex-M4, Reuse with Reshuffling on AArch64, and Amortize the Mismatch on CUDA. This yields a bitsliced Cortex-M4 implementation with secret-independent control flow and memory access patterns (4,962 cycles/block), an AArch64 pre-shuffle design that reuses the AESE instruction with AddRoundKey folded in (up to 6,520 MB/s), and a CUDA shared-memory T-table implementation reaching 81.16 GiB/s; we report throughput on AArch64 and CUDA because per-block cycle measurement is not directly available on those platforms. Replacing the R256 cryptographic core in four NIST PQC reference codebases on Apple M2, with minimal integration changes where needed, yields signing speedups of $1.18\times$--$114.3\times$ and verification speedups up to $155.6\times$, with the end-to-end gain governed by each scheme's R256 fraction.

We show that the CRT-FHE scheme of Pradhan et al. is insecure for laws within its assumed error distribution range. The secret key follows from the public key by a single ring inversion whenever the public multiplier is a unit. The plaintext is recovered from any ciphertext under such a law without the secret key, for every multiplier, giving chosen-plaintext advantage $1/2$. We further show that the transformation from ordinary Ring-LWE to CRT-RLWE does not preserve the error distribution, so it does not establish that CRT-RLWE is at least as hard as Ring-LWE.

One mechanism underlies both. The Chinese remainder theorem (CRT) function is reduced modulo $p_1p_2$ while its output is used modulo a coprime modulus $q$, so under every zero-preserving section an error in $p_2\mathcal{R}$ encodes to zero. The law $p_2B_1$ is so confined, meets the stated conditions, and decrypts correctly. Confinement is not a weakness of scale: scaling any baseline law by $p_2$ leaves its ordinary Ring-LWE problem exactly equivalent, while the reduced encoder destroys every error it produces. The reduction discrepancy is a multiple of $p_1p_2$ and not of $q$, so the small-error premise of the proof cannot remove it, and at the reported parameters a single error coefficient refutes the identity while satisfying that premise. The centered binomial $B_2$ separates the coefficient laws at total variation distance $3/8$, and at the reported dimension that distance between the induced polynomial laws is exponentially close to one.

With the growing deployment of secure multi-party computation (MPC) in data-intensive applications, the offline generation and distribution of authenticated multiplication triples has become a key scalability bottleneck. Existing software-only preprocessing protocols, such as MASCOT and LowGear, typically incur substantial interaction and computation costs when the number of participants or the triple demand is large. This paper proposes a trusted execution environment (TEE) server–assisted aggregated offline deployment scheme that moves expensive interactive preprocessing into a remotely attested enclave and distributes participant-specific authenticated triple shares over authenticated-encrypted channels. Conceptually, the enclave serves as a TEE-backed pseudorandom correlation generator (PCG) that outputs authenticated correlated randomness for MPC with one-way delivery. We design an end-to-end workflow covering remote attestation, per-participant session establishment, and encrypted distribution. The proposed protocol applies to both semi-honest and malicious adversaries; we provide a security analysis against malicious adversaries with abort. Experimental results show clear efficiency improvements over MP-SPDZ implementations of MASCOT and LowGear. Specifically, the proposed scheme achieves a generation rate three times that of MASCOT, while exhibiting linear scalability up to 100k participants. Furthermore, by employing a streaming processing strategy, it efficiently supports the generation of up to 10M triples with an amortized time significantly lower than that of purely software-based protocols, enabling practical and highly scalable preprocessing for large-scale heterogeneous MPC deployments.

Public-key encryption (PKE) is a fundamental primitive in modern cryptography, and many PKE schemes have been standardized and widely deployed. To reason about security in complex and highly compositional environments, Zhandry and Zhang (CRYPTO 2020) initiated the study of indifferentiability for public-key cryptosystems. However, their construction for PKE departs substantially from the design paradigms used in practice, and to date no practical public-key encryption schemes are known to achieve indifferentiability.

In this work, we further investigate indifferentiability for public-key encryption, asking whether it can be achieved for practical, standardized schemes. We provide evidence that the answer is yes: slightly augmented standardized group-based encryption schemes can indeed achieve provable indifferentiability. Our contributions are threefold:

-- Identifying a barrier in the existing ideal PKE model: We revisit the ideal PKE definition of Zhandry and Zhang and identify an artificial requirement---namely, pseudorandom public keys and ciphertexts---that constitutes an inherent barrier to achieving indifferentiability from groups.

-- Redefining the idealized model for PKE: We propose a revised ideal PKE model that removes this pseudorandomness requirement, thereby opening the possibility of achieving indifferentiable public-key encryption from practical group-based schemes. --Making standardized PKE indifferentiable: We consider two public-key encryption schemes standardized in ISO/IEC 18033-2---Elliptic Curve Integrated Encryption Scheme (ECIES) and Public-Key Secure Encryption (PSEC)---and show that, under slight augmentation, both are indifferentiable from our revised ideal PKE.

In conclusion, our work advances the development of indifferentiable yet practical public-key encryption schemes, enabling future research and protocol design to build on standard PKE schemes while enjoying strong composability guarantees.

Ring signatures provide signer anonymity for ad hoc sets of public keys. Generic Abe-Ohkubo-Suzuki (AOS) transforms are well understood for plain Fiat--Shamir and hash-and-sign signatures, but not for their rejection-sampling variants: Fiat--Shamir with aborts (FSwA) and hash-and-sign with retry (HSwR). We formalize AOS ring transforms for FSwA and HSwR and analyze their security in the quantum random-oracle model. For unforgeability, we reduce security under adaptive ring-signing queries to security without signing queries using essentially the same assumptions as in security proofs for the corresponding ordinary signatures; handling adaptive corruption additionally requires the simulation property to remain valid after key exposure. Strong unforgeability additionally requires response uniqueness and special soundness for FSwA, or second-preimage resistance and non-invertibility for HSwR. The residual no-signing-query requirement admits generic reductions, but with loss exponential in the number of honest keys. Finally, an ML-DSA case study shows that augmented public keys achieve the required key-exposure simulation while identifying its limitations; we also identify conditions for candidate HSwR instantiations.

The main barrier to practical fully homomorphic encryption remains the latency and cost of bootstrapping, the ciphertext refresh step that enables unbounded computation. We design new methods that reduce both the latency and the circuit depth of bootstrapping in the FHEW/TFHE framework, which represents the state-of-the-art for lightweight bootstrapping and for computing deep and unstructured Boolean functions over encrypted data.

Our first contribution leverages LWE with a sparse small-norm secret, an assumption known to be equivalent to standard LWE and already widely used in FHE constructions. For an LWE secret of dimension $n$ and Hamming weight $h$, we obtain bootstrapping procedures whose arithmetic complexity decreases from $\tilde O(n^2)$ to $\tilde O(n h)$ $\mathbb{Z}_q$ multiplications while preserving the same asymptotic number of additions. Concretely, this yields a $4.5$--$7.5\times$ practical speedup for gate and functional bootstrapping over the state-of-the-art OpenFHE implementation.

Our second contribution introduces a new RLWE variant with structured secrets, called \emph{\mainrlwevarianttext}, and uses it to significantly reduce the circuit depth of FHEW/TFHE bootstrapping via a new relinearization-free BV multiplication technique. In concrete parameter settings, this reduces the number of sequential NTT/INTT layers required for bootstrapping to just 3, compared to more than 500 in standard FHEW/TFHE, while keeping the overall number of unit 32 or 64-bit word operations comparable to standard FHEW/TFHE bootstrapping. This substantial depth reduction suggests the potential for significantly lower bootstrapping latency on parallel, high-throughput architectures such as GPUs.

Finally, we analyze the security of the new RLWE assumption underlying our depth reduction, including worst-case-to-average-case and search-to-decision reductions, as well as evaluations against concrete attacks.

Zero-knowledge proofs are an operational infrastructure for rollups, private payments, verifiable execution, and zkVM applications. We treat them as succinct proofs of validity whose privacy properties depend on the system and the mode of use. Published benchmarks often compare different workloads, proof modes, and hardware paths, which makes their results hard to interpret. This work presents a unified host-agent framework for benchmarking heterogeneous proving systems under a common execution and reporting method. Each prover runs in an isolated containerized agent and is selected through a scheme-adapter layer. The agent reports canonical JSON artifacts linked to a hashed run manifest and workload-specific semantic contracts. The host checks the public semantic fields and the agent's verification flag to ensure backends are compared on the same declared public claim, even when their circuits, traces, or guest pipelines differ. We evaluate circuit-based, transparent, GPU-accelerated, folding, and zkVM systems: Groth16, ICICLE, Halo2, Plonky3, Winterfell, Nova, RISC Zero with CUDA and Groth16 wrapping, and SP1 with and without AVX. The suite uses six primary workloads with comparable semantics, together with secondary hash workloads that expose specialization. No prover family dominates all deployment criteria. At 8 CPU cores, Plonky3 and Winterfell have the smallest across-case proving-time and RAM figures. Groth16 and ICICLE produce sub-kilobyte proofs. Winterfell has the lowest host verification time. zkVM systems trade larger proofs and higher memory for programmability. On the Merkle-path micro-benchmark, pairing artifacts remain sub-kilobyte, whereas wrapping a zkVM receipt yields a Groth16-sized artifact at a high proving cost. GPU acceleration helps most after fixed setup costs are amortized. The main contribution is methodological: validate the statement being proved, disclose the security profile, and report resource limits in addition to proving time.

Decentralized lending protocols encode credit markets as smart contracts whose design choices affect gas cost, capital efficiency, liquidation behavior, and risk allocation. We compare Aave V3, SparkLend, Compound III, and Morpho Blue in matched Ethereum fork tests with wstETH collateral, USDC debt, and one fixed chain state. The tests measure call-path gas, annualized rates, thirty-day debt growth, maximum borrow capacity, and liquidation outcomes. It is important to note that the observed orderings for gas costs and rates are specific to this test artifact and could change under different collateral assets or utilization regimes. Within this setting, Morpho Blue has the lowest measured interaction call-path gas and highest borrow capacity, while shifting risk selection to isolated permissionless markets. Furthermore, Morpho Blue's evaluation uses a deployed market for rate measurements but a constructed market for liquidation testing. Aave V3 and SparkLend provide broader pooled-market abstractions with higher measured call-path gas. Compound III simplifies borrowing around one base asset per market; its low-gas absorb step is offset by a separate buy collateral liquidation path. We provide a Foundry-based Ethereum-fork test suite for reproducing these measurements and comparing lending-design trade-offs.

Decentralized Finance (DeFi) continues to experience rapid growth, yet a significant portion of capital remains inefficiently utilized in overprovisioned lending reserves or inactive liquidity positions. This paper presents two extension-based improvement proposals aimed at increasing capital efficiency in DeFi protocols. The first addresses idle capital in pool-based lending by adding an allocation layer that can deploy otherwise unused liquidity into external yield-generating strategies. The second targets inactive concentrated-liquidity positions through a position-management layer that automates range migration. Both proposals are examined in terms of motivation, mechanism design, expected effects, implementation approach, and practical limitations. Evaluation results are proposal-specific: the lending analysis indicates meaningful supplier-yield uplift under selected external-yield assumptions, while the range-migration analysis focuses on active-time sensitivity and execution cost. Prototype benchmarks suggest that both mechanisms can be implemented as modular extensions, but also expose additional gas overhead and proposal-specific risks, including external-strategy dependence, recall and loss-allocation concerns, and range-policy misconfiguration.

We remove the Boneh--Lipton conjecture from the proof of Corrigan-Gibbs and Wu (CRYPTO~2024) that Jacobi signatures modulo $N=p^2q$ are one-way. This relates the one-wayness of the pseudorandom generator proposed by Damg{\aa}rd in 1988 to a standard number-theoretic problem alone.

Several decentralized applications and blockchains, such as blockchain-based voting systems or Proof-of-Social-Capital, require a strict one-account-per-person policy, yet public identity records often expose sensitive attributes or enable offline attribution. This work presents a Proof-of-Uniqueness blockchain-based registry that composes an issuer-signed verifiable credential, two zero-knowledge proofs, a threshold verifiable oblivious pseudorandom function (vOPRF), and a smart contract. The first proof authorizes a blinded evaluation of an issuer's certified canonical identifier, and the second validates the OPRF transcript and binds the resulting global nullifier to a wallet. The design further binds issuer authorization, credential status, validity bounds, canonical encoding, and replay state. Its person-level guarantee is conditional on a stable injective identifier within a coordinated issuance namespace and a stable, valid OPRF key. Confidentiality holds against public observers and against fewer than the OPRF threshold of nodes, but not against an issuer that actively probes its own identifiers. Our prototype couples Noir and UltraPlonk circuits, three local threshold OPRF nodes, and a Solidity contract. For one fixed-schema credential input, it derives a single wallet-bound deterministic nullifier, verifies a real 2,144-byte proof on-chain, and rejects a repeated nullifier with $O(1)$ lookups. One real enrollment consumes 615k gas, and proof construction takes about 65 seconds on one desktop software thread.

Memory-Hard Functions (MHFs) are a cryptographic primitive designed to protect passwords and other low-entropy secrets against brute-force attacks. The strongest and most natural formalization of memory-hardness is sustained space complexity (SSC), which measures how long an attacker's memory remains above a given threshold. Ideally, one would like to ensure that any parallel attacker must sustain $\Theta(N)$ memory for $\Theta(N)$ steps, while the function can also be computed in sequential time $\Theta(N)$. Unfortunately, this goal is impossible to achieve. Thus, the appropriate objective is to establish strong tradeoffs between sustained space complexity and cumulative memory complexity (CMC), another strong notion of memory hardness. Blocki and Holman (CRYPTO 2022) achieved strong SSC/CMC tradeoffs in the dynamic pebbling model, but their construction relied on expensive combinatorial graphs, and the pebbling abstraction does not rule out more efficient attacks in the stronger Parallel Random Oracle Model (PROM).

We address both limitations. We construct a new data-dependent MHF (dMHF), DEGSample, and prove the first SSC/CMC tradeoff for dMHFs directly in the PROM. In the dynamic pebbling model, DEGSample achieves the same ideal tradeoff as prior work: any dynamic pebbling strategy either sustains $\Omega(N)$ memory for $\Omega(N)$ steps or incurs a maximal CMC penalty $\Omega(N^{3-\epsilon})$. In the PROM, we prove that any attacker either sustains $\Omega(N)$ memory for $\Omega(N)$ steps or incurs a steep CMC penalty of at least $\Omega(N^{2.5-\epsilon})$. To prove this, we introduce a new graph property called ancestral robustness and show that, together with another property called fractional depth-robustness, it suffices to obtain strong PROM tradeoffs via a natural dynamization procedure to turn the graph into a dMHF. The PROM lower bound combines a time-space trade-off argument with an extraction procedure that converts any PROM execution into a cost-equivalent pebbling of the realized graph.

While decentralized identity management systems strive for autonomy, most still rely on centralized mechanisms (e.g., phone numbers or government-issued IDs) to achieve Sybil resistance and prevent fake identity attacks. This article proposes an identity management architecture that ensures robust Sybil resistance and is fully decentralized, unlike the systems currently in widespread use. The proposed solution synergizes facial biometric verification with anti-Sybil social graph analysis. By leveraging blockchain technology, zero-knowledge proofs, and trusted execution environments, the system ensures the uniqueness, anonymity, and privacy of registered users without relying on centralized authorities. The operation of the proposed system was demonstrated through simulations of a network of 100 entities across three social graph models and through a proof-of-concept implementation that utilizes fast Plonky2 zero-knowledge proofs. To our knowledge, this is the first work that proposes a Sybil-resistant identity system without sacrificing decentralization and privacy, while not relying on any centralized credential issuers.

Zero-knowledge proofs based on VOLE have recently become a promising approach for designing post-quantum signature schemes. Such schemes are constructed by having a signer prove knowledge of a secret input for a prescribed one-way function. In this work, we optimize VOLE-based signature schemes from syndrome decoding (SD) and the permuted kernel problem (PKP). Despite relying on different one-way functions, these schemes share a common modeling method. Elementary vectors are compressed into shorter witnesses and then reconstructed through low-degree polynomials. We propose a unified framework for elementary-vector encoding and reconstruction. By choosing different parameters, this framework captures previous modeling approaches for SD and PKP as special cases. Based on this framework, we propose an optimized encoding and reconstruction approach that reduces the extended witness size and hence the final signature size. At NIST Level I security, our SD- and PKP-based schemes achieve “signature + public key” sizes of 3,496 and 3,341 bytes, respectively, improving over the corresponding 3,775 bytes of SDitH v2.0 and 3,577 bytes of PERK v2.2. Furthermore, we construct a 3,673-byte post-quantum ring signature for rings of 2^20 members, which is 27% and 70% smaller than those of Chiang et al. (CCS ’25) and BLOOM (ASIACRYPT ’22), respectively.

Private Set Union (PSU) allows two parties to compute the union of their private sets while revealing nothing beyond the union. Existing PSU protocols mainly follow two paradigms: reverse private membership test (RPMT) and invertible Bloom lookup table (IBLT). IBLT-based protocols achieve linear complexity using lightweight symmetric-key operations and offer excellent concrete efficiency. RPMT, on the other hand, provides a more general membership-testing functionality that can serve as a reusable building block for PSU and other private-set computations. However, existing RPMT-based protocols either rely on costly building blocks, such as public-key operations and generic secure two-party computation, or incur super-linear complexity. This raises a natural question: can the generality of the RPMT paradigm be retained while matching the asymptotic and concrete efficiency of IBLT-based PSU?

In this work, we answer this question affirmatively by introducing a lightweight mechanism for multi-query membership testing. Our mechanism yields a concretely efficient multi-query RPMT (mqRPMT) protocol that is useful beyond PSU and may be of independent interest. Building on this protocol, we construct a PSU protocol with linear computation and communication complexity. Our construction avoids expensive public-key operations and generic secure two-party computation, relying instead on efficient symmetric-key primitives.

We extensively evaluate our protocol against state-of-the-art PSU protocols from both the RPMT and IBLT paradigms. Compared with the leading RPMT-based PSU protocol from PKC 2024, our construction is $41.7\times$ $-$ $48.9\times$ faster in the LAN setting and up to $4.5\times$ faster in WAN settings. Compared with the leading IBLT-based PSU protocol from EUROCRYPT 2026, our protocol achieves competitive and, in several metrics, superior performance: it is $1.9\times$ $-$ $2.5\times$ faster in LAN settings and reduces communication by up to $1.4\times$. These results demonstrate that the broader applicability of the RPMT abstraction need not come at the cost of asymptotic or concrete efficiency.

The Learning With Errors (LWE) problem with small max-norm secrets and errors forms the foundation of several practical lattice-based cryptographic schemes, including NTRU-based constructions and the recently standardized CRYSTALS-Kyber and CRYSTALS-Dilithium. While recent combinatorial attacks have significantly improved the asymptotic complexity of solving small max-norm LWE, the fastest known methods require prohibitively large memory, often comparable to their runtime. To address this issue, Esser et al. (ASIACRYPT~2023) introduced the first substantially improved polynomial-memory algorithms for recovering small max-norm LWE secrets via nested collision search. In this work, we further improve the asymptotic complexity of polynomial-memory attacks on small max-norm LWE. We introduce a refined nested collision search framework together with new representation structures that increase the number of valid representations while preserving polynomial-memory complexity. This leads to improved asymptotic runtimes across the entire range of relative secret weights. For uniformly random ternary secrets of length $n$, our best algorithm reduces the polynomial-memory runtime from $2^{0.926n}$ to $2^{0.8595n}$, corresponding to an asymptotic speedup of approximately $2^{0.0665n}$. We further extend our framework to the secret distributions used in CRYSTALS-Kyber and CRYSTALS-Dilithium, obtaining improved complexity exponents. Additionally, we apply the proposed refinement to the polynomial-memory nested collision search framework of Esser and May~(EUROCRYPT~2020) for random subset-sum problem, reducing its asymptotic runtime from $2^{0.645n}$ to $2^{0.6432n}$. Although the latter improvement is modest, it provides an independent application of our framework and demonstrates its applicability beyond the LWE setting.

Matrix concentration for Markov chains was initiated in the expander-walk setting by Garg, Lee, Song, and Srivastava'18 [GLSS18]. However, the constant obtained in [GLSS18] is quite loose, and it is natural to ask whether a tighter proof can yield the same constant as in the independent matrix concentration setting. In this paper, we provide a positive answer to this question. Our Hoeffding exponent is sharp, as shown by a scalar obstruction. Our Chernoff and Bernstein constants improve upon those in [GLSS18] and Neeman, Shi, and Ward'24 [NSW24], respectively.

This paper studies the post-quantum multi-key security of Galois/Counter Mode (GCM) in the Quantum Ideal Cipher Model (QICM). GCM is one of the most widely deployed AEAD schemes. In practice, widely deployed cryptosystems are often instantiated under many independent keys, making the multi-key setting practically relevant. A trivial extension of a single-key security bound to the multi-key setting incurs a security loss proportional to the number of keys. In particular, in the post-quantum setting, the term corresponding to exhaustive key search becomes $up^2/2^k$, where $u$ is the number of keys and $k$ is the key length. Here, $u$ is the number of keys, $k$ is the key length, and $p$ is the number of quantum queries to the underlying block cipher $E$ and its inverse, which serves as a coarse measure of the amount of offline (quantum) computation performed by the adversary. For example, when $u=2^{32}$, the trivial bound does not guarantee security for $p \geq 2^{48}$ when $k=128$, and even for $k=192$, it ceases to guarantee security for $p \geq 2^{80}$.

We show that, at the cost of some additional loss terms, the term $up^2/2^k$ can be replaced by a term of order $\sqrt{dp^2/2^k}$, where $d$ denotes the maximum number of keys under which the same nonce appears in encryption queries. Thus, when $d$ is much smaller than $u$ (and the additional loss terms remain small), our bound improves upon the trivial multi-key bound. This can be viewed as a post-quantum counterpart of the classical result of Hoang et al. (CCS 2018). As in their work, we further show that, for randomized nonce-generation mechanisms that abstract patterns used in protocols such as TLS, the parameter $d$ remains small even when $u$ is large. Although our bounds are not tight and leave room for improvement, they yield a notable improvement over the trivial multi-key bound for several concrete parameter settings. To the best of our knowledge, this is the first non-trivial post-quantum multi-key security bound for an AEAD mode in the QICM. Our proof combines the reprogramming-and-resampling approach of Alagic et al. (EUROCRYPT 2022) with counting arguments used in the classical multi-user analysis of GCM by Hoang et al.

AI image generation has made image misinformation a serious concern. To address this issue, the Coalition for Content Provenance and Authenticity (C2PA) standard adopts digital signatures to attest that an image originates from an authorized source, such as an attested camera or authorized AI provider. In practice, however, raw images are rarely published directly: photos are typically compressed before publication, which invalidates any C2PA signature. Recent works have proposed the use of zero-knowledge proofs (zk-SNARKs) to prove that only allowed edits were applied to a C2PA-signed original image. Unfortunately, prior works only support simple edits (e.g. cropping, blurring, and resizing) and do not support lossy image compression like JPEG, which is ubiquitous. The purpose of compression is to save communication. Therefore, unlike other edits, it cannot be verified directly, requires small proof sizes, and is unsuitable to outsourcing. To address these limitations, we present SPEG, the first practical proof system that supports the full image-transmission pipeline on personal devices. We present two protocols that support JPEG compression, while proving validity of the C2PA signature on the original image. The two modes are incomparable: the first is compatible with an arbitrary hashing algorithm (we use Poseidon for efficiency), whereas the second is significantly faster but requires the C2PA to use a polynomial commitment (e.g., KZH) instead of a conventional hash. Our key optimizations are handling the non-algebraic JPEG Encoding outside the proving circuit, and avoiding range checks in our floating-point arithmetic. We can prove the JPEG compression of an FHD(1080p) image in 47s in the Poseidon mode and in 2s in the fast mode. The fastest prior work (VerITAS) which only handles simple resizing, requires 227s on the same consumer hardware. Additionally, we identify a security gap in VIMz (PETS 25) that enables forgery of proofs for unauthorized images and provide a fix. We also prove that we can securely use the popular powers-of-tau SRS with the polynomial commitment scheme KZH.