Paper 2021/1176

Amortized Threshold Symmetric-key Encryption

Mihai Christodorescu, Sivanarayana Gaddam, Pratyay Mukherjee, and Rohit Sinha

Abstract

Threshold cryptography enables cryptographic operations while keeping the secret keys distributed at all times. Agrawal et al. (CCS'18) propose a framework for Distributed Symmetric-key Encryption (DiSE). They introduce a new notion of Threshold Symmetric-key Encryption (TSE), in that encryption and decryption are performed by interacting with a threshold number of servers. However, the necessity for interaction on each invocation limits performance when encrypting large datasets, incurring heavy computation and communication on the servers. This paper proposes a new approach to resolve this problem by introducing a new notion called Amortized Threshold Symmetric-key Encryption (ATSE), which allows a "privileged" client (with access to sensitive data) to encrypt a large group of messages using a single interaction. Importantly, our notion requires a client to interact for decrypting each ciphertext, thus providing the same security (privacy and authenticity) guarantee as DiSE with respect to a "not-so-privileged" client. We construct an ATSE scheme based on a new primitive that we formalize as flexible threshold key-derivation (FTKD), which allows parties to interactively derive pseudorandom keys in different modes in a threshold manner. Our FTKD construction, which uses bilinear pairings, is based on a distributed variant of left/right constrained PRF by Boneh and Waters (Asiacrypt'13). Despite our use of bilinear maps, our scheme achieves significant speed-ups due to the amortized interaction. Our experiments show 40x lower latency and 30x more throughput in some settings.

Note: Added Page number

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. MAJOR revision.ACM CCS 2021
DOI
10.1145/3460120.3485256
Keywords
Threshold CryptographyConstraint PRFDistributed PRF
Contact author(s)
pratyay85 @ gmail com
History
2021-09-17: revised
2021-09-14: received
See all versions
Short URL
https://ia.cr/2021/1176
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1176,
      author = {Mihai Christodorescu and Sivanarayana Gaddam and Pratyay Mukherjee and Rohit Sinha},
      title = {Amortized Threshold Symmetric-key Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1176},
      year = {2021},
      doi = {10.1145/3460120.3485256},
      note = {\url{https://eprint.iacr.org/2021/1176}},
      url = {https://eprint.iacr.org/2021/1176}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.