Efficient verifiable computation over quotient polynomial rings

Jai Hyun Park, Jung Hee Cheon, Dongwoo Kim

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)953-971
Number of pages19
JournalInternational Journal of Information Security
Volume21
Issue number5
DOIs
StatePublished - Oct 2022

Keywords

  • Homomorphic encryption
  • Quotient polynomial rings
  • Secure outsourcing
  • Verifiable computation

Fingerprint

Dive into the research topics of 'Efficient verifiable computation over quotient polynomial rings'. Together they form a unique fingerprint.

Cite this