Multiplicative secret sharing schemes from Reed-Muller type codes

摘要

Multiplicative linear secret sharing schemes are the building blocks for multiparty computation protocols. Such schemes can be defined in terms of linear codes with an additional algebraic structure. We show that Reed-Muller codes have the required additional structure and we introduce a more general class of Reed-Muller type codes suitable for linear secret sharing and multiparty computation. The codes have highly structured generator and parity check matrices that can be used for very efficient implementations over the binary field.