Secret Sharing and Secure Computing from Monotone Formulae

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

Secret Sharing and Secure Computing from Monotone Formulae

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

Department of Computer Science

Research output: Working paper/Preprint › Working paper › Research

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

Original language	English
Number of pages	23
Publication status	Published - 2012

Keywords

cryptographic protocols

Access to Document

http://eprint.iacr.org/2012/536

Cite this

@techreport{4de6b8b30fe2492f8379937e4bca59b4,

title = "Secret Sharing and Secure Computing from Monotone Formulae",

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{\aa}rd and Ishai",

keywords = "cryptographic protocols ",

author = "Damg{\aa}rd, {Ivan Bjerre} and Jonas K{\"o}lker and Miltersen, {Peter Bro}",

note = "Cryptology ePrint Archive, Report 2012/536. 11 Sep 2012: 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.",

year = "2012",

language = "English",

type = "WorkingPaper",

}

TY - UNPB

T1 - Secret Sharing and Secure Computing from Monotone Formulae

AU - Damgård, Ivan Bjerre

AU - Kölker, Jonas

AU - Miltersen, Peter Bro

N1 - Cryptology ePrint Archive, Report 2012/536. 11 Sep 2012: 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.

PY - 2012

Y1 - 2012

N2 - 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

AB - 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

KW - cryptographic protocols

M3 - Working paper

BT - Secret Sharing and Secure Computing from Monotone Formulae

ER -

Secret Sharing and Secure Computing from Monotone Formulae

Abstract

Keywords

Access to Document

Fingerprint

Cite this