TY - JOUR
T1 - Interactive Proofs for Rounding Arithmetic
AU - Chen, Shuo
AU - Cheon, Jung Hee
AU - Kim, Dongwoo
AU - Park, Daejun
N1 - Publisher Copyright:
© 2013 IEEE.
PY - 2022
Y1 - 2022
N2 - Interactive proofs are a type of verifiable computing that secures the integrity of computations. The need is increasing as more computations are outsourced to untrusted parties, e.g., cloud computing 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 or financial applications) that inherently require approximate arithmetic. In this paper, we present an efficient interactive proof system for arithmetic circuits with rounding gates that can represent approximate arithmetic. The main idea is to reduce the rounding gate into a small sub-circuit without rounding, 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 reduce the rounding operation to a low-degree 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, further optimization on the proof generation cost for rounding is presented employing a Galois ring. Our experimental results show the efficiency of our protocol for approximate arithmetic, e.g., the implementation performed two orders of magnitude better than the existing system for a nested 128 by 128 matrix multiplication of depth 12 on the 16-bit fixed-point arithmetic.
AB - Interactive proofs are a type of verifiable computing that secures the integrity of computations. The need is increasing as more computations are outsourced to untrusted parties, e.g., cloud computing 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 or financial applications) that inherently require approximate arithmetic. In this paper, we present an efficient interactive proof system for arithmetic circuits with rounding gates that can represent approximate arithmetic. The main idea is to reduce the rounding gate into a small sub-circuit without rounding, 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 reduce the rounding operation to a low-degree 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, further optimization on the proof generation cost for rounding is presented employing a Galois ring. Our experimental results show the efficiency of our protocol for approximate arithmetic, e.g., the implementation performed two orders of magnitude better than the existing system for a nested 128 by 128 matrix multiplication of depth 12 on the 16-bit fixed-point arithmetic.
KW - Approximate arithmetic
KW - interactive proof
KW - verifiable computing
UR - http://www.scopus.com/inward/record.url?scp=85142784193&partnerID=8YFLogxK
U2 - 10.1109/ACCESS.2022.3223136
DO - 10.1109/ACCESS.2022.3223136
M3 - Article
AN - SCOPUS:85142784193
SN - 2169-3536
VL - 10
SP - 122706
EP - 122725
JO - IEEE Access
JF - IEEE Access
ER -