International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Signature-based Witness Encryption with Compact Ciphertext

Authors:
Gennaro Avitabile , IMDEA Software Institute
Nico Döttling , Helmholtz Center for Information Security
Bernardo Magri , The University of Manchester
Christos Sakkas , The University of Manchester
Stella Wohnig , Helmholtz Center for Information Security and Saarland University
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2024
Abstract: Signature-based witness encryption (SWE) is a recently proposed notion that allows to encrypt a message with respect to a tag $T$ and a set of signature verification keys. The resulting ciphertext can only be decrypted by a party who holds at least $k$ different valid signatures w.r.t. $T$ and $k$ different verification keys out of the $n$ keys specified at encryption time. Natural applications of this primitive involve distributed settings (e.g., blockchains), where multiple parties sign predictable messages, such as polling or randomness beacons. However, known SWE schemes without trusted setup have ciphertexts that scale linearly in the number of verification keys. This quickly becomes a major bottleneck as the system gets more distributed and the number of parties increases. Towards showing the feasibility of SWE with ciphertext size sub-linear in the number of keys, we give a construction based on indistinguishability obfuscation (iO) for Turing machines and a new flavour of puncturable signatures that we call \emph{strongly} puncturable signatures (SPS). SPS allows to generate key pairs which are strongly punctured at a message $T$, meaning that with overwhelming probability no valid signature exists for message $T$ under the punctured key pair. Moreover, punctured keys are indistinguishable from standard non-punctured keys.
BibTeX
@inproceedings{asiacrypt-2024-34590,
  title={Signature-based Witness Encryption with Compact Ciphertext},
  publisher={Springer-Verlag},
  author={Gennaro Avitabile and Nico Döttling and Bernardo Magri and Christos Sakkas and Stella Wohnig},
  year=2024
}