Paper 2020/1329

Adaptively secure Threshold Symmetric-key Encryption

Pratyay Mukherjee

Abstract

In a threshold symmetric-key encryption (TSE) scheme, encryption/decryption is performed by interacting with any threshold number of parties who hold parts of the secret-keys. Security holds as long as the number of corrupt (possibly colluding) parties stay below the threshold. Recently, Agrawal et al. [CCS 2018] (alternatively called DiSE) initiated the study of TSE. They proposed a generic TSE construction based on any distributed pseudorandom function (DPRF). Instantiating with DPRF constructions by Naor, Pinkas and Reingold [Eurocrypt 1999] (also called NPR) they obtained several efficient TSE schemes with various merits. However, their security models and corresponding analyses consider only static (and malicious) corruption, in that the adversary fixes the set of corrupt parties in the beginning of the execution before acquiring any information (except the public parameters) and is not allowed to change that later. In this work we augment the DiSE TSE definitions to the fully adaptive (and malicious) setting, in that the adversary is allowed to corrupt parties dynamically at any time during the execution. The adversary may choose to corrupt a party depending on the information acquired thus far, as long as the total number of corrupt parties stays below the threshold. We also augment DiSE’s DPRF definitions to support adaptive corruption. We show that their generic TSE construction, when plugged-in with an adaptive DPRF (satisfying our definition), meets our adaptive TSE definitions. We provide an efficient instantiation of the adaptive DPRF, proven secure assuming decisional Diffie-Hellman assumption (DDH), in the random oracle model. Our construction borrows ideas from Naor, Pinkas and Reingold’s [Eurocrypt 1999] statically secure DDH-based DPRF (used in DiSE) and Libert, Joye and Yung’s [PODC 2014] adaptively secure threshold signature. Similar to DiSE, we also give an extension satisfying a strengthened adaptive DPRF definition, which in turn yields a stronger adaptive TSE scheme. For that, we construct a simple and efficient adaptive NIZK protocol for proving a specific commit-and-prove style statement in the random oracle model assuming DDH.

Note: Minor formatting changed