Multiplicative and verifiably multiplicative secret sharing for multipartite adversary structures

被引:0
|
作者
Reo Eriguchi
Noboru Kunihiro
Koji Nuida
机构
[1] The University of Tokyo,
[2] National Institute of Advanced Industrial Science and Technology (AIST),undefined
[3] University of Tsukuba,undefined
[4] Kyushu University,undefined
来源
Designs, Codes and Cryptography | 2023年 / 91卷
关键词
Secure multiparty computation; Multiplicative secret sharing; Verifiability; Multipartite adversary structure; 94A60;
D O I
暂无
中图分类号
学科分类号
摘要
d-Multiplicative secret sharing enables n players to locally compute additive shares of the product of d secrets from their shares. Barkol et al. (Journal of Cryptology, 2010) show that it is possible to construct a d-multiplicative scheme for any adversary structure satisfying the Qd\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$Q_d$$\end{document} property, in which no d sets cover the whole set of players. In this paper, we focus on multipartite adversary structures and propose efficient multiplicative and verifiably multiplicative secret sharing schemes tailored to them. First, our multiplicative scheme is applicable to any multipartite Qd\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$Q_d$$\end{document}-adversary structure. If the number of parts is constant, our scheme achieves a share size polynomial in the number n of players while the general construction by Barkol et al. results in exponentially large share size in the worst case. We also propose its variant defined over smaller fields. As a result, for a special class of bipartite adversary structures with two maximal points, it achieves a constant share size for arbitrary n while the share size of the first scheme necessarily incurs a logarithmic factor of n. Secondly, we devise a more efficient scheme for a special class of multipartite ones such that players in each part have the same weight and a set of players belongs to the adversary structure if and only if the sum of their weights is at most a threshold. Thirdly, if the adversary structure is Qd+1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$Q_{d+1}$$\end{document}, our first scheme is shown to be a verifiably multiplicative scheme that detects incorrect outputs with probability 1. For multipartite adversary structures with a constant number of parts, it improves the worst-case share and proof sizes of the only known general construction by Yoshida and Obana (IEEE Transactions on Information Theory, 2019). Finally, we propose a more efficient verifiably multiplicative scheme by allowing small error probability δ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta $$\end{document} and focusing on a more restricted class of multipartite adversary structures. Our scheme verifies computation of polynomials and can achieve a share size independent of δ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\delta $$\end{document} while the previous construction only works for monomials and results in a share size involving a factor of logδ-1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\log \delta ^{-1}$$\end{document}.
引用
收藏
页码:1751 / 1778
页数:27
相关论文
共 50 条
  • [1] Multiplicative and verifiably multiplicative secret sharing for multipartite adversary structures
    Eriguchi, Reo
    Kunihiro, Noboru
    Nuida, Koji
    DESIGNS CODES AND CRYPTOGRAPHY, 2023, 91 (05) : 1751 - 1778
  • [2] Verifiably Multiplicative Secret Sharing
    Yoshida, Maki
    Obana, Satoshi
    INFORMATION THEORETIC SECURITY, ICITS 2017, 2017, 10681 : 73 - 82
  • [3] Verifiably Multiplicative Secret Sharing
    Yoshida, Maki
    Obana, Satoshi
    IEEE TRANSACTIONS ON INFORMATION THEORY, 2019, 65 (05) : 3233 - 3245
  • [4] Compact Verifiably Multiplicative Secret Sharing
    Yoshida, Maki
    Obana, Satoshi
    PROCEEDINGS OF 2020 INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY AND ITS APPLICATIONS (ISITA2020), 2020, : 437 - 441
  • [5] Hybrid Multiplicative Secret Sharing
    Yoshida, Maki
    2021 IEEE INFORMATION THEORY WORKSHOP (ITW), 2021,
  • [6] On multiplicative linear secret sharing schemes
    Nikov, V
    Nikova, S
    Preneel, B
    PROGRESS IN CRYPTOLOGY -INDOCRYPT 2003, 2003, 2904 : 135 - 147
  • [7] On d-Multiplicative Secret Sharing
    Omer Barkol
    Yuval Ishai
    Enav Weinreb
    Journal of Cryptology, 2010, 23 : 580 - 593
  • [8] On d-Multiplicative Secret Sharing
    Barkol, Omer
    Ishai, Yuval
    Weinreb, Enav
    JOURNAL OF CRYPTOLOGY, 2010, 23 (04) : 580 - 593
  • [9] Strongly Multiplicative and 3-Multiplicative Linear Secret Sharing Schemes
    Zhang, Zhifang
    Liu, Mulan
    Chee, Yeow Meng
    Ling, San
    Wang, Huaxiong
    ADVANCES IN CRYPTOLOGY - ASIACRYPT 2008, 2008, 5350 : 19 - +
  • [10] The multiplicative quantum adversary
    Spalek, Robert
    TWENTY-THIRD ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS, 2008, : 237 - 248