A key generation device according to the present invention hierarchically constructs a Y-ary tree structure where n reception devices are assigned to leaves, and forms subgroups where individual intermediate nodes existing between the leaves and a root of the Y-ary tree structure are defined as parent nodes. By providing new parameters to the individual intermediate parameters, the subgroups can be formed flexibly. In a case where no excluded customer exists or the number of excluded customers is small, the size of a header to be delivered and the calculation amount of an operation that a customer needs to perform can be reduced.