Skip to main content
Top

2021 | OriginalPaper | Chapter

Flexible and Efficient Verifiable Computation on Encrypted Data

Authors : Alexandre Bois, Ignacio Cascudo, Dario Fiore, Dongwoo Kim

Published in: Public-Key Cryptography – PKC 2021

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We consider the problem of verifiable and private delegation of computation [Gennaro et al. CRYPTO’10] in which a client stores private data on an untrusted server and asks the server to compute functions over this data. In this scenario we aim to achieve three main properties: the server should not learn information on inputs and outputs of the computation (privacy), the server cannot return wrong results without being caught (integrity), and the client can verify the correctness of the outputs faster than running the computation (efficiency). A known paradigm to solve this problem is to use a (non-private) verifiable computation (VC) to prove correctness of a homomorphic encryption (HE) evaluation on the ciphertexts. Despite the research advances in obtaining efficient VC and HE, using these two primitives together in this paradigm is concretely expensive. Recent work [Fiore et al. CCS’14, PKC’20] addressed this problem by designing specialized VC solutions that however require the HE scheme to work with very specific parameters; notably HE ciphertexts must be over \(\mathbb {Z}_q\) for a large prime q.
In this work we propose a new solution that allows a flexible choice of HE parameters, while staying modular (based on the paradigm combining VC and HE) and efficient (the VC and the HE schemes are both executed at their best efficiency). At the core of our new protocol are new homomorphic hash functions for Galois rings. As an additional contribution we extend our results to support non-deterministic computations on encrypted data and an additional privacy property by which verifiers do not learn information on the inputs of the computation.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Footnotes
1
Precisely, our basic scheme in Sect. 3 works for a q that is a prime power; in the full version of this paper we generalize it to any (possibly composite) integer q.
 
2
It is composed of gates performing addition or multiplication.
 
3
We assume that the cost of basic operation over a ring (\(\mathbb {Z}_t[X]/(h)\) or \(\mathbb {Z}_t[X]/(f)\)) depends on its degree (\(d_h\) or \(d_f\)) for simplicity.
 
4
This is not the case in other schemes, e.g., \(\mathsf {BGV}\) [BGV12] or \(\mathsf {FV}\) [FV12] schemes where multiplication of ciphertexts accompanies rounding or bitwise operations.
 
5
Usual argument systems deal mainly with arithmetic of a field, and it requires to represent arithmetic of a ring by that of a field, resulting in substantial inefficiency.
 
6
We refer to Lemma 1 for this notation.
 
7
Here, we assume that the wiring predicate [CMT12] of the circuit is computable in \(O(\log S)\) complexity. Generally, if the circuit is log-space uniform, the cost of verifier has an additional \(O(poly(\log S))\) term.
 
8
More precisely, the argument follows if \(\varDelta \) is not zero when reduced modulo p. Otherwise, \(\varDelta = p^k \delta \) for some \(k<e\) and a polynomial \(\delta \) which is not zero when reduced modulo p, and \(\delta \) has h as a factor in \(\mathbb {Z}_p[X]\): \(h | \varDelta \) gives that, by division, \(\delta (X) = h(X)Q(X) + p^{e-k}r(X)\) in \(\mathbb {Z}_q[X]\) and h is a factor of \(\delta \) in \(\mathbb {Z}_p[X]\).
 
9
For \(n\in \mathbb {Z}^+\), the function is defined as follows: if n is square-free with k prime factors, \(\mu (n) = (-1)^{k}\); if \(n = 1, \mu (n) = 1\); otherwise, \(\mu (n) = 0\).
 
10
\(\vec {v}^{\,\ell }\) denotes \(\ell \) concatenations of \(\vec v\).
 
11
For this, we skip the modulo reduction by f at the (delegated) computation.
 
12
Each signifies the time complexity of \({\mathcal P}\), that of \(\mathcal{V}\), and the communication cost.
 
13
This operation can be deterministic, e.g., embedding w in the ciphertext space.
 
14
Recall that \(R_q := \mathbb {Z}_q[X]/(f)\) and \(\hat{g}(c_x,c_w) \bmod {f} = \textsf {FHE.Eval}_{pk}(g,(c_x,c_w))\).
 
Literature
[AHIV17]
go back to reference Ames, S., Hazay, C., Ishai, Y., Venkitasubramaniam, M.: Ligero: lightweight sublinear arguments without a trusted setup. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 2017, pp. 2087–2104. ACM Press, New York (2017) Ames, S., Hazay, C., Ishai, Y., Venkitasubramaniam, M.: Ligero: lightweight sublinear arguments without a trusted setup. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 2017, pp. 2087–2104. ACM Press, New York (2017)
[Ben81]
go back to reference Ben-Or, M.: Probabilistic algorithms in finite fields. In: 22nd FOCS, pp. 394–398. IEEE Computer Society Press (October 1981) Ben-Or, M.: Probabilistic algorithms in finite fields. In: 22nd FOCS, pp. 394–398. IEEE Computer Society Press (October 1981)
[BGV12]
go back to reference Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. In: Goldwasser, S. (ed.) ITCS 2012, pp. 309–325. ACM (January 2012) Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. In: Goldwasser, S. (ed.) ITCS 2012, pp. 309–325. ACM (January 2012)
[CMT12]
go back to reference Cormode, G., Mitzenmacher, M., Thaler, J.: Practical verified computation with streaming interactive proofs. In: Goldwasser, S. (ed.) ITCS 2012, pp. 90–112. ACM (January 2012) Cormode, G., Mitzenmacher, M., Thaler, J.: Practical verified computation with streaming interactive proofs. In: Goldwasser, S. (ed.) ITCS 2012, pp. 90–112. ACM (January 2012)
[FGP14]
go back to reference Fiore, D., Gennaro, R., Pastro, V.: Efficiently verifiable computation on encrypted data. In: Ahn, G.-J., Yung, M., Li, N. (eds.) ACM CCS 2014, pp. 844–855. ACM Press (November 2014) Fiore, D., Gennaro, R., Pastro, V.: Efficiently verifiable computation on encrypted data. In: Ahn, G.-J., Yung, M., Li, N. (eds.) ACM CCS 2014, pp. 844–855. ACM Press (November 2014)
[Gen09]
go back to reference Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Mitzenmacher, M. (ed.) 41st ACM STOC, pp. 169–178. ACM Press, New York (2009) Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Mitzenmacher, M. (ed.) 41st ACM STOC, pp. 169–178. ACM Press, New York (2009)
[GKR08]
go back to reference Goldwasser, S., Kalai, Y.T., Rothblum, G.N.: Delegating computation: interactive proofs for muggles. In: Ladner, R.E., Dwork, C. (eds.) 40th ACM STOC, pp. 113–122. ACM Press (May 2008) Goldwasser, S., Kalai, Y.T., Rothblum, G.N.: Delegating computation: interactive proofs for muggles. In: Ladner, R.E., Dwork, C. (eds.) 40th ACM STOC, pp. 113–122. ACM Press (May 2008)
[Kil92]
go back to reference Kilian, J.: A note on efficient zero-knowledge proofs and arguments (extended abstract). In: 24th ACM STOC, pp. 723–732. ACM Press (May 1992) Kilian, J.: A note on efficient zero-knowledge proofs and arguments (extended abstract). In: 24th ACM STOC, pp. 723–732. ACM Press (May 1992)
[Sho99]
go back to reference Shoup, V.: Efficient computation of minimal polynomials in algebraic extensions of finite fields. In: Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation, ISSAC 1999 (1999) Shoup, V.: Efficient computation of minimal polynomials in algebraic extensions of finite fields. In: Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation, ISSAC 1999 (1999)
[SV14]
go back to reference Smart, N.P., Vercauteren, F.: Fully homomorphic SIMD operations. Des. Codes Cryptogr. 71(1), 57–81 (2014)CrossRef Smart, N.P., Vercauteren, F.: Fully homomorphic SIMD operations. Des. Codes Cryptogr. 71(1), 57–81 (2014)CrossRef
[VZGG13]
go back to reference Von Zur Gathen, J., Gerhard, J.: Modern Computer Algebra. Cambridge University Press, Cambridge (2013)CrossRef Von Zur Gathen, J., Gerhard, J.: Modern Computer Algebra. Cambridge University Press, Cambridge (2013)CrossRef
[Wan03]
go back to reference Wan, Z.-X.: Lectures on Finite Fields and Galois Rings. World Scientific Publishing Company, Singapore (2003)CrossRef Wan, Z.-X.: Lectures on Finite Fields and Galois Rings. World Scientific Publishing Company, Singapore (2003)CrossRef
[WTs+18]
go back to reference Wahby, R.S., Tzialla, I., Shelat, A., Thaler, J., Walfish, M.: Doubly-efficient zkSNARKs without trusted setup. In: 2018 IEEE Symposium on Security and Privacy, pp. 926–943. IEEE Computer Society Press (May 2018) Wahby, R.S., Tzialla, I., Shelat, A., Thaler, J., Walfish, M.: Doubly-efficient zkSNARKs without trusted setup. In: 2018 IEEE Symposium on Security and Privacy, pp. 926–943. IEEE Computer Society Press (May 2018)
Metadata
Title
Flexible and Efficient Verifiable Computation on Encrypted Data
Authors
Alexandre Bois
Ignacio Cascudo
Dario Fiore
Dongwoo Kim
Copyright Year
2021
DOI
https://doi.org/10.1007/978-3-030-75248-4_19

Premium Partner