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.

Timed commitments [Boneh and Naor, CRYPTO 2000] are the timed analogue of standard commitments, where the commitment can be non-interactively opened after a pre-specified amount of time passes. Timed commitments have a large spectrum of applications, such as sealed bid auctions, fair contract signing, fair multi-party computation, and cryptocurrency payments. Unfortunately, all practical constructions rely on a (private-coin) trusted setup and do not scale well with the number of participants. These are two severe limiting factors that have hindered the widespread adoption of this primitive.

Ring signatures were introduced by Rivest, Shamir, and Tauman in 2001. These signatures allow a signer to anonymously authenticate a message on behalf of a group of his choice. This concept was then extended by Bresson, Stern, and Szydlo into$t$-out-of-$N$(threshold) ring signatures in 2002. We propose in this article a generalization of Stern's code-based identification (and signature) scheme to design a practical$t$-out-of-$N$threshold ring signature scheme. The size of the resulting signatures is in${\cal O}(N)$and does not depend on$t$, contrary to most of the existing protocols. Our scheme is existentially unforgeable under a chosen message attack in the random oracle model assuming the hardness of the minimum distance problem, is unconditionally source hiding, has a very short public key and has an overall complexity in${\cal O}(N)$. This protocol is the first efficient code-based ring signature scheme and the first code-based threshold ring signature scheme. Moreover it has a better complexity than number-theory based schemes which have a complexity in${\cal O}(Nt)$. This paper is an extended version of a paper published in the conference PQCrypto 2008, with complete proofs and definitions.

Ad hoc networks are dynamic networks formed "on the fly" by a set of nodes. Achieving secure routing in such networks is a big challenge. Asymmetric signature schemes provide mechanisms for authentication, but may result in inefficient implementations, specially when a large number of nodes is expected. Some of these efficiency problems can be mitigated with the use of aggregate signatures, which reduce the space and computations required for managing many different signatures. In this work we formalize a new concept, aggregate designated verifier signature schemes, which is suitable for authentication of routes in reactive protocols. We propose a specific and efficient scheme with provable security in the random oracle model