Anamorphic signatures allow covert communication through signatures in environments where encryption is restricted. They enable trusted recipients with a double-key to extract hidden messages while the signature remains indistinguishable from a regular one. However, the traditional notion of anamorphic signatures suffers from vulnerabilities, particularly when a single recipient or sender is compromised, exposing all hidden messages and providing undeniable proof that citizens are part of the anamorphic exchange. To address these limitations, we explore a threshold-based approach to distribute trust among multiple recipients, preventing adversaries from decrypting anamorphic messages even if some recipients are compromised. Our first contribution is the formalization of the notion of threshold-recipient anamorphic signatures, where decryption is possible only through collaboration among a subset of recipients. We then explore a stronger model in which the dictator controls the key-generation process through which it learns all secret keys, as well as how citizens store cryptographic keys. A particular example of this model in the real world is a dictator providing citizens with electronic identity documents (eIDs) and blocking all other usage of cryptography. We demonstrate that anamorphic communication is still possible even in such a scenario. Our construction is secure against quantum adversaries and does not rely on any computational assumptions beyond the random-oracle model. Finally, we present an impossibility result for encoding anamorphic messages with a threshold-sender model when using many existing threshold signature schemes, even when the adversary is part of the signing group. Our work outlines both the possibilities and limitations of extending anamorphic signatures with threshold cryptography, offering new insights into improving the security and privacy of individuals under authoritarian regimes.

Web3 applications, such as on-chain games, NFT minting, and leader elections necessitate access to unbiased, unpredictable, and publicly verifiable randomness. Despite its broad use cases and huge demand, there is a notable absence of comprehensive treatments of on-chain verifiable randomness services. To bridge this, we offer an extensive formal analysis of on-chain verifiable randomness services. We present the first formalization of on-chain verifiable randomness in the blockchain setting by introducing the notion of Verifiable Randomness as a Service (VRaaS). We formally define VRaaS using an ideal functionality$\mathcal{F}\text{VRaaS}$in the Universal Composability model. Our definition not only captures the core features of randomness services, such as unbiasability, unpredictability, and public verifiability, but also accounts for many other crucial nuances pertaining to different entities involved, such as smart contracts. Within our framework we study a generic design of Verifiable Random Function (VRF)-based randomness service - where the randomness requester provides an input on which the randomness is evaluated as VRF output. We show that it does satisfy our formal VRaaS definition. Furthermore, we show that the generic protocol captures many real-world randomness services like Chainlink VRF and Supra dVRF. Moreover, we investigate the minimalism of the frame-work. Towards that, first we show that, the two transactions in-built in our framework are actually necessary for any randomness service to support the essential qualities. We also discover practical vulnerabilities in other designs such as Algorand beacon, Pyth VRF and Band VRF, captured within our framework.

Blockchain service offerings have seen a rapid rise in recent times. Many of these services realize a decentralized architecture with a threshold adversary to avoid a single point of failure and to mitigate key escrow issues. Although payments to such services are straightforward in systems that support smart contracts, achieving fairness poses challenges in systems like Bitcoin, which use the UTXO model with limited scripting capabilities. This is especially challenging without smart contracts, as we wish to pay only the required threshold of$t$+ 1 out of the$n$servers offering the service, without any server claiming payment twice. In this paper, we introduce Vitārit11.A Sanskrit word for ‘distributed’, a novel payment solution tailored for threshold cryptographic services in UTXO systems like Bitcoin. Our approach guarantees robust, provable security while facilitating practical deployment. We focus on the t-out-of-n distributed threshold verifiable random function (VRF) service with certain properties, such as threshold BLS signatures, a recently highlighted area of interest. Our protocol enables clients to request verifiable random function (VRF) values from the threshold service, triggering payments to up to$t$+ 1 servers of the distributed threshold VRF. Our efficient design relies on simple transactions using signature verification scripts, making it immediately applicable in Bitcoin-like systems. We also introduce new tools and techniques at both the cryptographic and transaction layers, including a novel signature-VRF exchange protocol for standard constructions, which may be of independent interest. Additionally, our transaction flow design prevents malicious servers from claiming payments twice, offering broader implications for decentralized payment systems. Our prototype implementation shows that in the two-party interaction, the client takes 126.4 msec, and the server takes 204 msec, demonstrating practicality and deployability of the system.

Single-use delegatable signatures allow a delegatee to give the signing right in a restrictive way to a third party. This cryptographic primitive finds applications in the design of blank checks and can even delegate access rights in web authentication. Unfortunately, known constructions work only with non-standard signature schemes and require non-existing secure hardware, making them impractical.

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 (which also degrades fungibility and leads to high transaction fees), do not support atomic swaps across a wide range of currencies, or come with incomplete security proofs.To overcome these limitations, we introduce Sweep-UC1, the first fair exchange protocol that simultaneously is efficient, minimizes scripting, and is compatible with a wide range of currencies (more than the state of the art). We build SweepUC from modular sub-protocols and give a rigorous security analysis in the UC framework. Many of our tools and security definitions can be used in standalone fashion and may serve as useful components for future constructions of fair exchange.

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 mediator makes both versions inherently different. The mediator applies access policies to rate-limit users' access to the service while, at the same time, should be oblivious to the website/origin the user is trying to access. In this paper, we formally define the rate-limited Privacy Pass protocol and propose a game-based security model to capture the informal security notions introduced by Hendrickson et al.. We show a construction from simple building blocks that fulfills our security definitions and even allows for a post-quantum secure instantiation. Interestingly, the instantiation proposed in the IETF draft is a specific case of our construction. Thus, we can reuse the security arguments for the generic construction and show that the version used in practice is secure.

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 certain reasonable adversarial models, (2) are inefficient in practice or (3) are incompatible with many existing currencies.

The FIDO2 standard is a widely-used class of challenge-response type protocols that allows to authenticate to an online service using a hardware token. Barbosa et al. (CRYPTO ‘21) provided the first formal security model and analysis for the FIDO2 standard. However, their model has two shortcomings: (1) It does not include privacy, one of the key features claimed by FIDO2. (2) It only covers tokens that store all secret keys locally. In contrast, due to limited memory, most existing FIDO2 tokens either derive all secret keys from a common seed or store keys on the server (the latter approach is also known as key wrapping).In this paper, we revisit the security of the WebAuthn component of FIDO2 as implemented in practice. Our contributions are as follows. (1) We adapt the model of Barbosa et al. so as to capture authentication tokens using key derivation or key wrapping. (2) We provide the first formal definition of privacy for the WebAuthn component of FIDO2. We then prove the privacy of this component in common FIDO2 token implementations if the underlying building blocks are chosen appropriately. (3) We address the unsolved problem of global key revocation in FIDO2. To this end, we introduce and analyze a simple revocation procedure that builds on the popular BIP32 standard used in cryptocurrency wallets and can efficiently be implemented with existing FIDO2 servers.

Two-factor authentication (2FA) mitigates the security risks of passwords as sole authentication factor. FIDO2---the de facto standard for interoperable web authentication---leverages strong, hardware-backed second factors. However, practical challenges hinder wider FIDO2 user adoption for 2FA tokens, such as the extra costs (20-30 per token) or the risk of inaccessible accounts upon token loss/theft.

This paper presents a timing attack on the FIDO2 (Fast IDentity Online) authentication protocol that allows attackers to link user accounts stored in vulnerable authenticators, a serious privacy concern. FIDO2 is a new standard specified by the FIDO industry alliance for secure token online authentication. It complements the W3C WebAuthn specification by providing means to use a USB token or other authenticator (which holds the secret authenticating material and implements FIDO protocols) as a second factor during the authentication process. From a cryptographic perspective, the protocol is a simple challenge-response where the elliptic curve digital signature algorithm is used to sign challenges. To protect the privacy of the user the token uses unique key pairs per service. To accommodate for small memory, tokens use various techniques that make use of a special parameter called a key handle sent by the service to the token with which the token can securely produce an authentication key (through generation or decryption). We identify and analyse a vulnerability in the way the processing of key handles is implemented that allows attackers to remotely link user accounts on multiple services. We show that for vulnerable authenticators there is a difference between the time it takes to process a key handle for a different service but correct authenticator, and for a different authenticator but correct service. This difference can be used to perform a timing attack allowing an adversary to link user’s accounts across services. We present several real world examples of adversaries that are in a position to execute our attack and can benefit from linking accounts. We found that two of the eight hardware authenticators we tested were vulnerable despite FIDO level 1 certification, indicating a not insignificant problem. This vulnerability cannot be easily mitigated on authenticators because, for security reasons, they usually do not allow firmware updates. In addition, we show that due to the way existing browsers implement the WebAuthn standard, the attack can be executed remotely. However, we discuss countermeasures that can be implemented by browser providers to mitigate the remote form of the attack.

Anonymous credentials (ACs) are a powerful cryptographic tool for the secure use of digital services, when simultaneously aiming for strong privacy guarantees of users combined with strong authentication guarantees for providers of services. They allow users to selectively prove possession of attributes encoded in a credential without revealing any other meaningful information about themselves. While there is a significant body of research on AC systems, modern use-cases of ACs such as mobile applications come with various requirements not sufficiently considered so far. These include preventing the sharing of credentials and coping with resource constraints of the platforms (e.g., smart cards such as SIM cards in smartphones). Such aspects are typically out of scope of AC constructions, and, thus AC systems that can be considered entirely practical have been elusive so far.

In a Single Secret Leader Election (SSLE), a group of participants aim to randomly choose exactly one leader from the group with the restriction that the identity of the leader will be known to the chosen leader and nobody else. At a later time, the elected leader should be able to publicly reveal her identity and prove that she has won the election. The election process itself should work properly even if many registered users are passive and do not send any messages. Among the many applications of SSLEs, their potential for enabling more efficient proof-of-stake based cryptocurrencies have recently received increased attention.

Group signatures present a compromise between the traditional goals of digital signatures and the need for signer privacy, allowing for the creation of unforgeable signatures in the name of a group which reveal nothing about the actual signer's identity beyond their group membership. An important consideration that is absent in prevalent models is that group membership itself may be sensitive information, especially if group membership is dynamic, i.e. membership status may change over time. We address this issue by introducing formal notions of membership privacy for fully dynamic group signature schemes, which can be easily integrated into the most expressive models of group signature security to date. We then propose a generic construction for a fully dynamic group signature scheme with membership privacy that is based on signatures with flexible public key (SFPK) and signatures on equivalence classes (SPSEQ). Finally, we devise novel techniques for SFPK to construct a highly efficient standard model scheme (i.e. without random oracles) that provides shorter signatures than even the non-private state-of-the-art from standard assumptions. This shows that, although the strictly stronger security notions we introduce have been completely unexplored in the study of fully dynamic group signatures so far, they do not come at an additional cost in practice.

Security of many cryptographic protocols is conditioned by the quality of the random elements generated in the course of the protocol execution. On the other hand, cryptographic devices implementing these protocols are designed given technical limitations, usability requirements and cost constraint s. This frequently results in a black box solution. Unfortunately, black box random number generators may enable creating backdoors for stealing signing keys, breaking authentication protocols and encrypted communication. In this paper we deal with this problem and extend our approach proposed during MYCRYPT’2016. The solution discussed is generating random parameters so that: (a) the protocols are backwards compatible (a user gets additional data that can be simply ignored), (b) verification of randomness might be executed any time without notice, so a device is forced to behave honestly, (c) the solution makes almost no intrusion in the existing protocols and is easy to implement, (d) the owner of a cryptographic device becomes secured against its designer and manufacturer that may even predict the output of the generator. In this paper we focus on a case when Diffie-Hellman protocol is executed for a generator that itself is a secret – this case has not been solved in our paper from MYCRYPT’2016. On the other hand, exactly this case occurs for the PACE protocol from the ICAO standard specifying electronic travel documents. For the sake of the proof we develop a framework of nested security games that aims to enable security proofs of modified protocols without redoing the proofs designed for their original versions.

The paper discusses the issue of thermal imaging attacks on a variety of keyboard devices, such as cash machines, payment terminals, combination locks or computer keyboards. The aim of the research was to obtain the entered code or password in the most non-invasive way. As it turned out, attacks based on images from thermal imaging cameras are very easy to carry out and work in almost every case, which calls for extra safety measures. The authors consider various attack scenarios and come up with recommendations for both manufacturers and users of electronic keyboard security systems.

In this paper we investigate the concept of cancelable biometrics and propose a new scheme for user authorisation providing anonymity based on privacy-preserving computations on sets. We define a problem called (t;n) -Threshold Subset Problem and apply it to a biometric-based security system. Our solution implements biometric template protection based on one-way transformations and Bloom filters. Users authentication data is stored in form of a whitelist and the authorisation process is based on a zero-knowledge proof approach. Using oblivious polynomial evaluation (OPE) a legitimate user is able to recreate a secret polynomial and answer the challenge send by a verifier. We assume that biometric data can be acquired and digitized to the form of a vector representation.

Anonymous credential systems have to provide strong privacy protection: a user may prove his (chosen) attributes without leaking neither his identity nor other attributes. In this paper we consider U-Prove - one of the major commercial anonymous credential systems.

We present a variant of the protocol stack for anonymous authentication implemented in German personal identity documents. We strengthen the system by eliminating group keys - a potential target of attack for a powerful adversary aiming to undermine Restricted Identification mechanisms. We provide a mechanism of authentication that merges Chip Authentication protocol with Restricted Identification.