METHOD AND APPARATUS FOR SECURE DELEGATION OF COMPUTATION

摘要

A method for delegating a computational burden from a computationally limited party to a computationally superior party is disclosed. Computations that can be delegated include inversion and exponentiation modulo any number m. This can be then used for sending encrypted messages by a computationally limited party in a standard cryptographic framework, such as RSA. Security of delegating computation is not based on any computational hardness assumptions, but instead on the presence of numerous decoys of the actual secrets.

主权项

1. A method for delegating computational burden between a sending party and a receiving party for encrypting a message x with a key k to produce an encrypted message xk where the message x is an element of a list of integers (m), the method comprising steps of:
instructing the receiving party to identify n elements (xi . . . xn) from the list of integers (m) having elements xi . . . xm, wherein n is greater than log log (k), greater than zero and is less than m, k is a key known by at least the receiving party that is greater than zero and less than m, wherein the step of instructing is performed by the sending party; getting from the receiving party a list of the n elements (xi . . . xn) that were identified; confirming, for each xi, thatm2n≤xi+1-xi≤mnis satisfied;
choosing r random elements xij from the list of the n elements (xi . . . xn) that were identified, wherein 1≦r≦log log(k) to produce a list of randomly chosen elements 1≦i1, . . . , ir≦n; computing y=xxi1−1xi2−1 . . . xir−1 wherein xi1−1xi2−1 . . . xir−1; sending y to the receiving party; obtaining yk from the receiving party; encrypting the message x with the key k according to xk=xi1k . . . xirkyk wherein yk was obtained by the sending party from the receiving party in the step of obtaining.