International Association
for Cryptologic Research

Mosca introduced three crucial aspects for real-world cryptography in the quantum computing era: security shelf-life, migration time, and collapse time. While collapse time has been extensively studied, migration time has not received as much attention. Acknowledging the complexity of post-quantum cryptography (PQC) migration, NIST launched the `Migration to Post-Quantum Cryptography' project in June 2022. Migration to PQC involves three primary tasks: inventorying the use of cryptography, analyzing risks and determining migration priorities, and executing migration to PQC. The two tasks of inventorying and migration, in particular, demand capabilities of cryptographic visibility and cryptographic agility, respectively. This is especially important for enterprises that own and maintain numerous IT systems for migration at scale. While participating in NIST's `Migration to PQC' project, we investigated the possibility of using existing open sources to obtain cryptographic visibility and agility. More specifically, we modified or extended the features of existing open-source tools in the DevOps pipeline for automated inventorying of cryptographic usage, and also demonstrated changing cryptographic providers without altering applications making use of the well-designed Java Cryptography Architecture. We have gained a clearer understanding and several findings regarding migration to PQC, and this talk will provide insights for IT service providers as well as open-source community regarding PQC migration. Next, we briefly describe how we can make use of existing tools to gain cryptographic visibility and agility.

Secure 2-party computation (2PC) enables secure inference that offers protection for both proprietary machine learning (ML) models and sensitive inputs to them. However, the existing secure inference solutions suffer from high latency and communication overheads, particularly for transformers. Function secret sharing (FSS) is a recent paradigm for obtaining efficient 2PC protocols with a preprocessing phase. We provide SIGMA, the first end-to-end system for secure transformer inference based on FSS. By constructing new FSS-based protocols for complex machine learning functionalities, such as Softmax and GeLU, and also accelerating their computation on GPUs, SIGMA improves the latency of secure inference of transformers by 11 − 19× over the state-of-the-art that uses preprocessing and GPUs. We present the first secure inference of generative pre-trained transformer (GPT) models. In particular, SIGMA executes GPT-Neo with 1.3 billion parameters in 7.4s and HuggingFace’s GPT2 in 1.6s.

Security critical software comes with numerous side-channel leakages left unpatched due to a lack of resources or experts. The situation will only worsen as the pace of code development accelerates, with developers relying on Large Language Models (LLMs) to automatically generate code. In this work, we explore the use of LLMs in generating patches for vulnerable code with microarchitectural side-channel leakages. For this, we investigate the generative abilities of powerful LLMs by carefully crafting prompts following a zero-shot learning approach. All generated code is dynamically analyzed by leakage detection tools which are capable of pinpointing information leakage at the instruction level leaked either from secret dependent accesses or branches or vulnerable Spectre gadgets, respectively. Carefully crafted prompts are used to generate candidate replacements for vulnerable code which are then analyzed for correctness and for leakage resilience. After extensive experimentation, we determined that the way prompts are formed and stacked over a series of queries plays a critical role in the LLMs' ability to generate correct and leakage-free patches. We develop a number of tricks to improve the chances of correct and side-channel secure code. Moreover, when we compare various LLMs, we found that OpenAI's GPT4 is far superior compared to Google PaLM and Meta LLaMA in generating patches with nearly all leakages fixed in a microbenchmark of vulnerable codes as well as Spectre v1 gadgets. We also found that GPT4 is more successful than GPT3.5 in generating both correct and secure code, with many failed attempts observed in the latter. As for efficiency, GPT4 provides a far more efficient patch with up to 10 times less overhead when compared to the clang compiler-supported lfence Spectre mitigation. The GPT4-based configuration costs in API calls a mere few cents per vulnerability fixed.

Recent progress in large language models (LLMs) has led to demand for measures to detect AI-generated text, as evidenced by Biden's recent executive order, and pledges by several major companies to embed watermarks in the outputs of their models. A promising and popular solution for detecting AI-generated content is watermarking, where a hidden signal is embedded in the LLM's output. Intuitively, desirable properties of LLM watermarks are clear: they should not hurt the quality of the model, and human-generated text should not be falsely flagged as watermarked. However, these properties are challenging to define because of idiosyncracies in human text and a lack of a clear text quality measure, especially when LLMs have a wide variety of downstream applications. In [CGZ23], we show how {cryptography} can be leveraged to formally define these properties of quality and lack of false positives, which we call undetectability and soundness. Undetectability requires that no efficient algorithm can distinguish between the original LLM and the watermarked LLM. Soundness requires that any fixed text is detected as watermarked with negligible probability. [CGZ23] constructs a fairly simple watermarking scheme that achieves these properties. In this talk, we begin by giving background on policy discussion and media coverage surrounding detection of AI-generated text. We then present our work in [CGZ23], in particular covering the model, definitions, and scheme. We conclude by discussing directions for future work, emphasizing interesting cryptographic questions.

Deployment of end-to-end encryption (E2EE) has improved the confidentiality and the integrity of data in various contexts, including messaging, cloud storage, and other web applications. E2EE protocols, such as messaging and file storage, have been studied extensively, instilling confidence in their security. Consequently, there has been a meteoric rise in the adoption of these tools, and E2EE is now a core component of complex systems that impact billions of users. As these applications evolve into intricate, feature-rich ecosystems, our understanding of their security becomes increasingly opaque, and whether the strong security guarantees of the underlying E2EE protocols extend to the broader systems is unclear. As such, a new line of work has analyzed the security of various deployed E2EE applications, finding numerous attacks and proposing mitigations. The purpose of this talk is to bring attention to an emerging threat model for E2EE applications, and motivate future work within the cryptography community. At a high-level, our threat model considers an adversary that simply sends chosen payloads to a victim client, and subsequently observes the encrypted application state. We refer to attacks in this setting as injection attacks. The core of our presentation will consist of an overview of this threat model, highlighting a common root cause of injection attacks. Then, we will present concrete vulnerabilities uncovered in real-world systems across two application domains: backups of messaging applications (based on a recent paper that we will present at S&P ‘24), and password managers (based on ongoing work, which will be made public after we finish the disclosure process). Lastly, we conclude with some general takeaways and directions for future work.

In 2020, the Federal Communications Commission (FCC) began mandating the adoption of the STIR/SHAKEN protocol by all telephone service providers operating in the United States. This protocol aims to reduce the number of fraudulent robocalls by creating a reputation system for providers, disincentivizing providers from permitting fraudulent calls to originate from their network. This talk will discuss our ongoing study of the privacy implications of STIR/SHAKEN. Our study has uncovered severe privacy issues stemming from the design and implementation of the cryptography in STIR/SHAKEN. Notably, STIR/SHAKEN requires, for every call, highly sensitive call metadata (e.g., caller and callee numbers) to be signed in a cryptographically non-repudiable way and transmitted unencrypted between providers; this gives anyone the ability to cryptographically assert a call took place. Further, because third-party signing-as-a-service is widespread, this highly sensitive metadata is often revealed to off-path third parties. The talk will give the relevant background on telephony and STIR/SHAKEN, describe these privacy issues in detail, and discuss our ongoing research on solutions. We will also highlight unusual real-world cryptography challenges that arise, such as blind verification for signatures.

No abstract

Encrochat was a communications network and service provider that offered modified Android smartphones offering end-to-end encrypted communication based on the Signal protocol. In 2020, French law enforcement — in collaboration with agencies in the UK and the Netherlands as well as the European Agency for Law Enforcement Cooperation (Europol) — compromised the Encrochat network and exfiltrated historical data as well as real-time messaging data and metadata for weeks. The compromise remained undetected for approximately two months, after which Encrochat administrators shut down the network. Encrochat was used by organised crime groups in Europe (and elsewhere), and the exfiltrated information was used as supporting evidence in over 6000 arrests and related prosecutions across Europe; the information also led to the seizure or freezing of over 900 million euros as criminal funds, and the seizure of hundreds of tonnes of illegal drugs. The London Metropolitan Police, which made use of the intelligence gathered, described this as “the most significant operation the Metropolitan Police Service has ever launched against serious and organised crime”. In this talk, we examine what is known about how Encrochat was compromised, and how we know what we know at this time. In particular, we will discuss: the security and cryptography features used in Encrochat; what is currently known about how law enforcement breached the Encrochat network in 2020 and a potential earlier compromise; how we pieced together what is currently known from public sources such as historical Internet data, court records, and news reports; and legal, practical, and social limitations on the attack.

In Fall 2021, the president of Museums Moving Forward (MMF) approached us, cryptographers at Boston University, about using MPC to support one of their new projects. In this talk, we will share the story of the resulting deployment of MPC for social good. While our talk will cover the technical details of features we developed in the web-based JIFF framework in response to MMF’s needs, our primary focus will be the lessons that we learned about deploying MPC for social good throughout the process. Working collaboratively across disciplinary boundaries required developing shared language, bridging epistemological gaps, and designing new MPC features on the fly to recover from mistakes. Our goal is to uncover the messiness that usually gets suppressed in technical write-ups of cryptographic deployments. Understanding these pitfalls is critical for the continued growth of MPC and indispensable for cryptographers developing working relationships with non-technical stakeholder groups.

No abstract

In this talk, we describe PQXDH, a new post-quantum key agreement protocol deployed by Signal, its formal analysis using the ProVerif and CryptoVerif protocol analysis tools, and how this analysis influenced version 2 of PQXDH. We focus on the lessons learned in this process and how formal verification can be a powerful tool in an industrial setting. The talk will be given jointly by Rolfe Schmidt and Karthikeyan Bhargavan.

The past year has marked significant progress in secure messaging technologies. In March 2023, the Messaging Layer Security (MLS) protocol was standardized by the IETF, followed by Signal's introduction in May 2023 of PQXDH, a post-quantum alternative to the X3DH handshake. In the first part of this presentation, we identify scalability challenges that may hinder the widespread adoption of MLS and Signal in a post-quantum context, particularly in regions with limited mobile data plans. This analysis is backed by real-world quantitative data. In the second part of this talk, we propose a novel protocol with improved bandwidth consumption. It incorporates efficient post-quantum primitives, specifically multi-recipient public key encryption (mPKEs), optimized for secure messaging. We anticipate that our approach will be an order of magnitude more efficient than direct adaptations of existing protocols in practical scenarios.

This presentation delves into the recent publication of the Messaging Layer Security (MLS) standard, its unique features, and its impact on the future of secure messaging. We will discuss the standardization process of MLS, highlighting what worked, areas for improvement, and how formal analysis has been pivotal in building this new standard for the first time in a way that significantly departs from TLS due to the complexity of the protocol. In the first section, we will explore the core properties of the final version of MLS, such as the continuous group key agreement at its core and diverse properties such as message consistency, features that distinguish it from the Signal protocol. The presentation will cover the tradeoffs chosen by the MLS as we decided to ensure membership agreement and transparency as well as message consistency and non-repudiation as a default unlike existing protocols. We will also explore consequences of those choices such as the increased ability of malicious insiders to perform denial of service attacks on the group in absence of specific extensions being designed for group state proofs of correctness. If time permits, we might mention how to add deniability to the protocol. The next section of the presentation will focus on the future of MLS, discussing Post-Quantum cryptography and our ability to retain PCS in this context. We will mention efficiency challenges, and metadata privacy models depending on service provider architectures which make significant differences in the concrete privacy properties of a deployment. This will be followed by an examination of implementations and deployments, such as in Cisco WebEx and Google's commitment to deploying MLS for Android Messages and RCS 2.0. This last use case is expected to represent over a billion Monthly Active Users in 2024. If time permits, we will discuss potential deployments on platforms like Android and the Web and the challenge it causes, especially with respect to tracking on the Web. A second part of the talk will be dedicated to interoperability challenges in the context of the Digital Market Act (DMA) and how the MIMI working group will tackle that challenge at the IETF. We will explore the influence of DMA on messengers, identify unresolved issues, and discuss the integration of MLS with MIMI, especially with respect to identifiers and privacy considerations. The presentation will conclude with a forward-looking statement about the continued evolution of MLS and its applications. This abstract captures the essence of our discussion: MLS is a substantial development in secure messaging, designed for large dynamic groups and expected to reach billions of monthly active users in the next few years through platforms like Android or the Web. MLS stands as a cornerstone for secure messaging, co-designed with academic input and integrated with technologies like SFrame for WebRTC or eventually later Media over QUIC (MOQ).

The recent Hertzbleed disclosure demonstrates how remote-timing analysis can reveal secret information previously only accessible to local-power analysis. At worst, this constitutes a fundamental break in the constant-time programming principles and the many deployed programs that rely on them. But all hope is not lost. Hertzbleed relies on a coarse-grained, noisy channel that is difficult to exploit. Indeed, the Hertzbleed paper required a bespoke cryptanalysis to attack a specific cryptosystem (SIKE). Thus, it remains unclear if Hertzbleed represents a threat to the broader security ecosystem. In this paper, we demonstrate that Hertzbleed's effects affect cryptosystems beyond SIKE. We demonstrate how latent gadgets in other cryptosystem implementations---specifically ``constant-time'' ECDSA and Classic McEliece---can be combined with existing cryptanalysis to bootstrap Hertzbleed attacks on those cryptosystems.

Microarchitectural side-channel attacks have shaken the foundations of modern processor design. This talk will discuss the latest research on this topic.

The scale and frequency of password database compromises has led to widespread and persistent credential stuffing attacks, in which attackers attempt to use credentials leaked from one service to compromise accounts with other services. In response, browser vendors have integrated password leakage detection tools, which automatically check the user’s credentials against a list of compromised accounts upon each login, warning the user to change their password if a match is found. In particular, Google Chrome uses a centralized leakage detection service designed by Thomas et al. (USENIX Security ’19) that aims to both preserve the user’s privacy and hide the server’s list of compromised credentials. In this paper, we show that Chrome’s implementation of this protocol is vulnerable to several microarchitectural side- channel attacks that violate its security properties. Specifically, we demonstrate attacks against Chrome’s use of the memory-hard hash function scrypt, its hash-to-elliptic curve function, and its modular inversion algorithm. While prior work discussed the theoretical possibility of side-channel attacks on scrypt, we develop new techniques that enable this attack in practice, allowing an attacker to recover the user’s password with a single guess when using a dictionary attack. For modular inversion, we present a novel cryptanalysis of the Binary Extended Euclidian Algorithm (BEEA) that extracts its inputs given a single, noisy trace, thereby allowing a malicious server to learn information about a client’s password. This paper was presented at USENIX Security 2023, and the full version can be found at https://www.usenix.org/system/files/usenixsecurity23-kwong.pdf

The Internet has plenty of public images that are transformations (e.g., resize, crop, grayscale) of original unpublished ones. Various reasons recommend to keep private an original image, such as its economic value and its sensitive content. Several concrete scenarios, including selling images over the Internet, fighting misinformation and detecting deep fakes, would highly benefit from a system allowing to efficiently prove and verify the authenticity of a transformed image (i.e., the public image is a result of a faithful transformation over a private and authentic original image). This work presents the design of a system allowing the possessor of a signed private image to compute a faithful transformation, guaranteeing 1) confidentiality (no leak), 2) efficient proof generation (the proof can be computed with a cheap laptop), 3) integrity (only the advertised transformations have been applied) and 4) efficient fraud detection (fast detection of bogus proofs). Our system is based on a divide-et-impera approach through sub-transformations applied to tiles of the original image that are then reconnected together along with their sub-proofs. We discuss how to realize a few transformations. In particular, we have performed an experimental evaluation on the popular resize operation and the results confirm the viability of our approach. A faithful transformation of a high-resolution image of 30MP with a tile size of slightly less than 750KP can be generated on a common PC with 16GB of RAM and 8 cores, leaving free some resources for other light computations. The total amount of time to compute the proof for the entire image is slightly more than 45 minutes. Prior results require either an excessive amount of memory during the computation of a proof (resulting in huge proof generation time due to page faults) or the upload of the original image to some external cloud services negatively affecting confidentiality/decentralization.

Incoming regulation on AI such as the EU AI act, requires impact assessment and risk management to ensure fairness, accountability, and provide transparency for “high-risk” AI systems. This seems to require that companies provide unfettered access to a third party auditor who will provide a “seal of approval” before an AI system can be deployed. This often creates a tension between companies trying to protect trade secrets and auditors who need “white box” access to the data and models. In this talk, we examine how cryptography can, not only help resolve this tension, but additionally provide stronger transparency guarantees to the end user. The talk will consist of two parts: 1) An overview of the AI Policy landscape tailored to a cryptographers. The goal of which is to "distill" policy demands into research questions that cryptographers can tackle. 2) Next we will present our construction for "zero-knowledge proofs of training" and discuss challenges and lessons that were learned along the way. The technical paper "Experiment with Zero-Knowledge Proofs of Training" was accepted at CCS 2023.

In recent years, FHE has made significant gains in performance and usability. As a result, we see a first wave of real-world deployments and an increasing demand for practical applications of FHE. However, deploying FHE in the real world requires addressing challenges that have so far received less attention, as the community was primarily focused on achieving efficiency and usability. Specifically, the assumption of a semi-honest evaluating party, which is at the core of most FHE research, is incompatible with a large number of deployment scenarios. Scenarios that violate this assumption do not simply suffer from correctness issues, as one might expect, but in fact enable an adversary to completely undermine the confidentiality guarantees of FHE, up to and including very practical key-recovery attacks. As a response, a variety of works have tried to augment FHE for settings beyond the traditional semi-honest assumption. This fundamentally revolves around guaranteeing some form of integrity for FHE, while retaining sufficient malleability to allow homomorphic computations. However, it remains unclear to what extent existing approaches actually address the challenges of real-world deployment, as we identify significant gaps between the assumptions these works generally make and the way state-of-the-art FHE schemes are used in practice. In this talk, we survey and analyze existing approaches to FHE integrity in the context of real-world deployment scenarios, identify capabilities, shortcomings, and promising candidates. We also implemented and evaluated these constructions experimentally on realistic workloads, and we give some numbers. Finally, we conclude with a discussion on current capabilities, recommendations for future research directions, and an overview of the hurdles on the path to our ideal end-goal: a cryptographic equivalent of a trusted execution environment, i.e., a cryptoprocessor enabling fully private and verifiable computation.

This talk will outline the cryptographic protocols which are needed to implement private smart contracts (over and above that of basic FHE encryption and evaluation operations). Our motivation is the Zama fhEVM protocol, but the cryptographic primitives we will outline will be of general interest and apply to many FHE-enabled applications.

This talk will propose a new approach for building the next generation of AEAD. In the last few years, researchers and practitioners have discovered that widely deployed AEAD schemes, designed almost two decades ago, have many limitations. These range from uncomfortably small security margins to outright security vulnerabilities. We will discuss foundational theory and concrete designs for the next generation of AEAD schemes. Our designs better support real-world workloads while retaining performance.

One of the most popular symmetric encryption schemes in use on the Internet is ChaCha20-Poly1305. It is the default choice in tools like OpenSSH and Wireguard, and one of only three supported ciphersuites in TLS 1.3. ChaCha20Poly1305 utilizes a polynomial-based hash function for constructing Message Authentication Codes via the Wegman-Carter MAC construction. This entails evaluating the polynomial hash over the data, and blinding the output with a pseudorandom value obtained by enciphering a nonce with a blockcipher. More specifically, it uses Poly1305, originally designed with specific hardware in mind. Today, nearly 20 years later, we ask the following question: Given today's advancements and applications would we still converge to this same design?

This talk will discuss a simple approach to “encrypt forever” with a single AES-GCM key. It is called Double-Nonce-Derive-Key AES-GCM (DNDK-GCM) and is based on extending the 96-bit nonce length to any s-bit nonce length for s < 256 (e.g., 192). The security of the resulting AEAD can be proven under the same assumptions that base the security of AES-GCM because no additional cryptographic primitive is involved. The talk will discuss these security margins and explain why it is possible to use DNDK-GCM for processing even a total of 264 bytes under one key and remain withing the NIST specified 2^(-32) margins. This implies that the cryptoperiod of a key is not limited by the cryptographic bounds that indicate key wear-out. As a bonus, we will also toss in a key commitment string. By now, DNDK-GCM has become the default encryption mode on Meta infrastructure. The talk will provide a detailed performance analysis to show the cost of DNDK-GCM, relative to AES-GCM, and to some other AEADs that are being used at Meta. It will explain some considerations and challenges associated with defining and migrating to a new default on live cloud systems, discuss the standards compliance aspect, and provide some numbers on the scale at which this mode operates.

Common verification steps in cryptographic protocols, such as signature or message authentication code checks or the validation of elliptic curve points, are crucial for the overall security of the protocol. Yet implementation errors omitting these steps easily remain unnoticed, as often the protocol will function perfectly anyways. One of the most prominent examples is Apple's goto fail bug where the erroneous certificate verification skipped over several of the required steps, marking invalid certificates as correctly verified. This vulnerability went undetected for at least 17 months. In this talk, we ask whether cryptographic implementations have to be so brittle. What if we could make crypto bugs surface through noticeable errors in a program's functionality? We introduce a mechanism which supports such detection of implementation errors on a cryptographic level. Instead of merely returning a binary acceptance decision, we let verification procedures return more fine-grained information in form of what we call a confirmation code. We then show how to escalate verification errors affecting these confirmation codes to functional errors on the overall protocol level. Concretely, we show that when confirmation codes satisfy a carefully defined unpredictability property, we can provably integrate them into secure connection establishment via key exchange and tie security to basic functionality: if verification steps in the key exchange are faulty, the connection establishment will fail, making an implementation error like goto fail detectable through a simple connection test. We present intuitive (and provably secure) confirmation codes for RSA-PSS signatures, HMAC, and the validation of elliptic curve points and discuss what is needed for their practical deployment.

Over the past decade, proof systems, and especially zero-knowledge proofs, have seen an explosion of interest from academic researchers and practitioners. The resulting modern proof systems are being widely deployed in blockchain and cryptocurrency settings. Though built using novel technical ideas, many modern proof systems share a key ingredient with classic schemes: the Fiat-Shamir (F-S) transform. F-S is a generic way to compile an interactive proof system with a public-coin verifier to a non-interactive one by hashing the prover’s messages to generate verifier’s challenges. Prior work has shown that it is surprisingly easy to implement F-S incorrectly, and that incorrect F-S breaks classic proof systems like Schnorr. However, little is known about the risk of incorrectly implementing F-S for the modern proof systems being used in practice today; since more proof systems that use F-S are being deployed than ever before, it is crucial to understand whether vulnerable code exists and how it could be exploited. In this talk, we will present a broad survey of the state of the Fiat-Shamir transform in implementations of modern proof systems. Our talk’s contributions are fourfold. First, we will describe an extensive survey we conducted on implementations of the F-S transform in modern proof systems which identified dozens of incorrect implementations. For one such implementation, Incognito Chain’s Bulletproofs, the incorrect implementation could have led to untraceable theft of millions of dollars of funds. Second, we introduce novel attacks on incorrect F-S for four modern proof systems of interest: Bulletproofs, Plonk, Wesolowski’s VDF, and Spartan. We demonstrate attacks on adaptive knowledge soundness for all four protocols: for example, using the F-S transform described in the Wesolowski’s VDF paper, an attacker could claim to have performed orders of magnitude more squarings than it actually did. Third, we look at the applications in which these proof systems are used and try to understand whether these attacks are exploitable in relevant application contexts. Here the picture is more mixed: we show that the vulnerabilities are clearly exploitable in some applications, such as transactions using Plonk or Bulletproofs, but in other cases external constraints seem to prevent “lifting” soundness attacks to overlying protocols. Finally, we develop a set of clear recommendations to academic researchers and practitioners to try to ensure future implementations of proof systems use F-S correctly. This talk is based on a paper that was published at IEEE S&P ‘23, where it received a Distinguished Paper Award.

Count-Min Sketch (CMS) and HeavyKeeper (HK) are two realizations of a compact frequency estimator (CFE). These probabilistic data structures maintain a compact summary of high-volume streaming data and provide approximate estimates of the number of times an element occurred. CFEs are commonly used in streaming settings to identify elements with the largest frequencies (i.e., top-K elements, heavy hitters, elephant flows). Finding extreme elements is important for network planning, network monitoring, recommendation systems, etc. Traditionally, probabilistic guarantees on the accuracy of frequency estimates are proved under the implicit assumption that stream elements do not depend upon the internal randomness of the structure. This assumption is often not well-matched with reality; malicious actors could be incentivized to manipulate the data stream. In this talk, we reveal vulnerabilities in CMS and HK to adaptive attacks, by presenting attacks that cause significant estimation errors. For instance, elements never seen in the stream can be manipulated to resemble heavy hitters in CMS. This could, for example, cause network flow monitoring systems relying on CFEs to identify non-existent or benign flows as possible threats. Conversely, HK can make legitimate heavy hitters disappear. We analyze our attacks analytically and experimentally, obtaining a tight agreement between the two. These negative results seem unavoidable for (at least) sketch-based CFEs with parameters that are reasonable in practice. On the positive side, we build a new CFE (Count-Keeper) that can be seen as a composition of the CMS and HK structures. Count-Keeper estimates are typically more accurate (by at least a factor of two) than CMS for “honest” streams. Further, our attacks against CMS and HK are less effective (and more resource intensive) when used against Count-Keeper. Lastly, Count-Keeper has a native ability to flag estimates that are suspicious, which neither CMS or HK (or any other CFE, to our knowledge) admits.

Censorship circumvention tools enable clients to access endpoints in a network despite the presence of a censor. Censors use a variety of techniques to identify content they wish to block, including patterns that are characteristic of proxy or circumvention protocols. In response to this class of blocking behavior, circumvention practitioners have developed a family of "fully encrypted" protocols (FEPs), intended to have traffic that appears indistinguishable from random. For such protocols to be effective it is crucial that one can establish shared keys and protocol agreement without revealing to observers that an obfuscated protocol is in use. Despite their social significance to millions of users, there is no formal description of security for this handshake phase. This talk recounts the development of the obfs4 handshake, a highly-adopted FEP used to enable access to the Tor network in censored regions, which has incurred an iterative design process in response to censor behavior. We then present concrete results from our work formalizing obfuscated key exchange, capturing the goals of these protocols concretely and analyzing the obfs4 design. We demonstrate how to extend the obfs4 design to defend against stronger censorship attacks and to make it quantum-safe. With our analysis in mind, we point to challenges that remain in modeling and improving upon obfuscated protocols for future work.

Transparency logs are a powerful tool that makes it possible to bring accountability where it is unpractical to improve trust. Certificate Transparency pioneered and popularized the use of transparency logs, but also presents a model that is not very reusable due to its peculiar PKI context, and the technology has markedly improved since. In this talk we'll discuss the new designs, what properties they provide and when they are appropriate as a solution, how they are implemented, deployed, and scaled, and how they enable new transparency log applications, with plenty of real world examples.

We present a system for key management and protection of data at rest. At the heart of our system is a new protocol for secure key derivation, departing from the common practice of envelope encryption. Our solution adheres to existing enterprise architecture best practices and performance requirements. Our system is implemented at industrial scale, managing tens of thousands of root keys and serving thousands of server side key derivation requests per second. Our system is not only performant in terms of latency and throughput, but also offers non-trivial monetary cost reduction. The talk will present the key derivation protocol, and discuss system’s security and scalability.

Our web search queries reveal sensitive information about us: where we are (“Hikes in Toronto”), how we are feeling (“Causes of neck pain”), what we are doing (“How to find a lawyer”), and much more. Even if we use privacy-conscious search engines, such as DuckDuckGo, the search engine’s servers see our query strings in plaintext. As a result, search engines today accumulate a trove of sensitive data about us; this data is an attractive target for theft in a data breach, abuse by an authoritarian government, or sale to a third party. This talk will present Tiptoe, a search engine that learns nothing about what its users are searching for. With Tiptoe, a client sends only the encryption of its search query to the search engine’s servers. The search engine then executes a cryptographic protocol to identify the web pages that best answer the user’s query—without ever decrypting the query, without learning what the user is searching for, and without learning what search results it is sending back. Tiptoe’s privacy guarantee is based on cryptography alone; it does not require any trusted hardware or non-colluding servers. The Tiptoe search engine answers these queries in the span of seconds: searching over a public web crawl (360 million pages) incurs 57 MiB of client-server communication and 2.7 seconds of client-perceived latency.

The world of U.S. equities trading is highly competitive, involves many participants, and has significant global impact. Traders in this arena are responsible for overseeing the movement of billions of dollars, often on behalf of others, and thereby have a responsibility to develop reliable and well-performing trading strategies. “Controlling information leakage” is widely considered fundamental to high-quality, competitive trading strategies. In other words, good trading strategies maintain a level of privacy from an outside market observer. However important and highly valued this information leakage control property may seem, to our knowledge there exists no formal definition for this property in the context of equities trading strategies. Our work addresses this and creates a strong foundation for theoretical and practical work in this domain.

In early 2021, Apple announced the AirTag: a quarter-sized low-powered device that utilizes the privacy-preserving FindMy network to find physical objects. The release of Airtags has been highly controversial, in part because stalkers have misused them to track potential victims. In response to this threat, Apple came up with a strategy to detect stalkers at the cost of innocent AirTag users's privacy. Their methodology is currently in the process of being standardized by the IETF. In this talk, we will show that the hard trade-off presented by Apple is not necessary and that it is possible to efficiently achieve both privacy and stalker detection. We hope that by bringing this pressing issue to the attention of the community, we can spur more meaningful discussion on what privacy properties offline-finding networks should provide and incentivize the adoption of more privacy-preserving protocols.

Billions of devices running the RISC-V Open Source ISA have been shipped, and an increasing number of those implement cryptography instructions from the Cryptography Extensions Task Group (CETG). As a significant development, the RISC-V Android platform requires a CPU with vector cryptography extensions. We describe RISC-V extensions currently being developed for High Assurance and Post-Quantum Cryptography.

Zero-Knowledge proofs form the cornerstone of privacy-based cryptography. Research on their efficient realizations based on number-theoretic and hash-based assumptions dates back several decades, and there are now fairly optimized solutions based on these foundations. With the coming of quantum computing, one will eventually need to consider schemes whose security is based on quantum-resistant assumptions. Hash-based schemes are a very good candidate for this; but lattice-based ones could in principle be even more efficient. Basic cryptographic primitives based on lattices, such as KEMs and digital signatures, are faster than their classical counterparts, and shorter than hash-based constructions (such as signatures). Recent papers on lattice-based zero-knowledge have shown that these advantages could also extend into more advanced constructions. One can indeed use efficient lattice operations to construct SNARKs and ZK proofs with significantly shorter proof sizes than the hash-based counterparts. These proofs have already shown themselves useful in the designs of various privacy-based protocols, but like all ZK proofs, they are fairly non-trivial to instantiate and use. Just like proofs based on other assumptions, lattice-based ones are also quite intricate and non-trivial to use. Researchers working on number-theoretic and hash-based proofs have provided excellent libraries that make their proofs easy-to-use. In this work, we do the same for lattices. We implement a library that allows for easy consumption of SNARKs and ZK-proofs by protocol designers. The foundation of the library consists of algebraic operations upon which the most efficient recent lattice-based SNARKs and ZK proofs are built. These low-level implementations, as well as the ZK protocols, are written in C. We then create a Python wrapper that allows protocol designers to easily create instances and create proofs, as well as use the efficient C operations to be able to write their protocols entirely in Python without sacrificing much in the form of efficiency. We illustrate the usefulness of the library with several instantiations of protocols from the literature that utilize lattice-based ZK proofs, and will present live demos.

The advent of quantum computers has sparked significant interest in post-quantum cryptographic schemes, as a replacement for currently used cryptographic primitives. In this context, lattice-based cryptography has emerged as the leading paradigm to build post-quantum cryptography. However, all existing viable replacements of the classical Diffie-Hellman key exchange require additional rounds of interactions, thus failing to achieve all the benefits of this protocol. Although earlier work has shown that lattice-based Non-Interactive Key Exchange~(NIKE) is theoretically possible, it has been considered too inefficient for real-life applications. In this work, we challenge this folklore belief and provide the first evidence against it. We construct an efficient lattice-based NIKE whose security is based on the standard module learning with errors (M-LWE) problem in the quantum random oracle model. Our scheme is obtained in two steps: (i) A passively-secure construction that achieves a strong notion of correctness, coupled with (ii) a generic compiler that turns any such scheme into an actively-secure one. To substantiate our efficiency claim, we provide an optimised implementation of our passively-secure construction in Rust and Jasmin. Our implementation demonstrates the scheme's applicability to real-world scenarios, yielding public keys of approximately $220$\,KBs. Moreover, the computation of shared keys takes fewer than $12$ million cycles on an Intel Skylake CPU, offering a post-quantum security level exceeding $120$ bits.

Anonymous credentials, first proposed by Chaum in 1985, enable individuals to prove attributes about themselves without revealing personal information. For example, they can prove that they live in Ontario without revealing their full home address. The award celebrates a sequence of results, starting in 2001, that developed the first efficient and fully anonymous credential schemes. This is an active area of research with many beautiful results by many talented cryptographers. We hope that this recognition will encourage further adoption of this technology.

Certificate Transparency was a response to the 2011 attack on DigiNotar and other Certificate Authorities. These attacks showed that the lack of transparency in the way CAs operate was a significant risk to the Web Public Key Infrastructure (PKI). It led to the creation of the Certificate Transparency project to improve Internet security by bringing accountability to the system that protects HTTPS. Since 2013, the Certificate Transparency community has effectively monitored and fixed certificate anomalies. The award recognizes the enermous effort that it took to make Certificate Transparency a reality on the Web, and the tangible security benefits that it brings to all Web users.

End-to-end encryption security guarantees crucially rely on the assumption that the user has the correct identity public key for the person they wish to communicate with. Traditionally, E2EE communication systems have required the user to perform cumbersome manual checks to verify these keys, e.g. by physically scanning QR codes, or by verbally reading a fingerprint. In practice, these verifications are rarely performed. Key transparency, first introduced in CONIKS, allows much of this verification to be automated. Roughly, the communication service provider regularly publishes a commitment to the identity key directory; this commitment must be publicly and consistently visible to all users. Every key request is accompanied by a proof that the key is correct w.r.t. the committed directory. Finally, the user’s device regularly monitors the committed directory to ensure that the user’s key is correctly reflected. This talk will present the motivation for key transparency and introduce the approach and intuition behind the constructions. It will then discuss some areas of active research and open problems.

Video conferencing apps like Zoom have hundreds of millions of daily users, making them a high-value target for surveillance and subversion. While such apps claim to achieve some forms of end-to-end encryption, they usually assume an incorruptible server that is able to identify and authenticate all the parties in a meeting. Concretely this means that, e.g., even when using the “end-to-end encrypted” setting, malicious Zoom servers could eavesdrop or impersonate in arbitrary groups. In this work, we show how security against malicious servers can be improved by changing the way in which such protocols use passwords (known as passcodes in Zoom) and integrating a password-authenticated key exchange (PAKE) protocol. To formally prove that our approach achieves its goals, we formalize a class of cryptographic protocols suitable for this setting, and define a basic security notion for them, in which group security can be achieved assuming the server is trusted to correctly authorize the group members. We prove that Zoom indeed meets this notion. We then propose a stronger security notion that can provide security against malicious servers, and propose a transformation that can achieve this notion. We show how we can apply our transformation to Zoom to provably achieve stronger security against malicious servers, notably without introducing new security elements.

Frequently, users on the web need to show that they are, for example, not a robot, old enough to access an age restricted video, or eligible to download an ebook from their local public library without being tracked. Anonymous credentials were developed to address these concerns. However, existing schemes do not handle the realities of deployment or the complexities of real-world identity. Instead, they implicitly make assumptions such as there being an issuing authority for anonymous credentials that, for real applications, requires the local department of motor vehicles to issue sophisticated cryptographic tokens to show users are over 18. In reality, there are multiple trust sources for a given identity attribute, their credentials have distinctively different formats, and many, if not all, issuers are unwilling to adopt new protocols. We present and build zk-creds, a protocol that uses general-purpose zero-knowledge proofs to 1) remove the need for credential issuers to hold signing keys: credentials can be issued to a bulletin board instantiated as a transparency log, Byzantine system, or even a blockchain; 2) convert existing identity documents into anonymous credentials without modifying documents or coordinating with their issuing authority; 3) allow for flexible, composable, and complex identity statements over multiple credentials. Concretely, identity assertions using zk-creds take less than 150ms in a real-world scenario of using a passport to anonymously access age-restricted videos. This paper was published at IEEE Security and Privacy 2023, and the full version can be found at https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=10179430.

Earlier this year, WhatsApp announced their plans to launch key transparency for all WhatsApp users. Key transparency solutions help strengthen the guarantee that end-to-end encryption provides to private, personal messaging applications in a transparent manner available to all. In this presentation, we will cover how key transparency works, what the improved end user experience is for those wishing to verify their contacts' public keys, and various deployment challenges and considerations we encountered when building our key transparency system. We also have released an open-source library called Auditable Key Directory (AKD) which we use in our deployment, and can potentially serve as a reference point for others that wish to deploy key transparency in the future.

This talk will cover Amazon Web Service’s (AWS) experience implementing and deploying cryptographic algorithms (henceforth, by “algorithm” we mean “cryptographic algorithm”), implemented with carefully targeted micro-architectural optimizations and formally verified with Automated Reasoning (AR). We will survey the challenges we faced, their solutions, and innovations we have made, using our development of X25519 and Ed25519 implementations as examples throughout. First we will motivate the choice of those algorithms and the challenges that we faced. Secondly, we will introduce our solutions to those challenges: implementations of X25519 and Ed25519 optimized for both x86_64 and aarch64 micro-architectures; HOL Light, the AR engine used to formally verify correctness of the implementations; and the technology stack used at AWS for algorithm deployment. Thirdly, we will present performance data for our new implementations. Finally, we will present ongoing and future work at AWS combining AR and algorithm implementations. In summary, we will argue that combining AR and algorithm implementations is possible and can yield fruitful results, as well as explaining how AWS deploys algorithms at scale.

Meta has recently begun rolling out default end-to-end encryption to their billions of Messenger users. We announced the project in 2019, and it has involved a long process of development and iteration in order to enable the migration to succeed. Messenger operates within a number of product constraints that increase the complexity of end-to-end encryption from standard approaches described elsewhere, all stemming from users’ expectations that a rich Messenger experience is available across all their devices. For example, we support: * multiple devices for each user, including ephemeral web sessions low-end devices with limited local storage or processing capacity; * message history; which has historically been available to all devices logged in to a Messenger account; * a number of rich features such as social integrations (e.g. sharing posts, previews, sticker search). The underlying architecture can dramatically impact the challenges faced in encrypting messages. Some challenges included: * data was sometimes structured in our backend such that there weren’t clear payloads to encrypt; * our surfaces, such as Facebook Lite, which have historically achieved a lightweight app by rendering the user’s entire screen server-side. Alongside Messenger’s product challenges, it’s helpful to actually be clear about the actual intention of end-to-end encryption. Specifically, in the non-cryptographic privacy goals that it implies around confidentiality and authenticity of messages. To put these into practice within the organisation, we required a more comprehensive approach, which - in retrospect - breaks down into a series of sub-requirements: * Confidential & authentic message transmission & storage. * Private feature implementations. * Limitations on what can be logged. * Application security. * Process to determine what we’re protecting. * A level of verifiability. We learned some general lessons from rolling out end-to-end encryption; including the challenge of communicating such changes to a global audience, as well as in testing and rolling out an inherent shift in product model and architecture in-place within an existing product. This included findings, such as: * Communicating end-to-end encryption with padlock icons in the user interface was at times interpreted differently in different contexts - with interpretations ranging from Meta having locked the chat to implying that the chat itself was subversive. * Replacing a product in-place makes testing especially challenging, as many factors end up being tested simultaneously, with outcomes which are difficult to disentangle. Our approach to message history raised a number of difficulties, including a fundamental tension that exists for storing end-to-end encrypted data; that forces the implementer to choose between sacrificing guaranteed message history availability, guaranteed messaging availability, and the ability to login to Facebook without introducing user-managed keys. To store e2ee messages, we designed a new cryptographic protocol which provides indexed storage, key rotation, and a diversity of recovery methods. The rollout of this created significant product challenges, as users had to make a choice around whether to use this solution, and - if so - how they should manage their recovery codes. This was particularly difficult because many users did not have a good understanding of the changes, we didn’t necessarily have the ability to interrupt the user at an appropriate time for them to think it through, nor did many of them want to engage with these prompts in the first place - despite the importance of making the right choice. Finally, we will look at some of the product features which presented particular challenges for us, and how we addressed making them work. These features include: * Sharing posts from Facebook into messages; which typically provides the user a preview of the post content, but for which the previewed content may be audience-controlled. * Sticker search; for which we wanted to protect the search terms from association with the user. End-to-end encryption for Messenger was a larger change than we had initially anticipated, which introduced complexity in most places that it touched. We learned a lot from addressing this new set of challenges, and we hope that these lessons can apply more broadly in future to help end-to-end encryption gain wider spread adoption.

The increasing harms caused by hate, harassment, and other forms of abuse online have motivated major platforms to explore hierarchical governance. The idea is to allow communities to have designated members take on moderation and leadership duties; meanwhile, members can still escalate issues to the platform. But these promising approaches have only been explored in plaintext settings where community content is public to the platform. It is unclear how one can realize hierarchical governance in the huge and increasing number of online communities that utilize end-to-end encrypted (E2EE) messaging for privacy. This talk will argue for the importance of adapting hierarchical governance to E2EE platforms, share some of our recent work towards privacy-preserving hierarchical governance, and discuss ongoing challenges in this space.

The SSH protocol provides secure access to network services, particularly remote terminal login and file transfer within organizational networks and to over 15 million servers on the open internet. SSH uses an authenticated key exchange to establish a secure channel between a client and a server, which protects the confidentiality and integrity of messages sent in either direction. The secure channel prevents message manipulation, replay, insertion, deletion, and reordering. At the network level, SSH uses the SSH Binary Packet Protocol over TCP. In this paper, we show that as new encryption algorithms and mitigations were added to SSH, the SSH Binary Packet Protocol is no longer a secure channel: SSH channel integrity (INT-PST) is broken for three widely used encryption modes. This allows prefix truncation attacks where some encrypted packets at the beginning of the SSH channel can be deleted without the client or server noticing it. We demonstrate several real-world applications of this attack. We show that we can fully break SSH extension negotiation (RFC 8308), such that an attacker can downgrade the public key algorithms for user authentication or turn off a new countermeasure against keystroke timing attacks introduced in OpenSSH 9.5. We also identified an implementation flaw in AsyncSSH that, together with prefix truncation, allows an attacker to redirect the victim’s login into a shell controlled by the attacker. In an internet-wide scan for vulnerable encryption modes and support for extension negotiation, we find that 77% of SSH servers support an exploitable encryption mode, while 57% even list it as their preferred choice. We identify two root causes that enable these attacks: First, the SSH handshake supports optional messages that are not authenticated. Second, SSH does not reset message sequence numbers when encryption is enabled. Based on this analysis, we propose effective and backward-compatible changes to SSH that mitigate our attacks.

Over the past 25 years, research has highlighted the fact that high-end hardware can be used by attackers to recover secret keys from devices. Numerous studies have demonstrated innovative secret key extraction techniques that rely on dedicated professional equipment to capture data-dependent physical leakage from target devices. These methods employ equipment like scopes to obtain power traces, software-defined radio and probes to capture electromagnetic radiation (EMR) traces, as well as ultrasonic microphones to capture acoustic traces. While these methods have deepened our understanding regarding the cryptanalytic risks associated with various types of leakage (EMR, acoustic, power) and high-end sensors to secret keys, much less is known about the cryptanalytic risks posed by optical leakage and accessible ubiquitous equipment such as video cameras. In this talk, we will reveal the findings from the two research papers, optical cryptanalysis (CCS’23) and video-based cryptanalysis (SP’24), and discuss how attackers can extract cryptographic keys using video footage of a device’s power LEDs captured by standard video cameras. In the first part of the talk, we will review the history of the side-channel cryptanalytic attacks from the first timing attack that was published in 1996, through the cryptanalytic power-based attacks and cryptanalytic EMR attacks that were published since 1998 until the acoustic attack that was published at 2014 and conclude interesting insights regarding the lessons we learned from these works. Next, we will discuss information leakage from power LEDs (based on the findings presented at CCS 23), and understand why the intensity of the light emitted by a device’s power LED can be used as an alternative to power traces obtained from the device to recover secret keys (2048-bit RSA, 256-bit ECDSA and 378-bit SIKE keys) from commonly used cryptographic libraries (Libgcrypt, GnuPG, PQCryptoSIDH) using a photodiode. In the second part of the talk, we will discuss how standard video cameras (e.g., of an iPhone 13 PRO Max, and security camera) can be used as alternatives for the photodiodes (based on the findings presented at SP’24) to extract secret keys (256-bit ECDSA and 378-bit SIKE keys). We will discuss a video camera’s rolling shutter and understand how it can be used to increase the sampling rate of a video camera from the frame-per-second rate (60 measurements per second) to the rolling shutter rate (60,000 measurements per second). We will see videos of secret key recoveries that were taken by a smartphone and by an Internet-connected security camera to recover a 256-bit ECDSA key (using the Minerva side-channel attack) and a 378-SIKE key (using the HertzBleed side-channel attack). At the end of the talk, we will discuss countermeasures, and provide insights regarding the real potential of extracting cryptographic keys by video cameras in our days and in the near future, taking into account the expected improvements in the specifications of video cameras expected by Moore’s Law.

In this work, we consider the problem of secure key leasing, also known as revocable cryptography (Agarwal et. al. Eurocrypt' 23, Ananth et. al. TCC' 23), as a strengthened security notion of its predecessor put forward in Ananth et. al. Eurocrypt' 21. This problem aims to leverage unclonable nature of quantum information to allow a lessor to lease a quantum key with reusability for evaluating a classical functionality. Later, the lessor can request the lessee to provably delete the key and then the lessee will be completely deprived of the capability to evaluate the function. In this work, we construct a secure key leasing scheme to lease a decryption key of a (classical) public-key, homomorphic encryption scheme from standard lattice assumptions. Our encryption scheme is exactly identical to the (primal) version of Gentry-Sahai-Waters homomorphic encryption scheme with a carefully chosen public key matrix. We achieve strong form of security where: * The entire protocol (including key generation and verification of deletion) uses merely classical communication between a classical lessor (client) and a quantum lessee (server). * Assuming standard assumptions, our security definition ensures that every computationally bounded quantum adversary could only simultaneously provide a valid classical deletion certificate and yet distinguish ciphertexts with at most negligible probability. Our security relies on the hardness of learning with errors assumption. Our scheme is the first scheme to be based on a standard assumption and satisfying the two properties mentioned above. The main technical novelty in our work is the design of an FHE scheme that enables us to apply elegant analyses done in the context of classically verifiable proofs of quantumness from LWE (Brakerski et. al.(FOCS'18, JACM'21) and its parallel amplified version in Radian et. al.(AFT'21)) to the setting of secure leasing. This connection leads to a modular construction and arguably simpler proofs than previously known. An important technical component we prove along the way is an amplified quantum search-to-decision reduction: we design an extractor that uses a quantum distinguisher (who has an internal quantum state) for decisional LWE, to extract secrets with success probability amplified to almost one. This technique might be of independent interest.

This paper improves upon the quantum circuits required for the Shor’s attack on binary elliptic curves. We present two types of quantum point addition, taking both qubit count and circuit depth into consideration.In summary, we propose an in-place point addition that improves upon the work of Banegas et al. from CHES’21, reducing the qubit count – depth product by more than 73% – 81% depending on the variant. Furthermore, we develop an out-of-place point addition by using additional qubits. This method achieves the lowest circuit depth and offers an improvement of over 92% in the qubit count – quantum depth product (for a single step).To the best of our knowledge, our work improves from all previous works (including the CHES’21 paper by Banegas et al., the IEEE Access’22 paper by Putranto et al., and the CT-RSA’23 paper by Taguchi and Takayasu) in terms of circuit depth and qubit count – depth product.Equipped with the implementations, we discuss the post-quantum security of the binary elliptic curve cryptography. Under the MAXDEPTH metric (proposed by the US government’s NIST), the quantum circuit with the highest depth in our work is 224, which is significantly lower than the MAXDEPTH limit of 240. For the gate count – full depth product, a metric for estimating quantum attack cost (proposed by NIST), the highest complexity in our work is 260 for the curve having degree 571 (which is comparable to AES-256 in terms of classical security), considerably below the post-quantum security level 1 threshold (of the order of 2156).

Recently, Differential Fault Attacks (DFAs) have proven highly effective against stream ciphers designed for Hybrid Homomorphic Encryption (HHE). In this work, we present a table-based DFA framework called the shortcut attack, which generalizes the attack proposed by Wang and Tang on the cipher Elisabeth. The framework applies to a broad sub-family of ciphers following the Group Filter Permutator (GFP) paradigm and enhances previous DFAs by improving both the fault identification and path generation steps. Notably, the shortcut attack circumvents the issue of function representation, allowing successful attacks even when the cipher’s filter function cannot be represented over the ring it is defined on.Additionally, we provide complexity estimates for the framework and apply the shortcut attack to Elisabeth-4 and its patches. As a result, we optimize the DFA on Elisabeth-4, requiring fewer keystreams and running faster than previous methods. Specifically, we achieve a DFA that requires only 3000 keystreams, which is one-fifth of the previous best result. We also successfully mount a practical DFA on Gabriel-4 and provide a theoretical DFA for Elisabeth-b4.For the latest patch, Margrethe-18-4, which follows the more general Mixed Filter Permutator (MFP) paradigm, we present a DFA in a stronger model. To the best of our knowledge, these are the first DFA results on the patches of Elisabeth-4. Finally, we derive security margins to prevent shortcut attacks on a broad sub-family of MFP ciphers, which can serve as parameter recommendations for designers.

Unprotected cryptographic implementations are vulnerable to implementation attacks, such as passive side-channel attacks and active fault injection attacks. Recently, countermeasures like polynomial masking and duplicated masking have been introduced to protect implementations against combined attacks that exploit leakage and faults simultaneously. While duplicated masking requires O (t · e) shares to resist an adversary capable of probing t values and faulting e values, polynomial masking requires only O (t · e) shares, which is particularly beneficial for affine computation. At CHES’24, Arnold et al. showed how to further improve the efficiency of polynomial masking in the presence of combined attacks by embedding two secrets into one polynomial sharing. This essentially reduces the complexity of previous constructions by half. The authors also observed that using techniques from packed secret sharing (Grosso et al., CHES’13) cannot easily achieve combined resilience to encode an arbitrary number of secrets in one polynomial encoding. In this work, we resolve these challenges and show that it is possible to embed an arbitrary number of secrets in one encoding and propose gadgets that are secure against combined attacks. We present two constructions that are generic and significantly improve the computational and randomness complexity of existing compilers, such as the laOla compiler presented by Berndt et al. at CRYPTO’23 and its improvement by Arnold et al. For example, for an AES evaluation that protects against t probes and e faults, we improve the randomness complexity of the state-of-the-art construction when t + e > 3, leading to an improvement of up to a factor of 2.41.

Oscillation-based physical unclonable functions (PUFs) are known to be sensitive to power trace side channel analyses (SCAs). Although previous work investigated on countermeasures, these required significant additional amount of hardware or were just able to obscure sign information of a frequency comparison, while the magnitude information remains available to the attacker. As recent innovation on oscillation-based PUFs also require the magnitude-information beside the sign, e.g., to increase the reliability, the need arises to protect both. We present a new protection approach to hide both sign and magnitude information of oscillation-based PUF from an attacker. By introducing random interruptions in the oscillation, the power spectrum is blurred while the quality of the PUF is maintained. In addition to concept simulations and the discussion of different implementations, we use the example of a loop-PUF to show that the presented countermeasure can withstand several attack scenarios.

The Multi-Scalar Multiplication (MSM) is the main barrier to accelerating Zero-Knowledge applications. In recent years, hardware acceleration of this algorithm on both FPGA and GPU has become a popular research topic and the subject of a multi-million dollar prize competition (ZPrize). This work presents OPTIMSM: Optimized Processing Through Iterative Multi-Scalar Multiplication. This novel accelerator focuses on the acceleration of the MSM algorithm for any Elliptic Curve (EC) by improving upon the Pippenger algorithm. A new iteration technique is introduced to decouple the required buckets from the window size, resulting in fewer EC computations for the same on-chip memory resources. Furthermore, we combine known optimizations from the literature for the first time to achieve additional latency improvements. Our enhanced MSM implementation significantly reduces computation time, achieving a speedup of up to x12.77 compared to recent FPGA implementations. Specifically, for the BLS12-381 curve, we reduce the computation time for an MSM of size 224 to 914 ms using a single compute unit on the U55C FPGA or to 231 ms using four U55C devices. These results indicate a substantial improvement in efficiency, paving the way for more scalable and efficient Zero-Knowledge proof systems.

In this paper we propose a constant time lattice reduction algorithm for integral dimension-4 lattices. Motivated by its application in the SQIsign postquantum signature scheme, we provide for the first time a constant time LLLlike algorithm with guarantees on the length of the shortest output vector. We implemented our algorithm and ensured through various tools that it indeed operates in constant time. Our experiments suggest that in practice our implementation outputs a Minkowski reduced basis and thus can replace a non constant time lattice reduction subroutine in SQIsign.

Making the most of TFHE programmable bootstrapping to evaluate functions or operators otherwise challenging to perform with only the native addition and multiplication of the scheme is a very active line of research. In this paper, we systematize this approach and apply it to build an 8-bit FHE processor abstraction, i.e., a software entity that works over FHE-encrypted 8-bit data and presents itself to the programmer by means of a conventional-looking assembly instruction set. In doing so, we provide several homomorphic LookUp Table (LUT) dereferencing operators based on variants of the tree-based method and show that they are the most efficient option for manipulating encryptions of 8-bit data (optimally represented as two basis 16 digits). We then systematically apply this approach over a set of around 50 instructions, including, notably, conditional assignments, divisions, or fixed-point arithmetic operations. We further test the approach on several simple algorithms, including the execution of a neuron with a sigmoid activation function with 16-bit precision. We conclude the paper by comparing our work to the FHE compilers available in the state of the art. Finally, this work reveals that a very limited set of functional bootstrapping patterns is versatile and efficient enough to achieve general-purpose FHE computations beyond the boolean circuit approach. As such, these patterns may be an appropriate target for further works on advanced software optimizations or hardware implementations.

Locking-based intellectual property (IP) protection for integrated circuits (ICs) being manufactured at untrusted facilities has been largely defeated by the satisfiability (SAT) attack, which can retrieve the secret key needed for instantiating proprietary functionality on locked circuits. As a result, redaction-based methods have gained popularity as a more secure way of protecting hardware IP. Among these methods, transistor-level programming (TRAP) prohibits the outright use of SAT attacks due to the mismatch between the logic-level at which SAT attack operates and the switch-level at which the TRAP fabric is programmed. Herein, we discuss the challenges involved in launching SAT attacks on TRAP and we propose solutions which enable expression of TRAP in propositional logic modeling in a way that accurately reflects switch-level circuit capabilities. Results obtained using a transistor-level SAT attack tool-set that we developed and are releasing corroborate that SAT attacks can be launched against TRAP. However, the increased complexity of switch-level circuit modeling prevents the attack from realistically compromising all but the most trivial IP-protected designs.

PUFs enable physical tamper protection for high-assurance devices without needing a continuous power supply that is active over the entire lifetime of the device. Several methods for PUF-based tamper protection have been proposed together with practical quantization and error correction schemes. In this work we take a step back from the implementation to analyze theoretical properties and limits. We apply zero leakage output quantization to existing quantization schemes and minimize the reconstruction error probability under zero leakage. We apply wiretap coding within a helper data algorithm to enable a reliable key reconstruction for the legitimate user while guaranteeing a selectable reconstruction complexity for an attacker, analogously to the security level for a cryptographic algorithm for the attacker models considered in this work. We present lower bounds on the achievable key rates depending on the attacker’s capabilities in the asymptotic and finite blocklength regime to give fundamental security guarantees even if the attacker gets partial information about the PUF response and the helper data. Furthermore, we present converse bounds on the number of PUF cells. Our results show for example that for a practical scenario one needs at least 459 PUF cells using 3 bit quantization to achieve a security level of 128 bit.

Resource-constrained devices such as wireless sensors and Internet of Things (IoT) devices have become ubiquitous in our digital ecosystem. These devices generate and handle a major part of our digital data. However, due to the impending threat of quantum computers on our existing public-key cryptographic schemes and the limited resources available on IoT devices, it is important to design lightweight post-quantum cryptographic (PQC) schemes suitable for these devices.In this work, we explored the design space of learning with error-based PQC schemes to design a lightweight key-encapsulation mechanism (KEM) suitable for resourceconstrained devices. We have done a scrupulous and extensive analysis and evaluation of different design elements, such as polynomial size, field modulus structure, reduction algorithm, and secret and error distribution of an LWE-based KEM. Our explorations led to the proposal of a lightweight PQC-KEM, Rudraksh, without compromising security. Our scheme provides security against chosen ciphertext attacks (CCA) with more than 100 bits of Core-SVP post-quantum security and belongs to the NIST-level-I security category (provide security at least as much as AES-128). We have also shown how ASCON can be used for lightweight pseudo-random number generation and hash function in the lattice-based KEMs instead of the widely used Keccak for lightweight design. Our FPGA results show that Rudraksh currently requires the least area among the PQC KEMs of similar security. Our implementation of Rudraksh provides a ~3x improvement in terms of the area requirement compared to the state-of-the-art areaoptimized implementation of Kyber, can operate at 63%-76% higher frequency with respect to high-throughput Kyber, and improves time-area-product ~2x compared to the state-of-the-art compact implementation of Kyber published in HPEC 2022.

Multi-scalar multiplication (MSM) is the primary building block in many pairing-based zero-knowledge proof (ZKP) systems. MSM at large scales has become the main bottleneck in ZKP implementations. Inspired by existing SIMD-accelerated work, we are focused on accelerating MSM computing efficiency using SIMD instructions in a single CPU environment. First, we propose a SIMD-accelerated MSM computing architecture with no write conflicts and constant memory overheads. This architecture utilizes multithreading to achieve task-level and loop-level parallelism and employs a three-tier buffer mechanism to maximize the utilization of the SIMD engine. Instanced with AVX512-IFMA instructions, we implement six SIMD elliptic curve arithmetic engines for different point addition in three coordinate systems and two groups. Moreover, we integrate our AVX-MSM implementation into the libsnark library, naming it AVX-ZK. In more detail, point deduplication and “Three-Stage” memory optimization are proposed to address problems existing in practical applications. Based on the RELIC library, our performance results on the BLS12-381 curve show that our AVX-MSM achieves up to 27.86x speedup over the most popular Pippenger algorithm. Compared with libsnark, our AVX-ZK implementation achieves over 11.53x (up to 20.26x) speedup under standard benchmarks.

In this paper, we introduce AETHER, an authenticated encryption scheme that achieves ultra-high throughput and low energy consumption, supporting a 256- bit key and a 128-bit tag. While inspired by an AEGIS-like structure, AETHER stands out with a completely redesigned round-update function. We replace the AES round function with a new inner function optimized for ultra-low latency and energy consumption. This function incorporates Orthros’s S-box and a 16x16 binary matrix from Akleylek et al., leading to a 1.56 times reduction in energy consumption and a 1.25 times reduction in delay compared to the AES round function. To further optimize hardware performance, we design the general construction of the roundupdate function to be more hardware-friendly, allowing parallel execution of the inner function on all 128-bit words, thereby enhancing both throughput and security against collision-based forgery attacks. AETHER achieves a throughput of 2.1 Tbit/s and an energy consumption of only 204.31 nJ, in the Nangate 15 nm standard cell library and a throughput of 5.23 Tbit/s and energy consumption of 1.83 nJ using the CNFET-OCL 5nm library, outperforming all existing AEADs.

Arithmetic hash functions defined over prime fields have been actively developed and used in verifiable computation (VC) protocols. Among those, ellipticcurve- based SNARKs require large (256-bit and higher) primes. Such hash functions are notably slow, losing a factor of up to 1000 compared to regular constructions like SHA-2/3.In this paper, we present the hash function Skyscraper, which is aimed at large prime fields and provides major improvements compared to Reinforced Concrete and Monolith. First, the design is exactly the same for all large primes, which simplifies analysis and deployment. Secondly, it achieves a performance comparable to cryptographic hash standards by using low-degree non-invertible transformations and minimizing modulo reductions. Concretely, it hashes two 256-bit prime field (BLS12-381 curve scalar field) elements in 135 nanoseconds, whereas SHA-256 needs 42 nanoseconds on the same machine.The low circuit complexity of Skyscraper, together with its high native speed, should allow a substantial reduction in many VC scenarios, particularly in recursive proofs.

The MPC-in-the-head with preprocessing (MPCitH-PP) paradigm presents a novel approach for constructing post-quantum digital signatures like Picnic3. This paper revisits the MPCitH-PP construction, analyzing both its offline and online phases and proposing a reformulation of the protocol. By identifying redundant computations in these phases, we optimize them into a single phase, thereby enhancing the efficiency of MPCitH-PP. Furthermore, we explore the independence of the mask, demonstrating that it can be calculated in parallel, which also enables the optimization of the masked witness calculation.Our optimized implementation of Picnic3 shows significant improvements. At the L1 security level, the optimal software implementation reduces MPCitH-PP calculation time to about 30% of the previous implementation. The optimal signature implementation costs about 78% of the previous implementation time. At the L5 security level, MPCitH-PP with parallelism optimal is reduced to about 26% of the previous solution’s time, and the optimal signature implementation runs at about 53% of the previous solution’s time. For the hardware implementation, our optimizations reduce the clock cycles of MPCitH-PP from r sequential rounds to a single parallel round, where r denotes the number of rounds in the LowMC algorithm, with little change in hardware usage, and perform better in AT product, especially for parallel computing.

CRYSTALS-Kyber, one of the NIST PQC standardization schemes, has garnered considerable attention from researchers in recent years for its side-channel security. Various targets have been explored in previous studies; however, research on extracting secret information from stack-optimized implementations targeting the Cortex-M4 remains scarce, primarily due to the lack of memory access operations, which increases the difficulty of attacks.This paper shifts the focus to the leakage of multiply instructions and present a novel cycle-level regression-based leakage model for the following attacks. We target the polynomial multiplications in decryption process of the stack-optimized implementation targeting the Cortex-M4, and propose two regression-based profiled attacks leveraging known ciphertext and chosen ciphertext methodologies to recover the secret coefficients individually. The later one can also be extended to the protected implementation.Our practical evaluation, conducted on the stack-optimized Kyber-768 implementation from the pqm4 repository, demonstrates the effectiveness of the proposed attacks. Focusing on the leakage from the pair-pointwise multiplication, specifically the macro doublebasemul_frombytes_asm, we successfully recover all secret coefficients with a success rate exceeding 95% using a modest number of traces for each attack. This research underscores the potential vulnerabilities in PQC implementations against side-channel attacks and contributes to the ongoing discourse on the physical security of cryptographic algorithms.

Secure aggregation is a popular solution to ensuring privacy for federated learning. However, when considering malicious participants in secure aggregation, it is difficult to achieve both privacy and high efficiency. Therefore, we propose SeaFlame, a communication-efficient secure aggregation protocol against malicious participants. Inspired by the state-of-the-art work, ELSA, SeaFlame also utilizes two non-colluding servers to ensure privacy against malicious entities and provide defenses against boosted gradients. Crucially, to improve communication efficiency, SeaFlame uses arithmetic sharing together with arithmetic-to-arithmetic share conversion to reduce client communication, and uses the random linear combination to reduce server communication.Security analysis proves that our SeaFlame guarantees privacy against malicious clients colluding with one malicious server. Experimental evaluation demonstrates that, compared to ELSA, SeaFlame optimizes communication by up to 10.5, 6.00, and 8.17 times for a client, a server, and all entities, at the expense of 1.25-1.86 times additional end-to-end runtime.

The McEliece cryptosystem is a strong contender for post-quantum schemes, including key encapsulation for confidentiality of key exchanges in network protocols. A McEliece secret key is a structured parity check matrix that is transformed via Gaussian elimination into an unstructured public key. We show that this transformation is highly critical with respect to side-channel leakage. We assume leakage of the elementary row operations during Gaussian elimination, motivated by McEliece implementations in the cryptographic libraries Classic McEliece and Botan.We propose a novel decoding algorithm to reconstruct a secret key from its public key with information from a Gaussian transformation leak. Even if the obtained side-channel leakage is extremely noisy, i.e., each bit is flipped with probability as high as r ≈ 0.4, we succeed to recover the secret key in a matter of minutes for all proposed (Classic) McEliece instantiations. Remarkably, for high-security McEliece parameters, our attack is more powerful in the sense that it can tolerate even larger r . We demonstrate our attack on the constant-time reference implementation of Classic McEliece in a single-trace setting, using an STM32L592 ARM processor.Our result stresses the necessity of properly protecting highly structured code-based schemes such as McEliece against side-channel leakage.

Floating-point arithmetic plays a central role in computer science and is used in various domains where precision and computational scale are essential. One notable application is in machine learning, where Fully Homomorphic Encryption (FHE) can play a crucial role in safeguarding user privacy. In this paper, we focus on TFHE and develop novel homomorphic operators designed to enable the construction of precise and adaptable homomorphic floating-point operations. Integrating floating-point arithmetic within the context of FHE is particularly challenging due to constraints such as small message space and the lack of information during computation. Despite these challenges, we were able to determine parameters for common precisions (e.g., 32-bit, 64-bit) and achieve remarkable computational speeds, with 32-bit floating-point additions completing in 2.5 seconds and multiplications in approximately 1 second in a multi-threaded environment. These metrics provide empirical evidence of the efficiency and practicality of our proposed methods, which significantly outperform previous efforts. Our results demonstrate a significant advancement in the practical application of FHE, making it more viable for real-world scenarios and bridging the gap between theoretical encryption techniques and practical usability.

Fully Homomorphic Encryption (FHE) enables privacy-preserving computation and has many applications. However, its practical implementation faces massive computation and memory overheads. To address this bottleneck, several Application-Specific Integrated Circuit (ASIC) FHE accelerators have been proposed. All these prior works put every component needed for FHE onto one chip (monolithic), hence offering high performance. However, they encounter common challenges associated with large-scale chip design, such as inflexibility, low yield, and high manufacturing costs. In this paper, we present the first-of-its-kind multi-chiplet-based FHE accelerator ‘REED’ for overcoming the limitations of prior monolithic designs. To utilize the advantages of multi-chiplet structures while matching the performance of larger monolithic systems, we propose and implement several novel strategies in the context of FHE. These include a scalable chiplet design approach, an effective framework for workload distribution, a custom inter-chiplet communication strategy, and advanced pipelined Number Theoretic Transform and automorphism design to enhance performance.Our instruction-set and power simulations experiments with a prelayout netlist indicate that REED 2.5D microprocessor consumes 96.7mm2 chip area, 49.4Waverage power in 7nm technology. It could achieve a remarkable speedup of up to 2,991x compared to a CPU (24-core 2xIntel X5690) and offer 1.9x better performance, along with a 50% reduction in development costs when compared to state-of-the-art ASIC FHE accelerators. Furthermore, our work presents the first instance of benchmarking an encrypted deep neural network (DNN) training. Overall, the REED architecture design offers a highly effective solution for accelerating FHE, thereby significantly advancing the practicality and deployability of FHE in real-world applications.

This paper presents KyberSlash1 and KyberSlash2 – two timing vulnerabilities in several implementations (including the official reference code) of the Kyber Post-Quantum Key Encapsulation Mechanism, recently standardized as ML-KEM. We demonstrate the exploitability of both KyberSlash1 and KyberSlash2 on two popular platforms: the Raspberry Pi 2 (Arm Cortex-A7) and the Arm Cortex-M4 microprocessor. Kyber secret keys are reliably recovered within minutes for KyberSlash2 and a few hours for KyberSlash1. We responsibly disclosed these vulnerabilities to maintainers of various libraries and they have swiftly been patched. We present two approaches for detecting and avoiding similar vulnerabilities. First, we patch the dynamic analysis tool Valgrind to allow detection of variable-time instructions operating on secret data, and apply it to more than 1000 implementations of cryptographic primitives in SUPERCOP. We report multiple findings. Second, we propose a more rigid approach to guarantee the absence of variable-time instructions in cryptographic software using formal methods.

At CHES 2024, Time Sharing Masking (TSM) was introduced as a novel low-latency masking technique for hardware circuits. TSM offers area and randomness efficiency, as well as glitch-extended PINI security, but it is limited to first-order security. We address this limitation and generalize TSM to higher-order security while maintaining all of TSM’s advantages. Additionally, we propose an area-latency tradeoff. We prove HO-TSM glitch-extended PINI security and successfully evaluate our circuits using formal verification tools. Furthermore, we demonstrate area- and latency-efficient implementations of the AES S-box, which do not exhibit leakage in TVLA on FPGA. Our proposed tradeoff enables a first-order secure implementation of a complete AES-128 encryption core with 92 kGE, 920 random bits per round, and 20 cycles of latency, which does not exhibit leakage in TVLA on FPGA.

Capability architectures such as CHERI (Capability Hardware Enhanced RISC Instructions) are an emerging technology designed to provide memory safety protection at the hardware level and are equipped to eradicate approximately 70% of the current software vulnerability attack surface. CHERI is an instruction set architecture extension and has been applied to a small number of processors, including various versions of RISC-V. One of the benefits of CHERI is that it inherently provides segregation or compartmentalisation of software, making it suitable for supporting other types of applications such as Trusted Execution Environments, where sensitive data and computation is conducted inside a secure enclave, away from the rest of the untrusted operating system and services. To prevent untrusted software from accessing these compartments or secure regions of memory CHERI uses the mechanism of sealed capabilities. Trusted execution environments however, have been proven vulnerable to not just software-based attacks, but hardware attacks as well. In this paper we present our CHERI-Crypt design, an encryption engine extension to a CHERI-RISC-V 32-bit processor, for transparent memory encryption of sealed CHERI capabilities to additionally protect sensitive data in memory against physical hardware attacks. We show that our CHERI-Crypt design can run an enclave test program within an encrypted CHERI seal and invoke process, requiring 626 additional clock cycles with a batch size of 32 bytes. Adding CHERI-Crypt reduces the maximum frequency of the base CPU by only 6 MHz, and requires approximately 3.5x more flip flops and LUTs.

Side-Channel Attacks (SCAs) pose a significant threat to data security in embedded environments. To counteract the power-based SCAs, masking is a widely used defense technique, that introduces randomness to obscure the sidechannel information generated during the processing of secret data. However, in practice, some challenges exist when implementing masking schemes. For example, in the implementation of Boolean masking, they may refer to low noise level and implementation flaws. To address the said implementation challenges, we present an effective and efficient solution that incorporates the code-based masking technique: We mask the shares of Boolean masking with code-based masking and then use a selfdesigned Instruction Set Extension (ISE) to perform efficient private computations within this masked domain. Based on a 32-bit RISC-V Ibex core, we develop a prototype implementation of our ISE, whereby it mainly wraps the ALU with three code-based encoders/decoders and integrates a leakage-resilient pseudo-random generator (PRG). Compared to the base core (vanilla Ibex), the hardware overhead of the ISE implementation is only 8%. The security evaluation based on formal verification and practical evaluation demonstrates that our ISE can provide a more robust practical security guarantee. Furthermore, our approach significantly reduces the signal-to-noise ratio (SNR) of each share, decreasing it to just 2% of the original SNR on the base core.

Side-channel analysis benefits a lot from deep learning techniques, which assist attackers in recovering the secret key with fewer attack traces than before, but it remains a problem to precisely measure deep learning model performance, so as to obtain a high-performance model. Commonly used evaluation metrics for deep learning like accuracy and precision cannot well meet the demand due to their deviation in side-channel analysis, and classical evaluation metrics for side-channel analysis like guessing entropy, success rate and TGE1 are not generic because they effectively evaluate model performance in only one of the two situations: whether models manage to recover the secret key with given attack traces or not, and not efficient because they need to be performed multiple times to counteract randomness. To attain an effective generic side-channel evaluation metric, we investigate the deterministic component of power consumption, find that the elements of score vector under a key follow a linearly transformed chi-square distribution approximately, and some wrong key hypotheses usually with top scores provide great assistance in model performance evaluation, and finally we propose a new metric called Leading Degree (LD) as well as its simplified version LD-simplified for measuring model performance, which offers similar accuracy but much better generality and efficiency compared with the classical side-channel benchmark metric TGE1, and offers similar generality and efficiency but significantly better accuracy compared with recently proposed sidechannel metrics like Label Correlation and Cross Entropy Ratio. LD/LD-simplified can be easily deployed in early stopping to avoid overfitting phenomena, and we build a bridge between LD/LD-simplified and TGE1, by observing an exponential relationship, which significantly shortens the estimating time for TGE1. At last, we apply LD as a reward function to better solve the reward function design problem in reinforcement learning-based model hyperparameter tuning of side-channel analysis, and obtain better CNN model architectures compared with the state-of-the-art models obtained by previous hyperparameter tuning methods.

We implement an optimized BGJ (Becker–Gama–Joux 2015) sieve and analyze its behavior in a study of RAM access overheads (and their minimization) in sieving algorithms for large lattice problems. Both experiment and theory points to BGJ’s inherent structure being much more memory-efficient than the BDGL (Becker–Ducas– Gama–Laahoven 2016) sieve, which uses asymptotically the fewest logical operations. In particular, a dimension-n BGJ sieve uses only 20.2075n+o(n) streaming (non-random) main memory accesses. A key insight: Bucket sizes decrease by orders of magnitude after each BGJ filtering layer, so that sub-buckets fit into successively much smaller (hence faster) storage areas. Our refined BGJ is competitive at cryptographic sizes and should outperform BDGL for all practically achievable dimensions.The above is corroborated by the results from our efficient CPU-based BGJ implementation in an optimized framework, which saves about 40% RAM footprint and is ≥ 24.5x more efficient gate-count-wise compared to the Ducas–Stevens–van Woerden 2021 4-GPU implementation, which like most prior sieving-based SVP computations is a HK3 (Herold–Kirshanova 2017) sieve. Notably, we solved the 183-dimensional SVP Darmstadt Challenge in 30 days on a 112-core server and 0.87 TB of RAM; similarly we also found a short vector in the 796-dimensional Ideal-SVP Challenge. Our implementation may offer further insights into the behavior of asymptotically “fast” sieving algorithms when applied to large-scale problems. Moreover, our refined cost estimation of SVP based on this implementation suggests that some NIST PQC candidates (e.g. Falcon-512), are not sure to meet NIST’s security requirements.

A receiver non-committing encryption (RNCE) scheme ~\cite{CFGN96,CHK05} allows one to sample a public key pk and (dummy) ciphertext ct without knowing the message m. Later, when the message is known, one can sample a secret key sk that looks like the secret key corresponding to pk, and decryption of ct produces m. In this work, we study receiver non-committing identity-based encryption (RNC-IBE). We give constructions based on standard assumptions on bilinear groups (prior works~\cite{HMNY21} require indistinguishability obfuscation). Our RNC-IBE constructions have important implications for incompressible identity based encryption. This notion was recently introduced ~\cite{GKRV24}. However, there were no constructions for the strongest security definitions in ~\cite{GKRV24}. Our RNC-IBE scheme also leads to the first incompressible IBE scheme with optimal ciphertext size, which was another open question in \cite{GKRV24}. We also give constructions for relaxed RNC-IBE (where the identity space is polynomial in the security parameter, but the public key is compact) that are based on DDH, LWE. This leads to a relaxed incompressible IBE scheme with strong security from the same assumptions.

We present BitGC, a garbling scheme for Boolean circuits with 1 bit per gate communication based on either ring learning with errors (RLWE) or NTRU assumption, with key-dependent message security. The garbling consists of 1) a homomorphically encrypted seed that can be expanded to encryption of many pseudo-random bits and 2) one-bit stitching information per gate to reconstruct garbled tables from the expanded ciphertexts. By using low-complexity PRGs, both the garbling and evaluation of each gate require only O(1) homomorphic addition/multiplication operations without bootstrapping.

We put forth a new primitive called obliviously programmable function (OPF) to construct two random-oracle-like primitives: – Universal computational extractors (UCEs), introduced by Bellare, Hoang, and Keelveedhi [3], can securely replace random oracles in various applications, including KDM-secure encryption, deterministic encryption, RSA-OAEP, universal hardcore bits, etc. – Multi-bit point obfuscation with auxiliary input (MB-AIPO). It enables upgrading CPA-secure public-key encryption (PKE) into a CCA-secure one [30] and serves as a tool to instantiate the ran- dom oracles used in the Fujisaki-Okamoto transform for lossy PKEs [32]. Despite their usefulness, constructing UCEs and MB-AIPO in the standard model is challenging. The existing constructions of both primitives [15,16] use indistinguishability obfuscation (iO) plus point functions with auxiliary input (AIPO). OPF can replace the use iO in the constructions of UCE and MB-AIPO. We use OPF plus AIPO to construct – UCE with one query for strongly unpredictable sources, – MB-AIPO for strongly unpredictable distributions and – PKE scheme that is IND-CPA secure in the presence of computationally uninvertible leakage on the secret key. We then construct OPF for NC1 circuits from lattice assumptions based on the GGH15 encodings [23], without using iO. In sum, we give new constructions of the above three primitives under the following assumptions: (1) LWE with subexponential hardness; (2) private-coin evasive LWE as- sumption for specific samplers; (3) the existence of AIPO in NC1. As a byproduct, we construct an ‘NC1-universal AIPO’ under the assumptions (1) and (2).

A multisignature scheme is used to aggregate signatures by multiple parties on a common message m into a single short signature on m. Multisignatures are used widely in practice, most notably, in proof-of-stake consensus protocols. In existing multisignature schemes, the verifier needs the public keys of all the signers in order to verify a multisignature issued by some subset of signers. We construct new practical multisignature schemes with three properties: (i) the verifier only needs to store a constant size public key in order to verify a multisignature by an arbitrary subset of parties, (ii) signature size is constant beyond the description of the signing set, and (iii) signers generate their secret signing keys locally, that is, without a distributed key generation protocol. Existing schemes satisfy properties (ii) and (iii). The new capability is property (i) which dramatically reduces the verifier's memory requirements from linear in the number of signers to constant. We give two pairing-based constructions: one in the random oracle model and one in the plain model. We also show that by relaxing property (iii), that is, allowing for a simple distributed key generation protocol, we can further improve efficiency while continuing to satisfy properties (i) and (ii). We give a pairing-based scheme and a lattice-based scheme in this relaxed model. Our pairing based constructions are closely related to a multisignature scheme due to Boneh, Drijvers, and Neven (Asiacrypt 2018), but with several key differences.

Approximate fully homomorphic encryption (FHE) schemes, such as the CKKS scheme (Cheon, Kim, Kim, Song, ASIACRYPT ’17), are among the leading schemes in terms of efficiency and are particularly suitable for Machine Learning (ML) tasks. Although efficient, approximate FHE schemes have some inherent risks: Li and Micciancio (EUROCRYPT ’21) demonstrated that while these schemes achieved the standard notion of CPA-security, they failed against a variant, IND-CPAD, in which the adversary is given limited access to the decryption oracle. Subsequently, Li, Micciancio, Schultz, and Sorrell (CRYPTO ’22) proved that with noise-flooding countermeasures which add Gaussian noise of sufficiently high variance before outputting the decrypted value, the CKKS scheme is secure. However, the variance required for provable security is very high, inducing a large loss in message precision. We consider a broad class of attacks on CKKS with noise-flooding countermeasures, which we call “semi-honest” attacks, in which an adversary obtains the view of an honest party who holds the public key and can make evaluation and decryption queries to an oracle. The ciphertexts submitted for decryption can be fresh ciphertexts, or can be ciphertexts resulting from the homomorphic evaluation of some circuit on fresh and independent ciphertexts. We analyze the concrete security of CKKS with various levels of noise- flooding in the face of such attacks. The aim of this work is to outline and precisely quantify the various trade-offs between the number of allowed decryptions before refreshing the keys, noise-flooding levels, and the concrete security of the scheme after a number of decryptions have been observed by the adversary. Due to the large dimension and modulus in typical FHE parameter sets, previous techniques even for estimating the concrete runtime of such attacks – such as those in (Dachman-Soled, Ducas, Gong, Rossi, CRYPTO ’20) – become computationally infeasible, since they involve high di- mensional and high precision matrix multiplication and inversion. We therefore develop new techniques that allow us to perform fast security estimation, even for FHE-size parameter sets.

Threshold signatures improve upon digital signatures by splitting the trust and robustness among multiple parties. In a (T, N) threshold signature any set of T parties can produce a signature but no set of less than T users can do so. Many such constructions are now available in the pre-quantum setting but post-quantum threshold schemes are still running heavy, with the state-of-the-art boasting signature sizes that are still an order of magnitude larger than post-quantum digital signatures. We propose a novel very efficient threshold signature scheme, with a signature size close to that of a single Dilithium signature for any threshold T of at most 8 users. Our construction reduces to well-studied problems (MLWE and SelfTargetMSIS) and does not need any heavy machinery, essentially consisting in just T parallel executions of the Dilithium signature scheme. Though the resulting scheme is remarkably simple, many technical difficulties, such as sharing a secret in small shares, or simulating rejecting transcripts, have kept such an efficient threshold signature out of reach until now.

Secure two-party comparison, known as Yao's millionaires' problem, has been a fundamental challenge in privacy-preserving computation. It enables two parties to compare their inputs without revealing the exact values of those inputs or relying on any trusted third party. One elegant approach to secure computation is based on homomorphic encryption. Recently, building on this approach, Carlton et al. (CT-RSA 2018) and Bourse et al. (CT-RSA 2020) presented novel solutions for the problem of secure integer comparison. These protocols have demonstrated significantly improved performance compared to the well-known and frequently used DGK protocol (ACISP 2007 and Int. J. Appl. Cryptogr. 1(4),323–324, 2009). In this paper, we introduce a class of higher residuosity attacks, which can be regarded as an extension of the classical quadratic residuosity attack on the decisional Diffie-Hellman problem. We demonstrate that the small RSA subgroup decision problems, upon which both the CEK and BST protocols are based, are not difficult to solve when the prime base \( p_0 \) is small (e.g., \( p_0 < 100 \)). Under these conditions, the protocols achieve optimal overall performance. Furthermore, we offer recommendations for precluding such attacks, including one approach that does not adversely affect performance. We hope that these attacks can be applied to analyze other number-theoretic hardness assumptions.

Considering security against quantum adversaries, while it is important to consider the traditional existential unforgeability (EUF-CMA security), it is desirable to consider security against adversaries making quantum queries to the signing oracle: Plus-one security (PO security) and blind unforgeability (BU security) proposed by Boneh and Zhandry (Crypto 2013) and Alagic et al. (EUROCRYPT 2020), respectively. Hash-and-sign is one of the most common paradigms for constructing EUF-CMA-secure signature schemes in the quantum random oracle model, employing a trapdoor function and a hash function. It is known that its derandomized version is PO- and BU-secure. A variant of hash-and-sign, known as hash-and-sign with retry (HSwR), formulated by Kosuge and Xagawa (PKC 2024), is widespread since it allows for weakening the security assumptions of a trapdoor function. Unfortunately, it has not been known whether HSwR can achieve PO- and BU-secure even with derandomization. In this paper, we apply a derandomization with bounded loops to HSwR. We demonstrate that HSwR can achieve PO and BU security through this approach. Since derandomization with bounded loops offers advantages in some implementations, our results support its wider adoption, including in NIST PQC candidates.

The Fiat-Shamir transform is one of the most widely applied methods for secure signature construction. Fiat-Shamir starts with an interactive zero-knowledge identification protocol and transforms this via a hash function into a non-interactive signature. The protocol's zero-knowledge property ensures that a signature does not leak information on its secret key $\vec s$, which is achieved by blinding $\vec s$ via proper randomness~$\vec y$. Most prominent Fiat-Shamir examples are DSA signatures and the new post-quantum standard Dilithium. In practice, DSA signatures have experienced fatal attacks via leakage of a few bits of the randomness~$\vec y$ per signature. Similar attacks now emerge for lattice-based signatures, such as Dilithium. We build on, improve and generalize the pioneering leakage attack on Dilithium by Liu, Zhou, Sun, Wang, Zhang, and Ming. {In theory}, their original attack can recover a 256-dimensional subkey of Dilithium-II (aka ML-DSA-44) from leakage in a single bit of $\vec{y}$ per signature, in any bit position $j \geq 6$. However, the memory requirement of their attack grows exponentially in the bit position $j$ of the leak. As a consequence, if the bit leak is in a high-order position, then their attack is infeasible. In our improved attack, we introduce a novel transformation, that allows us to get rid of the exponential memory requirement. Thereby, we make the attack feasible for \emph{all} bit positions $j \geq 6$. Furthermore, our novel transformation significantly reduces the number of required signatures in the attack. The attack applies more generally to all Fiat-Shamir-type lattice-based signatures. For a signature scheme based on module LWE over an $\ell$-dimensional module, the attack uses a 1-bit leak per signature to efficiently recover a $\frac{1}{\ell}$-fraction of the secret key. In the ring LWE setting, which can be seen as module LWE with $\ell = 1$, the attack thus recovers the whole key. For Dilithium-II, which uses $\ell = 4$, knowledge of a $\frac{1}{4}$-fraction of the 1024-dimensional secret key lets its security estimate drop significantly from $128$ to $84$ bits.

Multi-signatures allow a given set of parties to cooperate in order to create a digital signature whose size is independent of the number of signers. At the same time, no other set of parties can create such a signature. While non-interactive multi-signatures are known (e.g. BLS from pairings), many popular multi-signature schemes such as MuSig2 (which are constructed from pairing-free discrete logarithm-style assumptions) require interaction. Such interactive multi-signatures have recently found practical applications e.g. in the cryptocurrency space. Motivated by classical and emerging use cases of such interactive multi-signatures, we introduce the first systematic treatment of interactive multi-signatures in the universal composability (UC) framework. Along the way, we revisit existing game-based security notions and prove that constructions secure in the game-based setting can easily be made UC secure and vice versa. In addition, we consider interactive multi-signatures where the signers must interact in a fixed pattern (so-called ordered multi-signatures). Here, we provide the first construction of ordered multi-signatures based on the one-more discrete logarithm assumption, whereas the only other previously known construction required pairings. Our scheme achieves a stronger notion of unforgeability, guaranteeing that the adversary cannot obtain a signature altering the relative order of honest signers. We also present the first formalization of ordered multi-signatures in the UC framework and again show that our stronger game-based definitions are equivalent to UC security.

Registered Attribute-Based Encryption (RABE) enhances traditional attribute-based encryption by allowing users to register their own public keys, while a key curator transparently aggregates these keys into a compact master public key, addressing key escrow issues. In long-term applications, the compromise of users' secret keys becomes a significant risk, making key revocation a critical functionality. In this paper, we initiate a formal study of key revocation mechanisms for RABE and introduce two types: Deletable Registered Attribute-Based Encryption (DRABE) and Directly Revocable Registered Attribute-Based Encryption (RRABE). The key distinction between these two approaches lies in how the revocation process is managed. In DRABE, the key curator handles revocation by deleting previously registered keys and updating the master public key. In contrast, RRABE bypasses the need for such updates, allowing the encryptor to directly specify a set of revoked users during encryption. Our primary contribution is the construction of DRABE, where we propose a generic framework based on Slotted Registered Attribute-Based Encryption (sRABE), a primitive introduced by Hohenberger et al. at EUROCRYPT 2023. This generic construction inherits the predicate structure of the underlying sRABE scheme, enabling DRABE to support a wide range of predicates. By instantiating our construction with existing sRABE schemes, we obtain efficient pairing-based DRABE schemes for a bounded number of users, as well as schemes for an unbounded number of users, though the latter relies on non-black-box cryptographic techniques. For RRABE, we propose a semi-generic construction for Boolean formulae, utilizing RABE schemes that support these predicates.

Let $\star: G \times X \rightarrow X$ be the action of a group $G$ of size $N=|G|$ on a set $X$. Let $y = g \star x \in X$ be a {\em group action dlog} instance, where our goal is to compute the unknown group element $g \in G$ from the known set elements $x,y \in X$. The Galbraith-Hess-Smart (GHS) collision finding algorithm solves the group action dlog in $N^{\frac 1 2}$ steps with polynomial memory. We show that group action dlogs are suitable for precomputation attacks. More precisely, for any $s,t$ our precomputation algorithm computes within $st$ steps a hint of space complexity $s$, which allows to solve any group action dlog in an online phase within $t$ steps. A typical instantiation is $s=t=N^{\frac 1 3}$, which gives precomputation time $N^{\frac 2 3}$ and space~$N^{\frac 1 3}$, and online time only $N^{\frac 1 3}$. Moreover, we show that solving multiple group action dlog instances $y_1, \ldots , y_m$ allows for speedups. Namely, our collision finding algorithm solves $m$ group action dlogs in $\sqrt{m}N^{\frac 1 2}$ steps, instead of the straight-forward $mN^{\frac 1 2}$ steps required for running $m$ times GHS. Our multiple instance approach can be combined with our precomputations, allowing for a variety of tradeoffs. Technically, our precomputation and multiple instance group action dlog attacks are adaptations of the techniques from the standard dlog setting in abelian groups. While such an adaptation seems natural, it is per se unclear which techniques transfer from the dlog to the more general group action dlog setting, for which $X$ does not offer a group structure. Our algorithms have direct implications for all group action based cryptosystems, such as CSIDH and its variants. We provide experimental evidence that our techniques work well in the CSIDH setting.

Mixnets are powerful building blocks for providing anonymity in applications like electronic voting and anonymous messaging. The encryption schemes upon which traditional mixnets are built, as well as the zero-knowledge proofs used to provide verifiability, will, however, soon become insecure once a cryptographically-relevant quantum computer is built. In this work, we construct the most compact verifiable mixnet that achieves privacy and verifiability through encryption and zero-knowledge proofs based on the hardness of lattice problems, which are believed to be quantum-safe. A core component of verifiable mixnets is a proof of shuffle. The starting point for our construction is the proof of shuffle of Aranha et al. (CT-RSA 2021). We first identify an issue with the soundness proof in that work, which is also present in the adaptation of this proof in the mixnets of Aranha et al. (ACM CCS 2023) and Hough et al. (IACR CiC 2025). The issue is that one cannot directly adapt classical proofs of shuffle to the lattice setting due to the splitting structure of the rings used in lattice-based cryptography. This is not just an artifact of the proof, but a problem that manifests itself in practice, and we successfully mount an attack against the implementation of the first of the mixnets. We fix the problem and introduce a general approach for proving shuffles in splitting rings that can be of independent interest. The efficiency improvement of our mixnet over prior work is achieved by switching from re-encryption mixnets (as in the works of Aranha et al. and Hough et al.) to decryption mixnets with very efficient layering based on the hardness of the LWE and LWR problems over polynomial rings. The ciphertexts in our scheme are smaller by approximately a factor of 10X and 2X over the aforementioned instantiations, while the linear-size zero-knowledge proofs are smaller by a factor of 4X and 2X.

A verifiable delay function $\texttt{VDF}(x,T)\rightarrow (y,\pi)$ maps an input $x$ and time parameter $T$ to an output $y$ together with an efficiently verifiable proof $\pi$ certifying that $y$ was correctly computed. The function runs in $T$ sequential steps, and it should not be possible to compute $y$ much faster than that. The only known practical VDFs use sequential squaring in groups of unknown order as the sequential function, i.e., $y=x^{2^T}$. There are two constructions for the proof of exponentiation (PoE) certifying that $y=x^{2^T}$, with Wesolowski (Eurocrypt'19) having very short proofs, but they are more expensive to compute and the soundness relies on stronger assumptions than the PoE proposed by Pietrzak (ITCS'19). A recent application of VDFs by Arun, Bonneau and Clark (Asiacrypt'22) are short-lived proofs and signatures, which are proofs and signatures that are only sound for some time $t$, but after that can be forged by anyone. For this they rely on "watermarkable VDFs", where the proof embeds a prover chosen watermark. To achieve stronger notions of proofs/signatures with reusable forgeability, they rely on "zero-knowledge VDFs", where instead of the output $y$, one just proves knowledge of this output. The existing proposals for watermarkable and zero-knowledge VDFs all build on Wesolowski's PoE, for the watermarkable VDFs there's currently no security proof. In this work we give the first constructions that transform any PoEs in hidden order groups into watermarkable VDFs and into zkVDFs, solving an open question by Arun et al.. Unlike our watermarkable VDF, the zkVDF (required for reusable forgeability) is not very practical as the number of group elements in the proof is a security parameter. To address this, we introduce the notion of zero-knowledge proofs of sequential work (zkPoSW), a notion that relaxes zkVDFs by not requiring that the output is unique. We show that zkPoSW are sufficient to construct proofs or signatures with reusable forgeability, and construct efficient zkPoSW from any PoE, ultimately achieving short lived proofs and signatures that improve upon Arun et al's construction in several dimensions (faster forging times, arguably weaker assumptions). A key idea underlying our constructions is to not directly construct a (watermarked or zk) proof for $y=x^{2^T}$, but instead give a (watermarked or zk) proof for the more basic statement that $x',y'$ satisfy $x'=x^r,y'=y^r$ for some $r$, together with a normal PoE for $y'=(x')^{2^T}$.

We provide explicit descriptions for radical 2-isogenies in dimensions one, two and three using theta coordinates. These formulas allow us to efficiently navigate in the corresponding isogeny graphs. As an application of this, we implement different versions of the CGL hash function. Notably, the three-dimensional version is fastest, which demonstrates yet another potential of using higher dimensional isogeny graphs in cryptography.

There is a heavy preference towards instantiating BGV and BFV homomorphic encryption schemes where the cyclotomic order m is a power of two, as this admits highly efficient fast Fourier transformations. Field Instruction Multiple Data (FIMD) was introduced to increase packing capacity in the case of small primes and improve amortised performance, using reverse multiplication-friendly embeddings (RMFEs) to encode more data into each SIMD slot. However, FIMD currently does not admit bootstrapping. In this work, we achieve bootstrapping for RMFE-packed ciphertexts with low capacity loss. We first adapt the digit extraction algorithm to work over RMFE-packed ciphertexts, by applying the recode map after every evaluation of the lifting polynomial. This allows us to follow the blueprint of thin bootstrapping, performing digit extraction on a single ciphertext. To achieve the low capacity loss, we introduce correction maps to the Halevi-Shoup digit extraction algorithm, to remove all but the final recode of RMFE digit extraction. We implement several workflows for bootstrapping RMFE-packed ciphertexts in HElib, and benchmark them against thin bootstrapping for m=32768. Our experiments show that the basic strategy of recoding multiple times in digit extraction yield better data packing, but result in very low remaining capacity and latencies of up to hundreds of seconds. On the other hand, using correction maps gives up to 6 additional multiplicative depth and brings latencies often below 10 seconds, at the cost of lower packing capacity.

Multi-signatures allow to combine several individual signatures into a compact one and verify it against a short aggregated key. Compared to threshold signatures, multi-signatures enjoy non-interactive key generation but give up on the threshold-setting. Recent works by Das et al. (CCS'23) and Garg et al. (S&P'24) show how multi-signatures can be turned into schemes that enable efficient verification when an ad hoc threshold -- determined only at verification -- is satisfied. This allows to keep the simple key generation of multi-signatures and support flexible threshold settings in the signing process later on. Both works use the same idea of combining BLS multi-signatures with inner-product proofs over committed keys. Das et al. give a somewhat generic proof from both building blocks, which we show to be flawed, whereas Garg et al. give a direct proof for the combined construction in the algebraic group model. In this work, we identify the common blueprint used in both works and abstract the proof-based approach through the building block of a commit-and-prove system for vectors (CP). We formally define a flexible set of security properties for the CP system and show how it can be securely combined with a multi-signature to yield a signature with ad hoc thresholds. Our scheme also lifts the threshold signatures into the multiverse setting recently introduced by Baird et al. (S&P'23), which allows signers to re-use their long-term keys across several groups. The challenge in the generic construction is to express -- and realize -- the combination of homomorphic proofs and commitments (needed to realize flexible thresholds over fixed group keys) and their simulation extractability (needed in the threshold signature security proof). We finally show that a CP instantiation closely following the ideas of Das et al. can be proven secure, but requires a new flexible-base DL-assumption to do so.

In this work, we explore the field of lattice-based Predicate Encryption (PE), with a focus on enhancing compactness and refining functionality. First, we present a more compact bounded collusion predicate encryption scheme compared to previous constructions, significantly reducing both the per-unit expansion and fixed overhead, while maintaining an optimal linear blow-up proportional to $Q$. Next, we propose a Predicate Inner Product Functional Encryption (P-IPFE) scheme based on our constructed predicate encryption scheme. P-IPFE preserves the attribute-hiding property while enabling decryption to reveal only the inner product between the key and message vectors, rather than the entire message as in traditional PE. Our P-IPFE scheme also achieves bounded collusion resistance while inheriting the linear compactness optimized in the underlying PE scheme. Additionally, it supports any polynomial-sized and bounded-depth circuits, thereby extending beyond the inner-product predicate class in prior works. Furthermore, all the proposed schemes achieve selective fully attribute-hiding security in the simulation-based model, therefore, can further attain semi-adaptive security by adopting existing upgrading techniques.

The Leftover Hash Lemma (LHL) is a powerful tool for extracting randomness from an entropic distribution, with numerous applications in cryptography. LHLs for discrete Gaussians have been explored in both integer settings by Gentry et al. (GPV, STOC'08) and algebraic ring settings by Lyubashevsky et al. (LPR, Eurocrypt'13). However, the existing LHLs for discrete Gaussians have two main limitations: they require the Gaussian parameter to be larger than certain smoothing parameters, and they cannot handle cases where fixed and arbitrary information is leaked. In this work, we present new LHLs for discrete Gaussians in both integer and ring settings. Our results show that the Gaussian parameter can be improved by a factor of $\omega(\sqrt{\log\lambda})$ and $O(\sqrt{N})$ compared to the regularity lemmas of GPV and LPR, respectively, under similar parameter choices such as the dimension and ring. Furthermore, our new LHLs can be applied to leaked discrete Gaussians, and the result can be used to establish asymptotic hardness of the extended MLWE assumptions, addressing an open question in recent works by Lyubashevsky et al. (LNP, Crypto'22). Our central techniques involve new fine-grained analyses of the min-entropy in discrete Gaussians modulo sublattices and should be of interest.

We consider adversaries able to perform a nonzero but small number of discrete logarithm computations, as would be expected with near-term quantum computers. Schemes with public parameters consisting of a few group elements are now at risk; could an adversary knowing the discrete logarithms of these elements go on to easily compromise the security of many users? We study this question for known schemes and find, across them, a perhaps surprising variance in the answers. In a first class are schemes, including Okamoto and Katz-Wang signatures, that we show fully retain security even when the discrete logs of the group elements in their parameters are known to the adversary. In a second class are schemes like Cramer-Shoup encryption and the SPAKE2 password-authenticated key exchange protocol that we show retain some partial but still meaningful and valuable security. In the last class are schemes we show by attack to totally break. The distinctions uncovered by these results shed light on the security of classical schemes in a setting of immediate importance, and help make choices moving forward.

Algorithm-Substitution Attacks (ASAs) have traditionally targeted secretly-keyed algorithms (for example, symmetric encryption or signing) with the goal of undetectably exfiltrating the underlying key. We initiate work in a new direction, namely ASAs on algorithms that are public, meaning contain no secret-key material. Examples are hash functions, and verification algorithms of signature schemes or non-interactive arguments. In what we call a PA-SA (Public-Algorithm Substitution Attack), the big-brother adversary replaces the public algorithm $f$ with a subverted algorithm, while retaining a backdoor to the latter. Since there is no secret key to exfiltrate, one has to ask what a PA-SA aims to do. We answer this with definitions that consider big-brother's goal for the PA-SA to be three-fold: it desires utility (it can break an $f$-using scheme or application), undetectability (outsiders can't detect the substitution) and exclusivity (nobody other than big-brother can exploit the substitution). We start with a general setting in which $f$ is arbitrary, formalizing strong definitions for the three goals, and then give a construction of a PA-SA that we prove meets them. We use this to derive, as applications, PA-SAs on hash functions, signature verification and verification of non-interactive arguments, exhibiting new and effective ways to subvert these. As a further application of the first two, we give a PA-SA on X.509 TLS certificates. Our constructions serve to help defenders and developers identify potential attacks by illustrating how they might be built.

We explore advanced security notions for threshold signature schemes, focusing on Beyond UnForgeability Features (BUFF), introduced by Cremers et al. (S&P’21) in the non-threshold setting. The BUFF properties protect against attacks based on maliciously chosen keys, e.g., expropriating a message-signature pair under a new public key (called exclusive ownership). We first formalize these notions in the threshold setting and examine their relationships. Notably, unlike regular signature schemes, the hierarchy of variants of exclusive ownership notions only holds for threshold schemes if they are also robust. We then present a generic compiler that transforms any threshold signature scheme to satisfy exclusive ownership, and message-bound signature properties with minimal overhead. Furthermore, we modify the threshold BLS signature scheme to achieve these additional properties without increasing signature size. Lastly, we identify specific structures in threshold signature schemes where BUFF properties can be naturally extended from the underlying standard signature scheme, and we analyze and prove the security properties in some of the existing threshold schemes.

We study blockchain-based provably anonymous payment systems between \emph{light clients}. Such clients interact with the blockchain through full nodes, which can see what the light clients read and write. The goal of our work is to enable light clients to perform anonymous payments, while maintaining privacy even against the full nodes through which they interact with the blockchain. We formalize the problem in the UC model and present a provably secure solution. We show that a variation of tree ORAM gives obliviousness even when an adversary can follow how its own data elements move in the tree. We use this for anonymity via shuffling of payments on the blockchain, while at the same time allowing the light client to know a few positions among which to find its payment without knowing the current state of the blockchain. In comparison to existing works, we are the first ones that simultaneously provide strong anonymity guarantees, provable security, and anonymity with respect to full nodes. Along the way, we make several contributions that may be of independent interest. We define and construct anonymous-coin friendly encryption schemes and show how they can be used within anonymous payment systems. We define and construct efficient compressible randomness beacons, which produce unpredictable values in regular intervals and allow for storing all published values in a short digest.

Non-interactive zero-knowledge proofs (NIZK) are essential building blocks in threshold cryptosystems like multiparty signatures, distributed key generation, and verifiable secret sharing, allowing parties to prove correct behavior without revealing secrets. Furthermore, universally composable (UC) NIZKs enable seamless composition in the larger cryptosystems. A popular way to construct NIZKs is to compile interactive protocols using the Fiat-Shamir transform. Unfortunately, Fiat-Shamir transformed NIZK requires rewinding the adversary and is not *straight-line extractable*, making it at odds with UC. Using Fischlin's transform gives straight-line extractability, but at the expense of many repetitions of the underlying protocol leading to poor concrete efficiency and difficulty in setting parameters. In this work, we propose a simple new transform that compiles a Sigma protocol for an algebraic relation into a UC-NIZK protocol *without any overheads of repetition*. - Given a Sigma protocol for proving m algebraic statements over n witnesses, we construct a compiler to transform it into a *straight-line extractable* protocol using an additively homomorphic encryption scheme AHE. Our prover executes the Sigma protocol's prover once and computes 2n encryptions. The verification process involves running the Sigma protocol verifier once and then computing n encryptions, which are homomorphically verified against the prover generated encryptions. We apply the Fiat-Shamir transform to the above straight-line extractable Sigma protocol to obtain a UC-NIZK. We instantiate AHE using class group-based encryption where the public key of the encryption scheme is obliviously sampled using a suitable hash function. This yields a UC-NIZK protocol in the random oracle model.

Multi-signatures allow a set of parties to produce a single signature for a common message by combining their individual signatures. The result can be verified using the aggregated public key that represents the group of signers. Very recent work by Lehmann and Özbay (PKC '24) studied the use of multi-signatures for ad-hoc privacy-preserving group signing, formalizing the notion of multi-signatures with probabilistic yet verifiable key aggregation. Moreover, they proposed new BLS-type multi-signatures, allowing users holding a long-term key pair to engage with different groups, without the aggregated key leaking anything about the corresponding group. This enables key-reuse across different groups in a privacy-preserving way. Unfortunately, their technique cannot be applied to Schnorr-type multi-signatures, preventing state-of-the-art multi-signatures to benefit from those privacy features. In this work, we revisit the privacy framework from Lehmann and Özbay. Our first contribution is a generic lift that adds privacy to any multi-signature with deterministic key aggregation. As our second contribution, we study two concrete multi-signatures, and give dedicated transforms that take advantage of the underlying structures for improved efficiency. The first one is a slight modification of the popular MuSig2 scheme, achieving the strongest privacy property for free compared to the original scheme. The second is a variant of the lattice-based multi-signature scheme DualMS, making our construction the first post-quantum secure multi-signature for ad-hoc privacy-preserving group signing. The light overhead incurred by the modifications in our DualMS variant still allow us to benefit from the competitiveness of the original scheme.

An $(n, t)$-Verifiable Secret Sharing (VSS) scheme allows a dealer to share a secret among $n$ parties, s.t. all the parties can verify the validity of their shares and only a set of them, i.e., more than $t$, can access the secret. In this paper, we present $\Pi$, as a unified framework for constructing computational VSS schemes in the honest-majority setting, based on Shamir secret sharing. Notably, $\Pi$ does not rely on homomorphic commitments; instead requires a random oracle and any commitment scheme that extra to its core attributes hiding and binding, it might be homomorphic and/or Post-Quantum (PQ) secure. - When employing Discrete Logarithm (DL)-based commitments, $\Pi$ enables the construction of two novel VSS schemes in the RO model, named $\Pi_P$ and $\Pi_F$. Compared to the well-known Pedersen and Feldman VSS schemes, both $\Pi_P$ and $\Pi_F$ require $O(1)$ (resp. $O(t)$) exponentiations in the verification (resp. reconstruction) process, as opposed to $O(t)$ (resp. $O(t^2)$), albeit at the expense of a constant factor slower sharing and increased communication. - By instantiating $\Pi$ with a hash-based commitment, we obtain a novel PQ-secure VSS scheme, labeled $\Pi_{LA}$. \Pi_{LA}} outperforms the recent protocol by Atapoor, Baghery, Cozzo, and Pedersen from Asiacrypt'23 by a constant factor in all metrics. $\Pi_{LA}$ can also be seen as an amplified version of the simple VSS scheme, proposed by Gennaro, Rabin, and Rabin at PODC'98. - Building upon $\Pi_F$, we construct a Publicly VSS (PVSS) scheme, labeled $\Pi_S$, that can be seen as a new variant of Schoenmakers' scheme from Crypto'99. To this end, we first define the Polynomial Discrete Logarithm (PDL) problem, as a generalization of DL and then build a variant of the Schnorr Proof of Knowledge (PoK) scheme based on the new hardness assumption. We think the PDL relation and the associated PoK scheme can be independently interesting for Shamir-based threshold protocols. We believe $\Pi$ is general enough to be employed in various contexts such as lattices, isogenies, and an extensive array of practical use cases.

Key-exfiltration attacks on cryptographic keys represent a significant threat to computer security. One proposed defense against such attacks is big-key cryptography which seeks to make cryptographic secrets so large that it is infeasible for an adversary to exfiltrate the key (without being detected). However, this also introduces an inconvenience to the user who must now store the large key on all of their different devices. The work of Döttling, Garg, Sekar and Wang (TCC 2022) introduces an elegant solution to this problem in the form of big-key identity-based encryption (IBE). Here, there is a large master secret key, but very short identity keys. The user can now store the large master secret key as her long-term key, and can provision each of her devices with short ephemeral identity keys (say, corresponding to the current date). In this way, the long-term secret key is protected by conventional big-key cryptography, while the user only needs to distribute short ephemeral keys to their different devices. Döttling et al. introduce and construct big-key IBE from standard pairing-based assumptions. However, their scheme only satisfies selective security where the adversary has to declare its challenge set of identities at the beginning of the security game. The more natural notion of security is adaptive security where the user can adaptively choose which identities it wants to challenge after seeing the public parameters (and part of the master secret key). In this work, we give the first adaptively-secure construction of big-key IBE from standard cryptographic assumptions. Our first construction relies on indistinguishability obfuscation (and one-way functions), while our second construction relies on witness encryption for NP together with standard pairing-based assumptions. To prove adaptive security, we rely on the dual-system methodology.

Ratcheted key exchange captures the heart of modern secure messaging, wherein protocol participants continuously update their secret material to protect against full state exposure through forward security (protecting past secrets and messages) and post-compromise security (recovering from compromise). However, many practical attacks only provide the adversary with partial information about the secret state of a given party, an attack vector that has been extensively studied under the umbrella of leakage resilience. Existing models of ratcheted key exchange or messaging therefore provide less-than-optimal guarantees under partial leakage due to inherent limitations in security under full state exposure that are exacerbated by relaxations in security made by many practical protocols for performance reasons. In this work, we initiate the study of leakage-resilient ratcheted key exchange that provides typical guarantees under full state exposure and additional guarantees under partial state exposure between ratchets of the protocol. We consider unidirectional ratcheted key exchange (URKE) where one party acts as the sender and the other as receiver. Starting from the notions of Balli et al. introduced at ASIACRYPT 2020, we formalise a key indistinguishability game under randomness manipulation and bounded leakage (KIND), which in particular enables the adversary to continually leak a bounded amount of the sender's state between honest send calls. We construct a corresponding protocol from a key-updatable key encapsulation mechanism (kuKEM) and a leakage-resilient one-time MAC. By instantiating this MAC in the random oracle model (ROM), results from Balli et al. imply that in the ROM, kuKEM and KIND-secure URKE are equally powerful, i.e., can be built from each other. As a second step, given the strong limitations that key indistinguishability imposes on the adversary, we formalise a one-wayness game that also permits leakage on the receiver. We then propose a corresponding construction from leakage-resilient kuKEM, which we introduce, and a leakage-resilient one-time MAC. Furthermore, we show that leakage-resilient kuKEM and one-way-secure URKE can be built from each other in the ROM, highlighting the increased cost that strong one-way security entails. Our work opens exciting directions for developing practical, leakage-resilient messaging protocols.