Strongly Multiplicative and 3-Multiplicative Linear Secret Sharing Schemes

被引：0

作者：

Zhang, Zhifang ^{[1
]}

Liu, Mulan ^{[1
]}

Chee, Yeow Meng ^{[2
]}

Ling, San ^{[2
]}

Wang, Huaxiong ^{[2
,3
]}

机构：

[1] Chinese Acad Sci, Acad Math & Syst Sci, Key Lab Math Mech, Beijing, Peoples R China

[2] Nanyang Technol Univ, Sch Phys & Math Sci, Div Math Sci, Singapore, Singapore

[3] Macquarie Univ, Ctr Adv Comput Algorithms and Cryptogra, Dept Comp, N Ryde, NSW 2109, Australia

来源：

ADVANCES IN CRYPTOLOGY - ASIACRYPT 2008 | 2008年 / 5350卷

基金：

新加坡国家研究基金会; 澳大利亚研究理事会;

关键词：

monotone span program; secure multi-party computation; strongly multiplicative linear secret sharing scheme;

D O I：

暂无

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：19 / +

页数：3

共 16 条

[1] [Anonymous], 1996, THESIS TECHNION ISRA
[2] Bar-Ilan J., 1989, Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing, P201, DOI 10.1145/72981.72995
[3] Chen H, 2008, LECT NOTES COMPUT SC, V4965, P451
[4] Chen H, 2006, LECT NOTES COMPUT SC, V4117, P521
[5] Cramer R, 2005, LECT NOTES COMPUT SC, V3621, P327
[6] Cramer R, 2000, LECT NOTES COMPUT SC, V1807, P316
[7] Cramer R, 2007, LECT NOTES COMPUT SC, V4622, P613
[8] FEHR S, 1999, THESIS FEDERAL I TEC
[9] Goldreich O., 1987, STOC, P218, DOI DOI 10.1145/28395.28420
[10] Karchmer M., 1993, Proceedings of the Eighth Annual Structure in Complexity Theory Conference (Cat. No.93CH3281-3), P102, DOI 10.1109/SCT.1993.336536

← 1 2 →