Inverse-image sampling device, inverse-image sampling method, and inverse-image sampling program

Abstract

A grouping means 11 that extracts basis vectors from a set of basis vectors for a lattice having a predetermined relationship with a matrix used to generate a public key, and that groups the basis vectors such that a predetermined condition is satisfied. A sampling means 12 that samples, for at least one group, the same number of arbitrary values as the number of a plurality of basis vectors included in that group, in parallel for the individual basis vectors, onto a lattice constituted by the plurality of basis vectors, the arbitrary values serving as random numbers following a discrete Gaussian distribution. The predetermined condition is that each of the basis vectors included in a group is orthogonal to the other basis vectors included in the same group and is also orthogonal to Gram-Schmidt basis vectors, which are vectors obtained by orthogonalizing the other basis vectors by Gram-Schmidt orthogonalization.

Claims

1. An inverse-image sampling device comprising: a grouping unit, implemented by a hardware including one or more processors, that extracts basis vectors from a set of basis vectors for a lattice having a predetermined relationship with a matrix used to generate a public key, and that groups the basis vectors such that a predetermined condition is satisfied; and a sampling unit, implemented by the hardware, that samples, for at least one group, the same number of arbitrary values as the number of a plurality of basis vectors included in that group, in parallel for the individual basis vectors, onto a lattice constituted by the plurality of basis vectors, the arbitrary values serving as random numbers following a discrete Gaussian distribution, wherein the predetermined condition is that each of the basis vectors included in a group is orthogonal to the other basis vectors included in the same group and is also orthogonal to Gram-Schmidt basis vectors, which are vectors obtained by orthogonalizing the other basis vectors by Gram-Schmidt orthogonalization.

2. The inverse-image sampling device according to claim 1, wherein the basis vectors for the lattice are vectors each having a non-zero component of (2, −1).

3. The inverse-image sampling device according to claim 2, wherein the sampling unit acquires an arbitrary vector, samples arbitrary values as random numbers following a discrete Gaussian distribution with an element of the acquired arbitrary vector as the center, and outputs a vector composed of the sampled arbitrary values and a plurality of basis vectors included in the group.

4. The inverse-image sampling device according to claim 3, further comprising: a plurality of sampling unit implemented by the hardware, wherein the plurality of sampling unit include a sampling unit that receives an input of a vector output from another sampling unit.

5. The inverse-image sampling device according to claim 4, further comprising: a generation unit, implemented by the hardware, that generates a Gram-Schmidt basis vector of the basis vector included in the group, wherein the sampling unit samples arbitrary values by using the generated Gram-Schmidt basis vector.

6. The inverse-image sampling device according to claim 3, further comprising: a generation unit, implemented by the hardware, that generates a Gram-Schmidt basis vector of the basis vector included in the group, wherein the sampling unit samples arbitrary values by using the generated Gram-Schmidt basis vector.

7. The inverse-image sampling device according to claim 2, further comprising: a generation unit, implemented by the hardware, that generates a Gram-Schmidt basis vector of the basis vector included in the group, wherein the sampling unit samples arbitrary values by using the generated Gram-Schmidt basis vector.

8. The inverse-image sampling device according to claim 7, further comprising: the same number of generation unit, implemented by the hardware, as the number of groups generated by the grouping unit with grouping.

9. The inverse-image sampling device according to claim 1, wherein the sampling unit acquires an arbitrary vector, samples arbitrary values as random numbers following a discrete Gaussian distribution with an element of the acquired arbitrary vector as the center, and outputs a vector composed of the sampled arbitrary values and a plurality of basis vectors included in the group.

10. The inverse-image sampling device according to claim 9, further comprising: a plurality of sampling unit implemented by the hardware, wherein the plurality of sampling unit include a sampling unit that receives an input of a vector output from another sampling unit.

11. The inverse-image sampling device according to claim 10, further comprising: a generation unit, implemented by the hardware, that generates a Gram-Schmidt basis vector of the basis vector included in the group, wherein the sampling unit samples arbitrary values by using the generated Gram-Schmidt basis vector.

12. The inverse-image sampling device according to claim 11, further comprising: the same number of generation unit, implemented by the hardware, as the number of groups generated by the grouping unit with grouping.

13. The inverse-image sampling device according to claim 9, further comprising: a generation unit, implemented by the hardware, that generates a Gram-Schmidt basis vector of the basis vector included in the group, wherein the sampling unit samples arbitrary values by using the generated Gram-Schmidt basis vector.

14. The inverse-image sampling device according to claim 13, further comprising: the same number of generation unit, implemented by the hardware, as the number of groups generated by the grouping unit with grouping.

15. The inverse-image sampling device according to claim 1, further comprising: a generation unit, implemented by the hardware, that generates a Gram-Schmidt basis vector of the basis vector included in the group, wherein the sampling unit samples arbitrary values by using the generated Gram-Schmidt basis vector.

16. The inverse-image sampling device according to claim 15, further comprising: the same number of generation unit, implemented by the hardware, as the number of groups generated by the grouping unit with grouping.

17. A computer-implemented inverse-image sampling method comprising the steps of: extracting basis vectors from a set of basis vectors for a lattice having a predetermined relationship with a matrix used to generate a public key, and grouping the basis vectors such that a predetermined condition is satisfied; and sampling, for at least one group, the same number of arbitrary values as the number of a plurality of basis vectors included in that group, in parallel for the individual basis vectors, onto a lattice constituted by the plurality of basis vectors, the arbitrary values serving as random numbers following a discrete Gaussian distribution, wherein the predetermined condition is that each of the basis vectors included in a group is orthogonal to the other basis vectors included in the same group and is also orthogonal to Gram-Schmidt basis vectors, which are vectors obtained by orthogonalizing the other basis vectors by Gram-Schmidt orthogonalization.

18. The computer-implemented inverse-image sampling method according to claim 17, wherein the basis vectors for the lattice are vectors each having a non-zero component of (2, −1).

19. A non-transitory computer-readable capturing medium having captured therein an inverse-image sampling program for causing a computer to perform: a grouping process of extracting basis vectors from a set of basis vectors for a lattice having a predetermined relationship with a matrix used to generate a public key, and of grouping the basis vectors such that a predetermined condition is satisfied; and a sampling process of sampling, for at least one group, the same number of arbitrary values as the number of a plurality of basis vectors included in that group, in parallel for the individual basis vectors, onto a lattice constituted by the plurality of basis vectors, the arbitrary values serving as random numbers following a discrete Gaussian distribution, wherein the predetermined condition is that each of the basis vectors included in a group is orthogonal to the other basis vectors included in the same group and is also orthogonal to Gram-Schmidt basis vectors, which are vectors obtained by orthogonalizing the other basis vectors by Gram-Schmidt orthogonalization.

20. The medium according to claim 19, wherein the basis vectors for the lattice are vectors each having a non-zero component of (2, −1).

Description

BRIEF DESCRIPTION OF DRAWINGS

(1) FIG. 1 is an explanatory diagram showing an example of a generation algorithm of random numbers following a discrete Gaussian distribution.

(2) FIG. 2 is a block diagram showing a configuration example of a first exemplary embodiment of a parallel inverse-image sampling device according to the present invention.

(3) FIG. 3 is a block diagram showing a configuration example of a data structure generation unit 1100 of a first exemplary embodiment.

(4) FIG. 4 is a block diagram showing a configuration example of a Level parallel computation unit 1200 of the first exemplary embodiment.

(5) FIG. 5 is a flowchart showing an operation of a sampling process performed by the parallel inverse-image sampling device 1000 of the first exemplary embodiment.

(6) FIG. 6 is a block diagram showing an outline of an inverse-image sampling device according to the present invention.

(7) FIG. 7 is an explanatory diagram showing an example of an inverse-image sampling process.

(8) FIG. 8 is an explanatory diagram showing an example of a generation algorithm of random numbers following a discrete Gaussian distribution with the center as the origin.

DESCRIPTION OF EMBODIMENT

Exemplary Embodiment 1

(9) Hereinafter, an exemplary embodiment of the present invention will be described with reference to appended drawings. Incidentally, a computing operation is performed by Z.sub.q=Z/qZ also in this exemplary embodiment.

(10) First, the configuration of the sampling process on a dual primitive lattice of this exemplary embodiment will be simply described. First, description is made on a method of generating random numbers following a discrete Gaussian distribution on a lattice Λ(B) having a general form, which is not limited to a dual primitive lattice, having c{right arrow over ( )} as the center. Note that, however, B=(b.sub.1{right arrow over ( )}, . . . , b.sub.n{right arrow over ( )}) is satisfied.

(11) FIG. 1 is an explanatory diagram showing an example of a generation algorithm of random numbers following a discrete Gaussian distribution. The algorithm shown in FIG. 1 corresponds to an algorithm shown in FIG. 8.

(12) In the loop of the fourth to ninth lines of the algorithm shown in FIG. 1, z.sub.i is generated in a single process and c.sub.i−1 is updated on the basis of the generated z.sub.i. Furthermore, in the next process, the discrete Gaussian distribution is updated on the basis of the updated c.sub.i−1 and then z.sub.i−1 is generated. In other words, random numbers z.sub.n, . . . , z.sub.1 are sequentially generated.

(13) When a matrix basis b.sub.i{right arrow over ( )} is orthogonal to a Gram-Schmidt basis of each of the matrix bases b.sub.i+1{right arrow over ( )}, . . . , b.sub.i+j{right arrow over ( )} in the algorithm shown in FIG. 1, the processes of (i+j) to (i+1) and the process of i in the processes of (i+j) to i in the loop of the fourth to ninth lines in the algorithm shown in FIG. 1 are able to be computed in parallel.

(14) Specifically, a process of sampling with a sequential loop of (i+j) to i is equal to a process of computing a sampling result with a sequential loop of (i+j) to (i+1) and a sampling result of i in parallel and outputting a sum of the sampling results.

(15) In this exemplary embodiment, the data structure of the basis matrix S of the dual primitive lattice is divided so that the above characteristics are utilized. The basis vectors constituting the basis matrix S is divided into groups so that a predetermined condition is satisfied.

(16) The predetermined condition is that each of the basis vectors included in the group is orthogonal to the other basis vectors included in the same group and is also orthogonal to Gram-Schmidt basis vectors, which are vectors obtained by orthogonalizing the other basis vectors by

(17) Gram-Schmidt orthogonalization.

(18) For example, the basis matrix S=(a.sub.1{right arrow over ( )}, . . . , a.sub.K{right arrow over ( )}) of the dual primitive lattice are divided into the Levels (groups) as described below.

(19) Basis vector set of Level 0={a.sub.i{right arrow over ( )}:i=2.sup.0*(odd number)},

(20) Basis vector set of Level 1={a.sub.i{right arrow over ( )}:i=2.sup.1*(odd number)},

(21) Basis vector set of Level 2={a.sub.i{right arrow over ( )}:i=2.sup.2*(odd number)}, . . .

(22) In addition, the basis belonging to each Level satisfies a condition of being orthogonal to all Gram-Schmidt bases of other bases in the same Level. The method of dividing the basis vectors constituting the basis matrix S is not limited to the above method.

(23) For example, in the case where the basis vector set of a predetermined Level is {b.sub.1{right arrow over ( )}, b.sub.2{right arrow over ( )}, b.sub.3{right arrow over ( )}}, the following relationship is established between the basis vectors.
[MATH. 13]
{right arrow over (b)}.sub.1⊥{{tilde over ({right arrow over (b)})}.sub.2,{tilde over ({right arrow over (b)})}.sub.3}{right arrow over (b)}.sub.2⊥{{tilde over ({right arrow over (b)})}.sub.1,{tilde over ({right arrow over (b)})}.sub.3}{right arrow over (b)}.sub.3⊥{{tilde over ({right arrow over (b)})}.sub.2,{tilde over ({right arrow over (b)})}.sub.1}  Equation (7)

(24) In other words, the parallel computation of the sampling process is able to be performed in the same Level. Incidentally, the sampling process for a basis set that does not satisfy the above condition is performed in a sequential manner.

(25) Therefore, the algorithm of this exemplary embodiment is as described below, the algorithm instead serving as the process of fourth to ninth lines in the algorithm shown in FIG. 1.

(26) Proposed Algorithm STEP 0

(27) First, as a precomputation process, a Level division of basis vectors constituting the basis matrix of the dual primitive lattice is performed such that the predetermined condition is satisfied.
Level j={a.sub.1.sup.j, . . . , a.sub.I(j).sup.j}(0≤j≤L(K))

(28) Proposed Algorithm STEP 1

(29) Subsequently, the following computation is performed from j=0 corresponding to the lowest Level to j=L(K) corresponding to the highest Level. Note that K indicates the dimension of S.

(30) 0$\begin{array}{cc}\left[\mathrm{MATH}.14\right]& \\ \stackrel{.fwdarw.}{c}\leftarrow \stackrel{.fwdarw.}{c}-\underset{i=1}{\overset{I\left(j\right)}{.Math.}}\left({\alpha }_i\leftarrow D_{z,\frac{.Math.\stackrel{.fwdarw.}{c},{\stackrel{.fwdarw.}{\tilde{\alpha }}}_i^J.Math.}{{.Math.{\stackrel{.fwdarw.}{\tilde{\alpha }}}_i^J.Math.}^2}}\right){\stackrel{->}{\alpha }}_i^J& \mathrm{Equation}\left(8\right)\end{array}$

(31) The last vector (0, . . . , 0, 2).sup.t is included in the Level L(K), which is the highest Level.

(32) Description will be made on a concrete example of enabling a parallel computation in the same Level, by using a basis vector set of the aforementioned predetermined Level. Specifically, description will be made on an example of a sampling process for a case of i+j=3 and i+1=1.

(33) In the sampling process following the algorithm shown in FIG. 1, the following vectors are sequentially computed for c{right arrow over ( )} used as the center of an input discrete Gaussian distribution.

(34) $\begin{array}{cc}\left[\mathrm{MATH}.15\right]& \\ {\stackrel{.fwdarw.}{c}}_2\leftarrow \stackrel{.fwdarw.}{c}-\left({\alpha }_1\leftarrow D_{z,\frac{.Math.\stackrel{.fwdarw.}{c},{\stackrel{.fwdarw.}{\tilde{b}}}_3.Math.}{{.Math.{\stackrel{.fwdarw.}{\tilde{b}}}_3.Math.}^2}}\right){\stackrel{->}{b}}_3{\stackrel{.fwdarw.}{c}}_1\leftarrow {\stackrel{.fwdarw.}{c}}_2-\left({\alpha }_2\leftarrow D_{z,\frac{.Math.{\stackrel{.fwdarw.}{c}}_2,{\stackrel{.fwdarw.}{\tilde{b}}}_2.Math.}{{.Math.{\stackrel{.fwdarw.}{\tilde{b}}}_2.Math.}^2}}\right){\stackrel{->}{b}}_2\stackrel{.fwdarw.}{d}\leftarrow {\stackrel{.fwdarw.}{c}}_1-\left({\alpha }_3\leftarrow D_{z,\frac{.Math.{\stackrel{.fwdarw.}{c}}_1,{\stackrel{.fwdarw.}{\tilde{b}}}_1.Math.}{{.Math.{\stackrel{.fwdarw.}{\tilde{b}}}_1.Math.}^2}}\right){\stackrel{->}{b}}_1& \end{array}$

(35) Coefficients α.sub.1 to coefficient α.sub.3 correspond to random numbers. Furthermore, the vector (d{right arrow over ( )}-c{right arrow over ( )}) corresponds to a vector z{right arrow over ( )} computed in the inverse-image sampling STEP 3. Since the equation (7) is satisfied in this example, the following relationship is established, for example.
{right arrow over (c)}.sub.2,{tilde over ({right arrow over (b)})}.sub.2=({right arrow over (c)}−α.sub.1{right arrow over (b)}.sub.3),{tilde over ({right arrow over (b)})}.sub.2={right arrow over (c)},{tilde over ({right arrow over (b)})}.sub.2−α.sub.1{right arrow over (b)}.sub.3,{tilde over ({right arrow over (b)})}.sub.2={right arrow over (c)},{tilde over ({right arrow over (b)})}.sub.2[MATH. 16]

(36) In other words, even if c.sub.2{right arrow over ( )} is not given, a coefficient α.sub.2, which is a random number following the discrete Gaussian distribution, is computed. Similarly, the following relationship is established.

(37) $\begin{array}{cc}\left[\mathrm{MATH}.17\right]& \\ .Math.{\stackrel{.fwdarw.}{c}}_1,{\stackrel{.fwdarw.}{\tilde{b}}}_1.Math.=.Math.\left({\stackrel{.fwdarw.}{c}}_2-{\alpha }_2{\stackrel{->}{b}}_2\right),{\stackrel{.fwdarw.}{\tilde{b}}}_1.Math.=.Math.{\stackrel{.fwdarw.}{c}}_2,{\stackrel{.fwdarw.}{\tilde{b}}}_1.Math.-{\alpha }_2.Math.{\stackrel{.fwdarw.}{b}}_2,{\stackrel{.fwdarw.}{\tilde{b}}}_1.Math.=.Math.\left(\stackrel{.fwdarw.}{c}-{\alpha }_1{\stackrel{->}{b}}_3\right),{\stackrel{.fwdarw.}{\tilde{b}}}_1.Math.=.Math.\stackrel{.fwdarw.}{c},{\stackrel{.fwdarw.}{\tilde{b}}}_1.Math.-{\alpha }_1.Math.{\stackrel{.fwdarw.}{b}}_3,{\stackrel{.fwdarw.}{\tilde{b}}}_1.Math.=.Math.\stackrel{.fwdarw.}{c},{\stackrel{.fwdarw.}{\tilde{b}}}_1.Math.& \end{array}$

(38) In other words, even if c.sub.2{right arrow over ( )} and c.sub.1{right arrow over ( )} are not given, a coefficient α.sub.3, which is a random number following the discrete Gaussian distribution, is computed. Therefore, the coefficients α.sub.1 to α.sub.3 are computed in parallel, by which a vector d{right arrow over ( )} is computed at high speed.

(39) [Description of Configuration]

(40) FIG. 2 is a block diagram showing a configuration example of a first exemplary embodiment of a parallel inverse-image sampling device according to the present invention. As shown in FIG. 2, a parallel inverse-image sampling device 1000 of this exemplary embodiment includes a data structure generation unit 1100, a Level parallel computation unit 1200, and an output unit 1300.

(41) The data structure generation unit 1100 has a function of generating a data structure optimum for a basis matrix of a dual primitive lattice. FIG. 3 is a block diagram showing a configuration example of the data structure generation unit 1100 of the first exemplary embodiment.

(42) As shown in FIG. 3, the data structure generation unit 1100 of this exemplary embodiment includes a zeroth data set extraction means 1110 to a K-th data set extraction means 111K, and a Gram-Schmidt basis computation means 1120 to a Gram-Schmidt basis computation means 112K.

(43) The configuration example of the data structure generation unit 1100 shown in FIG. 3 is a configuration example of a data structure generation unit that generates a data structure optimum for the basis matrix of the dual primitive lattice. The configuration example shown in FIG. 3 is a configuration example adopted in the case where a dividing method into respective Levels is previously determined since the basis matrix of the dual primitive lattice is previously determined.

(44) In other words, a user is able to previously give a dividing method into respective Levels to the parallel inverse-image sampling device 1000. In the case where the dividing method into respective Levels is previously given, each data set extraction means extracts a data set according to the given dividing method into the respective Levels.

(45) Each data set extraction means has a function of extracting a data set of each Level. For example, the zeroth data set extraction means 1110 extracts a data set of Level 0, {a.sub.1.sup.0, . . . , a.sub.I(0).sup.0}.

(46) Moreover, each Gram-Schmidt basis computation means has a function of computing a Gram-Schmidt basis for a data set of each Level. For example, the Gram-Schmidt basis computation means 1120 computes a Gram-Schmidt basis for a data set of Level 0, {.sub.1.sup.0, . . . , a{tilde over ( )}.sub.I(0).sup.0}.

(47) The Level parallel computation unit 1200 has a function of computing random numbers following a discrete Gaussian distribution for each Level in parallel. FIG. 4 is a block diagram showing a configuration example of a Level parallel computation unit 1200 of the first exemplary embodiment.

(48) As shown in FIG. 4, the Level parallel computation unit 1200 of this exemplary embodiment includes a zeroth parallel computation means 1210 to a K-th parallel computation means 121K. Each parallel computation means has a function of computing random numbers following a discrete Gaussian distribution of each Level in parallel. For example, the zeroth parallel computation means 1210 computes random numbers following the discrete Gaussian distribution at Level 0 in parallel.

(49) The output unit 1300 has a function of outputting random numbers or the like computed by the Level parallel computation unit 1200.

(50) [Description of Operation]

(51) Hereinafter, description will be made on an operation in which the parallel inverse-image sampling device 1000 of this exemplary embodiment samples random numbers as arbitrary values on a dual primitive lattice, with reference to FIG. 5. FIG. 5 is a flowchart showing the operation of a sampling process performed by the parallel inverse-image sampling device 1000 of the first exemplary embodiment.

(52) In this example, symbols are defined as follows with N∈Z as a security parameter.
[MATH. 18]
K∈N,q=2.sup.K,σ=ω(√{square root over (log N)})  Equation (9)

(53) First, the data structure generation unit 1100 receives input data. Subsequently, the zeroth data set extraction means 1110 to the K-th data set extraction means 111K acquire data sets of respective Levels according to, for example, a given dividing method into respective Levels (step S100). The process of step S100 corresponds to a process of grouping in such a way that a predetermined condition is satisfied.

(54) Subsequently, the zeroth data set extraction means 1110 inputs the extracted data set of Level 0 into the Gram-Schmidt basis computation means 1120. The Gram-Schmidt basis computation means 1120 then computes a Gram-Schmidt basis for the data set of Level 0 (step S110).

(55) Subsequently, the Gram-Schmidt basis computation means 1120 inputs the computed Gram-Schmidt basis into other all Gram-Schmidt basis computation means and the zeroth parallel computation means 1210.

(56) Similarly, the first data set extraction means 1111 inputs an extracted data set of Level 1 into the Gram-Schmidt basis computation means 1121. The Gram-Schmidt basis computation means 1121 then computes the Gram-Schmidt basis for the data set of Level 1 (step S111).

(57) Subsequently, the Gram-Schmidt basis computation means 1121 inputs the computed Gram-Schmidt basis into other all Gram-Schmidt basis computation means and a first parallel computation means 1211.

(58) Similarly, the K-th data set extraction means 111K inputs the extracted data set of Level L(K) into the Gram-Schmidt basis computation means 112K. The Gram-Schmidt basis computation means 112K then computes the Gram-Schmidt basis for the data set of Level L(K) (step S11K).

(59) Subsequently, the Gram-Schmidt basis computation means 112K inputs the computed Gram-Schmidt basis into other all Gram-Schmidt basis computation means and the K-th parallel computation means 121K. The processes of the above steps S100 to S11K constitute the precomputation process.

(60) Subsequently, the parallel inverse-image sampling device 1000 generates random numbers following the discrete Gaussian distribution on the dual primitive lattice. First, the zeroth parallel computation means 1210 receives u.sub.0{right arrow over ( )} from the input means (not shown). Incidentally, u.sub.0{right arrow over ( )} corresponds to c{right arrow over ( )} in the algorithm shown in FIG. 1.

(61) Subsequently, the zeroth parallel computation means 1210 generates, in parallel, random numbers following a discrete Gaussian distribution with u.sub.0{right arrow over ( )} on the lattice of Level 0 as the center (step S120). After generating the random numbers, the zeroth parallel computation means 1210 inputs an output value u.sub.1{right arrow over ( )} into the first parallel computation means 1211.

(62) Subsequently, the first parallel computation means 1211 receives u.sub.1{right arrow over ( )} from the zeroth parallel computation means 1210. The first parallel computation means 1211 generates, in parallel, random numbers following a discrete Gaussian distribution with u.sub.1{right arrow over ( )} on the lattice of Level 1 as the center (step S121). The first parallel computation means 1211 inputs an output value u.sub.2{right arrow over ( )} into a second parallel computation means 1212.

(63) Hereinafter, the respective parallel computation means sequentially perform the processes corresponding to the process of step S120. Finally, the K-th parallel computation means 121K receives u.sub.L(K){right arrow over ( )} from a (K−1)th parallel computation means 121(K−1). The K-th parallel computation means 121K generates, in parallel, random numbers following a discrete Gaussian distribution with u.sub.L(K){right arrow over ( )} on the lattice of Level L(K) as the center (step S12K).

(64) Unless the basis vector of Level L(K) satisfies the condition of being orthogonal to other all Gram-Schmidt bases in the same Level, the K-th parallel computation means 121K sequentially generates random numbers following the discrete Gaussian distribution.

(65) The K-th parallel computation means 121K inputs u.sub.L(K)+1{right arrow over ( )} into the output unit 1300. After the output unit 1300 outputs u.sub.L(K)+1{right arrow over ( )}, the parallel inverse-image sampling device 1000 ends the sampling process.

(66) Incidentally, a device (not shown) other than the parallel inverse-image sampling device 1000 subtracts u.sub.0{right arrow over ( )} from the output u.sub.L(K)+1{right arrow over ( )} to find a linear sum of random numbers and bases. The process of finding the linear sum of random numbers and bases corresponds to a process of computing a vector z{right arrow over ( )} in the inverse-image sampling STEP 3. Moreover, the parallel inverse-image sampling device 1000 may find the linear sum of random numbers and bases.

Description of Advantageous Effects

(67) The object of the present invention is to increase the speed of the sampling process by optimizing the data structure of the basis matrix S of the dual primitive lattice so as to enable the execution of a parallel computation.

(68) An inverse-image sampling process of a trapdoor one-way function requires generation of random numbers following a discrete Gaussian distribution on a predetermined lattice, which is referred to as “dual primitive lattice.” In this exemplary embodiment, an algorithm for optimizing the data structure of the basis matrix of the dual primitive lattice is introduced into a process of generating random numbers.

(69) With the introduction of the algorithm for optimizing the data structure, an algorithm for generating random numbers on the dual primitive lattice described in NPL 1 is partially rewritten to an algorithm enabling the execution of a parallel computation. In other words, a high-speed inverse-image sampling process is implemented.

(70) The following describes a reason for the implementation of the high-speed inverse-image sampling process. In a general method of outputting random numbers following the discrete Gaussian distribution on the dual primitive lattice, there is used an algorithm for generating random numbers following a discrete Gaussian distribution on a general lattice, which is not limited to the dual primitive lattice.

(71) In the algorithm for generating random numbers following the discrete Gaussian distribution on the general lattice, the random numbers are output after sequentially performing procedures for a discrete Gaussian distribution on integers for each basis vector on the lattice as an output target.

(72) If there is a predetermined type of orthogonality relation between basis vectors, a procedure for the discrete Gaussian distribution is performed in parallel between the basis vectors having the orthogonality relation. In other words, the procedure for the discrete Gaussian distribution need not be sequentially performed.

(73) For utilization of the above characteristics, the parallel inverse-image sampling device 1000 of this exemplary embodiment performs level division of the basis vectors so that the above orthogonality relation is satisfied within the same level, particularly for the basis matrix of the dual primitive lattice.

(74) If the algorithm for generating random numbers following the discrete Gaussian distribution is performed after the execution of the above processes, a parallel computation of random numbers can be performed within the same level, thereby enabling execution of a high-speed inverse-image sampling process. If the level division is performed for Level 0 to Level N, the processing time of the inverse-image sampling process is almost proportional to log.sub.2N.

(75) The parallel inverse-image sampling device 1000 of this exemplary embodiment may be implemented by, for example, a central processing unit (CPU) that performs processing according to a program stored in a non-transitory storage medium. Specifically, the data structure generation unit 1100, the Level parallel computation unit 1200, and the output unit 1300 may be implemented by the CPU that performs processes according to a program control, for example. Furthermore, the parallel inverse-image sampling device 1000 of this exemplary embodiment may be a data processor.

(76) Furthermore, the respective units of the parallel inverse-image sampling device 1000 of this exemplary embodiment may be implemented by hardware circuits. For example, the data structure generation unit 1100, the Level parallel computation unit 1200, and the output unit 1300 are each implemented by large scale integration (LSI). Alternatively, these units may be implemented by a single LSI.

(77) Subsequently, the outline of the present invention will be described. FIG. 6 is a block diagram showing an outline of an inverse-image sampling device according to the present invention. An inverse-image sampling device 10 according to the present invention includes: a grouping means 11 (for example, the data structure generation unit 1100) that extracts basis vectors from a set of basis vectors for a lattice having a predetermined relationship with a matrix used to generate a public key, and that groups the basis vectors such that a predetermined condition is satisfied; and a sampling means 12 (for example, the Level parallel computation unit 1200) that samples, for at least one group, the same number of arbitrary values as the number of a plurality of basis vectors included in that group, in parallel for the individual basis vectors, onto a lattice constituted by the plurality of basis vectors, the arbitrary values serving as random numbers following a discrete Gaussian distribution, and the predetermined condition is that each of the basis vectors included in a group is orthogonal to the other basis vectors included in the same group and is also orthogonal to Gram-Schmidt basis vectors, which are vectors obtained by orthogonalizing the other basis vectors by Gram-Schmidt orthogonalization.

(78) The configuration enables the inverse-image sampling device to sample arbitrary values, in parallel, as random numbers following discrete Gaussian distributions having different centers. The sampled arbitrary values are used to generate an inverse image of a trapdoor one-way function.

(79) Furthermore, the basis vectors for the lattice may be vectors each having a non-zero component of (2, −1).

(80) According to the above configuration, the inverse-image sampling device is able to sample arbitrary values as random numbers following a discrete Gaussian distribution in parallel for each of the bases constituting the basis matrix of a dual primitive lattice.

(81) Moreover, the sampling means 12 may acquire an arbitrary vector and sample arbitrary values as random numbers following a discrete Gaussian distribution with an element of the acquired arbitrary vector as the center and may output a vector composed of the sampled arbitrary values and a plurality of basis vectors included in the group.

(82) The above configuration enables the inverse-image sampling device to generate an inverse image of a trapdoor one-way function.

(83) Furthermore, the inverse-image sampling device 10 may include a plurality of sampling means 12 and the plurality of sampling means may include a sampling means that receives an input of a vector output from another sampling means.

(84) The above configuration enables the inverse-image sampling device to generate the inverse image of the trapdoor one-way function at higher speed.

(85) Furthermore, the inverse-image sampling device 10 may include a generation means that generates a Gram-Schmidt basis vector of the basis vector included in the group (for example, the Gram-Schmidt basis computation means 1120 to the Gram-Schmidt basis computation means 112K), and the sampling means 12 may sample arbitrary values by using the generated Gram-Schmidt basis vector.

(86) The above configuration enables the inverse-image sampling device to sample arbitrary values as random numbers following discrete Gaussian distributions having different centers at higher speed.

(87) Furthermore, the inverse-image sampling device 10 may include the same number of generation means as the number of groups generated by the grouping means 11 with grouping.

(88) The above configuration enables the inverse-image sampling device to sample arbitrary values as random numbers following discrete Gaussian distributions having different centers at higher speed.

(89) Although the present invention has been described with reference to the exemplary embodiments and examples hereinabove, the present invention is not limited thereto. A variety of changes, which can be understood by those skilled in the art, may be made in the configuration and details of the present invention within the scope thereof.

REFERENCE SIGNS LIST

(90) 10 Inverse-image sampling device

(91) 11 Grouping means

(92) 12 Sampling means

(93) 1000 Parallel inverse-image sampling device

(94) 1100 Data structure generation unit

(95) 1110 Zeroth data set extraction means

(96) 1111 First data set extraction means

(97) 111K K-th data set extraction means

(98) 1120 to 112K Gram-Schmidt basis computation means

(99) 1200 Level parallel computation unit

(100) 1210 Zeroth parallel computation means

(101) 1211 First parallel computation means

(102) 121K K-th parallel computation means

(103) 1300 Output unit