Publications

Adaptor signatures enable scriptless protocols on blockchains such as Bitcoin by allowing a buyer to lock a coin based on an NP statement and release payment to any party that reveals the corresponding witness. They underlie a broad class of layer-2 protocols, including payment channels, cross-chain swaps, and coin-mixing services, which today secure billions of dollars in locked value.

Fairness for existing adaptor-signature constructions, however, is inherently two-party, so does not apply to deployments in which the buyer or witness holder is operated by a committee. In this work, we formalize and solve the fair exchange problem in that setting. We consider a buyer group holding shares of a signing key controlling a coin, and a seller group holding shares of a secret witness.

The goal is to guarantee fairness both between groups (ensuring that each group obtains its asset if and only if the other does), as well as within groups (ensuring that all honest buyers learn the witness and all honest sellers receive payment), even in the presence of malicious insiders and/or partial information leakage. We present efficient protocols achieving these guarantees under standard cryptographic assumptions on scriptless blockchains with timelocks.

Our construction introduces two new primitives of independent interest, threshold adaptor signatures and certified witness encryption, which we define, analyze, and instantiate efficiently.

Adaptor signatures extend the functionality of digital signatures by enabling the computation of pre-signatures on messages relative to statements in NP relations. Pre-signatures are publicly verifiable objects that simultaneously hide and commit to a standard signature on the same message. Anyone possessing a valid witness for the statement can adapt the pre-signature into a full signature under the underlying signature scheme. Since adaptor signatures are commonly used as building blocks in larger systems—such as blockchain protocols—it is natural to seek a security definition within the Universal Composability (UC) framework. A recent attempt by Tairi et al. (CCS’23) introduced the first UC functionality for adaptor signatures. This paper makes both negative and positive contributions. Negative results. We show that the functionality proposed by Tairi et al. suffers from critical limitations:

• The functionality fails to guarantee extractability and adaptability—the core security properties of adaptor signatures—to higher-level protocols.
• No adaptor signature scheme can realize the functionality. Positive results. We propose a new UC functionality that faithfully captures the latest security guarantees of adaptor signatures as formalized via game-based notions by Gerhart et al. (EUROCRYPT’24): - Our functionality guarantees extractability, unique extractability, and pre-signature adaptability in a way that is composable and meaningful for higher-level protocols. - We show that it is realizable by an enhanced Schnorr-based adaptor signature scheme that we construct. Our construction maintains compatibility with existing infrastructure and is efficient enough for practical deployment, particularly in Bitcoin-like environments.

Password-Hardened Encryption (PHE) protects against offline brute-force attacks by involving an external ratelimiter that enforces rate-limited decryption without learning passwords or keys. Threshold Password-Hardened Encryption (TPHE), introduced by Brost et al. (CCS’20), distributes this trust among multiple ratelimiters. Despite its promise, the security foundations of TPHE remain unclear.

We make three contributions: (1) We uncover a flaw in the proof of Brost et al.’s TPHE scheme, which invalidates its claimed security and leaves the guarantees of existing constructions uncertain; (2) We provide the first universal composability (UC) formalization of PHE and TPHE, unifying previous fragmented models and supporting key rotation, an essential feature for long-term security and related primitives such as updatable encryption; (3) We present the first provably secure TPHE scheme, which is both round-optimal and UC-secure, thus composable in real-world settings; and we implement and evaluate our protocol, demonstrating practical efficiency that outperforms prior work in realistic WAN scenarios.

Adaptor signatures extend the functionality of regular signatures through the computation of pre-signatures on messages for statements of NP relations. Presignatures are publicly verifiable; they simultaneously hide and commit to a signature of an underlying signature scheme on that message. Anybody possessing a corresponding witness for the statement can adapt the pre-signature to obtain the “regular” signature. Adaptor signatures have found numerous applications for conditional payments in blockchain systems, like payment channels (CCS’20, CCS’21), private coin mixing (CCS’22, SP’23), and oracle-based payments (NDSS’23). In our work, we revisit the state of the security of adaptor signatures and their constructions. In particular, our two main contributions are:

• Security Gaps and Definitions: We review the widely-used security model of adaptor signatures due to Aumayr et al. (ASIACRYPT’21) and identify gaps in their definitions that render known protocols for private coin-mixing and oracle-based payments insecure. We give simple counterexamples of adaptor signatures that are secure w.r.t. their definitions but result in insecure instantiations of these protocols. To fill these gaps, we identify a minimal set of modular definitions that align with these practical applications.

• Secure Constructions: Despite their popularity, all known constructions are (1) derived from identification schemes via the Fiat-Shamir transform in the random oracle model or (2) require modifications to the underlying signature verification algorithm, thus making the construction useless in the setting of cryptocurrencies. More concerningly, all known constructions were proven secure w.r.t. the insufficient definitions of Aumayr et al., leaving us with no provably secure adaptor signature scheme to use in applications.

Firstly, in this work, we salvage all current applications by proving the security of the widely-used Schnorr adaptor signatures under our proposed definitions. We then provide several new constructions, including presenting the first adaptor signature schemes for Camenisch-Lysyanskaya (CL), BonehBoyen-Shacham (BBS+), and Waters signatures, all of which are proven secure in the standard model. Our new constructions rely on a new abstraction of digital signatures, called dichotomic signatures, which covers the essential properties we need to build adaptor signatures. Proving the security of all constructions (including identification-based schemes) relies on a novel nonblack-box proof technique. Both our digital signature abstraction and the proof technique could be of independent interest to the community.

Bitcoin and other cryptocurrencies have recently introduced support for Schnorr signatures whose cleaner algebraic structure, as compared to ECDSA, allows for simpler and more practical constructions of highly demanded “t-of-n” threshold signatures. However, existing Schnorr threshold signature schemes still fall short of the needs of real-world applications due to their assumption that the network is synchronous and due to their lack of robustness, i.e., the guarantee that t honest signers are able to obtain a valid signature even in the presence of other malicious signers who try to disrupt the protocol. This hinders the adoption of threshold signatures in the cryptocurrency ecosystem, e.g., in second-layer protocols built on top of cryptocurrencies.

In this work, we propose ROAST, a simple wrapper that turns a given threshold signature scheme into a scheme with a robust and asynchronous signing protocol, as long as the underlying signing protocol is semi-interactive (i.e., has one preprocessing round and one actual signing round), provides identifiable aborts, and is unforgeable under concurrent signing sessions. When applied to the state-of-the-art Schnorr threshold signature scheme FROST, which fulfills these requirements, we obtain a simple, efficient, and highly practical Schnorr threshold signature scheme.

Decentralized cryptocurrencies still suffer from three interrelated weaknesses: Low transaction rates, high transaction fees, and long confirmation times. Payment Channels promise to be a solution to these issues, and many constructions for real-life cryptocurrencies, such as Bitcoin, are known. Somewhat surprisingly, no such solution is known for Monero, the largest privacy-preserving cryptocurrency, without requiring system-wide changes like a hard-fork of its blockchain.

In this work, we close this gap by presenting PayMo. This first payment channel protocol is fully compatible with Monero’s transaction scheme and can be readily used to perform off-chain payments. Notably, transactions in PayMo are identical to standard transactions in Monero, therefore not hampering the coins’ fungibility. Using PayMo, we also construct a provably secure and scriptless atomic-swap protocol compatible with the transaction scheme of Monero: One can now securely swap a token of Monero with a token of several major cryptocurrencies such as Bitcoin, Ethereum, Ripple, Cardano, etc. Before our work, atomic swaps protocol for Monero existed only for a limited set of other currencies via ad-hoc approaches.

Our main technical contribution is a new construction of an efficient verifiable timed linkable ring signature, where signatures can be hidden for a pre-determined amount of time in a verifiable way. Our scheme is fully compatible with the transaction scheme of Monero, and it might be of independent interest to develop other applications on Monero.

We implemented PayMo and our results show that, even with high network latency and with a single CPU core, two regular users can perform up to 93500 payments over 2 minutes (the block production rate of Monero). This is approximately five orders of magnitude improvement over the current payment rate of Monero.

A ring signature scheme allows the signer to sign on behalf of an ad hoc set of users, called a ring. The verifier can be convinced that a ring member signs, but cannot point to the exact signer. Ring signatures have become increasingly important today with their deployment in anonymous cryptocurrencies. Conventionally, it is implicitly assumed that all ring members are equally likely to be the signer. This assumption is generally false in reality, leading to various practical and devastating deanonymizing attacks in Monero, one of the largest anonymous cryptocurrencies. These attacks highlight the unsatisfactory situation that how a ring should be chosen is poorly understood.

We propose an analytical model of ring samplers towards a deeper understanding of them through systematic studies. Our model helps to describe how anonymous a ring sampler is with respect to a given signer distribution as an information-theoretic measure. We show that this measure is robust, in the sense that it only varies slightly when the signer distribution varies slightly. We then analyze three natural samplers – uniform, mimicking, and partitioning – under our model with respect to a family of signer distributions modeled after empirical Bitcoin data. We hope that our work paves the way towards researching ring samplers from a theoretical point of view.

Monero is the largest cryptocurrency with built-in cryptographic privacy features. The transactions are authenticated using zero-knowledge spend proofs, which provide a certain level of anonymity by hiding the source accounts from which the funds are sent among a set of other accounts. Due to its similarities to ring signatures, this core cryptographic component is called Ring Confidential Transactions (RingCT). Because of its practical relevance, several works attempt to analyze the security of RingCT. Since RingCT is rather complex, most of them are either informal, miss fundamental functionalities, or introduce undesirable trusted setup assumptions. Regarding efficiency, Monero currently deploys a scheme in which the size of the spend proof is linear in the ring size. This limits the ring size to only a few accounts, which in turn limits the acquired anonymity significantly and facilitates de-anonymization attacks.

As a solution to these problems, we present the first rigorous formalization of RingCT as a cryptographic primitive. We then propose a generic construction of RingCT and prove it secure in our formal security model. By instantiating our generic construction with new efficient zero-knowledge proofs, we obtain Omniring, a fully-fledged RingCT scheme in the discrete logarithm setting that provides the highest concrete and asymptotic efficiency as of today. Omniring is the first RingCT scheme which 1) does not require a trusted setup or pairing-friendly elliptic curves, 2) has a proof size logarithmic in the size of the ring, and 3) allows to share the same ring between all source accounts in a transaction, thereby enabling significantly improved privacy level without sacrificing performance. Our zero-knowledge proofs rely on novel enhancements to the Bulletproofs framework (S&P 2018), which we believe are of independent interest.

Sanitizable signatures allow designated parties (the sanitizers) to apply arbitrary modifications to some restricted parts of signed messages. A secure scheme should not only be unforgeable, but also protect privacy and hold both the signer and the sanitizer accountable. Two important security properties that are seemingly difficult to achieve simultaneously and efficiently are invisibility and unlinkability. While invisibility ensures that the admissible modifications are hidden from external parties, unlinkability says that sanitized signatures cannot be linked to their sources. Achieving both properties simultaneously is crucial for applications where sensitive personal data is signed with respect to data-dependent admissible modifications. The existence of an efficient construction achieving both properties was recently posed as an open question by Camenisch et al. (PKC’17).

In this work, we propose a solution to this problem with a two-step construction. First, we construct (non-accountable) invisible and unlinkable sanitizable signatures from signatures on equivalence classes and other basic primitives. Second, we put forth a generic transformation using verifiable ring signatures to turn any non-accountable sanitizable signature into an accountable one while preserving all other properties. When instantiating in the generic group and random oracle model, the efficiency of our construction is comparable to that of prior constructions, while providing stronger security guarantees.

Order-preserving encryption (OPE) is an encryption scheme with the property that the ordering of the plaintexts carry over to the ciphertexts. This primitive is particularly useful in the setting of encrypted databases because it enables efficient range queries over encrypted data. Given its practicality and usefulness in the design of databases on encrypted data, OPE’s popularity is growing. Unfortunately, nearly all computationally efficient OPE constructions are vulnerable against ciphertext frequency-leakage, which allows for inferring the underlying plaintext frequency. To overcome this weakness, Kerschbaum recently proposed a security model, designed a frequency-hiding OPE scheme, and analyzed its security in the programmable random oracle model (CCS 2015).

In this work, we demonstrate that Kerschbaum’s definition is imprecise and using its natural interpretation, we describe an attack against his scheme. We generalize our attack and show that his definition is, in fact, not satisfiable. The basic idea of our impossibility result is to show that any scheme satisfying his security notion is also IND-CPA-secure, which contradicts the very nature of OPE. As a consequence, no such scheme can exist. To complete the picture, we rule out the imprecision in the security definition and show that a slight adaption of Kerschbaum’s tree-based scheme fulfills it.

A ring signature scheme allows one party to sign messages on behalf of an arbitrary set of users, called the ring. The anonymity of the scheme guarantees that the signature does not reveal which member of the ring signed the message. The ring of users can be selected ”on-thefly” by the signer and no central coordination is required. Ring signatures have made their way into practice in the area of privacy-enhancing technologies and they build the core of several cryptocurrencies. Despite their popularity, almost all ring signature schemes are either secure in the random oracle model or in the common reference string model. The only candidate instantiations in the plain model are either impractical or not fully functional. In this work, we close this gap by proposing a new construction paradigm for ring signatures without random oracles: We show how to efficiently instantiate full-fledged ring signatures from signature schemes with rerandomizable keys and non-interactive zero-knowledge. We obtain the following results:

• The first almost practical ring signature in the plain model from standard assumptions in bilinear groups.

• The first efficient ring signature in the plain model secure under a generalization of the knowledge of exponent assumption.

Oblivious RAM (ORAM) has emerged as an enabling technology to secure cloud-based storage services. The goal of this cryptographic primitive is to conceal not only the data but also the access patterns from the server. While the early constructions focused on a single client scenario, a few recent works have focused on a setting where multiple clients may access the same data, which is crucial to support data sharing applications. All these works, however, either do not consider malicious clients or they significantly constrain the definition of obliviousness and the system’s practicality. It is thus an open question whether a natural definition of obliviousness can be enforced in a malicious multi-client setting and, if so, what the communication and computational lower bounds are.

In this work, we formalize the notion of maliciously secure multi-client ORAM, we prove that the server-side computational complexity of any secure realization has to be Ω(n), and we present a cryptographic instantiation of this primitive based on private information retrieval techniques, which achieves an O(√N) communication complexity. We further devise an efficient access control mechanism, built upon a novel and generally applicable realization of plaintext equivalence proofs for ciphertext vectors. Finally, we demonstrate how our lower bound can be bypassed by leveraging a trusted proxy, obtaining logarithmic communication and server-side computational complexity. We implemented our scheme and conducted an experimental evaluation, demonstrating the feasibility of our approach.

We introduce delegatable functional signatures (DFS) which support the delegation of signing capabilities to another party, called the evaluator, with respect to a functionality F. In a DFS, the signer of a message can choose an evaluator, specify how the evaluator can modify the signature without voiding its validity, allow additional input and decide how the evaluator can further delegate its capabilities.

The main contribution of this paper is twofold. First, we propose DFS, a novel cryptographic primitive that unifies several seemingly different signature primitives, including functional signatures as defined by Boyle, Goldwasser, and Ivan (eprint 2013/401), sanitizable signatures, identity based signatures, and blind signatures. To achieve this unification, we present several definitions of unforgeability and privacy. Finding appropriate and meaningful definitions in this context is challenging due to the natural mealleability of DFS and due to the multi-party setting that may involve malicious keys. Second, we present a complete characterization of the instantiability of DFS under common assumptions, like the existence of one-way functions. Here, we present both positive and negative results. On the positive side we show that DFS not achieving our notion of privacy can be constructed from one-way functions. Furthermore, we show that unforgerable and private DFS can be constructed from doubly enhanced trapdoor permutations. On the negative side we show that the previous result is optimal regarding its underlying assumptions presenting an impossibility result for unforgeable private DFS from one-way permutations.

In a sanitizable signature scheme the signer allows a designated third party, called the sanitizer, to modify certain parts of the message and adapt the signature accordingly. Ateniese et al. (ESORICS 2005) introduced this primitive and proposed five security properties which were formalized by Brzuska et al. (PKC 2009). Subsequently, Brzuska et al. (PKC 2010) suggested an additional security notion, called unlinkability which says that one cannot link sanitized message-signature pairs of the same document. Moreover, the authors gave a generic construction based on group signatures that have a certain structure. However, the special structure required from the group signature scheme only allows for inefficient instantiations.

Here, we present the first efficient instantiation of unlinkable sanitizable signatures. Our construction is based on a novel type of signature schemes with re-randomizable keys. Intuitively, this property allows to re-randomize both the signing and the verification key separately but consistently. This allows us to sign the message with a re-randomized key and to prove in zero-knowledge that the derived key originates from either the signer or the sanitizer. We instantiate this generic idea with Schnorr signatures and efficient Σ-protocols, which we convert into non-interactive zero-knowledge proofs via the Fiat-Shamir transformation. Our construction is at least one order of magnitude faster than instantiating the generic scheme of Brzuska et al. with the most efficient group signature schemes.

Pseudorandom functions (PRFs) are one of the most fundamental building blocks in cryptography with numerous applications such as message authentication codes and private key encryption. In this work, we propose a new framework to construct PRFs with the overall goal to build efficient PRFs from standard assumptions with an almost tight proof of security. The main idea of our framework is to start from a PRF for any small domain (i.e. poly-sized domain) and turn it into an ℓ-bounded pseudorandom function, i.e., into a PRF whose outputs are pseudorandom for the first ℓ distinct queries to F . In the second step, we apply a novel technique which we call on-the-fly adaptation that turns any bounded PRF into a fully-fledged (large domain) PRF. Both steps of our framework have a tight security reduction, meaning that any successful attacker can be turned into an efficient algorithm for the underlying hard computational problem without any significant increase in the running time or loss of success probability.

Instantiating our framework with specific number theoretic assumptions, we construct a PRF based on k-LIN (and thus DDH) that is faster than all known constructions, which reduces almost tightly to the underlying problem, and which has shorter keys. Instantiating our framework with general assumptions, we construct a PRF with very flat circuits whose security tightly reduces to the security of some small domain PRF.

In structure-preserving signatures on equivalence classes (SPS-EQ-R), introduced at Asiacrypt 2014, each message M in (G*)^ℓ is associated to its projective equivalence class, and a signature commits to the equivalence class: anybody can transfer the signature to a new, scaled, representative.

In this work, we give the first black-box construction of a public-key encryption scheme from any SPS-EQ-R satisfying a simple new property which we call perfect composition. The construction does not involve any non-black-box technique and the implication is that such SPS-EQ-R cannot be constructed from one-way functions in a black-box way. The main idea of our scheme is to build a verifiable encrypted signature (VES) first and then apply the general transformation suggested by Calderon et al. (CT-RSA 2014).

The original definition of VES requires that the underlying signature scheme be correct and secure in addition to other security properties. The latter have been extended in subsequent literature, but the former requirements have sometimes been neglected, leaving a hole in the security notion. We show that Calderon et al.’s notion of resolution independence fills this gap.

A recent line of work has explored the use of physically uncloneable functions (PUFs) for secure computation, with the goals of (1) achieving universal composability without additional setup, and/or (2) obtaining unconditional security (i.e., avoiding complexity-theoretic assumptions). Initial work assumed that all PUFs, even those created by an attacker, are honestly generated. Subsequently, researchers have investigated models in which an adversary can create malicious PUFs with arbitrary behavior. Researchers have considered both malicious PUFs that might be stateful, as well as malicious PUFs that can have arbitrary behavior but are guaranteed to be stateless. We settle the main open questions regarding secure computation in the malicious-PUF model:

• We prove that unconditionally secure oblivious transfer is impossible, even in the standalone setting, if the adversary can construct (malicious) stateful PUFs.

• If the attacker is limited to creating (malicious) stateless PUFs, then universally composable two-party computation is possible without computational assumptions.

Verifiable random functions (VRFs), firstly proposed by Micali, Rabin, and Vadhan (FOCS 99), are pseudorandom functions with the additional property that the owner of the seed SK can issue publicly-verifiable proofs for the statements “f (SK , x) = y”, for any input x. Moreover, the output of VRFs is guaranteed to be unique, which means that y = f (SK , x) is the only image that can be proven to map to x. Due to their properties, VRFs are a fascinating primitive that have found several theoretical and practical applications. However, despite their popularity, constructing VRFs seems to be a challenging task. Indeed only a few constructions based on specific number-theoretic problems are known and basing a scheme on a general assumption is still an open problem. Towards this direction, Brakerski, Goldwasser, Rothblum, and Vaikuntanathan (TCC 2009) recently showed that verifiable random functions cannot be constructed from one-way permutations in a black-box way. In this paper we put forward the study of the relationship between VRFs and well-established cryptographic primitives. As our main result, we prove that VRFs cannot be based on the existence of trapdoor permutations (TDPs) in a black-box manner. Our result sheds light on the nature of VRFs and can be considered interesting for at least two reasons:

• First, given the separation result of Brakerski et al., one may think as though VRFs would naturally belong to the “public-key world”, and thus it is interesting to figure out their relationship with other public-key primitives. In this sense, our result shows that VRFs are much stronger because we imply separations of VRFs from most of the primitives in this world: basically everything that is implied by TDPs is strictly weaker. These primitives include e.g., public-key encryption (even CCA-secure), oblivious transfer, and key-agreement.

• Second, the notion of VRFs is closely related to other two primitives: weak verifiable random functions (weak-VRFs) and verifiable pseudorandom generators (VPRGs). Weak-VRFs, defined by Brakerski et al., are a relaxation of VRFs in which the pseudorandomness holds only with respect to random inputs. VPRGs, introduced by Dwork and Naor (FOCS 2000), are pseudorandom generators that allow the owner of the seed to prove the correctness of subsets of the generated bits. It is well known that “regular” PRFs can be constructed from pseudorandom generators and from weak-PRFs in a black-box way. It was thus an open problem (already recognized by Dwork and Naor in their paper) whether similar approaches could be applicable to the “verifiable” analogous of such primitives. Since weak-VRFs and VPRGs are implied by TDPs, we give a negative answer to this problem showing that the case of verifiable random functions is essentially different.

All known round optimal (i.e., two-move) blind signature schemes either need a common reference string, rely on random oracles, or assume the hardness of some interactive assumption. At Eurocrypt 2010, Fischlin and Schröder showed that a broad class of three-move blind signature scheme cannot be instantiated in the standard model based on any non-interactive assumption. This puts forward the question if round optimal blind signature schemes exist in the standard model.

Here, we give a positive answer presenting the first round optimal blind signature scheme that is secure in the standard model without any setup assumptions. Our solution does not need interactive assumptions.

Sanitizable signatures have been introduced by Ateniese et al. (ESORICS 2005) and allow an authorized party, the sanitizer, to modify a predetermined part of a signed message without invalidating the signature. Brzuska et al. (PKC 2009) gave the first comprehensive formal treatment of the five security properties for such schemes. These are unforgeability, immutability, privacy, transparency and accountability. They also provide a modification of the sanitizable signature scheme proposed by Ateniese et al. such that it provably satisfies all security requirement. Unfortunately, their scheme comes with rather large signature sizes and produces computational overhead that increases with the number of admissible modifications.

In this paper we show that by sacrificing the transparency property —thus allowing to distinguish whether a message has been sanitized or not— we can obtain a sanitizable signature scheme that is still provably secure concerning the other aforementioned properties but significantly more efficient. We propose a construction that is based solely on regular signature schemes, produces short signatures and only adds a small computational overhead.