Paper 2024/101

Unconditional Security using (Random) Anonymous Bulletin Board

Albert Yu, Purdue University West Lafayette
Hai H. Nguyen, ETH Zurich
Aniket Kate, Purdue University West Lafayette, Supra Research
Hemanta K. Maji, Purdue University West Lafayette

In a seminal work, Ishai et al. (FOCS–2006) studied the viability of designing unconditionally secure protocols for key agreement and secure multi-party computation (MPC) using an anonymous bulletin board (ABB) as a building block. While their results establish the feasibility of key agreement and honest-majority MPC in the ABB model, the optimality of protocols with respect to their round and communication complexity is not studied. This paper enriches this study of unconditional security in the ABB model in multiple ways. - We present a key agreement protocol with a novel combinatorial insight to offer a 200% throughput over the (FOCS–2006) study; i.e., using the same number of messages, we can (almost) double the bit-length of the agreed key. We also prove the near optimality of our approach. - We offer unconditionally secure protocols for the (random) string oblivious transfer functionalities. We present a $1$-round chosen message random string oblivious transfer and show how to extend it to a non-interactive (random) string oblivious transfer protocol and a $2$-round chosen message string oblivious transfer. - We prove a $1$-round lower bound for BEC under certain conditions. Central to our technical contributions is the abstraction of a distributional variant of the random ABB functionality. Investigating the concrete efficiency of founding MPC from this primitive leads to fascinating new mathematical challenges in well-established MPC models, which will be of broader interest to the community.

Available format(s)
Cryptographic protocols
Publication info
Information Theoretic CryptographyOblivious TransferAnonymous Bulletin Board
Contact author(s)
yu646 @ purdue edu
nhhai196 @ gmail com
aniket @ purdue edu
hmaji @ purdue edu
2024-01-29: revised
2024-01-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Albert Yu and Hai H. Nguyen and Aniket Kate and Hemanta K. Maji},
      title = {Unconditional Security using (Random) Anonymous Bulletin Board},
      howpublished = {Cryptology ePrint Archive, Paper 2024/101},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.