You are looking at a specific version 20190702:142305 of this paper. See the latest version.

Paper 2019/762

Verifiable Computing for Approximate Computation

Shuo Chen and Jung Hee Cheon and Dongwoo Kim and Daejun Park

Abstract

Verifiable computing (VC) is a complexity-theoretic method to secure the integrity of computations. The need is increasing as more computations are outsourced to untrusted parties, e.g., cloud platforms. Existing techniques, however, only deal with exact computations, without the capability of rounding (e.g., "$1.11 \times 2.22 = 2.4642$" is verifiable, but $1.11 \times 2.22 \simeq 2.46$" is not). Hence, in a long sequence of calculations (e.g., multiplications), the number of digits of the result keeps increasing and will quickly exceed the precision limit of the underlying system. Because of this limitation, VC is currently missing the opportunity in the whole AI space where approximate computations are unavoidable. In pursuit of the vision of verifiable AI computing, a solution to support the rounding operation is necessary. In this paper, we present an efficient verifiable computing scheme to achieve it. The main idea is to reduce the rounding operation into an efficient arithmetic circuit representation, and reuse the machinery of the Goldwasser, Kalai, and Rothblum's protocol (also known as the GRK protocol), the state-of-the-art interactive proof protocol. Specifically, we shift the algebraic structure from a field to a ring to better deal with the notion of "digits", and generalize the original GKR protocol over a ring. Then, we reduce the rounding operation to a low-degree polynomial in a ring, and present a novel, optimal circuit construction of an arbitrary polynomial to transform the rounding polynomial to an optimal arithmetic circuit representation. Moreover, we further optimize the proof generation cost for rounding by employing a Galois ring. We provide experimental results that show the efficiency of our scheme for approximate computations. For example, our implementation performed two orders of magnitude better than the existing GKR protocol for a nested 128x128 matrix multiplication of depth 12 on the 16-bit fixed-point arithmetic.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
verifiable computinginteractive proofsapproximate arithmeticdelegation of computation
Contact author(s)
shuochen @ microsoft com,jhcheon @ snu ac kr,dwkim606 @ snu ac kr,daejunpark @ gmail com
History
2019-07-02: received
Short URL
https://ia.cr/2019/762
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.