A vector generation unit generates a vector xn so that xn[i]≠xn[j] if kn[i]=kn[j] at i≠j. A set generation unit generates a set Bn,j so that individual elements correspond to combinations of the N−1 pieces of elements, which are individually selected from sets M0, . . . , MN−1 other than a set Mn, and xn[j] and the elements for all of the combinations are included. A matrix generation unit generates a matrix Tn′ so that the matrix Tn′ includes rows identical to Tn[j] in the number equal to the number of elements of the set Bn,j. A key generation unit generates a vector kn′ so that elements of the matrix Tn′ which correspond to a row identical to Tn[j] correspond to combinations of kn[j] and elements of the set Bn,j and further, the elements of the set Bn,j are different from each other when there are a plurality of rows identical to Tn[j].