Singh et. al. recently uploaded a preprint describing a new hash function inspired by the Collatz Conjecture. After performing some cursory tests, the proposed function appears to be completely unsuitable for cryptographic purposes, and should not be used.

We initiate a systematic study of information-theoretic cryptography with {\em weak privacy}, only requiring that the adversary cannot rule out any possible secret. For a parameter $0<p\le 1$, we say that a primitive has $p$-weak privacy ($p$-WP) if for every possible view $V$ and inputs $x_1,x_2$, the ratio between the probabilities of the adversary observing $V$ on $x_1$ and on $x_2$ is at least $p$. This generalizes both perfect privacy, which is $p$-WP for $p=1$, and a previous ``combinatorial'' notion of privacy, which is $p$-WP for {\em some} $p>0$. We obtain the following main results. Positive results. We present efficient WP constructions for generalized secret sharing, decomposable randomized encodings, and the related notions of garbling schemes and PSM protocols, as well as interactive secure multiparty computation protocols in the plain model and in the OT-hybrid model. For secret sharing, we settle a question of Beimel and Franklin (TCC 2007), showing that every $n$-party access structure admits a WP scheme with per-party share size $O(n)$. When all unauthorized sets have constant size, we get a $p$-WP scheme with constant share size and $p\ge 1/poly(n)$. Negative result. For decomposable randomized encodings, we show that a previous lower bound technique of Ball et al.\ (ITCS 2020) applies also to the WP notion. Together with our upper bound, this shows that the optimal WP garbling size of the worst-case $f:\{0,1\}^n\to\{0,1\}$ is $\tilde{\Theta}(n^2)$. Application. While WP may seem like an unrealistically weak security notion, we demonstrate its usefulness towards achieving traditional security guarantees. Concretely, under the standard LPN assumption, we show that any $p$-WP secret-sharing scheme with inverse-polynomial $p$ implies a {\em computationally secure} secret-sharing scheme for a related access structure. Together with our positive results for WP secret sharing, this implies a super-polynomial improvement of the share size for a natural class of access structures.

This study investigates and improves the differential cryptanalysis of the ARADI block cipher, a low-latency cryptographic system developed by the United States National Security Agency for memory encryption. The preliminary security assessment of ARADI revealed deficiencies that require additional examination. This study revisits and corrects the key recovery attack introduced by Bellini et al. (Indocrypt 2024). By correcting these mistakes, the research presents a precise 11-round key recovery method with revised attack complexities. Additionally, the analysis is expanded to introduce a key recovery attack for 12 rounds of ARADI, leaving the security margin of the cipher to only 4 rounds.

We propose a novel timestamping mechanism for consensus protocols that reliably assigns submission times to honest transactions while preventing adversarial transactions from forging their timestamps. Our mechanism remains secure even under asynchronous networks and in the presence of corrupted parties. We demonstrate how it can be integrated into the three main families of consensus protocols and show its compatibility with layer-2 solutions. This construction enables robust layer-2 implementations that do not rely on timing assumptions, remain resilient under network saturation, and prevent collusion between users and validators to censor honest users.

Random beacons play a critical role in blockchain protocols by providing publicly verifiable, unpredictable randomness essential for secure assignment of protocol roles such as block producers and committee membership. In the interest of efficiency, many deployed blockchains adopt beacon algorithms that suffer from grinding: an adversarial attack in which a party exploits freedom given by the protocol to bias the outcome of the random beacon by resampling it several times and picking the most desirable outcome. To compound the problem, beacons often operate in an iterative manner, where the beacon output produced during one protocol epoch serves as the random seed for the beacon’s invocation in the next epoch. This amplifies the security threat, as such attacks may then aggregate their power over many epochs. In this article, we formulate a generic framework for information-theoretic analysis of grinding in iterated randomness beacons. We define the natural grinding capacity of a beacon, intuitively corresponding to the amount of grinding it allows with a uniformly random seed. We then prove that sufficiently strong tail bounds on this quantity can be transformed into a guarantee on smooth min-entropy of the iterated beacon’s output, even conditioned on all past outputs and irrespective of the inner workings of the beacon. Such min-entropy guarantees can immediately be translated into corresponding statements about various applications of the beacon to committee selection, incentives, or underlying protocol security. Our main technical result concerns conventional longest-chain protocols, where we establish that the combinatorial structure of the forest of longest chains can be leveraged to control grinding. Instantiating the generic framework with these grinding upper bounds, we establish that the randomness beacon of the Ouroboros Praos protocol is secure against adversaries controlling up to about 12% of stake—even without any assumptions bounding the adversarial computational power invested into grinding. This is a qualitatively new guarantee for the protocol.

BBS/BBS+ signatures are the most promising solution to instantiate practical and lightweight anonymous credentials. They underlie standardization efforts by the W3C and the IRTF. Due to their potential for large scale deployment, it is paramount to understand their concrete security, but a number of questions have been left open by prior works. To this end, the security proofs by Au et al. (SCN '06), Camenisch et al. (TRUST '16), and Tessaro and Zhu (EUROCRYPT '23) show reductions from $q$-SDH in groups of prime order $p$, where $q$ is the number of issued signatures. However, these prior works left the possibility open that BBS/BBS+ is {\em even more secure} than what can be guaranteed by such proofs. Indeed, while the $q$-SDH assumption is subject to an attack that uses $O(\sqrt{p/q})$ group exponentiations (Cheon, EUROCRYPT '06) for several choices of $q$, no attack with a similar complexity appears to affect either of BBS+ and {\em deterministic} BBS, for which the best known attacks amount to recovering the secret key by breaking the discrete logarithm problem. The assumption that this attack is best possible also seemingly justifies the choice of parameters in practice. Our result shows that this expectation is not true. We show new attacks against BBS+ and "deterministic" BBS which, after seeing $q$ signatures, allow us to recover the secret key with the same complexity as solving the $\Theta(q)$-Discrete Logarithm problem, which in turn is proportional to $O(\sqrt{p/q})$ for many choices of $q$. Further, we also extend the attack to a reduction showing that the security of BBS+ and deterministic BBS implies the $\Theta(q)$-SDH assumption.

Privacy-preserving advertisement attribution allows websites selling goods to learn statistics on which advertisement campaigns can be attributed to converting sales. Existing proposals rely on users to locally store advertisement history on their browser and report attribution measurements to an aggregation service (instantiated with multiparty computation over non-colluding servers). The service computes and reveals the aggregate statistic. The service hides individual user contributions, but it does not guarantee integrity against misbehaving users that may submit fraudulent measurements. Our work proposes a new cryptographic primitive, "secret share attestation", in which secret shares input into a multiparty computation protocol are accompanied by an attestation of integrity by a third party: advertisers include signature attestations when serving ads that are later included in contributed measurements. We propose two constructions based on the standards-track BBS signatures and efficient signatures over equivalence classes, respectively. We implement and evaluate our protocols in the context of the advertising application to demonstrate their practicality.

Fault injection attacks (FIA) pose significant security threats to embedded systems as they exploit weaknesses across multiple layers, including system software, instruction set architecture (ISA), microarchitecture, and physical hardware. Early detection and understanding of how physical faults propagate to system-level behavior are essential to safeguarding cyberinfrastructure. This work introduces CRAFT, a framework that combines pre-silicon analysis with post-silicon validation to systematically uncover and analyze fault injection vulnerabilities. Our study, conducted on a RISC-V soft-core processor (cv$32$e$40$x) reveals two novel vulnerabilities. First, we demonstrate a method to induce instruction skips by glitching the clock (single-glitch attack), which prevents critical values from being loaded from memory, thus disrupting program execution. Second, we show a technique that converts a fetched legal instruction into an illegal one mid-execution, diverting control flow in a manner exploitable by attackers. Notably, we identified a specific timing window in which the processor fails to detect these illegal control-flow diversions, allowing silent, undetected corruption of the program state. By simulating $9248$ FIA scenarios at pre-silicon and conducting root-cause analysis of the RISC-V pipeline, we trace the faults to a previously unreported vulnerability in a pipeline register shared between the instruction fetch and decode stages. Our approach reduced the search space for post-silicon experiments by $97.31$\%, showing pre-silicon advantages for post-silicon testing. Finally, we validate our identified exploit cases on real hardware (FPGA).

The increasing use of multi-party computation (MPC) has spurred the design of symmetric key primitives specifically suited for MPC environments. Recently, weak pseudorandom functions (wPRFs) based on the alternating moduli paradigm have been proposed as a promising class of MPC-friendly primitives. The wPRF proposed at CRYPTO 2024, in its One-to-One parameter set, has been shown to be vulnerable to a key recovery attack dubbed Zeroed-Out, exploiting collisions in the queries. In this paper, we identify that the aforementioned wPRFs conform to a specific structure, called pointwise-keyed function, and further show a different, general key recovery attack. This method, applied to wPRFs in the One-to-One parameter set attacked by Zeroed-out, improves upon the complexity and achieves an attack with complexity below the birthday bound, and stays effective against the proposed countermeasures. For the first time, it succeeds in attacking one of the two Many-to-One parameter sets and stays effective against one of the proposed countermeasures. We also consider its applicability to the alternative wPRF of similar structure proposed by Boneh et al at TCC 2018.

The machine learning problem of model extraction was first introduced in 1991 and gained prominence as a cryptanalytic challenge starting with Crypto 2020. For over three decades, research in this field has primarily focused on ReLU-based neural networks. In this work, we take the first step towards the cryptanalytic extraction of PReLU neural networks, which employ more complex nonlinear activation functions than their ReLU counterparts. We propose a raw output-based parameter recovery attack for PReLU networks and extend it to more restrictive scenarios where only the top-m probability scores are accessible. Our attacks are rigorously evaluated through end-to-end experiments on diverse PReLU neural networks, including models trained on the MNIST dataset. To the best of our knowledge, this is the first practical demonstration of PReLU neural network extraction across three distinct attack scenarios.

Payment Channel Networks (PCNs) are the most scalable and trust-minimized solution to Bitcoin's scalability challenges. Within PCNs, connected payer and payee can make arbitrary off-chain transactions through multi-hop payments (MHPs), while intermediate relays charge relay fees by providing liquidity. However, current MHPs face critical security threats including fee-stealing attacks and griefing attacks. In this paper, we first identify new fee-stealing attacks targeting most existing MHP protocols. Then we demonstrate the impossibility of griefing resistance by reducing the griefing resistance MHP to a fair secret exchange problem. Finally, we introduce Zeus, the first Bitcoin-compatible MHP that is secure against fee-stealing attacks and offers bounded griefing protection against $k$-cost-sensitive adversaries—those who only launch griefing attacks when the damage exceeds a $k$ fraction of their cost. These guarantees are established through rigorous proofs in the Global Universal Composability (GUC) framework. Our comprehensive evaluation demonstrates that Zeus reduces worst-case griefing damage to 28% and 75% compared to MHP schemes such as AMHL~(NDSS'19) and Blitz~(USENIX SEC'21), respectively. Our results further show that, even under the most adverse configurations in the Lightning Network, Zeus ensures attackers incur costs at least 10x higher than potential damage.

The NIST Post-Quantum Cryptography (PQC) standardization has entered its fourth round, underscoring the critical importance of addressing side-channel attacks (SCA), a dominant threat in real-world cryptographic implementations, especially on embedded devices. This paper presents a novel chosen-ciphertext side-channel attack against CRYSTALS-Kyber (standardized as ML-KEM) implementations with Fisher-Yates shuffled polynomial reduction. We propose an efficient and fault-tolerant key recovery algorithm that, by crafting malicious ciphertexts, induces changes in the Hamming weight distribution of an intermediate polynomial's coefficients (the output of the shuffled polynomial reduction during decapsulation), enabling recovery of secret key coefficients from these changes. To ensure robustness, we propose an error-correction strategy that leverages the Hamming weight classifier's behavior to constrain and shrink the correction search space, maintaining effectiveness even with less accurate classifiers or in low-SNR environments. A Multi-Layer Perceptron (MLP) is employed for Hamming weight classification from side-channel traces, achieving 97.11% accuracy. We combine statistical analysis with explainable deep learning for precise trace segmentation during pre-processing. Experimental results demonstrate full key recovery with only an average of $10 + 354 \times 3$ ciphertext queries and a success rate of 97.98%, reducing the adversarial effort by 95.36% compared to contemporary bit-flip techniques. Although shuffling aims to disrupt temporal correlations, our results show that statistical features persist and leak through shuffled implementations. This work reveals enduring SCA risks in shuffled implementations and informs a broader reassessment of PQC side-channel resilience.

We are now entering an era where the large-scale deployment of anonymous credentials seems inevitable, driven both by legislation requiring age verification and the desire to distinguish humans from bots in the face of the proliferation of AI-generated content. However, the widespread deployment of anonymous credentials faces the same security and fraud concerns as existing credentials, but without the established techniques for securing them. For non-anonymous credentials on the web today, authentication is a continuous process in which servers collect large volumes of behavioral data to protect account holders (e.g., by detecting account compromise) or to combat fraudulent behavior. In this paper, we propose Continuous Anonymous Authentication (CAA) schemes and give a concrete construction and applications for preventing credential sharing and theft. CAA schemes allow us to move the server-side collection, storage, and processing of these behavioral signals to the client while maintaining privacy and integrity. CAA schemes support, on the client side, a number of common behavioral analysis tests and analytics both for determining fraudulent behavior and updating security policies. We implement a prototype, zk-Cookies, which runs in the browser, and supports common behavioral signals such as IP address and geolocation history, browser fingerprinting, and page view history. Using this, we build a prototype application for age verification based on legacy credentials (like passports). We implement these checks efficiently in zk-SNARKs, and also show how to securely implement differentially private behavioral analytics in a zk-SNARK. The simplest version of our construction can perform the computation for an update in under 200 ms.

Permutation and multiset checks underpin many SNARKs, yet existing techniques either incur superlinear prover time or rely on auxiliary commitments with soundness error that grows linearly in the input size. We present new arguments with linear-time provers and logarithmic soundness, without auxiliary commitments. Prior work achieving logarithmic soundness error arithmetizes the permutation as a product of several multilinear polynomials, a formulation chosen for compatibility with the classic Sumcheck PIOP. A simpler alternative treats permutations as multilinear extensions of their permutation matrices. While this formulation was previously believed to require quadratic prover time, we show that this overhead can be eliminated by taking a linear-algebraic perspective. This viewpoint has a key advantage: partially evaluating the multilinear polynomial of the permutation requires no additional field operations and amounts to applying the inverse permutation to the verifier's challenge vector. This makes the step essentially free in terms of algebraic cost, unlike in prior approaches. Compared to concurrent work BiPerm (Bünz et al., ePrint Archive, 2025), our scheme requires no permutation preprocessing and supports prover-supplied permutations. We show a sparsity-aware PCS like Dory (Lee, TCC, 2021) can compile our PIOP to a SNARK such that the resulting SNARK prover still runs in time $O(n)$. Our construction is the first logarithmically-sound SNARK with an $O(n)$-time prover for both permutation and multiset checks. We further prove a matching optimal prover lower bound, and we identify specific permutations that can be evaluated by the verifier in $O(\mathrm{polylog}(n))$-time. The ability to evaluate these permutations in $O(\mathrm{polylog}(n))$ time allows the verifier to avoid relying on prover-supplied commitments or evaluation proofs. As a result, we obtain the first logarithmically sound, field-agnostic SNARK with an $O(n)$-time prover in this setting.

Deniable authentication allows Alice to authenticate a message to Bob, while retaining deniability towards third parties. In particular, not even Bob can convince a third party that Alice authenticated that message. Clearly, in this setting Bob should not be considered trustworthy. Furthermore, deniable authentication is necessary for deniable key exchange, as explicitly desired by Signal and off-the-record (OTR) messaging. In this work we focus on (publicly verifiable) designated verifier signatures (DVS), which are a widely used primitive to achieve deniable authentication. We propose a definition of deniability against malicious verifiers for DVS. We give a construction that achieves this notion in the random oracle (RO) model. Moreover, we show that our notion is not achievable in the standard model with a concrete attack; thereby giving a non-contrived example of the RO heuristic failing. All previous protocols that claim to achieve deniable authentication against malicious verifiers (like Signal's initial handshake protocols X3DH and PQXDH) rely on the Extended Knowledge of Diffie–Hellman (EKDH) assumption. We show that this assumption is broken and that these protocols do not achieve deniability against malicious verifiers.

Existing PVSS schemes suffer from at least $O(n)$ online complexity due to the need to individually encrypt and prove/ verify each of the $n$ shares. In this work, we present a generic framework for constructing PVSS schemes with $O(1)$ complexity for share distribution and (the expected to be repeated numerous times) public verification. Our key insight lies in establishing a novel connection between PVSS and CCA2-Secure threshold encryption (CCATE), which enables public verifiability enforced by Non-Interactive Zero-Knowledge (NIZK) proofs. We show that a CCATE scheme can be generically transformed into a secure PVSS scheme, eliminating the $O(n)$ bottleneck per on-line operations. We instantiate the framework by presenting two CCATE constructions: 1) A pairing-free scheme based on a committee-based Distributed Key Generation (DKG) protocol and Threshold ElGamal encryption. 2) A silent setup scheme leveraging a non-interactive distributed key generation, relying on Power-of-Tau ceremony. Furthermore, we introduce solutions for dynamic membership updates in both DKG constructions, demonstrating their practicality and adaptability for real-world applications. The scheme is based on an off-line setup stage (before a specific value to share is given) where the $O(n)$ complexity is dealt with. Although our schemes incur higher setup costs, they drastically reduce the complexity of the critical distribution and verification stages to constant time. This trade-off marks a significant advancement in the scalability of PVSS-based systems, especially in the context of blockchain modern transactions. Conceptually, the work points out how variants of the notion of Threshold Encryption can potentially serve as a ``compression mechanism'' for information sharing schemes.

Germany is currently rolling out an opt-out, nation-scale database of the medical records of the majority of its population, with low-income people being disproportionally represented among its users. While there has been considerable criticism of the system coming from civil society, independent academic analysis of the system by the cryptography and information security community has been largely absent. In this paper, we aim to raise awareness of the system’s existence and, based on the system’s public specifications, highlight several concerning cryptographic engineering decisions. Our core observations is that the system’s most sensitive long-term user keys are derived by a rudimentary, home-grown centralized key escrow mechanism. This mechanism relies on a per-use salt and only 256 bit of entropy, shared globally across millions of users. Furthermore, the system’s specification mandates only level 3 compliance with the obsolete FIPS 140-2 security standard, which requires “hard, opaque potting”, but lacks active tamper sensing. As a result, the system remains vulnerable to attacks by nation states and other well-funded adversaries.

Security Meshes are patterns of sensing traces covering an area that are used in Hardware Security Modules (HSMs) and other systems to detect attempts to physically intrude into the device's protective shell. State-of-the-art solutions manufacture meshes in bespoke processes from carefully chosen materials, which is expensive and makes replication challenging. Additionally, state-of-the-art monitoring circuits sacrifice either monitoring precision or cost efficiency. In this paper, we present an embeddable security mesh monitoring circuit constructed from low-cost, standard components that utilizes Time Domain Reflectometry (TDR) to create a unique fingerprint of a mesh. Our approach is both low-cost and precise, and enables the use of inexpensive standard Printed Circuit Boards (PCBs) as security mesh material. We demonstrate a working prototype of our TDR circuit costing less than 10 € in components that achieves both time resolution and rise time better than 200 ps—a 25 × improvement over previous work. We demonstrate a simple classifier that detects several types of advanced attacks such as probing using an oscilloscope probe or micro-soldering attacks with no false negatives.

An anonymous credential (AC) system with partial disclosure allows users to prove possession of a credential issued by an issuer while selectively disclosing a subset of their attributes to a verifier in a privacy-preserving manner. In keyed-verification AC (KVAC) systems, the issuer and verifier share a secret key. Existing KVAC schemes rely on computationally expensive zero-knowledge proofs during credential presentation, with the presentation size growing linearly with the number of attributes. In this work, we propose two highly efficient KVAC constructions that eliminate the need for zero-knowledge proofs during the credential presentation and achieve constant-size presentations. Our first construction adapts the approach of Fuchsbauer, Hanser and Slamanig (JoC'19), which achieved constant-size credential presentation in a publicly verifiable setting using their proposed structure-preserving signatures on equivalence classes (SPS-EQ) and set commitment schemes, to the KVAC setting. We introduce structure-preserving message authentication codes on equivalence classes (SP-MAC-EQ) and designated-verifier set commitments (DVSC), resulting in a KVAC system with constant-size credentials (2 group elements) and presentations (5 group elements). To avoid the bilinear groups and pairing operations required by SP-MAC-EQ, our second construction uses a homomorphic MAC with a simplified DVSC. While this sacrifices constant-size credentials ($n+2$ group elements, where $n$ is the number of attributes), it retains constant-size presentations (2 group elements) in a pairingless setting. We formally prove the security of both constructions and provide open-source implementation results demonstrating their practicality. We extensively benchmarked our KVAC protocols and, additionally, bechmarked the efficiency of our SP-MAC-EQ scheme against the original SPS-EQ scheme, showcasing significant performance improvements.

Over the past decades, extensive research has been conducted on lightweight cryptographic primitives. The linear layer plays an important role in their security. In this paper, we propose a family of linear layers consisting of XORs and rotations, which is called multiple rows mixers (MRM). It is a family designed for LS-type ciphers, but mixing elements from several rows. We investigate the impact of the linear layers on the 3-round trail weight of permutations and explore the properties of the inverse of the linear layers with a low XOR count. We employ a generic and extensible approach to determine the parameters of MRM. This approach can automatically generate linear layers that meet the requirements of a given branch number. By applying these design principles and methods, we derive a linear layer that has a dimension of 5 × 64, a differential branch number of 12, a linear branch number of 5 and a computational cost of 2.6 XOR operations per bit. MRM is not limited to fixed dimension and can be extended to other dimensions. In addition, we present a concrete instantiation of a 320-bit permutation using a more efficient instance of MRM, named Hsilu. Its non-linear layer employs the χ operating on columns. Compared with the permutations of Gaston and NIST lightweight standard Ascon, the round function of Hsilu requires fewer XOR operations. Hsilu exhibits competitive security and performance with Ascon and Gaston. We demonstrate that the best-found 3-round differential and linear trails of Hsilu have much higher weights than those of Ascon. Hsilu outperforms Gaston and Ascon in terms of both software and hardware performance.

With the rise of in-vehicle and car-to-x communication systems, ensuring robust security in automotive networks is becoming increasingly vital. As the industry shifts toward Ethernet-based architectures, the IEEE 802.1AE MACsec standard is gaining prominence as a critical security solution for future in-vehicle networks (IVNs). MACsec utilizes the MACsec Key Agreement Protocol (MKA), defined in the IEEE 802.1X standard, to establish secure encryption keys for data transmission. However, when applied to 10BASE-T1S Ethernet networks with multidrop topologies, MKA encounters a significant challenge known as the real-time paradox. This paradox arises from the competing demands of prioritizing key agreement messages and real-time control data, which conflict with each other. Infineon addresses this challenge with its innovative In-Line Key Agreement (IKA) protocol. By embedding key agreement information directly within a standard data frame, IKA effectively resolves the real-time paradox and enhances network performance. This paper establishes a theoretical worst-case delay bound for key agreement in multidrop 10BASE-T1S IVNs with more than two nodes, using Network Calculus techniques. The analysis compares the MKA and IKA protocols in terms of performance. For a startup scenario involving a 16-node network with a 50 bytes MPDU size, the MKA protocol exhibits a worst-case delay that is 1080% higher than that of IKA. As the MPDU size increases to 1486 bytes, this performance gap narrows significantly, reducing the delay difference to just 6.6%.

Fault injection attacks target cryptographic primitives implemented in hardware by deliberately inducing faults, leading to abnormal behavior that can be exploited to extract sensitive information. To mitigate these threats, practical and low-overhead countermeasures, whether at the algorithmic or physical level, are essential. However, the real-world effectiveness of these countermeasures remains uncertain, as it is not always clear whether, or to what extent, their underlying security assumptions hold in practice. Therefore, a thorough evaluation under realistic attack scenarios, including recent techniques such as Electromagnetic Fault Injection (EMFI), is crucial. In this work, we demonstrate the resistance of a protected real-world target chip against EMFI. Specifically, our fabricated 65 nm CMOS ASIC employs concurrent error correction based on the techniques described in Impeccable Circuits II as an algorithm-level countermeasure. At the physical level, the chip integrates multiple coils of varying sizes and positions that serve as sensors for electromagnetic fields. We employ a practical and affordable attack setup featuring a commercial fault-injection probe mounted on an XYZ stage for precise positioning over the ASIC. This setup allows us to investigate the effects of various attack parameters, including the probe’s position, pulse polarity, and voltage level. Our results highlight that the coils serve as a lightweight and effective countermeasure for the practical detection of EMFI attempts. In contrast, for concurrent error correction, a gap between theory and practice emerges: the protection overhead actually makes such designs more susceptible to EMFI in real-world scenarios.

Aggregate signatures allow compressing multiple single-signer signatures into a single short aggregate signature. This primitive has attracted new attention due to applications in blockchains and cryptocurrencies. In multisig addresses, which is one of such applications, aggregate signatures reduce the sizes of transactions from multisig addresses. Security of aggregate signatures under adaptive corruptions of signing keys is important, since one of the motivations of multisig addresses was a countermeasure against signing key exposures. We propose the first aggregate signature scheme tightly secure under adaptive corruptions using pairings. An aggregate signature includes two source group elements of bilinear groups plus a bit vector whose length is equal to the number of single-signer signatures being aggregated. To construct a scheme, we employ a technique from quasi-adaptive non-interactive zero-knowledge arguments. Our construction can be seen as modularization and tightness improvement of Libert et al.'s threshold signature scheme supporting signature aggregation (Theoretical Computer Science 645) in a non-threshold setting.

The increased popularity of large language models (LLMs) raises serious privacy concerns, where users' private queries are sent to untrusted servers. Many cryptographic techniques have been proposed to provide privacy, such as secure multiparty computation (MPC), which enables the evaluation of LLMs directly on private data. However, cryptographic techniques have been deemed impractical as they introduce large communication and computation. On the other hand, many obfuscation techniques have been proposed, such as split inference, where part of the model is evaluated on edge devices to hide the input data from untrusted servers, but these methods provide limited privacy guarantees. We propose Fission, a privacy-preserving framework that improves latency while providing strong privacy guarantees. Fission utilizes an MPC network for linear computations, while nonlinearities are computed on a separate evaluator network that receives shuffled values in the clear and returns nonlinear functions evaluated at these values back to the MPC network. As a result, each evaluator only gets access to parts of the shuffled data, while the model weights remain private. We evaluate fission on a wide set of LLMs and compare it against prior works. Fission results in up to eight times faster inference and eight times reduced bandwidth compared to prior works while retaining high accuracy. Finally, we construct an attack on obfuscation techniques from related works that show significant information leakage, and we demonstrate how Fission enhances privacy.

Verifiable Computation over encrypted data (VCoed) has two popular paradigms: SNARK-FHE (applying SNARKs to prove FHE operations) and FHE-SNARK (homomorphically evaluating SNARK proofs). For the existing works, FHE-SNARK has a much better efficiency compared to SNARK-FHE. In this work, we follow the line of FHE-SNARK and further improve its efficiency by designing Phalanx—an FHE-friendly SNARK that is: a) 3× lower multiplicative depth than FRI-based SNARKs; and b) Compatible with FHE SIMD operations. Based on Phalanx, we construct an FHE-SNARK scheme that has: a) $7.3×\sim 24.4×$ speedup: 2.27-hour proof generation for $2^{20}$-gate circuits on a single core CPU and 0.68-hour when the input ciphertexts are in iNTT form (vs. 16.57 hours in the state-of-the-art); and b) Practical verification: 61.4 MB proofs with 2.8 seconds verification (single core).

The European Commission's 2022 proposal for a regulation on child sexual abuse material, popularly labelled ChatControl, obliges online services to detect, report, and remove prohibited content, through client-side scanning. This paper examines the proposal as a case of undone science in computer security ethics: a domain where technical feasibility and rights-compatibility questions remain systematically underexplored. Combining legal analysis with philosophy of technology, the paper argues that client-side scanning transforms end-to-end encryption from a right to secrecy into a conditional privilege of use. By integrating Isaiah Berlin's concept of negative liberty, Langdon Winner’s account of the politics of artifacts, and David Hess’s notion of undone science, the analysis traces how design choices become moral constraints. The discussion situates the European debate within broader concerns about proportionality, epistemic selectivity, and the governance of digital infrastructures. Ultimately, the study shows that the controversy over ChatControl is not only about privacy or child protection but about the epistemic norms that define what counts as legitimate technological knowledge.

We consider reversely-degraded wiretap channels, for which the secrecy capacity is zero if there is no channel feedback. This work focuses on a seeded modular code design for the Gaussian wiretap channel with channel output feedback, combining universal hash functions for security and learned feedback-based codes for reliability to achieve positive secrecy rates. We study the trade-off between communication reliability and information leakage, illustrating that feedback enables agreeing on a secret key shared between legitimate parties, overcoming the security advantage of the wiretapper. Our findings also motivate code designs for sensing-assisted secure communication, to be used in next-generation integrated sensing and communication methods.

Distributed randomness beacon protocols, which continuously generate publicly verifiable randomness values, are crucial for many applications. Recently, there have been many approaches, such as Hydrand (S\&P'20), SPURT (S\&P'22), OptRand (NDSS'23) and GRandLine (CCS'24), based on publicly verifiable secret sharing (PVSS) to implement beacon protocols. However, two key challenges remain unresolved: asynchrony and reconfiguration. In this paper, we propose the $\mathsf{AsyRand}$ beacon protocol to address these challenges. We incorporate a producer-consumer model to decouple the distribution and reconstruction of PVSS secrets. Parties continuously produce and distribute new PVSS commitments, which are the encrypted shares and the proofs. Meanwhile, all parties store received commitments using first-in-first-out queues and collectively consume each commitment to recover the corresponding secret for beacon generation. To achieve asynchronous consensus, we employ reliable broadcast for distribution and apply $t$-validated asynchronous Byzantine agreement for reconstruction. To achieve reconfiguration, honest parties can collectively remove a faulty party if his queue remains empty for an extended duration, and a new party can join the system using reliable broadcast. We also introduce a novel PVSS scheme based on Sigma protocol and Fiat-Shamir heuristic, which is of independent interest. Consequently, $\mathsf{AsyRand}$ maintains state-of-the-art complexity with $O(n^2)$ communication complexity, $O(n)$ computation complexity, and $O(n)$ verification complexity while achieving asynchrony and reconfiguration. Experimental results highlight the performance of $\mathsf{AsyRand}$ compared to existing works.

In Private Information Retrieval (PIR), a client wishes to retrieve the value of an index $i$ from a public database of $N$ values without leaking information about the index $i$. In their recent seminal work, Corrigan-Gibbs and Kogan (EUROCRYPT 2020) introduced the first two-server PIR protocol with sublinear amortized server time and sublinear, $O(\sqrt{N}\log N)$ bandwidth. In a followup work, Shi et al. (CRYPTO 2021) reduced the bandwidth to polylogarithmic by proposing a construction based on privately puncturable pseudorandom functions, a primitive whose only construction known to date is based on heave cryptographic primitives. Partly because of this, their PIR protocol does not achieve concrete efficiency. In this paper we propose TreePIR, a two-server PIR protocol with sublinear amortized server time and polylogarithmic bandwidth whose security can be based on just the DDH assumption. TreePIR can be partitioned in two phases, both sublinear: The first phase is remarkably simple and only requires pseudorandom generators. The second phase is a single-server PIR protocol on \emph{only} $\sqrt{N}$ indices, for which we can use the protocol by D\"ottling et al. (CRYPTO 2019) based on DDH, or, for practical purposes, the most concretely efficient single-server PIR protocol. Not only does TreePIR achieve better asymptotics than previous approaches while resting on weaker cryptographic assumptions, but it also outperforms existing two-server PIR protocols in practice. The crux of our protocol is a new cryptographic primitive that we call weak privately puncturable pseudorandom functions, which we believe can have further applications.

Homomorphic encryption (HE) is a foundational technology in privacy-enhancing cryptography, enabling computation over encrypted data. Recently, generalized HE primitives designed for multi-party applications, such as multi-party HE (MPHE), have garnered significant research interest. While constructing secure multi-party protocols from MPHE in the semi-honest model is straightforward, achieving malicious security remains challenging as it requires zero-knowledge arguments of knowledge (ZKAoKs) for MPHE ciphertexts and public keys. In this work, we design practical ZKAoKs for MPHE that validate the well-formedness of public keys and ciphertexts. Specifically, we develop our ZKAoKs within the polynomial interactive oracle proof (PIOP) framework. To achieve this, we introduce novel optimization techniques that seamlessly integrate constraints for MPHE into the PIOP framework, enabling the design of PIOPs for validating all types of MPHE public keys, including relinearization and automorphism keys. To the best of our knowledge, our construction is the first ZKAoK for MPHE that validates automorphism keys. We instantiate our PIOP using a lattice-based polynomial commitment scheme (PCS). When compared with the previous state-of-the-art construction, PELTA (CCS' 2023), our implementation achieves a 5.4x reduction in proof size, a 111x speed-up in proof generation, and a 768x improvement in verification time for validating the encryption key. In addition to the encryption key, we provide benchmark results for all types of ZKAoKs required for MPHE, presenting the first concrete performance results in compiling passively secure MPHE-based protocols into maliciously secure ones.

Proof systems of arbitrary computations have found many applications in recent years. However, the proving algorithm has a consequent complexity tied to the size of the computation being proved. Thus, proving large computations is quite inefficient. One of these large computations is the scalar multiplication over an elliptic curve. In this work, we provide new techniques for reducing the time corresponding to proving a scalar multiplication, using integer lattice reduction or a (half) extended Euclidean algorithm in a ring of integers. We investigate optimizations in the case of small (complex multiplication) discriminant curves, and its generalization for multi scalar multiplications as used in signature verification. We provide an optimized Golang implementation for different elliptic curves in different proof systems settings. The speed-up in proving time is between 22% and 53% compared to the previous state-of-the-art.

Homomorphic Encryption (HE) allows parties to securely outsource data while enabling computation on encrypted data, protect- ing against malicious parties and data leakages. More recent HE schemes enable approximate arithmetic on complex vectors and approximation of non-linear functions, specifically useful for image processing algorithms. The Fourier Shape Descriptor (FSD) is a classical method for shape matching via frequency-domain representation, and we show that FSD can be computed entirely in the encrypted domain. To the best of our knowledge, this is the first work to implement secure shape descriptors and matching via HE. We also present two experiments for similar and different shapes, and measure the performance of the encrypted algo- rithm.

Function Secret Sharing (FSS) schemes enable to share secret functions between multiple parties, with notable applications in anonymous communication and privacy-preserving machine learning. While two-party schemes offer logarithmic key sizes, multi-party schemes remain less practical due to significantly larger keys. Although several approaches have been proposed to improve multi-party schemes, a significant efficiency gap remains between the two-party and multi-party settings. Our work introduces noisy FSS: a relaxation of FSS preserving the standard privacy guarantees but relaxing the correctness definition by allowing a small amount of noise in the output. We formally define noisy FSS and show how the noise introduced by the scheme can be leveraged to provide differential private outputs in statistics applications. To demonstrate the benefits of this relaxation, we adapt a scheme proposed by Corrigan-Gibbs et al. (S&P'15). While their scheme provides the smallest key sizes among multi-party schemes, they do not support some applications notably in statistics due to their non-linear share decoding. On the contrary, recent works such as Goel et al. (CRYPTO'25) have larger keys, but support all FSS applications. Our noisy adapted scheme offers the best of both worlds by matching the best key sizes, while providing the properties necessary to statistics applications.

Masking is one of the most widespread countermeasures against side-channel attacks. However, its integration into hardware implementation is subject to physical hazards that can mitigate its security. To counter glitches, the most studied physical hazard, an effective solution is to resynchronize the signals by integrating additional hardware layers into the architecture. However, these solutions have an impact on the performance of the implementation. A solution to avoid these limitations is to use more shares to compute higher-degree functions. We study the cost of this approach, denominated ($td+n$)-masking. We first derive optimal dependence structures for the creation on non-complete sharings, which allow us to obtain efficient implementation of substitution boxes. As a case study, we use these elements to create a second-order masked architecture for the PRESENT cipher. We perform multiple TVLA tests to validate our approach. Our results confirm that the strategy is efficient in terms of performance, at the cost of increased hardware resources.

We present a new distinguisher for alternant and Goppa codes, whose complexity is subexponential in the error-correcting capability, hence better than that of generic decoding algorithms. Moreover it does not suffer from the strong regime limitations of the previous distinguishers or structure recovery algorithms: in particular, it applies to the codes used in the Classic McEliece candidate for postquantum cryptography standardization. The invariants that allow us to distinguish are graded Betti numbers of the homogeneous coordinate ring of a shortening of the dual code. Since its introduction in 1978, this is the first time an analysis (in the CPA model) of the McEliece cryptosystem breaks the exponential barrier.

We propose an efficient fully homomorphic encryption (FHE) scheme tailored for matrix arithmetic based on the Ring-Learning with Errors (RLWE) problem. The proposed scheme naturally supports matrix multiplication, addition, and Hadamard multiplication for batched matrices of various sizes over both complex numbers and integers. Encrypted matrix multiplication is reduced to four matrix multiplications of ciphertext elements, without the need for expensive operations such as slot-to-coefficient conversion or ring switching. In addition, the scheme efficiently supports matrix transformations, including general and conjugate transpositions, as well as matrix rotations: inter-matrix rotations across batched matrices and intra-matrix rotations within rows and columns. Moreover, the proposed FHE scheme can be directly combined with existing bootstrapping algorithms. By eliminating the need for expensive operations such as repeated slot rotations and conversion between slot- and coefficient-encoding, the proposed construction achieves significant performance improvements. In our construction, encrypted multiplications of $n\times n$ matrices under slot encoding are decomposed into two parts: (1) matrix multiplication — four $n\times n$ matrix multiplications of ciphertext coefficients, and (2) key switching — with a total cost approximately 2–4 times that of Hadamard multiplication. We implemented the proposed scheme and utilized the FLINT library for the matrix multiplication component. Experimental results demonstrate that, even when leveraging highly optimized implementations, matrix multiplication remains the major cost, indicating that our construction substantially reduces auxiliary overheads and achieves strong overall efficiency.

Non-Interactive Timed Commitment schemes (NITC) allow to open any commitment after a specified delay. This is useful for sealed bid auctions and as primitive for more complex protocols. We present the first NITC without repeated squaring or black box algorithms like generic NIZK proofs or generic one-way functions. It has fast verification, almost arbitrary delay and satisfies IND-CCA hiding and perfect binding. Our protocol is based on isogenies between supersingular elliptic curves making it presumably quantum secure. It needs no trusted setup and can use a wide variety of primes. We also have a SageMath implementation.

This work presents a RISC-V extension for Post-Quantum Cryptography (PQC) called HORCRUX, which provides a unified Instruction-Set Extension (ISE) supporting all NIST-approved PQC algorithms. HORCRUX addresses the current fragmentation in hardware support, where existing extensions typically focus on individual algorithms or limited subsets of PQC schemes, and targets the common kernels shared across ML-KEM, ML-DSA, SLH-DSA, and HQC. To address the primary computational bottlenecks of all these algorithms (namely, modular arithmetic, matrix multiplication, and hash transformations), the extension introduces new RISC-V instructions executed by a tightly coupled coprocessor. This coprocessor requires only minimal hardware resources, making the architecture efficient for constrained devices while still providing substantial acceleration. An experimental evaluation on a Zynq UltraScale+ FPGA demonstrates speedups of up to 3× for lattice and hash-based schemes, and over 30× for code-based schemes, while adding less than 2,900 LUTs and 400 FFs to the design. The extension’s modular structure maintains backward compatibility with standard RISC-V cores, offering a scalable solution for deploying PQC on highly constrained embedded systems.

A Threshold Fully Homomorphic Encryption (ThFHE) scheme enables the generation of a global public key and secret key shares for multiple parties, allowing any threshold of these parties to collaboratively decrypt a ciphertext without revealing their individual secret keys. By leveraging the homomorphic properties of FHE, this scheme supports the distributed computation of arbitrary functions across multiple parties. As distributed execution of cryptographic tasks becomes popular, the demand for ThFHE schemes grows accordingly. We identify three major challenges with existing solutions. (i) They often take unrealistic assumptions with regards to the network model, assuming the threshold of parties to participate in decryption is known a-priori, available throughout multiple communication rounds, and is consistent between parties. (ii) They incur a super-linear overhead on the underlying FHE public parameters. Both issues pose challenges on scaling with the number of parties. (iii) They require heavyweight Zero-Knowledge Proofs (ZKPs) during decryption, thereby introducing a significant computational overhead in order to tolerate malicious behavior. In this work, we introduce a ThFHE scheme that faces the above three challenges and is designed to scale with the number of parties N. Our scheme operates within the well-established asynchronous communication model. At the same time, upon decryption, the ciphertext only incurs a linear (3/4)N + t additive overhead on the ciphertext modulus size. Additionally, when allowed to rely on non-Post-Quantum (PQ) secure additively homomorphic encryption schemes, we provide a method with an O(1) overhead, independent of N. Lastly, we propose a preprocessing technique that allows the parties to batch and preprocess all necessary ZKPs in an offline phase before the encrypted inputs and evaluation circuit are determined. In turn, this enables the system to effectively manage traffic spikes by exploiting idle periods to perform the ZKPs. We build on a ring-based FHE scheme, specifically using the BGV scheme for clarity and concreteness. Nonetheless, the techniques also apply to BFV, CKKS, and TFHE schemes.

Multi-key fully homomorphic encryption (MKFHE) extends the capability of fully homomorphic encryption by enabling homomorphic computations on ciphertexts encrypted under different keys. Multi-key blind rotation is the core and most computationally intensive component of MKFHE. The NTRU-based multi-key blind rotation proposed by Xiang et al. (ASIACRYPT 2024) has the potential to achieve smaller key sizes, faster blind rotation, and lower noise compared to its RLWE-based counterpart. However, while the multi-key blind rotation in the RLWE-based scheme proposed by Kwak et al. (PKC 2024) remains compatible with their single-key counterpart, the NTRU-based versions do not. This motivates our work to advance NTRU-based schemes in both efficiency and compatibility. We propose a novel workflow for NTRU-based multi-key blind rotation that achieves compatibility with its single-key counterpart. Our approach significantly reduces both computational and storage complexity compared to the state-of-the-art NTRU-based design, while maintaining a comparable noise magnitude. Building upon this workflow, we further construct two MKFHE schemes for bootstrapping multi-key LWE ciphertexts and multi-key matrix NTRU ciphertexts, both supporting a super-constant number of parties with respect to the ring dimension $N$. Experimental results demonstrate that our method outperforms existing NTRU-based bootstrapping for TFHE-like MKFHE in both computational efficiency and bootstrapping key size. Specifically, our 2-key gate bootstrapping takes only 26ms and requires a bootstrapping key of size 7.34MB, achieving a 3.1× speedup and a 1.9× key size reduction compared to prior NTRU-based works.

Prange's information set algorithm is a decoding algorithm for arbitrary linear codes. It decodes corrupted codewords of any $\mathbb{F}_2$-linear code $C$ of message length $n$ up to relative error rate $O(\log n / n)$ in $\mathsf{poly}(n)$ time. We show that the error rate can be improved to $O((\log n)^2 / n)$, provided: (1) the decoder has access to a polynomial-length advice string that depends on $C$ only, and (2) $C$ is $n^{-\Omega(1)}$-balanced. As a consequence we improve the error tolerance in decoding random linear codes if inefficient preprocessing of the code is allowed. This reveals potential vulnerabilities in cryptographic applications of Learning Noisy Parities with low noise rate. Our main technical result is that the Hamming weight of $Hw$, where $H$ is a random sample of *short dual* codewords, measures the proximity of a word $w$ to the code in the regime of interest. Given such $H$ as advice, our algorithm corrects errors by locally minimizing this measure. We show that for most codes, the error rate tolerated by our decoder is asymptotically optimal among all algorithms whose decision is based on thresholding $Hw$ for an arbitrary polynomial-size advice matrix $H$.

Lattice-based key-homomorphic encodings introduced by Boneh et al.~(Eurocrypt'14)---known as BGG+ encodings---underpin many primitives, including key-policy attribute-based encryption (KP-ABE). Many applications beyond KP-ABE require simulating the homomorphic evaluation of FHE ciphertexts over BGG+ encodings, which involves nonlinear operations on integers of magnitude up to the ciphertext modulus $q$. However, due to noise growth incurred by multiplication, the encodable integers must be kept small, typically bits, thereby forcing nonlinear operations to be simulated by Boolean circuits and incurring a circuit-size blow-up polynomial in $\log_2 q$. Apart from resorting to costly bootstrapping for BGG+ encodings, no method is known to beat this baseline. We propose a method to evaluate lookup tables~(LUTs) over BGG+ encodings that operates directly on base-$B$ digit representations for $2<B<\sqrt{q}$, with noise growth independent of the magnitudes of the encoded integers. Consequently, this replaces the $\log_2 q$ factor in the circuit-size blow-up with $\log_{B} q$, yielding a reduction in evaluation time by a factor polynomial in $\log_2 B$. We obtain: (i) small-integer arithmetic with base-$B$ outputs in constant size; (ii) modulo-$q$ multiplication with circuit size quadratic in $\log_{B} q$; and (iii) homomorphic ciphertext multiplication in the Gentry--Sahai--Waters FHE scheme~(Crypto'13) with circuit size approximately cubic in $\log_{B} q$. As an application, we build a KP-ABE scheme that is selectively secure under the Ring-LWE assumption and compatible with our LUT evaluation method. This reduces decryption cost by a factor polynomial in $\log_2 B$ at the expense of a polynomial-in-$B$ increase in decryption-key generation cost and decryption-key size, which is an attractive trade-off because decryption is invoked far more frequently than key generation in ABE applications.

We present a novel homomorphic trace evaluation algorithm $\mathsf{RevHomTrace}$, which mitigates the phase amplification problem that comes with the definition of the field trace. Our $\mathsf{RevHomTrace}$ overcomes the phase amplification with only a negligible computational overhead, thereby improving the usability of the homomorphic field trace algorithm. Moreover, our tweak also improves the noise propagation of the $\mathsf{HomTrace}$ and breaks the traditional $O(N^{3})$ variance bound in previous works into $O(N \log N)$. Our experimental results obtained by integrating $\mathsf{RevHomTrace}$ into state-of-the-art homomorphic encryption algorithms further demonstrate the usefulness of our algorithm. Specifically, $\mathsf{RevHomTrace}$ improves the noise accumulation of the (high precision) circuit bootstrapping, which also achieves maximal $1.30\times$ speedup by replacing the costly high precision trace evaluation. Also, based on our idea of $\mathsf{RevHomTrace}$, we present a low latency, high precision LWE-to-GLWE packing algorithm $\mathtt{MS}$-$\mathtt{PackLWEs}$. We also show that our $\mathtt{MS}$-$\mathtt{PackLWEs}$ significantly reduces the packing error without severe degradation of performance.

At CHES 2017, Banik et al. proposed a lightweight block cipher GIFT consisting of two versions GIFT-64 and GIFT-128. Recently, there are lots of authenticated encryption schemes that adopt GIFT-128 as their underlying primitive, such as GIFT-COFB and HyENA. To promote a comprehensive perception of the soundness of the designs, we evaluate their security against differential-linear cryptanalysis. For this, automatic tools have been developed to search differential-linear approximation for the ciphers based on S-boxes. With the assistance of the automatic tools, we find 13-round differential-linear approximations for GIFT-COFB and HyENA. Based on the distinguishers, 18-round key-recovery attacks are given for the message processing phase and initialization phase of both ciphers. Moreover, the resistance of GIFT-64/128 against differential-linear cryptanalysis is also evaluated. The 12-round and 17-round differential-linear approximations are found for GIFT-64 and GIFT-128 respectively, which lead to 18-round and 19-round key-recovery attacks respectively. Here, we stress that our attacks do not threaten the security of these ciphers.

The generic group model (GGM) is fundamental for evaluating the feasibility and limitations of group-based cryptosystems. Two prominent versions of the GGM exist in the literature: Shoup's GGM and Maurer's GGM. Zhandry (CRYPTO 2022) points out inherent limitations in Maurer's GGM by demonstrating that several textbook cryptographic primitives, which are provably secure in Shoup's GGM, cannot be proven secure in Maurer's model. In this work, we further investigate Shoup's GGM and identify novel limitations that have been previously overlooked. Specifically, to prevent generic algorithms from generating valid group elements without querying the oracle, the model typically employs sufficiently large encoding lengths. This leads to sparse encodings, a setting referred to as the sparse generic group model (sparse GGM). We emphasize that this sparseness introduces several constraints: --Groups with AE and Black-Box Separation: Shoup's GGM is typically instantiated with elliptic curve groups, which admit admissible encodings (AE)—functions mapping from Z_N to elliptic curve points. We establish a black-box separation, showing that the sparse GGM fails to capture cryptographic groups that are both (1) computational Diffie-Hellman (CDH) secure and (2) compatible with admissible encodings. --Comparison with EC-GGM: We examine the relationship between the sparse GGM and the Elliptic Curve Generic Group Model (EC-GGM) introduced by Groth and Shoup (EUROCRYPT 2022), which inherently yields CDH-secure groups with admissible encodings. Within the framework of indifferentiability, we prove that EC-GGM is strictly stronger than sparse GGM. --Dense Groups and Black-Box Separation: We revisit groups with dense encodings and establish a black-box separation between CDH-secure dense groups and the sparse GGM. --Extension to Bilinear Settings: Our results naturally extend to the sparse Generic Bilinear Group Model (GBM), demonstrating that the aforementioned constraints still hold. In conclusion, our findings indicate that both feasibility and impossibility results in Shoup's GGM should be reinterpreted in a fine-grained manner, encouraging further exploration of cryptographic constructions and black-box separations in EC-GGM or dense GGM.

Privacy is a growing concern for smart contracts on public ledgers. In recent years, we have seen several practical systems for privacy-preserving smart contracts, but they only target privacy of on-chain data, and rely on trusted off-chain parties with user data -- for instance, a decentralized finance application (e.g. exchange) relies on an off-chain matching engine to process client orders that get settled on-chain, where privacy only applies to the on-chain data. Privacy conscious users demand stronger notions of privacy, for their identity and their data, from all other parties in the ecosystem. We propose a novel framework for smart contracts that ensures {\em doubly private} execution, addressing {both on-chain and off-chain privacy} requirements. In our framework, clients submit their requests in a privacy-preserving manner to a group of (potentially mutually untrusting) servers. These servers collaboratively match client requests without learning any information about the data or identities of the clients. We then present {\em Jigsaw}, an efficient cryptographic realization of our proposed framework. {\em Jigsaw} builds on the ZEXE architecture (Bowe et al., S\&P 2020), which leverages zkSNARKs, and extends Collaborative zkSNARKs (Ozdemir and Boneh, USENIX 2022) to enable proof generation by a group of servers. In Jigsaw, we introduce a novel collaborative zkSNARK construction that achieves low latency and reduced proving time, and showcase these advantages over sample applications ranging from trading in a decentralized exchange to auctions and voting. Our experiments demonstrate that {\em Jigsaw} is roughly $40-50$x faster in proof generation and uses orders-of-magnitude less bandwidth than the naive approach of using off-the-shelf Collaborative zkSNARKs.