A matrix and key generation device in which N is an integer which is 1 or larger, n is an integer which is between 0 and N-1 inclusive, K n is an integer which is 1 or larger, i and j are integers, T n is a matrix having K n rows, k n is a vector which includes K n pieces of elements, T n [j] is a row on a j-th order of the matrix T n, k n [j] is an element on a j-th order of the vector k n, m n is an upper limit number in which the elements of the vector k n are duplicated, M n is a set composed of m n pieces of elements which are different from each other, M n [i] is an element on an i-th order of the set M n, the element on the j-th order of the vector k n is an element corresponding to a row on the j-th order of the matrix T n, and the matrices T 0,..., T N-1 and the vectors k 0,..., k N-1 are inputs, the matrix and key generation device comprising: a vector generation unit operable to generate a vector x n, of which a number of pieces of elements is K n and each of the elements is an element of the set Mn, with respect to each of n=0,..., N-1 so that x n [i]≠x n [j] if k n [i]=k n [j] at i≠j; a set generation unit operable to generate a set B n,j with respect to each of n=0,..., N-1 and each of j=1,..., K n so that individual elements correspond to combinations of N-1 pieces of elements, the N-1 pieces of elements being individually selected from sets M 0,..., M N-1 other than the set M n, and x n [j], and the elements for all of the combinations are included; a matrix generation unit operable to generate a matrix T n ' with respect to each of n=0,..., N-1 so that rows identical to T n [j] are included in a number equal to a number of elements of the set B n,j for all of j=1,..., K n; and a key generation unit operable to generate a vector k n ' with respect to each of n=0,..., N-1 so that an element of the matrix T n ', the element corresponding to a row identical to T n [j], corresponds to a combination of k n [j] and an element of the set B n,j and further, the elements of the set B n,j are different from each other when there are a plurality of rows identical to T n [j]. a vector generation unit operable to generate a vector x n, of which a number of pieces of elements is K n and each of the elements is an element of the set Mn, with respect to each of n=0,..., N-1 so that x n [i]≠x n [j] if k n [i]=k n [j] at i≠j; a set generation unit operable to generate a set B n,j with respect to each of n=0,..., N-1 and each of j=1,..., K n so that individual elements correspond to combinations of N-1 pieces of elements, the N-1 pieces of elements being individually selected from sets M 0,..., M N-1 other than the set M n, and x n [j], and the elements for all of the combinations are included; a matrix generation unit operable to generate a matrix T n ' with respect to each of n=0,..., N-1 so that rows identical to T n [j] are included in a number equal to a number of elements of the set B n,j for all of j=1,..., K n; and a key generation unit operable to generate a vector k n ' with respect to each of n=0,..., N-1 so that an element of the matrix T n ', the element corresponding to a row identical to T n [j], corresponds to a combination of k n [j] and an element of the set B n,j and further, the elements of the set B n,j are different from each other when there are a plurality of rows identical to T n [j].