Paper 2012/536

Secret Sharing and Secure Computing from Monotone Formulae

Ivan Bjerre Damgård, Jonas Kölker, and Peter Bro Miltersen

Abstract

We present a construction of log-depth formulae for various threshold functions based on atomic threshold gates of constant size. From this, we build a new family of linear secret sharing schemes that are multiplicative, scale well as the number of players increases and allows to raise a shared value to the characteristic of the underlying field without interaction. Some of these schemes are in addition strongly multiplicative. Our formulas can also be used to construct multiparty protocols from protocols for a constant number of parties. In particular we implement black-box multiparty computation over non-Abelian groups in a way that is much simpler than previously known and we also show how to get a protocol in this setting that is efficient and actively secure against a constant fraction of corrupted parties, a long standing open problem. Finally, we show a negative result on usage of our scheme for pseudorandom secret sharing as defined by Cramer, Damgård and Ishai.

Note: An upcoming version of this paper will include Gil Cohen, Yuval Ishai, Ran Raz and Ron Rothblum as coauthors and will contain several additional results.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
ivan @ cs au dk
History
2012-09-20: received
Short URL
https://ia.cr/2012/536
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/536,
      author = {Ivan Bjerre Damgård and Jonas Kölker and Peter Bro Miltersen},
      title = {Secret Sharing and Secure Computing from Monotone Formulae},
      howpublished = {Cryptology ePrint Archive, Paper 2012/536},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/536}},
      url = {https://eprint.iacr.org/2012/536}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.