A secure maximum value computation apparatus comprising: an initialization unit configured to set X' = X, assuming X = {[[x 1]], [[x 2]],..., [[x n]]}, wherein a value of a certain value a hid by encryption, secret sharing, or the like is referred to as a secret value of a and is represented as [[a]]; a pair creation unit configured to create, from among the X', one or more pairs in such a manner that no element in the X' is included in two or more pairs; a determination unit configured to determine, through secure computation, a secret value that is a larger value among [[x i]] and [[x j]] included in each of the one or more pairs, with respect to an order R for each of the one or more pairs that are created; a set updating unit configured to set, as a new X', when there is a secret value that is not included in the one or more pairs in the X', a set including the secret value that is not included in the one or more pairs in the X' and the secret value determined by the determination unit; a control unit configured to perform a control to repeat, with the new X' as the X', processing operations of the pair creation unit, the determination unit, and the set updating unit until |X'| = 1 holds; and a flag determination unit configured to determine, with a secret value that is an only element of the X' that meets |X'| = 1 as a maximum value, a flag [[z(x i)]] (i = 1,..., n) in such a manner that [[z(x g)]] = [] holds when [[x g]] (g ∈ [1, n]) is a maximum value and [[z(x i)]] = [] holds when i ≠ g holds, characterized in that the pair creation unit is configured to create two or more pairs at least once; and the flag determination unit determines the flag [[z(x i)]] (i = 1,..., n) by performing following processing operations (a) and (b), on [x i] that is included in the X' even once: (a) the flag determination unit sets [[z(x g)]] = [] when [[x i]] is [[x g]], and (b) when [[x k]] is computed by the comparison between [[x i]] and [[x j]] and [[z(x k)]] has already been computed, the flag determination unit uses the comparison result of [[x i]] and [[x j]], and [[z(x k)]] to perform computation such that [[z(x+)]] = [[x k]] holds for [[x+]], which is the larger one of [[x i]] and [[x j]], and that [[z(x-)]] = [] holds for [[x-]], which is not the larger one of [[x i]] and [[x j]], wherein the computation of the flag [[z(x i)]] is performed in the reverse order of the computations of the pair creation unit, the determination unit, the set updating unit and the control unit. an initialization unit configured to set X' = X, assuming X = {[[x 1]], [[x 2]],..., [[x n]]}, wherein a value of a certain value a hid by encryption, secret sharing, or the like is referred to as a secret value of a and is represented as [[a]]; a pair creation unit configured to create, from among the X', one or more pairs in such a manner that no element in the X' is included in two or more pairs; a determination unit configured to determine, through secure computation, a secret value that is a larger value among [[x i]] and [[x j]] included in each of the one or more pairs, with respect to an order R for each of the one or more pairs that are created; a set updating unit configured to set, as a new X', when there is a secret value that is not included in the one or more pairs in the X', a set including the secret value that is not included in the one or more pairs in the X' and the secret value determined by the determination unit; a control unit configured to perform a control to repeat, with the new X' as the X', processing operations of the pair creation unit, the determination unit, and the set updating unit until |X'| = 1 holds; and a flag determination unit configured to determine, with a secret value that is an only element of the X' that meets |X'| = 1 as a maximum value, a flag [[z(x i)]] (i = 1,..., n) in such a manner that [[z(x g)]] = [] holds when [[x g]] (g ∈ [1, n]) is a maximum value and [[z(x i)]] = [] holds when i ≠ g holds, characterized in that the pair creation unit is configured to create two or more pairs at least once; and the flag determination unit determines the flag [[z(x i)]] (i = 1,..., n) by performing following processing operations (a) and (b), on [x i] that is included in the X' even once: (a) the flag determination unit sets [[z(x g)]] = [] when [[x i]] is [[x g]], and (b) when [[x k]] is computed by the comparison between [[x i]] and [[x j]] and [[z(x k)]] has already been computed, the flag determination unit uses the comparison result of [[x i]] and [[x j]], and [[z(x k)]] to perform computation such that [[z(x+)]] = [[x k]] holds for [[x+]], which is the larger one of [[x i]] and [[x j]], and that [[z(x-)]] = [] holds for [[x-]], which is not the larger one of [[x i]] and [[x j]], (a) the flag determination unit sets [[z(x g)]] = [] when [[x i]] is [[x g]], and (b) when [[x k]] is computed by the comparison between [[x i]] and [[x j]] and [[z(x k)]] has already been computed, the flag determination unit uses the comparison result of [[x i]] and [[x j]], and [[z(x k)]] to perform computation such that [[z(x+)]] = [[x k]] holds for [[x+]], which is the larger one of [[x i]] and [[x j]], and that [[z(x-)]] = [] holds for [[x-]], which is not the larger one of [[x i]] and [[x j]], wherein the computation of the flag [[z(x i)]] is performed in the reverse order of the computations of the pair creation unit, the determination unit, the set updating unit and the control unit.