International Association
for Cryptologic Research

Decentralized Multi-Client Functional Encryption (DMCFE) is a multi-user extension of Functional Encryption (FE) without relying on a trusted third party. However, a fundamental requirement for DMCFE is that the decryptor must collect the partial functional keys and the ciphertexts from all clients. If one client does not generate the partial functional key or the ciphertext, the decryptor cannot obtain any useful information. We found that this strong requirement limits the application of DMCFE in scenarios such as statistical analysis and machine learning. In this paper, we first introduce a new primitive named Robust Decentralized Multi-Client Functional Encryption (RDMCFE), a notion generalized from DMCFE that aims to tolerate the problem of negative clients leading to nothing for the decryptor, where negative clients represent participants that are unable or unwilling to compute the partial functional key or the ciphertext. Conversely, a client is said to be a positive one if it is able and willing to compute both the partial functional key and the ciphertext. In RDMCFE scheme, the positive client set S is known by each positive client such that the generated partial functional keys help to eliminate the influence of negative clients, and the decryptor can learn the function value corresponding to the sensitive data of all positive clients when the cardinality of the set S is not less than a given threshold. We present such constructions for functionalities corresponding to the evaluation of inner products. 1. We provide a basic RDMCFE construction through the technique of double-masking structure, which is inspired by the work of Bonawitz et al. (CCS 2017). The storage and communication overheads of the construction are small and independent of the length of the vector. However, in the basic construction, for the security guarantee, one set of secret keys can be used to generate partial functional keys for only one function. 2. We show how to design the enhanced construction so that partial functional keys for different functions can be generated with the same set of secret keys, at the cost of increasing storage and communication overheads. Specifically, in the enhanced RDMCFE construction, we protect the mask through a single-input FE scheme and a threshold secret sharing scheme having the additively homomorphic property.

Unique signatures are digital signatures with exactly one unique and valid signature for each message. The security reduction for most unique signatures has a natural reduction loss (in the existentially unforgeable against chosen-message attacks, namely EUF-CMA, security model under a non-interactive hardness assumption). In Crypto 2017, Guo {\it et al.} proposed a particular chain-based unique signature scheme where each unique signature is composed of $n$ BLS signatures computed sequentially like a blockchain. Under the computational Diffie-Hellman assumption, their reduction loss is $n\cdot q_H^{1/n}$ for $q_H$ hash queries and it is logarithmically tight when $n=\log{q_H}$. However, it is currently unknown whether a better reduction than logarithmical tightness for the chain-based unique signatures exists. We show that the proposed chain-based unique signature scheme by Guo {\it et al.} must have the reduction loss $q^{1/n}$ for $q$ signature queries when each unique signature consists of $n$ BLS signatures. We use a meta reduction to prove this lower bound in the EUF-CMA security model under any non-interactive hardness assumption, and the meta-reduction is also applicable in the random oracle model. We also give a security reduction with reduction loss $4\cdot q^{1/n}$ for the chain-based unique signature scheme (in the EUF-CMA security model under the CDH assumption). This improves significantly on previous reduction loss $n\cdot q_H^{1/n}$ that is logarithmically tight at most. The core of our reduction idea is a {\em non-uniform} simulation that is specially invented for the chain-based unique signature construction.

We introduce Multimodal Private Signature (MPS) - an anonymous signature system that offers a novel accountability feature: it allows a designated opening authority to learn \emph{some partial information}~$\ms{op}$ about the signer's identity $\ms{id}$, and nothing beyond. Such partial information can flexibly be defined as $\ms{op} = \ms{id}$ (as in group signatures), or as $\ms{op} = \mb{0}$ (like in ring signatures), or more generally, as $\ms{op} = G_j(\ms{id})$, where $G_j(\cdot)$ is certain disclosing function. Importantly, the value of $op$ is known in advanced by the signer, and hence, the latter can decide whether she/he wants to disclose that piece of information. The concept of MPS significantly generalizes the notion of tracing in traditional anonymity-oriented signature primitives, and can enable various new and appealing privacy-preserving applications. We formalize the definitions and security requirements for MPS. We next present a generic construction to demonstrate the feasibility of designing MPS in a modular manner and from commonly used cryptographic building blocks (ordinary signatures, public-key encryption and NIZKs). We also provide an efficient construction in the standard model based on pairings, and a lattice-based construction in the random oracle model.