SECRET MODULUS CONVERSION SYSTEM, DISTRIBUTED PROCESSING APPARATUS, SECRET MODULUS CONVERSION METHOD, PROGRAM

1 . A secure modulus conversion system including n pieces of distributed processing apparatuses wherein:

n pieces of the distributed processing apparatuses each include a first secret sharing conversion circuitry, a bit decomposition circuitry, an addition circuitry, a first modulus conversion circuitry, a second modulus conversion circuitry, a second secret sharing conversion circuitry, and a sure computation circuitry;

two distributed processing apparatuses p 0 , p 1 of n pieces of the distributed processing apparatuses each include a second modulus conversion circuitry,

it is assumed that a share ((a)) p is a (k,n)-secret-sharing share of a plain text a by modulo p, where n in (k,n)-secret-sharing is any one of an integer of 3 or more, k is any one of an integer of 2 or more and less than n, and it is assumed that a share <a> p is a (k,k)-additive-secret-sharing share of a plain text a by modulo p;

n pieces of the first secret sharing conversion circuitries configured to convert (k,n)-secret-sharing share ((a)) p into (k,k)-additive-secret-sharing share <a> p of shares which distributed processing apparatuses p 0 and p 1 have;

the bit decomposition circuitry of the distributed processing apparatus p 0 configured to calculate a′ 0 :—<a> p 0 +(2 |p| −p) by using a share <a> p 0 ;

n pieces of the bit decomposition circuitries configured to perform (k,n)-secret-sharing of each bit of a′ 0 to obtain a bit representation share ((a′ 0 )) 2{circumflex over ( )}|p| , perform (k,n)-secret-sharing of each bit of a share <a> p 1 to obtain a bit representation share ((a 1 )) 2{circumflex over ( )}|p| ;

n pieces of the addition circuitries configured to obtain a bit representation share ((a′ 0 +a 1 )) 2{circumflex over ( )}(|p|+1) of a′ 0 +a 1 from the share ((a′ 0 )) 2{circumflex over ( )}|p| and the share ((a 1 )) 2{circumflex over ( )}|p| by an additive circuit;

it is assumed that the most significant bit of the share ((a′ 0 +a 1 )) 2{circumflex over ( )}(|p|+1) is a share ((q)) 2 , n pieces of the first modulus conversion circuitries configured to obtain a share ((q)) Q from the share ((q)) Q by mod 2→mod Q conversion;

two of the second modulus conversion circuitries configured to obtain <a> p 0 mod Q, <a> p 1 mod Q from <a> p 0 , <a> p 1 respectively, and set as a share a′> Q ;

n pieces of the second secret sharing conversion circuitries configured to convert the share <a′> Q into (k,n)-secret-sharing to obtain (k,n)-secret-sharing share ((a′)) Q ; and

n pieces of the sure computation circuitries configured to calculate ((a)) Q =((a′)) Q −p((q)) Q from the share ((a′)) Q and the share ((q)) Q .

2 . A distributed processing apparatus included in a secure modulus conversion system comprising:

it is assumed that a share ((a)) p is a (k,n)-secret-sharing share of a plain text a by modulo p, where n in (k,n)-secret-sharing is any one of an integer of 3 or more, k is any one of an integer of 2 or more and less than n, and it is assumed that a share <a> p is a (k,k)-additive-secret-sharing share of a plain text a by modulo p;

a first secret sharing conversion circuitry configured to convert (k,n)-secret-sharing share ((a)) p into (k,k)-additive-secret-sharing share <a> p of shares which distributed processing apparatuses p 0 and p 1 have together with (n−1) pieces of distributed processing apparatuses;

a bit decomposition circuitry configured to perform (k,n)-secret-sharing of each bit of a′ 0 to obtain a bit representation share ((a′ 0 )) 2{circumflex over ( )}|p| , and perform (k,n)-secret-sharing of each bit of a share <a> p 1 to obtain a bit representation share ((a 1 )) 2{circumflex over ( )}|p| together with (n−1) pieces of distributed processing apparatuses;

an addition circuitry configured to obtain a bit representation share ((a′ 0 +a 1 )) 2{circumflex over ( )}(|p|+1) of a′ 0 +a 1 from the share ((a′ 0 )) 2{circumflex over ( )}|p| and the share ((a 1 )) 2{circumflex over ( )}|p| by an additive circuit together with (n−1) pieces of distributed processing apparatuses;

it is assumed that the most significant bit of the share ((a′ 0 +a 1 )) 2{circumflex over ( )}(|p|+1) is a share ((q)) 2 , a first modulus conversion circuitry configured to obtain a share ((q)) Q from the share ((q)) 2 by mod 2→mod Q conversion together with (n−1) pieces of the distributed processing apparatuses;

it is assumed that <a> p 0 mod Q, <a> p 1 mod Q are set as a share a′> Q , a second secret sharing conversion circuitry configured to convert the share a′> Q into (k,n)-secret-sharing to obtain (k,n)-secret-sharing share ((a′)) Q together with (n−1) pieces of distributed processing apparatuses; and

a sure computation circuitry configured to calculate ((a)) Q =((a′)) Q −p((q)) Q from the share ((a′)) Q and the share ((q)) Q together with (n−1) pieces of distributed processing apparatuses.

3 . a secure modulus conversion method using a secure modulus conversion system including n pieces of distributed processing apparatuses wherein:

n pieces of the distributed processing apparatuses each include a first secret sharing conversion circuitry, a bit decomposition circuitry, an addition circuitry, a first modulus conversion circuitry, a second modulus conversion circuitry, a second secret sharing conversion circuitry, and a sure computation circuitry;

two distributed processing apparatuses p 0 , p 1 of n pieces of the distributed processing apparatuses each include a second modulus conversion circuitry; and comprising:

a first modulus conversion step in which it is assumed that a share ((a)) p is a (k,n)-secret-sharing share of a plain text a by modulo p, where n in (k,n)-secret-sharing is any one of an integer of 3 or more, k is any one of an integer of 2 or more and less than n, and it is assumed that a share <a> p is a (k,k)-additive-secret-sharing share of a plain text a by modulo p,

n pieces of the first secret sharing conversion circuitries convert (k,n)-secret-sharing share ((a)) p into (k,k)-additive-secret-sharing share <a> p of shares which distributed processing apparatuses p 0 and p 1 have;

a bit decomposition step in which it is assumed that a′ 0 :=<a> p 0 +(2 |p| −p), n pieces of the bit decomposition circuitries perform (k,n)-secret-sharing of each bit of a′ 0 to obtain a bit representation share ((a′ 0 )) 2{circumflex over ( )}|p| , perform (k,n)-secret-sharing of each bit of a share <a> p 1 to obtain a bit representation share ((a 1 )) 2{circumflex over ( )}|p| ;

an addition step in which n pieces of the addition circuitries obtain a bit representation share ((a′ 0 +a 1 )) 2{circumflex over ( )}(|p|+1) of a′ 0 +a 1 from the share ((a′ 0 )) 2{circumflex over ( )}|p| and the share ((a 1 )) 2{circumflex over ( )}|p| by an additive circuit;

a first modulus conversion step in which it is assumed that the most significant bit of the share ((a′ 0 +a 1 )) 2{circumflex over ( )}(|p|+1) is a share ((q)) 2 , n pieces of the first modulus conversion circuitries obtain a share ((q)) Q from the share ((q)) 2 by mod 2→mod Q conversion;

a second modulus conversion step in which two of the second modulus conversion circuitries obtain <a> p 0 mod Q, <a> p 1 mod Q from <a> p 0 , <a> p 1 respectively, and set as a share <a′> Q ;

a second secret sharing conversion step in which n pieces of the second secret sharing conversion circuitries convert the share <a′> Q into (k,n)-secret-sharing to obtain (k,n)-secret-sharing share ((a′)) Q ; and

a sure computation step in which n pieces of the sure computation circuitries calculate ((a)) Q =((a′)) Q −p((q)) Q from the share ((a′)) Q and the share ((q)) Q .

4 . A non-transitory computer readable medium that stores a program causing a computer to function as the distributed processing apparatus according to claim 2 .