International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: YOLO YOSO: Fast and Simple Encryption and Secret Sharing in the YOSO Model

Authors:
Ignacio Cascudo , IMDEA Software Institute
Bernardo David , IT University Copenhagen
Lydia Garms , Keyless Technologies Limited
Anders Konring , IT University Copenhagen
Download:
Search ePrint
Search Google
Conference: ASIACRYPT 2022
Abstract: Achieving adaptive (or proactive) security in cryptographic protocols is notoriously difficult due to the adversary's power to dynamically corrupt parties as the execution progresses. Inspired by the work of Benhamouda \textit{et al.} in TCC 2020, Gentry \textit{et al.} in CRYPTO 2021 introduced the YOSO (You Only Speak Once) model for constructing adaptively (or proactively) secure protocols in massively distributed settings (\textit{e.g.} blockchains). In this model, instead of having all parties execute an entire protocol, smaller \emph{anonymous committees} are randomly chosen to execute each individual round of the protocol. After playing their role, parties encrypt protocol messages towards the the next anonymous committee and erase their internal state before publishing their ciphertexts. However, a big challenge remains in realizing YOSO protocols: \emph{efficiently} encrypting messages towards anonymous parties selected at random without learning their identities, while proving the encrypted messages are valid with respect to the protocol. In particular, the protocols of Benhamouda \textit{et al.} and of Gentry \textit{et al.} require showing ciphertexts contain valid shares of secret states. We propose concretely efficient methods for encrypting a protocol's secret state towards a random anonymous committee. We start by proposing a very simple and efficient scheme for encrypting messages towards randomly and anonymously selected parties. We then show constructions of publicly verifiable secret (re-)sharing (PVSS) schemes with concretely efficient proofs of (re-)share validity that can be generically instantiated from encryption schemes with certain linear homomorphic properties. In addition, we introduce a new PVSS with proof of sharing consisting of just two field elements, which as far as we know is the first achieving this, and may be of independent interest. Finally, we show that our PVSS schemes can be efficiently realized from our encyption scheme.
BibTeX
@inproceedings{asiacrypt-2022-32542,
  title={YOLO YOSO: Fast and Simple Encryption and Secret Sharing in the YOSO Model},
  publisher={Springer-Verlag},
  author={Ignacio Cascudo and Bernardo David and Lydia Garms and Anders Konring},
  year=2022
}