Secure computation device, secure computation method, program, and recording medium

Patent metadata

Field	Value
Publication number	US-11515998-B2
Application number	US-201816638987-A
Country	US
Kind code	B2
Filing date	Aug 16, 2018
Priority date	Aug 22, 2017
Publication date	Nov 29, 2022
Grant date	Nov 29, 2022

Abstract

A secure computation device obtains concealed information {M(i0, . . . , iS−1)} of a table M(i0, . . . , iS−1) having one-variable function values as its members. It is to be noted that M(ib, 0, . . . , ib, S−1) generated by substituting counter values ib, 0, . . . , ib, S−1 into the table M(i0, . . . , iS−1) represents a matrix Mb, γ, μ, which is any one of Mb, 2, 1, . . . , Mb, 3, 2. The secure computation device obtains concealed information {Mb, γ, μ} by secure computation using concealed information {ib, 0}, . . . , {ib, S−1} and the concealed information {M(i0, . . . , iS−1)}, and obtains concealed information {Mb, Γ, MU} of a matrix Mb, Γ, MU, which is obtained by execution of a remaining process including those processes among a process Pj, 1, a process Pj, 2, a process Pj, 3, and a process Pj, 4, that are performed subsequent to a process Pγ, μ.

First claim

What is claimed is:

1. A secure computation device among a plurality of secure computation devices performing secure computation for a block cipher, wherein
B is an integer equal to or greater than 1, R is an integer equal to or greater than 3, S is an integer equal to or greater than 2, U=S 2 holds, F is a finite field, b=0, . . . , B−1 holds, r=1, . . . , R holds, and j=2, R holds,
the secure computation device is configured to perform, in cooperation and in communication over a network with the remaining of the plurality of secure computation devices,
round processing in a first round includes a process P 1, 4 , the process P 1, 4 including processing for obtaining a matrix M b, 1, 4 by adding S counter values i b, 0 , . . . , i b, S−1 to S members in one of columns of an S×S matrix that is formed from members of a round key k 1 ∈ F U of the first round, respectively,
round processing in a jth round includes a process P j, 1 , a process P j, 2 , a process P j, 3 , and a process P j, 4 , the process P j, 1 including processing for obtaining a matrix M b, j, 1 by permutation of members of a matrix M b, j−1, 4 , the process P j, 2 including processing for obtaining a Matrix M b, j, 2 by cyclically shifting members of the matrix M b, j, 1 on a per-row basis, the process P j, 3 including processing for obtaining a matrix M b, j, 3 which has linear sums of S members of each column of the matrix M b, j, 2 as the S members of that column, and the process P j, 4 including processing for obtaining a matrix M b, j, 4 by adding the respective members of a round key k j of the jth round to the respective members of the matrix M b, j, 3 , and
the secure computation device includes processing circuitry configured to
receive concealed information {P b } of plaintext block P b , which is a divided share such that each of the plurality of secure computation devices receive a different share of concealed information {P b } from among concealed information concealed information {P 0 }, . . . , {P B−1 } that is generated based on dividing plaintext P for encryption into plaintext blocks P 0 , . . . , P B−1 and performing secret sharing such that the plaintext block P is concealed from each of the plurality of secure computation devices,

the processing circuitry being further configured to implement:
a table generation unit that performs an early-stage process for obtaining concealed information {M(i 0 , . . . , i S−1 )} of a table M(i 0 , . . . , i S−1 ) having one-variable function values for a variable i=i 0 , . . . , i S−1 as its members, by secure computation using concealed information of any one of round keys k 1 , . . . , k 3 ,
a table calculation unit that obtains concealed information {M b, γ, μ } of a matrix M b, γ, μ for b=0, . . . , B−1 by secure computation using concealed information {i b, 0 }, . . . , {i b, S−1 )} of the counter values i b,0 , . . . , i b, S−1 and the concealed information {M(i 0 , . . . , i S−1 )}, where M(i b, 0 , . . . , i b, S−i ) generated by substituting the counter values i b, 0 , . . . , i b, S−1 into the table M(i 0 , . . . , i S−1 ) represents the matrix M b, γ, μ , which is any one of M b, 2, 1 , . . . , M b, 3, 2 ,
a round processing unit that performs a later-stage process for obtaining concealed information {M b, Γ, MU } of a matrix M b, Γ, MU which is obtained by execution of a remaining process, by secure computation using concealed information of any one of round keys k 2 , . . . , k R+1 and the concealed information {M b, γ, μ }, where the remaining process includes those processes among the process P j, 1 , the process P j, 2 , the process P j, 3 , and the process P j, 4 for j=2, . . . , R that are performed subsequent to a process P γ, μ , and
an addition unit that performs an addition process for obtaining concealed information {C b } of C b =M b, R+1, 4 +P b by secure computation using the obtained concealed information {M b, Γ, MU } of a matrix M b, Γ, MU and the received concealed information {P b } and outputting the concealed information {C b } of C b =M b, R+1, 4 +P b , wherein all of the plurality of secure computation devices output different shares of concealed information {C b } of C b =M b , R+ 1 , 4 +P b which can be reconstructed externally to the plurality of secure computation devices to obtain the plaintext data P.

2. The secure computation device among a plurality of secure computation devices performing secure computation for a block cipher, wherein
B is an integer equal to or greater than 1, R is an integer equal to or greater than 3, S is an integer equal to or greater than 2, U=S 2 holds, F is a finite field, b= 0 , . . . , B−1 holds, r=1, . . . , R holds, and j=2, . . . , R holds,
the secure computation device is configured to perform, in cooperation and in communication over a network with the remaining of the plurality of secure computation devices,
round processing in a first round includes a process P 1, 4 , the process P 1, 4 including processing for obtaining a matrix M b, 1, 4 by adding S counter values i b, 0 , . . . , i b, S−1 to S members in one of columns of an S×S matrix that is formed from members of a round key k 1 ∈ F U of the first round, respectively,
round processing in a jth round includes a process P j, 1 , a process P j, 2 , a process P j, 3 , and a process P j, 4 , the process P j, 1 including processing for obtaining a matrix M b, j, 1 by permutation of members of a matrix M b, j−1, 4 , the process P j, 2 including processing for obtaining a matrix M b, j, 2 by cyclically shifting members of the matrix M b, j, 1 on a per-row basis, the process P j, 3 including processing for obtaining a matrix M b, j, 3 which has linear sums of S members of each column of the matrix M b, j, 2 as the S members of that column, and the process P j, 4 including processing for obtaining a matrix M b, j, 4 by adding the respective members of a round key k j of the jth round to the respective members of the matrix M b, j, 3 , and

the secure computation device includes processing circuitry configured to
receive concealed information {P b } of plaintext block P b , which is a divided share such that each of the plurality of secure computation devices receive a different share of concealed information {P b } from among concealed information concealed information {P 0 }, . . . , {P B−1 } that is generated based on dividing plaintext P for encryption into plaintext blocks P 0 , . . . , P B−1 and performing secret sharing such that the plaintext block P is concealed from each of the plurality of secure computation devices

the processing circuitry being further configured to implement:
a table generation unit that performs an early-state process for obtaining concealed information {M(i 0 , . . . , i S−1 )} of a table M(i 0 , . . . , i S−1 ) having one-variable function values for a variable i=i 0 , . . . , i S−1 as its members, by secure computation using concealed information of any one of round keys k 1 , . . . , k 3 ,
a table calculation unit that obtains concealed information {M b, γ, μ } of a matrix M b, γ, μ for b= 0 , . . . , B− 1 by secure computation using concealed information {i b, 0 }, . . . , {i b, S−1 } of the counter values i b, 0 , . . . , i b, S−1 and the concealed information {M(i 0 , . . . , i S−1 )}, where M(i b, 0 , . . . , i b, S−1 ) generated by substituting the counter values i b, 0 , . . . , i b, S−1 into the table M(i 0 , . . . , i S−1 ) represents the matrix M b, γ, μ , which is any one of the matrix M b, 2, 1 , M b, 2, 2 , M b, 2, 3 , M b, 2, 4 , M b, 3, 1 , or . . . , M b, 3, 2 ,
a round processing unit that performs a later-state process for obtaining concealed information {M b, Γ, MU } of a matrix M b, Γ, MU which is obtained by execution of a remaining process, by secure computation using concealed information of any one of round keys k 2 ,

Assignees

• Nippon Telegraph & Telephone

Inventors

• Ikarashi Dai
• Kikuchi Ryo

Classifications

• H04L2209/46

  Secure multiparty computation, e.g. millionaire problem · CPC title

• H04L9/0637 Primary

  Modes of operation, e.g. cipher block chaining [CBC], electronic codebook [ECB] or Galois/counter mode [GCM] · CPC title

• H04L9/0631 Primary

  Substitution permutation network [SPN], i.e. cipher composed of a number of stages or rounds each involving linear and nonlinear transformations, e.g. AES algorithms · CPC title

• G09C1/00

  Apparatus or methods whereby a given sequence of signs, e.g. an intelligible text, is transformed into an unintelligible sequence of signs by transposing the signs or groups of signs or by replacing them by others according to a predetermined system (cryptographic typewriters G09C3/00) · CPC title