HIGHLY EFFICIENT SECRECY-PRESERVING PROOFS OF CORRECTNESS OF COMPUTATION

摘要

Presented are methods and systems for highly efficient proofs of correctness of computations that preserve secrecy of the input values and calculations. One embodiment includes a method for verifiably determining at least one output for a secrecy preserving computations where the method includes acts of calculating an output from submitted inputs according to an announced calculation, translating a value in the calculation into two components that are a randomized representation of that value, publishing commitments to the at least two components, revealing a portion of the randomized representation in response to a verification request, and enabling verification of the calculation of the output using the revealed portion of the randomized representation. According to one aspect of the secrecy preserving verification the numbers involved in the secrecy preserving calculation are represented by a randomly constructed representing pair. In another aspect, revealing one member of the pair allows for verification without compromising secrecy. In one embodiment, arrangement of the translation process ensures that in the verification only truly independently random numbers, or operations on them, are revealed and checked.