TY - JOUR
T1 - Efficient verifiable computation over quotient polynomial rings
AU - Park, Jai Hyun
AU - Cheon, Jung Hee
AU - Kim, Dongwoo
N1 - Publisher Copyright:
© 2022, The Author(s), under exclusive licence to Springer-Verlag GmbH, DE.
PY - 2022/10
Y1 - 2022/10
N2 - In a situation where computation and data are delegated to the third party, e.g., in cloud computing services, securing both data privacy and computation integrity simultaneously has been a challenging problem. Recently, (Fiore et al., 2014) proposed a generic solution where the data privacy is guaranteed with homomorphic encryption (HE) and the computation integrity is guaranteed with verifiable computation (VC) on the ciphertext operations of HE. However, the main bottleneck was the huge cost of VC for operations of ciphertexts which are over quotient polynomial rings. In this paper, we propose an efficient VC for operations of quotient polynomial rings, which can resolve this bottleneck. Specifically, we adapt Goldwasser, Kalai, Rothblum’s interactive proof protocol (a.k.a. GKR protocol), and its recent refinements to handle arithmetic of a quotient polynomial ring more efficiently. The main ideas are (i) to generalize the previous approaches exploiting commitment schemes for efficient verification of field operations to the case of polynomial ring operations, and (ii) to reduce the verification of operations on polynomials to that of operations on scalars. As a result, our method provides substantial asymptotic efficiency improvement (roughly, × log N-- N where N is the degree of polynomials) compared to usual VC when verifying operations of quotient polynomial rings, which is also confirmed by our experimental evaluation.
AB - In a situation where computation and data are delegated to the third party, e.g., in cloud computing services, securing both data privacy and computation integrity simultaneously has been a challenging problem. Recently, (Fiore et al., 2014) proposed a generic solution where the data privacy is guaranteed with homomorphic encryption (HE) and the computation integrity is guaranteed with verifiable computation (VC) on the ciphertext operations of HE. However, the main bottleneck was the huge cost of VC for operations of ciphertexts which are over quotient polynomial rings. In this paper, we propose an efficient VC for operations of quotient polynomial rings, which can resolve this bottleneck. Specifically, we adapt Goldwasser, Kalai, Rothblum’s interactive proof protocol (a.k.a. GKR protocol), and its recent refinements to handle arithmetic of a quotient polynomial ring more efficiently. The main ideas are (i) to generalize the previous approaches exploiting commitment schemes for efficient verification of field operations to the case of polynomial ring operations, and (ii) to reduce the verification of operations on polynomials to that of operations on scalars. As a result, our method provides substantial asymptotic efficiency improvement (roughly, × log N-- N where N is the degree of polynomials) compared to usual VC when verifying operations of quotient polynomial rings, which is also confirmed by our experimental evaluation.
KW - Homomorphic encryption
KW - Quotient polynomial rings
KW - Secure outsourcing
KW - Verifiable computation
UR - http://www.scopus.com/inward/record.url?scp=85128542987&partnerID=8YFLogxK
U2 - 10.1007/s10207-022-00590-x
DO - 10.1007/s10207-022-00590-x
M3 - Article
AN - SCOPUS:85128542987
SN - 1615-5262
VL - 21
SP - 953
EP - 971
JO - International Journal of Information Security
JF - International Journal of Information Security
IS - 5
ER -