nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Fine-Grained Secure Computation

verfasst von : Matteo Campanelli, Rosario Gennaro

Erschienen in: Theory of Cryptography

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This paper initiates a study of Fine Grained Secure Computation: i.e. the construction of secure computation primitives against “moderately complex” adversaries. We present definitions and constructions for compact Fully Homomorphic Encryption and Verifiable Computation secure against (non-uniform) \(\mathsf {NC}^1\) adversaries. Our results do not require the existence of one-way functions and hold under a widely believed separation assumption, namely \(\mathsf {NC}^{1}\subsetneq \oplus \mathsf {L}/ {\mathsf {poly}}\). We also present two application scenarios for our model: (i) hardware chips that prove their own correctness, and (ii) protocols against rational adversaries potentially relevant to the Verifier’s Dilemma in smart-contracts transactions such as Ethereum.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Secure Computation Using Leaky Correlations (Asymptotically Optimal Constructions)

Nächstes Kapitel On the Structure of Unconditional UC Hybrid Protocols

Nur mit Berechtigung zugänglich

We intentionally refer to it as “cost” to keep the notion generic. For concreteness one can think of C as the running time required to run the protocol.

A separation implied by \(\mathsf {L}\ne \mathsf {NC}^1\). See Sect. 1.1 for more details.

This is a reference to Impagliazzo’s “five possible worlds” [Imp95].

Naturally the security guarantees of these schemes are more limited compared to their standard definitions.

The techniques in [GKR08, GR18] are based on properties of finite fields. Arithmetic in such fields can be carried out by circuits of constant depth with threshold gates (\(\mathsf {TC}^0\)), but not in \(\mathsf {AC}^0[2]\).

Where the ciphertexts do not grow in size with each homomorphic operation.

Where not only the circuit depth is constant but also the size of the circuit is quasilinear – the size of the verification circuit should be \(O({\mathsf {poly}}(\lambda )(n+m))\) where n and m are the size of the input and output respectively.

More precisely, that a permutation statistically indistinguishable from a random one can be sampled in \(\mathsf {AC}^0\).

See also Remark C.1.

TrueBit: https://truebit.io/.

Stated as Lemma 4.3 in [DVV16].

We are only requiring to decrypt ciphertexts that are output by \(\mathsf {HE.Eval}(\cdots )\).

In terms of circuit depth, the main overhead when evaluating f homomorphically is given by the multiplication gates (addition, on the other hand, is “for free” — see definition of \(\mathsf {HE.Eval}\) above). A single homomorphic multiplication can be performed by a depth two \(\mathsf {AC}^0[2]\) circuit, but this requires depth \(\varOmega (\log (n))\) with a circuit of fan-in two. Therefore, a circuit for f with \(\omega (1)\) multiplicative depth would require an evaluation of \(\omega (\log (n))\) depth, which would be out of \(\mathsf {NC}^1\). On the other hand, observe that for any function f in \(\mathsf {AC}^0[2]\) with constant multiplicative depth, the evaluation stays in \(\mathsf {AC}^0[2]\). This because there is a constant number (depth) of homomorphic multiplications each requiring an \(\mathsf {AC}^0[2]\) computation.

In the evaluation algorithm we ignore the distinction between deterministic and random input.

The reader can find additional details in Appendix B.

Recall that the output of the expanded approximating function \(f'\) is a bit string and thus each \(\varvec{c}^{\text {out}}_i\) encrypts a bit string.

Further details on the complexity of \(\mathcal{VC}\) follow. All the algorithms are in \(\mathsf {AC}^0_{\text {CM}}[2]\), except for the online stage. In fact, \(\mathsf {VC.Verify}\) and \(\mathsf {VC.ProbGen}\) are in \(\mathsf {AC}^0[2]\). Moreover, they are not in \(\mathsf {AC}^0_{\text {Q}}[2]\) as they perform in parallel a non-constant (polylogarithmic) number of decryptions and permutations respectively, and these involve non-constant fan-in gates. Notice that even though the online stage is not in \(\mathsf {AC}^0_{\text {Q}}[2]\) we still have a gain at verification time (although not in an asymptotic sense). This because of the specific structure of these circuits. Consider for example what happens when implementing \(\mathsf {VC.Verify}\) or \(\mathsf {VC.ProbGen}\) with a fan-in two circuit. Their depth will be \(c (\log (n)+\log (\lambda ))\) for a constant c. Contrast this with a circuit f in \(\mathsf {AC}^0_{\text {Q}}[2]\) of constant depth D that we may want to verify. With fan-in two, the depth of f will become \(c'D\log (n)\) (for a constant \(c'\)), which may be significantly larger.

We refer the reader to [Gol01].

Notice that the syntax of \(\mathsf {Eval}\) can also be extended to return a sequence of encryptions for the case of multi-output functions. We will use this fact in Sect. 3.3. See also Remark A.1.

This allows our \(\mathsf {NC}^0\) circuit to “know” which gates to copy and which ones to transform based on their position only.

I.e. the size of the verification circuit should be \(O({\mathsf {poly}}(\lambda )(n+m))\) where n and m are the size of the input and output respectively.

These observations would not hold for the computational setting, which is out of the scope of this paper.

[ACK+02]

Anderson, D.P., Cobb, J., Korpela, E., Lebofsky, M., Werthimer, D.: SETI@home: an experiment in public-resource computing. Commun. ACM 45(11), 56–61 (2002)CrossRef

[AIK04]

Applebaum, B., Ishai, Y., Kushilevitz, E.: Cryptography in \(NC^{0}\). In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 166–175 (2004)

[AIK10]

Applebaum, B., Ishai, Y., Kushilevitz, E.: From secrecy to soundness: efficient verification via secure computation. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6198, pp. 152–163. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14165-2_14CrossRef

[AM12]

Azar, P.D., Micali, S.: Rational proofs. In: Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, pp. 1017–1028. ACM (2012)

[AM13]

Azar, P.D., Micali, S.: Super-efficient rational proofs. In: Proceedings of the Fourteenth ACM Conference on Electronic Commerce, pp. 29–30. ACM (2013)

[BCI+13]

Bitansky, N., Chiesa, A., Ishai, Y., Paneth, O., Ostrovsky, R.: Succinct non-interactive arguments via linear interactive proofs. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 315–333. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36594-2_18CrossRef

[BP11]

Boyar, J., Peralta, R.C.: A depth-16 circuit for the AES S-box. IACR Cryptology ePrint Archive (2011)

[BRSV17]

Ball, M., Rosen, A., Sabin, M., Vasudevan, P.N.: Average-case fine-grained hardness. In: Electronic Colloquium on Computational Complexity (ECCC), vol. 24, p. 39 (2017)

[BV14]

Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) lwe. SIAM J. Comput. 43(2), 831–871 (2014)MathSciNetCrossRef

[CG15]

Campanelli, M., Gennaro, R.: Sequentially composable rational proofs. In: Khouzani, M.H.R., Panaousis, E., Theodorakopoulos, G. (eds.) GameSec 2015. LNCS, vol. 9406, pp. 270–288. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-25594-1_15CrossRef

[CG17]

Campanelli, M., Gennaro, R.: Efficient rational proofs for space bounded computations. In: Rass, S., An, B., Kiekintveld, C., Fang, F., Schauer, S. (eds.) International Conference on Decision and Game Theory for Security, vol. 10575, pp. 53–73. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-68711-7_4CrossRefMATH

[CKV10]

Chung, K.-M., Kalai, Y., Vadhan, S.: Improved delegation of computation using fully homomorphic encryption. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 483–501. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_26CrossRef

[CM97]

Cachin, C., Maurer, U.: Unconditional security against memory-bounded adversaries. In: Kaliski, B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 292–306. Springer, Heidelberg (1997). https://doi.org/10.1007/BFb0052243CrossRef

[CMT12]

Cormode, G., Mitzenmacher, M., Thaler, J.: Practical verified computation with streaming interactive proofs. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pp. 90–112. ACM (2012)

[DN92]

Dwork, C., Naor, M.: Pricing via processing or combatting junk mail. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 139–147. Springer, Heidelberg (1993). https://doi.org/10.1007/3-540-48071-4_10CrossRef

[DVV16]

Degwekar, A., Vaikuntanathan, V., Vasudevan, P.N.: Fine-grained cryptography. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9816, pp. 533–562. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53015-3_19CrossRef

[Gen09]

Gentry, C.: A fully homomorphic encryption scheme. Stanford University (2009)

[GGH+07]

Goldwasser, S., Gutfreund, D., Healy, A., Kaufman, T., Rothblum, G.N.: Verifying and decoding in constant depth. In: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, pp. 440–449. ACM (2007)

[GGH+16]

Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. SIAM J. Comput. 45(3), 882–929 (2016)MathSciNetCrossRef

[GGP10]

Gennaro, R., Gentry, C., Parno, B.: Non-interactive verifiable computing: outsourcing computation to untrusted workers. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 465–482. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_25CrossRef

[GGPR13]

Gennaro, R., Gentry, C., Parno, B., Raykova, M.: Quadratic span programs and succinct NIZKs without PCPs. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 626–645. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38348-9_37CrossRef

[GKR08]

Goldwasser, S., Kalai, Y.T., Rothblum, G.N.: Delegating computation: interactive proofs for muggles. In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, pp. 113–122. ACM (2008)

[GMR89]

Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186–208 (1989)MathSciNetCrossRef

[Gol01]

Goldreich, O.: Foundations of Cryptography: Basic Tools, vol. 1. Cambridge University Press, New York (2001)CrossRef

[Gol09]

Goldreich, O.: Foundations of Cryptography: Basic Applications, vol. 2. Cambridge University Press, New York (2009)MATH

[GR18]

Goldreich, O., Rothblum, G.N.: Simple doubly-efficient interactive proof systems for locally-characterizable sets. In: LIPIcs-Leibniz International Proceedings in Informatics, vol. 94. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)

[Hag91]

Hagerup, T.: Fast parallel generation of random permutations. In: Albert, J.L., Monien, B., Artalejo, M.R. (eds.) ICALP 1991. LNCS, vol. 510, pp. 405–416. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-54233-7_151CrossRef

[Has87]

Hastad, J.: One-way permutations in NC0. Inf. Process. Lett. 26(3), 153–155 (1987)CrossRef

[IK00a]

Ishai, Y., Kushilevitz, E.: Randomizing polynomials: a new representation with applications to round-efficient secure computation. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, pp. 294–304. IEEE (2000)

[IK02]

Ishai, Y., Kushilevitz, E.: Perfect constant-round secure computation via perfect randomizing polynomials. In: Widmayer, P., Eidenbenz, S., Triguero, F., Morales, R., Conejo, R., Hennessy, M. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 244–256. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45465-9_22CrossRef

[Imp95]

Impagliazzo, R.: A personal view of average-case complexity. In: Proceedings of Tenth Annual IEEE Structure in Complexity Theory Conference, pp. 134–147. IEEE (1995)

[LTKS15]

Luu, L., Teutsch, J., Kulkarni, R., Saxena, P.: Demystifying incentives in the consensus computer. In: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pp. 706–719. ACM (2015)

[Mer78]

Merkle, R.C.: Secure communications over insecure channels. Commun. ACM 21(4), 294–299 (1978)CrossRef

[MV91]

Matias, Y., Vishkin, U.: Converting high probability into nearly-constant time - with applications to parallel hashing. In: Proceedings of the Twenty-third Annual ACM Symposium on Theory of Computing, STOC 1991, pp. 307–316. ACM, New York (1991)

[Raz87]

Razborov, A.A.: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Math. Notes Acad. Sci. USSR 41(4), 333–338 (1987)CrossRef

[SYY99]

Sander, T., Young, A., Yung, M.: Non-interactive cryptocomputing for NC1. In: Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p. 554. IEEE Computer Society (1999)

[Yao82]

Yao, A.C.: Protocols for secure computations. In: 23rd Annual Symposium on Foundations of Computer Science, SFCS 2008, pp. 160–164. IEEE (1982)

Titel: Fine-Grained Secure Computation
verfasst von: Matteo Campanelli
Rosario Gennaro
Verlag: Springer International Publishing
Buch: Theory of Cryptography
Print ISBN: 978-3-030-03809-0

Electronic ISBN: 978-3-030-03810-6

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-030-03810-6_3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner