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

Abstract

A vector generation unit generates a vector xso that x[i]≠x[j] if k[i]=k[j] at i≠j. A set generation unit generates a set Bso that individual elements correspond to combinations of the N−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′ 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′ so that elements of the matrix T′ 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].