Nippon Telegraph and Telephone Corporation

Naoto Kiribuchi

Dai Ikarashi

Koki Hamada

Hiroyoshi Takiguchi

Gembu Morohashi

Teruko Miyata

Ryo Kikuchi

Koji Chida

Hitoshi Fuji

Shigeru Kayaguchi

A secure joining system is a secure joining system including a plurality of secure computing apparatuses. The plurality of secure computing apparatuses include a first vector joining unit, a first permutation calculation unit, a first vector generation unit, a second vector joining unit, a first permutation application unit, a second vector generation unit, a first inverse permutation application unit, a first vector extraction unit, a second permutation application unit, a third vector generation unit, a second inverse permutation application unit, a second vector extraction unit, a modified second table generation unit, a third permutation application unit, a fourth vector generation unit, a shifting unit, a third inverse permutation application unit, a bit inversion unit, a third vector extraction unit, a modified first table generation unit, a first table joining unit, and a first table formatting unit.

Secure joining system, method, secure computing apparatus and program

A relay device transfers a plurality of original data fragments corresponding to a plurality of secret sharing values of original data to a plurality of secure computation devices, transfers, to each of the secure computation devices, a request to send a result fragment based on a secure computation result corresponding to any one of the original data fragments, and transfers the result fragment. The relay device controls timing with which the original data fragments are transferred and timing with which the request to send is transferred.

Secure computation system and relay device, and method, program, and recording medium thereof

A secure equijoin technique of generating one table from two tables while curbing the volume of communications traffic is provided. The technique includes: a first permutation generating meansthat generates a permutation &#x3c;&#x3c3;&#x3e; from an element sequence which is generated from the first column of a table L and the first column of a table R; a first column generating meansthat generates, for j=2, . . . , a, by using the permutation &#x3c;&#x3c3;&#x3e;, a prefix sum, and an inverse permutation &#x3c;&#x3c3;&#x3e;, the j-th column of a table J from an element sequence which is generated from the to j-th column of the table L; a join-result element sequence generating meansthat generates a join-result element sequence from an element sequence ([[1]], . . . , [[1]], [[0]], . . . , [[0]], [[&#x2212;1]], . . . , [[&#x2212;1]]) by using the permutation &#x3c;&#x3c3;&#x3e;, the prefix sum, and the inverse permutation &#x3c;&#x3c3;&#x3e;; a second column generating meansthat generates, for j=a+1, . . . , a+b&#x2212;1, the j-th column of the table J by using the join-result element sequence and the j&#x2212;a+1-th column of the table R; and a third column generating meansthat generates the first column of the table J by using the join-result element sequence and the first column of the table R.

Secure equijoin system, secure equijoin device, secure equijoin method, and program

A database system comprises a determining partdetermining whether or not to conceal information to be registered in a database, a terminal devicethat, if the determining partdetermines that the information is to be concealed, generates N information fragments by secret-sharing the information and sends the N information fragments to a system management device, where N is a predetermined positive integer, the system management devicesending the N information fragments received from the terminal deviceto N different database devices, and N database deviceseach storing one of N information fragments received from the system management device

Database system and database processing method

A vector generation unit generates a vector xso that x[i]&#x2260;x[j] if k[i]=k[j] at i&#x2260;j. A set generation unit generates a set Bso that individual elements correspond to combinations of the N&#x2212;1 pieces of elements, which are individually selected from sets M, . . . , Mother than a set M, and x[j] and the elements for all of the combinations are included. A matrix generation unit generates a matrix T' so that the matrix T&#x2032; includes rows identical to T[j] in the number equal to the number of elements of the set B. A key generation unit generates a vector k&#x2032; so that elements of the matrix T&#x2032; which correspond to a row identical to T[j] correspond to combinations of k[j] and elements of the set Band further, the elements of the set Bare different from each other when there are a plurality of rows identical to T[j].

Matrix and key generation device, matrix and key generation system, matrix coupling device, matrix and key generation method, and program

Determination as to whether a nondecreasing sequence exists or not is efficiently made. A sorting part sorts elements of a set Pin ascending order to generate vectors tand b. A merging part generates vectors tand bby repeating the process of merging vectors (t, b) and (t, b) to generate (t, b). A stable-sorting part generates a vector e by coupling and stably sorting vectors band t. A searching part searches for sets of (&#x3bb;, x, y) in which e[&#x3bb;] is b[x] and e[&#x3bb;+1] is t[y] and generates a set X including all x and a set Y including all y. An extracting part sorts t[x] (x&#x2208;X) in ascending order to generate a vector tand sorts b[y] (y&#x2208;Y) in ascending order to generate a vector b. If the length of a vector tis 0, a determining part outputs a result of determination that indicates the absence of a nondecreasing sequence.

Nondecreasing sequence determining device, method and program

The positions in a text in which partial character strings in a pattern appear are efficiently detected. A partial-character-string position detecting devicetakes inputs of a secret text [t] of a text t, a secrete text &#x3c;p&#x3e; of a pattern p, a secret text &#x3c;c&#x3e; of a vector c, and a secret text &#x3c;E&#x3e; of a matrix E and outputs a secret text &#x3c;H&#x3e; of a matrix H. A first matrix generating partgenerates a secret text &#x3c;F&#x3e; of a matrix F, in which F[i][j]=E[i][j+i mod n+1] (where it is assumed that E[i][n]=&#xac;c[i]). A second matrix generating partgenerates a secret text &#x3c;F'&#x3e; of a matrix F&#x2032;, in which F[i][j]=1 is set if c[i]=0 or if c[i]=1 and F[k][j]=1 for every k that is successively c[k]=1, otherwise F[i][j]=0 is set, where k=i, . . . , n&#x2212;1. A third matrix generating partcomputes &#x3c;H[i][j]&#x3e;=&#x3c;F[i][j&#x2212;i mod n+1]&#x3e;&#x2227;&#x3c;c[i]&#x3e;&#x2227;&#xac;&#x3c;c[i&#x2212;1]&#x3e; to generate the secrete text &#x3c;H&#x3e;.

Device, method and program for detecting positions of partial character strings

Data processing is performed while personal information is kept concealed. A registrant terminal splits a registration input password and allocates the split pieces to secure computation servers. The secure computation servers verify whether the password matches. The registrant terminal splits target data and allocates the data shared values to the secure computation servers. The secure computation servers store the data shared values. A user terminal splits a utilization input password and allocates the split pieces to the secure computation servers. The secure computation servers verify whether the password matches. The user terminal sends a data processing request to the secure computation servers. The secure computation servers execute secure computation of the data shared values to generate processing result shared values. The user terminal recovers the processing result from the processing result shared values.

Growing community of inventors

Musashino, Japan

Naoto Kiribuchi