Witness-based cryptographic program checking and robust function sharing

Abstract

We suggest a new methodology for "result checking" that enables us to extend the notion of Blum's program result checking to the on-line checking of cryptographic functions. In our model, the checker not only needs to be assured of the correctness of the result but the owner of the program needs to be sure not to give away anything but the requested result on the (authorized) input. The existing approaches for program result checking of numerical problems often ask the program a number of extra queries (different from the actual input). In the case of cryptographic functions, this may be in contradiction with the security requirement of the program owner. Additional queries, in fact, may be used to gain unauthorized advantage (for example, imagine the implications of the on-line checking of a decryption device that requires the decryption of extra ciphertexts). In [Blum88], the notion of a simple checker was introduced where, for the purpose of efficiency, extra queries are not allowed. In our model, we do allow extra queries, but only when the response does not carry "knowledge," (namely computational advantage). We use a new "witnessbased" approach and give constructions that apply to various cryptographic scenarios while making sure that the checker/program interaction releases no extra knowledge. It is based on the fact that with certain homomorphic functions, having a witness which is an initial correct value will enable checking the entire function domain, and the fact that having a random value of a cryptographic function typically does not reduce its security. The notion has various applications. A particularly useful application is achieving "efficient robust function sharing", a method by which the power to apply a cryptographic function (e.g., RSA decryption/signature) is shared among multiple trustees. As long as a quorum of the trustees is not corrupted and is available, we can apply the function on the input parameters while maintaining the security of the function. With robustness we are able to tolerate and identify misbehaving trustees, both with efficiency and on-line, when computing a function value.