Publications
Detailed Information
Efficient verifiable computation over quotient polynomial rings
Cited 0 time in
Web of Science
Cited 0 time in Scopus
- Authors
- Issue Date
- 2022-10
- Publisher
- Springer Verlag
- Citation
- International Journal of Information Security, Vol.21 No.5, pp.953-971
- 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 ringmore 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, xlog 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.
- ISSN
- 1615-5262
- Files in This Item:
- There are no files associated with this item.
- Appears in Collections:
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.