Verifiable computation using re-randomizable garbled circuits

• Main Authors: ZHAO, Qingsong, ZENG, Qingkai, LIU, Ximeng, XU, Huanliang
• Format: text
• Language: Chinese
• Published: Institutional Knowledge at Singapore Management University 2019
• Subjects: Cryptographic reverse firewall; Homomorphic encryption; Re-randomizable garbled circuit; Verifiable computation; Information Security
• Online Access: https://ink.library.smu.edu.sg/sis_research/4417; https://ink.library.smu.edu.sg/context/sis_research/article/5420/viewcontent/create_pdf.pdf
• Institution: Singapore Management University

Yao's garbled circuit allows a client to outsource a function computation to a server with verifiablity. Unfortunately, the garbled circuit suffers from a one-time usage. The combination of fully homomorphic encryption (FHE) and garbled circuits enables the client and the server to reuse the garbled circuit with multiple inputs (Gennaro et al.). However, there still seems to be a long way to go for improving the efficiency of all known FHE schemes and it need much stronger security assumption. On the other hand, the construction is only proven to be secure in a weaker model where an adversary can not issue any number of verification queries to the client. Somewhat homomorphic encryption schemes, whose assumptions are much weaker than the FHE schemes, support a limited number of homomorphic operations. However, they can be much faster and more compact than the FHE schemes. In this work, a verifiable computation scheme is presented which can tolerate any number of malicious verification queries with additively homomorphic encryption. The proposed technique comes from the construction of re-randomizable garbled circuits in which the distribution of the original garbled circuit is computationally indistinguishable from the re-randomized garbled circuit. The proposed scheme is based on the decisional Diffie-Hellman (DDH) assumption. A technique solution is also given to construct cryptographic reverse firewalls, which is called reusable cryptographic reverse firewalls, using re-randomizable garbled circuits. Namely, the solution allows garbled circuits to be generated once and then securely re-randomized for many times on cryptographic reverse firewalls.