A key exchanging apparatus transmits the contribution data to the plurality of counterpart apparatuses, generates a signer contribution confirmation signature with respect to a contribution data set including all the contribution data received from the plurality of counterpart apparatuses, generates auxiliary data and auxiliary data validity certification sentence from the contribution data set and the contribution random number, transmits the auxiliary data, the auxiliary data validity certification sentence and the contribution confirmation signature to the plurality of counterpart apparatuses, verifies validity of auxiliary data by using the counterpart identifier set, the counterpart public key set, the contribution confirmation signature set including the data received from the plurality of counterpart apparatuses, the auxiliary data set and the auxiliary data validity certification sentence set, and generates a public key from the contribution data set and the auxiliary data received from the plurality of counterpart apparatuses.