Differential privacy is a fundamental concept for protecting individual privacy in databases while enabling data analysis. Conceptually, it is assumed that the adversary has no direct access to the database, and therefore, encryption is not necessary. However, with the emergence of cloud computing and the << on-cloud >> storage of vast databases potentially contributed by multiple parties, it is becoming increasingly necessary to consider the possibility of the adversary having (at least partial) access to sensitive databases. A consequence is that, to protect the on-line database, it is now necessary to employ encryption. At PoPETs'19, it was the first time that the notion of differential privacy was considered for encrypted databases, but only for a limited type of query, namely histograms. Subsequently, a new type of query, summation, was considered at CODASPY'22. These works achieve statistical differential privacy, by still assuming that the adversary has no access to the encrypted database. In this paper, we take an essential step further by assuming that the adversary can eventually access the encrypted data, making it impossible to achieve statistical differential privacy because the security of encryption (beyond the one-time pad) relies on computational assumptions. Therefore, the appropriate privacy notion for encrypted databases that we target is computational differential privacy, which was introduced by Beimel et al. at CRYPTO '08. In our work, we focus on the case of functional encryption, which is an extensively studied primitive permitting some authorized computation over encrypted data. Technically, we show that any randomized functional encryption scheme that satisfies simulation-based security and differential privacy of the output can achieve computational differential privacy for multiple queries to one database. Our work also extends the summation query to a much broader range of queries, specifically linear queries, by utilizing inner-product functional encryption. Hence, we provide an instantiation for inner-product functionalities by proving its simulation soundness and present a concrete randomized inner-product functional encryption with computational differential privacy against multiple queries. In terms of efficiency, our protocol is almost as practical as the underlying inner product functional encryption scheme. As evidence, we provide a full benchmark, based on our concrete implementation for databases with up to 1 000 000 entries. Our work can be considered as a step towards achieving privacy-preserving encrypted databases for a wide range of query types and considering the involvement of multiple database owners.

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.

We introduce Anonymous Identity Based Encryption with Traceable Identities, in which we provide a new feature to anonymous identity-based encryption schemes: lifting the anonymity of some specific recipients in necessary situations (such as when they are suspected as criminals). Our primitive allows a tracer, given a tracing key associated to an identity, to filter all the ciphertexts that are sent to this specific identity (and only those). As it is primordial to preserve the privacy of the law-abiding users, the security takes into account the collusion of tracers and corrupted users.

Lightweight devices, such as a smartcard associated with a top‐box decoder in pay‐TV or a SIM card coupled with a powerful (but not totally trusted) smartphone, play an important role in modern applications. The essential requirements for a cryptographic scheme to be truly implemented in lightweight devices are that it should have compact secret key size and support fast decryption. Attribute‐based broadcast encryption (ABBE) combines the functionalities of both broadcast encryption and attribute‐based encryption in an efficient way, ABBE is therefore a promising cryptographic scheme to be used in practical applications such as mobile pay‐TV, satellite transmission, or Internet of Things. Designing an ABBE scheme which can be truly implemented in lightweight devices is still an open question. In this study, the authors solve it by proposing an efficient constant‐size private key ciphertext‐policy ABBE scheme for disjunctive normal form supporting fast decryption and achieving standard security levels of an ABBE scheme. They concretely show that the authors’ scheme can be truly implemented in a prototype for a smartphone‐based cloud storage use case. In particular, they show how to alleviate some parts of their scheme so as to obtain a very practical system, and they give some concrete benchmarks.

We provide efficient constructions for trace-and-revoke systems with public traceability in the black-box confirmation model. Our constructions achieve adaptive security, are based on standard assumptions and achieve significant efficiency gains compared to previous constructions.

Broadcast encryption aims at sending a content to a large arbitrary group of users at once. Currently, the most efficient schemes provide constant-size headers, that encapsulate ephemeral session keys under which the payload is encrypted. However, in practice, and namely for pay-TV, providers have to send various contents to different groups of users. Headers are thus specific to each group, one for each channel: as a consequence, the global overhead is linear in the number of channels. Furthermore, when one wants to zap to and watch another channel, one has to get the new header and decrypt it to learn the new session key: either the headers are sent quite frequently or one has to store all the headers, even if one watches one channel only. Otherwise, the zapping time becomes unacceptably long.

Inspired by the fact that many e-mail addresses correspond to groups of users, Abdalla introduced the notion of identity-based encryption with wildcards (WIBE), which allows a sender to simultaneously encrypt messages to a group of users matching a certain pattern, defined as a sequence of identity strings and wildcards. This notion was later generalized by Abdalla, Kiltz, and Neven, who considered more general delegation patterns during the key derivation process. Despite its many applications, current constructions have two significant limitations: 1) they are only known to be fully secure when the maximum hierarchy depth is a constant; and 2) they do not hide the pattern associated with the ciphertext. To overcome these, this paper offers two new constructions. First, we show how to convert a WIBE scheme of Abdalla into a (nonanonymous) WIBE scheme with generalized key delegation (WW-IBE) that is fully secure even for polynomially many levels. Then, to achieve anonymity, we initially consider hierarchical predicate encryption (HPE) schemes with more generalized forms of key delegation and use them to construct an anonymous WW-IBE scheme. Finally, to instantiate the former, we modify the HPE scheme of Lewko to allow for more general key delegation patterns. Our proofs are in the standard model and use existing complexity assumptions.