2000 results sorted by ID
Possible spell-corrected query: authentication protocol
Performance and Privacy: A Low-Latency Secure Anonymous Authentication Protocol with OPRF
Wenjv Hu, Yanping Ye, Yin Li
Cryptographic protocols
erforming privacy-preserving queries, particularly anonymous authentication, against large-scale datasets presents critical tradeoffs between security, latency, scalability. Existing cryptographic solutions often impose linear
computation or communication overheads. This paper introduces a novel,
efficient protocol for secure anonymous authentication, uniquely combining matrix partitioning via hash prefixes with Oblivious Pseudorandom Functions in a
three-server semi-honest model....
Guarding the Signal: Secure Messaging with Reverse Firewalls
Yevgeniy Dodis, Bernardo Magri, Noah Stephens-Davidowitz, Yiannis Tselekounis
Cryptographic protocols
Secure messaging protocols allow users to communicate asynchronously over untrusted channels with strong guarantees of privacy, authenticity, forward secrecy, and post-compromise security. However, traditional security analyses of these protocols assume complete trust in the hardware and software of honest participants, overlooking a significant class of real-world threats known as subversion attacks. These attacks alter cryptographic algorithms to compromise security, by exfiltrating...
ZK-NR: A Layered Cryptographic Architecture for Explainable Non-Repudiation
Thierry Emmanuel MINKA MI NGUIDJOI, MANI ONANA Flavien Serge, DJOTIO NDIÉ Thomas
Cryptographic protocols
This paper introduces ZK-NR, a modular cryptographic protocol designed to ensure privacy-preserving non-repudiation in the co-production of digital public services. By integrating Merkle commitments, zero-knowledge proofs (STARKs), threshold BLS signatures, and post-quantum Dilithium authentication, ZK-NR enables the creation of secure, verifiable, and auditable evidence across decentralized infrastructures. Unlike traditional digital signatures or blockchain-based logs, ZK-NR provides...
Laconic PSI on Authenticated Inputs and Applications
James Bartusek, Sanjam Garg, Abhishek Jain, Guru-Vamsi Policharla
Cryptographic protocols
A common issue with using secure computation in practice is that its security does not place any restrictions on what an adversary can use as input in the protocol. In this work, we focus on the practically-motivated setting of (two-message, labeled) private set intersection (PSI), and advocate for a clean and versatile solution to this problem: PSI on authenticated inputs.
Our central contributions are summarized as follows.
- We formulate a novel definition of PSI on authenticated...
Tanuki: New Frameworks for (Concurrently Secure) Blind Signatures from Post-Quantum Groups Actions
Lucjan Hanzlik, Yi-Fu Lai, Marzio Mula, Eugenio Paracucchi, Daniel Slamanig, Gang Tang
Cryptographic protocols
Blind signatures are fundamental cryptographic primitives enabling privacy-preserving authentication and have seen renewed interest in the post-quantum literature.
Existing efficient constructions predominantly rely on Fischlin’s generic paradigm instantiated over lattice assumptions, while blinding techniques for sigma-protocol-based blind signatures remain sparse beyond lattices. Moreover, achieving provable concurrent security under polynomially many sessions has been a longstanding...
LAPWN: A Lightweight User–Server Authentication Protocol for Wireless Networks
Sajjad Alizadeh, Reza Hooshmand
Cryptographic protocols
The Internet of Things (IoT) is composed of interconnected devices that exchange data over a network,
enabling applications in healthcare, transportation, and smart environments. As IoT ecosystems expand,
ensuring security and privacy remains a critical challenge. Many IoT devices rely on wireless
networks for data transmission, making them vulnerable to eavesdropping, tracking, and tampering.
This highlights the need for robust authentication mechanisms. To address these concerns,...
A New PUF-Based Authenticated Key Establishment Protocol for V2G Networks
Milad Seddigh, Seyed Hamid Baghestani, Mahdi Esfahani
Cryptographic protocols
Vehicle-to-grid (V2G) refers to the bidirectional communication and energy flows that allow renewable energy sources to supply supplementary electrical services between electric cars (EVs) and the power grid. Additionally, V2G lowers environmental pollution and energy issues while providing efficient charging services. A PUF-based, reliable, anonymous authentication and key establishment scheme for V2G networks was recently presented by Sungjin Yu et al. In this paper, we show that the Yu et...
TrafficProof: Privacy-Preserving Reliable Traffic Information Sharing in Social Internet of Vehicles
Stefan Dziembowski, Shahriar Ebrahimi, Parisa Hassanizadeh, Susil Kumar Mohanty
Applications
In the Social Internet of Vehicles (SIoV), effective data sharing is essential for applications including road safety, traffic management, and situational awareness. However, the decentralized and open nature of SIoV presents significant challenges in simultaneously ensuring data integrity, user privacy, and system accountability. This paper presents a protocol for secure and location-accurate traffic data sharing that fully preserves the anonymity and privacy of participating witnesses. The...
XHMQV: Better Efficiency and Stronger Security for Signal’s Initial Handshake based on HMQV
Rune Fiedler, Felix Günther, Jiaxin Pan, Runzhi Zeng
Cryptographic protocols
The Signal protocol is the most widely deployed end-to-end-encrypted messaging protocol. Its initial handshake protocol X3DH allows parties to asynchronously derive a shared session key without the need to be online simultaneously, while providing implicit authentication, forward secrecy, and a form of offline deniability. The X3DH protocol has been extensively studied in the cryptographic literature and is acclaimed for its strong "maximum-exposure" security guarantees, hedging against...
Trusted Hardware-Assisted Leaderless Byzantine Fault Tolerance Consensus
Liangrong Zhao, Jérémie Decouchant, Joseph K. Liu, Qinghua Lu, Jiangshan Yu
Applications
Byzantine Fault Tolerance (BFT) Consensus protocols with trusted hardware assistance have been extensively explored for their improved resilience to tolerate more faulty processes. Nonetheless, the potential of trust hardware has been scarcely investigated in leaderless BFT protocols. RedBelly is assumed to be the first blockchain network whose consensus is based on a truly leaderless BFT algorithm. This paper proposes a trusted hardware-assisted leaderless BFT consensus protocol by offering...
Towards Trustless Provenance: A Privacy-Preserving Framework for On-chain Media Verification
Piotr Mikołajczyk, Parisa Hassanizadeh, Shahriar Ebrahimi
Applications
As generative models continue to evolve, verifying the authenticity, provenance, and integrity of digital media has become increasingly critical—particularly for domains like journalism, digital art, and scientific documentation.
In this work, we present a decentralized verifiable media ecosystem for managing, verifying, and transacting authentic digital media using zero-knowledge proofs (ZKPs).
Building on VIMz (Dziembowski et al., PETS'25), we extend the framework in three key...
Burn Your Vote: Decentralized and Publicly Verifiable Anonymous Voting at Scale
Stefan Dziembowski, Shahriar Ebrahimi, Haniyeh Habibi, Parisa Hassanizadeh, Pardis Toolabi
Cryptographic protocols
Secure and trustworthy electronic voting requires more than correctness and censorship resistance, it must also ensure voter privacy, vote confidentiality, and protection against coercion. Prior work attempt to address these challenges using heavyweight cryptographic primitives such as homomorphic encryption, time-lock puzzles, or multi-party computation. These approaches often involve complex computations, depend on trusted parties, and typically do not scale well. We propose a lightweight,...
TEAKEX: TESLA-Authenticated Group Key Exchange
Qinyi Li, Lise Millerjord, Colin Boyd
Cryptographic protocols
We present a highly efficient authenticated group key exchange protocol, TEAKEX, using only symmetric key primitives. Our protocol provides proven strong security, including forward secrecy, post-compromise security, and post-quantum security. For online applications we claim that TEAKEX is much simpler and more efficient than currently available alternatives. As part of our construction we also give a new abstract security definition for delayed authentication and describe its instantiation...
On the UC-(In)Security of PAKE Protocols Without the Random Oracle Model
Naman Kumar, Jiayu Xu
Cryptographic protocols
A Password-Authenticated Key Exchange (PAKE) protocol allows two parties to jointly establish a cryptographic key, where the only information shared in advance is a low-entropy password. The first efficient PAKE protocol whose security does not rely on the random oracle model is the one by Katz, Ostrovsky and Yung (KOY, EUROCRYPT 2001). Unfortunately, the KOY protocol has only been proven secure in the game-based setting, and it is unclear whether KOY is secure in the stronger Universal...
LP2+: a robust symmetric-key AKE protocol with perfect forward secrecy, and an advocacy for thorough security proofs
Pierre-Alain Jacqmin, Jean Liénardy
Cryptographic protocols
Symmetric-key authenticated key establishment (AKE) protocols are particularly well suited in resource constraint environments such as internet of things (IoT) devices. Moreover, they often rely on better understood assumptions than asymmetric ones. In this paper, we review the security model for symmetric-key AKE protocols. We show why several existing models allow trivial attacks while they do not protect against some non-trivial ones. We fix these issues with our new security...
Authenticated Key Exchange Protocol with Remote Randomness
John C. W. Chan
Cryptographic protocols
A conventional Authenticated Key Exchange (AKE) protocol consumes fresh random coins from the local random source. However, recent studies of bad randomness expose the vulnerability of some AKE protocols under small subgroup attacks when the random coins are manipulated or being repeated. It is important to ensure the bad randomness of one random source will not affect the security of the AKE protocol as a whole.
Thus, we introduce the notion of remote randomness by introducing...
Practical Deniable Post-Quantum X3DH: A Lightweight Split-KEM for K-Waay
Guilhem Niot
Public-key cryptography
The Signal Protocol, underpinning secure messaging for billions, faces the challenge of migrating to a post-quantum world while preserving critical properties like asynchrony and deniability. While Signal’s PQXDH key exchange protocol addresses post-quantum confidentiality, full migration of the X3DH protocol remains elusive. Relying on a split KEM (K-Waay, USENIX ’24) offers a promising migration path, but it has so far suffered from size limitations compared to concurrent works...
Row Reduction Techniques for $n$-Party Garbling
Kelong Cong, Emmanuela Orsini, Erik Pohle, Oliver Zajonc
Cryptographic protocols
Recent advancements in maliciously secure garbling have significantly improved the efficiency of constant-round multi-party computation. Research in the field has primarily focused on reducing communication complexity through row reduction techniques and improvements to the preprocessing phase with the use of simpler correlations.
In this work, we present two contributions to reduce the communication complexity of state of the art multi-party garbling with an arbitrary number of...
A Specification of an Anonymous Credential System Using BBS+ Signatures with Privacy-Preserving Revocation and Device Binding
Christoph Graebnitz, Nicolas Buchmann, Martin Seiffert, Marian Margraf
Cryptographic protocols
Recently, there has been a growing interest in anonymous credentials (ACs) as they can mitigate the risk of personal data being processed by untrusted actors without consent and beyond the user's control. Furthermore, due to the privacy-by-design paradigm of ACs, they can prove possession of personal attributes, such as an authenticated government document containing sensitive personal information, while preserving the privacy of the individual by not actually revealing the data. Typically,...
Post-Quantum Cryptography in eMRTDs: Evaluating PAKE and PKI for Travel Documents
Nouri Alnahawi, Melissa Azouaoui, Joppe W. Bos, Gareth T. Davies, SeoJeong Moon, Christine van Vredendaal, Alexander Wiesmaier
Implementation
Passports, identity cards and travel visas are examples of machine readable travel documents (MRTDs) or eMRTDs for their electronic variants. The security of the data exchanged between these documents and a reader is secured with a standardized password authenticated key exchange (PAKE) protocol known as PACE.
A new world-wide protocol migration is expected with the arrival of post-quantum cryptography (PQC) standards. In this paper, we focus on the impact of this migration on constrained...
POBA: Privacy-Preserving Operator-Side Bookkeeping and Analytics
Dennis Faut, Valerie Fetzer, Jörn Müller-Quade, Markus Raiber, Andy Rupp
Cryptographic protocols
Many user-centric applications face a common privacy problem: the need to collect, store, and analyze sensitive user data. Examples include check-in/check-out based payment systems for public transportation, charging/discharging electric vehicle batteries in smart grids, coalition loyalty programs, behavior-based car insurance, and more. We propose and evaluate a generic solution to this problem. More specifically, we provide a formal framework integrating privacy-preserving data collection,...
Scrutinizing the Security of AES-based Hashing and One-way Functions
Shiyao Chen, Jian Guo, Eik List, Danping Shi, Tianyu Zhang
Attacks and cryptanalysis
AES has cemented its position as the primary symmetric-key primitive for a wide range of cryptographic applications, which motivates the analysis on the concrete security of AES in practical instantiations, for instance, the collision resistance of AES-based hashing, the key commitment security of AES-based authenticated encryption schemes, and the one-wayness of AES-based one-way functions in ZK and MPC protocols. In this work, we introduce single-color initial structures (SCIS) into...
2025/754
Last updated: 2025-05-20
On graph based pseudo quadratic multivariate maps of prescribed degree as instruments of key establishment
Vasyl Ustimenko, Tymoteusz Chojecki
Cryptographic protocols
Let us assume that one of two trusted parties (administrator) manages the information system (IS) and another one (user) is going to use the resources of this IS during the certain time interval. So they need establish secure user’s access password to the IS resources of this system via selected authenticated key exchange protocol. So they need to communicate via insecure communication channel and secretly con-struct a cryptographically strong session key that can serve for the...
On graph based pseudo quadratic multivariate maps of prescribed degree as instruments of key establishment.
Vasyl Ustimenko, Tymoteusz Chojecki
Cryptographic protocols
Let us assume that one of two trusted parties (administrator) manages the information system (IS) and another one (user) is going to use the resources of this IS during the certain time interval. So they need establish secure user’s access password to the IS resources of this system via selected authenticated key exchange protocol. So they need to communicate via insecure communication channel and secretly con-struct a cryptographically strong session key that can serve for the...
Seamless Post-Quantum Transition: Agile and Efficient Encryption for Data-at-Rest
Stephan Krenn, Thomas Lorünser, Sebastian Ramacher, Federico Valbusa
Cryptographic protocols
As quantum computing matures, its impact on traditional cryptographic protocols becomes increasingly critical, especially for data-at-rest scenarios where large data sets remain encrypted for extended periods of time.
This paper addresses the pressing need to transition away from pre-quantum algorithms by presenting an agile cryptosystem that securely and efficiently supports post-quantum Key Encapsulation Mechanisms (KEMs).
The proposed solution is based on combining a CCA-secure KEM with...
Universal Blind and Verifiable Delegated Quantum Computation with Classical Clients
Vicent Esteve Voltes
Cryptographic protocols
Delegation of quantum computation in a trustful way is one of the most fundamental challenges toward the realization of future quantum cloud computing. While considerable progress has been made, no known protocol provides a purely classical client with universal delegated quantum computation while simultaneously ensuring blindness (input privacy), verifiability (soundness), and robustness against quantum noise—a feat that must be achieved under stringent cryptographic assumptions and with...
Post-quantum Cryptographic Analysis of SSH
Benjamin Benčina, Benjamin Dowling, Varun Maram, Keita Xagawa
Cryptographic protocols
The Secure Shell (SSH) protocol is one of the first security protocols on the Internet to upgrade itself to resist attacks against future quantum computers, with the default adoption of the "quantum (otherwise, classically)" secure hybrid key exchange in OpenSSH from April 2022. However, there is a lack of a comprehensive security analysis of this quantum-resistant version of SSH in the literature: related works either focus on the hybrid key exchange in isolation and do not consider...
Intermundium-DL: Assessing the Resilience of Current Schemes to Discrete-Log-Computation Attacks on Public Parameters
Mihir Bellare, Doreen Riepel, Laura Shea
Public-key cryptography
We consider adversaries able to perform a nonzero but small number of discrete logarithm computations, as would be expected with near-term quantum computers. Schemes with public parameters consisting of a few group elements are now at risk; could an adversary knowing the discrete logarithms of these elements go on to easily compromise the security of many users? We study this question for known schemes and find, across them, a perhaps surprising variance in the answers. In a first class are...
Audience Injection Attacks: A New Class of Attacks on Web-Based Authorization and Authentication Standards
Pedram Hosseyni, Ralf Kuesters, Tim Würtele
Cryptographic protocols
We introduce audience injection attacks, a novel class of vulnerabilities that impact widely used Web-based authentication and authorization protocols, including OAuth 2.0, OpenID Connect, FAPI, CIBA, the Device Authorization Grant, and various well-established extensions, such as Pushed Authorization Requests, Token Revocation, Token Introspection, and their numerous combinations.
These protocols underpin services for billions of users across diverse ecosystems worldwide, spanning low-risk...
Making BBS Anonymous Credentials eIDAS 2.0 Compliant
Nicolas Desmoulins, Antoine Dumanois, Seyni Kane, Jacques Traoré
Cryptographic protocols
eIDAS 2.0 (electronic IDentification, Authentication and trust Services) is a very ambitious regulation aimed at equipping European citizens with a personal digital identity wallet (EU Digital Identity Wallet) on a mobile phone that not only needs to achieve a high level of security, but also needs to be available as soon as possible for a large number of citizens and respect their privacy (as per GDPR - General Data Protection Regulation).
In this paper, we introduce the foundations of...
DSM: Decentralized State Machine - The Missing Trust Layer of the Internet
Brandon Ramsay
Cryptographic protocols
The modern internet relies heavily on centralized trust systems controlled by corporations, governments, and intermediaries to manage authentication, identity, and value transfer. These models introduce fundamental vulnerabilities, including censorship, fraud, and systemic insecurity. The Decentralized State Machine (DSM) addresses these issues by introducing a mathematically enforced trust layer that eliminates the need for consensus mechanisms, third-party validators, and centralized...
Universally Composable Relaxed Asymmetric Password-Authenticated Key Exchange
Shuya Hanai, Keisuke Tanaka, Masayuki Tezuka, Yusuke Yoshida
Cryptographic protocols
Password-Authenticated Key Exchange (PAKE) establishes a secure channel between two parties who share a password. Asymmetric PAKE is a variant of PAKE, where one party stores a hash of the password to preserve security under the situation that the party is compromised. The security of PAKE and asymmetric PAKE is often analyzed in the framework of universal composability (UC).
Abdalla et al. (CRYPTO '20) relaxed the UC security of PAKE and showed that the relaxed security still guarantees...
An Optimized Instantiation of Post-Quantum MQTT protocol on 8-bit AVR Sensor Nodes
YoungBeom Kim, Seog Chung Seo
Implementation
Since the selection of the National Institute of Standards and Technology (NIST) Post-Quantum Cryptography (PQC) standardization algorithms, research on integrating PQC into security protocols such as TLS/SSL, IPSec, and DNSSEC has been actively pursued. However, PQC migration for Internet of Things (IoT) communication protocols remains largely unexplored. Embedded devices in IoT environments have limited computational power and memory, making it crucial to optimize PQC algorithms for...
Strong Federated Authentication With Password-based Credential Against Identity Server Corruption
Changsong Jiang, Chunxiang Xu, Guomin Yang, Li Duan, Jing Wang
Cryptographic protocols
We initiate the study of strong federated authentication with password-based credential against identity server corruption (SaPBC). We provide a refined formal security model, which captures all the necessary security properties in registration, authentication, and session key establishment between a user and an application server. The new model with fine-grained information leakage separates the leakage of password-related files and long-term secrets (including passwords and credentials)....
VeriSSO: A Privacy-Preserving Legacy-Compatible Single Sign-On Protocol Using Verifiable Credentials
Ifteher Alom, Sudip Bhujel, Yang Xiao
Applications
Single Sign-On (SSO) is a popular authentication mechanism enabling users to access multiple web services with a single set of credentials. Despite its convenience, SSO faces outstanding privacy challenges. The Identity Provider (IdP) represents a single point of failure and can track users across different Relying Parties (RPs). Multiple colluding RPs may track users through common identity attributes. In response, anonymous credential-based SSO solutions have emerged to offer...
Adaptively Secure Threshold Blind BLS Signatures and Threshold Oblivious PRF
Stanislaw Jarecki, Phillip Nazarian
Cryptographic protocols
We show the first threshold blind signature scheme and threshold Oblivious PRF (OPRF) scheme which remain secure in the presence of an adaptive adversary, who can adaptively decide which parties to corrupt throughout the lifetime of the scheme. Moreover, our adaptively secure schemes preserve the minimal round complexity and add only a small computational overhead over prior solutions that offered security only for a much less realistic static adversary, who must choose the subset of...
An Efficient Sequential Aggregate Signature Scheme with Lazy Verification
Arinjita Paul, Sabyasachi Dutta, Kouichi Sakurai, C. Pandu Rangan
Public-key cryptography
A sequential aggregate signature scheme (SAS) allows multiple potential signers to sequentially aggregate their respective signatures into a single compact signature. Typically, verification of a SAS signatures requires access to all messages and public key pairs utilized in the aggregate generation. However, efficiency is crucial for cryptographic protocols to facilitate their practical implementation. To this end, we propose a sequential aggregate signature scheme with lazy verification...
On Deniable Authentication against Malicious Verifiers
Rune Fiedler, Roman Langrehr
Public-key cryptography
Deniable authentication allows Alice to authenticate a message to Bob, while retaining deniability towards third parties. In particular, not even Bob can convince a third party that Alice authenticated that message. Clearly, in this setting Bob should not be considered trustworthy. Furthermore, deniable authentication is necessary for deniable key exchange, as explicitly desired by Signal and off-the-record (OTR) messaging.
In this work we focus on (publicly verifiable) designated...
Achieving Data Reconstruction Hardness and Efficient Computation in Multiparty Minimax Training
Truong Son Nguyen, Yi Ren, Guangyu Nie, Ni Trieu
Applications
Generative models have achieved remarkable success in a wide range of applications. Training such models using proprietary data from multiple parties has been studied in the realm of federated learning. Yet recent studies showed that reconstruction of authentic training data can be achieved in such settings.
On the other hand, multiparty computation (MPC) guarantees standard data privacy, yet scales poorly for training generative models.
In this paper, we focus on improving...
Privacy and Security of FIDO2 Revisited
Manuel Barbosa, Alexandra Boldyreva, Shan Chen, Kaishuo Cheng, Luís Esquível
Cryptographic protocols
We revisit the privacy and security analyses of FIDO2, a widely deployed standard for passwordless authentication on the Web. We discuss previous works and conclude that each of them has at least one of the following limitations:
(i) impractical trusted setup assumptions,
(ii) security models that are inadequate in light of state of the art of practical attacks,
(iii) not analyzing FIDO2 as a whole, especially for its privacy guarantees.
Our work addresses these gaps and proposes...
Non-interactive Anonymous Tokens with Private Metadata Bit
Foteini Baldimtsi, Lucjan Hanzlik, Quan Nguyen, Aayush Yadav
Cryptographic protocols
Anonymous tokens with private metadata bit (ATPM) have received increased interest as a method for anonymous user authentication while also allowing the issuer to embed trust signals inside the token that are only readable by the authority who holds the secret key. A drawback of all existing ATPM constructions is that they require interaction between the client and the issuer during the issuance process. In this work, we build the first non-interactive anonymous tokens (NIAT) with private...
Exploring How to Authenticate Application Messages in MLS: More Efficient, Post-Quantum, and Anonymous Blocklistable
Keitaro Hashimoto, Shuichi Katsumata, Guillermo Pascual-Perez
Cryptographic protocols
The Message Layer Security (MLS) protocol has recently been standardized by the IETF. MLS is a scalable secure group messaging protocol expected to run more efficiently compared to the Signal protocol at scale, while offering a similar level of strong security. Even though MLS has undergone extensive examination by researchers, the majority of the works have focused on confidentiality.
In this work, we focus on the authenticity of the application messages exchanged in MLS. Currently, MLS...
TreeKEM: A Modular Machine-Checked Symbolic Security Analysis of Group Key Agreement in Messaging Layer Security
Théophile Wallez, Jonathan Protzenko, Karthikeyan Bhargavan
Cryptographic protocols
The Messaging Layer Security (MLS) protocol standard proposes a novel tree-based protocol that enables efficient end-to-end encrypted messaging over large groups with thousands of members. Its functionality can be divided into three components: TreeSync for authenticating and synchronizing group state, TreeKEM for the core group key agreement, and TreeDEM for group message encryption. While previous works have analyzed the security of abstract models of TreeKEM, they do not account for the...
Hybrid Obfuscated Key Exchange and KEMs
Felix Günther, Michael Rosenberg, Douglas Stebila, Shannon Veitch
Cryptographic protocols
Hiding the metadata in Internet protocols serves to protect user privacy, dissuade traffic analysis, and prevent network ossification. Fully encrypted protocols require even the initial key exchange to be obfuscated: a passive observer should be unable to distinguish a protocol execution from an exchange of random bitstrings. Deployed obfuscated key exchanges such as Tor's pluggable transport protocol obfs4 are Diffie–Hellman-based, and rely on the Elligator encoding for obfuscation....
Juicebox Protocol: Distributed Storage and Recovery of Secrets Using Simple PIN Authentication
Nora Trapp, Diego Ongaro
Cryptographic protocols
Existing secret management techniques demand users memorize complex passwords, store convoluted recovery phrases, or place their trust in a specific service or hardware provider. We have designed a novel protocol that combines existing cryptographic techniques to eliminate these complications and reduce user complexity to recalling a short PIN. Our protocol specifically focuses on a distributed approach to secret storage that leverages Oblivious Pseudorandom Functions (OPRFs) and a...
Making Protocol FSU Revocable
Kazuma Wariki, Atsushi Fujioka, Akira Nagai, Kan Yasuda
Cryptographic protocols
This paper examines whether a revocation function can be added to a protocol, protocol FSU, which is an asymmetric pairing variant of a protocol that has been adopted as an international standard, ISO/IEC11770-3. Protocol FSU is an identity-based authenticated-key exchange protocol based on a mathematical problem, an asymmetric gap bilinear Diffie--Hellman (GBDH) problem.
To make protocol FSU revocable, a generic technique is applied, which converts an identity-based encryption scheme to a...
UC-Security of Encrypted Key Exchange: A Tutorial
Jiayu Xu
Cryptographic protocols
Password-Authenticated Key Exchange (PAKE) is a type of key exchange protocols secure against man-in-the-middle adversaries, in the setting where the two parties only agree upon a low-entropy "password" in advance. The first and arguably most well-studied PAKE protocol is Encrypted Key Exchange (EKE) (Bellovin and Marritt, 1992), and the standard security notion for PAKE is in the Universal Composability (UC) framework (Canetti et al., 2005). While the UC-security of EKE has been "folklore"...
Authenticated BitGC for Actively Secure Rate-One 2PC
Hanlin Liu, Xiao Wang, Kang Yang, Yu Yu
Cryptographic protocols
In this paper, we present a constant-round actively secure two-party computation protocol with small communication based on the ring learning with errors (RLWE) assumption with key-dependent message security. Our result builds on the recent BitGC protocol by Liu, Wang, Yang, and Yu (Eurocrypt 2025) with communication of one bit per gate for semi-honest security. First, we achieve a different manner of distributed garbling, where the global correlation is secret-shared among the two parties....
NoIC: PAKE from KEM without Ideal Ciphers
Afonso Arriaga, Manuel Barbosa, Stanislaw Jarecki
Cryptographic protocols
We show a generic compiler from KEM to (Universally Composable) PAKE in the Random Oracle Model (ROM) and without requiring an Ideal Cipher. The compiler is akin to Encrypted Key Exchange (EKE) by Bellovin-Merritt, but following the work of McQuoid et al. it uses only a 2-round Feistel to password-encrypt a KEM public key. The resulting PAKE incurs only insignificant cost overhead over the underlying KEM, and it is a secure UC PAKE if KEM is secure and key-anonymous under the...
Uniformly Most Powerful Tests for Ad Hoc Transactions in Monero
Brandon Goodell, Rigo Salazar, Freeman Slaughter
Cryptographic protocols
We introduce a general, low-cost, low-power statistical test for transactions in transaction protocols with small anonymity set authentication (TPSASAs), such as Monero. The test classifies transactions as ad hoc (spontaneously constructed to spend a deterministically selected key) or self-churned (constructed from a probability distribution very close to that of the default wallet software, and with the same sender and receiver). The test is a uniformly most powerful (UMP) likelihood ratio...
On the Power of Sumcheck in Secure Multiparty Computation
Zhe Li, Chaoping Xing, Yizhou Yao, Chen Yuan
Cryptographic protocols
Lund et al. (JACM 1992) invented the powerful Sumcheck protocol that has been extensively used in complexity theory and in designing concretely efficient (zero-knowledge) arguments. In this work, we systematically study Sumcheck in the context of secure multi-party computation (MPC). Our main result is a new generic framework for lifting semi-honest MPC protocols to maliciously secure ones, with a {\em constant} multiplicative overhead in {\em both} computation and communication, and in the...
Efficient Pseudorandom Correlation Generators for Any Finite Field
Zhe Li, Chaoping Xing, Yizhou Yao, Chen Yuan
Foundations
Correlated randomness lies at the core of efficient modern secure multi-party computation (MPC) protocols. Costs of generating such correlated randomness required for the MPC online phase protocol often constitute a bottleneck in the overall protocol.
A recent paradigm of {\em pseudorandom correlation generator} (PCG) initiated by Boyle et al. (CCS'18, Crypto'19) offers an appealing solution to this issue. In sketch, each party is given a short PCG seed, which can be locally expanded into...
Shadowfax: A Deniability-Preserving AKEM Combiner
Phillip Gajland, Vincent Hwang, Jonas Janneck
Cryptographic protocols
As cryptographic protocols transition to post-quantum security, most adopt hybrid solutions combining pre-quantum and post-quantum assumptions. However, this shift often introduces trade-offs in terms of efficiency, compactness, and in some cases, even security. One such example is deniability, which enables users, such as journalists or activists, to deny authorship of potentially incriminating messages. While deniability was once mainly of theoretical interest, protocols like X3DH, used in...
hax: Verifying Security-Critical Rust Software using Multiple Provers
Karthikeyan Bhargavan, Maxime Buyse, Lucas Franceschino, Lasse Letager Hansen, Franziskus Kiefer, Jonas Schneider-Bensch, Bas Spitters
Implementation
We present hax, a verification toolchain for Rust targeted at security-critical software such as cryptographic libraries, protocol imple- mentations, authentication and authorization mechanisms, and parsing and sanitization code. The key idea behind hax is the pragmatic observation that different verification tools are better at handling different kinds of verification goals. Consequently, hax supports multiple proof backends, including domain-specific security analysis tools like ProVerif...
Doubly Efficient Fuzzy Private Set Intersection for High-dimensional Data with Cosine Similarity
Hyunjung Son, Seunghun Paik, Yunki Kim, Sunpill Kim, Heewon Chung, Jae Hong Seo
Cryptographic protocols
Fuzzy private set intersection (Fuzzy PSI) is a cryptographic protocol for privacy-preserving similarity matching, which is one of the essential operations in various real-world applications such as facial authentication, information retrieval, or recommendation systems. Despite recent advancements in fuzzy PSI protocols, still a huge barrier remains in deploying them for these applications. The main obstacle is the high dimensionality, e.g., from 128 to 512, of data; lots of existing...
Keyed-Verification Anonymous Credentials with Highly Efficient Partial Disclosure
Omid Mirzamohammadi, Jan Bobolz, Mahdi Sedaghat, Emad Heydari Beni, Aysajan Abidin, Dave Singelee, Bart Preneel
Cryptographic protocols
An anonymous credential (AC) system with partial disclosure allows users to prove possession of a credential issued by an issuer while selectively disclosing a subset of their attributes to a verifier in a privacy-preserving manner. In keyed-verification AC (KVAC) systems, the issuer and verifier share a secret key. Existing KVAC schemes rely on computationally expensive zero-knowledge proofs during credential presentation, with the presentation size growing linearly with the number of...
Bundled Authenticated Key Exchange: A Concrete Treatment of (Post-Quantum) Signal's Handshake Protocol
Keitaro Hashimoto, Shuichi Katsumata, Thom Wiggers
Cryptographic protocols
The Signal protocol relies on a special handshake protocol, formerly X3DH and now PQXDH, to set up secure conversations. Prior analyses of these protocols (or proposals for post-quantum alternatives) have all used highly tailored models to the individual protocols and generally made ad-hoc adaptations to "standard" AKE definitions, making the concrete security attained unclear and hard to compare between similar protocols. Indeed, we observe that some natural Signal handshake protocols...
Efficient Authentication Protocols from the Restricted Syndrome Decoding Problem
Thomas Johansson, Mustafa Khairallah, Vu Nguyen
Cryptographic protocols
In this paper, we introduce an oracle version of the Restricted Syndrome Decoding Problem (RSDP) and propose novel authentication protocols based on the hardness of this problem. They follow the basic structure of the HB-family of authentication protocols and later improvements but demonstrate several advantages.
An appropriate choice of multiplicative subgroup and ring structure gives rise to a very efficient hardware implementation compared to other \emph{Learning Parity with Noise} based...
Post-Quantum DNSSEC with Faster TCP Fallbacks
Aditya Singh Rawat, Mahabir Prasad Jhanwar
Cryptographic protocols
In classical DNSSEC, a drop-in replacement with quantum-safe cryptography would increase DNS query resolution times by $\textit{at least}$ a factor of $2\times$. Since a DNS response containing large post-quantum signatures is likely to get marked truncated ($\texttt{TC}$) by a nameserver (resulting in a wasted UDP round-trip), the client (here, the resolver) would have to retry its query over TCP, further incurring a $\textit{minimum}$ of two round-trips due to the three-way TCP...
PQConnect: Automated Post-Quantum End-to-End Tunnels
Daniel J. Bernstein, Tanja Lange, Jonathan Levin, Bo-Yin Yang
Applications
This paper introduces PQConnect, a post-quantum end-to-end tunneling protocol that automatically protects all packets between clients that have installed PQConnect and servers that have installed and configured PQConnect.
Like VPNs, PQConnect does not require any changes to higher-level protocols and application software. PQConnect adds cryptographic protection to unencrypted applications, works in concert with existing pre-quantum applications to add post-quantum protection, and adds a...
Fully Hybrid TLSv1.3 in WolfSSL on Cortex-M4
Mila Anastasova, Reza Azarderakhsh, Mehran Mozaffari Kermani
Cryptographic protocols
To provide safe communication across an unprotected medium such as the internet, network protocols are being established. These protocols employ public key techniques to perform key exchange and authentication. Transport Layer Security (TLS) is a widely used network protocol that enables secure communication between a server and a client. TLS is employed in billions of transactions per second. Contemporary protocols depend on traditional methods that utilize the computational complexity of...
Succinct Homomorphic MACs from Groups and Applications
Yuval Ishai, Hanjun Li, Huijia Lin
Foundations
Homomorphic message authentication codes (HMACs) allow users to authenticate data using a shared secret key, while supporting computation over authenticated data. Given data $(m_1, \ldots, m_n)$ and their tags $(\sigma_1, \ldots, \sigma_n)$, anyone can evaluate a circuit $C$ on the data and tags to produce a succinct tag authenticating the output $C(m_1, \ldots, m_n)$. Importantly, tags remain succinc -- of size polynomial in the security parameter $\lambda$ -- regardless of the size of $C$....
COCO: Coconuts and Oblivious Computations for Orthogonal Authentication
Yamya Reiki
Cryptographic protocols
Authentication often bridges real-world individuals and their virtual public identities, like usernames, user IDs and e-mails, exposing vulnerabilities that threaten user privacy. This research introduces COCO (Coconuts and Oblivious Computations for Orthogonal Authentication), a framework that segregates roles among Verifiers, Authenticators, and Clients to achieve privacy-preserving authentication.
COCO eliminates the need for Authenticators to directly access virtual public identifiers...
Breaking and Provably Restoring Authentication: A Formal Analysis of SPDM 1.2 including Cross-Protocol Attacks
Cas Cremers, Alexander Dax, Aurora Naska
Cryptographic protocols
The SPDM (Security Protocol and Data Model) protocol is a standard under development by the DMTF consortium, and supported by major industry players including Broadcom, Cisco, Dell, Google, HP, IBM, Intel, and NVIDIA. SPDM 1.2 is a complex protocol that aims to provide platform security, for example for communicating hardware components or cloud computing scenarios.
In this work, we provide the first holistic, formal analysis of SPDM 1.2: we model the full protocol flow of SPDM considering...
Anonymous credentials from ECDSA
Matteo Frigo, abhi shelat
Cryptographic protocols
Anonymous digital credentials allow a user to prove possession of an attribute that has been asserted by an identity issuer without revealing any extra information about themselves. For example, a user who has received a digital passport credential can prove their “age is $>18$” without revealing any other attributes such as their name or date of birth.
Despite inherent value for privacy-preserving authentication, anonymous credential schemes have been difficult to deploy at scale. ...
NICE-PAKE: On the Security of KEM-Based PAKE Constructions without Ideal Ciphers
Nouri Alnahawi, Jacob Alperin-Sheriff, Daniel Apon, Gareth T. Davies, Alexander Wiesmaier
Cryptographic protocols
Password Authenticated Key Exchange (PAKE) is a fundamental
cryptographic component that allows two parties to establish a
shared key using only (potentially low-entropy) passwords. The interest
in realizing generic KEM-based PAKEs has increased significantly in the
last few years as part of the global migration effort to quantum-resistant
cryptography. One such PAKE is the CAKE protocol, proposed by Beguinet et al. (ACNS ’23). However, despite its simple design based on
the...
DGMT: A Fully Dynamic Group Signature From Symmetric-key Primitives
Mojtaba Fadavi, Sabyasachi Karati, Aylar Erfanian, Reihaneh Safavi-Naini
Foundations
A group signatures allows a user to sign a message anonymously on behalf of a group and provides accountability by using an opening authority who can ``open'' a signature and reveal the signer's identity. Group signatures have been widely used in privacy-preserving applications including anonymous attestation and anonymous authentication. Fully dynamic group signatures allow new members to join the group and existing members to be revoked if needed. Symmetric-key based group signature...
Universally Composable Server-Supported Signatures for Smartphones
Nikita Snetkov, Jelizaveta Vakarjuk, Peeter Laud
Cryptographic protocols
Smart-ID is an application for signing and authentication provided as a service to residents of Belgium, Estonia, Latvia and Lithuania. Its security relies on multi-prime server-supported RSA, password-authenticated key shares and clone detection mechanism. Unfortunately, the security properties of the underlying protocol have been specified only in ``game-based'' manner. There is no corresponding ideal functionality that the actual protocol is shown to securely realize in the universal...
Universally Composable and Reliable Password Hardening Services
Shaoqiang Wu, Ding Wang
Cryptographic protocols
The password-hardening service (PH) is a crypto service that armors canonical password authentication with an external key against offline password guessing in case the password file is somehow compromised/leaked. The game-based formal treatment of PH was brought by Everspaugh et al. at USENIX Security'15. Their work is followed by efficiency-enhancing PO-COM (CCS'16), security-patching Phoenix (USENIX Security'17), and functionality-refining PW-Hero (SRDS'22). However, the issue of single...
Multi-Holder Anonymous Credentials from BBS Signatures
Andrea Flamini, Eysa Lee, Anna Lysyanskaya
Cryptographic protocols
The eIDAS 2.0 regulation aims to develop interoperable digital identities for European citizens, and it has recently become law. One of its requirements is that credentials be unlinkable. Anonymous credentials (AC) allow holders to prove statements about their identity in a way that does not require to reveal their identity and does not enable linking different usages of the same credential. As a result, they are likely to become the technology that provides digital identity for...
Tightly-Secure Group Key Exchange with Perfect Forward Secrecy
Emanuele Di Giandomenico, Doreen Riepel, Sven Schäge
Public-key cryptography
In this work, we present a new paradigm for constructing Group Authenticated Key Exchange (GAKE). This result is the first tightly secure GAKE scheme in a strong security model that allows maximum exposure attacks (MEX) where the attacker is allowed to either reveal the secret session state or the long-term secret of all communication partners. Moreover, our protocol features the strong and realistic notion of (full) perfect forward secrecy (PFS), that allows the attacker to actively modify...
Attacking Automotive RKE Security: How Smart are your ‘Smart’ Keys?
Ritul Satish, Alfred Daimari, Argha Chakrabarty, Kahaan Shah, Debayan Gupta
Attacks and cryptanalysis
Remote Keyless Entry (RKE) systems are ubiqui-
tous in modern day automobiles, providing convenience for
vehicle owners - occasionally at the cost of security. Most
automobile companies have proprietary implementations of
RKE; these are sometimes built on insecure algorithms and
authentication mechanisms. This paper presents a compre-
hensive study conducted on the RKE systems of multiple
cars from four automobile manufacturers not previously
explored.
Specifically, we analyze the...
Quantum One-Time Protection of any Randomized Algorithm
Sam Gunn, Ramis Movassagh
Foundations
The meteoric rise in power and popularity of machine learning models dependent on valuable training data has reignited a basic tension between the power of running a program locally and the risk of exposing details of that program to the user. At the same time, fundamental properties of quantum states offer new solutions to data and program security that can require strikingly few quantum resources to exploit, and offer advantages outside of mere computational run time. In this work, we...
Advanced Transparency System
Yuxuan Sun, Yuncong Hu, Yu Yu
Applications
In contemporary times, there are many situations where users need to verify that their information is correctly retained by servers. At the same time, servers need to maintain transparency logs. Many algorithms have been designed to address this problem. For example, Certificate Transparency (CT) helps track certificates issued by Certificate Authorities (CAs), while CONIKS aims to provide key transparency for end users. However, these algorithms often suffer from either high append time or...
PriSrv: Privacy-Enhanced and Highly Usable Service Discovery in Wireless Communications
Yang Yang, Robert H. Deng, Guomin Yang, Yingjiu Li, HweeHwa Pang, Minming Huang, Rui Shi, Jian Weng
Cryptographic protocols
Service discovery is essential in wireless communications. However, existing service discovery protocols provide no or very limited privacy protection for service providers and clients, and they often leak sensitive information (e.g., service type, client’s identity and mobility pattern), which leads to various network-based attacks (e.g., spoofing, man-in-the-middle, identification and tracking). In this paper, we propose a private service discovery protocol, called PriSrv, which allows a...
Provable Security Analysis of Butterfly Key Mechanism Protocol in IEEE 1609.2.1 Standard
Alexandra Boldyreva, Virendra Kumar, Jiahao Sun
Cryptographic protocols
The paper provides the first provable security analysis of the Butterfly Key Mechanism (BKM) protocol from IEEE 1609.2.1 standard. The BKM protocol specifies a novel approach for efficiently requesting multiple certificates for use in vehicle-to-everything (V2X) communication. We define the main security goals of BKM, such as vehicle privacy and communication authenticity. We prove that the BKM protocol, with small modifications, meets those security goals. We also propose a way to...
Proteus: A Fully Homomorphic Authenticated Transciphering Protocol
Lars Wolfgang Folkerts, Nektarios Georgios Tsoutsos
Cryptographic protocols
Fully Homomorphic Encryption (FHE) is a powerful technology that allows a cloud server to perform computations directly on ciphertexts. To overcome the overhead of sending and storing large FHE ciphertexts, the concept of FHE transciphering was introduced, allowing symmetric key encrypted ciphertexts to be transformed into FHE ciphertexts by deploying symmetric key decryption homomorphically. However, existing FHE transciphering schemes remain unauthenticated and malleable, allowing...
Maximizing the Utility of Cryptographic Setups: Secure PAKEs, with either functional RO or CRS
Yuting Xiao, Rui Zhang, Hong-Sheng Zhou
Cryptographic protocols
For Password-Based Authenticated Key Exchange (PAKE), an idealized setup such as random oracle (RO) or a trusted setup such as common reference string (CRS) is a must in the universal composability (UC) framework (Canetti, FOCS 2001). Given the potential failure of a CRS or RO setup, it is natural to consider distributing trust among the two setups, resulting a CRS-or-RO-setup (i.e., CoR-setup).
However, the infeasibility highlighted by Katz et al. (PODC 2014) suggested that it is...
Juggernaut: Efficient Crypto-Agnostic Byzantine Agreement
Daniel Collins, Yuval Efron, Jovan Komatovic
Cryptographic protocols
It is well known that a trusted setup allows one to solve the Byzantine agreement problem in the presence of $t<n/2$ corruptions, bypassing the setup-free $t<n/3$ barrier. Alas, the overwhelming majority of protocols in the literature have the caveat that their security crucially hinges on the security of the cryptography and setup, to the point where if the cryptography is broken, even a single corrupted party can violate the security of the protocol. Thus these protocols provide higher...
MatriGear: Accelerating Authenticated Matrix Triple Generation with Scalable Prime Fields via Optimized HE Packing
Hyunho Cha, Intak Hwang, Seonhong Min, Jinyeong Seo, Yongsoo Song
Cryptographic protocols
The SPDZ protocol family is a popular choice for secure multi-party computation (MPC) in a dishonest majority setting with active adversaries. Over the past decade, a series of studies have focused on improving its offline phase, where special additive shares called authenticated triples are generated. However, to accommodate recent demands for matrix operations in secure machine learning and big integer arithmetic in distributed RSA key generation, updates to the offline phase are...
Threshold PAKE with Security against Compromise of all Servers
Yanqi Gu, Stanislaw Jarecki, Pawel Kedzior, Phillip Nazarian, Jiayu Xu
Cryptographic protocols
We revisit the notion of threshold Password-Authenticated Key Exchange (tPAKE), and we extend it to augmented tPAKE (atPAKE), which protects password information even in the case all servers are compromised, except for allowing an (inevitable) offline dictionary attack. Compared to prior notions of tPAKE this is analogous to replacing symmetric PAKE, where the server stores the user's password, with an augmented (or asymmetric) PAKE, like OPAQUE [JKX18], where the server stores a password...
Eva: Efficient Privacy-Preserving Proof of Authenticity for Lossily Encoded Videos
Chengru Zhang, Xiao Yang, David Oswald, Mark Ryan, Philipp Jovanovic
Applications
With the increasing usage of fake videos in misinformation campaigns, proving the provenance of an edited video becomes critical, in particular, without revealing the original footage. We formalize the notion and security model of proofs of video authenticity and give the first cryptographic video authentication protocol Eva, which supports lossy codecs and arbitrary edits and is proven secure under well-established cryptographic assumptions. Compared to previous cryptographic methods for...
Design issues of ``an anonymous authentication and key agreement protocol in smart living''
Zhengjun Cao, Lihua Liu
Attacks and cryptanalysis
The Li et al.'s scheme [Computer Communications, 186 (2022), 110-120)] uses XOR operation to realize the private transmission of sensitive information, under the assumption that if only one parameter in the expression $ a= b\oplus c $ is known, an adversary cannot retrieve the other two. The assumption neglects that the operands $b$ and $c$ must be of the same bit-length, which leads to the exposure of a substring in the longer operand. The scheme wrongly treats timestamps as random...
Efficient Asymmetric PAKE Compiler from KEM and AE
You Lyu, Shengli Liu, Shuai Han
Cryptographic protocols
Password Authenticated Key Exchange (PAKE) allows two parties to establish a secure session key with a shared low-entropy password pw. Asymmetric PAKE (aPAKE) extends PAKE in the client-server setting, and the server only stores a password file instead of the plain password so as to provide additional security guarantee when the server is compromised.
In this paper, we propose a novel generic compiler from PAKE to aPAKE in the Universal Composable (UC) framework by making use of Key...
Password-Protected Key Retrieval with(out) HSM Protection
Sebastian Faller, Tobias Handirk, Julia Hesse, Máté Horváth, Anja Lehmann
Cryptographic protocols
Password-protected key retrieval (PPKR) enables users to store and retrieve high-entropy keys from a server securely. The process is bootstrapped from a human-memorizable password only, addressing the challenge of how end-users can manage cryptographic key material. The core security requirement is protection against a corrupt server, which should not be able to learn the key or offline- attack it through the password protection. PPKR is deployed at a large scale with the WhatsApp Backup...
EUCLEAK
Thomas Roche
Attacks and cryptanalysis
Secure elements are small microcontrollers whose main purpose is to generate/store secrets and then execute cryptographic operations. They undergo the highest level of security evaluations that exists (Common Criteria) and are often considered inviolable, even in the worst-case attack scenarios. Hence, complex secure systems build their security upon them.
FIDO hardware tokens are strong authentication factors to sign in to applications (any web service supporting FIDO); they often embed...
Coral: Maliciously Secure Computation Framework for Packed and Mixed Circuits
Zhicong Huang, Wen-jie Lu, Yuchen Wang, Cheng Hong, Tao Wei, WenGuang Chen
Cryptographic protocols
Achieving malicious security with high efficiency in dishonest-majority secure multiparty computation is a formidable challenge. The milestone works SPDZ and TinyOT have spawn a large family of protocols in this direction. For boolean circuits, state-of-the-art works (Cascudo et. al, TCC 2020 and Escudero et. al, CRYPTO 2022) have proposed schemes based on reverse multiplication-friendly embedding (RMFE) to reduce the amortized cost. However, these protocols are theoretically described and...
High-Throughput GPU Implementation of Dilithium Post-Quantum Digital Signature
Shiyu Shen, Hao Yang, Wangchen Dai, Hong Zhang, Zhe Liu, Yunlei Zhao
Implementation
Digital signatures are fundamental building blocks in various protocols to provide integrity and authenticity. The development of the quantum computing has raised concerns about the security guarantees afforded by classical signature schemes. CRYSTALS-Dilithium is an efficient post-quantum digital signature scheme based on lattice cryptography and has been selected as the primary algorithm for standardization by the National Institute of Standards and Technology. In this work, we present a...
Privacy-Preserving in Cloud Networks: An Efficient, Revocable and Authenticated Encrypted Search Scheme
Yibo Cao, Shiyuan Xu, Gang Xu, Xiu-Bo Chen, Yuling Chen, Siu-Ming Yiu
Applications
With the widespread development of cloud networks, performing searches on encrypted data (without decryption) has become a critical issue. Public key authenticated encryption with keyword search (PAEKS) allows for the retrieval of encrypted data while resisting insider keyword guessing attacks (IKGAs). Most PAEKS schemes do not support access control in multi-receiver models. To address this limitation, attribute-based encryption has been introduced. However, the access privileges for the...
Password-authenticated Cryptography from Consumable Tokens
Ghada Almashaqbeh
Cryptographic protocols
Passwords are widely adopted for user authentication in practice, which led to the question of whether we can bootstrap a strongly-secure setting based on them. Historically, this has been extensively studied for key exchange; bootstrap from a low-entropy password to a high entropy key securing the communication. Other instances include digital lockers, signatures, secret sharing, and encryption.
Motivated by a recent work on consumable tokens (Almashaqbeh et al., Eurocrypt 2022), we...
Generation of Authenticated Secret-Shared Scaled Unit Vectors for Beaver Triples
Vincent Rieder
Cryptographic protocols
For secure multi-party computation in the line of the secret-sharing based
SPDZ protocol, actively secure multiplications consume correlated randomness
in the form of authenticated Beaver triples, which need to be generated in advance.
Although it is a well-studied problem, the generation of Beaver triples is
still a bottleneck in practice. In the two-party setting, the best solution with low
communication overhead is the protocol by Boyle et al. (Crypto 2020), which
is derived from...
A note on ``a novel authentication protocol for IoT-enabled devices''
Zhengjun Cao, Lihua Liu
Attacks and cryptanalysis
We show that the authentication protocol [IEEE Internet Things J., 2023, 10(1), 867-876] is not correctly specified, because the server cannot complete its computations. To revise, the embedded device needs to compute an extra point multiplication over the underlying elliptic curve. We also find the protocol cannot provide anonymity, not as claimed. It can only provide pseudonymity.
Cryptanalysis of two post-quantum authenticated key agreement protocols
Mehdi Abri, Hamid Mala
Attacks and cryptanalysis
As the use of the internet and digital devices has grown rapidly, keeping digital communications secure has become very important. Authenticated Key Agreement (AKA) protocols play a vital role in securing digital communications. These protocols enable the communicating parties to mutually authenticate and securely establish a shared secret key. The emergence of quantum computers makes many existing AKA protocols vulnerable to their immense computational power. Consequently, designing new...
Shared-Custodial Password-Authenticated Deterministic Wallets
Poulami Das, Andreas Erwig, Sebastian Faust
Cryptographic protocols
Cryptographic wallets are an essential tool in Blockchain networks to ensure the secure storage and maintenance of an user's cryptographic keys. Broadly, wallets can be divided into three categories, namely custodial, non-custodial, and shared-custodial wallets. The first two are centralized solutions, i.e., the wallet is operated by a single entity, which inherently introduces a single point of failure. Shared-custodial wallets, on the other hand, are maintained by two independent parties,...
Post-Quantum Ready Key Agreement for Aviation
Marcel Tiepelt, Christian Martin, Nils Maeurer
Cryptographic protocols
Transitioning from classically to quantum secure key agreement protocols may require to exchange fundamental components, for example, exchanging Diffie-Hellman-like key exchange with a key encapsulation mechanism (KEM). Accordingly, the corresponding security proof can no longer rely on the Diffie-Hellman assumption, thus invalidating the security guarantees. As a consequence, the security properties have to be re-proven under a KEM-based security notion.
We initiate the study of the...
Obfuscated Key Exchange
Felix Günther, Douglas Stebila, Shannon Veitch
Cryptographic protocols
Censorship circumvention tools enable clients to access endpoints in a network despite the presence of a censor. Censors use a variety of techniques to identify content they wish to block, including filtering traffic patterns that are characteristic of proxy or circumvention protocols and actively probing potential proxy servers. Circumvention practitioners have developed fully encrypted protocols (FEPs), intended to have traffic that appears indistinguishable from random. A FEP is typically...
Password-authenticated Key Exchange and Applications
Kristian Gjøsteen
Cryptographic protocols
We analyse a two password-authenticated key exchange protocols, a variant of CPace and a protocol related to the well-known SRP protocol. Our security results are tight. The first result gives us some information about trade-offs for design choices in CPace. The second result provides information about the security of SRP.
Our analysis is done in a new game-based security definition for password-authenticated key exchange. Our definition accomodates arbitrary password sampling...
SACfe: Secure Access Control in Functional Encryption with Unbounded Data
Uddipana Dowerah, Subhranil Dutta, Frank Hartmann, Aikaterini Mitrokotsa, Sayantan Mukherjee, Tapas Pal
Cryptographic protocols
Privacy is a major concern in large-scale digital applications, such as cloud-computing, machine learning services, and access control. Users want to protect not only their plain data but also their associated attributes (e.g., age, location, etc). Functional encryption (FE) is a cryptographic tool that allows fine-grained access control over encrypted data. However, existing FE fall short as they are either inefficient and far from reality or they leak sensitive user-specific...
The Committing Security of MACs with Applications to Generic Composition
Ritam Bhaumik, Bishwajit Chakraborty, Wonseok Choi, Avijit Dutta, Jérôme Govinden, Yaobin Shen
Secret-key cryptography
Message Authentication Codes (MACs) are ubiquitous primitives deployed in multiple flavors through standards such as HMAC, CMAC, GMAC, LightMAC, and many others. Its versatility makes it an essential building block in applications necessitating message authentication and integrity checks, in authentication protocols, authenticated encryption schemes, or as a pseudorandom or key derivation function. Its usage in this variety of settings makes it susceptible to a broad range of attack...
Lattice-based Fault Attacks against ECMQV
Weiqiong Cao, Hua Chen, Jingyi Feng, Linmin Fan, Wenling Wu
Attacks and cryptanalysis
ECMQV is a standardized key agreement protocol based on ECC with an additional implicit signature authentication. In this paper we investigate the vulnerability of ECMQV against fault attacks and propose two efficient lattice-based fault attacks. In our attacks, by inducing a storage fault to the ECC parameter $a$ before the execution of ECMQV, we can construct two kinds of weak curves and successfully pass the public-key validation step in the protocol. Then, by solving ECDLP and using a...
erforming privacy-preserving queries, particularly anonymous authentication, against large-scale datasets presents critical tradeoffs between security, latency, scalability. Existing cryptographic solutions often impose linear computation or communication overheads. This paper introduces a novel, efficient protocol for secure anonymous authentication, uniquely combining matrix partitioning via hash prefixes with Oblivious Pseudorandom Functions in a three-server semi-honest model....
Secure messaging protocols allow users to communicate asynchronously over untrusted channels with strong guarantees of privacy, authenticity, forward secrecy, and post-compromise security. However, traditional security analyses of these protocols assume complete trust in the hardware and software of honest participants, overlooking a significant class of real-world threats known as subversion attacks. These attacks alter cryptographic algorithms to compromise security, by exfiltrating...
This paper introduces ZK-NR, a modular cryptographic protocol designed to ensure privacy-preserving non-repudiation in the co-production of digital public services. By integrating Merkle commitments, zero-knowledge proofs (STARKs), threshold BLS signatures, and post-quantum Dilithium authentication, ZK-NR enables the creation of secure, verifiable, and auditable evidence across decentralized infrastructures. Unlike traditional digital signatures or blockchain-based logs, ZK-NR provides...
A common issue with using secure computation in practice is that its security does not place any restrictions on what an adversary can use as input in the protocol. In this work, we focus on the practically-motivated setting of (two-message, labeled) private set intersection (PSI), and advocate for a clean and versatile solution to this problem: PSI on authenticated inputs. Our central contributions are summarized as follows. - We formulate a novel definition of PSI on authenticated...
Blind signatures are fundamental cryptographic primitives enabling privacy-preserving authentication and have seen renewed interest in the post-quantum literature. Existing efficient constructions predominantly rely on Fischlin’s generic paradigm instantiated over lattice assumptions, while blinding techniques for sigma-protocol-based blind signatures remain sparse beyond lattices. Moreover, achieving provable concurrent security under polynomially many sessions has been a longstanding...
The Internet of Things (IoT) is composed of interconnected devices that exchange data over a network, enabling applications in healthcare, transportation, and smart environments. As IoT ecosystems expand, ensuring security and privacy remains a critical challenge. Many IoT devices rely on wireless networks for data transmission, making them vulnerable to eavesdropping, tracking, and tampering. This highlights the need for robust authentication mechanisms. To address these concerns,...
Vehicle-to-grid (V2G) refers to the bidirectional communication and energy flows that allow renewable energy sources to supply supplementary electrical services between electric cars (EVs) and the power grid. Additionally, V2G lowers environmental pollution and energy issues while providing efficient charging services. A PUF-based, reliable, anonymous authentication and key establishment scheme for V2G networks was recently presented by Sungjin Yu et al. In this paper, we show that the Yu et...
In the Social Internet of Vehicles (SIoV), effective data sharing is essential for applications including road safety, traffic management, and situational awareness. However, the decentralized and open nature of SIoV presents significant challenges in simultaneously ensuring data integrity, user privacy, and system accountability. This paper presents a protocol for secure and location-accurate traffic data sharing that fully preserves the anonymity and privacy of participating witnesses. The...
The Signal protocol is the most widely deployed end-to-end-encrypted messaging protocol. Its initial handshake protocol X3DH allows parties to asynchronously derive a shared session key without the need to be online simultaneously, while providing implicit authentication, forward secrecy, and a form of offline deniability. The X3DH protocol has been extensively studied in the cryptographic literature and is acclaimed for its strong "maximum-exposure" security guarantees, hedging against...
Byzantine Fault Tolerance (BFT) Consensus protocols with trusted hardware assistance have been extensively explored for their improved resilience to tolerate more faulty processes. Nonetheless, the potential of trust hardware has been scarcely investigated in leaderless BFT protocols. RedBelly is assumed to be the first blockchain network whose consensus is based on a truly leaderless BFT algorithm. This paper proposes a trusted hardware-assisted leaderless BFT consensus protocol by offering...
As generative models continue to evolve, verifying the authenticity, provenance, and integrity of digital media has become increasingly critical—particularly for domains like journalism, digital art, and scientific documentation. In this work, we present a decentralized verifiable media ecosystem for managing, verifying, and transacting authentic digital media using zero-knowledge proofs (ZKPs). Building on VIMz (Dziembowski et al., PETS'25), we extend the framework in three key...
Secure and trustworthy electronic voting requires more than correctness and censorship resistance, it must also ensure voter privacy, vote confidentiality, and protection against coercion. Prior work attempt to address these challenges using heavyweight cryptographic primitives such as homomorphic encryption, time-lock puzzles, or multi-party computation. These approaches often involve complex computations, depend on trusted parties, and typically do not scale well. We propose a lightweight,...
We present a highly efficient authenticated group key exchange protocol, TEAKEX, using only symmetric key primitives. Our protocol provides proven strong security, including forward secrecy, post-compromise security, and post-quantum security. For online applications we claim that TEAKEX is much simpler and more efficient than currently available alternatives. As part of our construction we also give a new abstract security definition for delayed authentication and describe its instantiation...
A Password-Authenticated Key Exchange (PAKE) protocol allows two parties to jointly establish a cryptographic key, where the only information shared in advance is a low-entropy password. The first efficient PAKE protocol whose security does not rely on the random oracle model is the one by Katz, Ostrovsky and Yung (KOY, EUROCRYPT 2001). Unfortunately, the KOY protocol has only been proven secure in the game-based setting, and it is unclear whether KOY is secure in the stronger Universal...
Symmetric-key authenticated key establishment (AKE) protocols are particularly well suited in resource constraint environments such as internet of things (IoT) devices. Moreover, they often rely on better understood assumptions than asymmetric ones. In this paper, we review the security model for symmetric-key AKE protocols. We show why several existing models allow trivial attacks while they do not protect against some non-trivial ones. We fix these issues with our new security...
A conventional Authenticated Key Exchange (AKE) protocol consumes fresh random coins from the local random source. However, recent studies of bad randomness expose the vulnerability of some AKE protocols under small subgroup attacks when the random coins are manipulated or being repeated. It is important to ensure the bad randomness of one random source will not affect the security of the AKE protocol as a whole. Thus, we introduce the notion of remote randomness by introducing...
The Signal Protocol, underpinning secure messaging for billions, faces the challenge of migrating to a post-quantum world while preserving critical properties like asynchrony and deniability. While Signal’s PQXDH key exchange protocol addresses post-quantum confidentiality, full migration of the X3DH protocol remains elusive. Relying on a split KEM (K-Waay, USENIX ’24) offers a promising migration path, but it has so far suffered from size limitations compared to concurrent works...
Recent advancements in maliciously secure garbling have significantly improved the efficiency of constant-round multi-party computation. Research in the field has primarily focused on reducing communication complexity through row reduction techniques and improvements to the preprocessing phase with the use of simpler correlations. In this work, we present two contributions to reduce the communication complexity of state of the art multi-party garbling with an arbitrary number of...
Recently, there has been a growing interest in anonymous credentials (ACs) as they can mitigate the risk of personal data being processed by untrusted actors without consent and beyond the user's control. Furthermore, due to the privacy-by-design paradigm of ACs, they can prove possession of personal attributes, such as an authenticated government document containing sensitive personal information, while preserving the privacy of the individual by not actually revealing the data. Typically,...
Passports, identity cards and travel visas are examples of machine readable travel documents (MRTDs) or eMRTDs for their electronic variants. The security of the data exchanged between these documents and a reader is secured with a standardized password authenticated key exchange (PAKE) protocol known as PACE. A new world-wide protocol migration is expected with the arrival of post-quantum cryptography (PQC) standards. In this paper, we focus on the impact of this migration on constrained...
Many user-centric applications face a common privacy problem: the need to collect, store, and analyze sensitive user data. Examples include check-in/check-out based payment systems for public transportation, charging/discharging electric vehicle batteries in smart grids, coalition loyalty programs, behavior-based car insurance, and more. We propose and evaluate a generic solution to this problem. More specifically, we provide a formal framework integrating privacy-preserving data collection,...
AES has cemented its position as the primary symmetric-key primitive for a wide range of cryptographic applications, which motivates the analysis on the concrete security of AES in practical instantiations, for instance, the collision resistance of AES-based hashing, the key commitment security of AES-based authenticated encryption schemes, and the one-wayness of AES-based one-way functions in ZK and MPC protocols. In this work, we introduce single-color initial structures (SCIS) into...
Let us assume that one of two trusted parties (administrator) manages the information system (IS) and another one (user) is going to use the resources of this IS during the certain time interval. So they need establish secure user’s access password to the IS resources of this system via selected authenticated key exchange protocol. So they need to communicate via insecure communication channel and secretly con-struct a cryptographically strong session key that can serve for the...
Let us assume that one of two trusted parties (administrator) manages the information system (IS) and another one (user) is going to use the resources of this IS during the certain time interval. So they need establish secure user’s access password to the IS resources of this system via selected authenticated key exchange protocol. So they need to communicate via insecure communication channel and secretly con-struct a cryptographically strong session key that can serve for the...
As quantum computing matures, its impact on traditional cryptographic protocols becomes increasingly critical, especially for data-at-rest scenarios where large data sets remain encrypted for extended periods of time. This paper addresses the pressing need to transition away from pre-quantum algorithms by presenting an agile cryptosystem that securely and efficiently supports post-quantum Key Encapsulation Mechanisms (KEMs). The proposed solution is based on combining a CCA-secure KEM with...
Delegation of quantum computation in a trustful way is one of the most fundamental challenges toward the realization of future quantum cloud computing. While considerable progress has been made, no known protocol provides a purely classical client with universal delegated quantum computation while simultaneously ensuring blindness (input privacy), verifiability (soundness), and robustness against quantum noise—a feat that must be achieved under stringent cryptographic assumptions and with...
The Secure Shell (SSH) protocol is one of the first security protocols on the Internet to upgrade itself to resist attacks against future quantum computers, with the default adoption of the "quantum (otherwise, classically)" secure hybrid key exchange in OpenSSH from April 2022. However, there is a lack of a comprehensive security analysis of this quantum-resistant version of SSH in the literature: related works either focus on the hybrid key exchange in isolation and do not consider...
We consider adversaries able to perform a nonzero but small number of discrete logarithm computations, as would be expected with near-term quantum computers. Schemes with public parameters consisting of a few group elements are now at risk; could an adversary knowing the discrete logarithms of these elements go on to easily compromise the security of many users? We study this question for known schemes and find, across them, a perhaps surprising variance in the answers. In a first class are...
We introduce audience injection attacks, a novel class of vulnerabilities that impact widely used Web-based authentication and authorization protocols, including OAuth 2.0, OpenID Connect, FAPI, CIBA, the Device Authorization Grant, and various well-established extensions, such as Pushed Authorization Requests, Token Revocation, Token Introspection, and their numerous combinations. These protocols underpin services for billions of users across diverse ecosystems worldwide, spanning low-risk...
eIDAS 2.0 (electronic IDentification, Authentication and trust Services) is a very ambitious regulation aimed at equipping European citizens with a personal digital identity wallet (EU Digital Identity Wallet) on a mobile phone that not only needs to achieve a high level of security, but also needs to be available as soon as possible for a large number of citizens and respect their privacy (as per GDPR - General Data Protection Regulation). In this paper, we introduce the foundations of...
The modern internet relies heavily on centralized trust systems controlled by corporations, governments, and intermediaries to manage authentication, identity, and value transfer. These models introduce fundamental vulnerabilities, including censorship, fraud, and systemic insecurity. The Decentralized State Machine (DSM) addresses these issues by introducing a mathematically enforced trust layer that eliminates the need for consensus mechanisms, third-party validators, and centralized...
Password-Authenticated Key Exchange (PAKE) establishes a secure channel between two parties who share a password. Asymmetric PAKE is a variant of PAKE, where one party stores a hash of the password to preserve security under the situation that the party is compromised. The security of PAKE and asymmetric PAKE is often analyzed in the framework of universal composability (UC). Abdalla et al. (CRYPTO '20) relaxed the UC security of PAKE and showed that the relaxed security still guarantees...
Since the selection of the National Institute of Standards and Technology (NIST) Post-Quantum Cryptography (PQC) standardization algorithms, research on integrating PQC into security protocols such as TLS/SSL, IPSec, and DNSSEC has been actively pursued. However, PQC migration for Internet of Things (IoT) communication protocols remains largely unexplored. Embedded devices in IoT environments have limited computational power and memory, making it crucial to optimize PQC algorithms for...
We initiate the study of strong federated authentication with password-based credential against identity server corruption (SaPBC). We provide a refined formal security model, which captures all the necessary security properties in registration, authentication, and session key establishment between a user and an application server. The new model with fine-grained information leakage separates the leakage of password-related files and long-term secrets (including passwords and credentials)....
Single Sign-On (SSO) is a popular authentication mechanism enabling users to access multiple web services with a single set of credentials. Despite its convenience, SSO faces outstanding privacy challenges. The Identity Provider (IdP) represents a single point of failure and can track users across different Relying Parties (RPs). Multiple colluding RPs may track users through common identity attributes. In response, anonymous credential-based SSO solutions have emerged to offer...
We show the first threshold blind signature scheme and threshold Oblivious PRF (OPRF) scheme which remain secure in the presence of an adaptive adversary, who can adaptively decide which parties to corrupt throughout the lifetime of the scheme. Moreover, our adaptively secure schemes preserve the minimal round complexity and add only a small computational overhead over prior solutions that offered security only for a much less realistic static adversary, who must choose the subset of...
A sequential aggregate signature scheme (SAS) allows multiple potential signers to sequentially aggregate their respective signatures into a single compact signature. Typically, verification of a SAS signatures requires access to all messages and public key pairs utilized in the aggregate generation. However, efficiency is crucial for cryptographic protocols to facilitate their practical implementation. To this end, we propose a sequential aggregate signature scheme with lazy verification...
Deniable authentication allows Alice to authenticate a message to Bob, while retaining deniability towards third parties. In particular, not even Bob can convince a third party that Alice authenticated that message. Clearly, in this setting Bob should not be considered trustworthy. Furthermore, deniable authentication is necessary for deniable key exchange, as explicitly desired by Signal and off-the-record (OTR) messaging. In this work we focus on (publicly verifiable) designated...
Generative models have achieved remarkable success in a wide range of applications. Training such models using proprietary data from multiple parties has been studied in the realm of federated learning. Yet recent studies showed that reconstruction of authentic training data can be achieved in such settings. On the other hand, multiparty computation (MPC) guarantees standard data privacy, yet scales poorly for training generative models. In this paper, we focus on improving...
We revisit the privacy and security analyses of FIDO2, a widely deployed standard for passwordless authentication on the Web. We discuss previous works and conclude that each of them has at least one of the following limitations: (i) impractical trusted setup assumptions, (ii) security models that are inadequate in light of state of the art of practical attacks, (iii) not analyzing FIDO2 as a whole, especially for its privacy guarantees. Our work addresses these gaps and proposes...
Anonymous tokens with private metadata bit (ATPM) have received increased interest as a method for anonymous user authentication while also allowing the issuer to embed trust signals inside the token that are only readable by the authority who holds the secret key. A drawback of all existing ATPM constructions is that they require interaction between the client and the issuer during the issuance process. In this work, we build the first non-interactive anonymous tokens (NIAT) with private...
The Message Layer Security (MLS) protocol has recently been standardized by the IETF. MLS is a scalable secure group messaging protocol expected to run more efficiently compared to the Signal protocol at scale, while offering a similar level of strong security. Even though MLS has undergone extensive examination by researchers, the majority of the works have focused on confidentiality. In this work, we focus on the authenticity of the application messages exchanged in MLS. Currently, MLS...
The Messaging Layer Security (MLS) protocol standard proposes a novel tree-based protocol that enables efficient end-to-end encrypted messaging over large groups with thousands of members. Its functionality can be divided into three components: TreeSync for authenticating and synchronizing group state, TreeKEM for the core group key agreement, and TreeDEM for group message encryption. While previous works have analyzed the security of abstract models of TreeKEM, they do not account for the...
Hiding the metadata in Internet protocols serves to protect user privacy, dissuade traffic analysis, and prevent network ossification. Fully encrypted protocols require even the initial key exchange to be obfuscated: a passive observer should be unable to distinguish a protocol execution from an exchange of random bitstrings. Deployed obfuscated key exchanges such as Tor's pluggable transport protocol obfs4 are Diffie–Hellman-based, and rely on the Elligator encoding for obfuscation....
Existing secret management techniques demand users memorize complex passwords, store convoluted recovery phrases, or place their trust in a specific service or hardware provider. We have designed a novel protocol that combines existing cryptographic techniques to eliminate these complications and reduce user complexity to recalling a short PIN. Our protocol specifically focuses on a distributed approach to secret storage that leverages Oblivious Pseudorandom Functions (OPRFs) and a...
This paper examines whether a revocation function can be added to a protocol, protocol FSU, which is an asymmetric pairing variant of a protocol that has been adopted as an international standard, ISO/IEC11770-3. Protocol FSU is an identity-based authenticated-key exchange protocol based on a mathematical problem, an asymmetric gap bilinear Diffie--Hellman (GBDH) problem. To make protocol FSU revocable, a generic technique is applied, which converts an identity-based encryption scheme to a...
Password-Authenticated Key Exchange (PAKE) is a type of key exchange protocols secure against man-in-the-middle adversaries, in the setting where the two parties only agree upon a low-entropy "password" in advance. The first and arguably most well-studied PAKE protocol is Encrypted Key Exchange (EKE) (Bellovin and Marritt, 1992), and the standard security notion for PAKE is in the Universal Composability (UC) framework (Canetti et al., 2005). While the UC-security of EKE has been "folklore"...
In this paper, we present a constant-round actively secure two-party computation protocol with small communication based on the ring learning with errors (RLWE) assumption with key-dependent message security. Our result builds on the recent BitGC protocol by Liu, Wang, Yang, and Yu (Eurocrypt 2025) with communication of one bit per gate for semi-honest security. First, we achieve a different manner of distributed garbling, where the global correlation is secret-shared among the two parties....
We show a generic compiler from KEM to (Universally Composable) PAKE in the Random Oracle Model (ROM) and without requiring an Ideal Cipher. The compiler is akin to Encrypted Key Exchange (EKE) by Bellovin-Merritt, but following the work of McQuoid et al. it uses only a 2-round Feistel to password-encrypt a KEM public key. The resulting PAKE incurs only insignificant cost overhead over the underlying KEM, and it is a secure UC PAKE if KEM is secure and key-anonymous under the...
We introduce a general, low-cost, low-power statistical test for transactions in transaction protocols with small anonymity set authentication (TPSASAs), such as Monero. The test classifies transactions as ad hoc (spontaneously constructed to spend a deterministically selected key) or self-churned (constructed from a probability distribution very close to that of the default wallet software, and with the same sender and receiver). The test is a uniformly most powerful (UMP) likelihood ratio...
Lund et al. (JACM 1992) invented the powerful Sumcheck protocol that has been extensively used in complexity theory and in designing concretely efficient (zero-knowledge) arguments. In this work, we systematically study Sumcheck in the context of secure multi-party computation (MPC). Our main result is a new generic framework for lifting semi-honest MPC protocols to maliciously secure ones, with a {\em constant} multiplicative overhead in {\em both} computation and communication, and in the...
Correlated randomness lies at the core of efficient modern secure multi-party computation (MPC) protocols. Costs of generating such correlated randomness required for the MPC online phase protocol often constitute a bottleneck in the overall protocol. A recent paradigm of {\em pseudorandom correlation generator} (PCG) initiated by Boyle et al. (CCS'18, Crypto'19) offers an appealing solution to this issue. In sketch, each party is given a short PCG seed, which can be locally expanded into...
As cryptographic protocols transition to post-quantum security, most adopt hybrid solutions combining pre-quantum and post-quantum assumptions. However, this shift often introduces trade-offs in terms of efficiency, compactness, and in some cases, even security. One such example is deniability, which enables users, such as journalists or activists, to deny authorship of potentially incriminating messages. While deniability was once mainly of theoretical interest, protocols like X3DH, used in...
We present hax, a verification toolchain for Rust targeted at security-critical software such as cryptographic libraries, protocol imple- mentations, authentication and authorization mechanisms, and parsing and sanitization code. The key idea behind hax is the pragmatic observation that different verification tools are better at handling different kinds of verification goals. Consequently, hax supports multiple proof backends, including domain-specific security analysis tools like ProVerif...
Fuzzy private set intersection (Fuzzy PSI) is a cryptographic protocol for privacy-preserving similarity matching, which is one of the essential operations in various real-world applications such as facial authentication, information retrieval, or recommendation systems. Despite recent advancements in fuzzy PSI protocols, still a huge barrier remains in deploying them for these applications. The main obstacle is the high dimensionality, e.g., from 128 to 512, of data; lots of existing...
An anonymous credential (AC) system with partial disclosure allows users to prove possession of a credential issued by an issuer while selectively disclosing a subset of their attributes to a verifier in a privacy-preserving manner. In keyed-verification AC (KVAC) systems, the issuer and verifier share a secret key. Existing KVAC schemes rely on computationally expensive zero-knowledge proofs during credential presentation, with the presentation size growing linearly with the number of...
The Signal protocol relies on a special handshake protocol, formerly X3DH and now PQXDH, to set up secure conversations. Prior analyses of these protocols (or proposals for post-quantum alternatives) have all used highly tailored models to the individual protocols and generally made ad-hoc adaptations to "standard" AKE definitions, making the concrete security attained unclear and hard to compare between similar protocols. Indeed, we observe that some natural Signal handshake protocols...
In this paper, we introduce an oracle version of the Restricted Syndrome Decoding Problem (RSDP) and propose novel authentication protocols based on the hardness of this problem. They follow the basic structure of the HB-family of authentication protocols and later improvements but demonstrate several advantages. An appropriate choice of multiplicative subgroup and ring structure gives rise to a very efficient hardware implementation compared to other \emph{Learning Parity with Noise} based...
In classical DNSSEC, a drop-in replacement with quantum-safe cryptography would increase DNS query resolution times by $\textit{at least}$ a factor of $2\times$. Since a DNS response containing large post-quantum signatures is likely to get marked truncated ($\texttt{TC}$) by a nameserver (resulting in a wasted UDP round-trip), the client (here, the resolver) would have to retry its query over TCP, further incurring a $\textit{minimum}$ of two round-trips due to the three-way TCP...
This paper introduces PQConnect, a post-quantum end-to-end tunneling protocol that automatically protects all packets between clients that have installed PQConnect and servers that have installed and configured PQConnect. Like VPNs, PQConnect does not require any changes to higher-level protocols and application software. PQConnect adds cryptographic protection to unencrypted applications, works in concert with existing pre-quantum applications to add post-quantum protection, and adds a...
To provide safe communication across an unprotected medium such as the internet, network protocols are being established. These protocols employ public key techniques to perform key exchange and authentication. Transport Layer Security (TLS) is a widely used network protocol that enables secure communication between a server and a client. TLS is employed in billions of transactions per second. Contemporary protocols depend on traditional methods that utilize the computational complexity of...
Homomorphic message authentication codes (HMACs) allow users to authenticate data using a shared secret key, while supporting computation over authenticated data. Given data $(m_1, \ldots, m_n)$ and their tags $(\sigma_1, \ldots, \sigma_n)$, anyone can evaluate a circuit $C$ on the data and tags to produce a succinct tag authenticating the output $C(m_1, \ldots, m_n)$. Importantly, tags remain succinc -- of size polynomial in the security parameter $\lambda$ -- regardless of the size of $C$....
Authentication often bridges real-world individuals and their virtual public identities, like usernames, user IDs and e-mails, exposing vulnerabilities that threaten user privacy. This research introduces COCO (Coconuts and Oblivious Computations for Orthogonal Authentication), a framework that segregates roles among Verifiers, Authenticators, and Clients to achieve privacy-preserving authentication. COCO eliminates the need for Authenticators to directly access virtual public identifiers...
The SPDM (Security Protocol and Data Model) protocol is a standard under development by the DMTF consortium, and supported by major industry players including Broadcom, Cisco, Dell, Google, HP, IBM, Intel, and NVIDIA. SPDM 1.2 is a complex protocol that aims to provide platform security, for example for communicating hardware components or cloud computing scenarios. In this work, we provide the first holistic, formal analysis of SPDM 1.2: we model the full protocol flow of SPDM considering...
Anonymous digital credentials allow a user to prove possession of an attribute that has been asserted by an identity issuer without revealing any extra information about themselves. For example, a user who has received a digital passport credential can prove their “age is $>18$” without revealing any other attributes such as their name or date of birth. Despite inherent value for privacy-preserving authentication, anonymous credential schemes have been difficult to deploy at scale. ...
Password Authenticated Key Exchange (PAKE) is a fundamental cryptographic component that allows two parties to establish a shared key using only (potentially low-entropy) passwords. The interest in realizing generic KEM-based PAKEs has increased significantly in the last few years as part of the global migration effort to quantum-resistant cryptography. One such PAKE is the CAKE protocol, proposed by Beguinet et al. (ACNS ’23). However, despite its simple design based on the...
A group signatures allows a user to sign a message anonymously on behalf of a group and provides accountability by using an opening authority who can ``open'' a signature and reveal the signer's identity. Group signatures have been widely used in privacy-preserving applications including anonymous attestation and anonymous authentication. Fully dynamic group signatures allow new members to join the group and existing members to be revoked if needed. Symmetric-key based group signature...
Smart-ID is an application for signing and authentication provided as a service to residents of Belgium, Estonia, Latvia and Lithuania. Its security relies on multi-prime server-supported RSA, password-authenticated key shares and clone detection mechanism. Unfortunately, the security properties of the underlying protocol have been specified only in ``game-based'' manner. There is no corresponding ideal functionality that the actual protocol is shown to securely realize in the universal...
The password-hardening service (PH) is a crypto service that armors canonical password authentication with an external key against offline password guessing in case the password file is somehow compromised/leaked. The game-based formal treatment of PH was brought by Everspaugh et al. at USENIX Security'15. Their work is followed by efficiency-enhancing PO-COM (CCS'16), security-patching Phoenix (USENIX Security'17), and functionality-refining PW-Hero (SRDS'22). However, the issue of single...
The eIDAS 2.0 regulation aims to develop interoperable digital identities for European citizens, and it has recently become law. One of its requirements is that credentials be unlinkable. Anonymous credentials (AC) allow holders to prove statements about their identity in a way that does not require to reveal their identity and does not enable linking different usages of the same credential. As a result, they are likely to become the technology that provides digital identity for...
In this work, we present a new paradigm for constructing Group Authenticated Key Exchange (GAKE). This result is the first tightly secure GAKE scheme in a strong security model that allows maximum exposure attacks (MEX) where the attacker is allowed to either reveal the secret session state or the long-term secret of all communication partners. Moreover, our protocol features the strong and realistic notion of (full) perfect forward secrecy (PFS), that allows the attacker to actively modify...
Remote Keyless Entry (RKE) systems are ubiqui- tous in modern day automobiles, providing convenience for vehicle owners - occasionally at the cost of security. Most automobile companies have proprietary implementations of RKE; these are sometimes built on insecure algorithms and authentication mechanisms. This paper presents a compre- hensive study conducted on the RKE systems of multiple cars from four automobile manufacturers not previously explored. Specifically, we analyze the...
The meteoric rise in power and popularity of machine learning models dependent on valuable training data has reignited a basic tension between the power of running a program locally and the risk of exposing details of that program to the user. At the same time, fundamental properties of quantum states offer new solutions to data and program security that can require strikingly few quantum resources to exploit, and offer advantages outside of mere computational run time. In this work, we...
In contemporary times, there are many situations where users need to verify that their information is correctly retained by servers. At the same time, servers need to maintain transparency logs. Many algorithms have been designed to address this problem. For example, Certificate Transparency (CT) helps track certificates issued by Certificate Authorities (CAs), while CONIKS aims to provide key transparency for end users. However, these algorithms often suffer from either high append time or...
Service discovery is essential in wireless communications. However, existing service discovery protocols provide no or very limited privacy protection for service providers and clients, and they often leak sensitive information (e.g., service type, client’s identity and mobility pattern), which leads to various network-based attacks (e.g., spoofing, man-in-the-middle, identification and tracking). In this paper, we propose a private service discovery protocol, called PriSrv, which allows a...
The paper provides the first provable security analysis of the Butterfly Key Mechanism (BKM) protocol from IEEE 1609.2.1 standard. The BKM protocol specifies a novel approach for efficiently requesting multiple certificates for use in vehicle-to-everything (V2X) communication. We define the main security goals of BKM, such as vehicle privacy and communication authenticity. We prove that the BKM protocol, with small modifications, meets those security goals. We also propose a way to...
Fully Homomorphic Encryption (FHE) is a powerful technology that allows a cloud server to perform computations directly on ciphertexts. To overcome the overhead of sending and storing large FHE ciphertexts, the concept of FHE transciphering was introduced, allowing symmetric key encrypted ciphertexts to be transformed into FHE ciphertexts by deploying symmetric key decryption homomorphically. However, existing FHE transciphering schemes remain unauthenticated and malleable, allowing...
For Password-Based Authenticated Key Exchange (PAKE), an idealized setup such as random oracle (RO) or a trusted setup such as common reference string (CRS) is a must in the universal composability (UC) framework (Canetti, FOCS 2001). Given the potential failure of a CRS or RO setup, it is natural to consider distributing trust among the two setups, resulting a CRS-or-RO-setup (i.e., CoR-setup). However, the infeasibility highlighted by Katz et al. (PODC 2014) suggested that it is...
It is well known that a trusted setup allows one to solve the Byzantine agreement problem in the presence of $t<n/2$ corruptions, bypassing the setup-free $t<n/3$ barrier. Alas, the overwhelming majority of protocols in the literature have the caveat that their security crucially hinges on the security of the cryptography and setup, to the point where if the cryptography is broken, even a single corrupted party can violate the security of the protocol. Thus these protocols provide higher...
The SPDZ protocol family is a popular choice for secure multi-party computation (MPC) in a dishonest majority setting with active adversaries. Over the past decade, a series of studies have focused on improving its offline phase, where special additive shares called authenticated triples are generated. However, to accommodate recent demands for matrix operations in secure machine learning and big integer arithmetic in distributed RSA key generation, updates to the offline phase are...
We revisit the notion of threshold Password-Authenticated Key Exchange (tPAKE), and we extend it to augmented tPAKE (atPAKE), which protects password information even in the case all servers are compromised, except for allowing an (inevitable) offline dictionary attack. Compared to prior notions of tPAKE this is analogous to replacing symmetric PAKE, where the server stores the user's password, with an augmented (or asymmetric) PAKE, like OPAQUE [JKX18], where the server stores a password...
With the increasing usage of fake videos in misinformation campaigns, proving the provenance of an edited video becomes critical, in particular, without revealing the original footage. We formalize the notion and security model of proofs of video authenticity and give the first cryptographic video authentication protocol Eva, which supports lossy codecs and arbitrary edits and is proven secure under well-established cryptographic assumptions. Compared to previous cryptographic methods for...
The Li et al.'s scheme [Computer Communications, 186 (2022), 110-120)] uses XOR operation to realize the private transmission of sensitive information, under the assumption that if only one parameter in the expression $ a= b\oplus c $ is known, an adversary cannot retrieve the other two. The assumption neglects that the operands $b$ and $c$ must be of the same bit-length, which leads to the exposure of a substring in the longer operand. The scheme wrongly treats timestamps as random...
Password Authenticated Key Exchange (PAKE) allows two parties to establish a secure session key with a shared low-entropy password pw. Asymmetric PAKE (aPAKE) extends PAKE in the client-server setting, and the server only stores a password file instead of the plain password so as to provide additional security guarantee when the server is compromised. In this paper, we propose a novel generic compiler from PAKE to aPAKE in the Universal Composable (UC) framework by making use of Key...
Password-protected key retrieval (PPKR) enables users to store and retrieve high-entropy keys from a server securely. The process is bootstrapped from a human-memorizable password only, addressing the challenge of how end-users can manage cryptographic key material. The core security requirement is protection against a corrupt server, which should not be able to learn the key or offline- attack it through the password protection. PPKR is deployed at a large scale with the WhatsApp Backup...
Secure elements are small microcontrollers whose main purpose is to generate/store secrets and then execute cryptographic operations. They undergo the highest level of security evaluations that exists (Common Criteria) and are often considered inviolable, even in the worst-case attack scenarios. Hence, complex secure systems build their security upon them. FIDO hardware tokens are strong authentication factors to sign in to applications (any web service supporting FIDO); they often embed...
Achieving malicious security with high efficiency in dishonest-majority secure multiparty computation is a formidable challenge. The milestone works SPDZ and TinyOT have spawn a large family of protocols in this direction. For boolean circuits, state-of-the-art works (Cascudo et. al, TCC 2020 and Escudero et. al, CRYPTO 2022) have proposed schemes based on reverse multiplication-friendly embedding (RMFE) to reduce the amortized cost. However, these protocols are theoretically described and...
Digital signatures are fundamental building blocks in various protocols to provide integrity and authenticity. The development of the quantum computing has raised concerns about the security guarantees afforded by classical signature schemes. CRYSTALS-Dilithium is an efficient post-quantum digital signature scheme based on lattice cryptography and has been selected as the primary algorithm for standardization by the National Institute of Standards and Technology. In this work, we present a...
With the widespread development of cloud networks, performing searches on encrypted data (without decryption) has become a critical issue. Public key authenticated encryption with keyword search (PAEKS) allows for the retrieval of encrypted data while resisting insider keyword guessing attacks (IKGAs). Most PAEKS schemes do not support access control in multi-receiver models. To address this limitation, attribute-based encryption has been introduced. However, the access privileges for the...
Passwords are widely adopted for user authentication in practice, which led to the question of whether we can bootstrap a strongly-secure setting based on them. Historically, this has been extensively studied for key exchange; bootstrap from a low-entropy password to a high entropy key securing the communication. Other instances include digital lockers, signatures, secret sharing, and encryption. Motivated by a recent work on consumable tokens (Almashaqbeh et al., Eurocrypt 2022), we...
For secure multi-party computation in the line of the secret-sharing based SPDZ protocol, actively secure multiplications consume correlated randomness in the form of authenticated Beaver triples, which need to be generated in advance. Although it is a well-studied problem, the generation of Beaver triples is still a bottleneck in practice. In the two-party setting, the best solution with low communication overhead is the protocol by Boyle et al. (Crypto 2020), which is derived from...
We show that the authentication protocol [IEEE Internet Things J., 2023, 10(1), 867-876] is not correctly specified, because the server cannot complete its computations. To revise, the embedded device needs to compute an extra point multiplication over the underlying elliptic curve. We also find the protocol cannot provide anonymity, not as claimed. It can only provide pseudonymity.
As the use of the internet and digital devices has grown rapidly, keeping digital communications secure has become very important. Authenticated Key Agreement (AKA) protocols play a vital role in securing digital communications. These protocols enable the communicating parties to mutually authenticate and securely establish a shared secret key. The emergence of quantum computers makes many existing AKA protocols vulnerable to their immense computational power. Consequently, designing new...
Cryptographic wallets are an essential tool in Blockchain networks to ensure the secure storage and maintenance of an user's cryptographic keys. Broadly, wallets can be divided into three categories, namely custodial, non-custodial, and shared-custodial wallets. The first two are centralized solutions, i.e., the wallet is operated by a single entity, which inherently introduces a single point of failure. Shared-custodial wallets, on the other hand, are maintained by two independent parties,...
Transitioning from classically to quantum secure key agreement protocols may require to exchange fundamental components, for example, exchanging Diffie-Hellman-like key exchange with a key encapsulation mechanism (KEM). Accordingly, the corresponding security proof can no longer rely on the Diffie-Hellman assumption, thus invalidating the security guarantees. As a consequence, the security properties have to be re-proven under a KEM-based security notion. We initiate the study of the...
Censorship circumvention tools enable clients to access endpoints in a network despite the presence of a censor. Censors use a variety of techniques to identify content they wish to block, including filtering traffic patterns that are characteristic of proxy or circumvention protocols and actively probing potential proxy servers. Circumvention practitioners have developed fully encrypted protocols (FEPs), intended to have traffic that appears indistinguishable from random. A FEP is typically...
We analyse a two password-authenticated key exchange protocols, a variant of CPace and a protocol related to the well-known SRP protocol. Our security results are tight. The first result gives us some information about trade-offs for design choices in CPace. The second result provides information about the security of SRP. Our analysis is done in a new game-based security definition for password-authenticated key exchange. Our definition accomodates arbitrary password sampling...
Privacy is a major concern in large-scale digital applications, such as cloud-computing, machine learning services, and access control. Users want to protect not only their plain data but also their associated attributes (e.g., age, location, etc). Functional encryption (FE) is a cryptographic tool that allows fine-grained access control over encrypted data. However, existing FE fall short as they are either inefficient and far from reality or they leak sensitive user-specific...
Message Authentication Codes (MACs) are ubiquitous primitives deployed in multiple flavors through standards such as HMAC, CMAC, GMAC, LightMAC, and many others. Its versatility makes it an essential building block in applications necessitating message authentication and integrity checks, in authentication protocols, authenticated encryption schemes, or as a pseudorandom or key derivation function. Its usage in this variety of settings makes it susceptible to a broad range of attack...
ECMQV is a standardized key agreement protocol based on ECC with an additional implicit signature authentication. In this paper we investigate the vulnerability of ECMQV against fault attacks and propose two efficient lattice-based fault attacks. In our attacks, by inducing a storage fault to the ECC parameter $a$ before the execution of ECMQV, we can construct two kinds of weak curves and successfully pass the public-key validation step in the protocol. Then, by solving ECDLP and using a...
