Verifiable Computing for Approximate Arithmetic
김동우 · Seoul National University Open Repository (Seoul National University) · 2020
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, have mainly focused on exact computations, but not approximate arithmetic, e.g., floating-point or fixed-point arithmetic.This makes it hard to apply them to certain types of computations (e.g., machine learning, data analysis, and scientific computation) that inherently require approximate arithmetic.In this thesis, we present an efficient interactive proof system for arithmetic circuits with rounding gates that can represent approximate arithmetic.The main idea is to represent the rounding gate into a small subcircuit, and reuse the machinery of the Goldwasser, Kalai, and Rothblum's protocol (also known as the GKR protocol) and its recent refinements.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 represent the rounding operation by a low-degree i ii polynomial over a ring, and develop a novel, optimal circuit construction of an arbitrary polynomial to transform the rounding polynomial to an optimal 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 system for approximate arithmetic.For example, our implementation performed two orders of magnitude better than the existing system for a nested 128ˆ128 matrix multiplication of depth 12 on the 16-bit fixed-point arithmetic.