Paper 2020/618

Bounds on Ad Hoc Threshold Encryption

Ivan Damgård and Sophia Yakoubov

Abstract

Threshold encryption is encryption to a group of n intended recipients in such a way that any t+1 out of the n recipients together can decrypt, but t or fewer learn nothing about the message. Ad hoc threshold encryption (ATE) is threshold encryption with no trusted setup beyond a PKI (that is, all keys are generated independently). The techniques known in the ad hoc setting suffer either from ciphertexts linear in (n-t) (Daza et. al), or from reliance on cumbersome primitives like indistinguishability obfuscation (Reyzin et. al). In this paper, we set out to determine whether we can get ATE with short ciphertexts from standard primitives. We therefore work in a model where we limit reliance on computational assumptions. We do this by demanding information theoretic security given black-box access to limited cryptographic tools such as non-interactive key exchange and pseudorandom generators. We show that, with access only to idealized two-party key exchange, any secure ATE scheme must produce ciphertexts of size at least (n-t-1)l (where l is the length of the message). If access is additionally given to an idealized PRG, the lower bound on ciphertext size becomes k(n-t)/2 + l (where k is the length of the input to the PRG). If idealized q-party key exchange for q > 2 is availabe, then we can achieve a constant-size ciphertext, at the cost of invoking the key exchange an exponential number of times. We also prove that, if the size of the ciphertext is optimal (that is, equal to the size of the message), the exponential overhead is unavoidable. Finally, we give some alternative constructions demonstrating that the overhead can be reduced at the cost of slightly larger ciphertext size.