658 results sorted by ID
Possible spell-corrected query: definition
Composing Timed Cryptographic Protocols: Foundations and Applications
Karim Eldefrawy, Benjamin Terner, Moti Yung
Foundations
Time-lock puzzles are unique cryptographic primitives that use computational complexity to keep information secret for some period of time, after which security expires. Unfortunately, current analysis techniques of time-lock primitives provide no sound mechanism to build multi-party cryptographic protocols which use expiring security as a building block. We explain in this paper that all other attempts at this subtle problem lack either composability, a fully consistent analysis, or...
Cryptographic Accumulators: New Definitions, Enhanced Security, and Delegatable Proofs
Anaïs Barthoulot, Olivier Blazy, Sébastien Canard
Public-key cryptography
Cryptographic accumulators, introduced in 1993 by Benaloh and De
Mare, represent a set with a concise value and offer proofs of (non-)membership. Accumulators have evolved, becoming essential in anonymous credentials, e-cash, and blockchain applications. Various properties like dynamic and universal emerged for specific needs, leading to multiple accumulator definitions. In 2015, Derler, Hanser, and Slamanig proposed a unified model, but new properties, including zero-knowledge security,...
Lattice-Based Succinct Mercurial Functional Commitment for Circuits: Definitions and Constructions
Hongxiao Wang, Siu-Ming Yiu, Yanmin Zhao, Zoe L. Jiang, Min Xie
Foundations
Vector commitments gain a lot of attention because of their wide usage in applications such as blockchain and accumulator. Mercurial vector commitments and mercurial functional commitments (MFC), as significant variants of VC, are the central techniques to construct more advanced cryptographic primitives such as zero-knowledge set and zero-knowledge functional elementary database (ZK-FEDB).
However, the current MFC only supports linear functions, limiting its application, i.e. building the...
Subverting Cryptographic Protocols from A Fine-Grained Perspective - A Case Study on 2-Party ECDSA
Jialiu Cheng, Yi Wang, Rongmao Chen, Xinyi Huang
Cryptographic protocols
The revelations of Edward Snowden in 2013 rekindled concerns within the cryptographic community regarding the potential subversion of cryptographic systems. Bellare et al. (CRYPTO'14) introduced the notion of Algorithm Substitution Attacks (ASAs), which aim to covertly leak sensitive information by undermining individual cryptographic primitives. In this work, we delve deeply into the realm of ASAs against protocols built upon cryptographic primitives. In particular, we revisit the existing...
Highly-Effective Backdoors for Hash Functions and Beyond
Mihir Bellare, Doreen Riepel, Laura Shea
Applications
We study the possibility of schemes whose public parameters have been generated along with a backdoor. We consider the goal of the big-brother adversary to be two-fold: It desires utility (it can break the scheme) but also exclusivity (nobody else can). Starting with hash functions, we give new, strong definitions for these two goals, calling the combination high effectiveness. We then present a construction of a backdoored hash function that is highly effective, meaning provably meets our...
Privacy Preserving Biometric Authentication for Fingerprints and Beyond
Marina Blanton, Dennis Murphy
Cryptographic protocols
Biometric authentication eliminates the need for users to remember secrets and serves as a convenient mechanism for user authentication. Traditional implementations of biometric-based authentication store sensitive user biometry on the server and the server becomes an attractive target of attack and a source of large-scale unintended disclosure of biometric data. To mitigate the problem, we can resort to privacy-preserving computation and store only protected biometrics on the server. While...
Updatable Policy-Compliant Signatures
Christian Badertscher, Monosij Maitra, Christian Matt, Hendrik Waldner
Cryptographic protocols
Policy-compliant signatures (PCS) are a recently introduced primitive by Badertscher et
al. [TCC 2021] in which a central authority distributes secret and public keys associated with sets of attributes (e.g., nationality, affiliation with a specific department, or age) to its users. The authority also enforces a policy determining which senders can sign messages for which receivers based on a joint check of their attributes. For example, senders and receivers must have the same nationality,...
Anamorphic Encryption: New Constructions and Homomorphic Realizations
Dario Catalano, Emanuele Giunta, Francesco Migliaro
Public-key cryptography
The elegant paradigm of Anamorphic Encryption (Persiano et al., Eurocrypt 2022) considers the question of establishing a private communication in a world controlled by a dictator.
The challenge is to allow two users, sharing some secret anamorphic key, to exchange covert messages without the dictator noticing, even when the latter has full access to the regular secret keys.
Over the last year several works considered this question and proposed constructions, novel extensions and...
Traceable Secret Sharing: Strong Security and Efficient Constructions
Dan Boneh, Aditi Partap, Lior Rotem
Secret-key cryptography
Suppose Alice uses a $t$-out-of-$n$ secret sharing to store her secret key on $n$ servers. Her secret key is protected as long as $t$ of them do not collude. However, what if a less-than-$t$ subset of the servers decides to offer the shares they have for sale? In this case, Alice should be able to hold them accountable, or else nothing prevents them from selling her shares. With this motivation in mind, Goyal, Song, and Srinivasan (CRYPTO 21) introduced the concept of {\em traceable secret...
C'est très CHIC: A compact password-authenticated key exchange from lattice-based KEM
Afonso Arriaga, Manuel Barbosa, Stanislaw Jarecki, Marjan Skrobot
Cryptographic protocols
Several Password Authenticated Key Exchange (PAKE) protocols have been recently proposed that leverage a Key-Encapsulation Mechanism (KEM) to create an efficient and easy-to-implement post-quantum secure PAKE. This line of work is driven by the intention of the National Institute of Standards and Technology (NIST) to soon standardize a lattice-based post-quantum KEM called $\mathsf{Kyber}$. In two recent works, Beguinet et al. (ACNS 2023) and Pan and Zeng (ASIACRYPT 2023) proposed generic...
SweetPAKE: Key exchange with decoy passwords
Afonso Arriaga, Peter Y.A. Ryan, Marjan Skrobot
Cryptographic protocols
Decoy accounts are often used as an indicator of the compromise of sensitive data, such as password files. An attacker targeting only specific known-to-be-real accounts might, however, remain undetected. A more effective method proposed by Juels and Rivest at CCS'13 is to maintain additional fake passwords associated with each account. An attacker who gains access to the password file is unable to tell apart real passwords from fake passwords, and the attempted usage of a false password...
FRIDA: Data Availability Sampling from FRI
Mathias Hall-Andersen, Mark Simkin, Benedikt Wagner
Foundations
As blockchains like Ethereum continue to grow, clients with limited resources can no longer store the entire chain.
Light nodes that want to use the blockchain, without verifying that it is in a good state overall, can just download the block headers without the corresponding block contents.
As those light nodes may eventually need some of the block contents, they would like to ensure that they are in principle available.
Data availability sampling, introduced by Bassam et al., is a...
Application-Aware Approximate Homomorphic Encryption: Configuring FHE for Practical Use
Andreea Alexandru, Ahmad Al Badawi, Daniele Micciancio, Yuriy Polyakov
Public-key cryptography
Fully Homomorphic Encryption (FHE) is a powerful tool for performing privacy-preserving analytics over encrypted data. A promising method for FHE over real and complex numbers is approximate homomorphic encryption, instantiated with the Cheon-Kim-Kim-Song (CKKS) scheme. The CKKS scheme enables efficient evaluation for many privacy-preserving machine learning applications. Despite its high efficiency, there is currently a lot of confusion on how to securely instantiate CKKS for a given...
Fully Homomorphic Encryption beyond IND-CCA1 Security: Integrity through Verifiability
Mark Manulis, Jérôme Nguyen
Public-key cryptography
We focus on the problem of constructing fully homomorphic encryption (FHE) schemes that achieve some meaningful notion of adaptive chosen-ciphertext security beyond CCA1. Towards this, we propose a new notion, called security against verified chosen-ciphertext attack (vCCA). The idea behind it is to ascertain integrity of the ciphertext by imposing a strong control on the evaluation algorithm. Essentially, we require that a ciphertext obtained by the use of homomorphic evaluation must be...
Foundations of Anonymous Signatures: Formal Definitions, Simplified Requirements, and a Construction Based on General Assumptions
Jan Bobolz, Jesus Diaz, Markulf Kohlweiss
Public-key cryptography
In today's systems, privacy is often at odds with utility: users that reveal little information about themselves get restricted functionality, and service providers mistrust them. In practice, systems tip to either full anonymity (e.g. Monero), or full utility (e.g. Bitcoin). Well-known cryptographic primitives for bridging this gap exist: anonymous credentials (AC) let users disclose a subset of their credentials' attributes, revealing to service providers "just what they need"; group...
YouChoose: A Lightweight Anonymous Proof of Account Ownership
Aarav Varshney, Prashant Agrawal, Mahabir Prasad Jhanwar
Cryptographic protocols
We explore the issue of anonymously proving account ownership (anonymous PAO). Such proofs allow a prover to prove to a verifier that it owns a valid account at a server without being tracked by the server or the verifier, without requiring any changes at the server's end and without even revealing to it that any anonymous PAO is taking place. This concept is useful in sensitive applications like whistleblowing. The first introduction of anonymous PAOs was by Wang et al., who also introduced...
Practical Two-party Computational Differential Privacy with Active Security
Fredrik Meisingseth, Christian Rechberger, Fabian Schmid
Cryptographic protocols
In this work we revisit the problem of using general-purpose MPC schemes to emulate the trusted dataholder in central differential privacy, to achieve same accuracy but without the need to trust one single dataholder. In particular, we consider the two-party model of having two computational parties (or dataholders) each with their own dataset wishing to compute a canonical differentially private mechanism on their combined data and to do so with active security. We start by remarking that...
A Transaction-Level Model for Blockchain Privacy
François-Xavier Wicht, Zhipeng Wang, Duc V. Le, Christian Cachin
Applications
Considerable work explores blockchain privacy notions. Yet, it usually employs entirely different models and notations, complicating potential comparisons. In this work, we use the Transaction Directed Acyclic Graph (TDAG) and extend it to capture blockchain privacy notions (PDAG). We give consistent definitions for untraceability and unlinkability. Moreover, we specify conditions on a blockchain system to achieve each aforementioned privacy notion. Thus, we can compare the two most...
On the Security of Rate-limited Privacy Pass
Hien Chu, Khue Do, Lucjan Hanzlik
Cryptographic protocols
The privacy pass protocol allows users to redeem anonymously issued cryptographic tokens instead of solving annoying CAPTCHAs. The issuing authority verifies the credibility of the user, who can later use the pass while browsing the web using an anonymous or virtual private network. Hendrickson et al. proposed an IETF draft (privacypass-rate-limit-tokens-00) for a rate-limiting version of the privacy pass protocol, also called rate-limited Privacy Pass (RlP). Introducing a new actor called a...
That’s not my signature! Fail-stop signatures for a post-quantum world
Cecilia Boschini, Hila Dahari, Moni Naor, Eyal Ronen
Public-key cryptography
The Snowden's revelations kick-started a community-wide effort to develop cryptographic tools against mass surveillance.
In this work, we propose to add another primitive to that toolbox: Fail-Stop Signatures (FSS) [EC'89].
FSS are digital signatures enhanced with a forgery-detection mechanism that can protect a PPT signer from more powerful attackers.
Despite the fascinating concept, research in this area stalled after the '90s. However, the ongoing transition to post-quantum...
QCB is Blindly Unforgeable
Jannis Leuther, Stefan Lucks
Secret-key cryptography
QCB is a proposal for a post-quantum secure, rate-one authenticated encryption with associated data scheme (AEAD) based on classical OCB3 and \(\Theta\)CB, which are vulnerable against a quantum adversary in the Q2 setting. The authors of QCB prove integrity under plus-one unforgeability, whereas the proof of the stronger definition of blind unforgeability has been left as an open problem. After a short overview of QCB and the current state of security definitions for authentication, this...
PSKPIR: Symmetric Keyword Private Information Retrieval based on PSI with Payload
Zuodong Wu, Dawei Zhang, Yong Li, Xu Han
Applications
Symmetric Private Information Retrieval (SPIR) is a protocol that protects privacy during data transmission. However, the existing SPIR focuses only on the privacy of the data to be requested on the server, without considering practical factors such as the payload that may be present during data transmission. This could seriously prevent SPIR from being applied to many complex data scenarios and hinder its further expansion. To solve such problems, we propose a primitive (PSKPIR) for...
On the (In)Security of the BUFF Transform
Jelle Don, Serge Fehr, Yu-Hsuan Huang, Patrick Struck
Public-key cryptography
The BUFF transform is a generic transformation for digital signature schemes, with the purpose of obtaining additional security properties beyond standard unforgeability, e.g., exclusive ownership and non-resignability. In the call for additional post-quantum signatures, these were explicitly mentioned by the NIST as ``additional desirable security properties'', and some of the submissions indeed refer to the BUFF transform with the purpose of achieving them, while some other submissions...
Three Party Secure Computation with Friends and Foes
Bar Alon, Amos Beimel, Eran Omri
Cryptographic protocols
In secure multiparty computation (MPC), the goal is to allow a set of mutually distrustful parties to compute some function of their private inputs in a way that preserves security properties, even in the face of adversarial behavior by some of the parties. However, classical security definitions do not pose any privacy restrictions on the view of honest parties. Thus, if an attacker adversarially leaks private information to honest parties, it does not count as a violation of privacy. This...
CryptoZoo: A Viewer for Reduction Proofs
Chris Brzuska, Christoph Egger, Kirthivaasan Puniamurthy
Cryptographers rely on visualization to effectively communicate cryptographic constructions with one another. Visual frameworks such as constructive cryptography (TOSCA 2011), the joy of cryptography (online book) and state-separating proofs (SSPs, Asiacrypt 2018) are useful to communicate not only the construction, but also their proof visually by representing a cryptographic system as graphs.
One SSP core feature is the re-use of code, e.g., a package of code might be used in a game...
Polynomial IOPs for Memory Consistency Checks in Zero-Knowledge Virtual Machines
Yuncong Zhang, Shi-Feng Sun, Ren Zhang, Dawu Gu
Cryptographic protocols
Zero-Knowledge Virtual Machines (ZKVMs) have gained traction in recent years due to their potential applications in a variety of areas, particularly blockchain ecosystems. Despite tremendous progress on ZKVMs in the industry, no formal definitions or security proofs have been established in the literature. Due to this lack of formalization, existing protocols exhibit significant discrepancies in terms of problem definitions and performance metrics, making it difficult to analyze and compare...
Unclonable Commitments and Proofs
Vipul Goyal, Giulio Malavolta, Justin Raizes
Foundations
Non-malleable cryptography, proposed by Dolev, Dwork, and Naor (SICOMP '00), has numerous applications in protocol composition. In the context of proofs, it guarantees that an adversary who receives a proof cannot maul it into another valid proof. However, non-malleable cryptography (particularly in the non-interactive setting) suffers from an important limitation: An attacker can always copy the proof and resubmit it to another verifier (or even multiple verifiers).
In this work, we...
Accountable Decryption made Formal and Practical
Rujia Li, Yuanzhao Li, Qin Wang, Sisi Duan, Qi Wang, Mark Ryan
Cryptographic protocols
With the increasing scale and complexity of online activities, accountability, as an after-the-fact mechanism, has become an effective complementary approach to ensure system security. Decades of research have delved into the connotation of accountability. They fail, however, to achieve practical accountability of decryption. This paper seeks to address this gap. We consider the scenario where a client (called encryptor, her) encrypts her data and then chooses a delegate (a.k.a. decryptor,...
Leakage-Free Probabilistic Jasmin Programs
José Bacelar Almeida, Denis Firsov, Tiago Oliveira, Dominique Unruh
Foundations
We give a semantic characterization of leakage-freeness through timing side-channels for Jasmin programs. Our characterization also covers probabilistic Jasmin programs that are not constant-time. In addition, we provide a characterization in terms of probabilistic relational Hoare logic and prove equivalence of both definitions. We also prove that our new characterizations are compositional. Finally, we relate new definitions to the existing ones from prior work which only apply to...
Revisiting Remote State Preparation with Verifiability: A New Set of Notions with Well-behaved Properties
Jiayu Zhang
Cryptographic protocols
In remote state preparation with verifiability (RSPV), a client would like to prepare a quantum state (sampled from a state family) on the server side, such that ideally the client knows its full description, while the server holds and only holds the state itself. A closely related notion called self-testing, which is recently generalized to the single-server computationally-secure setting [MV21, aims at certifying the server's operation. These notions have been widely studied in various...
Auditable Obfuscation
Shalini Banerjee, Steven D. Galbraith
Foundations
We introduce a new variant of malicious obfuscation. Our formalism is incomparable to the existing definitions by Canetti and Varia (TCC 2010), Canetti et al. (EUROCRYPT 2022) and Badrinarayanan et al. (ASIACRYPT 2016). We show that this concept is natural and applicable to obfuscation-as-a-service platforms. We next define a new notion called auditable obfuscation which provides security against malicious obfuscation. Finally, we construct a proof of concept of the developed notions based...
Identity-Based Matchmaking Encryption, Revisited: Strong Security and Practical Constructions from Standard Classical and Post-Quantum Assumptions
Sohto Chiku, Keitaro Hashimoto, Keisuke Hara, Junji Shikata
Public-key cryptography
Identity-based matchmaking encryption (IB-ME) [Ateniese et al. Crypto 2019] allows users to communicate privately in an anonymous and authenticated manner.
After the seminal paper by Ateniese et al., a lot of work has been done on the security and construction of IB-ME.
In this work, we revisit the security definitions and construction of IB-ME and provide the following three contributions.
-- First, we embark on the task of classifying the existing security notions of IB-ME.
We...
Reframing And Extending The Random Probing Expandibility To Make Probing-Secure Compilers Tolerate A Constant Noise
Giuseppe Manzoni
Foundations
In the context of circuits leaking the internal state, there are various models to analyze what the adversary can see, like the $p$-random probing model in which the adversary can see the value of each wire with probability $p$. In this model, for a fixed $p$, it's possible to reach an arbitrary security by 'expanding' a stateless circuit via iterated compilation, reaching a security of $2^{-\kappa}$ with a polynomial size in $\kappa$.
The existing proofs of the expansion work by first...
Bicameral and Auditably Private Signatures
Khoa Nguyen, Partha Sarathi Roy, Willy Susilo, Yanhong Xu
Cryptographic protocols
This paper introduces Bicameral and Auditably Private Signatures (BAPS) -- a new privacy-preserving signature system with several novel features. In a BAPS system, given a certified attribute $\mathbf{x}$ and a certified policy $P$, a signer can issue a publicly verifiable signature $\Sigma$ on a message $m$ as long as $(m, \mathbf{x})$ satisfies $P$. A noteworthy characteristic of BAPS is that both attribute $\mathbf{x}$ and policy $P$ are kept hidden from the verifier, yet the latter is...
SoK: Public Key Encryption with Openings
Carlo Brunetta, Hans Heum, Martijn Stam
Public-key cryptography
When modelling how public key encryption can enable secure communication, we should acknowledge that secret information, such as private keys or the randomness used for encryption, could become compromised. Intuitively, one would expect unrelated communication to remain secure, yet formalizing this intuition has proven challenging. Several security notions have appeared that aim to capture said scenario, ranging from the multi-user setting with corruptions, via selective opening attacks...
Fine-Grained Proxy Re-Encryption: Definitions & Constructions from LWE
Yunxiao Zhou, Shengli Liu, Shuai Han, Haibin Zhang
Public-key cryptography
Proxy re-encryption (PRE) allows a proxy with a re-encryption key to translate a ciphertext intended for Alice (delegator) to another ciphertext intended for Bob (delegatee) without revealing the underlying message. However, with PRE, Bob can obtain the whole message from the re-encrypted ciphertext, and Alice cannot take flexible control of the extent of the message transmitted to Bob.
In this paper, we propose a new variant of PRE, called Fine-Grained PRE (FPRE), to support...
Are continuous stop-and-go mixnets provably secure?
Debajyoti Das, Claudia Diaz, Aggelos Kiayias, Thomas Zacharias
Applications
This work formally analyzes the anonymity guarantees of continuous stop-and-go mixnets and attempts to answer the above question. Existing mixnet based anonymous communication protocols that aim to provide provable anonymity guarantees rely on round-based communication models --- which requires synchronization among all the nodes and clients, and difficult to achieve in practice. Continuous stop-and-go mixnets (e.g., Loopix and Nym) provide a nice alternative by adding a random delay for...
Applications of Finite non-Abelian Simple Groups to Cryptography in the Quantum Era
María Isabel González Vasco, Delaram Kahrobaei, Eilidh McKemmie
Cryptographic protocols
The theory of finite simple groups is a (rather unexplored) area likely to provide interesting computational problems and modelling tools useful in a cryptographic context. In this note, we review some applications of finite non-abelian simple groups to cryptography and discuss different scenarios in which this theory is clearly central, providing the relevant definitions to make the material accessible to both cryptographers and group theorists, in the hope of stimulating further...
Post-Quantum Asynchronous Remote Key Generation for FIDO2 Account Recovery
Jacqueline Brendel, Sebastian Clermont, Marc Fischlin
Public-key cryptography
The Fast IDentity Online (FIDO) Alliance develops open standards to replace password-based authentication by token-based so- lutions. The latest protocol suite FIDO2 provides a promising alterna- tive which many key players have already adopted or are planning to. The central authentication mechanism WebAuthn uses cryptographic keys stored on the device to authenticate clients to a relying party via a challenge-response protocol. Yet, this approach leaves several open issues about...
Ordering Transactions with Bounded Unfairness: Definitions, Complexity and Constructions
Aggelos Kiayias, Nikos Leonardos, Yu Shen
Foundations
An important consideration in the context of distributed ledger protocols is fairness in terms of transaction ordering. Recent work [Crypto 2020] revealed a connection of (receiver) order fairness to social choice theory and related impossibility results arising from the Condorcet paradox. As a result of the impossibility, various relaxations of order fairness were proposed in prior works. Given that distributed ledger protocols, especially those processing smart contracts, must serialize...
On the Black-Box Impossibility of Multi-Designated Verifiers Signature Schemes from Ring Signature Schemes
Kyosuke Yamashita, Keisuke Hara
Foundations
From the work by Laguillaumie and Vergnaud in ICICS'04, it has been widely believed that multi-designated verifier signature schemes (MDVS) can be constructed from ring signature schemes in general.
However in this paper, somewhat surprisingly, we prove that it is impossible to construct an MDVS scheme from a ring signature scheme in a black-box sense (in the standard model).
The impossibility stems from the difference between the definitions of unforgeability.
To the best of our...
On the Security of Universal Re-Encryption
Fabio Banfi, Ueli Maurer, Silvia Ritsch
Public-key cryptography
A universal re-encryption (URE) scheme is a public-key encryption scheme enhanced with an algorithm that on input a ciphertext, outputs another ciphertext which is still a valid encryption of the underlying plaintext. Crucially, such a re-encryption algorithm does not need any key as input, but the ciphertext is guaranteed to be valid under the original key-pair. Therefore, URE schemes lend themselves naturally as building blocks of mixnets: A sender transmits the encryption of a message...
Post Quantum Fuzzy Stealth Signatures and Applications
Sihang Pu, Sri AravindaKrishnan Thyagarajan, Nico Döttling, Lucjan Hanzlik
Public-key cryptography
Private payments in blockchain-based cryptocurrencies have been a topic of research, both academic and industrial, ever since the advent of Bitcoin. Stealth address payments were proposed as a solution to improve payment privacy for users and are, in fact, deployed in several major cryptocurrencies today. The mechanism lets users receive payments so that none of these payments are linkable to each other or the recipient. Currently known stealth address mechanisms either (1) are insecure in...
Coercion Mitigation for Voting Systems with Trackers: A Selene Case Study
Kristian Gjøsteen, Thomas Haines, Morten Rotvold Solberg
Cryptographic protocols
An interesting approach to achieving verifiability in voting systems is to make use of tracking numbers. This gives voters a simple way of verifying that their ballot was counted: they can simply look up their ballot/tracker pair on a public bulletin board. It is crucial to understand how trackers affect other security properties, in particular privacy. However, existing privacy definitions are not designed to accommodate tracker-based voting systems. Furthermore, the addition of trackers...
Properties of Lattice Isomorphism as a Cryptographic Group Action
Benjamin Benčina, Alessandro Budroni, Jesús-Javier Chi-Domínguez, Mukul Kulkarni
Foundations
In recent years, the Lattice Isomorphism Problem (LIP) has served as an underlying assumption to construct quantum-resistant cryptographic primitives, e.g. the zero-knowledge proof and digital signature scheme by Ducas and van Woerden (Eurocrypt 2022), and the HAWK digital signature scheme (Asiacrypt 2022).
While prior lines of work in group action cryptography, e.g. the works of Brassard and Yung (Crypto 1990), and more recently Alamati, De Feo, Montgomery and Patranabis (Asiacrypt...
Moving a Step of ChaCha in Syncopated Rhythm
Shichang Wang, Meicheng Liu, Shiqi Hou, Dongdai Lin
Attacks and cryptanalysis
The stream cipher ChaCha is one of the most widely used ciphers in the real world, such as in TLS, SSH and so on. In this paper, we study the security of ChaCha via differential cryptanalysis based on probabilistic neutrality bits (PNBs). We introduce the \textit{syncopation} technique for the PNB-based approximation in the backward direction, which significantly amplifies its correlation by utilizing the property of ARX structure. In virtue of this technique, we present a new and efficient...
Foundations of Data Availability Sampling
Mathias Hall-Andersen, Mark Simkin, Benedikt Wagner
Foundations
Towards building more scalable blockchains, an approach known as data availability sampling (DAS) has emerged over the past few years.
Even large blockchains like Ethereum are planning to eventually deploy DAS to improve their scalability.
In a nutshell, DAS allows the participants of a network to ensure the full availability of some data without any one participant downloading it entirely.
Despite the significant practical interest that DAS has received, there are currently no formal...
Unlinkable Policy-Compliant Signatures for Compliant and Decentralized Anonymous Payments
Christian Badertscher, Mahdi Sedaghat, Hendrik Waldner
Cryptographic protocols
Privacy-preserving payment systems face the difficult task of balancing privacy and accountability: on one hand, users should be able to transact privately and anonymously, on the other hand, no illegal activities should be tolerated. The challenging question of finding the right balance lies at the core of the research on accountable privacy that stipulates the use of cryptographic techniques for policy enforcement. Current state-of-the-art systems are only able to enforce rather limited...
Auditable Attribute-Based Credentials Scheme and Its Application in Contact Tracing
Pengfei Wang, Xiangyu Su, Mario Larangeira, Keisuke Tanaka
Public-key cryptography
During the pandemic, the limited functionality of existing privacy-preserving contact tracing systems highlights the need for new designs. Wang et al. proposed an environmental-adaptive framework (CSS '21) but failed to formalize the security. The similarity between their framework and attribute-based credentials (ABC) inspires us to reconsider contact tracing from the perspective of ABC schemes. In such schemes, users can obtain credentials on attributes from issuers and prove the...
Transaction Fairness in Blockchains, Revisited
Rujia Li, Xuanwei Hu, Qin Wang, Sisi Duan, Qi Wang
Applications
With the growing number of decentralized finance (DeFi) applications, transaction fairness in blockchains has gained much research interest. As a broad concept in distributed systems and blockchains, fairness has been used in different contexts, varying from ones related to the liveness of the system to ones that focus on the received order of transactions. In this work, we revisit the fairness definitions and find that existing fairness definitions are not adapted to blockchains with...
Aggregate Signatures with Versatile Randomization and Issuer-Hiding Multi-Authority Anonymous Credentials
Omid Mir, Balthazar Bauer, Scott Griffy, Anna Lysyanskaya, Daniel Slamanig
Cryptographic protocols
Anonymous credentials (AC) have emerged as a promising privacy-preserving solu- tion for user-centric identity management. They allow users to authenticate in an anonymous and unlinkable way such that only required information (i.e., attributes) from their credentials are re- vealed. With the increasing push towards decentralized systems and identity, e.g., self-sovereign identity (SSI) and the concept of verifiable credentials, this also necessitates the need for suit- able AC systems. For...
SoK: Data Sovereignty
Jens Ernstberger, Jan Lauinger, Fatima Elsheimy, Liyi Zhou, Sebastian Steinhorst, Ran Canetti, Andrew Miller, Arthur Gervais, Dawn Song
Applications
Society appears to be on the verge of recognizing the need for control over sensitive data in modern web applications. Recently, many systems claim to give control to individuals, promising the preeminent goal of data sovereignty. However, despite recent attention, research and industry efforts are fragmented and lack a holistic system overview. In this paper, we provide the first transecting systematization of data sovereignty by drawing from a dispersed body of knowledge. We clarify the...
Compact Circuits for Efficient Mobius Transform
Subhadeep Banik, Francesco Regazzoni
Implementation
The Mobius transform is a linear circuit used to compute the evaluations of a Boolean function over all points on its input domain. The operation is very useful in finding the solution of a system of polynomial equations over GF(2) for obvious reasons. However the operation, although linear, needs exponential number of logic operations (around $n\cdot 2^{n-1}$ bit xors) for an $n$-variable Boolean function. As such, the only known hardware circuit to efficiently compute the Mobius transform...
CryptAttackTester: high-assurance attack analysis
Daniel J. Bernstein, Tung Chou
Attacks and cryptanalysis
Quantitative analyses of the costs of cryptographic attack algorithms play a central role in comparing cryptosystems, guiding the search for improved attacks, and deciding which cryptosystems to standardize. Unfortunately, these analyses often turn out to be wrong. Sometimes errors are not caught until years later.
This paper introduces CryptAttackTester (CAT), a software framework for high-assurance quantification of attack effectiveness. CAT enforces complete definitions of attack...
What If Alice Wants Her Story Told?
Anindya Bhandari, Allison Bishop
Foundations
In this paper, we pose the problem of defining technical privacy guarantees for anonymizing stories. This is a challenge that arises in practice in contexts like journalism and memoir writing, and can be crucial in determining whether a story gets told and how effectively it is presented. While recent decades have seen leaps and bounds in the development of approaches like differential privacy for numerical and categorical data sets, none of these techniques are directly applicable to...
Public-Key Encryption with Quantum Keys
Khashayar Barooti, Alex B. Grilo, Loïs Huguenin-Dumittan, Giulio Malavolta, Or Sattath, Quoc-Huy Vu, Michael Walter
Foundations
In the framework of Impagliazzo's five worlds, a distinction is often made between two worlds, one where public-key encryption exists (Cryptomania), and one in which only one-way functions exist (MiniCrypt). However, the boundaries between these worlds can change when quantum information is taken into account. Recent work has shown that quantum variants of oblivious transfer and multi-party computation, both primitives that are classically in Cryptomania, can be constructed from one-way...
Security-Preserving Distributed Samplers: How to Generate any CRS in One Round without Random Oracles
Damiano Abram, Brent Waters, Mark Zhandry
Cryptographic protocols
A distributed sampler is a way for several mutually distrusting parties to non-interactively generate a common reference string (CRS) that all parties trust. Previous work constructs distributed samplers in the random oracle model, or in the standard model with very limited security guarantees. This is no accident, as standard model distributed samplers with full security were shown impossible.
In this work, we provide new definitions for distributed samplers which we show achieve...
Unifying Freedom and Separation for Tight Probing-Secure Composition
Sonia Belaïd, Gaëtan Cassiers, Matthieu Rivain, Abdul Rahman Taleb
The masking countermeasure is often analyzed in the probing model. Proving the probing security of large circuits at high masking orders is achieved by composing gadgets that satisfy security definitions such as non-interference (NI), strong non-interference (SNI) or free SNI. The region probing model is a variant of the probing model, where the probing capabilities of the adversary scale with the number of regions in a masked circuit. This model is of interest as it allows better reductions...
How to Use (Plain) Witness Encryption: Registered ABE, Flexible Broadcast, and More
Cody Freitag, Brent Waters, David J. Wu
Cryptographic protocols
Witness encryption is a generalization of public-key encryption where the public key can be any NP statement x and the associated decryption key is any witness w for x. While early constructions of witness encryption relied on multilinear maps and indistinguishability obfuscation (iO), recent works have provided direct constructions of witness encryption that are more efficient than iO (and also seem unlikely to yield iO). Motivated by this progress, we revisit the possibility of using...
Private Eyes: Zero-Leakage Iris Searchable Encryption
Julie Ha, Chloe Cachet, Luke Demarest, Sohaib Ahmad, Benjamin Fuller
Cryptographic protocols
This work introduces Private Eyes, the first zero-leakage biometric database. The leakage of the system is unavoidable: 1) the log of the dataset size and 2) the fact that a query occurred. Private Eyes is built from symmetric searchable encryption. Approximate proximity queries are used: given a noisy reading of a biometric, the goal is to retrieve all stored records that are close enough according to a distance metric.
This work introduces Private Eyes, the first zero-leakage biometric...
Applications of Timed-release Encryption with Implicit Authentication
Angelique Faye Loe, Liam Medley, Christian O'Connell, Elizabeth A. Quaglia
Applications
A whistleblower is a person who leaks sensitive information on a prominent individual or organisation engaging in an unlawful or immoral activity.
Whistleblowing has the potential to mitigate corruption and fraud by identifying the misuse of capital.
In extreme cases whistleblowing can also raise awareness about unethical practices to individuals by highlighting dangerous working conditions.
Obtaining and sharing the sensitive information associated with whistleblowing can carry great...
Two Party Fair Exchange
Alex Dalton, David Thomas, Peter Cheung
Cryptographic protocols
Fair Exchange (FE) protocols are a class of cryptographic
protocol in which two parties, X and Y , exchange some secret data, where the ability of each party to receive secret data is contingent on having sent secret data of their own. When exchanging secret data without the support of FE protocols, whoever sends their secret first makes themselves vulnerable to the possibility that the other participant will cheat and won’t send their secret in return. It is widely believed that FE...
Generic Construction of Broadcast Authenticated Encryption with Keyword Search
Keita Emura
Public-key cryptography
As a multi-receiver variant of public key authenticated encryption with keyword search (PAEKS), broadcast authenticated encryption with keyword search (BAEKS) was proposed by Liu et al. (ACISP 2021). BAEKS focuses on receiver anonymity, where no information about the receiver is leaked from ciphertexts, which is reminiscent of the anonymous broadcast encryption. Here, there are rooms for improving their security definitions, e.g., two challenge sets of receivers are selected before the setup...
How to achieve bidirectional zero-knowledge authentication?
Jin Li, Xingyu Li, Chang Chen, Guoyu Yang, Junyang Li, Qi Chen, Hongyang Yan
Cryptographic protocols
Due to the completeness, reliability and zero-knowledge nature, the zero-knowledge proof is widely used to designed various protocols, including zero-knowledge authentication protocols. However, the existing zero-knowledge proof scheme cannot realize bidirectional authentication. In this paper, we design a series of bidirectional zero-knowledge
protocols based on two new flavors of operations applicable to multiplicative cyclic group. The two notions are formally defined in this paper. We...
A Map of Witness Maps: New Definitions and Connections
Suvradip Chakraborty, Manoj Prabhakaran, Daniel Wichs
Public-key cryptography
A \emph{witness map} deterministically maps a witness $w$ of some NP statement $x$ into computationally sound proof that $x$ is true, with respect to a public common reference string (CRS). In other words, it is a deterministic, non-interactive, computationally sound proof system in the CRS model. A \emph{unique witness map} (UWM) ensures that for any fixed statement $x$, the witness map should output the same \emph{unique} proof for $x$, no matter what witness $w$ it is applied to. More...
Asymmetric Group Message Franking: Definitions & Constructions
Junzuo Lai, Gongxian Zeng, Zhengan Huang, Siu Ming Yiu, Xin Mu, Jian Weng
Public-key cryptography
As online group communication scenarios become more and more common these years, malicious or unpleasant messages are much easier to spread on the internet. Message franking is a crucial cryptographic mechanism designed for content moderation in online end-to-end messaging systems, allowing the receiver of a malicious message to report the message to the moderator. Unfortunately, the existing message franking schemes only consider 1-1 communication scenarios.
In this paper, we...
On Circuit Private, Multikey and Threshold Approximate Homomorphic Encryption
Kamil Kluczniak, Giacomo Santato
Public-key cryptography
Homomorphic encryption for approximate arithmetic allows one to encrypt discretized real/complex numbers and evaluate arithmetic circuits over them. The first scheme, called CKKS, was introduced by Cheon et al. (Asiacrypt 2017) and gained tremendous attention. The enthusiasm for CKKS-type encryption stems from its potential to be used in inference or multiparty computation tasks that do not require an exact output.
A desirable property for homomorphic encryption is circuit privacy,...
A Formal Treatment of Distributed Key Generation, and New Constructions
Chelsea Komlo, Ian Goldberg, Douglas Stebila
Public-key cryptography
In this work, we present a novel generic construction for a Distributed Key Generation (DKG) scheme. Our generic construction relies on three modular cryptographic building blocks. The first is an aggregatable Verifiable Secret Sharing (AgVSS) scheme, the second is a Non-Interactive Key Exchange (NIKE) scheme, and the third is a secure hash function. We give formal definitions for the AgVSS and NIKE schemes, as well as concrete constructions. The utility of this generic construction is...
Simple Two-Round OT in the Explicit Isogeny Model
Emmanuela Orsini, Riccardo Zanotto
Public-key cryptography
In this work we apply the Type-Safe (TS) generic group model, recently introduced by Zhandry (2022), to the more general setting of group actions and extend it to the universal composability (UC) framework of Canetti (2000). We then relax this resulting model, that we call UC-TS, to define an algebraic action framework (UC-AA), where the adversaries can behave algebraically, similarly to the algebraic group model (AGM), but for group actions. Finally, we instantiate UC-AA with isogeny-based...
Public Key Encryption with Secure Key Leasing
Shweta Agrawal, Fuyuki Kitagawa, Ryo Nishimaki, Shota Yamada, Takashi Yamakawa
Public-key cryptography
We introduce the notion of public key encryption with secure key leasing (PKE-SKL). Our notion supports the leasing of decryption keys so that a leased key achieves the decryption functionality but comes with the guarantee that if the quantum decryption key returned by a user passes a validity test, then the user has lost the ability to decrypt. Our notion is similar in spirit to the notion of secure software leasing (SSL) introduced by Ananth and La Placa (Eurocrypt 2021) but captures...
The propagation game: on simulatability, correlation matrices, and probing security
Vittorio Zaccaria
Attacks and cryptanalysis
This work is intended for researchers in the field of side-channel attacks, countermeasure analysis, and probing security.
It reports on a formalization of simulatability in terms of linear algebra properties, which we think will provide a useful tool in the practitioner toolbox. The formalization allowed us to revisit some existing definitions (such as probe isolating non-interference) in a simpler way that corresponds to the propagation of erase morphisms. From a theoretical perspective,...
One-out-of-Many Unclonable Cryptography: Definitions, Constructions, and More
Fuyuki Kitagawa, Ryo Nishimaki
Foundations
The no-cloning principle of quantum mechanics enables us to achieve amazing unclonable cryptographic primitives, which is impossible in classical cryptography. However, the security definitions for unclonable cryptography are tricky. Achieving desirable security notions for unclonability is a challenging task. In particular, there is no indistinguishable-secure unclonable encryption and quantum copy-protection for single-bit output point functions in the standard model. To tackle this...
Classical and Quantum Security of Elliptic Curve VRF, via Relative Indifferentiability
Chris Peikert, Jiayu Xu
Public-key cryptography
Verifiable random functions (VRFs) are essentially pseudorandom
functions for which selected outputs can be proved correct and unique,
without compromising the security of other outputs. VRFs have numerous
applications across cryptography, and in particular they have recently
been used to implement committee selection in the Algorand protocol.
Elliptic Curve VRF (ECVRF) is an elegant construction,
originally due to Papadopoulos et al., that is now under consideration
by the Internet...
Asymmetric Trapdoor Pseudorandom Generators: Definitions, Constructions, and Applications to Homomorphic Signatures with Shorter Public Keys
Jinpeng Hou, Yansong Gao, Anmin Fu, Jie Chen, Xiaofeng Chen, Yuqing Zhang, Willy Susilo, Josef Pieprzyk
Public-key cryptography
We introduce a new primitive called the asymmetric trapdoor pseudorandom generator (ATPRG), which belongs to pseudorandom generators with two additional trapdoors (a public trapdoor and a secret trapdoor) or backdoor pseudorandom generators with an additional trapdoor (a secret trapdoor). Specifically, ATPRG can only generate public pseudorandom numbers $pr_1,\dots,pr_N$ for the users having no knowledge of the public trapdoor and the secret trapdoor; so this function is the same as...
A Practical Compiler for Attribute-Based Encryption: New Decentralized Constructions and More
Marloes Venema
Public-key cryptography
The pair encodings framework is an important result in the simplified design of complex attribute-based encryption schemes. In particular, it reduces the effort of proving security of a scheme to proving security of the associated pair encoding, which can then be transformed into a provably secure pairing-based encryption scheme with a compiler. Especially the symbolic property, as introduced by Agrawal and Chase (EUROCRYPT '17), has proven to be a valuable security notion that is both...
Towards Secure Evaluation of Online Functionalities (Corrected and Extended Version)
Andreas Klinger, Ulrike Meyer
Foundations
To date, ideal functionalities securely realized with secure multi-party computation (SMPC) mainly considers functions of the private inputs of a fixed number of a priori known parties. In this paper, we generalize these definitions such that protocols implementing online algorithms in a distributed fashion can be proven to be privacy-preserving. Online algorithms compute online functionalities that allow parties to arrive and leave over time, to provide multiple inputs and to obtain...
Expert Mental Models of SSI Systems and Implications for End-User Understanding
Alexandra Mai
Applications
Self-sovereign identity (SSI) systems have gained increasing attention over the last five years. In a variety of fields (e.g., education, IT security, law, government), developers and researchers are attempting to give end-users back their right to and control of their data. Although prototypes and theoretical concepts for SSI applications exist, the majority of them are still in their infancy. Due to missing definitions and standards, there is currently a lack of common understanding of SSI...
Private Access Control for Function Secret Sharing
Sacha Servan-Schreiber, Simon Beyzerov, Eli Yablon, Hyojae Park
Cryptographic protocols
Function Secret Sharing (FSS; Eurocrypt 2015) allows a dealer to share a function f with two or more evaluators. Given secret shares of a function f, the evaluators can locally compute secret shares of f(x) on an input x, without learning information about f.
In this paper, we initiate the study of access control for FSS. Given the shares of f, the evaluators can ensure that the dealer is authorized to share the provided function. For a function family F and an access control list defined...
Stronger Security and Generic Constructions for Adaptor Signatures
Wei Dai, Tatsuaki Okamoto, Go Yamamoto
Foundations
Adaptor signatures have seen wide applications in layer-2 and peer-to-peer blockchain ap- plications such as atomic swaps and payment channels. We first identify two shortcomings of previous literature on adaptor signatures. (1) Current aim of “script-less” adaptor signatures restricts instantiability, limiting designs based on BLS or current NIST PQC candidates. (2) We identify gaps in current formulations of security. In particular, we show that current notions do not rule out a class of...
Authenticated Encryption with Key Identification
Julia Len, Paul Grubbs, Thomas Ristenpart
Secret-key cryptography
Authenticated encryption with associated data (AEAD) forms the core of much of symmetric cryptography, yet the standard techniques for modeling AEAD assume recipients have no ambiguity about what secret key to use for decryption. This is divorced from what occurs in practice, such as in key management services, where a message recipient can store numerous keys and must identify the correct key before decrypting. To date there has been no formal investigation of their security properties or...
Proactive Refresh for Accountable Threshold Signatures
Dan Boneh, Aditi Partap, Lior Rotem
Cryptographic protocols
An accountable threshold signature (ATS) is a threshold signature scheme where every signature identifies the quorum of signers who generated that signature. They are widely used in financial settings where signers need to be held accountable for threshold signatures they generate. In this paper we initiate the study of proactive refresh for accountable threshold signatures. Proactive refresh is a protocol that lets the group of signers refresh their shares of the secret key, without...
Anonymous Tokens with Hidden Metadata Bit from Algebraic MACs
Melissa Chase, F. Betül Durak, Serge Vaudenay
Cryptographic protocols
On the one hand, the web needs to be secured from malicious activities such as bots or DoS attacks; on the other hand, such needs ideally should not justify services tracking people's activities on the web. Anonymous tokens provide a nice tradeoff between allowing an issuer to ensure that a user has been vetted and protecting the users' privacy. However, in some cases, whether or not a token is issued reveals a lot of information to an adversary about the strategies used to distinguish...
Sweep-UC: Swapping Coins Privately
Lucjan Hanzlik, Julian Loss, Sri AravindaKrishnan Thyagarajan, Benedikt Wagner
Cryptographic protocols
Fair exchange (also referred to as atomic swap) is a fundamental operation in any cryptocurrency that allows users to atomically exchange coins.
While a large body of work has been devoted to this problem, most solutions lack on-chain privacy. Thus, coins retain a public transaction history which is known to degrade the fungibility of a currency. This has led to a flourishing line of related research on fair exchange with privacy guarantees. Existing protocols either rely on heavy scripting...
Extendable Threshold Ring Signatures with Enhanced Anonymity
Gennaro Avitabile, Vincenzo Botta, Dario Fiore
Cryptographic protocols
Threshold ring signatures are digital signatures that allow $t$ parties to sign a message while hiding their identity in a larger set of $n$ users called ''ring''.
Recently, Aranha et al. [PKC 2022] introduced the notion of \emph{extendable} threshold ring signatures (ETRS).
ETRS allow one to update, in a non-interactive manner, a threshold ring signature on a certain message so that the updated signature has a greater threshold, and/or an augmented set of potential signers.
An...
A Systematization of Voter Registration Security
Jack Cable, Andrés Fábrega, Sunoo Park, Michael A. Specter
Foundations
Voter registration is an essential part of almost any election process, and its security is a critical component of election security. Yet, despite notable compromises of voter registration systems, relatively little academic work has been devoted to securing voter registration systems, compared to research on other aspects of election security. In this paper, we present a systematic treatment of voter registration system security. We propose the first rigorous definitional framework for...
Exploiting algebraic structures in probing security
Maxime Plançon
Implementation
The so-called $\omega$-encoding, introduced by Goudarzi, Joux and Rivain (Asiacrypt 2018), generalizes the commonly used arithmetic encoding. By using the additionnal structure of this encoding, they proposed a masked multiplication gadget (GJR) with quasilinear (randomness and operations) complexity. A follow-up contribution by Goudarzi, Prest, Rivain and Vergnaud in this line of research appeared in TCHES 2021. The authors revisited the aforementioned multiplication gadget (GPRV), and...
The Key Lattice Framework for Concurrent Group Messaging
Kelong Cong, Karim Eldefrawy, Nigel P. Smart, Ben Terner
Cryptographic protocols
Today, two-party secure messaging is well-understood and widely adopted on the Internet, e.g., Signal and WhatsApp. Multiparty protocols for secure group messaging on the other hand are less mature and many protocols with different tradeoffs exist. Generally, such protocols require parties to first agree on a shared secret group key and then periodically update it while preserving forward secrecy (FS) and post compromise security (PCS).
We present a new framework, called a key lattice,...
Pseudorandom (Function-Like) Quantum State Generators: New Definitions and Applications
Prabhanjan Ananth, Aditya Gulati, Luowen Qian, Henry Yuen
Foundations
Pseudorandom quantum states (PRS) are efficiently constructible states that are computationally indistinguishable from being Haar-random, and have recently found cryptographic applications. We explore new definitions, new properties and applications of pseudorandom states, and present the following contributions:
1. New Definitions: We study variants of pseudorandom function-like state (PRFS) generators, introduced by Ananth, Qian, and Yuen (CRYPTO'22), where the pseudorandomness property...
ParaDiSE: Efficient Threshold Authenticated Encryption in Fully Malicious Model
Shashank Agrawal, Wei Dai, Atul Luykx, Pratyay Mukherjee, Peter Rindal
Cryptographic protocols
Threshold cryptographic algorithms achieve robustness against key and access compromise by distributing secret keys among multiple entities. Most prior work focuses on threshold public-key primitives, despite extensive use of authenticated encryption in practice. Though the latter can be deployed in a threshold manner using multi-party computation (MPC), doing so incurs a high communication cost. In contrast, dedicated constructions of threshold authenticated encryption algorithms can...
Cryptographic Administration for Secure Group Messaging
David Balbás, Daniel Collins, Serge Vaudenay
Cryptographic protocols
Many real-world group messaging systems delegate group administration to the application level, failing to provide formal guarantees related to group membership. Taking a cryptographic approach to group administration can prevent both implementation and protocol design pitfalls that result in a loss of confidentiality and consistency for group members.
In this work, we introduce a cryptographic framework for the design of group messaging protocols that offer strong security guarantees for...
Bet-or-Pass: Adversarially Robust Bloom Filters
Moni Naor, Noa Oved
Foundations
A Bloom filter is a data structure that maintains a succinct and probabilistic representation of a set $S\subseteq U$ of elements from a universe $U$. It supports approximate membership queries. The price of the succinctness is allowing some error, namely false positives: for any $x\notin S$, it might answer `Yes' but with a small (non-negligible) probability.
When dealing with such data structures in adversarial settings, we need to define the correctness guarantee and formalize the...
DiAE: Re-rolling the DiSE
Alexandre Duc, Robin Müller, Damian Vizár
Secret-key cryptography
The notion of distributed authenticated encryption was formally introduced by Agrawal et al. in ACM CCS 2018. In their work, they propose the DiSE construction building upon a distributed PRF (DPRF), a commitment scheme and a PRG. We show that most of their constructions do not meet some of the claimed security guarantees. In fact, all the concrete instantiations of DiSE, as well as multiple follow-up papers (one accepted at ACM CCS 2021), fail to satisfy their strongly-secure definitions....
Cryptographic Role-Based Access Control, Reconsidered
Bin Liu, Antonis Michalas, Bogdan Warinschi
Cryptographic protocols
A significant shortcoming of traditional access control mechanisms is their heavy reliance on reference monitors. Being single points of failure, monitors need to run in protected mode and have permanent online presence in order to handle all access requests. Cryptographic access control offers an alternative solution that provides better scalability and deployability. It relies on security guarantees of the underlying cryptographic primitives and the appropriate key distribution/management...
On Committing Authenticated Encryption
John Chan, Phillip Rogaway
Secret-key cryptography
We provide a strong definition for committing authenticated-encryption (cAE), as well as a framework that encompasses earlier and weaker definitions. The framework attends not only to what is committed but also the extent to which the adversary knows or controls keys. We slot into our framework strengthened cAE-attacks on GCM and OCB. Our main result is a simple and efficient construction, CTX, that makes a nonce-based AE (nAE) scheme committing. The transformed scheme achieves the...
A Modular Approach to the Incompressibility of Block-Cipher-Based AEADs
Akinori Hosoyamada, Takanori Isobe, Yosuke Todo, Kan Yasuda
Secret-key cryptography
Incompressibility is one of the most fundamental security goals in white-box cryptography.
Given recent advances in the design of efficient and incompressible block ciphers such as SPACE, SPNbox and WhiteBlock,
we demonstrate the feasibility of reducing incompressible AEAD modes to incompressible block ciphers.
We first observe that several existing AEAD modes of operation, including CCM, GCM(-SIV), and OCB, would be all insecure against white-box adversaries even when used with an...
Functional Encryption with Secure Key Leasing
Fuyuki Kitagawa, Ryo Nishimaki
Foundations
Secure software leasing is a quantum cryptographic primitive that enables us to lease software to a user by encoding it into a quantum state. Secure software leasing has a mechanism that verifies whether a returned software is valid or not. The security notion guarantees that once a user returns a software in a valid form, the user no longer uses the software.
In this work, we introduce the notion of secret-key functional encryption (SKFE) with secure key leasing, where a decryption key...
Puncturable Key Wrapping and Its Applications
Matilda Backendal, Felix Günther, Kenneth G. Paterson
Secret-key cryptography
We introduce puncturable key wrapping (PKW), a new cryptographic primitive that supports fine-grained forward security properties in symmetric key hierarchies. We develop syntax and security definitions, along with provably secure constructions for PKW from simpler components (AEAD schemes and puncturable PRFs). We show how PKW can be applied in two distinct scenarios. First, we show how to use PKW to achieve forward security for TLS 1.3 0-RTT session resumption, even when the server's...
Strongly Anonymous Ratcheted Key Exchange
Benjamin Dowling, Eduard Hauck, Doreen Riepel, Paul Rösler
Cryptographic protocols
Anonymity is an (abstract) security goal that is especially important to threatened user groups. Therefore, widely deployed communication protocols implement various measures to hide different types of information (i.e., metadata) about their users. Before actually defining anonymity, we consider an attack vector about which targeted user groups can feel concerned: continuous, temporary exposure of their secrets. Examples for this attack vector include intentionally planted viruses on...
Adversarial Correctness and Privacy for Probabilistic Data Structures
Mia Filić, Kenneth G. Paterson, Anupama Unnikrishnan, Fernando Virdia
Applications
We study the security of Probabilistic Data Structures (PDS) for
handling Approximate Membership Queries (AMQ); prominent
examples of AMQ-PDS are Bloom and Cuckoo filters. AMQ-PDS
are increasingly being deployed in environments where adversaries
can gain benefit from carefully selecting inputs, for example to
increase the false positive rate of an AMQ-PDS. They are also being
used in settings where the inputs are sensitive and should remain
private in the face of adversaries who can...
Machine-Checked Proofs of Privacy Against Malicious Boards for Selene & Co
Constantin Cătălin Drăgan, François Dupressoir, Ehsan Estaji, Kristian Gjøsteen, Thomas Haines, Peter Y. A. Ryan, Peter B. Rønne, Morten Rotvold Solberg
Cryptographic protocols
Privacy is a notoriously difficult property to achieve in complicated systems and especially in electronic voting schemes. Moreover, electronic voting schemes is a class of systems that require very high assurance. The literature contains a number of ballot privacy definitions along with security proofs for common systems. Some machine-checked security proofs have also appeared. We define a new ballot privacy notion that captures a larger class of voting schemes. This notion improves on the...
Time-lock puzzles are unique cryptographic primitives that use computational complexity to keep information secret for some period of time, after which security expires. Unfortunately, current analysis techniques of time-lock primitives provide no sound mechanism to build multi-party cryptographic protocols which use expiring security as a building block. We explain in this paper that all other attempts at this subtle problem lack either composability, a fully consistent analysis, or...
Cryptographic accumulators, introduced in 1993 by Benaloh and De Mare, represent a set with a concise value and offer proofs of (non-)membership. Accumulators have evolved, becoming essential in anonymous credentials, e-cash, and blockchain applications. Various properties like dynamic and universal emerged for specific needs, leading to multiple accumulator definitions. In 2015, Derler, Hanser, and Slamanig proposed a unified model, but new properties, including zero-knowledge security,...
Vector commitments gain a lot of attention because of their wide usage in applications such as blockchain and accumulator. Mercurial vector commitments and mercurial functional commitments (MFC), as significant variants of VC, are the central techniques to construct more advanced cryptographic primitives such as zero-knowledge set and zero-knowledge functional elementary database (ZK-FEDB). However, the current MFC only supports linear functions, limiting its application, i.e. building the...
The revelations of Edward Snowden in 2013 rekindled concerns within the cryptographic community regarding the potential subversion of cryptographic systems. Bellare et al. (CRYPTO'14) introduced the notion of Algorithm Substitution Attacks (ASAs), which aim to covertly leak sensitive information by undermining individual cryptographic primitives. In this work, we delve deeply into the realm of ASAs against protocols built upon cryptographic primitives. In particular, we revisit the existing...
We study the possibility of schemes whose public parameters have been generated along with a backdoor. We consider the goal of the big-brother adversary to be two-fold: It desires utility (it can break the scheme) but also exclusivity (nobody else can). Starting with hash functions, we give new, strong definitions for these two goals, calling the combination high effectiveness. We then present a construction of a backdoored hash function that is highly effective, meaning provably meets our...
Biometric authentication eliminates the need for users to remember secrets and serves as a convenient mechanism for user authentication. Traditional implementations of biometric-based authentication store sensitive user biometry on the server and the server becomes an attractive target of attack and a source of large-scale unintended disclosure of biometric data. To mitigate the problem, we can resort to privacy-preserving computation and store only protected biometrics on the server. While...
Policy-compliant signatures (PCS) are a recently introduced primitive by Badertscher et al. [TCC 2021] in which a central authority distributes secret and public keys associated with sets of attributes (e.g., nationality, affiliation with a specific department, or age) to its users. The authority also enforces a policy determining which senders can sign messages for which receivers based on a joint check of their attributes. For example, senders and receivers must have the same nationality,...
The elegant paradigm of Anamorphic Encryption (Persiano et al., Eurocrypt 2022) considers the question of establishing a private communication in a world controlled by a dictator. The challenge is to allow two users, sharing some secret anamorphic key, to exchange covert messages without the dictator noticing, even when the latter has full access to the regular secret keys. Over the last year several works considered this question and proposed constructions, novel extensions and...
Suppose Alice uses a $t$-out-of-$n$ secret sharing to store her secret key on $n$ servers. Her secret key is protected as long as $t$ of them do not collude. However, what if a less-than-$t$ subset of the servers decides to offer the shares they have for sale? In this case, Alice should be able to hold them accountable, or else nothing prevents them from selling her shares. With this motivation in mind, Goyal, Song, and Srinivasan (CRYPTO 21) introduced the concept of {\em traceable secret...
Several Password Authenticated Key Exchange (PAKE) protocols have been recently proposed that leverage a Key-Encapsulation Mechanism (KEM) to create an efficient and easy-to-implement post-quantum secure PAKE. This line of work is driven by the intention of the National Institute of Standards and Technology (NIST) to soon standardize a lattice-based post-quantum KEM called $\mathsf{Kyber}$. In two recent works, Beguinet et al. (ACNS 2023) and Pan and Zeng (ASIACRYPT 2023) proposed generic...
Decoy accounts are often used as an indicator of the compromise of sensitive data, such as password files. An attacker targeting only specific known-to-be-real accounts might, however, remain undetected. A more effective method proposed by Juels and Rivest at CCS'13 is to maintain additional fake passwords associated with each account. An attacker who gains access to the password file is unable to tell apart real passwords from fake passwords, and the attempted usage of a false password...
As blockchains like Ethereum continue to grow, clients with limited resources can no longer store the entire chain. Light nodes that want to use the blockchain, without verifying that it is in a good state overall, can just download the block headers without the corresponding block contents. As those light nodes may eventually need some of the block contents, they would like to ensure that they are in principle available. Data availability sampling, introduced by Bassam et al., is a...
Fully Homomorphic Encryption (FHE) is a powerful tool for performing privacy-preserving analytics over encrypted data. A promising method for FHE over real and complex numbers is approximate homomorphic encryption, instantiated with the Cheon-Kim-Kim-Song (CKKS) scheme. The CKKS scheme enables efficient evaluation for many privacy-preserving machine learning applications. Despite its high efficiency, there is currently a lot of confusion on how to securely instantiate CKKS for a given...
We focus on the problem of constructing fully homomorphic encryption (FHE) schemes that achieve some meaningful notion of adaptive chosen-ciphertext security beyond CCA1. Towards this, we propose a new notion, called security against verified chosen-ciphertext attack (vCCA). The idea behind it is to ascertain integrity of the ciphertext by imposing a strong control on the evaluation algorithm. Essentially, we require that a ciphertext obtained by the use of homomorphic evaluation must be...
In today's systems, privacy is often at odds with utility: users that reveal little information about themselves get restricted functionality, and service providers mistrust them. In practice, systems tip to either full anonymity (e.g. Monero), or full utility (e.g. Bitcoin). Well-known cryptographic primitives for bridging this gap exist: anonymous credentials (AC) let users disclose a subset of their credentials' attributes, revealing to service providers "just what they need"; group...
We explore the issue of anonymously proving account ownership (anonymous PAO). Such proofs allow a prover to prove to a verifier that it owns a valid account at a server without being tracked by the server or the verifier, without requiring any changes at the server's end and without even revealing to it that any anonymous PAO is taking place. This concept is useful in sensitive applications like whistleblowing. The first introduction of anonymous PAOs was by Wang et al., who also introduced...
In this work we revisit the problem of using general-purpose MPC schemes to emulate the trusted dataholder in central differential privacy, to achieve same accuracy but without the need to trust one single dataholder. In particular, we consider the two-party model of having two computational parties (or dataholders) each with their own dataset wishing to compute a canonical differentially private mechanism on their combined data and to do so with active security. We start by remarking that...
Considerable work explores blockchain privacy notions. Yet, it usually employs entirely different models and notations, complicating potential comparisons. In this work, we use the Transaction Directed Acyclic Graph (TDAG) and extend it to capture blockchain privacy notions (PDAG). We give consistent definitions for untraceability and unlinkability. Moreover, we specify conditions on a blockchain system to achieve each aforementioned privacy notion. Thus, we can compare the two most...
The privacy pass protocol allows users to redeem anonymously issued cryptographic tokens instead of solving annoying CAPTCHAs. The issuing authority verifies the credibility of the user, who can later use the pass while browsing the web using an anonymous or virtual private network. Hendrickson et al. proposed an IETF draft (privacypass-rate-limit-tokens-00) for a rate-limiting version of the privacy pass protocol, also called rate-limited Privacy Pass (RlP). Introducing a new actor called a...
The Snowden's revelations kick-started a community-wide effort to develop cryptographic tools against mass surveillance. In this work, we propose to add another primitive to that toolbox: Fail-Stop Signatures (FSS) [EC'89]. FSS are digital signatures enhanced with a forgery-detection mechanism that can protect a PPT signer from more powerful attackers. Despite the fascinating concept, research in this area stalled after the '90s. However, the ongoing transition to post-quantum...
QCB is a proposal for a post-quantum secure, rate-one authenticated encryption with associated data scheme (AEAD) based on classical OCB3 and \(\Theta\)CB, which are vulnerable against a quantum adversary in the Q2 setting. The authors of QCB prove integrity under plus-one unforgeability, whereas the proof of the stronger definition of blind unforgeability has been left as an open problem. After a short overview of QCB and the current state of security definitions for authentication, this...
Symmetric Private Information Retrieval (SPIR) is a protocol that protects privacy during data transmission. However, the existing SPIR focuses only on the privacy of the data to be requested on the server, without considering practical factors such as the payload that may be present during data transmission. This could seriously prevent SPIR from being applied to many complex data scenarios and hinder its further expansion. To solve such problems, we propose a primitive (PSKPIR) for...
The BUFF transform is a generic transformation for digital signature schemes, with the purpose of obtaining additional security properties beyond standard unforgeability, e.g., exclusive ownership and non-resignability. In the call for additional post-quantum signatures, these were explicitly mentioned by the NIST as ``additional desirable security properties'', and some of the submissions indeed refer to the BUFF transform with the purpose of achieving them, while some other submissions...
In secure multiparty computation (MPC), the goal is to allow a set of mutually distrustful parties to compute some function of their private inputs in a way that preserves security properties, even in the face of adversarial behavior by some of the parties. However, classical security definitions do not pose any privacy restrictions on the view of honest parties. Thus, if an attacker adversarially leaks private information to honest parties, it does not count as a violation of privacy. This...
Cryptographers rely on visualization to effectively communicate cryptographic constructions with one another. Visual frameworks such as constructive cryptography (TOSCA 2011), the joy of cryptography (online book) and state-separating proofs (SSPs, Asiacrypt 2018) are useful to communicate not only the construction, but also their proof visually by representing a cryptographic system as graphs. One SSP core feature is the re-use of code, e.g., a package of code might be used in a game...
Zero-Knowledge Virtual Machines (ZKVMs) have gained traction in recent years due to their potential applications in a variety of areas, particularly blockchain ecosystems. Despite tremendous progress on ZKVMs in the industry, no formal definitions or security proofs have been established in the literature. Due to this lack of formalization, existing protocols exhibit significant discrepancies in terms of problem definitions and performance metrics, making it difficult to analyze and compare...
Non-malleable cryptography, proposed by Dolev, Dwork, and Naor (SICOMP '00), has numerous applications in protocol composition. In the context of proofs, it guarantees that an adversary who receives a proof cannot maul it into another valid proof. However, non-malleable cryptography (particularly in the non-interactive setting) suffers from an important limitation: An attacker can always copy the proof and resubmit it to another verifier (or even multiple verifiers). In this work, we...
With the increasing scale and complexity of online activities, accountability, as an after-the-fact mechanism, has become an effective complementary approach to ensure system security. Decades of research have delved into the connotation of accountability. They fail, however, to achieve practical accountability of decryption. This paper seeks to address this gap. We consider the scenario where a client (called encryptor, her) encrypts her data and then chooses a delegate (a.k.a. decryptor,...
We give a semantic characterization of leakage-freeness through timing side-channels for Jasmin programs. Our characterization also covers probabilistic Jasmin programs that are not constant-time. In addition, we provide a characterization in terms of probabilistic relational Hoare logic and prove equivalence of both definitions. We also prove that our new characterizations are compositional. Finally, we relate new definitions to the existing ones from prior work which only apply to...
In remote state preparation with verifiability (RSPV), a client would like to prepare a quantum state (sampled from a state family) on the server side, such that ideally the client knows its full description, while the server holds and only holds the state itself. A closely related notion called self-testing, which is recently generalized to the single-server computationally-secure setting [MV21, aims at certifying the server's operation. These notions have been widely studied in various...
We introduce a new variant of malicious obfuscation. Our formalism is incomparable to the existing definitions by Canetti and Varia (TCC 2010), Canetti et al. (EUROCRYPT 2022) and Badrinarayanan et al. (ASIACRYPT 2016). We show that this concept is natural and applicable to obfuscation-as-a-service platforms. We next define a new notion called auditable obfuscation which provides security against malicious obfuscation. Finally, we construct a proof of concept of the developed notions based...
Identity-based matchmaking encryption (IB-ME) [Ateniese et al. Crypto 2019] allows users to communicate privately in an anonymous and authenticated manner. After the seminal paper by Ateniese et al., a lot of work has been done on the security and construction of IB-ME. In this work, we revisit the security definitions and construction of IB-ME and provide the following three contributions. -- First, we embark on the task of classifying the existing security notions of IB-ME. We...
In the context of circuits leaking the internal state, there are various models to analyze what the adversary can see, like the $p$-random probing model in which the adversary can see the value of each wire with probability $p$. In this model, for a fixed $p$, it's possible to reach an arbitrary security by 'expanding' a stateless circuit via iterated compilation, reaching a security of $2^{-\kappa}$ with a polynomial size in $\kappa$. The existing proofs of the expansion work by first...
This paper introduces Bicameral and Auditably Private Signatures (BAPS) -- a new privacy-preserving signature system with several novel features. In a BAPS system, given a certified attribute $\mathbf{x}$ and a certified policy $P$, a signer can issue a publicly verifiable signature $\Sigma$ on a message $m$ as long as $(m, \mathbf{x})$ satisfies $P$. A noteworthy characteristic of BAPS is that both attribute $\mathbf{x}$ and policy $P$ are kept hidden from the verifier, yet the latter is...
When modelling how public key encryption can enable secure communication, we should acknowledge that secret information, such as private keys or the randomness used for encryption, could become compromised. Intuitively, one would expect unrelated communication to remain secure, yet formalizing this intuition has proven challenging. Several security notions have appeared that aim to capture said scenario, ranging from the multi-user setting with corruptions, via selective opening attacks...
Proxy re-encryption (PRE) allows a proxy with a re-encryption key to translate a ciphertext intended for Alice (delegator) to another ciphertext intended for Bob (delegatee) without revealing the underlying message. However, with PRE, Bob can obtain the whole message from the re-encrypted ciphertext, and Alice cannot take flexible control of the extent of the message transmitted to Bob. In this paper, we propose a new variant of PRE, called Fine-Grained PRE (FPRE), to support...
This work formally analyzes the anonymity guarantees of continuous stop-and-go mixnets and attempts to answer the above question. Existing mixnet based anonymous communication protocols that aim to provide provable anonymity guarantees rely on round-based communication models --- which requires synchronization among all the nodes and clients, and difficult to achieve in practice. Continuous stop-and-go mixnets (e.g., Loopix and Nym) provide a nice alternative by adding a random delay for...
The theory of finite simple groups is a (rather unexplored) area likely to provide interesting computational problems and modelling tools useful in a cryptographic context. In this note, we review some applications of finite non-abelian simple groups to cryptography and discuss different scenarios in which this theory is clearly central, providing the relevant definitions to make the material accessible to both cryptographers and group theorists, in the hope of stimulating further...
The Fast IDentity Online (FIDO) Alliance develops open standards to replace password-based authentication by token-based so- lutions. The latest protocol suite FIDO2 provides a promising alterna- tive which many key players have already adopted or are planning to. The central authentication mechanism WebAuthn uses cryptographic keys stored on the device to authenticate clients to a relying party via a challenge-response protocol. Yet, this approach leaves several open issues about...
An important consideration in the context of distributed ledger protocols is fairness in terms of transaction ordering. Recent work [Crypto 2020] revealed a connection of (receiver) order fairness to social choice theory and related impossibility results arising from the Condorcet paradox. As a result of the impossibility, various relaxations of order fairness were proposed in prior works. Given that distributed ledger protocols, especially those processing smart contracts, must serialize...
From the work by Laguillaumie and Vergnaud in ICICS'04, it has been widely believed that multi-designated verifier signature schemes (MDVS) can be constructed from ring signature schemes in general. However in this paper, somewhat surprisingly, we prove that it is impossible to construct an MDVS scheme from a ring signature scheme in a black-box sense (in the standard model). The impossibility stems from the difference between the definitions of unforgeability. To the best of our...
A universal re-encryption (URE) scheme is a public-key encryption scheme enhanced with an algorithm that on input a ciphertext, outputs another ciphertext which is still a valid encryption of the underlying plaintext. Crucially, such a re-encryption algorithm does not need any key as input, but the ciphertext is guaranteed to be valid under the original key-pair. Therefore, URE schemes lend themselves naturally as building blocks of mixnets: A sender transmits the encryption of a message...
Private payments in blockchain-based cryptocurrencies have been a topic of research, both academic and industrial, ever since the advent of Bitcoin. Stealth address payments were proposed as a solution to improve payment privacy for users and are, in fact, deployed in several major cryptocurrencies today. The mechanism lets users receive payments so that none of these payments are linkable to each other or the recipient. Currently known stealth address mechanisms either (1) are insecure in...
An interesting approach to achieving verifiability in voting systems is to make use of tracking numbers. This gives voters a simple way of verifying that their ballot was counted: they can simply look up their ballot/tracker pair on a public bulletin board. It is crucial to understand how trackers affect other security properties, in particular privacy. However, existing privacy definitions are not designed to accommodate tracker-based voting systems. Furthermore, the addition of trackers...
In recent years, the Lattice Isomorphism Problem (LIP) has served as an underlying assumption to construct quantum-resistant cryptographic primitives, e.g. the zero-knowledge proof and digital signature scheme by Ducas and van Woerden (Eurocrypt 2022), and the HAWK digital signature scheme (Asiacrypt 2022). While prior lines of work in group action cryptography, e.g. the works of Brassard and Yung (Crypto 1990), and more recently Alamati, De Feo, Montgomery and Patranabis (Asiacrypt...
The stream cipher ChaCha is one of the most widely used ciphers in the real world, such as in TLS, SSH and so on. In this paper, we study the security of ChaCha via differential cryptanalysis based on probabilistic neutrality bits (PNBs). We introduce the \textit{syncopation} technique for the PNB-based approximation in the backward direction, which significantly amplifies its correlation by utilizing the property of ARX structure. In virtue of this technique, we present a new and efficient...
Towards building more scalable blockchains, an approach known as data availability sampling (DAS) has emerged over the past few years. Even large blockchains like Ethereum are planning to eventually deploy DAS to improve their scalability. In a nutshell, DAS allows the participants of a network to ensure the full availability of some data without any one participant downloading it entirely. Despite the significant practical interest that DAS has received, there are currently no formal...
Privacy-preserving payment systems face the difficult task of balancing privacy and accountability: on one hand, users should be able to transact privately and anonymously, on the other hand, no illegal activities should be tolerated. The challenging question of finding the right balance lies at the core of the research on accountable privacy that stipulates the use of cryptographic techniques for policy enforcement. Current state-of-the-art systems are only able to enforce rather limited...
During the pandemic, the limited functionality of existing privacy-preserving contact tracing systems highlights the need for new designs. Wang et al. proposed an environmental-adaptive framework (CSS '21) but failed to formalize the security. The similarity between their framework and attribute-based credentials (ABC) inspires us to reconsider contact tracing from the perspective of ABC schemes. In such schemes, users can obtain credentials on attributes from issuers and prove the...
With the growing number of decentralized finance (DeFi) applications, transaction fairness in blockchains has gained much research interest. As a broad concept in distributed systems and blockchains, fairness has been used in different contexts, varying from ones related to the liveness of the system to ones that focus on the received order of transactions. In this work, we revisit the fairness definitions and find that existing fairness definitions are not adapted to blockchains with...
Anonymous credentials (AC) have emerged as a promising privacy-preserving solu- tion for user-centric identity management. They allow users to authenticate in an anonymous and unlinkable way such that only required information (i.e., attributes) from their credentials are re- vealed. With the increasing push towards decentralized systems and identity, e.g., self-sovereign identity (SSI) and the concept of verifiable credentials, this also necessitates the need for suit- able AC systems. For...
Society appears to be on the verge of recognizing the need for control over sensitive data in modern web applications. Recently, many systems claim to give control to individuals, promising the preeminent goal of data sovereignty. However, despite recent attention, research and industry efforts are fragmented and lack a holistic system overview. In this paper, we provide the first transecting systematization of data sovereignty by drawing from a dispersed body of knowledge. We clarify the...
The Mobius transform is a linear circuit used to compute the evaluations of a Boolean function over all points on its input domain. The operation is very useful in finding the solution of a system of polynomial equations over GF(2) for obvious reasons. However the operation, although linear, needs exponential number of logic operations (around $n\cdot 2^{n-1}$ bit xors) for an $n$-variable Boolean function. As such, the only known hardware circuit to efficiently compute the Mobius transform...
Quantitative analyses of the costs of cryptographic attack algorithms play a central role in comparing cryptosystems, guiding the search for improved attacks, and deciding which cryptosystems to standardize. Unfortunately, these analyses often turn out to be wrong. Sometimes errors are not caught until years later. This paper introduces CryptAttackTester (CAT), a software framework for high-assurance quantification of attack effectiveness. CAT enforces complete definitions of attack...
In this paper, we pose the problem of defining technical privacy guarantees for anonymizing stories. This is a challenge that arises in practice in contexts like journalism and memoir writing, and can be crucial in determining whether a story gets told and how effectively it is presented. While recent decades have seen leaps and bounds in the development of approaches like differential privacy for numerical and categorical data sets, none of these techniques are directly applicable to...
In the framework of Impagliazzo's five worlds, a distinction is often made between two worlds, one where public-key encryption exists (Cryptomania), and one in which only one-way functions exist (MiniCrypt). However, the boundaries between these worlds can change when quantum information is taken into account. Recent work has shown that quantum variants of oblivious transfer and multi-party computation, both primitives that are classically in Cryptomania, can be constructed from one-way...
A distributed sampler is a way for several mutually distrusting parties to non-interactively generate a common reference string (CRS) that all parties trust. Previous work constructs distributed samplers in the random oracle model, or in the standard model with very limited security guarantees. This is no accident, as standard model distributed samplers with full security were shown impossible. In this work, we provide new definitions for distributed samplers which we show achieve...
The masking countermeasure is often analyzed in the probing model. Proving the probing security of large circuits at high masking orders is achieved by composing gadgets that satisfy security definitions such as non-interference (NI), strong non-interference (SNI) or free SNI. The region probing model is a variant of the probing model, where the probing capabilities of the adversary scale with the number of regions in a masked circuit. This model is of interest as it allows better reductions...
Witness encryption is a generalization of public-key encryption where the public key can be any NP statement x and the associated decryption key is any witness w for x. While early constructions of witness encryption relied on multilinear maps and indistinguishability obfuscation (iO), recent works have provided direct constructions of witness encryption that are more efficient than iO (and also seem unlikely to yield iO). Motivated by this progress, we revisit the possibility of using...
This work introduces Private Eyes, the first zero-leakage biometric database. The leakage of the system is unavoidable: 1) the log of the dataset size and 2) the fact that a query occurred. Private Eyes is built from symmetric searchable encryption. Approximate proximity queries are used: given a noisy reading of a biometric, the goal is to retrieve all stored records that are close enough according to a distance metric. This work introduces Private Eyes, the first zero-leakage biometric...
A whistleblower is a person who leaks sensitive information on a prominent individual or organisation engaging in an unlawful or immoral activity. Whistleblowing has the potential to mitigate corruption and fraud by identifying the misuse of capital. In extreme cases whistleblowing can also raise awareness about unethical practices to individuals by highlighting dangerous working conditions. Obtaining and sharing the sensitive information associated with whistleblowing can carry great...
Fair Exchange (FE) protocols are a class of cryptographic protocol in which two parties, X and Y , exchange some secret data, where the ability of each party to receive secret data is contingent on having sent secret data of their own. When exchanging secret data without the support of FE protocols, whoever sends their secret first makes themselves vulnerable to the possibility that the other participant will cheat and won’t send their secret in return. It is widely believed that FE...
As a multi-receiver variant of public key authenticated encryption with keyword search (PAEKS), broadcast authenticated encryption with keyword search (BAEKS) was proposed by Liu et al. (ACISP 2021). BAEKS focuses on receiver anonymity, where no information about the receiver is leaked from ciphertexts, which is reminiscent of the anonymous broadcast encryption. Here, there are rooms for improving their security definitions, e.g., two challenge sets of receivers are selected before the setup...
Due to the completeness, reliability and zero-knowledge nature, the zero-knowledge proof is widely used to designed various protocols, including zero-knowledge authentication protocols. However, the existing zero-knowledge proof scheme cannot realize bidirectional authentication. In this paper, we design a series of bidirectional zero-knowledge protocols based on two new flavors of operations applicable to multiplicative cyclic group. The two notions are formally defined in this paper. We...
A \emph{witness map} deterministically maps a witness $w$ of some NP statement $x$ into computationally sound proof that $x$ is true, with respect to a public common reference string (CRS). In other words, it is a deterministic, non-interactive, computationally sound proof system in the CRS model. A \emph{unique witness map} (UWM) ensures that for any fixed statement $x$, the witness map should output the same \emph{unique} proof for $x$, no matter what witness $w$ it is applied to. More...
As online group communication scenarios become more and more common these years, malicious or unpleasant messages are much easier to spread on the internet. Message franking is a crucial cryptographic mechanism designed for content moderation in online end-to-end messaging systems, allowing the receiver of a malicious message to report the message to the moderator. Unfortunately, the existing message franking schemes only consider 1-1 communication scenarios. In this paper, we...
Homomorphic encryption for approximate arithmetic allows one to encrypt discretized real/complex numbers and evaluate arithmetic circuits over them. The first scheme, called CKKS, was introduced by Cheon et al. (Asiacrypt 2017) and gained tremendous attention. The enthusiasm for CKKS-type encryption stems from its potential to be used in inference or multiparty computation tasks that do not require an exact output. A desirable property for homomorphic encryption is circuit privacy,...
In this work, we present a novel generic construction for a Distributed Key Generation (DKG) scheme. Our generic construction relies on three modular cryptographic building blocks. The first is an aggregatable Verifiable Secret Sharing (AgVSS) scheme, the second is a Non-Interactive Key Exchange (NIKE) scheme, and the third is a secure hash function. We give formal definitions for the AgVSS and NIKE schemes, as well as concrete constructions. The utility of this generic construction is...
In this work we apply the Type-Safe (TS) generic group model, recently introduced by Zhandry (2022), to the more general setting of group actions and extend it to the universal composability (UC) framework of Canetti (2000). We then relax this resulting model, that we call UC-TS, to define an algebraic action framework (UC-AA), where the adversaries can behave algebraically, similarly to the algebraic group model (AGM), but for group actions. Finally, we instantiate UC-AA with isogeny-based...
We introduce the notion of public key encryption with secure key leasing (PKE-SKL). Our notion supports the leasing of decryption keys so that a leased key achieves the decryption functionality but comes with the guarantee that if the quantum decryption key returned by a user passes a validity test, then the user has lost the ability to decrypt. Our notion is similar in spirit to the notion of secure software leasing (SSL) introduced by Ananth and La Placa (Eurocrypt 2021) but captures...
This work is intended for researchers in the field of side-channel attacks, countermeasure analysis, and probing security. It reports on a formalization of simulatability in terms of linear algebra properties, which we think will provide a useful tool in the practitioner toolbox. The formalization allowed us to revisit some existing definitions (such as probe isolating non-interference) in a simpler way that corresponds to the propagation of erase morphisms. From a theoretical perspective,...
The no-cloning principle of quantum mechanics enables us to achieve amazing unclonable cryptographic primitives, which is impossible in classical cryptography. However, the security definitions for unclonable cryptography are tricky. Achieving desirable security notions for unclonability is a challenging task. In particular, there is no indistinguishable-secure unclonable encryption and quantum copy-protection for single-bit output point functions in the standard model. To tackle this...
Verifiable random functions (VRFs) are essentially pseudorandom functions for which selected outputs can be proved correct and unique, without compromising the security of other outputs. VRFs have numerous applications across cryptography, and in particular they have recently been used to implement committee selection in the Algorand protocol. Elliptic Curve VRF (ECVRF) is an elegant construction, originally due to Papadopoulos et al., that is now under consideration by the Internet...
We introduce a new primitive called the asymmetric trapdoor pseudorandom generator (ATPRG), which belongs to pseudorandom generators with two additional trapdoors (a public trapdoor and a secret trapdoor) or backdoor pseudorandom generators with an additional trapdoor (a secret trapdoor). Specifically, ATPRG can only generate public pseudorandom numbers $pr_1,\dots,pr_N$ for the users having no knowledge of the public trapdoor and the secret trapdoor; so this function is the same as...
The pair encodings framework is an important result in the simplified design of complex attribute-based encryption schemes. In particular, it reduces the effort of proving security of a scheme to proving security of the associated pair encoding, which can then be transformed into a provably secure pairing-based encryption scheme with a compiler. Especially the symbolic property, as introduced by Agrawal and Chase (EUROCRYPT '17), has proven to be a valuable security notion that is both...
To date, ideal functionalities securely realized with secure multi-party computation (SMPC) mainly considers functions of the private inputs of a fixed number of a priori known parties. In this paper, we generalize these definitions such that protocols implementing online algorithms in a distributed fashion can be proven to be privacy-preserving. Online algorithms compute online functionalities that allow parties to arrive and leave over time, to provide multiple inputs and to obtain...
Self-sovereign identity (SSI) systems have gained increasing attention over the last five years. In a variety of fields (e.g., education, IT security, law, government), developers and researchers are attempting to give end-users back their right to and control of their data. Although prototypes and theoretical concepts for SSI applications exist, the majority of them are still in their infancy. Due to missing definitions and standards, there is currently a lack of common understanding of SSI...
Function Secret Sharing (FSS; Eurocrypt 2015) allows a dealer to share a function f with two or more evaluators. Given secret shares of a function f, the evaluators can locally compute secret shares of f(x) on an input x, without learning information about f. In this paper, we initiate the study of access control for FSS. Given the shares of f, the evaluators can ensure that the dealer is authorized to share the provided function. For a function family F and an access control list defined...
Adaptor signatures have seen wide applications in layer-2 and peer-to-peer blockchain ap- plications such as atomic swaps and payment channels. We first identify two shortcomings of previous literature on adaptor signatures. (1) Current aim of “script-less” adaptor signatures restricts instantiability, limiting designs based on BLS or current NIST PQC candidates. (2) We identify gaps in current formulations of security. In particular, we show that current notions do not rule out a class of...
Authenticated encryption with associated data (AEAD) forms the core of much of symmetric cryptography, yet the standard techniques for modeling AEAD assume recipients have no ambiguity about what secret key to use for decryption. This is divorced from what occurs in practice, such as in key management services, where a message recipient can store numerous keys and must identify the correct key before decrypting. To date there has been no formal investigation of their security properties or...
An accountable threshold signature (ATS) is a threshold signature scheme where every signature identifies the quorum of signers who generated that signature. They are widely used in financial settings where signers need to be held accountable for threshold signatures they generate. In this paper we initiate the study of proactive refresh for accountable threshold signatures. Proactive refresh is a protocol that lets the group of signers refresh their shares of the secret key, without...
On the one hand, the web needs to be secured from malicious activities such as bots or DoS attacks; on the other hand, such needs ideally should not justify services tracking people's activities on the web. Anonymous tokens provide a nice tradeoff between allowing an issuer to ensure that a user has been vetted and protecting the users' privacy. However, in some cases, whether or not a token is issued reveals a lot of information to an adversary about the strategies used to distinguish...
Fair exchange (also referred to as atomic swap) is a fundamental operation in any cryptocurrency that allows users to atomically exchange coins. While a large body of work has been devoted to this problem, most solutions lack on-chain privacy. Thus, coins retain a public transaction history which is known to degrade the fungibility of a currency. This has led to a flourishing line of related research on fair exchange with privacy guarantees. Existing protocols either rely on heavy scripting...
Threshold ring signatures are digital signatures that allow $t$ parties to sign a message while hiding their identity in a larger set of $n$ users called ''ring''. Recently, Aranha et al. [PKC 2022] introduced the notion of \emph{extendable} threshold ring signatures (ETRS). ETRS allow one to update, in a non-interactive manner, a threshold ring signature on a certain message so that the updated signature has a greater threshold, and/or an augmented set of potential signers. An...
Voter registration is an essential part of almost any election process, and its security is a critical component of election security. Yet, despite notable compromises of voter registration systems, relatively little academic work has been devoted to securing voter registration systems, compared to research on other aspects of election security. In this paper, we present a systematic treatment of voter registration system security. We propose the first rigorous definitional framework for...
The so-called $\omega$-encoding, introduced by Goudarzi, Joux and Rivain (Asiacrypt 2018), generalizes the commonly used arithmetic encoding. By using the additionnal structure of this encoding, they proposed a masked multiplication gadget (GJR) with quasilinear (randomness and operations) complexity. A follow-up contribution by Goudarzi, Prest, Rivain and Vergnaud in this line of research appeared in TCHES 2021. The authors revisited the aforementioned multiplication gadget (GPRV), and...
Today, two-party secure messaging is well-understood and widely adopted on the Internet, e.g., Signal and WhatsApp. Multiparty protocols for secure group messaging on the other hand are less mature and many protocols with different tradeoffs exist. Generally, such protocols require parties to first agree on a shared secret group key and then periodically update it while preserving forward secrecy (FS) and post compromise security (PCS). We present a new framework, called a key lattice,...
Pseudorandom quantum states (PRS) are efficiently constructible states that are computationally indistinguishable from being Haar-random, and have recently found cryptographic applications. We explore new definitions, new properties and applications of pseudorandom states, and present the following contributions: 1. New Definitions: We study variants of pseudorandom function-like state (PRFS) generators, introduced by Ananth, Qian, and Yuen (CRYPTO'22), where the pseudorandomness property...
Threshold cryptographic algorithms achieve robustness against key and access compromise by distributing secret keys among multiple entities. Most prior work focuses on threshold public-key primitives, despite extensive use of authenticated encryption in practice. Though the latter can be deployed in a threshold manner using multi-party computation (MPC), doing so incurs a high communication cost. In contrast, dedicated constructions of threshold authenticated encryption algorithms can...
Many real-world group messaging systems delegate group administration to the application level, failing to provide formal guarantees related to group membership. Taking a cryptographic approach to group administration can prevent both implementation and protocol design pitfalls that result in a loss of confidentiality and consistency for group members. In this work, we introduce a cryptographic framework for the design of group messaging protocols that offer strong security guarantees for...
A Bloom filter is a data structure that maintains a succinct and probabilistic representation of a set $S\subseteq U$ of elements from a universe $U$. It supports approximate membership queries. The price of the succinctness is allowing some error, namely false positives: for any $x\notin S$, it might answer `Yes' but with a small (non-negligible) probability. When dealing with such data structures in adversarial settings, we need to define the correctness guarantee and formalize the...
The notion of distributed authenticated encryption was formally introduced by Agrawal et al. in ACM CCS 2018. In their work, they propose the DiSE construction building upon a distributed PRF (DPRF), a commitment scheme and a PRG. We show that most of their constructions do not meet some of the claimed security guarantees. In fact, all the concrete instantiations of DiSE, as well as multiple follow-up papers (one accepted at ACM CCS 2021), fail to satisfy their strongly-secure definitions....
A significant shortcoming of traditional access control mechanisms is their heavy reliance on reference monitors. Being single points of failure, monitors need to run in protected mode and have permanent online presence in order to handle all access requests. Cryptographic access control offers an alternative solution that provides better scalability and deployability. It relies on security guarantees of the underlying cryptographic primitives and the appropriate key distribution/management...
We provide a strong definition for committing authenticated-encryption (cAE), as well as a framework that encompasses earlier and weaker definitions. The framework attends not only to what is committed but also the extent to which the adversary knows or controls keys. We slot into our framework strengthened cAE-attacks on GCM and OCB. Our main result is a simple and efficient construction, CTX, that makes a nonce-based AE (nAE) scheme committing. The transformed scheme achieves the...
Incompressibility is one of the most fundamental security goals in white-box cryptography. Given recent advances in the design of efficient and incompressible block ciphers such as SPACE, SPNbox and WhiteBlock, we demonstrate the feasibility of reducing incompressible AEAD modes to incompressible block ciphers. We first observe that several existing AEAD modes of operation, including CCM, GCM(-SIV), and OCB, would be all insecure against white-box adversaries even when used with an...
Secure software leasing is a quantum cryptographic primitive that enables us to lease software to a user by encoding it into a quantum state. Secure software leasing has a mechanism that verifies whether a returned software is valid or not. The security notion guarantees that once a user returns a software in a valid form, the user no longer uses the software. In this work, we introduce the notion of secret-key functional encryption (SKFE) with secure key leasing, where a decryption key...
We introduce puncturable key wrapping (PKW), a new cryptographic primitive that supports fine-grained forward security properties in symmetric key hierarchies. We develop syntax and security definitions, along with provably secure constructions for PKW from simpler components (AEAD schemes and puncturable PRFs). We show how PKW can be applied in two distinct scenarios. First, we show how to use PKW to achieve forward security for TLS 1.3 0-RTT session resumption, even when the server's...
Anonymity is an (abstract) security goal that is especially important to threatened user groups. Therefore, widely deployed communication protocols implement various measures to hide different types of information (i.e., metadata) about their users. Before actually defining anonymity, we consider an attack vector about which targeted user groups can feel concerned: continuous, temporary exposure of their secrets. Examples for this attack vector include intentionally planted viruses on...
We study the security of Probabilistic Data Structures (PDS) for handling Approximate Membership Queries (AMQ); prominent examples of AMQ-PDS are Bloom and Cuckoo filters. AMQ-PDS are increasingly being deployed in environments where adversaries can gain benefit from carefully selecting inputs, for example to increase the false positive rate of an AMQ-PDS. They are also being used in settings where the inputs are sensitive and should remain private in the face of adversaries who can...
Privacy is a notoriously difficult property to achieve in complicated systems and especially in electronic voting schemes. Moreover, electronic voting schemes is a class of systems that require very high assurance. The literature contains a number of ballot privacy definitions along with security proofs for common systems. Some machine-checked security proofs have also appeared. We define a new ballot privacy notion that captures a larger class of voting schemes. This notion improves on the...
