Strongly multiplicative and 3-multiplicative linear secret sharing schemes

Zhifang Zhang*, Mulan Liu, Yeow Meng Chee, San Ling, Huaxiong Wang

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapter

4 Citations (Scopus)

Abstract

Strongly multiplicative linear secret sharing schemes (LSSS) have been a powerful tool for constructing secure multi-party computation protocols. However, it remains open whether or not there exist efficient constructions of strongly multiplicative LSSS from general LSSS. In this paper, we propose the new concept of 3-multiplicative LSSS, and establish its relationship with strongly multiplicative LSSS. More precisely, we show that any 3-multiplicative LSSS is a strongly multiplicative LSSS, but the converse is not true; and that any strongly multiplicative LSSS can be efficiently converted into a 3-multiplicative LSSS. Furthermore, we apply 3-multiplicative LSSS to the computation of unbounded fan-in multiplication, which reduces its round complexity to four (from five of the previous protocol based on multiplicative LSSS). We also give two constructions of 3-multiplicative LSSS from Reed-Muller codes and algebraic geometric codes. We believe that the construction and verification of 3-multiplicative LSSS are easier than those of strongly multiplicative LSSS. This presents a step forward in settling the open problem of efficient constructions of strongly multiplicative LSSS from general LSSS.

Original languageEnglish
Title of host publicationAdvances in Cryptology - ASIACRYPT 2008
Subtitle of host publication14th International Conference on the Theory and Application of Cryptology and Information Security, Melbourne, Australia, December 7-11, 2008. Proceedings
EditorsJosef Pieprzyk
Place of PublicationBerlin
PublisherSpringer, Springer Nature
Pages19-36
Number of pages18
ISBN (Electronic)9783540892557
ISBN (Print)3540892540, 9783540892540
DOIs
Publication statusPublished - 2008
Event14th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2008 - Melbourne, VIC, Australia
Duration: 7 Dec 200811 Dec 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5350 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other14th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2008
CountryAustralia
CityMelbourne, VIC
Period7/12/0811/12/08

Fingerprint Dive into the research topics of 'Strongly multiplicative and 3-multiplicative linear secret sharing schemes'. Together they form a unique fingerprint.

Cite this