Cryptology ePrint Archive: Report 2017/718

Conditionally Secure Secrecy Computation using Secret Sharing Scheme for n<2k-1 (full paper)

Ahmad Akmal Aminuddin Mohd Kamal and Keiichi Iwamura

Abstract: Typically, when secrecy multiplication is performed in multiparty computation using Shamir’s (k,n) threshold secret sharing scheme, the result is a polynomial with degree of 2k-2 instead of k-1. This causes a problem where, in order to reconstruct a multiplication result, the number of polynomials needed will increase from k to 2k-1. Shingu et al. proposed a method to solve the problem that the degree of polynomial increases when secrecy multiplication is performed by using the (scalar value×polynomial) approach instead of the typical (polynomial×polynomial). However, this method is not secure when a combination operation, such as a product-sum operation, is performed. In this paper, we propose a multiparty computation that uses a secret sharing scheme that is secure against a product-sum operation but does not increase the degree of polynomial of the output. We prove that all combinations of the basic operations (addition, subtraction, multiplication, and division) can be performed securely using this scheme. We also propose three preconditions and finally show that our proposed method is information-theoretic secure against a passive adversary.

Category / Keywords: cryptographic protocols / conditionally secure, secret sharing, secrecy computation, product-sum operation, n<2k-1

Original Publication (with major differences): IEEE Xplore

Date: received 25 Jul 2017

Contact author: ahmad at sec ee kagu tus ac jp

Available format(s): PDF | BibTeX Citation

Version: 20170727:181531 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]