nach oben

Journal of Cryptology

Erschienen in:

04.01.2017

Practical Homomorphic Message Authenticators for Arithmetic Circuits

verfasst von: Dario Catalano, Dario Fiore

Erschienen in: Journal of Cryptology | Ausgabe 1/2018

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Homomorphic message authenticators allow the holder of a (public) evaluation key to perform computations over previously authenticated data, in such a way that the produced tag \(\sigma \) can be used to certify the authenticity of the computation. More precisely, a user, knowing the secret key \(\mathsf{sk}\) used to authenticate the original data, can verify that \(\sigma \) authenticates the correct output of the computation. This primitive has been recently formalized by Gennaro and Wichs, who also showed how to realize it from fully homomorphic encryption. In this paper, we show new constructions of this primitive that, while supporting a smaller set of functionalities (i.e., polynomially bounded arithmetic circuits as opposite to boolean ones), are much more efficient and easy to implement. Moreover, our schemes can tolerate any number of (malicious) verification queries. Our first construction relies on the sole assumption that one-way functions exist, allows for arbitrary composition (i.e., outputs of previously authenticated computations can be used as inputs for new ones) but has the drawback that the size of the produced tags grows with the degree of the circuit. Our second solution, relying on the D-Diffie-Hellman Inversion assumption, offers somewhat orthogonal features as it allows for very short tags (one single group element!) but poses some restrictions on the composition side.

Vorheriger Artikel Minimizing Locality of One-Way Functions via Semi-private Randomized Encodings

Nächster Artikel Functional Encryption for Randomized Functionalities in the Private-Key Setting from Minimal Assumptions

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

Informally, the degree of an arithmetic circuit is related to the degree of the polynomial computed by the circuit (see next section for more details).

Very briefly, this assumption states that it is computationally infeasible to compute \(g^{1/x}\), given \(g, g^{x}, g^{x^2}, \ldots , g^{x^{D-1}}\).

More precisely, their basic construction cannot support verification queries at all. This can be extended to allow for some fixed a priori number of queries q at the cost of increasing by O(q) the size of the tag.

While, in general, every polynomial defines a unique function, the converse is not true as a function may be expressed as a polynomial in several ways.

One should think of such a situation as if one stored two different values under the same unique index in a remote database.

The same argument can be actually extended to \(d/p<1/c\) for some constant c.

This bound follows from that one can use optimized algorithms based on FFT to compute the convolution.

However, this \(r_{{\tau }^*}\) might have been implicitly used before. In particular the adversary might have already asked some non-easy verification query containing the input label \({\tau }^*\).

S. Agrawal and D. Boneh. Homomorphic MACs: MAC-based integrity for network coding, in M. Abdalla, D. Pointcheval, P.-A. Fouque, and D. Vergnaud, editors, ACNS 09, volume 5536 of LNCS (Springer, 2009), pp. 292–305

J. H. Ahn, D. Boneh, J. Camenisch, S. Hohenberger, a. shelat, and B. Waters. Computing on authenticated data, in R. Cramer, editor, TCC 2012, volume 7194 of LNCS (Springer, 2012), pp. 1–20

B. Applebaum, Y. Ishai, and E. Kushilevitz. From secrecy to soundness: Efficient verification via secure computation, in S. Abramsky, C. Gavoille, C. Kirchner, F. Meyer auf der Heide, and P.G. Spirakis, editors, ICALP 2010, Part I, volume 6198 of LNCS (Springer, 2010), pp. 152–163

N. Attrapadung and B. Libert. Homomorphic network coding signatures in the standard model, in D. Catalano, N. Fazio, R. Gennaro, and A. Nicolosi, editors, PKC 2011, volume 6571 of LNCS (Springer, 2011), pp. 17–34

N. Attrapadung, B. Libert, and T. Peters. Computing on authenticated data: New privacy definitions and constructions, in X. Wang and K. Sako, editors, ASIACRYPT 2012, volume 7658 of LNCS (Springer, 2012), pp. 367–385

N. Attrapadung, B. Libert, and T. Peters. Efficient completely context-hiding quotable and linearly homomorphic signatures, in K. Kurosawa and G. Hanaoka, editors, PKC 2013, volume 7778 of LNCS (Springer, 2013), pp. 386–404

M. Backes, D. Fiore, and R. M. Reischuk. Verifiable delegation of computation on outsourced data, in A.-R. Sadeghi, V. D. Gligor, and M. Yung, editors, ACM CCS 13 (ACM Press, 2013) pp. 863–874

S. Benabbas, R. Gennaro, and Y. Vahlis. Verifiable delegation of computation over large datasets, in P. Rogaway, editor, CRYPTO 2011, volume 6841 of LNCS (Springer, 2011), pp. 111–131

N. Bitansky, R. Canetti, A. Chiesa, and E. Tromer. From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again, in S. Goldwasser, editor, ITCS 2012 (ACM 2012), pp. 326–349

10.

N. Bitansky, R. Canetti, A. Chiesa, and E. Tromer. Recursive composition and bootstrapping for SNARKs and proof-carrying data. Cryptology ePrint Archive, Report 2012/095, 2012. http://eprint.iacr.org/2012/095

11.

D. Boneh, D. Freeman, J. Katz, and B. Waters. Signing a linear subspace: Signature schemes for network coding, in S. Jarecki and G. Tsudik, editors, PKC 2009, volume 5443 of LNCS (Springer, 2009), pp. 68–87

12.

D. Boneh and D. M. Freeman. Homomorphic signatures for polynomial functions, in K. G. Paterson, editor, EUROCRYPT 2011, volume 6632 of LNCS (Springer, 2011), pp. 149–168

13.

D. Boneh and D. M. Freeman. Linearly homomorphic signatures over binary fields and new tools for lattice-based signatures, in D. Catalano, N. Fazio, R. Gennaro, and A. Nicolosi, editors, PKC 2011, volume 6571 of LNCS (Springer, 2011), pp. 1–16

14.

X. Boyen. The uber-assumption family (invited talk), in S.D. Galbraith and K.G. Paterson, editors, PAIRING 2008, volume 5209 of LNCS (Springer, 2008), pp. 39–56

15.

D. Catalano and D. Fiore. Practical homomorphic MACs for arithmetic circuits, in T. Johansson and P.Q. Nguyen, editors, EUROCRYPT 2013, volume 7881 of LNCS (Springer, 2013), pp. 336–352

16.

D. Catalano, D. Fiore, R. Gennaro, and L. Nizzardo. Generalizing homomorphic MACs for arithmetic circuits, in H. Krawczyk, editor, PKC 2014, volume 8383 of LNCS (Springer, 2014), pp. 538–555

17.

D. Catalano, D. Fiore, R. Gennaro, and K. Vamvourellis. Algebraic (trapdoor) one-way functions and their applications, in A. Sahai, editor, TCC 2013, volume 7785 of LNCS (Springer, 2013), pp. 680–699

18.

D. Catalano, D. Fiore, R. Gennaro, and K. Vamvourellis. Algebraic (trapdoor) one-way functions: Constructions and applications. Theoretical Computer Science, 592:143–165, 2015.MathSciNetCrossRefMATH

19.

D. Catalano, D. Fiore, and L. Nizzardo. Programmable hash functions go private: Constructions and application to (homomorphic) signatures with shorter public keys, in Advances in Cryptology—CRYPTO 2015—35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16–20, 2015, Proceedings, Part II, volume 9216 of LNCS (Springer, 2015), pp. 254–274

20.

D. Catalano, D. Fiore, and B. Warinschi. Adaptive pseudo-free groups and applications, in K.G. Paterson, editor, EUROCRYPT 2011, volume 6632 of LNCS (Springer, 2011), pp. 207–223

21.

D. Catalano, D. Fiore, and B. Warinschi. Efficient network coding signatures in the standard model, in M. Fischlin, J. Buchmann, and M. Manulis, editors, PKC 2012, volume 7293 of LNCS (Springer, 2012), pp. 680–696

22.

D. Catalano, D. Fiore, and B. Warinschi. Homomorphic signatures with efficient verification for polynomial functions, in J.A. Garay and R. Gennaro, editors, CRYPTO 2014, Part I, volume 8616 of LNCS (Springer, 2014), pp. 371–389

23.

K.-M. Chung, Y. Kalai, and S. P. Vadhan. Improved delegation of computation using fully homomorphic encryption, in T. Rabin, editor, CRYPTO 2010, volume 6223 of LNCS (Springer, 2010), pp. 483–501

24.

K.-M. Chung, Y. T. Kalai, F.-H. Liu, and R. Raz. Memory delegation, in P. Rogaway, editor, CRYPTO 2011, volume 6841 of LNCS (Springer, 2011), pp. 151–168

25.

R. A. DeMillo and R. J. Lipton. A probabilistic remark on algebraic program testing. Information Processing Letters, 7(4):193–195, 1978.CrossRefMATH

26.

D. Fiore and R. Gennaro. Publicly verifiable delegation of large polynomials and matrix computations, with applications, in T. Yu, G. Danezis, and V.D. Gligor, editors, ACM CCS 12 (ACM Press, 2012), pp. 501–512

27.

D. M. Freeman. Improved security for linearly homomorphic signatures: A generic framework, in M. Fischlin, J. Buchmann, and M. Manulis, editors, PKC 2012, volume 7293 of LNCS (Springer, 2012), pp. 697–714

28.

R. Gennaro, C. Gentry, and B. Parno. Non-interactive verifiable computing: Outsourcing computation to untrusted workers, in T. Rabin, editor, CRYPTO 2010, volume 6223 of LNCS (Springer, 2010), pp. 465–482

29.

R. Gennaro, J. Katz, H. Krawczyk, and T. Rabin. Secure network coding over the integers, in P.Q. Nguyen and D. Pointcheval, editors, PKC 2010, volume 6056 of LNCS (Springer, 2010), pp. 142–160

30.

R. Gennaro and D. Wichs. Fully homomorphic message authenticators, in K. Sako and P. Sarkar, editors, ASIACRYPT 2013, Part II, volume 8270 of LNCS (Springer, 2013), pp. 301–320

31.

C. Gentry. Fully homomorphic encryption using ideal lattices, in M. Mitzenmacher, editor, 41st ACM STOC (ACM Press, 2009), pp. 169–178

32.

C. Gentry and D. Wichs. Separating succinct non-interactive arguments from all falsifiable assumptions, in L. Fortnow and S.P. Vadhan, editors, 43rd ACM STOC (ACM Press, 2011), pp. 99–108

33.

S. Goldwasser, Y.T. Kalai, and G.N. Rothblum. Delegating computation: interactive proofs for muggles, in R.E. Ladner and C. Dwork, editors, 40th ACM STOC (ACM Press, 2008), pp. 113–122

34.

S. Gorbunov, V. Vaikuntanathan, and D. Wichs. Leveled fully homomorphic signatures from standard lattices, in 47th ACM STOC (ACM Press, 2015)

35.

R. Johnson, D. Molnar, D.X. Song, and D. Wagner. Homomorphic signature schemes, in B. Preneel, editor, CT-RSA 2002, volume 2271 of LNCS (Springer, 2002), pp. 244–262

36.

J. Kilian. A note on efficient zero-knowledge proofs and arguments (extended abstract), in 24th ACM STOC (ACM Press, 1992), pp. 723–732

37.

B. Libert, T. Peters, M. Joye, and M. Yung. Linearly homomorphic structure-preserving signatures and their applications, in R. Canetti and J.A. Garay, editors, CRYPTO 2013, Part II, volume 8043 of LNCS (Springer, 2013), pp. 289–307

38.

S. Micali. CS proofs (extended abstracts), in 35th FOCS (IEEE Computer Society Press, 1994), pp. 436–453

39.

S. Mitsunari, R. Sakai, and M. Kasahara. A new traitor tracing. IEICE Transactions on Fundamentals, E85-A(2):481–484, 2002.

40.

B. Parno, M. Raykova, and V. Vaikuntanathan. How to delegate and verify in public: Verifiable computation from attribute-based encryption, in R. Cramer, editor, TCC 2012, volume 7194 of LNCS (Springer, 2012), pp. 422–439

41.

J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27:701–717, 1980.MathSciNetCrossRefMATH

42.

H. Shacham and B. Waters. Compact proofs of retrievability, in J. Pieprzyk, editor, ASIACRYPT 2008, volume 5350 of LNCS (Springer, 2008), pp. 90–107

43.

A. Shpilka and A. Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science, 5(3-4):207–388, 2010.MathSciNetMATH

44.

P. Valiant. Incrementally verifiable computation or proofs of knowledge imply time/space efficiency, in R. Canetti, editor, TCC 2008, volume 4948 of LNCS (Springer, 2008), pp. 1–18

45.

R. Zippel. Probabilistic algorithms for sparse polynomials. In E. W. Ng, editor, EUROSM ’79, volume 72 of Lecture Notes in Computer Science (Springer, 1979), pp. 216–226

Titel: Practical Homomorphic Message Authenticators for Arithmetic Circuits
verfasst von: Dario Catalano
Dario Fiore
Publikationsdatum: 04.01.2017
Verlag: Springer US
Erschienen in: Journal of Cryptology / Ausgabe 1/2018
Print ISSN: 0933-2790
Elektronische ISSN: 1432-1378
DOI: https://doi.org/10.1007/s00145-016-9249-1

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"

Weitere Artikel der Ausgabe 1/2018

Incremental Deterministic Public-Key Encryption

Minimizing Locality of One-Way Functions via Semi-private Randomized Encodings

Functional Encryption for Randomized Functionalities in the Private-Key Setting from Minimal Assumptions

A Black-Box Construction of Non-malleable Encryption from Semantically Secure Encryption

Making the Impossible Possible

How Many Queries are Needed to Distinguish a Truncated Random Permutation from a Random Function?