83 results sorted by ID
Mild Asymmetric Message Franking: Illegal-Messages-Only and Retrospective Content Moderation
Zhengan Huang, Junzuo Lai, Gongxian Zeng, Jian Weng
Public-key cryptography
Many messaging platforms have integrated end-to-end (E2E) encryption into their services. This widespread adoption of E2E encryption has triggered a technical tension between user privacy and illegal content moderation. The existing solutions either support only unframeability or deniability, or they are prone to abuse (the moderator can perform content moderation for all messages, whether illegal or not), or they lack mechanisms for retrospective content moderation.
To address the above...
Stateful Communication with Malicious Parties
Chen-Da Liu-Zhang, Christopher Portmann, Guilherme Rito
Foundations
Cryptography's most common use is secure communication---e.g. Alice can use encryption to hide the contents of the messages she sends to Bob (confidentiality) and can use signatures to assure Bob she sent these messages (authenticity). While one typically considers stateless security guarantees---for example a channel that Alice can use to send messages securely to Bob---one can also consider stateful ones---e.g. an interactive conversation between Alice, Bob and their friends where...
Ring Signatures for Deniable AKEM: Gandalf's Fellowship
Phillip Gajland, Jonas Janneck, Eike Kiltz
Public-key cryptography
Ring signatures, a cryptographic primitive introduced by Rivest, Shamir and Tauman (ASIACRYPT 2001), offer signer anonymity within dynamically formed user groups. Recent advancements have focused on lattice-based constructions to improve efficiency, particularly for large signing rings. However, current state-of-the-art solutions suffer from significant overhead, especially for smaller rings.
In this work, we present a novel NTRU-based ring signature scheme, Gandalf, tailored towards...
A Deniability Analysis of Signal's Initial Handshake PQXDH
Rune Fiedler, Christian Janson
Cryptographic protocols
Many use messaging apps such as Signal to exercise their right to private communication. To cope with the advent of quantum computing, Signal employs a new initial handshake protocol called PQXDH for post-quantum confidentiality, yet keeps guarantees of authenticity and deniability classical. Compared to its predecessor X3DH, PQXDH includes a KEM encapsulation and a signature on the ephemeral key. In this work we show that PQXDH does not meet the same deniability guarantees as X3DH due to...
A Deniably Authenticated Searchable Public Key Encryption Scheme in Mobile Electronic Mail System
Shuhan Zeng, Yongjian Liao, Chuanhao Zhou, Jinlin He, Hongwei Wang
Public-key cryptography
Confidentiality and authentication are two main security goals in secure electronic mail (e-mail). Furthermore, deniability is also a significant security property for some e-mail applications to protect the privacy of the sender. Although searchable encryption solves the keyword searching problem in a secure e-mail system, it also breaks the deniability of the system. Because the adversary can obtain the information of the data sender and data user from the trapdoor as well as ciphertext...
Non-Binding (Designated Verifier) Signature
Ehsan Ebrahimi
Cryptographic protocols
We argue that there are some scenarios in which
plausible deniability might be desired for a digital signature
scheme. For instance, the non-repudiation property of conventional
signature schemes is problematic in designing an Instant
Messaging system (WPES 2004). In this paper, we formally
define a non-binding signature scheme in which the Signer
is able to disavow her own signature if she wants, but, the
Verifier is not able to dispute a signature generated by the
Signer. That is,...
K-Waay: Fast and Deniable Post-Quantum X3DH without Ring Signatures
Daniel Collins, Loïs Huguenin-Dumittan, Ngoc Khanh Nguyen, Nicolas Rolin, Serge Vaudenay
Cryptographic protocols
The Signal protocol and its X3DH key exchange core are regularly used by billions of people in applications like WhatsApp but are unfortunately not quantum-secure. Thus, designing an efficient and post-quantum secure X3DH alternative is paramount. Notably, X3DH supports asynchronicity, as parties can immediately derive keys after uploading them to a central server, and deniability, allowing parties to plausibly deny having completed key exchange. To satisfy these constraints, existing...
On The Practical Advantage of Committing Challenges in Zero-Knowledge Protocols
David Naccache, Ofer Yifrach-Stav
Cryptographic protocols
The Fiat-Shamir transform is a classical technique for turning any zero-knowledge $\Sigma$-protocol into a signature scheme.
In essence, the idea underlying this transform is that deriving the challenge from the digest of the commitment suppresses simulatability and hence provides non-interactive proofs of interaction.
It follows from that observation that if one wishes to preserve deniability the challenge size (per round) must be kept low. For instance in the original Fiat-Shamir...
NOTRY: deniable messaging with retroactive avowal
Faxing Wang, Shaanan Cohney, Riad Wahby, Joseph Bonneau
Cryptographic protocols
Modern secure messaging protocols typically aim to provide deniability. Achieving this requires that convincing cryptographic transcripts can be forged without the involvement of genuine users. In this work, we observe that parties may wish to revoke deniability and avow a conversation after it has taken place. We propose a new protocol called Not-on-the-Record-Yet (NOTRY) which enables users to prove a prior conversation transcript is genuine. As a key building block we propose avowable...
Shufflecake: Plausible Deniability for Multiple Hidden Filesystems on Linux
Elia Anzuoni, Tommaso Gagliardoni
Applications
We present Shufflecake, a new plausible deniability design to hide the existence of encrypted data on a storage medium making it very difficult for an adversary to prove the existence of such data. Shufflecake can be considered a ``spiritual successor'' of tools such as TrueCrypt and VeraCrypt, but vastly improved: it works natively on Linux, it supports any filesystem of choice, and can manage multiple volumes per device, so to make deniability of the existence of hidden partitions really...
Deniable Cryptosystems: Simpler Constructions and Achieving Leakage Resilience
Zhiyuan An, Haibo Tian, Chao Chen, Fangguo Zhang
Public-key cryptography
Deniable encryption (Canetti et al. CRYPTO ’97) is an intriguing primitive, which provides security guarantee against coercion by allowing a sender to convincingly open the ciphertext into a fake message. Despite the notable result by Sahai and Waters STOC ’14 and other efforts in functionality extension, all the deniable public key encryption (DPKE) schemes suffer from intolerable overhead due to the heavy building blocks, e.g., translucent sets or indistinguishability obfuscation. Besides,...
Real-World Deniability in Messaging
Daniel Collins, Simone Colombo, Loïs Huguenin-Dumittan
Applications
This work explores real-world deniability in messaging. We propose a formal model that considers the entire messaging system to analyze deniability in practice. Applying this model to the Signal application and DKIM-protected email, we demonstrate that these systems do not offer practical deniability guarantees. Additionally, we analyze 140 court cases in Switzerland that use conversations on messaging applications as evidence and find that none consider deniability, providing evidence that...
Anamorphic Encryption, Revisited
Fabio Banfi, Konstantin Gegier, Martin Hirt, Ueli Maurer, Guilherme Rito
Public-key cryptography
An anamorphic encryption scheme allows two parties who share a so-called double key to embed covert messages in ciphertexts of an established PKE scheme. This protects against a dictator that can force the receiver to reveal the secret keys for the PKE scheme, but who is oblivious about the existence of the double key. We identify two limitations of the original model by Persiano, Phan, and Yung (EUROCRYPT 2022). First, in their definition a double key can only be generated once, together...
Deniable Authentication when Signing Keys Leak
Suvradip Chakraborty, Dennis Hofheinz, Ueli Maurer, Guilherme Rito
Public-key cryptography
Deniable Authentication is a highly desirable property for secure messaging protocols: it allows a sender Alice to authentically transmit messages to a designated receiver Bob in such a way that only Bob gets convinced that Alice indeed sent these messages. In particular, it guarantees that even if Bob tries to convince a (non-designated) party Judy that Alice sent some message, and even if Bob gives Judy his own secret key, Judy will not be convinced: as far as Judy knows, Bob could be...
Complete Knowledge: Preventing Encumbrance of Cryptographic Secrets
Mahimna Kelkar, Kushal Babel, Philip Daian, James Austgen, Vitalik Buterin, Ari Juels
Most cryptographic protocols model a player’s knowledge of secrets in a simple way. Informally, the player knows a secret in the sense that she can directly furnish it as a (private) input to a protocol, e.g., to digitally sign a message.
The growing availability of Trusted Execution Environments (TEEs) and secure multiparty computation, however, undermines this model of knowledge. Such tools can encumber a secret sk and permit a chosen player to access sk conditionally, without actually...
DSKE: Digital Signature with Key Extraction
Zhipeng Wang, Orestis Alpos, Alireza Kavousi, Sze Yiu Chau, Duc V. Le, Christian Cachin
Cryptographic protocols
This work introduces DSKE, digital signatures with key extraction. In a DSKE scheme, the private key can be extracted if more than a threshold of signatures on different messages are ever created while, within the threshold, each signature continues to authenticate the signed message. We give a formal definition of DSKE, as well as two provably secure constructions, one from hash-based digital signatures and one from polynomial commitments.
We demonstrate that DSKE is useful for...
Secure Messaging with Strong Compromise Resilience, Temporal Privacy, and Immediate Decryption
Cas Cremers, Mang Zhao
Cryptographic protocols
Recent years have seen many advances in designing secure messaging protocols, aiming at provably strong security properties in theory or high efficiency for real-world practical deployment. However, important trade-off areas of the design space inbetween these elements have not yet been explored.
In this work we design the first provably secure protocol that at the same time achieves (i) strong resilience against finegrained compromise, (ii) temporal privacy, and (iii) immediate...
Subverting Deniability
Marcel Armour, Elizabeth A. Quaglia
Attacks and cryptanalysis
Deniable public-key encryption (DPKE) is a cryptographic primitive that allows the sender of an encrypted message to later claim that they sent a different message.
DPKE's threat model assumes powerful adversaries who can coerce users to reveal plaintexts; it is thus reasonable to consider other advanced capabilities, such as the ability to subvert algorithms in a so-called Algorithm Substitution Attack (ASA). An ASA replaces a trusted algorithm with a subverted version that undermines...
A tale of two models: formal verification of KEMTLS via Tamarin
Sofía Celi, Jonathan Hoyland, Douglas Stebila, Thom Wiggers
Public-key cryptography
KEMTLS is a proposal for changing the TLS handshake to authenticate the handshake using long-term key encapsulation mechanism keys instead of signatures, motivated by trade-offs in the characteristics of post-quantum algorithms. Prior proofs of security of KEMTLS and its variant KEMTLS-PDK have been hand-written proofs in the reductionist model under computational assumptions. In this paper, we present computer-verified symbolic analyses of KEMTLS and KEMTLS-PDK using two distinct Tamarin...
Time-Deniable Signatures
Gabrielle Beck, Arka Rai Choudhuri, Matthew Green, Abhishek Jain, Pratyush Ranjan Tiwari
Public-key cryptography
In this work we propose time-deniable signatures (TDS), a new primitive that facilitates deniable authentication in protocols such as DKIM-signed email. As with traditional signatures, TDS provide strong authenticity for message content, at least for a sender-chosen period of time. Once this time period has elapsed, however, time-deniable signatures can be forged by any party who obtains a signature. This forgery property ensures that signatures serve a useful authentication purpose for a...
How to Avoid Repetitions in Lattice-based Deniable Zero-Knowledge Proofs
Xavier Arnal, Abraham Cano, Tamara Finogina, Javier Herranz
Cryptographic protocols
Interactive zero-knowledge systems are a very important cryptographic primitive, used in many applications, especially when deniability (also known as non-transferability) is desired. In the lattice-based setting, the currently most efficient interactive zero-knowledge systems employ the technique of rejection sampling, which implies that the interaction does not always finish correctly in the first execution; the whole interaction must be re-run until abort does not happen.
While...
Hecate: Abuse Reporting in Secure Messengers with Sealed Sender
Rawane Issa, Nicolas Alhaddad, Mayank Varia
Applications
End-to-end encryption provides strong privacy protections to billions of people, but it also complicates efforts to moderate content that can seriously harm people. To address this concern, Tyagi et al. [CRYPTO 2019] introduced the concept of asymmetric message franking (AMF), which allows people to report abusive content to a moderator, while otherwise retaining end-to-end privacy by default and even compatibility with anonymous communication systems like Signal’s sealed sender.
In this...
SoK: Plausibly Deniable Storage
Chen Chen, Xiao Liang, Bogdan Carbunar, Radu Sion
Applications
Data privacy is critical in instilling trust and empowering the societal pacts of modern technology-driven democracies. Unfortunately, it is under continuous attack by overreaching or outright oppressive governments, including some of the world's oldest democracies. Increasingly-intrusive anti-encryption laws severely limit the ability of standard encryption to protect privacy. New defense mechanisms are needed.
Plausible deniability (PD) is a powerful property, enabling users to hide the...
Simulation-Based Bi-Selective Opening Security for Public Key Encryption
Junzuo Lai, Rupeng Yang, Zhengan Huang, Jian Weng
Public-key cryptography
Selective opening attacks (SOA) (for public-key encryption, PKE) concern such a multi-user scenario, where an adversary adaptively corrupts some fraction of the users to break into a subset of honestly created ciphertexts, and tries to learn the information on the messages of some unopened (but potentially related) ciphertexts. Until now, the notion of selective opening attacks is only considered in two settings: sender selective opening (SSO), where part of senders are corrupted and...
Do you feel a chill? Using PIR against chilling effects for censorship-resistant publishing
Miti Mazmudar, Stan Gurtler, Ian Goldberg
Applications
Peer-to-peer distributed hash tables (DHTs) rely on volunteers to contribute their computational resources, such as disk space and bandwidth. In order to incentivize these node operators of privacy-preserving DHTs, it is important to prevent exposing them to the data that is stored on the DHT and/or queried for. Vasserman et al.'s CROPS aimed at providing plausible deniability to server nodes by encrypting stored content. However, node operators are still exposed to the contents of queries....
Post-Quantum Signal Key Agreement with SIDH
Samuel Dobson, Steven D. Galbraith
Cryptographic protocols
In the effort to transition cryptographic primitives and protocols to quantum-resistant alternatives, an interesting and useful challenge is found in the Signal protocol. The initial key agreement component of this protocol, called X3DH, has so far proved more subtle to replace - in part due to the unclear security model and properties the original protocol is designed for. This paper defines a formal security model for the original signal protocol, in the context of the standard eCK and CK+...
Post-quantum Asynchronous Deniable Key Exchange and the Signal Handshake
Jacqueline Brendel, Rune Fiedler, Felix Günther, Christian Janson, Douglas Stebila
Cryptographic protocols
The key exchange protocol that establishes initial shared secrets in the handshake of the Signal end-to-end encrypted messaging protocol has several important characteristics: (1) it runs asynchronously (without both parties needing to be simultaneously online), (2) it provides implicit mutual authentication while retaining deniability (transcripts cannot be used to prove either party participated in the protocol), and (3) it retains security even if some keys are compromised (forward...
On the Cryptographic Deniability of the Signal Protocol
Nihal Vatandas, Rosario Gennaro, Bertrand Ithurburn, Hugo Krawczyk
Cryptographic protocols
Offline deniability is the ability to a-posteriori deny having participated in a particular communication session. This property has been widely assumed for the Signal messaging application, yet no formal proof has appeared in the literature. In this paper, we present what we believe is the first formal study of the offline deniability of the Signal protocol. Our analysis shows that building a deniability proof for Signal is non-trivial and requires strong assumptions on the underlying...
An Efficient and Generic Construction for Signal's Handshake (X3DH): Post-Quantum, State Leakage Secure, and Deniable
Keitaro Hashimoto, Shuichi Katsumata, Kris Kwiatkowski, Thomas Prest
Cryptographic protocols
The Signal protocol is a secure instant messaging protocol that underlies the security of numerous applications such as WhatsApp, Skype, Facebook Messenger among many others. The Signal protocol consists of two sub-protocols known as the X3DH protocol and the double ratchet protocol, where the latter has recently gained much attention. For instance, Alwen, Coretti, and Dodis (Eurocrypt'19) provided a concrete security model along with a generic construction based on simple building blocks...
Deniable Fully Homomorphic Encryption from LWE
Shweta Agrawal, Shafi Goldwasser, Saleet Mossel
Public-key cryptography
We define and construct Deniable Fully Homomorphic Encryption based on the Learning With Errors (LWE) polynomial hardness assumption. Deniable FHE enables storing encrypted data in the cloud to be processed securely without decryption, maintaining deniability of the encrypted data, as well the prevention of vote-buying in electronic voting schemes where encrypted votes can be tallied without decryption.
Our constructions achieve compactness independently of the level of deniability- both...
Towards Multiparty Computation Withstanding Coercion of All Parties
Ran Canetti, Oxana Poburinnaya
Cryptographic protocols
Incoercible multi-party computation (Canetti-Gennaro ’96) allows parties to engage in secure computation with the additional guarantee that the public transcript of the computation cannot be used by a coercive outsider to verify representations made by the parties regarding their inputs, outputs, and local random choices. That is, it is guaranteed that the only deductions regarding the truthfulness of such representations, made by an outsider who has witnessed the communication among...
A discretization attack
Daniel J. Bernstein
Applications
This paper presents an attack against common procedures for comparing the size-security tradeoffs of proposed cryptosystems. The attack begins with size-security tradeoff data, and then manipulates the presentation of the data in a way that favors a proposal selected by the attacker, while maintaining plausible deniability for the attacker.
As concrete examples, this paper shows two manipulated comparisons of size-security tradeoffs of lattice-based encryption proposals submitted to the...
vault1317/signal-dakez: An authenticated key exchange protocol with a public key concealing and a participation deniability designed for secure messaging
Richard B. Riddick
Cryptographic protocols
A deniable authenticated key exchange can establish a secure communication channel while leaving no cryptographic evidence of communication. Some well-designed protocol today, even in the case of betrayal by some participants and disclosure of long-term key materials, cannot leave any cryptographic evidence. However, this is no longer enough: If “Big data” technology is used to analyse data fetched from pivotal nodes, it’s not difficult to register your identity through your long-term public...
Epochal Signatures for Deniable Group Chats
Andreas Hülsing, Fiona Johanna Weber
Cryptographic protocols
We introduce formal definitions for deniability in group
chats by extending a pre-existing model that did not have
this property. We then introduce “epochal signatures” as
an almost drop-in replacement for signatures, which can
be used to make certain undeniable group-chats deniable
by just performing that replacement. Following that we
provide a practical epochal signature scheme and prove
its security.
Stronger Security and Constructions of Multi-Designated Verifier Signatures
Ivan Damgård, Helene Haagh, Rebekah Mercer, Anca Nițulescu, Claudio Orlandi, Sophia Yakoubov
Cryptographic protocols
Off-the-Record (OTR) messaging is a two-party message authentication protocol that also provides plausible deniability: there is no record that can later convince a third party what messages were actually sent. To extend OTR to group messaging we need to consider issues that are not present in the 2-party case. In group OTR (as in two-party OTR), the sender should be able to authenticate (or sign) his messages so that group members can verify who sent a message (that is, signatures should be...
BioID: a Privacy-Friendly Identity Document
Fatih Balli, F. Betül Durak, Serge Vaudenay
Cryptographic protocols
We design a suite of protocols so that a small tamper-resistant device can be used as a biometric identity document which can be scanned by authorized terminals. We target both strongly secure identification and strong privacy. Unlike biometric passports, our protocols leak no digital evidence and are essentially deniable. Besides, getting the identity information from the device requires going through access control. Access control can follow either a strong PKI-based path or a weak...
Asymmetric Message Franking: Content Moderation for Metadata-Private End-to-End Encryption
Nirvan Tyagi, Paul Grubbs, Julia Len, Ian Miers, Thomas Ristenpart
Public-key cryptography
Content moderation is crucial for stopping abuse and harassment via messaging on online platforms. Existing moderation mechanisms, such as message franking, require platform providers to see user identifiers on encrypted traffic. These mechanisms cannot be used in messaging systems in which users can hide their identities, such as Signal. The key technical challenge preventing moderation is in simultaneously achieving cryptographic accountability while preserving deniability. In this work,...
KeyForge: Mitigating Email Breaches with Forward-Forgeable Signatures
Michael Specter, Sunoo Park, Matthew Green
Cryptographic protocols
Email breaches are commonplace, and they expose a wealth of personal, business, and political data whose release may have devastating consequences. Such damage is compounded by email’s strong attributability: today, any attacker who gains access to your email can easily prove to others that the stolen messages are authentic, a property arising from a necessary anti-spam/anti-spoofing protocol called DKIM. This greatly increases attackers’ capacity to do harm by selling the stolen information...
Anonymous Deniable Identification in Ephemeral Setup & Leakage Scenarios
Łukasz Krzywiecki, Mirosław Kutyłowski, Jakub Pezda, Marcin Słowik
Cryptographic protocols
In this paper we concern anonymous identification, where the verifier
can check that the user belongs to a given group of users (just like in case of
ring signatures), however a transcript of a session executed between a user and a
verifier is deniable. That is, neither the verifier nor the prover can convice a third
party that a given user has been involved in a session but also he cannot prove
that any user has been interacting with the verifier. Thereby one can achieve high
standards for...
Identity-Based Higncryption
Hongbing Wang, Yunlei Zhao
Public-key cryptography
Identity-based cryptography (IBC) is fundamental to security and privacy protection. Identity-based authenticated encryption (i.e., signcryption) is an important IBC primitive, which has numerous and promising applications. After two decades of research on signcryption,recently a new cryptographic primitive, named higncryption, was proposed. Higncryption can be viewed as privacy-enhanced signcryption, which integrates public key encryption, entity authentication, and identity concealment...
Fully Deniable Interactive Encryption
Ran Canetti, Sunoo Park, Oxana Poburinnaya
Cryptographic protocols
Deniable encryption (Canetti et al., Crypto 1996) enhances secret communication over public channels, providing the additional guarantee that the secrecy of communication is protected even if the parties are later coerced (or willingly bribed) to expose their entire internal states: plaintexts, keys and randomness.
To date, constructions of deniable encryption --- and more generally, interactive deniable communication --- only address restricted cases where only one party is compromised...
End-to-End Secure Mobile Group Messaging with Conversation Integrity and Deniability
Michael Schliep, Nicholas Hopper
Cryptographic protocols
In this paper, we describe Mobile CoWPI, a deployable, end-to-end secure mobile group messaging application
with proofs of security. Mobile CoWPI allows dynamic groups of users to participate in, join, and leave private,
authenticated conversations without requiring the participants to be simultaneously online or maintain reliable network
connectivity. We identify the limitations of mobile messaging and how they affect conversational integrity and
deniability. We define strong models of...
Circumventing Cryptographic Deniability with Remote Attestation
Lachlan J. Gunn, Ricardo Vieitez Parra, N. Asokan
Deniable messaging protocols allow two parties to have 'off-the-record' conversations without leaving any record that can convince external verifiers about what either of them said during the conversation. Recent events like the Podesta email dump underscore the importance of deniable messaging to politicians, whistleblowers, dissidents and many others. Consequently, messaging protocols like Signal and OTR are designed with cryptographic mechanisms to ensure deniable communication,...
P2KMV: A Privacy-preserving Counting Sketch for Efficient and Accurate Set Intersection Cardinality Estimations
Hagen Sparka, Florian Tschorsch, Björn Scheuermann
Applications
In this paper, we propose P2KMV, a novel privacy-preserving counting sketch, based on the k minimum values algorithm. With P2KMV, we offer a versatile privacy-enhanced technology for obtaining statistics, following the principle of data minimization, and aiming for the sweet spot between privacy, accuracy, and computational efficiency. As our main contribution, we develop methods to perform set operations, which facilitate cardinality estimates under strong privacy requirements. Most...
Activate Later Certificates for V2X -- Combining ITS efficiency with privacy
Eric R. Verheul
We specify Issue First Activate Later (IFAL). This is an ETSI type of V2X Public Key Infrastructure based on short-lived pseudonymous certificates without Certificate Revocation Lists. IFAL certificates are valid in the future but can only be used together with periodically provided activation codes. IFAL supports controlled de-pseudonymization enabling provisioning to stop for misbehaving vehicles.
IFAL allows for flexible policies, trade-offs between three essential V2X properties: trust,...
Deniable Attribute Based Encryption for Branching Programs from LWE
Daniel Apon, Xiong Fan, Feng-Hao Liu
Public-key cryptography
Deniable encryption (Canetti et al. CRYPTO '97) is an intriguing primitive that provides a security guarantee against not only eavesdropping attacks as required by semantic security, but also stronger coercion attacks performed after the fact. The concept of deniability has later demonstrated useful and powerful in many other contexts, such as leakage resilience, adaptive security of protocols, and security against selective opening attacks. Despite its conceptual usefulness, our...
Deniable Functional Encryption
Angelo De Caro, Vincenzo Iovino, Adam O'Neill
Deniable encryption, first introduced by Canetti et al. (CRYPTO 1997), allows a sender and/or receiver of encrypted communication to produce fake but authentic-looking coins and/or secret keys that ``open'' the communication to a different message. Here we initiate its study for the more general case of functional encryption (FE), as introduced by Boneh et al. (TCC 2011), wherein a receiver in possession of a key k can compute from any encryption of a message x the value F(k,x) according to...
The Ultimate Transposition Cipher (UTC)
Gideon Samid
An Ultimate Transposition Cipher (UTC) is defined as a cipher that transposes any permutation of some n elements to any other permutation of the same elements. Hence, by listing together the protected message and plausible alternatives to it, and then mixing it, one secures a ciphertext which the intended reader will readily "un-mix" (using the shared key), but the cryptanalyst will find proper keys for all the 'decoy messages' and will not be able to go further. The UTC transposed...
Bi-Deniable Inner Product Encryption from LWE
Daniel Apon, Xiong Fan, Feng-Hao Liu
Public-key cryptography
Deniable encryption (Canetti et al. CRYPTO '97) is an intriguing primitive that provides a security guarantee against not only eavesdropping attacks as required by semantic security, but also stronger coercion attacks performed after the fact. The concept of deniability has later demonstrated useful and powerful in many other contexts, such as leakage resilience, adaptive security of protocols, and security against selective opening attacks. Despite its conceptual usefulness, our...
Group Signature with Deniability: How to Disavow a Signature
Ai Ishida, Keita Emura, Goichiro Hanaoka, Yusuke Sakai, Keisuke Tanaka
Public-key cryptography
Group signatures are a class of digital signatures with enhanced privacy. By using this type of signature, a user can sign a message on behalf of a specific group without revealing his identity, but in the case of a dispute, an authority can expose the identity of the signer. However, in some situations it is only required to know whether a specific user is the signer of a given signature. In this case, the use of a standard group signature may be problematic since the specified user might...
2014/859
Last updated: 2014-11-17
Provably secure pairing-free identity-based partially blind signature scheme and its application in online e-cash system
SK Hafizul Islam, G. P. Biswas
Public-key cryptography
The blind signature scheme permits the user to acquire a signature
from the signer; however, the message and the final signature are
unknown to the signer. In a partially blind signature (PBS) scheme,
the signer can explicitly incorporate a common information in the
signature based on some agreement with the user and without
violating the blindness property. Many PBS schemes have been
proposed recently either by using certificate authority-based public
infrastructure (CA-PKI) or pairing...
Online Deniability for Multiparty Protocols with Applications to Externally Anonymous Authentication
Alonso Gonzalez-Ulloa, Alejandro Hevia
Foundations
In the problem of anonymous authentication (Boneh et al. CCS 1999), a sender wishes to authenticate a message to a given recipient in a way that preserves anonymity: the recipient does not know the identity of the sender and only is assured that the sender belongs to some authorized set. Although solutions for the problem exist (for example, by using ring signatures, e.g. Naor, Crypto 2002), they provide no security when the anonymity set is a singleton. This work is motivated by the...
One-Round Deniable Key Exchange with Perfect Forward Security
Weiqiang Wen, Libin Wang, Min Xie
Cryptographic protocols
In response to the need for secure one-round authenticated key exchange protocols providing both perfect forward secrecy and full deniability, we put forward a new paradigm for constructing protocols from a Diffie-Hellman type protocol plus a non-interactive designated verifier proof of knowledge (DV-PoK) scheme. We define the notion of DV-PoK which is a variant of non-interactive zero-knowledge proof of knowledge, and provide an efficient DV-PoK scheme as a central technical building block...
Universally Composable Authentication and Key-exchange with Global PKI
Ran Canetti, Daniel Shahaf, Margarita Vald
Message authentication and key exchange are two of the most basic tasks of
cryptography. Solutions based on public-key infrastructure (PKI) are
prevalent. Still, the state of the art in composable security analysis of
PKI-based authentication and key exchange is somewhat unsatisfactory.
Specifically, existing treatments either (a)~make the unrealistic assumption
that the PKI is accessible only within the confines of the protocol itself,
thus failing to capture real-world PKI-based...
Prover Anonymous and Deniable Distance-Bounding Authentication
Sebastien Gambs, Cristina Onete, Jean-Marc Robert
Cryptographic protocols
In distance-bounding authentication protocols, a verifier confirms that a prover is (1) legitimate and (2) in the verifier's proximity. Proximity checking is done by running time-critical exchanges between both parties. This enables the verifier to detect relay attacks (a.k.a. mafia fraud). While most distance-bounding protocols
offer resistance to mafia and distance fraud as well as to impersonation attacks, only few protect the privacy of the authenticating prover.
One exception is the...
Practical Dual-Receiver Encryption---Soundness, Complete Non-Malleability, and Applications
Sherman S. M. Chow, Matthew Franklin, Haibin Zhang
Public-key cryptography
We reformalize and recast dual-receiver encryption (DRE) proposed in CCS '04, a public-key encryption (PKE) scheme for encrypting to two independent recipients in one shot. We start by defining the crucial soundness property for DRE, which ensures that two recipients will get the same decryption result. While conceptually simple, DRE with soundness turns out to be a powerful primitive for various goals for PKE, such as complete non-malleability (CNM) and plaintext-awareness (PA). We then...
ECC-Based Non-Interactive Deniable Authentication with Designated Verifier
Yalin Chen, Jue-Sam Chou
Recently, researchers have proposed many non-interactive deniable authentication (NIDA) protocols. Most of them claim that their protocols possess full deniability. However, after reviewing, we found that they either cannot achieve full deniability, or suffer KCI or SKCI attack; moreover, lack efficiency, because they are mainly based on DLP, factoring problem, or bilinear pairings. Due to this observation, and that ECC provides the security equivalence to RSA and DSA by using much smaller...
Fully Deniable Mutual Authentication Protocol Based on RSA Signature
Xi-Jun Lin, Lin Sun
Cryptographic protocols
Deniable authentication protocols allow a sender to authenticate a receiver, in a way that the receiver cannot convince a third party that such authentication (or any authentication) ever took place. In this study, we construct a fully deniable mutual authentication protocol based on RSA signature, and then a deniable authenticated key exchange protocol is constructed from the proposed protocol.
Fully Bideniable Public-Key Encryption
Marcel Šebek
Public-key cryptography
Bideniable encryption allows both sender and receiver in a public-key setting to simultaneously claim that a different message of their choice was transmitted, and support this claim by a good-looking encryption and key-generation randomness, respectively. A weaker version with two variants of algorithms is called flexible or multi-distributional deniability, a stronger one-algorithm version is called full deniability. Bendlin et al. (ASIACRYPT 2011) showed that certain kinds of...
A Cryptographic Analysis of OPACITY
Özgür Dagdelen, Marc Fischlin, Tommaso Gagliardoni, Giorgia Azzurra Marson, Arno Mittelbach, Cristina Onete
Cryptographic protocols
We take a closer look at the Open Protocol for Access Control, Identification, and Ticketing with privacY (OPACITY).
This Diffie--Hellman-based protocol
is supposed to provide a secure and privacy-friendly key establishment for contactless environments.
It is promoted by the US Department of Defense and meanwhile available in several standards such as ISO/IEC 24727-6 and ANSI 504-1.
To the best of our knowledge, so far no detailed cryptographic analysis has been publicly available.
Thus, we...
The PACE|AA Protocol for Machine Readable Travel Documents, and its Security
Jens Bender, Özgür Dagdelen, Marc Fischlin, Dennis Kügler
Cryptographic protocols
We discuss an efficient combination of the cryptographic protocols adopted by the International Civil Aviation Organization (ICAO) for securing the communication of machine readable travel documents and readers. Roughly, in the original protocol the parties first run the
Password-Authenticated Connection Establishment (PACE) protocol to establish a shared key and then the reader (optionally) invokes the Active Authentication (AA) protocol to verify the passport's validity. Here, we show that...
Scalable Deniable Group Key Establishment
Kashi Neupane, Rainer Steinwandt, Adriana Suarez Corona
The popular Katz-Yung compiler from CRYPTO 2003 can be used to transform unauthenticated group key establishment protocols into authenticated ones. In this paper we present a modication of Katz and Yung's construction which maintains the round complexity of their compiler, but for "typical" unauthenticated group key establishments adds authentication in such a way that deniability is achieved as well. As an application, a deniable authenticated group key establishment with three rounds of...
Hush Functions Extended to Any Size Input versus Any Size Output
Gideon Samid
Foundations
Traditional hush functions map a large number to a small number such that the reverse-hush has an infinity of solutions, and nonetheless a collision is hard to come by. This primitive is so abundantly useful that one is tempted to extend it such that any number large or small may be mapped to any number larger, or smaller while maintaining the above conditions. This extension would increase the flexibility of the commodity hush primitive, expand its current applications, and likely suggest...
Universally Composable Security With Local Adversaries
Ran Canetti, Margarita Vald
The traditional approach to formalizing ideal-model based definitions of security for multi-party protocols models adversaries (both real and ideal) as centralized entities that control all parties that deviate from the protocol. While this centralized-adversary modeling suffices for capturing basic security properties such as secrecy of local inputs and correctness of outputs against coordinated attacks, it turns out to be inadequate for capturing security properties that involve...
Bi-Deniable Public-Key Encryption
Adam O'Neill, Chris Peikert, Brent Waters
Public-key cryptography
In CRYPTO 1997, Canetti \etal put forward the intruiging notion of
\emph{deniable encryption}, which (informally) allows a sender and/or
receiver, having already performed some encrypted communication, to
produce `fake' (but legitimate-looking) random coins that open the
ciphertext to another message. Deniability is a powerful notion for
both practice and theory: apart from its inherent utility for
resisting coercion, a deniable scheme is also noncommitting (a useful
property in...
One-round Strongly Secure Key Exchange with Perfect Forward Secrecy and Deniability
Cas Cremers, Michele Feltz
Cryptographic protocols
Traditionally, secure one-round key exchange protocols in the PKI setting have either achieved perfect forward secrecy, or forms of deniability, but not both. On the one hand, achieving perfect forward secrecy against active attackers seems to require some form of authentication of the messages, as in signed Diffie-Hellman style protocols, that subsequently sacrifice deniability. On the other hand,
using implicit authentication along the lines of MQV and descendants sacrifices perfect...
A New Family of Implicitly Authenticated Diffie-Hellman Protocols
Andrew C. Yao, Yunlei Zhao
Cryptography algorithm standards play a key role both to the practice of information security and to cryptography theory research. Among them, the MQV and HMQV protocols ((H)MQV, in
short) are a family of implicitly authenticated Diffie-Hellman key-exchange (DHKE) protocols that are among the most efficient and are widely standardized. In this work, from some new perspectives
and under some new design rationales, and also inspired by the security analysis of HMQV, we develop a new family of...
A Novel Non-interactive Deniable Authentication Protocol with Designated Verifier on elliptic curve cryptosystem
Yalin Chen, Jue-Sam Chou, Chi-Fong Lin
Cryptographic protocols
Recently, many non-interactive deniable authentication (NIDA) protocols have been proposed. They are mainly composed of two types, signature-based and shared-secrecy based. After reviewing these schemes, we found that the signature-based approach can not deny the source of the message and thus can not achieve full deniability; and that, the shared-secrecy based approach suffers KCI attack although it can achieve full deniability. In addition, both types of schemes lack efficiency...
Timed Encryption and Its Application
Shaoquan Jiang
Cryptographic protocols
In this paper, we propose a new notion of timed encryption, in which the encryption is secure within time $t$ while
it is totally insecure after some time $T>t.$ We are interested in the case where $t$ and $T$ are both polynomial. We propose a concrete construction that is provably secure in the random oracle model. We show that it can be generically (although inefficient) constructed from a timed commitment of Boneh and Naor (CRYPTO'00). Finally, we apply this primitive to construct a...
Attribute-based group key establishment
Rainer Steinwandt, Adriana Suárez Corona
Cryptographic protocols
Motivated by the problem of establishing a session key among
parties based on the possession of certain credentials only, we discuss a
notion of attribute-based key establishment. A number of new issues arise
in this setting that are not present in the usual settings of group key
establishment where unique user identities are assumed to be publicly
available.
After detailing the security model, we give a two-round solution in the
random oracle model. As main technical tool we introduce a...
An Efficient Adaptive-Deniable-Concurrent Non-malleable Commitment Scheme
Seiko Arita
It is known that composable secure commitments, that is, concurrent non-malleable commitments exist in the plain model, based only on standard assumptions such as the existence of claw-free permutations or even one-way functions. Since being based on the plain model, the deniability of them is trivially satisfied, and especially the latter scheme satisfies also adaptivity, hence it is adaptive-deniable-concurrent non-malleable. However, those schemes cannot be said to be practically...
On Privacy Losses in the Trusted Agent Model (Abstract)
Paulo Mateus, Serge Vaudenay
Foundations
Tamper-proof devices are pretty powerful. They typically make security applications simpler (provided that the tamper-proof assumption is not violated). For application requiring privacy, we observe that some properties may become harder (if possible at all) to achieve when devices are maliciously used. We take the example of deniability, receipt-freeness, and anonymity.
We formalize the trusted agent model which assumes tamper-proof hardware in a way which captures the notion of...
Deniable Internet Key-Exchange
Andrew C. C. Yao, Frances F. Yao, Yunlei Zhao, Bin Zhu
Cryptographic protocols
In this work, we develop a family of protocols for deniable Internet Key-Exchange (IKE) with the following properties:
1. item Highly practical efficiency, and conceptual simplicity and clarity.
2. Forward and concurrent (non-malleable) deniability against adversaries with arbitrary auxiliary inputs, and better privacy
protection of players' roles.
3. Provable security in the Canetti-Krawczyk post-specified-peer model, and maintenance of essential security properties not captured by the...
Secure Deniable Authenticated Key Establishment for Internet Protocols
Meng-Hui Lim, Sanggon Lee, Youngho Park, Sangjae Moon
In 2003, Boyd et al. have proposed two deniable authenticated key establishment protocols for Internet Key Exchange (IKE). However, both schemes have been broken by Chou et al. in 2005 due to their susceptibility to key-compromise impersonation (KCI) attack. In this paper, we put forward the improved variants of both Boyd et al.'s schemes in order to defeat the KCI attack. On top of justifying our improvements, we further present a detailed security analysis to ensure that the desired...
An Enhanced ID-based Deniable Authentication Protocol on Pairings
Meng-Hui Lim, Sanggon Lee, Youngho Park, Hoonjae Lee
Deniability is defined as a privacy property which enables protocol principals to deny their involvement after they had taken part in a particular protocol run. Lately, Chou et al. had proposed their ID-based deniable authentication protocol after proving the vulnerability to Key-Compromise Impersonation (KCI) attack in Cao et al.'s protocol. In addition, they claimed that their protocol is not only secure, but also able to achieve both authenticity and deniability properties. However, in...
Universally Composable Security with Global Setup
Ran Canetti, Yevgeniy Dodis, Rafael Pass, Shabsi Walfish
Foundations
Cryptographic protocols are often designed and analyzed under some trusted setup assumptions, namely in settings where the participants have access to global information that is trusted to have some basic security properties. However, current modeling of security in the presence of such setup falls short of providing the expected security guarantees. A quintessential example of this phenomenon is the deniability concern: there exist natural protocols that meet the strongest known composable...
The Wrestlers Protocol: A simple, practical, secure, deniable protocol for key-exchange
Mark Wooding
Cryptographic protocols
We describe and prove (in the random-oracle model) the security of a simple but efficient zero-knowledge identification scheme, whose security is based on the computational Diffie-Hellman problem. Unlike other recent proposals for efficient identification protocols, we don't need any additional assumptions, such as the Knowledge of Exponent assumption.
From this beginning, we build a simple key-exchange protocol, and prove that it achieves `SK-security' -- and hence security in Canetti's...
Chameleon-Based Deniable Authenticated Key Agreement Protocol
Chunbo Ma, Jun Ao, Jianhua Li
As a useful means of safeguarding privacy of communications, deniable authentication has received much attention. A Chameleon-based deniable authenticated key agreement protocol is presented in this paper. The protocol has following properties. Any one of the two participants can’t present a digital proof to convince a third party that a claimed agreement has really taken place. Once a forgery occurs, the original entity can present a digital proof to disclose the forgery.
Deniable Authentication and Key Exchange
Mario Di Raimondo, Rosario Gennaro, Hugo Krawczyk
Cryptographic protocols
We extend the definitional work of Dwork, Naor and Sahai from deniable authentication to deniable key-exchange protocols. We then use these definitions to prove the deniability features of SKEME and SIGMA, two natural and efficient protocols which serve as basis for the Internet Key Exchange (IKE) protocol. The two protocols require distinct approaches to their deniability analysis, hence highlighting important definitional issues as well as necessitating different tools in the...
New Approaches for Deniable Authentication
Mario Di Raimondo, Rosario Gennaro
Cryptographic protocols
Deniable Authentication protocols allow a Sender to authenticate a message for a Receiver, in a way that the Receiver cannot convince a third party that such authentication (or any authentication) ever took place.
We present two new approaches to the problem of deniable authentication. The novelty of our schemes is that they do not require the use of CCA-secure encryption (all previous known solutions did), thus showing a different generic approach to the problem of deniable authentication....
Essential Shannon Security with Keys Smaller Than the Encrypted Message
Gideon Samid
Foundations
To a cryptographer the claim that “Shannon Security was achieved with keys smaller than the encrypted message" appears unworthy of attention, much as the claim of “perpetuum mobile” is to a physicist. Albeit, from an engineering point of view solar cells which power satellites exhibit an “essential perpetuum mobile” and are of great interest. Similarly for Shannon Security, as it is explored in this article. We discuss encryption schemes designed to confound a diligent cryptanalyst...
Tailored Key Encryption (TaKE) Tailoring a key for a given pair of plaintext/ciphertext
Gideon Samid
Foundations
Abstract. The prevailing cryptographies are attacked on the basis of
the fact that only a single element in the key space will match a
plausible plaintext with a given ciphertext. Any cryptography that
would violate this unique-key assumption, will achieve added security
through deniability (akin to One Time Pad). Such cryptography is being
described. It is achieved by breaking away from the prevailing notion
that the key is a binary string of a fixed length. The described key is
random-size...
Deniable Encryption
Ran Canetti, Cynthia Dwork, Moni Naor, Rafi Ostrovsky
Consider a situation in which the transmission of encrypted
messages is intercepted by an adversary who can later
ask the sender to reveal
the random choices (and also the secret key, if one exists)
used in generating
the ciphertext, thereby exposing the cleartext.
An encryption scheme is <B>deniable</B> if the sender can generate
`fake random choices' that will make the ciphertext `look like'
an encryption of a different cleartext, thus keeping the
real cleartext private.
Analogous...
Many messaging platforms have integrated end-to-end (E2E) encryption into their services. This widespread adoption of E2E encryption has triggered a technical tension between user privacy and illegal content moderation. The existing solutions either support only unframeability or deniability, or they are prone to abuse (the moderator can perform content moderation for all messages, whether illegal or not), or they lack mechanisms for retrospective content moderation. To address the above...
Cryptography's most common use is secure communication---e.g. Alice can use encryption to hide the contents of the messages she sends to Bob (confidentiality) and can use signatures to assure Bob she sent these messages (authenticity). While one typically considers stateless security guarantees---for example a channel that Alice can use to send messages securely to Bob---one can also consider stateful ones---e.g. an interactive conversation between Alice, Bob and their friends where...
Ring signatures, a cryptographic primitive introduced by Rivest, Shamir and Tauman (ASIACRYPT 2001), offer signer anonymity within dynamically formed user groups. Recent advancements have focused on lattice-based constructions to improve efficiency, particularly for large signing rings. However, current state-of-the-art solutions suffer from significant overhead, especially for smaller rings. In this work, we present a novel NTRU-based ring signature scheme, Gandalf, tailored towards...
Many use messaging apps such as Signal to exercise their right to private communication. To cope with the advent of quantum computing, Signal employs a new initial handshake protocol called PQXDH for post-quantum confidentiality, yet keeps guarantees of authenticity and deniability classical. Compared to its predecessor X3DH, PQXDH includes a KEM encapsulation and a signature on the ephemeral key. In this work we show that PQXDH does not meet the same deniability guarantees as X3DH due to...
Confidentiality and authentication are two main security goals in secure electronic mail (e-mail). Furthermore, deniability is also a significant security property for some e-mail applications to protect the privacy of the sender. Although searchable encryption solves the keyword searching problem in a secure e-mail system, it also breaks the deniability of the system. Because the adversary can obtain the information of the data sender and data user from the trapdoor as well as ciphertext...
We argue that there are some scenarios in which plausible deniability might be desired for a digital signature scheme. For instance, the non-repudiation property of conventional signature schemes is problematic in designing an Instant Messaging system (WPES 2004). In this paper, we formally define a non-binding signature scheme in which the Signer is able to disavow her own signature if she wants, but, the Verifier is not able to dispute a signature generated by the Signer. That is,...
The Signal protocol and its X3DH key exchange core are regularly used by billions of people in applications like WhatsApp but are unfortunately not quantum-secure. Thus, designing an efficient and post-quantum secure X3DH alternative is paramount. Notably, X3DH supports asynchronicity, as parties can immediately derive keys after uploading them to a central server, and deniability, allowing parties to plausibly deny having completed key exchange. To satisfy these constraints, existing...
The Fiat-Shamir transform is a classical technique for turning any zero-knowledge $\Sigma$-protocol into a signature scheme. In essence, the idea underlying this transform is that deriving the challenge from the digest of the commitment suppresses simulatability and hence provides non-interactive proofs of interaction. It follows from that observation that if one wishes to preserve deniability the challenge size (per round) must be kept low. For instance in the original Fiat-Shamir...
Modern secure messaging protocols typically aim to provide deniability. Achieving this requires that convincing cryptographic transcripts can be forged without the involvement of genuine users. In this work, we observe that parties may wish to revoke deniability and avow a conversation after it has taken place. We propose a new protocol called Not-on-the-Record-Yet (NOTRY) which enables users to prove a prior conversation transcript is genuine. As a key building block we propose avowable...
We present Shufflecake, a new plausible deniability design to hide the existence of encrypted data on a storage medium making it very difficult for an adversary to prove the existence of such data. Shufflecake can be considered a ``spiritual successor'' of tools such as TrueCrypt and VeraCrypt, but vastly improved: it works natively on Linux, it supports any filesystem of choice, and can manage multiple volumes per device, so to make deniability of the existence of hidden partitions really...
Deniable encryption (Canetti et al. CRYPTO ’97) is an intriguing primitive, which provides security guarantee against coercion by allowing a sender to convincingly open the ciphertext into a fake message. Despite the notable result by Sahai and Waters STOC ’14 and other efforts in functionality extension, all the deniable public key encryption (DPKE) schemes suffer from intolerable overhead due to the heavy building blocks, e.g., translucent sets or indistinguishability obfuscation. Besides,...
This work explores real-world deniability in messaging. We propose a formal model that considers the entire messaging system to analyze deniability in practice. Applying this model to the Signal application and DKIM-protected email, we demonstrate that these systems do not offer practical deniability guarantees. Additionally, we analyze 140 court cases in Switzerland that use conversations on messaging applications as evidence and find that none consider deniability, providing evidence that...
An anamorphic encryption scheme allows two parties who share a so-called double key to embed covert messages in ciphertexts of an established PKE scheme. This protects against a dictator that can force the receiver to reveal the secret keys for the PKE scheme, but who is oblivious about the existence of the double key. We identify two limitations of the original model by Persiano, Phan, and Yung (EUROCRYPT 2022). First, in their definition a double key can only be generated once, together...
Deniable Authentication is a highly desirable property for secure messaging protocols: it allows a sender Alice to authentically transmit messages to a designated receiver Bob in such a way that only Bob gets convinced that Alice indeed sent these messages. In particular, it guarantees that even if Bob tries to convince a (non-designated) party Judy that Alice sent some message, and even if Bob gives Judy his own secret key, Judy will not be convinced: as far as Judy knows, Bob could be...
Most cryptographic protocols model a player’s knowledge of secrets in a simple way. Informally, the player knows a secret in the sense that she can directly furnish it as a (private) input to a protocol, e.g., to digitally sign a message. The growing availability of Trusted Execution Environments (TEEs) and secure multiparty computation, however, undermines this model of knowledge. Such tools can encumber a secret sk and permit a chosen player to access sk conditionally, without actually...
This work introduces DSKE, digital signatures with key extraction. In a DSKE scheme, the private key can be extracted if more than a threshold of signatures on different messages are ever created while, within the threshold, each signature continues to authenticate the signed message. We give a formal definition of DSKE, as well as two provably secure constructions, one from hash-based digital signatures and one from polynomial commitments. We demonstrate that DSKE is useful for...
Recent years have seen many advances in designing secure messaging protocols, aiming at provably strong security properties in theory or high efficiency for real-world practical deployment. However, important trade-off areas of the design space inbetween these elements have not yet been explored. In this work we design the first provably secure protocol that at the same time achieves (i) strong resilience against finegrained compromise, (ii) temporal privacy, and (iii) immediate...
Deniable public-key encryption (DPKE) is a cryptographic primitive that allows the sender of an encrypted message to later claim that they sent a different message. DPKE's threat model assumes powerful adversaries who can coerce users to reveal plaintexts; it is thus reasonable to consider other advanced capabilities, such as the ability to subvert algorithms in a so-called Algorithm Substitution Attack (ASA). An ASA replaces a trusted algorithm with a subverted version that undermines...
KEMTLS is a proposal for changing the TLS handshake to authenticate the handshake using long-term key encapsulation mechanism keys instead of signatures, motivated by trade-offs in the characteristics of post-quantum algorithms. Prior proofs of security of KEMTLS and its variant KEMTLS-PDK have been hand-written proofs in the reductionist model under computational assumptions. In this paper, we present computer-verified symbolic analyses of KEMTLS and KEMTLS-PDK using two distinct Tamarin...
In this work we propose time-deniable signatures (TDS), a new primitive that facilitates deniable authentication in protocols such as DKIM-signed email. As with traditional signatures, TDS provide strong authenticity for message content, at least for a sender-chosen period of time. Once this time period has elapsed, however, time-deniable signatures can be forged by any party who obtains a signature. This forgery property ensures that signatures serve a useful authentication purpose for a...
Interactive zero-knowledge systems are a very important cryptographic primitive, used in many applications, especially when deniability (also known as non-transferability) is desired. In the lattice-based setting, the currently most efficient interactive zero-knowledge systems employ the technique of rejection sampling, which implies that the interaction does not always finish correctly in the first execution; the whole interaction must be re-run until abort does not happen. While...
End-to-end encryption provides strong privacy protections to billions of people, but it also complicates efforts to moderate content that can seriously harm people. To address this concern, Tyagi et al. [CRYPTO 2019] introduced the concept of asymmetric message franking (AMF), which allows people to report abusive content to a moderator, while otherwise retaining end-to-end privacy by default and even compatibility with anonymous communication systems like Signal’s sealed sender. In this...
Data privacy is critical in instilling trust and empowering the societal pacts of modern technology-driven democracies. Unfortunately, it is under continuous attack by overreaching or outright oppressive governments, including some of the world's oldest democracies. Increasingly-intrusive anti-encryption laws severely limit the ability of standard encryption to protect privacy. New defense mechanisms are needed. Plausible deniability (PD) is a powerful property, enabling users to hide the...
Selective opening attacks (SOA) (for public-key encryption, PKE) concern such a multi-user scenario, where an adversary adaptively corrupts some fraction of the users to break into a subset of honestly created ciphertexts, and tries to learn the information on the messages of some unopened (but potentially related) ciphertexts. Until now, the notion of selective opening attacks is only considered in two settings: sender selective opening (SSO), where part of senders are corrupted and...
Peer-to-peer distributed hash tables (DHTs) rely on volunteers to contribute their computational resources, such as disk space and bandwidth. In order to incentivize these node operators of privacy-preserving DHTs, it is important to prevent exposing them to the data that is stored on the DHT and/or queried for. Vasserman et al.'s CROPS aimed at providing plausible deniability to server nodes by encrypting stored content. However, node operators are still exposed to the contents of queries....
In the effort to transition cryptographic primitives and protocols to quantum-resistant alternatives, an interesting and useful challenge is found in the Signal protocol. The initial key agreement component of this protocol, called X3DH, has so far proved more subtle to replace - in part due to the unclear security model and properties the original protocol is designed for. This paper defines a formal security model for the original signal protocol, in the context of the standard eCK and CK+...
The key exchange protocol that establishes initial shared secrets in the handshake of the Signal end-to-end encrypted messaging protocol has several important characteristics: (1) it runs asynchronously (without both parties needing to be simultaneously online), (2) it provides implicit mutual authentication while retaining deniability (transcripts cannot be used to prove either party participated in the protocol), and (3) it retains security even if some keys are compromised (forward...
Offline deniability is the ability to a-posteriori deny having participated in a particular communication session. This property has been widely assumed for the Signal messaging application, yet no formal proof has appeared in the literature. In this paper, we present what we believe is the first formal study of the offline deniability of the Signal protocol. Our analysis shows that building a deniability proof for Signal is non-trivial and requires strong assumptions on the underlying...
The Signal protocol is a secure instant messaging protocol that underlies the security of numerous applications such as WhatsApp, Skype, Facebook Messenger among many others. The Signal protocol consists of two sub-protocols known as the X3DH protocol and the double ratchet protocol, where the latter has recently gained much attention. For instance, Alwen, Coretti, and Dodis (Eurocrypt'19) provided a concrete security model along with a generic construction based on simple building blocks...
We define and construct Deniable Fully Homomorphic Encryption based on the Learning With Errors (LWE) polynomial hardness assumption. Deniable FHE enables storing encrypted data in the cloud to be processed securely without decryption, maintaining deniability of the encrypted data, as well the prevention of vote-buying in electronic voting schemes where encrypted votes can be tallied without decryption. Our constructions achieve compactness independently of the level of deniability- both...
Incoercible multi-party computation (Canetti-Gennaro ’96) allows parties to engage in secure computation with the additional guarantee that the public transcript of the computation cannot be used by a coercive outsider to verify representations made by the parties regarding their inputs, outputs, and local random choices. That is, it is guaranteed that the only deductions regarding the truthfulness of such representations, made by an outsider who has witnessed the communication among...
This paper presents an attack against common procedures for comparing the size-security tradeoffs of proposed cryptosystems. The attack begins with size-security tradeoff data, and then manipulates the presentation of the data in a way that favors a proposal selected by the attacker, while maintaining plausible deniability for the attacker. As concrete examples, this paper shows two manipulated comparisons of size-security tradeoffs of lattice-based encryption proposals submitted to the...
A deniable authenticated key exchange can establish a secure communication channel while leaving no cryptographic evidence of communication. Some well-designed protocol today, even in the case of betrayal by some participants and disclosure of long-term key materials, cannot leave any cryptographic evidence. However, this is no longer enough: If “Big data” technology is used to analyse data fetched from pivotal nodes, it’s not difficult to register your identity through your long-term public...
We introduce formal definitions for deniability in group chats by extending a pre-existing model that did not have this property. We then introduce “epochal signatures” as an almost drop-in replacement for signatures, which can be used to make certain undeniable group-chats deniable by just performing that replacement. Following that we provide a practical epochal signature scheme and prove its security.
Off-the-Record (OTR) messaging is a two-party message authentication protocol that also provides plausible deniability: there is no record that can later convince a third party what messages were actually sent. To extend OTR to group messaging we need to consider issues that are not present in the 2-party case. In group OTR (as in two-party OTR), the sender should be able to authenticate (or sign) his messages so that group members can verify who sent a message (that is, signatures should be...
We design a suite of protocols so that a small tamper-resistant device can be used as a biometric identity document which can be scanned by authorized terminals. We target both strongly secure identification and strong privacy. Unlike biometric passports, our protocols leak no digital evidence and are essentially deniable. Besides, getting the identity information from the device requires going through access control. Access control can follow either a strong PKI-based path or a weak...
Content moderation is crucial for stopping abuse and harassment via messaging on online platforms. Existing moderation mechanisms, such as message franking, require platform providers to see user identifiers on encrypted traffic. These mechanisms cannot be used in messaging systems in which users can hide their identities, such as Signal. The key technical challenge preventing moderation is in simultaneously achieving cryptographic accountability while preserving deniability. In this work,...
Email breaches are commonplace, and they expose a wealth of personal, business, and political data whose release may have devastating consequences. Such damage is compounded by email’s strong attributability: today, any attacker who gains access to your email can easily prove to others that the stolen messages are authentic, a property arising from a necessary anti-spam/anti-spoofing protocol called DKIM. This greatly increases attackers’ capacity to do harm by selling the stolen information...
In this paper we concern anonymous identification, where the verifier can check that the user belongs to a given group of users (just like in case of ring signatures), however a transcript of a session executed between a user and a verifier is deniable. That is, neither the verifier nor the prover can convice a third party that a given user has been involved in a session but also he cannot prove that any user has been interacting with the verifier. Thereby one can achieve high standards for...
Identity-based cryptography (IBC) is fundamental to security and privacy protection. Identity-based authenticated encryption (i.e., signcryption) is an important IBC primitive, which has numerous and promising applications. After two decades of research on signcryption,recently a new cryptographic primitive, named higncryption, was proposed. Higncryption can be viewed as privacy-enhanced signcryption, which integrates public key encryption, entity authentication, and identity concealment...
Deniable encryption (Canetti et al., Crypto 1996) enhances secret communication over public channels, providing the additional guarantee that the secrecy of communication is protected even if the parties are later coerced (or willingly bribed) to expose their entire internal states: plaintexts, keys and randomness. To date, constructions of deniable encryption --- and more generally, interactive deniable communication --- only address restricted cases where only one party is compromised...
In this paper, we describe Mobile CoWPI, a deployable, end-to-end secure mobile group messaging application with proofs of security. Mobile CoWPI allows dynamic groups of users to participate in, join, and leave private, authenticated conversations without requiring the participants to be simultaneously online or maintain reliable network connectivity. We identify the limitations of mobile messaging and how they affect conversational integrity and deniability. We define strong models of...
Deniable messaging protocols allow two parties to have 'off-the-record' conversations without leaving any record that can convince external verifiers about what either of them said during the conversation. Recent events like the Podesta email dump underscore the importance of deniable messaging to politicians, whistleblowers, dissidents and many others. Consequently, messaging protocols like Signal and OTR are designed with cryptographic mechanisms to ensure deniable communication,...
In this paper, we propose P2KMV, a novel privacy-preserving counting sketch, based on the k minimum values algorithm. With P2KMV, we offer a versatile privacy-enhanced technology for obtaining statistics, following the principle of data minimization, and aiming for the sweet spot between privacy, accuracy, and computational efficiency. As our main contribution, we develop methods to perform set operations, which facilitate cardinality estimates under strong privacy requirements. Most...
We specify Issue First Activate Later (IFAL). This is an ETSI type of V2X Public Key Infrastructure based on short-lived pseudonymous certificates without Certificate Revocation Lists. IFAL certificates are valid in the future but can only be used together with periodically provided activation codes. IFAL supports controlled de-pseudonymization enabling provisioning to stop for misbehaving vehicles. IFAL allows for flexible policies, trade-offs between three essential V2X properties: trust,...
Deniable encryption (Canetti et al. CRYPTO '97) is an intriguing primitive that provides a security guarantee against not only eavesdropping attacks as required by semantic security, but also stronger coercion attacks performed after the fact. The concept of deniability has later demonstrated useful and powerful in many other contexts, such as leakage resilience, adaptive security of protocols, and security against selective opening attacks. Despite its conceptual usefulness, our...
Deniable encryption, first introduced by Canetti et al. (CRYPTO 1997), allows a sender and/or receiver of encrypted communication to produce fake but authentic-looking coins and/or secret keys that ``open'' the communication to a different message. Here we initiate its study for the more general case of functional encryption (FE), as introduced by Boneh et al. (TCC 2011), wherein a receiver in possession of a key k can compute from any encryption of a message x the value F(k,x) according to...
An Ultimate Transposition Cipher (UTC) is defined as a cipher that transposes any permutation of some n elements to any other permutation of the same elements. Hence, by listing together the protected message and plausible alternatives to it, and then mixing it, one secures a ciphertext which the intended reader will readily "un-mix" (using the shared key), but the cryptanalyst will find proper keys for all the 'decoy messages' and will not be able to go further. The UTC transposed...
Deniable encryption (Canetti et al. CRYPTO '97) is an intriguing primitive that provides a security guarantee against not only eavesdropping attacks as required by semantic security, but also stronger coercion attacks performed after the fact. The concept of deniability has later demonstrated useful and powerful in many other contexts, such as leakage resilience, adaptive security of protocols, and security against selective opening attacks. Despite its conceptual usefulness, our...
Group signatures are a class of digital signatures with enhanced privacy. By using this type of signature, a user can sign a message on behalf of a specific group without revealing his identity, but in the case of a dispute, an authority can expose the identity of the signer. However, in some situations it is only required to know whether a specific user is the signer of a given signature. In this case, the use of a standard group signature may be problematic since the specified user might...
The blind signature scheme permits the user to acquire a signature from the signer; however, the message and the final signature are unknown to the signer. In a partially blind signature (PBS) scheme, the signer can explicitly incorporate a common information in the signature based on some agreement with the user and without violating the blindness property. Many PBS schemes have been proposed recently either by using certificate authority-based public infrastructure (CA-PKI) or pairing...
In the problem of anonymous authentication (Boneh et al. CCS 1999), a sender wishes to authenticate a message to a given recipient in a way that preserves anonymity: the recipient does not know the identity of the sender and only is assured that the sender belongs to some authorized set. Although solutions for the problem exist (for example, by using ring signatures, e.g. Naor, Crypto 2002), they provide no security when the anonymity set is a singleton. This work is motivated by the...
In response to the need for secure one-round authenticated key exchange protocols providing both perfect forward secrecy and full deniability, we put forward a new paradigm for constructing protocols from a Diffie-Hellman type protocol plus a non-interactive designated verifier proof of knowledge (DV-PoK) scheme. We define the notion of DV-PoK which is a variant of non-interactive zero-knowledge proof of knowledge, and provide an efficient DV-PoK scheme as a central technical building block...
Message authentication and key exchange are two of the most basic tasks of cryptography. Solutions based on public-key infrastructure (PKI) are prevalent. Still, the state of the art in composable security analysis of PKI-based authentication and key exchange is somewhat unsatisfactory. Specifically, existing treatments either (a)~make the unrealistic assumption that the PKI is accessible only within the confines of the protocol itself, thus failing to capture real-world PKI-based...
In distance-bounding authentication protocols, a verifier confirms that a prover is (1) legitimate and (2) in the verifier's proximity. Proximity checking is done by running time-critical exchanges between both parties. This enables the verifier to detect relay attacks (a.k.a. mafia fraud). While most distance-bounding protocols offer resistance to mafia and distance fraud as well as to impersonation attacks, only few protect the privacy of the authenticating prover. One exception is the...
We reformalize and recast dual-receiver encryption (DRE) proposed in CCS '04, a public-key encryption (PKE) scheme for encrypting to two independent recipients in one shot. We start by defining the crucial soundness property for DRE, which ensures that two recipients will get the same decryption result. While conceptually simple, DRE with soundness turns out to be a powerful primitive for various goals for PKE, such as complete non-malleability (CNM) and plaintext-awareness (PA). We then...
Recently, researchers have proposed many non-interactive deniable authentication (NIDA) protocols. Most of them claim that their protocols possess full deniability. However, after reviewing, we found that they either cannot achieve full deniability, or suffer KCI or SKCI attack; moreover, lack efficiency, because they are mainly based on DLP, factoring problem, or bilinear pairings. Due to this observation, and that ECC provides the security equivalence to RSA and DSA by using much smaller...
Deniable authentication protocols allow a sender to authenticate a receiver, in a way that the receiver cannot convince a third party that such authentication (or any authentication) ever took place. In this study, we construct a fully deniable mutual authentication protocol based on RSA signature, and then a deniable authenticated key exchange protocol is constructed from the proposed protocol.
Bideniable encryption allows both sender and receiver in a public-key setting to simultaneously claim that a different message of their choice was transmitted, and support this claim by a good-looking encryption and key-generation randomness, respectively. A weaker version with two variants of algorithms is called flexible or multi-distributional deniability, a stronger one-algorithm version is called full deniability. Bendlin et al. (ASIACRYPT 2011) showed that certain kinds of...
We take a closer look at the Open Protocol for Access Control, Identification, and Ticketing with privacY (OPACITY). This Diffie--Hellman-based protocol is supposed to provide a secure and privacy-friendly key establishment for contactless environments. It is promoted by the US Department of Defense and meanwhile available in several standards such as ISO/IEC 24727-6 and ANSI 504-1. To the best of our knowledge, so far no detailed cryptographic analysis has been publicly available. Thus, we...
We discuss an efficient combination of the cryptographic protocols adopted by the International Civil Aviation Organization (ICAO) for securing the communication of machine readable travel documents and readers. Roughly, in the original protocol the parties first run the Password-Authenticated Connection Establishment (PACE) protocol to establish a shared key and then the reader (optionally) invokes the Active Authentication (AA) protocol to verify the passport's validity. Here, we show that...
The popular Katz-Yung compiler from CRYPTO 2003 can be used to transform unauthenticated group key establishment protocols into authenticated ones. In this paper we present a modication of Katz and Yung's construction which maintains the round complexity of their compiler, but for "typical" unauthenticated group key establishments adds authentication in such a way that deniability is achieved as well. As an application, a deniable authenticated group key establishment with three rounds of...
Traditional hush functions map a large number to a small number such that the reverse-hush has an infinity of solutions, and nonetheless a collision is hard to come by. This primitive is so abundantly useful that one is tempted to extend it such that any number large or small may be mapped to any number larger, or smaller while maintaining the above conditions. This extension would increase the flexibility of the commodity hush primitive, expand its current applications, and likely suggest...
The traditional approach to formalizing ideal-model based definitions of security for multi-party protocols models adversaries (both real and ideal) as centralized entities that control all parties that deviate from the protocol. While this centralized-adversary modeling suffices for capturing basic security properties such as secrecy of local inputs and correctness of outputs against coordinated attacks, it turns out to be inadequate for capturing security properties that involve...
In CRYPTO 1997, Canetti \etal put forward the intruiging notion of \emph{deniable encryption}, which (informally) allows a sender and/or receiver, having already performed some encrypted communication, to produce `fake' (but legitimate-looking) random coins that open the ciphertext to another message. Deniability is a powerful notion for both practice and theory: apart from its inherent utility for resisting coercion, a deniable scheme is also noncommitting (a useful property in...
Traditionally, secure one-round key exchange protocols in the PKI setting have either achieved perfect forward secrecy, or forms of deniability, but not both. On the one hand, achieving perfect forward secrecy against active attackers seems to require some form of authentication of the messages, as in signed Diffie-Hellman style protocols, that subsequently sacrifice deniability. On the other hand, using implicit authentication along the lines of MQV and descendants sacrifices perfect...
Cryptography algorithm standards play a key role both to the practice of information security and to cryptography theory research. Among them, the MQV and HMQV protocols ((H)MQV, in short) are a family of implicitly authenticated Diffie-Hellman key-exchange (DHKE) protocols that are among the most efficient and are widely standardized. In this work, from some new perspectives and under some new design rationales, and also inspired by the security analysis of HMQV, we develop a new family of...
Recently, many non-interactive deniable authentication (NIDA) protocols have been proposed. They are mainly composed of two types, signature-based and shared-secrecy based. After reviewing these schemes, we found that the signature-based approach can not deny the source of the message and thus can not achieve full deniability; and that, the shared-secrecy based approach suffers KCI attack although it can achieve full deniability. In addition, both types of schemes lack efficiency...
In this paper, we propose a new notion of timed encryption, in which the encryption is secure within time $t$ while it is totally insecure after some time $T>t.$ We are interested in the case where $t$ and $T$ are both polynomial. We propose a concrete construction that is provably secure in the random oracle model. We show that it can be generically (although inefficient) constructed from a timed commitment of Boneh and Naor (CRYPTO'00). Finally, we apply this primitive to construct a...
Motivated by the problem of establishing a session key among parties based on the possession of certain credentials only, we discuss a notion of attribute-based key establishment. A number of new issues arise in this setting that are not present in the usual settings of group key establishment where unique user identities are assumed to be publicly available. After detailing the security model, we give a two-round solution in the random oracle model. As main technical tool we introduce a...
It is known that composable secure commitments, that is, concurrent non-malleable commitments exist in the plain model, based only on standard assumptions such as the existence of claw-free permutations or even one-way functions. Since being based on the plain model, the deniability of them is trivially satisfied, and especially the latter scheme satisfies also adaptivity, hence it is adaptive-deniable-concurrent non-malleable. However, those schemes cannot be said to be practically...
Tamper-proof devices are pretty powerful. They typically make security applications simpler (provided that the tamper-proof assumption is not violated). For application requiring privacy, we observe that some properties may become harder (if possible at all) to achieve when devices are maliciously used. We take the example of deniability, receipt-freeness, and anonymity. We formalize the trusted agent model which assumes tamper-proof hardware in a way which captures the notion of...
In this work, we develop a family of protocols for deniable Internet Key-Exchange (IKE) with the following properties: 1. item Highly practical efficiency, and conceptual simplicity and clarity. 2. Forward and concurrent (non-malleable) deniability against adversaries with arbitrary auxiliary inputs, and better privacy protection of players' roles. 3. Provable security in the Canetti-Krawczyk post-specified-peer model, and maintenance of essential security properties not captured by the...
In 2003, Boyd et al. have proposed two deniable authenticated key establishment protocols for Internet Key Exchange (IKE). However, both schemes have been broken by Chou et al. in 2005 due to their susceptibility to key-compromise impersonation (KCI) attack. In this paper, we put forward the improved variants of both Boyd et al.'s schemes in order to defeat the KCI attack. On top of justifying our improvements, we further present a detailed security analysis to ensure that the desired...
Deniability is defined as a privacy property which enables protocol principals to deny their involvement after they had taken part in a particular protocol run. Lately, Chou et al. had proposed their ID-based deniable authentication protocol after proving the vulnerability to Key-Compromise Impersonation (KCI) attack in Cao et al.'s protocol. In addition, they claimed that their protocol is not only secure, but also able to achieve both authenticity and deniability properties. However, in...
Cryptographic protocols are often designed and analyzed under some trusted setup assumptions, namely in settings where the participants have access to global information that is trusted to have some basic security properties. However, current modeling of security in the presence of such setup falls short of providing the expected security guarantees. A quintessential example of this phenomenon is the deniability concern: there exist natural protocols that meet the strongest known composable...
We describe and prove (in the random-oracle model) the security of a simple but efficient zero-knowledge identification scheme, whose security is based on the computational Diffie-Hellman problem. Unlike other recent proposals for efficient identification protocols, we don't need any additional assumptions, such as the Knowledge of Exponent assumption. From this beginning, we build a simple key-exchange protocol, and prove that it achieves `SK-security' -- and hence security in Canetti's...
As a useful means of safeguarding privacy of communications, deniable authentication has received much attention. A Chameleon-based deniable authenticated key agreement protocol is presented in this paper. The protocol has following properties. Any one of the two participants can’t present a digital proof to convince a third party that a claimed agreement has really taken place. Once a forgery occurs, the original entity can present a digital proof to disclose the forgery.
We extend the definitional work of Dwork, Naor and Sahai from deniable authentication to deniable key-exchange protocols. We then use these definitions to prove the deniability features of SKEME and SIGMA, two natural and efficient protocols which serve as basis for the Internet Key Exchange (IKE) protocol. The two protocols require distinct approaches to their deniability analysis, hence highlighting important definitional issues as well as necessitating different tools in the...
Deniable Authentication protocols allow a Sender to authenticate a message for a Receiver, in a way that the Receiver cannot convince a third party that such authentication (or any authentication) ever took place. We present two new approaches to the problem of deniable authentication. The novelty of our schemes is that they do not require the use of CCA-secure encryption (all previous known solutions did), thus showing a different generic approach to the problem of deniable authentication....
To a cryptographer the claim that “Shannon Security was achieved with keys smaller than the encrypted message" appears unworthy of attention, much as the claim of “perpetuum mobile” is to a physicist. Albeit, from an engineering point of view solar cells which power satellites exhibit an “essential perpetuum mobile” and are of great interest. Similarly for Shannon Security, as it is explored in this article. We discuss encryption schemes designed to confound a diligent cryptanalyst...
Abstract. The prevailing cryptographies are attacked on the basis of the fact that only a single element in the key space will match a plausible plaintext with a given ciphertext. Any cryptography that would violate this unique-key assumption, will achieve added security through deniability (akin to One Time Pad). Such cryptography is being described. It is achieved by breaking away from the prevailing notion that the key is a binary string of a fixed length. The described key is random-size...
Consider a situation in which the transmission of encrypted messages is intercepted by an adversary who can later ask the sender to reveal the random choices (and also the secret key, if one exists) used in generating the ciphertext, thereby exposing the cleartext. An encryption scheme is <B>deniable</B> if the sender can generate `fake random choices' that will make the ciphertext `look like' an encryption of a different cleartext, thus keeping the real cleartext private. Analogous...
