Secure Computation by Secret Sharing using Input Encrypted with

Random Number

Keiichi Iwamura and Ahmad Akmal Aminuddin Mohd Kamal

Department of Electrical Engineering, Tokyo University of Science, Tokyo, Japan

Keywords: Secure Computation, Multiparty Computation, Secret Sharing, n<2k-1, Information-theoretical Security, Fast

Computation.

Abstract: Typically, unconditionally secure computation using a (𝑘,𝑛) threshold secret sharing is considered

impossible when 𝑛<2𝑘−1. Therefore, in our previous work, we first took the approach of finding the

conditions required for secure computation under the setting of 𝑛<2𝑘−1 and showed that secure

computation using a (𝑘, 𝑛) threshold secret sharing can be realized with a semi-honest adversary under the

following three preconditions: (1) the result of secure computation does not include 0; (2) random numbers

reconstructed by each server are fixed; and (3) each server holds random numbers unknown to the adversary

and holds shares of random numbers that make up the random numbers unknown to the adversary. In this

paper, we show that by leaving condition (3), secure computation with information-theoretic security against

a semi-honest adversary is possible with 𝑘≤𝑛<2𝑘−1. In addition, we clarify the advantage of using secret

information that has been encrypted with a random number as input to secure computation. One of the

advantages is the acceleration of the computation time. Namely, we divide the computation process into a

preprocessing phase and an online phase and shift the cost of communication to the preprocessing phase.

Thus, for computations such as inner product operations, we realize a faster online phase, compared with

conventional methods.

1 INTRODUCTION

Recently, with advancements in big data and the

Internet of Things (IoT), there has been a high

anticipation regarding technology that could make

use of an individual’s information. However, there is

still concern among individuals about the privacy,

security, and confidentiality of their information.

Therefore, to solve this problem, there is a need for a

technology that allows their information to be used

without infringing their privacy. One of the available

technologies that could permit this is called secure

computation, wherein a set of parties with private

inputs wish to compute a joint function of their inputs,

without revealing anything but the output. There are

two main approaches for constructing secure

computation protocols:

─ Secret sharing (Araki et al, 2016; Ben-Or et al,

1988; Cramer et al., 2000; Kamal et al., 2017;

Shingu et al., 2016; Tokita et al., 2018)

─ Homomorphic encryption (Bendlin et al., 2011;

Brakerski et al., 2012; Damgård et al., 2012;

Damgård et al., 2013; Smart et al., 2010; van Dijk

et al., 2010)

However, homomorphic encryption is known to

be expensive in terms of computational cost, and

therefore it requires a much longer computation time.

Therefore, approaches with lower computational cost

are preferable to homomorphic encryption, when

considering the utilization of big data and IoT data.

Secret sharing is a method in which a single input

is divided into multiple shares, which are then

distributed to multiple users. A known example of a

secret sharing is the

(

𝑘,𝑛

)

threshold secret sharing,

where an input 𝑠 is divided into 𝑛 number of shares.

The original input 𝑠 can only be reconstructed or

retrieved from a threshold 𝑘 number of shares, but

any 𝑘 − 1 or smaller number of shares reveals

nothing about the original input. Therefore, when

𝑛>𝑘, a

(

𝑘,𝑛

)

threshold secret sharing can realize

resistance toward loss of at most 𝑛−𝑘 servers.

However, secure computation using a secret

sharing can perform secure addition and subtraction

easily, but this is not so in the case of multiplication.

For example, in the

(

𝑘,𝑛

)

threshold secret sharing

proposed by Shamir (Shamir, 1979), the degree of a

polynomial changes from 𝑘−1 to 2𝑘− 2 for each

multiplication of polynomials. To restore the

540

Iwamura, K. and Kamal, A.

Secure Computation by Secret Sharing using Input Encrypted with Random Number.

DOI: 10.5220/0010552305400547

In Proceedings of the 18th International Conference on Security and Cryptography (SECRYPT 2021), pages 540-547

ISBN: 978-989-758-524-1

multiplication result, the number of shares required

increases from 𝑘 to 2𝑘−1 . Typically,

unconditionally secure computation is considered

impossible when 𝑛<2𝑘−1. Therefore, for most

information-theoretically secure computations using

a secret sharing, it is assumed that 𝑛≥2𝑘−1.

Conversely, there is little research on secure

computation using a secret sharing with 𝑘≤𝑛<

2𝑘− 1 . Methods such as the SPDZ method

(Damgård et al., 2012) have been proposed to

combine secret sharing with homomorphic

encryption to solve this problem. However, this

approach only realizes computational security, not

information-theoretic security. Our research focuses

on realizing secure computation of secret sharing with

𝑘≤𝑛<2𝑘−1; however, we took an approach of

first finding the conditions required to realize

information-theoretic security against semi-honest

adversaries, and then find another method for easing

the conditions required. The result is that we proposed

a secure computation known as the TUS (Tokyo

University of Science) methods (Shingu et al., 2016;

Kamal et al., 2017; Tokita et al., 2018) with the

following three conditions.

(1) The computation result does not include 0.

(2) Random numbers reconstructed by each server

are fixed.

(3) Each server holds random numbers unknown to

the adversary, and the shares of random

numbers that make up the random numbers

unknown to the adversary.

The characteristics of all TUS methods are that

the input of secure computation is first encrypted with

a random number before being used for secure

computation. However, the TUS methods incur high

computational costs and cannot realize fast

computation.

Therefore, in this study, we introduce a method to

improve the TUS methods to provide information-

theoretic security against a semi-honest adversary in

a particular condition with a faster computation

speed. Namely, we divide the computation process

into preprocessing and online phases and shift all

computations related to random numbers to the

preprocessing phase. Thus, we propose a method in

which the communication cost can be totally

eliminated from the online phase (known as the TUS

4 method). Next, we reduce the conditions required in

the TUS methods and show that the TUS methods can

be realized securely with only Condition (3). In

addition, we also discuss the merits and demerits of

the TUS methods.

Our proposed secure computation model is based

on a client/server model where any number of clients

can send shares of their inputs to 𝑛 servers that

perform the computation for the clients and return the

results to them without learning anything.

The remainder of this paper is organized as

follows: in Section 2, we present related works; in

Section 3, we explain the TUS 4 method, in Section 4

we explain the discussion on the merits and demerits

of encrypting inputs with random numbers and

discuss each conditions of the TUS methods. Finally,

in Section 5, we perform an experimental evaluation

and show that the TUS 4 method can realize an

overwhelmingly fast computation speed.

2 RELATED WORKS

2.1 SPDZ Method

Damgård et al. proposed a secure multiparty

computation called SPDZ methods (Damgård et al.,

2012; Damgård et al., 2013) that utilizes a somewhat

homomorphic encryption and is secure against a

dishonest majority with 𝑛=𝑘. SPDZ consists of a

preprocessing and an online phase. SPDZ ensures the

confidentiality of the inputted secrets by using an

additive secret sharing. Moreover, multiplication is

based on Beaver’s circuit randomization (Beaver,

1991), where shares of random numbers

〈

𝑎

〉

〈

𝑏

〉

〈

𝑐

〉

called a multiplicative triple, that satisfy 𝑎∙𝑏=𝑐 are

used. However, the construction of a multiplication

triple requires a fully homomorphic encryption

(Gentry, 2010) where the computation cost is high,

thus significantly increasing the overall process time.

Please refer to Section 2.1 in (Iwamura et al., 2021)

for the detailed protocol of SPDZ method.

2.2 Araki et al.’s Method

Typically, in a secure multiparty computation, the

cost of communication between servers can affect the

overall processing speed more than the actual cost of

computation. Therefore, Araki et al. proposed a

method for rapid secure computation under the

parameters 𝑛=3,𝑘=2, which requires only one

communication per multiplication (Araki et al.,

2016). Please refer to Section 2.2 in (Iwamura et al.,

2021) for the detailed multiplication protocol.

Note that it is usually not considered a problem,

even if communication is required in the

preprocessing phase. In addition, secure computation

of addition in Araki et al.’s method is performed

locally, where the shares are added together.

Secure Computation by Secret Sharing using Input Encrypted with Random Number

541

2.3 (𝒌,𝒏) Threshold Secret Sharing

A (𝑘,𝑛) threshold secret sharing satisfies both the

conditions stated below:

 Any 𝑘−1, or less, number of shares will reveal

nothing about the input 𝑠.

 Any 𝑘 and above number of shares will allow

for the reconstruction of the input 𝑠.

The classic methods of the (𝑘,𝑛) threshold secret

sharing are Shamir’s (𝑘,𝑛) threshold secret sharing

(Shamir’s method) proposed in (Shamir, 1979) and

the XOR-based method (XOR method) proposed in

(Kurihara et al., 2008). In our protocol, Shamir’s

method was used, and all computations were

performed in modulus 𝑝. The shares of input 𝑠, are

represented by



𝑠







2.4 The TUS Methods

Shingu et al. proposed a 2-inputs-1-output

computation called the TUS 1 method (Shingu et al.,

2016), where the input is first encrypted with a

random number. The encrypted input is momentarily

restored as a scalar value, and multiplication is

realized using the scalar value × polynomial

approach to prevent an increase in the polynomial

degree. However, the TUS 1 method is not capable of

coping with computations that require a combination

of addition/subtraction and multiplication/division.

Kamal et al. introduced an improved method

called the TUS 2 method, where the computation

involving a combination of addition/subtraction and

multiplication/division can also be performed

securely (Kamal et al., 2017). This method was

proven to be secure under the three aforementioned

conditions. However, the TUS 2 method incurs

significantly more computational cost.

Therefore, Tokita et al. realizes a more efficient

method for computation, known as the TUS 3 method

(Tokita et al., 2018), where XOR method of secret

sharing is used. The TUS 3 method also proposed a

way to ease one of the conditions (known as the TUS

3’ method), wherein there are no longer limitation for

the inputs of computation; however, the three

conditions still remain.

Moreover, information in Condition (3) is defined

as follow, where 𝜀=

∏

𝜀







is defined as a random

number unknown to the adversary.



𝜀





=



𝜀









𝜀









,…,



𝜀











Here,



𝜀







is a share of 𝜀 and



𝜀





is a set of share

containing shares of 𝜀 and 𝜀



(used to compute 𝜀).

3 THE TUS 4 METHOD

By dividing the computation process into the

preprocessing phase and online phase, it allows us

to shift parts of the computation that require

communication to the preprocessing phase. This

significantly reduce the cost of communication in the

online phase and speed up the entire process.

Here, instead of the simple product-sum operation

of 𝑎𝑏+ 𝑐, we present a solution for computing the

following extended product-sum operation:

𝑎

,

𝑎

,

…𝑎





,







This allows multiple computations to be

performed at once instead of only one computation of

𝑎𝑏 + 𝑐 each time. However, a single product-sum

operation can also be realized by setting the

parameters 𝑙=2,𝑚



=2,𝑚



=1.

Typically, because Equations (1) and (2) hold,

any computation of (𝑎



𝑎



…𝑎



) can be computed

from

(

𝑎



)

(

𝑎



)

,…,

(

𝑎



)

𝑎



𝑎



(

𝑎



)(

𝑎



)

−

(

𝑎



)

−

(

𝑎



)

+1 (1)

𝑎



𝑎



…𝑎



(

𝑎



…𝑎



)(

𝑎



)

−

(

𝑎



…𝑎



)

(2)

In addition, extending Equation (2) will result in

the following.

𝑎

…𝑎

𝑚

= 

(

−1

)

𝑖

𝑎

𝑗

′

+1

𝑚−𝑖

𝑗′=1

𝑚𝐶𝑚−𝑖

𝑖=0

However, 𝑗



is an element of the combination of

choosing the 𝑚−𝑖 number from 𝑚 number of 𝑎



1. For example, the following holds when 𝑚=3,4.

𝑎

(

𝑎

)(

𝑎

)(

𝑎

)

−

{(

𝑎

)(

𝑎

)

(

𝑎

)(

𝑎

)

(

𝑎

)(

𝑎

)}

(

𝑎

)

(

𝑎

)

(

𝑎

)

}

−1

𝑎

(

𝑎

)(

𝑎

)(

𝑎

)(

𝑎

)

−

{(

𝑎

)(

𝑎

)(

𝑎

)

(

𝑎

)(

𝑎

)(

𝑎

)

(

𝑎

)(

𝑎

)(

𝑎

)

(

𝑎

)(

𝑎

)(

𝑎

)}

{(

𝑎

)(

𝑎

)

(

𝑎

)(

𝑎

)

(

𝑎

)(

𝑎

)

(

𝑎

)(

𝑎

)

(

𝑎

)(

𝑎

)

(

𝑎

)(

𝑎

)}

−{

(

𝑎

)

(

𝑎

)

(

𝑎

)

(

𝑎

)

}

Therefore, when 𝑙=2,𝑚



=3,𝑚



=4, 𝑎



𝑎



𝑎



will be 𝑎

,

𝑎

,

𝑎

,

, and 𝑎



𝑎



𝑎



𝑎



will be

SECRYPT 2021 - 18th International Conference on Security and Cryptography

542

𝑎

,

𝑎

,

𝑎

,

𝑎

,

, thus allowing the following to be

computed.

𝑎

1,1

𝑎

2,1

𝑎

3,1

+𝑎

1,2

𝑎

2,2

𝑎

3,2

𝑎

4,2

In the TUS 4 method, inputs 𝑎

,

,𝑎

,

,….𝑎





,

must be within the modulus 𝑝 and be a number under

𝑝−2. In addition, all random numbers used were

uniformly distributed and did not include the value 0.

Moreover, all other values belong to 𝐺𝐹

(

𝑝

)

, and all

computations are performed with the modulus 𝑝 .

Moreover, we assume that communication between

players and servers is secure. In addition, random

numbers not known to the adversary shown in

Condition (3) are assumed to be 𝜀



()

(ℎ=1,…8),

and shares of all random numbers 𝜀

,

()

used to

construct 𝜀



()

are prepared and stored in the servers

in advance. Moreover, 𝑘 servers in Steps 4 and 5

shown in the preprocessing phase are chosen in

advance from 𝑛 servers. Below, for ease of

understanding, we show our protocol for 𝑚



=3;

however, it can also be extended to any 𝑚



Preprocessing Phase.

1. Dealer 𝐷 generates 𝑘 random numbers

𝑏

(

,

)

,

,𝑏

(

,

)

,

,…,𝑏

(

,

)

,

with respect to inputs

𝑎

,

(

𝑖=1,…,𝑙

)

, computes 𝑏

,

∏

𝑏

(

,

)

,





and sends 𝑏

(

,

)

,

to server 𝑆



2. Dealer 𝐷 performs Step 1. On 𝑎

,

,𝑎

,

3. Dealer 𝐷 sends 𝑏

,

to User 𝑈

,

(

𝑔=1,2,3

)

4. Server 𝑆



(

𝑗=0,…,𝑘−1

)

collects each

𝜀

,

(



)







(𝑢=0,…,𝑘−1,ℎ=1,…,8) and

reconstructs 𝜀

,

(



)

5. Server 𝑆



generates 𝑑



, computes the following,

and sends it to one of the servers (Here, we assume

the server to be server 𝑆



𝑑



𝑏

(

,

)

,

𝑏

(

,

)

,

𝑏

(

,

)

,

𝜀

,

(



)

𝑑



𝑏

(

,

)

,

𝑏

(

,

)

,

𝜀

,

(



)

𝑑



𝑏

(

,

)

,

𝑏

(

,

)

,

𝜀

,

(



)

𝑑



𝑏

(

,

)

,

𝑏

(

,

)

,

𝜀

,

()

𝑑



𝑏

(

,

)

,

𝜀

,

()

𝑑



𝑏

(

,

)

,

𝜀

,

()

𝑑



𝑏

(

,

)

,

𝜀

,

()

𝑑



𝜀

,

()

6. Server 𝑆



computes the following and sends to all

servers.

(

𝑖=1,…,𝑙

)

𝑑

𝑏

,

𝑏

,

𝑏

,

𝜀



(



)

=

𝑑



𝑏

(

,

)

,

𝑏

(

,

)

,

𝑏

(

,

)

,

𝜀

,

(



)





𝑑

𝑏

,

𝑏

,

𝜀



(



)

=

𝑑



𝑏

(

,

)

,

𝑏

(

,

)

,

𝜀

,

(



)





𝑑

𝑏

,

𝑏

,

𝜀



(



)

=

𝑑



𝑏

(

,

)

,

𝑏

(

,

)

,

𝜀

,

(



)





𝑑

𝑏

,

𝑏

,

𝜀



(



)

=

𝑑



𝑏

(

,

)

,

𝑏

(

,

)

,

𝜀

,

(



)





𝑑

𝑏

,

𝜀



(



)

=

𝑑



𝑏

(

,

)

,

𝜀

,

(



)





𝑑

𝑏

,

𝜀



(



)

=

𝑑



𝑏

(

,

)

,

𝜀

,

(



)





𝑑

𝑏

,

𝜀



(



)

=

𝑑



𝑏

(

,

)

,

𝜀

,

(



)





𝑑

𝜀



()

=

𝑑



𝜀

,

()





7. All servers 𝑆



compute and hold the following.



𝑑

𝑏

,

𝑏

,

𝑏

,







𝑑

𝑏

,

𝑏

,

𝑏

,

𝜀



(



)

×𝜀



(



)









𝑑

𝑏

,

𝑏

,







𝑑

𝑏

,

𝑏

,

𝜀



(



)

×𝜀



(



)









𝑑

𝑏

,

𝑏

,







𝑑

𝑏

,

𝑏

,

𝜀



(



)

×𝜀



(



)









𝑑

𝑏

,

𝑏

,







𝑑

𝑏

,

𝑏

,

𝜀



(



)

×𝜀



(



)









𝑑

𝑏

,







𝑑

𝑏

,

𝜀



(



)

×𝜀



(



)









𝑑

𝑏

,







𝑑

𝑏

,

𝜀



(



)

×𝜀



(



)









𝑑

𝑏

,







𝑑

𝑏

,

𝜀



(



)

×𝜀



(



)









𝑑







𝑑

𝜀



()

×𝜀



()







Encryption Phase.

1. User 𝑈

,

compute 𝑏

,

𝑎

,

+1＝𝑏

,

×𝑎

,

1 in regard to its input 𝑎

,

and send to all

servers. (𝑔=1,2,3)．

Online Phase.

1. All servers 𝑆



compute the following.

Secure Computation by Secret Sharing using Input Encrypted with Random Number

543

𝑑 𝑎

,

𝑎

,

𝑎

,













= 𝑏

,

𝑎

,

+1





×𝑏

,

𝑎

,

+1×𝑏

,

𝑎

,

+1

×

𝑑

𝑏

,

𝑏

,

𝑏

,







−𝑏

,

𝑎

,

+1×𝑏

,

𝑎

,

+1

×

𝑑

𝑏

,

𝑏

,







−𝑏

,

𝑎

,

+1×𝑏

,

𝑎

,

+1

×

𝑑

𝑏

,

𝑏

,







−𝑏

,

𝑎

,

+1×𝑏

,

𝑎

,

+1

×

𝑑

𝑏

,

𝑏

,







+𝑏

,

𝑎

,

+1×

𝑑

𝑏

,







+𝑏

,

𝑎

,

+1×

𝑑

𝑏

,







+𝑏

,

𝑎

,

+1×

𝑑

𝑏

,







−



𝑑









Reconstruction Phase.

1. The player collects 𝑑

∑

𝑎

,

𝑎

,

𝑎

,













, 𝑑



from

𝑘 servers 𝑆



, reconstructs 𝑑

∑

𝑎

,

𝑎

,

𝑎

,







,𝑑,

and computes the following.

𝑑

∑

𝑎

,

𝑎

,

𝑎

,







𝑑

= 𝑎

,

𝑎

,

𝑎

,







3.1 Security of the TUS 4 Method

In the proposed method of computation with 𝑡(=

∑

𝑚







) inputs and one output, if 𝑡−1 inputs and

the output are leaked to the adversary, the remaining

input can also be leaked. Similarly, when all 𝑡 inputs

are known to the adversary, the output can also be

leaked to the adversary. Therefore, we consider only

the following two types of adversaries:

Adversary 1 has information on 𝑡−2 inputs and one

output. Adversary 1 has information on the inputs

(and the random number used to encrypt them) and

the information needed to reconstruct the output. In

addition, the adversary also has knowledge of

information from 𝑘−1 server and attempts to learn

the remaining two inputs.

Adversary 2 has information on the 𝑡−1 inputs.

Adversary 2 has information on the inputs (and the

random numbers used to encrypt them). In addition,

the adversary also has knowledge of information from

𝑘−1 servers and attempts to learn the remaining one

input or output of the computation.

Proof of Security of the Preprocessing Phase.

Because our proposed method assumes a semi-honest

adversary, Dealer 𝐷 performs Steps 1–3 correctly and

privately, and sends it to each server and user. Server

𝑆



(

𝑗=0,…,𝑘−1

)

r e c o n s t r u c t 𝜀

,

()

(which is used

to construct 𝜀



()

) in Step 4; however, 𝜀



()

will not

leak from 𝑘−1 servers. In Step 5, server 𝑆



sends its

computed values to server 𝑆



; however, Adversaries

1 and 2 cannot decompose each individual random

number from this information. Therefore,

Adversaries 1 and 2 will not be able to learn

𝑑,𝑏

,

,𝑏

,

,𝑏

,

,𝜀



()

,…,𝜀



()

. In Step 6, Server 𝑆



multiplied all values and broadcast the result;

however, Adversaries 1 and 2 cannot decompose the

information to learn each individual random number.

Moreover, because the random number unknown to

the adversary shown in Condition (3) is used to

compute shares in Step 7, the shares held by each

server can be computed securely.

Therefore, for example, the following statement

is true. The same is true for the remaining shares.

Here, 𝐻(𝑥) represents the entropy of 𝑥.

𝐻

𝑑

𝑏

,

𝑏

,

𝑏

,







=𝐻

𝑑

𝑏

,

𝑏

,

𝑏

,









𝑑

𝑏

,

𝑏

,

𝑏

,

𝜀



(



)



Proof of Security of the Encryption Phase.

Since the input is less than 𝑝−2, even if one is added

to the input, it will not become 0. In addition, a

random number generated by the dealer is secure.

Therefore, the following statement is true and

remains true for the remainder of the inputs.

𝐻(𝑎

,

)=𝐻(𝑎

,

|𝑏

,

𝑎

,

+1)

Proof of Security of the Online Phase.

Security against Adversary 1

Assume that the adversary has information on all

inputs except 𝑎

,

,𝑎

,

. He/she also has information

from 𝑘−1 servers and the result of the computation.

Furthermore, Adversary 1 has information from Step

5 of the preprocessing phase, and also learns

𝑏

,

𝑎

,

+1 from the online phase. In addition,

Adversary 1 learns 𝑑

∑

𝑎

,

𝑎

,

𝑎

,







,𝑑 , and

∑

𝑎

,

𝑎

,

𝑎

,







from the reconstruction phase.

Consequently, Adversary 1 has the following

information (however, 𝑔′,𝑖′ excludes 1,1 and 2,1;

𝜀



(

,

)

means that it relates to the same value; 𝜀

∗

()

i s

used when 𝑖>1 ). By using this information,

Adversary 1 tries to learn about inputs 𝑎

,

,𝑎

,

SECRYPT 2021 - 18th International Conference on Security and Cryptography

544

𝐵=𝑑,𝑎





,

,𝑏





,

,𝑏

,

𝑎

,

+1,𝑏

,

𝑎

,

+1,

𝑏

,

𝑏

,

𝜀



(

,

)

𝑏

,

𝜀



(

,

)

𝑏

,

𝜀



(

,

)

,𝜀



(,)

,𝜀

∗

()



However, because each 𝜀



(



)

is independent,

𝑏

,

,𝑏

,

will not leak. In addition, because 𝜀



(



)

is not

used in the computation, it does not affect the

computation. Therefore, Adversary 1 will not be able

to learn 𝑎

,

,𝑎

,

. Therefore, the following are true:

𝐻𝑎

,

 = 𝐻𝑎

,

𝐵, 𝐻𝑎

,

 = 𝐻𝑎

,

𝐵

The same argument remains valid even for

combination of inputs other than 𝑎

,

,𝑎

,

In addition, in the aforementioned protocol, we

assumed 𝑚



=3 for ease of understanding. However,

even in the case other than 𝑚



=3, values that are not

leaked are not included in B; therefore, the same is

true for any 𝑚



. Therefore, the TUS 4 method is

information-theoretical secure against Adversary 1.

Security against Adversary 2

Assume that the adversary has information on all

inputs except 𝑎

,

in addition to information from

𝑘−1 servers. Furthermore, Adversary 2 has

information from Step 5 of the preprocessing phase,

and also learns 𝑏

,

𝑎

,

+1 from the online phase.

In addition, Adversary 2 learns 𝑘−1 number of

𝑑

∑

𝑎

,

𝑎

,

𝑎

,













,𝑑



from the reconstruction

phase. As a result, Adversary 2 has the following

information (however, 𝑔′,𝑖′ exclude 1,1; 𝜀



(

,

)

used to show that it relates to the same value, and 𝜀

∗

()

is used when 𝑖>1 ). However, 𝑗′ is less than 𝑘−1.

By using this information, Adversary 2 tries to learn

about input 𝑎

,

and output

∑

𝑎

,

𝑎

,

𝑎

,







𝐶

=𝑎

,

,𝑏

,

,𝑏

,

𝑎

,

+1,

𝑑

𝑏

,

𝜀



(

,,,

)

𝑑

𝜀



(

,,,

)

,𝜀

∗

()

,𝑑 𝑎

,

𝑎

,

𝑎

,













,𝑑





However, since each 𝜀



()

is independant, 𝑏

,

and

input 𝑎

,

will not be leaked. Moreover, Adversary 2

learns 𝑘−1 number of 𝑑

∑

𝑎

,

𝑎

,

𝑎

,













,𝑑



However, reconstruction is impossible with 𝑘−1

shares. Therefore, Adversary 2 will not be able to

learn the result of the computation.

The same is true even for inputs other than 𝑎

,

. In

addition, even in the case other than 𝑚



=3, values

that are not leaked are not included in C; therefore,

the same can be said for any 𝑚



.Therefore, the

following statements are true, and the TUS 4 method

is information-theoretical secure against Adversary 2.

𝐻𝑎

,

 = 𝐻𝑎

,

𝐶

𝐻 𝑎

,

𝑎

,

𝑎

,







 = 𝐻

∑

𝑎

,

𝑎

,

𝑎

,







𝐶

Proof of Security of the Reconstruction Phase.

Even if

∑

𝑎

,

𝑎

,

𝑎

,







is equal to 0, because

nothing is leaked from 𝑘 or fewer number of shares

of 𝑑

∑

𝑎

,

𝑎

,

𝑎

,













,𝑑



, Adversary 2 will not

able to learn about the result of the computation.

From the above, because the preprocessing phase

only processes information that does not depend on

any of the inputs, it can be performed in advance.

However, communication is required during the

preprocessing phase. Inputs are introduced in the

encryption phase, and the result is sent to all the

servers. All processes up to this stage are considered

the preprocessing of information. The online phase

uses all the computed values to perform

computations, and no communication is required.

Finally, in the reconstruction phase, the player

collects 𝑑

∑

𝑎

,

𝑎

,

𝑎

,













,𝑑



f r o m 𝑘 s e r v e r s 𝑆



From this, we learn that communication only occurs

in the preprocessing, encryption, and reconstruction

phases, and no communication occurs in the online

phase.

In addition, when 𝑛>𝑘, Steps 4 and 5 of the

preprocessing phase can be performed by 𝑘 servers,

but Step 7 and onwards must be performed by all 𝑛

servers. Therefore, the TUS 4 method is also

realizable when 𝑛≥𝑘. However, when the player

who wishes to reconstruct the result wants to collect

information from any 𝑘 servers in the reconstruction

phase, each server must distribute the values 𝑑



in the

preprocessing phase so that it can be reconstructed

from any 𝑘 servers.

4 DISCUSSION

4.1 Features of the TUS Methods

The TUS methods realize secure computation of

secret sharing by using inputs that has been encrypted

with random numbers. This is a combination of an

encryption with a random number and computation

Secure Computation by Secret Sharing using Input Encrypted with Random Number

545

using secret sharing, and the merits of this approach

are shown below. Please refer to Section 4 in

(Iwamura et al., 2021) for further details on each

feature. Here, Features I and II are realized in all the

TUS methods, but Feature III is realized in this study.

Therefore, we can state that the TUS 4 method

realized all the merits below.

Feature I: Input encrypted with random number can

be made public. In the TUS methods, the encrypted

input can be made public because the input is

encrypted with a random number. However, 𝑘

random numbers that make up the random number

need to be concealed.

Feature II: Secure computation with 𝑛<2𝑘−1 is

possible. Because the inputs are not distributed, but

are encrypted by multiplying with random numbers,

direct multiplication of these encrypted inputs will

not cause any increase in the polynomial degree.

Therefore, we could realize secure computation with

minimal server resources (minimum 𝑛=𝑘=2).

Feature III: Processes involving random numbers

can be computed in advance. Because the processes

in the encryption phase can be separated into multiple

processes such as multiplication with random

numbers, it is possible to realize an additional

preprocessing phase, where only processes related to

random numbers are performed in advance.

Demerit: The disadvantage of encrypting an input

with a random number is that when the input or the

result of the computation is equal to 0, information of

the input or output will be leaked. Therefore,

Condition (1) is required.

4.2 Discussion

Condition (1) is solved using the TUS 4 method,

where the reconstruction of the multiplication result

is only performed by the player that is allowed to

know the result.

Condition (2) is required when 𝑛>𝑘. If the

server or dealer distributes the random number using

secret sharing to all 𝑛 servers, even if 𝑛−𝑘 servers

are broken or lost, a substitute server can reconstruct

the random number that was handled by the broken

server and continue the computation. Thus, realizing

the server loss resistance of secret sharing. However,

it is important that the new server must handle the

same random number as the server that it is

substituting. This can be realized by implementing it

in the algorithm (assuming a semi-honest adversary).

Finally, Condition (3) can be solved depending on

the application considered. For example, when

considering implementation in searchable encryption

(Kamal et al., 2017), because the owner of secret

information will not be the adversary, Condition (3)

can be realized by requesting the owner to generate

random numbers that satisfy Condition (3). Moreover,

the use of a trusted execution environment such as

Intel’s Software Guard Extensions (SGX) (Intel

Corporation, 2015) can also help with the realization of

Condition (3). In future studies, we will consider the

most suitable approach for realizing Condition (3).

Therefore, the TUS 4 method only requires

Condition (3) to realizes secure computation against

a semi-honest adversary.

4.3 Qualitative Comparison

The SPDZ method is limited to the setting 𝑛=𝑘 ,

and Araki et al.’s method is limited to the setting 𝑛=

3,𝑘=2. Only the TUS methods allow for 𝑛,𝑘 to be

set at any value and can realize resistance toward

server loss. Araki et al.’s method uses the setting of

𝑛=3,𝑘=2; however, the computation cannot be

continued even if one server is lost; therefore, it is not

robust against server loss.

However, SPDZ method can accommodate

malicious adversaries. Moreover, Araki et al.

proposed two protocol versions: a protocol with

information-theoretic security and a protocol with

computational security.

5 PERFORMANCE EVALUATION

The evaluation is performed by computing 𝑙=

1,100,10000 -times of inner-product computation

and parameters 𝑛,𝑘 set at 𝑛=𝑘=2 for the TUS 4

method. Inner-product computation is often used in

statistical calculations such as distribution and sum of

squared deviation, meaning that it can be applied to

areas such as searching for gene sequences. In

addition, in the computation of the inner product, no

communication is required in the online phase of the

TUS 4 method. The detailed protocol used is the same

as that of the TUS 4 method when 𝑚



=2.

Tables 1 shows the results of the implementation

of the online phase using Amazon Web Service with

a maximum number of three servers. In particular, we

uses the t2.micro instance with 1 vCPU @ 2.5GHz

and 1GiB of RAM. Because the preprocessing and

encryption phases can be computed in advance, we

did not include a comparison of the processing time

in our evaluation. From Table 1, the TUS 4 method

with no communication in the online phase shows an

overwhelming increase in the computation speed.

SECRYPT 2021 - 18th International Conference on Security and Cryptography

546

Table 1: Comparison with conventional methods (for 𝑙=1,100,10000).

TUS 4 Method SPDZ Method Araki et al.’s Method

𝑙=1 𝑙=100 𝑙=10000 𝑙=1 𝑙=100 𝑙=10000 𝑙=1 𝑙=100 𝑙=10000

Computation [ms] 0.03 0.72 88.9 0.04 0.87 86.4 0.03 1.16 105

Connection

establishmen

[ms]

0 0 0 2.06 2.08 2.06 1.99 2.03 2.01

Communication [ms]

0 0 0 1.71 4.54 278 1.36 2.61 73.3

Total time [ms] 0.03 0.72 88.9 3.81 7.49 367 3.38 5.80 181

6 CONCLUSION

In this paper, we provide a method for easing the

conditions of the TUS methods that realize

information-theoretic security against a semi-honest

adversary when 𝑘≤𝑛<2𝑘−1, and show that it

can be realized by using only one condition. In

addition, we showed that the acceleration of the

computation time is possible by using the property

that processes related to random numbers can be

separated. In addition, we discussed the properties in

detail and showed that our proposed method is also

suitable for use in IoT. We also showed that our

proposed method is the only method that allows for

any 𝑛,𝑘 to be chosen for 𝑛≥𝑘.

In a future study, we will consider the most

suitable methods to solve Condition (3) and consider

a secure computation against malicious adversaries.

REFERENCES

Araki T., Furukawa J., Lindell Y., Nof A., Ohara K., 2016.

High throughput semi-honest secure three-party

computation with an honest majority. In CCS 2016, pp.

805-817. ACM, New York, NY, USA.

Beaver D., 1991. Efficient multiparty protocols using circuit

randomization. In CRYPTO 1991. LNCS, vol 576, pp.

420-432. Springer, Berlin, Heidelberg.

Ben-Or M., Goldwasser S., Wigderson A., 1988.

Completeness theorems for non-cryptographic fault-

tolerant distributed computation.” In STOC 1988, pp. 1-

10. ACM, New York, NY, USA.

Bendlin R., Damgård I., Orlandi C., Zakarias S., 2011. Semi-

homomorphic encryption and multiparty computation.”

In EUROCRYPT 2011. LNCS, vol. 6632, pp. 169-188.

Springer, Berlin, Heidelberg.

Brakerski Z., Gentry C., Vaikuntanathan V., 2009. (Leveled)

fully homomorphic encryption without bootstrapping. In

ITCS 2012, pp. 309-325. ACM, New York, NY, USA.

Cramer R., Damgård I., Maurer U., 2000. General secure

multi-party computation from any linear secret-sharing

scheme. In EUROCRYPT 2000. LNCS, vol 1807, pp.

316-334. Springer, Berlin, Heidelberg.

Damgård I., Pastro V., Smart N., Zakarias S., 2012.

Multiparty computation from somewhat homomorphic

encryption. In CRYPTO 2012. LNCS, vol 7417, pp. 643-

662. Springer, Berlin, Heidelberg.

Damgård I., Keller M., Larraia E., Pastro V., Scholl P., Smart

N.P., 2013. Practical covertly secure MPC for dishonest

majority – Or: Breaking the SPDZ Limits. In ESORICS

2013. LNCS, vol. 8134, pp. 1-18. Springer, Berlin,

Heidelberg.

Gentry C., 2010. A fully homomorphic encryption scheme.”

Ph.D Thesis, Stanford University, Stanford, CA, USA.

Intel Corporation. Intel SGX Evaluation SDK, User’s Guide

for Windows* OS, 2015. https://software.intel.com/sites/

products/sgx-sdk-usersguide-windows/Default.htm.

Iwamura K., Kamal A.A.A.M., 2021. Secure computation by

secret sharing using input encrypted with random

number (full paper). In Cryptology ePrint Archive,

Report 2021/548.

Kamal A.A.A.M., Iwamura K., 2017. Conditionally secure

multiparty computation using secret sharing scheme for

n<2k-1. In PST 2017, pp. 225-230. IEEE, Calgary, AB,

Canada.

Kamal A.A.A.M., Iwamura K., Kang H., 2017. Searchable

encryption of image based on secret sharing scheme. In

APSIPA ASC 2017. IEEE, pp. 1495-1503, Kuala

Lumpur, Malaysia.

Kurihara J., Kiyomoto S., Fukushima K., Tanaka T., 2008. A

new (k,n)-threshold secret sharing scheme and its

extension. In ISC 2008, pp. 455-470, Springer, Berlin,

Heidelberg.

Shamir A., 1979. How to share a secret. Communications of

the ACM, Vol. 22, Issue 11, pp. 612-613. ACM, New

York, NY, USA.

Shingu T., Iwamura K., Kaneda K., 2016. Secrecy

computation without changing polynomial degree in

Shamir’s (k, n) secret sharing scheme. In ICETE 2016,

pp.89-94. Lisbon, Portugal.

Smart N.P., Vercauteren F., 2010. Fully homomorphic

encryption with relatively small key and ciphertext sizes.

In PKC 2010. LNCS, vol. 6056, pp. 420-443. Springer,

Berlin, Heidelberg.

Tokita K., Iwamura K., 2018. Fast secure computation based

on secret sharing scheme for n<2k-1. In MobiSecServ

2018, pp. 1-5. IEEE, Miami Beach, FL.

van Dijk M., Gentry C., Halevi S., Vaikuntanathan V., 2010.

Fully homomorphic encryption over the integers.” In

EUROCRYPT 2010. LNCS, vol. 6110, pp. 24-43.

Springer, Berlin, Heidelberg.

Secure Computation by Secret Sharing using Input Encrypted with Random Number

547