Secret falsification detecting system, secret computation apparatus, secret falsification detecting method, and program

A secret falsification detecting system for detecting falsification during secret computation, with N secret computation apparatuses having, as inputs, shared values [a0], . . . , [aM-1] obtained by secret sharing M values a0, . . . , aM-1 and, as an output, a function value [F([a0], . . . , [aM-1])] obtained with a function F for performing secret computation that uses J types of secret sharing,

• wherein N is an integer equal to or larger than 3, M is an integer equal to or larger than 1, μ is an integer equal to or larger than 1, J is an integer equal to or larger than 2, m is an integer equal to or larger than 0 and smaller than M, and j is an integer equal to or larger than 0 and smaller than J;
• each of the secret computation apparatuses comprising:
• circuitry configured to
• obtain shared values [r0]m . . . , [rJ-1] by distributing J random numbers r0, . . . , rJ-1 by the secret sharing such that the random numbers r0, . . . , rJ-1 are concealed from all of the N secret computation apparatuses;
• calculate a shared value [amrj] by multiplying the shared value [am] by the shared value [rj], and generate a randomized shared value <am>:=<[am], [amrj]> by pairing the shared value [am] and the shared value [amrj], wherein the m-th shared value [am] is a shared value obtained by the j-th secret sharing;
• obtain, when performing secret computation that uses the j-th secret sharing, the function value [F([a0], . . . , [aM-1])] while including in a checksum Cj, randomized shared values that are computation objects and randomized shared values that are computation results;
• wait until all of secret computation that uses secret sharing are completed;
• and
• verify that the shared value [φj] obtained by multiplying the sum of shared values [f0], . . . , [fμj-1] included in the checksum Cj:=(<f0>, . . . , <fμj-1>) by the shared value [rj] is equal to the shared value [ψj] obtained by adding shared values [f0rj], . . . , [fμj-1rj] included in the checksum Cj:=(<f0>, . . . , <fμj-1>), wherein, for j=0, . . . , J−1, μj indicates the total number of randomized shared values included in the j-th checksum Cj, and <f0>, . . . , <fμj-1> indicate the randomized shared values included in the j-th checksum Cj;
• wherein when it is determined that no falsification is found after verifying all of J checksums C0, . . . , CJ-1, the system outputs the function value [F([a0], . . . , [aM-1])], and when it is determined that falsification is found, the system outputs information indicating that falsification is found,
• wherein j′ is an integer equal to or larger than 0 and smaller than J, j≢j′, the j-th secret sharing and the j′-th secret sharing are on an identical ring, and the j-th secret sharing can be converted to the j′-th secret sharing with a method in which falsification can be detected or a method in which falsification is impossible,
• the shared value [rj] is generated by secret sharing the random number rj by the j-th secret sharing, and the shared value [rj is converted to a shared value [rj′] obtained by the j′-th secret sharing, and
• the shared value [φj] calculated from the j-th checksum Cj and the shared value [ψj] calculated from the checksum Cj are converted to shared values obtained by the j′-th secret sharing, and it is verified that the shared value [ψj+ψj′] obtained by adding the shared value [ψj] to the shared value [ψj′] calculated from the j′-th checksum Cj′ is equal to the shared value [ψj+ψj′] obtained by adding the shared value [ψj] to the shared value [ψj′] calculated from the j′-th checksum Cj′.

A secret computation apparatus

• that is part of a secret falsification detecting system for detecting falsification during secret computation, with N secret computation apparatuses having, as inputs, shared values [a0], . . . , [aM-1] obtained by secret sharing M values a0, . . . , aM-1 and, as an output, a function value [F([a0], . . . , [aM-1])] obtained with a function F for performing secret computation that uses J types of secret sharing,
• for detecting falsification during secret computation, the secret computation apparatus having, as inputs, shared values [a0], . . . , [aM-1] obtained by secret sharing M values a0, . . . , aM-1 and, as an output, a function value [F([a0], . . . , [aM-1])] obtained with a function F for performing secret computation that uses J types of secret sharing,
• wherein M is an integer equal to or larger than 1, μ is an integer equal to or larger than 1, J is an integer equal to or larger than 2, m is an integer equal to or larger than 0 and smaller than M, and j is an integer equal to or larger than 0 and smaller than J;
• the secret computation apparatus comprising:
• circuitry configured to
• obtain shared values [r0], . . . , [rJ-1] by distributing J random numbers r0, . . . , rJ-1 by the secret sharing such that the random numbers r0, . . . , rJ-1 are concealed from all of the N secret computation apparatuses;
• calculate a shared value [amrj] by multiplying the shared value [am] by the shared value [rj], and generate a randomized shared value <am>:=<[am], [amrj]> by pairing the shared value [am] and the shared value [amrj], wherein the m-th shared value [am] is a shared value obtained by the i-th secret sharing;
• obtain, when performing secret computation that uses the i-th secret sharing the function value [F([a0], . . . , [aM-1])] while including, in a checksum Cj, randomized shared values that are computation objects and randomized shared values that are computation results;
• wait until all of secret computation that uses secret sharing are completed;
• and
• verify that the shared value [φj] obtained by multiplying the sum of shared values [f0], . . . , [fμj-1] included in the checksum Cj:=(<f0>, . . . , <fμj-1>) by the shared value [rj] is equal to the shared value [ψj] obtained by adding shared values [f0rj], . . . , [fμj-1rj], included in the checksum Cj:=(<f0>, . . . , <fμj-1>), wherein, for j=0, . . . , J−1, μj indicates the total number of randomized shared values included in the i-th checksum Cj, and <f0>, . . . , <fμj-1> indicate the randomized shared values included in the i-th checksum Cj;
• and
• wherein when it is determined that no falsification is found after verifying all of J checksums C0, . . . , CJ-1, the system outputs the function value [F([a0], . . . , [aM-1])], and when it is determined that falsification is found, the system outputs information indicating that falsification is found,
• wherein j′ is an integer equal to or larger than 0 and smaller than J, j≢j′, the j-th secret sharing and the j′-th secret sharing are on an identical ring, and the j-th secret sharing can be converted to the j′-th secret sharing with a method in which falsification can be detected or a method in which falsification is impossible,
• the shared value [rj] is generated by secret sharing the random number rj by the j-th secret sharing, and the shared value [rj] is converted to a shared value [rj′] obtained by the j′-th secret sharing, and
• the shared value [φj] calculated from the j-th checksum Cj and the shared value [ψj] calculated from the checksum Cj are converted to shared values obtained by the j′-th secret sharing, and it is verified that the shared value [φj+φj′] obtained by adding the shared value [φj] to the shared value [φj′] calculated from the j′-th checksum Cj′is equal to the shared value [ψj+ψj′] obtained by adding the shared value [104 j] to the shared value [ψj′] calculated from the j′-th checksum Cj′.

A non-transitory computer readable medium including computer executable instructions that make a secret computation apparatus for detecting falsification during secret computation perform a secret falsification detecting method, the secret computation apparatus having, as inputs, shared values [a0], . . . , [aM-1] obtained by secret sharing M values a0, . . . , aM-1 and, as an output, a function value [F([a0], . . . , [aM-1])] obtained with a function F for performing secret computation that uses J types of secret sharing,

• wherein M is an integer equal to or larger than 1, μ is an integer equal to or larger than 1, J is an integer equal to or larger than 2, m is an integer equal to or larger than 0 and smaller than M, and j is an integer equal to or larger than 0 and smaller than J;
• the secret falsification detecting method comprising:
• obtaining shared values [r0], . . . , [rJ-1] by distributing J random numbers r0, . . . , rJ-1 by the secret sharing such that the random numbers r0, . . . , rJ-1 are concealed from all of the N secret computation apparatuses;
• calculating a shared value [amrj] by multiplying the shared value [am] by the shared value [rj], and generating a randomized shared value <am>:=<[am], [amrj]> by pairing the shared value [am] and the shared value [amrj], wherein the m-th shared value [am] is a shared value obtained by the j-th secret sharing;
• obtaining, when performing secret computation that uses the j-th secret sharing, the function value [F([a0], . . . , [aM-1])] while including, in a checksum Cj, randomized shared values that are computation objects and randomized shared values that are computation results;
• waiting until all of secret computation that uses secret sharing are completed;
• and
• verifying that the shared value [φj] obtained by multiplying the sum of shared values [f0], . . . [fμj-1] included in the checksum Cj:=(<f0>, . . . , <fμj-1>) by the shared value [rj] is equal to the shared value [ψj] obtained by adding shared values [f0rj], . . . , [fμj-1rj] included in the checksum Cj:=(<f0>, . . . , <fμj-1>), wherein, for j=0, . . . , J−1, μj indicates the total number of randomized shared values included in the j-th checksum Cj, and <f0>, . . . , <fμj-1> indicate the randomized shared values included in the i-th checksum Cj;
• and
• when it is determined that no falsification is found after verifying all of J checksums C0, . . . , CJ-1, outputting the function value [F([a0], . . . , [aM-1])], and when it is determined that falsification is found, outputting information indicating that falsification is found,
• wherein j′ is an integer equal to or larger than 0 and smaller than J, j≢j′, the j-th secret sharing and the j′-th secret sharing are on an identical ring, and the j-th secret sharing can be converted to the j′-th secret sharing with a method in which falsification can be detected or a method in which falsification is impossible,
• the shared value [rj] is generated by secret sharing the random number rj by the j-th secret sharing, and the shared value [rj] is converted to a shared value [rj′] obtained by the j′-th secret sharing, and
• the shared value [φj] calculated from the j-th checksum Cj and the shared value [ψj] calculated from the checksum Cj are converted to shared values obtained by the j′-th secret sharing, and it is verified that the shared value [φj+φj′] obtained by adding the shared value [φj] to the shared value [φj′] calculated from the j′-th checksum Cj′is equal to the shared value [ψj+ψj′] obtained by adding the shared value [ψj] to the shared value [ψj′] calculated from the j′-th checksum Cj′.