One-time Programs with Cloud Storage and Its Application to Electronic Money

A One-time Program (OTP) is a program, proposed by Goldwasser et al., in which the number of executions is restricted to once. The OTP uses a Garbled Circuit (GC), a circuit which does not leak the information except the execution result, as a building block. However, we need to use a special hardware called One-time Memory (OTM) to permit access to only one of two labels necessary for the execution of the GC. When the OTM does not exist or it is expensive, the realistic realization of the OTP is difficult. Furthermore, the OTM needs to be transported to a program executor and needs the production cost. Instead of using OTMs, we propose a way to distribute inputs to multiple cloud storages by using Shamir's secret sharing. In addition, we apply the proposed method to electronic money. Existing electronic money schemes do not prevent double-spending itself, but detect it and identify the double-spender. Therefore, one can double-spend the same electronic money illegally in a short time. Then we can detect the double-spending and identify the double-spender after delivering a product, but the double-spender can abscond with it. To tackle such a problem, we construct an electronic money scheme which prevents double-spending itself based on the OTP that generates a digital signature during a transaction. Combining the proposed electronic money scheme with an existing electronic money scheme, we can also construct another electronic money scheme which can detect double-spending even if the security of the OTP is broken.