Distributed information generation apparatus, reconstruction apparatus, reconstruction result verification apparatus, and secret information distribution system, method, and program

A reconstruction result verification system including:

• a distributed information generation apparatus that distributes secret information, comprising:
• a secret information distribution apparatus;
• a distributed secret information distribution apparatus;
• and
• a distribution input means that receives secret information s, a threshold k, a number of distributed information n, and a predetermined fixed value t;
• wherein
• the secret information distribution apparatus includes:
• a first random number generation apparatus that generates n first random numbers which are different from the fixed value t and are different from one another, and outputs the generated first random numbers;
• a first distribution polynomial generation apparatus that generates a (k−1)-degree polynomial F by embedding the secret information s in the (k−1)-degree polynomial F;
• and
• a distributed information output apparatus that enters the respective first random numbers into the polynomial F to output values and also enters the fixed value t into the polynomial F to output a value;
• and wherein
• the distributed secret information distribution apparatus includes:
• a second random number generation apparatus that generates n second random numbers that are different from one another, and outputs the generated second random numbers;
• a second distribution polynomial generation apparatus that generates a (k−1)-degree polynomial G by embedding the output of the distributed information output apparatus in the (k−1)-degree polynomial G, the output of the distributed information output apparatus being the output when the fixed value t is entered into the polynomial F;
• and
• a distributed distributed information output apparatus that enters the respective second random numbers into the polynomial G to output values;
• and
• a reconstruction result verification apparatus that verifies a value output by a reconstruction apparatus that reconstructs secret information, wherein
• the reconstruction result verification apparatus receives a (k−1)-degree polynomial F output by the reconstruction apparatus and receives from storage apparatuses that store the outputs of the distributed information generation apparatus, a pair of a first random number r output by the secret information distribution apparatus, and an output v when the first random number r is entered into the polynomial F generated by the secret information distribution apparatus,
• outputs information indicating that cheating has not been detected when the received value v is equal to an output obtained by entering the first random number r into the polynomial F, and
• outputs information indicating detection of cheating when the received value v is not equal to the output.

A method of generating distributed information comprising:

• a distribution input step of receiving by a distribution input means information s, a threshold k, a number of distributed information n, and a predetermined fixed value t;
• a secret information distribution step;
• and
• a distributed secret information distribution step;
• the secret information distribution step including:
• a first random number generation step of generating by a secret information distribution apparatus n first random numbers that are different from the fixed value t and are different from one another, and outputting the generated first random numbers to store the generated first random numbers in a storage unit;
• a first distribution polynomial generation step of generating by the secret information distribution apparatus a (k−1)-degree polynomial F by embedding the secret information s in the (k−1)-degree polynomial F;
• and
• a distributed information output step of entering by the secret information distribution apparatus the respective first random numbers into the polynomial F to output values and also entering the fixed value t into the polynomial F to output a value to store the generated first random numbers in a storage unit;
• the distributed secret information distribution step including:
• a second random number generation apparatus step of generating by a distributed secret information distribution apparatus n second random numbers that are different from one another, and outputting the generated second random numbers to store the generated second random numbers in a storage unit;
• a second distribution polynomial generation step of generating by the distributed secret information distribution apparatus a (k−1)-degree polynomial G by embedding the output of the distributed information output step in the (k−1)-degree polynomial G, the output of the distributed information output step being the output when the fixed value t is entered into the polynomial F;
• and
• a distributed distributed information output step of entering by the distributed secret information distribution apparatus the respective second random numbers into the polynomial G to output values.

A reconstruction result verification method for verifying restored secret information, comprising a distributed information generation step that includes:

• a distribution input step, performed by a computing device, of receiving secret information s, a threshold k, a number of distributed information n, and a predetermined fixed value t;
• a secret information distribution step, performed by the computing device;
• and
• a distributed secret information distribution step, performed by the computing device;
• the secret information distribution step including:
• a first random number generation step, performed by the computing device, of generating n first random numbers that are different from the fixed value t and are different from one another, and outputting the generated first random numbers;
• a first distribution polynomial generation step, performed by the computing device, of generating a (k−1)-degree polynomial F by embedding the secret information s in the (k−1)-degree polynomial F;
• and
• a distributed information output step, performed by the computing device, of entering the respective first random numbers into the polynomial F to output values and also entering the fixed value t into the polynomial F to output a value;
• the distributed secret information distribution step including:
• a second random number generation apparatus step, performed by the computing device, of generating n second random numbers that are different from one another, and outputting the generated second random numbers;
• a second distribution polynomial generation step, performed by the computing device, of generating a (k−1)-degree polynomial G by embedding the output of the distributed information output step in the (k−1)-degree polynomial G, the output of the distributed information output step being the output when the fixed value t is entered into the polynomial F;
• and
• a distributed distributed information output step, performed by the computing device, of entering the respective second random numbers into the polynomial G to output values, wherein
• a (k−1)-degree polynomial F is received as the restored secret information, a pair of a first random number r output in the secret information distribution step and an output v when the first random number r is entered into the polynomial F generated in the secret information distribution step are received from storage apparatuses that store the contents output in the distributed information generation step, information indicating that cheating has not been detected is output when the received value v is equal to an output obtained by entering the first random number r into the polynomial F, and information indicating detection of cheating is output when the received value v is not equal to the output.

A computer-readable memory device storing a distributed information generation program for distributing secret information, the distributed information generation program causing a computer to execute:

• a distribution input process that receives secret information s, a threshold k, a number of distributed information n, and a predetermined fixed value t;
• a secret information distribution process;
• and
• a distributed secret information distribution process;
• in the secret information distribution process, the computer being caused to execute:
• a first random number generation process that generates n first random numbers which are different from the fixed value t and are different from one another, and outputs the generated first random numbers;
• a first distribution polynomial generation process that generates a (k−1)-degree polynomial F by embedding the secret information s in the (k−1)-degree polynomial F;
• and
• a distributed information output process that enters the respective first random numbers into the polynomial F to output values and also enters the fixed value t into the polynomial F to output a value;
• in the distributed secret information distribution process, the computer is caused to execute:
• a second random number generation process that generates n second random numbers which are different from one another, and outputs the generated second random numbers;
• a second distribution polynomial generation process that generates a (k−1)-degree polynomial G by embedding the output of the distributed information output process in the (k−1)-degree polynomial G, the output of the distributed information output process being the output when the fixed value t is entered into the polynomial F;
• and
• a distributed distributed information output process that enters the respective second random numbers to the polynomial G to output values.

A reconstruction result verification system, comprising:

• a distributed information generation apparatus and a reconstruction result verification apparatus that verifies a value output by a reconstruction apparatus that reconstructs secret information;
• wherein the distributed information generation apparatus includes:
• a secret information distribution apparatus that receives secret information s, a threshold k, a number of distributed information n, and a predetermined fixed value t, generates and outputs n first random numbers which are different from the fixed value t and are different from one another, generates a (k−1)-degree polynomial F′ by embedding the secret information s in the (k−1)-degree polynomial F′ enters the respective first random numbers into the polynomial F to output values, and enters the fixed value t into the polynomial F to output a value;
• and
• a distributed secret information distribution apparatus that generates and outputs n second random numbers that are different from one another, generates a (k−1)-degree polynomial G by embedding in the (k−1)-degree polynomial G the output of the secret information distribution apparatus when the fixed value t is entered into the polynomial F, and enters the respective second random numbers into the polynomial G to output values, wherein the reconstruction result verification apparatus includes:
• a unit that receives a (k−1)-degree polynomial F output by the reconstruction apparatus and receives from storage apparatuses that store the outputs of the distributed information generation apparatus, a pair of a first random number r output by the secret information distribution apparatus of the distributed information generation apparatus and an output v when the first random number r is entered into the polynomial F generated by the secret information distribution apparatus,
• a unit that outputs information indicating that cheating has not been detected when the received value v is equal to an output obtained by entering the first random number r into the polynomial F, and
• a unit that outputs information indicating detection of cheating when the received value v is not equal to the output.

A reconstruction apparatus comprising:

• a reconstruction input means that receives a threshold k and a fixed value t;
• a polynomial reconstruction apparatus that receives values v1 through vk and values r1 through rk which are different from one another and outputs a (k−1)-degree polynomial F′ which respectively supplies the values v1 through vk when the values r1 through rk are entered;
• a distributed secret information restoration apparatus that receives values w1 through wk and values x1 through xk which are different from one another and outputs a (k−1)-degree polynomial G′ which respectively supplies the values w1 through wk when the values x1 through xk are entered;
• and
• a cheating detection apparatus that outputs a value embedded in the polynomial F′ as secret information when a value embedded in the polynomial G′ is equal to an output obtained by entering the fixed value t into the polynomial F′ and outputs information indicating detection of cheating when the value embedded in the polynomial G′ is not equal to the output.

A reconstruction method for reconstructing secret information, the method comprising:

• receiving by a reconstruction input means a threshold k and a fixed value t;
• receiving by a polynomial reconstruction apparatus values v1 through vk and values r1 through rk which are different from one another and outputting a (k−1)-degree polynomial F′ which respectively supplies the values v1 through vk when the values r1 through rk are entered;
• receiving by a distributed secret information restoration apparatus values w1 through wk and values x1 through xk which are different from one another and outputting a (k−1)-degree polynomial G′ which respectively supplies the values w1 through wk when the values x1 through xk are entered;
• and
• outputting by a cheating detection apparatus a value embedded in the polynomial F′ as secret information when a value embedded in the polynomial G′ is equal to an output obtained by entering the fixed value t into the polynomial F′, and outputting information indicating detection of cheating when the value embedded in the polynomial G′ is not equal to the output.

A computer-readable memory device storing a reconstruction program for reconstructing secret information, the program causing a computer to execute:

• a reconstruction input process of receiving a threshold k and a fixed value t;
• a polynomial reconstruction process of receiving values v1 through vk and values r1 through rk which are different from one another and outputting a (k−1)-degree polynomial F′ which respectively supplies the values v1 through vk when the values r1 through rk are entered;
• and
• a distributed secret information reconstruction process of receiving values w1 through wk and values x1 through xk which are different from one another and outputting a (k−1)-degree polynomial G′ which respectively supplies the values w1 through wk when the values x1 through xk are entered;
• and
• a cheating detection process of outputting a value embedded in the polynomial F′ as secret information when a value embedded in the polynomial G′ is equal to an output obtained by entering the fixed value t into the polynomial F′, and outputting information indicating detection of cheating when the value embedded in the polynomial G′ is not equal to the output.