Complete Characterization of Broadcast and Pseudo-Signatures from Correlations

Varun Narayanan; Vinod M. Prabhakaran; Neha Sangwan; Shun Watanabe

Paper 2023/233

Complete Characterization of Broadcast and Pseudo-Signatures from Correlations

Varun Narayanan, Technion – Israel Institute of Technology

Vinod M. Prabhakaran

, Tata Institute of Fundamental Research

Neha Sangwan

, Tata Institute of Fundamental Research

Shun Watanabe

, Tokyo University of Agriculture and Technology

Abstract

Unconditionally secure broadcast is feasible among parties connected by pairwise secure links only if there is a strict two-thirds majority of honest parties when no additional resources are available. This limitation may be circumvented when the parties have recourse to additional resources such as correlated randomness. Fitzi, Wolf, and Wullschleger (CRYPTO 2004) attempted to characterize the conditions on correlated randomness shared among three parties which would enable them to realize broadcast. Due to a gap in their impossibility argument, it turns out that their characterization is incorrect. Using a novel construction we show that broadcast is feasible under a considerably larger class of correlations. In fact, we realize pseudo-signatures, which are information theoretic counterparts of digital signatures using which unconditionally secure broadcast may be obtained. We also obtain a matching impossibility result thereby characterizing the class of correlations on which three-party broadcast (and pseudo-signatures) can be based. Our impossibility proof, which extends the well-know argument of Fischer, Lynch and Merritt (Distr. Comp., 1986) to the case where parties observe correlated randomness, maybe of independent interest.

Note: Added funding information. Minor updates.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: A major revision of an IACR publication in EUROCRYPT 2023
Keywords: Unconditional security broadcast pseudo-signatures information theory
Contact author(s): varunnkv @ gmail com
vinodmp @ tifr res in
neha_010 @ tifr res in
shunwata @ cc tuat ac jp
History: 2023-02-24: revised; 2023-02-20: received; See all versions
Short URL: https://ia.cr/2023/233
License: CC BY

BibTeX

@misc{cryptoeprint:2023/233,
      author = {Varun Narayanan and Vinod M. Prabhakaran and Neha Sangwan and Shun Watanabe},
      title = {Complete Characterization of Broadcast and Pseudo-Signatures from Correlations},
      howpublished = {Cryptology ePrint Archive, Paper 2023/233},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/233}},
      url = {https://eprint.iacr.org/2023/233}
}