Secure reading apparatus, secure writing apparatus, method thereof, and program for reading and writing data in a sequence without revealing an access position

Abstract

Data is efficiently read from a sequence without a read position being revealed. A secure reading apparatus 1 receives a secret text sequence and a secret text of a read position as input, and outputs an element at the read position of the secret text sequence. A vector creating part (12) creates a vector expressing the read position. A compression computing part (13) repeatedly generates a new secret text sequence in which an inner product of a vector based on the secret text sequence and a vector expressing the read position is set as an element. The reading part (14) outputs the new secret text sequence having the number of elements of one as the element at the read position of the secret text sequence.

Claims

1. A secure reading apparatus comprising: an input circuitry configured to receive a secret text sequence and a secret text of a read position as input; a vector creating circuitry configured to create a secret text vector by using the secret text sequence received by the input circuitry and the secret text of a read position; a compression computing circuitry configured to repeat generation of a new secret text sequence in which an inner product of a vector expressing the read position and a vector on of the secret text sequence created by the vector generating circuitry until a number of elements of the new secret text sequence becomes one; a reading circuitry configured to output a secret text sequence having the one element number created by the compression computing circuitry as a secret text at the read position.

2. The secure reading apparatus according to claim 1, wherein n and k are set as integers equal to or greater than 2, and j is set as each integer equal to or greater than 1 and equal to or less than k, the apparatus input circuitry configured to receive the received secret text sequence received and the secret text of a read position as a secret text sequence [a.sub.0]=([a.sub.0[0]], [a.sub.0[1]], . . . , [a.sub.0[n−1]]) having a size n and a secret text [x] of a read position x as input; the reading circuitry is configured to output a secret text [a.sub.0[x]] which is an x-th element of the secret text sequence [a.sub.0], the vector creating circuitry is configured to create a secret text vector [v.sub.j] using the secret text [x] for each integer j, the compression computing circuitry is configured to create a secret text sequence [a.sub.j] using a secret text sequence [a.sub.j-i] and a secret text vector [v.sub.j] for each integer j, and the reading circuitry is configured to output the secret text sequence having the one element number as a secret text sequence [a.sub.k] having the one element number as the secret text [a.sub.0[x]] which is an x-th element of the secret text sequence [a.sub.0].

3. A non-transitory computer readable medium having a program recorded thereon for causing a computer to function as the secure reading apparatus according to claim 1.

4. The secure reading apparatus according to claim 2, wherein m.sub.1, m.sub.2, . . . , m.sub.k are set as natural numbers satisfying n≤m.sub.i×m.sub.2× . . . ×m.sub.k, n.sub.j is set as an integer defined with the following formula, and i is set as each integer equal to or greater than 0 and less than n.sub.j: $n_{j} = .Math. \frac{n}{m_{1} \times m_{2} \times .Math. \times m_{j}} .Math.,$ and the compression computing circuitry creates the secret text sequence [a.sub.j] in which an inner product of a secret text vector [b.sub.j, i] created using the secret text sequence [a.sub.j-1] for each integer i and the secret text vector [v.sub.j] is set as an i-th element.

5. The secure reading apparatus according to claim 4, wherein the processing circuitry creates the secret text vector [v.sub.j] having a size m.sub.j in which an x.sub.j mod m.sub.j-th element is 1 and other elements are 0 while x.sub.j is set as an integer defined with the following formula for each integer j: $x_{j} = .Math. \frac{x}{m_{1} \times m_{2} \times .Math. \times m_{j - 1}} .Math.,$ and creates the secret text vector [b.sub.j, i] in which [b.sub.j, i]=[a.sub.j-1[m.sub.ji+0]], [a.sub.j-1[m.sub.ji+1]], . . . , [a.sub.j-1[m.sub.ji+m.sub.j−1]]), and when λ≥|a.sub.j-i|, [a.sub.j-1[λ]]=0 for each integer i.

6. A secure reading apparatus comprising: an input circuitry configured to receive a secret text sequence and a secret text of a read position as input; a vector creating circuitry configured to create a secret text vector by using the secret text sequence received by the input circuitry and the secret text of a read position; a compression computing circuitry configured to repeat generation of a new secret text sequence in which an inner product of a vector expressing the read position and a vector of the secret text sequence created by the vector generating circuitry until a number of elements of the new secret text sequence becomes one; and a reading circuitry configured to output a secret text sequence having the one element number created by the compression computing circuitry as a secret text at the read position, wherein n and k are set as integers equal to or greater than 2, and j is set as each integer equal to or greater than 1 and equal to or less than k, the input circuitry configured to receives the received secret text sequence received and the secret text of a read position as a secret text sequence [a.sub.0]=([a.sub.0[0]], [a.sub.0[1]], . . . , [a.sub.0[n−1]]) having a size n and a secret text [x] of a read position x as input; the reading circuitry is configured to outputs a secret text [a.sub.0[x]] which is an x-th element of the secret text sequence [a.sub.0], the vector creating circuitry is configured to creates a secret text vector [v.sub.j] using the secret text [x] for each integer j, the compression computing circuitry is configured to creates a secret text sequence [a.sub.j] using a secret text sequence [a.sub.j-1] and a secret text vector [v.sub.j] for each integer j, and the reading circuitry is configured to output the secret text sequence having the one element number as a secret text sequence [a.sub.k] having the one element number as the secret text [a.sub.0[x]] which is an x-th element of the secret text sequence [a.sub.0], wherein m.sub.1, m.sub.2, . . . , m.sub.k are set as natural numbers satisfying n≤m.sub.1×m.sub.2× . . . ×m.sub.k, n.sub.i is set as an integer defined with the following formula, and i is set as each integer equal to or greater than 0 and less than n.sub.j: $n_{j} = .Math. \frac{n}{m_{1} \times m_{2} \times .Math. \times m_{j}} .Math.,$ and the compression computing circuitry creates the secret text sequence [a.sub.j] in which an inner product of a secret text vector [b.sub.j, i] created using the secret text sequence [a.sub.j-1] for each integer i and the secret text vector [v.sub.j] is set as an i-th element, wherein the processing circuitry creates the secret text vector [v.sub.j] having a size m.sub.j in which an x.sub.j mod m.sub.j-th element is 1 and other elements are 0 while x.sub.j is set as an integer defined with the following formula for each integer j: $x_{j} = .Math. \frac{x}{m_{1} \times m_{2} \times .Math. \times m_{j - 1}} .Math.,$ and creates the secret text vector [b.sub.j, i] in which [b.sub.j, i]=([a.sub.j-1[m.sub.ji+0]], [a.sub.j-1[m.sub.ji+1]], . . . , [a.sub.j-1[m.sub.ji+m.sub.j−1]]), and when λ≥|a.sub.j-1|, [a.sub.j-1[λ]]=0 for each integer i, wherein the secret text sequence [a.sub.0] and the secret text [x] are concealed through secret sharing in which, among shares obtained by dividing a plain text into s pieces, if arbitrary t shares are collected, the plain text can be reconstructed, while any information regarding the plain text cannot be obtained from less than t shares, where t is set as an integer equal to or greater than 1, s≥2t−1, and k, m.sub.i (i=1, 2, . . . , k) are defined with the following formula: $k = .Math. \frac{s - 1}{t - 1} .Math., m_{i} = .Math. n^{1 / k} .Math. .$

7. A secure reading method to be executed by a secure reading apparatus, the secure reading method comprising: receiving, by an input circuitry, a secret text sequence and a secret text of a read position as input; creating, by a vector creating circuitry, a secret text vector by using the secret text sequence received by the input circuitry and the secret text of a read position; repeating, by a compression computing circuitry, generation of a new secret text sequence in which an inner product of a vector expressing the read position and a vector of the secret text sequence created by the vector generating circuitry until a number of elements of the new secret text sequence becomes one; outputting by a reading circuitry, a secret text sequence having the one element number created by the compression computing circuitry as a secret text at the read position.

8. A secure writing apparatus comprising: an input circuitry configured to receive a secret text sequence, a secret text of a write address, and a secret text of a value to be written as input; an address decomposing circuitry configured to create an anonymous vector representing the writing of the value indicated by the secret text of the write address to the write address; a vector creating circuitry configured to select an element from the secret text vector and create a vector representing the write address and a vector representing the write value; a writing circuitry configured to add an inner product of a vector expressing the write address and a vector expressing the value to be written to the secret text sequence.

9. The secure writing apparatus according to claim 8, wherein n and m are set as integers equal to or greater than 2, i is set as each integer equal to or greater than 0 and less than m, and j is set as each integer equal to or greater than 0 and less than n, the input circuitry is configured to receive the received secret text sequence received and the secret text of a read position as a secret text sequence [a]=([a[0]], [a[1]], . . . , [a[n−1]]) having a size n, a secret text [x.sub.i] of a write address x and a secret text [y.sub.i] of a value to be written y.sub.i as input; the address decomposing circuitry is configured to create a secret text vector [w.sub.i] which expresses a write address x.sub.i of the value y.sub.i for each integer i, the vector creating circuitry is configured to select an element from the secret text vector [w.sub.i] and create secret text vectors [u.sub.j] and [v.sub.j] for each integer j, and the writing circuitry is configured to add the inner product of a vector expressing the write address and the vector expressing the value to be written to the secret text sequence by adding an inner product of the secret text vector [u.sub.j] and the secret text vector [v.sub.j] for each integer j to the secret text [a[j]] which is a j-th element of the secret text sequence [a].

10. The secure writing apparatus according to claim 9, wherein the processing circuitry concatenates secret text vectors [p.sub.i] and [q.sub.i] in which, when n.sub.2λ.sub.1+λ.sub.2=x.sub.i, p.sub.i[λ.sub.1]q.sub.i[λ.sub.2] becomes [y.sub.i] and otherwise becomes zero, to create the secret text vector [w.sub.i] while n.sub.1 and n.sub.2 are set as natural numbers satisfying n.sub.1n.sub.2≥n, and creates the secret text vectors [u.sub.j] and [v.sub.j] as in the following formula:
[u.sub.j[i]]=[p.sub.i[λ.sub.1]],
[v.sub.j[i]]=[q.sub.i[λ.sub.2]] where i is set as each integer equal to or greater than 0 and less than m, j is set as each integer equal to or greater than 0 and less than n, and λ.sub.1 and λ.sub.2 are set as in the following formula:
λ.sub.1=└j/n.sub.2┘,
λ.sub.2=j mod n.sub.2.

11. The secure writing apparatus according to claim 10, wherein the secret text vector [p.sub.i] is a secret text vector having a size n.sub.1 in which an element of
[p.sub.i[└x.sub.i/n.sub.2┘]] is one and other elements are zero, and the secret text vector [q.sub.i] is a secret text vector having a size n.sub.2 in which an element of
[q.sub.i[x.sub.i mod n.sub.2]] is [y.sub.i], and other elements are zero.

12. A secure writing apparatus comprising: an input circuitry configured to receive a secret text sequence, a secret text of a write address, and a secret text of a value to be written as input; an address decomposing circuitry configured to create an anonymous vector representing the writing of the value indicated by the secret text of the write address to the write address; a vector creating circuitry configured to select an element from the secret text vector and create a vector representing the write address and a vector representing the write value; a writing circuitry configured to add an inner product of a vector expressing the write address and a vector expressing the value to be written to the secret text sequence; wherein n and m are set as integers equal to or greater than 2, i is set as each integer equal to or greater than 0 and less than m, and j is set as each integer equal to or greater than 0 and less than n, the input circuitry is configured to receive the received secret text sequence received and the secret text of a read position as a secret text sequence [a]=([a[0]], [a[1]], . . . , [a[n−1]]) having a size n, a secret text [x.sub.i] of a write address x.sub.i and a secret text [y.sub.i] of a value to be written y.sub.i as input; the address decomposing circuitry is configured to creates a secret text vector [w.sub.i] which expresses a write address x.sub.i of the value y.sub.i for each integer i, the vector creating circuitry is configured to select an element from the secret text vector [w.sub.j] and create secret text vectors [u.sub.j] and [v.sub.j] for each integer j, and the writing circuitry is configured to add the inner product of a vector expressing the write address and the vector expressing the value to be written to the secret text sequence by adding an inner product of the secret text vector [u.sub.j] and the secret text vector [v.sub.j] for each integer j to the secret text [a[j]] which is a j-th element of the secret text sequence [a], wherein the processing circuitry concatenates secret text vectors [p.sub.i] and [q.sub.i] in which, when n.sub.2λ.sub.1+λ.sub.2=x.sub.i, p.sub.i[λ.sub.1]q.sub.i[λ.sub.2] becomes [y.sub.i] and otherwise becomes zero, to create the secret text vector [w.sub.i] while n.sub.1 and n.sub.2 are set as natural numbers satisfying n.sub.1n.sub.2≥n, and creates the secret text vectors [u.sub.j] and [v.sub.j] as in the following formula:
[u.sub.j[i]]=[p.sub.i[λ.sub.1]],
[v.sub.j[i]]=[q.sub.i[λ.sub.2]] where i is set as each integer equal to or greater than 0 and less than m, j is set as each integer equal to or greater than 0 and less than n, and λ.sub.1 and λ.sub.2 are set as in the following formula:
λ.sub.1=└j/n.sub.2┘,
λ.sub.2=j mod n.sub.2, wherein the secret text sequence [a], the secret text [x.sub.i] and the secret text [y.sub.i] are concealed through secret sharing in which t is set as an integer equal to or greater than 1, s≥2t−1, and, among shares obtained by dividing a plain text into s pieces, if arbitrary t shares are collected, the plain text can be obtained, while any information regarding the plain text cannot be obtained from less than t shares, and n.sub.1 and n.sub.2 are defined with the following formula:
n.sub.1,n.sub.2=┌n┐.

13. A secure writing method to be executed by a secure writing apparatus comprising: receiving, by an input circuitry, a secret text sequence, a secret text of a write address, and a secret text of a value to be written as input; creating, by an address decomposing circuitry, a vector of an anonymous sentence expressing writing of a value indicated by secret text of the writing address to the writing address; selecting, by a vector creating circuitry, an element from the secret text vector, and creating, by the vector creating circuitry, a vector expressing the writing address and a vector expressing the writing value; and adding, by a writing circuitry, an inner product of a vector expressing the write address and a vector expressing the value to be written to an element at the write address of the secret text sequence.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 is a diagram illustrating a functional configuration of a secure reading apparatus;

(2) FIG. 2 is a diagram illustrating processing procedure of a secure reading method;

(3) FIG. 3 is a diagram illustrating a functional configuration of a secure writing apparatus; and

(4) FIG. 4 is a diagram illustrating processing procedure of a secure writing method.

DETAILED DESCRIPTION OF THE EMBODIMENTS

(5) Prior to the description of embodiments, a notation method and definition of terms in this specification will be described.

(6) <Notation Method>

(7) A value obtained by concealing a certain value “a” through encryption, secret sharing, or the like, will be referred to as a secret text of “a”, and expressed as [a]. Further, “a” is referred to as a plain text of [a]. In a case where concealment is performed through secret sharing, an aggregate of fragments of secret sharing, possessed by respective secure computation apparatuses is referred to by [a]. The i-th element of a vector a=(a.sub.0, a.sub.1, . . . ) is referred to by a[i]. The number of elements of the vector a is expressed as |a|.
└x.square-solid.

(8) is a floor function, and indicates a maximum integer equal to or less than a real number x.
┌x┐

(9) is a ceiling function and indicates a minimum integer equal to or greater than the real number x.

(10) <Addition, Subtraction, Multiplication>

(11) In each operation of addition, subtraction and multiplication to be performed on a secret text, secret texts [a] and [b] of two values a and b are input, and secret texts [c.sub.1], [c.sub.2] and [c.sub.3] of c.sub.1, c.sub.2 and c.sub.3 which are respectively computation results of a+b, a−b and ab are computed. Execution of these kinds of operation will be expressed as in the following expressions.
[c.sub.1]←Add([a],[b]),
[c.sub.2]←Sub([a],[b]),
[c.sub.3]←Mul([a],[b])

(12) In a case where there is no possibility that misunderstanding is caused, Add([a], [b]), Sub([a], [b]), and Mul([a], [b]) will be respectively abbreviated as [a]+[b], [a]−[b] and [a][b].

(13) <Equality Testing>

(14) Processing in which the secret texts [a] and [b] of two values a and b are input, and a secret text [c] in which, if a=b, c=1, and, if a≠b, c=0, is computed will be expressed as in the following expression.
[c]←([a] custom character [b])

(15) Embodiments of the present invention will be described in detail below. Note that, in the drawings, the same reference numerals will be assigned to component parts having the same functions, and redundant description will be omitted.

First Embodiment

(16) A secure reading apparatus according to a first embodiment receives a secret text sequence and a secret text of a read position as input, and outputs an element at the read position of the secret text sequence. At this time, generation of a new secret text sequence in which an inner product of a vector expressing the read position and a vector based on the secret text sequence is set as an element is repeated until the number of elements of the new secret text sequence becomes one, and the new secret text sequence having the number of elements of one is output as the element at the read position.

(17) As illustrated in FIG. 1, a secure reading apparatus 1 in the first embodiment includes an input part 11, a vector creating part 12, a compression computing part 13 and a reading part 14. By this secure reading apparatus 1 performing processing in each step illustrated in FIG. 2, a secure reading method in the first embodiment is implemented.

(18) The secure reading apparatus 1 is a special apparatus configured by, for example, a special program being read into a publicly-known or dedicated computer having a central processing unit (CPU), a random access memory (RAM), or the like. The secure reading apparatus 1, for example, executes various kinds of processing under control of the CPU. Data input to the secure reading apparatus 1 and data obtained through respective kinds of processing are, for example, stored in the RAM, and the data stored in the RAM is read out to the CPU as necessary and is utilized for other processing. At least part of respective processing parts of the secure reading apparatus 1 may be configured with hardware such as an integrated circuit.

(19) A secure reading method to be executed by the secure reading apparatus 1 in the first embodiment will be described below with reference to FIG. 2.

(20) In step S11, the input part 11 receives a secret text sequence [a.sub.0]=([a.sub.0[0]], [a.sub.0[1]], . . . , [a.sub.0[n−1]]) having a size n, and a secret text [x] of a read position x as input. The input part 11 outputs the secret text sequence [a.sub.0] and the secret text [x] to the vector creating part 12.

(21) In step S12, the vector creating part 12 receives the secret text sequence [a.sub.0] and the secret text [x] from the input part 11, and creates a vector [v.sub.j] of k secret texts. However, k is an integer equal to or greater than 2, and j is each integer equal to or greater than 1 and equal to or less than k. Specifically, the secret text vector [v.sub.j] having a size m.sub.j in which m.sub.1, m.sub.2, . . . , m.sub.k are set as natural numbers satisfying n≤m.sub.1×m.sub.2× . . . ×m.sub.k, and x.sub.j is set as an integer defined in the formula (1) for each integer j, and the (x.sub.j mod m.sub.j)-th element is one, and other elements are zero, is created.

(22) $\begin{matrix} x_{j} = .Math. \frac{x}{m_{1} \times m_{2} \times .Math. \times m_{j - 1}} .Math. & (1) \end{matrix}$

(23) Particularly, if each input secret text is a share obtained through (t, s) Shamir secret sharing, k, m.sub.i (i=1, 2, . . . , k) can be set as in formula (2). Note that (t, s) Shamir secret sharing is secret sharing in which distributed values obtained by dividing an input plain text into s pieces are stored in s secure computation apparatuses, and if arbitrary t shares are collected, the plain text can be reconstructed, while any information regarding the plain text cannot be obtained from less than t shares. At this time, t is an integer equal to or greater than 1, and s≥2t−1.

(24) $\begin{matrix} k = .Math. \frac{s - 1}{t - 1} .Math., m_{i} = .Math. n^{1 / k} .Math. & (2) \end{matrix}$

(25) In step S13-1, the compression computing part 13 initializes j to 1.

(26) In step S13-2, the compression computing part 13 creates a vector of n.sub.j secret texts [b.sub.j, i] using a secret text sequence [a.sub.j-1]. The number n.sub.j of the secret text vector [b.sub.j, i] to be created differs depending on a value of j. Specifically, the secret text vector [b.sub.j, j] is computed assuming that n.sub.j is an integer defined in formula (3), i is set as each integer equal to or greater than 0 and less than n.sub.j, and [b.sub.j, i]=([a.sub.j-1[m.sub.ji+0]], [a.sub.j-1[m.sub.ji+1]], . . . , [a.sub.j-1[m.sub.ji+m.sub.j−1]]) (where, if λ=|a.sub.j-1|, [a.sub.j-1[λ]]=0).

(27) $\begin{matrix} n_{j} = .Math. \frac{n}{m_{1} \times m_{2} \times .Math. \times m_{j}} .Math. & (3) \end{matrix}$

(28) In step S13-3, the compression computing part 13 computes a secret text sequence [a.sub.j] in which an inner product of the secret text vector [b.sub.j, i] and the secret text vector [v.sub.j] is set as the i-th element.

(29) In step S13-4, the compression computing part 13 determines if j+1 is equal to or less than k (j+1≤k), and, if j+1 is equal to or less than k, increments j (j←j+1), and returns the processing to step S13-2, and, if j+1 is greater than k (j+1>k), outputs a secret text sequence [a.sub.k]. Note that, at this time, the secret text sequence [a.sub.k] is a sequence having the number of elements of one.

(30) In step S14, the reading part 14 outputs the secret text sequence [a.sub.k] having the number of elements of one as a secret text [a.sub.0[x]] which is the x-th element in a secret text sequence [a.sub.0].

(31) The first embodiment has a feature that reading of the i-th element is expressed with a k-depth inner product using a vector having a size Θ(n.sup.1/k) by utilizing characteristics that it is possible to perform up to k−1-depth multiplication (inner product) through communication corresponding to multiplication of one time in (t, s) Shamir secret sharing. As a result of a size of each vector being set as O(n.sup.1/k), so that k−1-depth computation can be completed with O(n.sup.1/k) times, it is possible to suppress an overall communication amount to O(n.sup.1/k).

Second Embodiment

(32) A secure writing apparatus in a second embodiment receives a secret text sequence, a secret text of a write address, and a secret text of a value to be written as input, and adds the value to an element at the write address of the secret text sequence. At this time, an inner product of a vector expressing the write address and a vector expressing the value to be written is added to the secret text sequence.

(33) As illustrated in FIG. 3, a secure writing apparatus 2 in the second embodiment includes an input part 21, an address decomposing part 22, a vector creating part 23 and a writing part 24. By this secure writing apparatus 2 performing processing in each step illustrated in FIG. 4, a secure writing method in the second embodiment is implemented.

(34) The secure writing apparatus 2 is a special apparatus configured by, for example, a special program being read into a publicly-known or dedicated computer having a central processing unit (CPU), a random access memory (RAM), or the like. The secure writing apparatus 2, for example, executes various kinds of processing under control of the CPU. Data input to the secure writing apparatus 2 and data obtained through respective kinds of processing are, for example, stored in the RAM, and the data stored in the RAM is read out to the CPU as necessary and is utilized for other processing. At least part of respective processing parts of the secure writing apparatus 2 may be configured with hardware such as an integrated circuit.

(35) A secure writing method to be executed by the secure writing apparatus 2 in the second embodiment will be described below with reference to FIG. 4.

(36) In step S21, the input part 21 receives a secret text sequence [a]=([a[0]], [a[1]], . . . , [a[n−1]]) having a size n, a secret text [x.sub.i] of m write addresses and a secret text [y.sub.i] of m values to be written as input. However, in is an integer equal to or greater than 2, and i is each integer equal to or greater than 0 and less than in. The input part 21 outputs the secret text [x.sub.i] of the write addresses and the secret text [y.sub.i] of the values to be written to the address decomposing part 22.

(37) In step S22, the address decomposing part 22 receives the secret text [x.sub.i] of the write addresses and the secret text [y.sub.i] of the values to be written from the input part 21, and creates a secret text vector [w.sub.i] which expresses writing of each value y.sub.i of the write address x.sub.i. Specifically, secret text vectors [p.sub.i], [q.sub.i] in which n.sub.1 and n.sub.2 are set as natural numbers satisfying n.sub.1n.sub.2≥n, p.sub.i[λ.sub.i]q.sub.i[λ.sub.2] becomes [y.sub.i] when n.sub.2λ.sub.1+λ.sub.2=x.sub.i, otherwise, becomes 0, are created, and the secret text vectors [p.sub.i], [q.sub.i] are concatenated to generate a secret text vector [w.sub.i]=[p.sub.i]∥[q.sub.i]. At this time, the secret text vector [p.sub.i] may be a secret text vector having a size n.sub.1 in which an element of
[p.sub.i[└x.sub.i/n.sub.2┘]]

(38) is one, and other elements are zero, and the secret text vector [q.sub.i] may be a secret text vector having a size n.sub.2 in which an element of
[q.sub.i[x.sub.i mod n.sub.2]]

(39) is [y.sub.i], and other elements are zero.

(40) Particularly, if each input secret text is a share obtained through (t, s) Shamir secret sharing, n.sub.1 and n.sub.2 can be set as in formula (4). Note that (t, s) Shamir secret sharing is secret sharing in which distributed values obtained by dividing an input plain text into s pieces are stored in s secure computation apparatuses, and, if arbitrary t shares are collected, the plain text can be reconstructed, while any information regarding the plain text cannot be obtained from less than t shares. At this time, t is an integer equal to or greater than 1, and s≥2t−1.
n.sub.1,n.sub.2=┌√{square root over (n)}┐ (4)

(41) In step S23, the vector creating part 23 selects an element from the secret text vector [w.sub.i] and generates secret text vectors [u.sub.j] and [v.sub.j] while j is set as each integer equal to or greater than 0 and less than n. Specifically, λ.sub.1 and λ.sub.2, are expressed as in formula (5) while i is set as each integer equal to or greater than 0 and less than in, and j is set as each integer equal to or greater than 0 and less than n.
Δ.sub.1=└j/n.sub.2┘,
Δ.sub.2=j mod n.sub.2 (5)

(42) The secret text vectors [u.sub.j] and [v.sub.j] are generated as in formula (6).
[u.sub.j[i]]=[p.sub.i[λ.sub.1]],
[v.sub.j[i]]=[q.sub.i[λ.sub.2]] (6)

(43) In step S24, the writing part 24 adds an inner product of the secret text vector [u.sub.j] and the secret text vector [v.sub.j] to a secret text [a[j]] which is the j-th element in the secret text sequence [a] while j is set as each integer equal to or greater than 0 and less than n.

(44) The second embodiment has a feature that a value to be written is expressed with an inner product of two vectors, so that a value to be added to each address of a write destination can be computed from the inner product of the vectors having a size m. Because the inner product can be computed through communication corresponding to multiplication of one time, it is possible to suppress an overall communication amount to O(n+m√n).

(45) While the embodiments of the present invention have been described above, a specific configuration is not limited to these embodiments, and it goes without saying that change, or the like, of design is incorporated into the present invention as appropriate within a scope not deviating from the gist of the present invention. Various kinds of processing described in the embodiments are not only executed in a chronological order in accordance with order of description, but may be executed in parallel or individually in accordance with processing performance of an apparatus which executes the processing or as necessary.

(46) [Program, Recording Medium]

(47) In a case where various kinds of processing functions at the respective apparatuses described in the above-described embodiments are implemented with a computer, processing content of functions which should be provided at the respective apparatuses is described with a program. Further, by this program being executed in the computer, various kinds of processing functions at the above-described respective apparatuses are realized on the computer.

(48) The program describing this processing content can be recorded in a computer-readable recording medium. The computer-readable recording medium may be, for example, any medium such as a magnetic recording apparatus, an optical disk, a magnetooptical recording medium and a semiconductor memory.

(49) Further, this program is distributed by, for example, a portable recording medium such as a DVD and a CD-ROM in which the program is recorded, being sold, given, lent, or the like. Still further, it is also possible to employ a configuration where this program is stored in a storage apparatus of a server computer, and the program is distributed by being transferred from the server computer to other computers over a network.

(50) A computer which executes such a program, for example, first, stores the program recorded in the portable recording medium or the program transferred from the server computer in a storage apparatus of the own computer once. Then, upon execution of the processing, this computer reads the program stored in the storage apparatus of the own computer and executes processing in accordance with the read program. Further, as another execution form of this program, the computer may directly read the program from the portable recording medium and execute processing in accordance with the program, and further, every time a program is transferred from the server computer to this computer, the computer may sequentially execute processing in accordance with the received program. Still further, it is also possible to employ a configuration where the above-described processing is executed through so-called ASP (Application Service Provider) service in which processing functions are realized only through an execution instruction and a result acquisition without the program being transferred from the server computer to this computer. Note that the program in the present embodiment includes information which is provided to be used for processing by an electronic computer and which is equivalent to a program (such as data which is not a direct command to the computer but has property of defining processing of a computer).

(51) Further, while, in the present embodiment, the present apparatus is configured by a predetermined program being executed on a computer, at least part of the processing content may be realized with hardware.

Secure reading apparatus, secure writing apparatus, method thereof, and program for reading and writing data in a sequence without revealing an access position

Assignee

Inventors

Cpc classification

Classification Explorer

G09C1/00

PHYSICS

Classification Explorer

G06F21/71

PHYSICS

Classification Explorer

H04L2209/46

ELECTRICITY

Classification Explorer

G06F21/72

PHYSICS

International classification

Classification Explorer

G06F21/00

PHYSICS

Classification Explorer

G09C1/00

PHYSICS

Classification Explorer

G06F21/72

PHYSICS

Abstract

Claims

Description