Adaptively Secure Non-interactive Threshold Cryptosystems

Threshold cryptography aims at enhancing the availability and security of decryption and signature schemes by splitting private keys into several (say

n

) shares (typically, each of size comparable to the original secret key). In these schemes, a quorum of at least (

t

 ≤ 

n

) servers needs to act upon a message to produce the result (decrypted value or signature), while corrupting less than

t

servers maintains the scheme’s security. For about two decades, extensive study was dedicated to this subject, which created a number of notable results. So far, most practical threshold signatures, where servers act non-interactively, were analyzed in the limited static corruption model (where the adversary chooses which servers will be corrupted at the system’s initialization stage). Existing threshold encryption schemes that withstand the strongest combination of adaptive malicious corruptions (allowing the adversary to corrupt servers at any time based on its complete view), and chosen-ciphertext attacks (CCA) all require interaction (in the non-idealized model) and attempts to remedy this problem resulted only in relaxed schemes. The same is true for threshold signatures secure under chosen-message attacks (CMA).

To date (for about 10 years), it has been open whether there are non-interactive threshold schemes providing the highest security (namely, CCA-secure encryption and CMA-secure signature) with scalable shares (

i.e.

, as short as the original key) and adaptive security. This paper answers this question affirmatively by presenting such efficient decryption and signature schemes within a unified algebraic framework.