I am a professor of Computer Science at the Dipartimento di Scienze Aziendali -- Management of Innovation Systems of the
Università di Salerno, Salerno, Italy.
My main research area is Theoretical Computer Science with a special focus on Cryptography.
-
Public-Key Anamorphism in (CCA-secure) Public-Key Encryption and Beyond.
CRYPTO 24,
with Duong Hieu Phan and Moti Yung.
[Show/Hide abstract]
The notion of (Receiver-) Anamorphic Encryption was put forth recently to show that a dictator (i.e., an overreaching government), which demands to get the receiver’s private key and even dictates messages to the sender, cannot prevent the receiver from getting an additional covert anamorphic message from a sender. The model required an initial private collaboration to share some secret. There may be settings though where an initial collaboration may be impossible or performance-wise prohibitive, or cases when we need an immediate message to be sent without private key generation (e.g., by any casual sender in need). This situation, to date, somewhat limits the applicability of anamorphic encryption. To overcome this, in this work, we put forth the new notion of “public-key anamorphic encryption,” where, without any initialization, any sender that has not coordinated in any shape or form with the receiver, can nevertheless, under the dictator control of the receiver’s private key, send the receiver an additional anamorphic secret message hidden from the dictator. We define the new notion with its unique new properties, and then prove that, quite interestingly, the known CCA-secure Koppula-Waters (KW) system is, in fact, public-key anamorphic.
We then describe how a public-key anamorphic scheme can support a new hybrid anamorphic encapsulation mode (KDEM) where the public anamorphic part serves a bootstrapping mechanism to activate regular anamorphic messages in the same ciphertext, thus together increasing the anamorphic channel capacity.
Looking at the state of research thus far, we observe that the initial system (Eurocrypt’22) that was shown to have regular anamorphic properties is the CCA-secure Naor-Yung (and other related schemes). Here we identify that the KW CCA-secure scheme also provides a new type of anamorphism. Thus, this situation is hinting that there may be a connection between some types of CCA-secure schemes and some type of anamorphic schemes (in spite of the fact that the goals of the two primitives are fundamentally different); this question is foundational in nature.
Given this, we identify a sufficient condition for a ``CCA-secure scheme which is black-box reduced from a CPA secure scheme'' to directly give rise to an ``anamorphic encryption scheme!'' Furthermore, we identify one extra property of the reduction, that yields a public-key anamorphic scheme as defined in this paper.
-
Efficient Secret Sharing for Large-Scale Applications.
CCS 24,
with Sarvar Patel, Joon Young Seo, and Kevin Yeo.
-
Optimal Non-Adaptive Cell Probe Dictionaries and Hashing.
ICALP 2024,
with
Kasper Green Larsen, Rasmus Pagh, Toniann Pitassi, Kevin Yeo, and Or Zamir.
[Show/Hide abstract]
We present a simple and provably optimal non-adaptive cell probe data structure for the static dictionary problem. Our data structure supports storing a set of n key-value pairs from
[u]X[u] using s words of space and answering key lookup queries in
t=O(lg(u/n)/lg(s/n)) nonadaptive probes.
This generalizes a solution to the membership problem
(i.e., where no values are associated with keys) due to Buhrman et al..
We also present matching lower bounds for the non-adaptive static membership problem in the deterministic setting. Our lower bound implies that both our dictionary algorithm and the preceding membership algorithm are optimal, and in particular that there is an inherent complexity gap in these problems between no adaptivity and one round of adaptivity (with which hashing-based algorithms solve these problems in constant time). Using the ideas underlying our data structure, we also obtain the first implementation of a n-wise independent family of hash functions with optimal evaluation time in the cell probe model.
-
Anamorphic Signatures: Secrecy from a Dictator Who Only Permits Authentication!
CRYPTO 23,
with Miroslaw Kutylowski, Duong Hieu Phan, Moti Yung, and Marcin Zawada:
[Show/Hide abstract]
The goal of this research is to raise technical doubts regarding the usefulness of the repeated attempts by governments to curb Cryptography (aka the “Crypto Wars”), and argue that they, in fact, cause more damage than adding effective control. The notion of Anamorphic Encryption was presented in Eurocrypt’22 for a similar aim. There, despite the presence of a Dictator who possesses all keys and knows all messages, parties can arrange a hidden “anamorphic” message in an otherwise indistinguishable from regular ciphertexts (wrt the Dictator).
In this work, we postulate a stronger cryptographic control setting where encryption does not exist (or is neutralized) since all communication is passed through the Dictator in, essentially, cleartext mode (or otherwise, when secure channels to and from the Dictator are the only confidentiality mechanism). Messages are only authenticated to assure recipients of the identity of the sender. We ask whether security against the Dictator still exists, even under such a strict regime which allows only authentication (i.e., authenticated/ signed messages) to pass end-to-end, and where received messages are determined by/ known to the Dictator, and the Dictator also eventually gets all keys to verify compliance of past signing. To frustrate the Dictator, this authenticated message setting gives rise to the possible notion of anamorphic channels inside signature and authentication schemes, where parties attempt to send undetectable secure messages (or other values) using signature tags which are indistinguishable from regular tags. We define and present implementation of schemes for anamorphic signature and authentication; these are applicable to existing and standardized signature and authentication schemes which were designed independently of the notion of anamorphic messages. Further, some cornerstone constructions of the foundations of signatures, in fact, introduce anamorphism.
-
Limits of Breach-Resistant and Snapshot-Oblivious RAMs.
CRYPTO 23,
with Kevin Yeo.
[Show/Hide abstract]
Oblivious RAMs (ORAMs) are an important cryptographic primitive that enable outsourcing data to a potentially untrusted server while hiding patterns of access to the data. ORAMs provide strong guarantees even in the face of a persistent adversary that views the transcripts of all operations and resulting memory contents. Unfortunately, the strong guarantees against persistent adversaries comes at the cost of efficiency as ORAMs are known to require overhead.
In an attempt to obtain faster constructions, prior works considered security against snapshot adversaries that only have limited access to operational transcripts and memory. We consider -snapshot adversaries that perform s data breaches and views the transcripts of total queries. Promisingly, Du, Genkin and Grubbs [Crypto’22] presented an ORAM construction with O(log L) overhead protecting against (1,L)-snapshot adversaries with
the transcript of L consecutive operations from a single breach.
For small values of L, this outperforms standard ORAMs.
In this work, we tackle whether it is possible to further push this construction beyond a single breach. Unfortunately, we show that protecting against even slightly stronger snapshot adversaries becomes difficult. As our main result, we present an \Omega(log n) lower bound for any ORAM protecting against a (3, 1)-snapshot adversary that performs three breaches and sees the transcript of only one query. In other words, our lower bound holds even if an adversary observes only memory contents during two breaches while managing to view the transcript of only one query in the other breach. Therefore, we surprisingly show that protecting against a snapshot adversary with three data breaches is as difficult as protecting against a persistent adversary.
-
The Self-Anti-Censorship Nature of Encryption: On the Prevalence of Anamorphic Cryptography.
PETS 23,
with Miroslaw Kutylowski, Duong Hieu Phan, Moti Yung, and Marcin Zawada:
[Show/Hide abstract]
As part of the responses to the ongoing crypto wars, the notion of Anamorphic Encryption was put forth. The notion allows private communication in spite of a dictator who is engaged in an extreme form of surveillance and or censorship, where it asks for all private keys and knows and may even dictate all messages. The original work pointed out efficient ways to use two known schemes in the anamorphic mode, bypassing the draconian censorship and hiding information from the all-powerful dictator. A question left open was whether these examples are outlier results or whether anamorphic mode is pervasive in existing systems. Here we answer the above question: we develop new techniques, expand the notion, and show that the notion of Anamorphic Cryptography is, in fact, very much prevalent. We first refine the notion of Anamorphic Encryption with respect to the nature of covert communication. Specifically, we distinguish Single-Receiver Encryption for many to one communication, and Multiple-Receiver Encryption for many to many communication within the group of conspiring users. We then show that Anamorphic Encryption can be embedded in the randomness used in the encryption, and we give families of constructions that can be applied to numerous ciphers. In total the families cover classical encryption schemes, some of which in actual use. Among our examples is an anamorphic channel with much higher capacity than the regular channel. In sum, the work shows the very large extent of the potential futility of control and censorship over the use of strong encryption by the dictator (typical for and even stronger than governments engaging in the ongoing crypto-wars): While such limitations obviously hurt utility which encryption typically brings to safety in computing systems, they essentially, are not helping the dictator. While the actual implications of what we show here and what it means in practice require further policy and legal analyses and perspectives, the technical aspects regarding the issues are clearly showing the futility of the war against Cryptography.
-
Dynamic Volume-Hiding Encrypted Multi-Maps with Applications to Searchable Encryption.
PETS 23,
with Ghous Amjad, Sarvar Patel, Kevin Yeo, and Moti Yung.
[Show/Hide abstract]
We study encrypted storage schemes where a client outsources data to an untrusted third-party server (such as a cloud storage provider) while maintaining the ability to privately query and dynamically update the data. We focus on encrypted multi-maps (EMMs), a structured encryption (STE) scheme that stores pairs of label and value tuples. EMMs allow queries on labels and return the associated value tuple. As responses are variable-length, EMMs are subject to volume leakage attacks introduced by Kellaris et al. [CCS'16]. To prevent these attacks, volume-hiding EMMs were introduced by Kamara and Moataz [Eurocrypt'19] that hide the label volumes (i.e., the value tuple lengths). As our main contribution, we present the first fully dynamic volume-hiding EMMs that are both asymptotically and concretely efficient. Furthermore, they are simultaneously forward and backward private which are the de-facto standard security notions for dynamic STE schemes. Additionally, we implement our schemes to showcase their concrete efficiency. Our experimental evaluations show that our constructions are able to add dynamicity with minimal to no additional cost compared to the prior best static volume-hiding schemes of Patel et al. [CCS'19].
-
Lower Bound Framework for Differentially Private and Oblivious Data Structures.
Eurocrypt 2023, with Kevin Yeo.
[Show/Hide abstract]
In recent years, there has been significant work in studying data structures that provide privacy for the operations that are executed. These primitives aim to guarantee that observable access patterns to physical memory do not reveal substantial information about the queries and updates executed on the data structure. Multiple recent works, including Larsen and Nielsen [Crypto'18], Persiano and Yeo [Eurocrypt'19], Hubáček et al. [TCC'19] and Komargodski and Lin [Crypto'21], have shown that logarithmic overhead is required to support even basic RAM (array) operations for various privacy notions including obliviousness and differential privacy as well as different choices of sizes for RAM blocks and memory cells .
We continue along this line of work and present the first logarithmic lower bounds for differentially private RAMs (DPRAMs) that apply regardless of the sizes of blocks and cells . This is the first logarithmic lower bounds for DPRAMs when blocks are significantly smaller than cells, that is . Furthermore, we present new logarithmic lower bounds for differentially private variants of classical data structure problems including sets, predecessor (successor) and disjoint sets (union-find) for which sub-logarithmic plaintext constructions are known. All our lower bounds extend to the multiple non-colluding servers setting.
We also address an unfortunate issue with this rich line of work where the lower bound techniques are difficult to use and require customization for each new result. To make the techniques more accessible, we generalize our proofs into a framework that reduces proving logarithmic lower bounds to showing that a specific problem satisfies two simple, minimal conditions. We show our framework is easy-to-use as all the lower bounds in our paper utilize the framework and hope our framework will spur more usage of these lower bound techniques.
-
Secure Selections on Encrypted Multi-writer Streams.
ACM Transactions on Privacy and Security, v. 25, no. 1,
with Angelo Massimo Perillo and Alberto Trombetta.
[Show/Hide abstract]
Performing searches over encrypted data is a very current and active area. Several efficient solutions have been provided for the single-writer scenario in which all sensitive data originate with one party (the Data Owner) that encrypts and uploads the data to a public repository. Subsequently, the Data Owner accesses the encrypted data through a Query Processor, which has direct access to the public encrypted repository. Motivated by the recent trend in pervasive data collection, we depart from this model and consider a multi-writer scenario in which the data originate with several and mutually untrusted parties, the Data Sources. In this new scenario, the Data Owner provides public parameters so that each Data Source can add encrypted items to the public encrypted stream; moreover, the Data Owner keeps some related secret information needed to generate tokens so that different Query Sources can decrypt different subsets of the encrypted stream, as specified by corresponding access policies.
We propose security model for this problem that we call Secure Selective Stream (SSS) and give a secure construction for it based on hard problems in Pairing-Based Cryptography. The cryptographic core of our construction is a new primitive, Amortized Orthogonality Encryption, that is crucial for the efficiency of the proposed implementation for SSS.
-
Anamorphic Encryption: Private Communication against a Dictator..
Eurocrypt 2022,
with Duong Hieu Phan and Moti Yung.
[Show/Hide abstract]
Cryptosystems have been developed over the years under the typical prevalent setting which assumes that the receiver’s key is kept secure from the adversary, and that the choice of the message to be sent is freely performed by the sender and is kept secure from the adversary as well. Under these fundamental and basic operational assumptions, modern Cryptography has flourished over the last half a century or so, with amazing achievements: New systems (including public-key Cryptography), beautiful and useful models (including security definitions such as semantic security), and new primitives (such as zero-knowledge proofs) have been developed. Furthermore, these fundamental achievements have been translated into actual working systems, and span many of the daily human activities over the Internet.
However, in recent years, there is an overgrowing pressure from many governments to allow the government itself access to keys and messages of encryption systems (under various names: escrow encryption, emergency access, communication decency acts, etc.). Numerous non-direct arguments against such policies have been raised, such as "the bad guys can utilize other encryption system" so all other cryptosystems have to be declared illegal, or that "allowing the government access is an ill-advised policy since it creates a natural weak systems security point, which may attract others (to masquerade as the government)." It has remained a fundamental open issue, though, to show directly that the above mentioned efforts by a government (called here “a dictator” for brevity) which mandate breaking of the basic operational assumption (and disallowing other cryptosystems), is, in fact, a futile exercise. This is a direct technical point which needs to be made and has not been made to date.
In this work, as a technical demonstration of the futility of the dictator’s demands, we invent the notion of “Anamorphic Encryption” which shows that even if the dictator gets the keys and the messages used in the system (before anything is sent) and no other system is allowed, there is a covert way within the context of well established public-key cryptosystems for an entity to immediately (with no latency) send piggybacked secure messages which are, in spite of the stringent dictator conditions, hidden from the dictator itself! We feel that this may be an important direct technical argument against the nature of governments’ attempts to police the use of strong cryptographic systems, and we hope to stimulate further works in this direction.
-
Limits of Preprocessing for Single-Server PIR.
SODA 22, with Kevin Yeo.
[Show/Hide abstract]
We present a lower bound for the static cryptographic data structure problem of single-server private
information retrieval (PIR). PIR considers the setting where a server holds a database of n entries and
a client wishes to privately retrieve the i-th entry without revealing the index i to the server. In our
work, we focus on PIR with preprocessing where an r-bit hint may be computed in a preprocessing stage
and stored by the server to be used to perform private queries in expected time t. We consider the
public preprocessing setting of Beimel et al. [JoC, 2004] where the hint is publicly available to everyone
including the adversary.
We prove that for any single-server computationally secure PIR with preprocessing it must be that
tr = Ω(n log n) when r = Ω(log n). If r=O(log n), we show that t = Ω(n). Our lower bound holds even
when the scheme errs with probability 1/n^2
and the adversary’s distinguishing advantage is 1/n.
Our work improves upon the tr = Ω(n) lower bound of Beimel et al. [JoC, 2004].
We prove our lower bound in a variant of the cell probe model where only accesses to the memory
are charged cost and computation and accesses to the hint are free. Our main technical contribution
is a novel use of the cell sampling technique (also known as the incompressibility technique) used to
obtain lower bounds on data structures. In previous works, this technique only leveraged the correctness
guarantees to prove lower bounds even when used for cryptographic primitives. Our work combines the
cell sampling technique with the privacy guarantees of PIR to construct a powerful, polynomial-time
adversary that is critical to proving our higher lower bounds.
-
Efficient Boolean Search over Encrypted Data with Reduced Leakage.
ASIACRYPT 21,
with Sarvar Patel, Joon Young Seo, and Kevin Yeo.
[Show/Hide abstract]
We study encrypted storage schemes where a client outsources data to an untrusted third-party server (such as a cloud storage provider) while maintaining the ability to privately query and dynamically update the stored data. We focus on encrypted multi-maps, a structured encryption (STE) scheme that stores pairs of label and value tuples that have several important applications (most notably, to searchable encryption and encrypted SQL databases). Encrypted multi-maps support queries for specific labels that return the associated value tuple. As responses are variable-length, encrypted multi-maps are subject to volume leakage attacks introduced by Kellaris et al. [CCS’16] with several follow-up works (including Grubbs et al. [CCS’18] and Lacharite et al. [SP’18]). To prevent these attacks, volume-hiding encrypted multi-maps were introduced by Kamara and Moataz [Eurocrypt’19] that hide the volume of labels (i.e., the size of the associated value tuple).
As our main contribution, we present the first fully dynamic constructions of volume-hiding encrypted multi-maps that are both asymptotically and concretely efficient. Furthermore, our constructions simultaneously provide forward and backward privacy that are the de-facto standard security notions for dynamic STE schemes (Stefanov et al. [NDSS’14] and Bost [CCS’16]). Additionally, we implement our schemes to showcase their concrete efficiency. Our experimental evaluations show that our constructions are able to add dynamicity with minimal to no additional cost compared to the prior best static volume-hiding schemes of Patel et al. [CCS’20].
-
Lower Bounds for Encrypted Multi-Maps and Searchable Encryption in the Leakage Cell Probe Mode.
CRYPTO 20,
with Sarvar Patel and Kevin Yeo.
[Show/Hide abstract]
We present strong evidence that the leakage of the global key-equality pattern is inherent for any dynamic EMM construction with O(1) efficiency.
In particular, we consider the slightly smaller leakage
where leakage of key-equality between update and query operations is
decoupled and the adversary only learns whether two operations of the
same type are performed on the same key or not.
We show that any EMM with at most decoupled key-equality pattern leakage incurs
Ω(log n) overhead in the leakage cell probe model.
This is tight as there exist ORAM-based constructions of EMMs with logarithmic slowdown that leak no more than the decoupled key-equality pattern (and actually, much less).
