[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content

Multi-key Fully-Homomorphic Aggregate MAC for Arithmetic Circuits

  • Conference paper
  • First Online:
Progress in Cryptology – INDOCRYPT 2024 (INDOCRYPT 2024)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 15495))

Included in the following conference series:

  • 4 Accesses

Abstract

Homomorphic message authenticators allow a user to perform computation on previously authenticated data producing a tag \(\sigma \) that can be used to verify the authenticity of the computation. We extend this notion to consider a multi-party setting where we wish to produce a tag that allows verifying (possibly different) computations on all party’s data at once. Moreover, the size of this tag should not grow as a function of the number of parties or the complexity of the computations. We construct the first aggregate homomorphic MAC scheme that achieves such aggregation of homomorphic tags. Moreover, the final aggregate tag consists of only a single group element. Our construction supports aggregation of computations that can be expressed by bounded-depth arithmetic circuits and is secure in the random oracle model based on the hardness of the Computational Co-Diffie-Hellman problem over an asymmetric bilinear map.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 49.99
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 59.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Notes

  1. 1.

    In what follows we abuse notation to use symbol x both for indeterminate and a scalar point.

  2. 2.

    Labels are used to identify the input wires in an arithmetic circuit describing a homomorphic computation.

  3. 3.

    In what follows, for ease of presentation we drop the subscript l from all terms since we are only considering the case of player \(p_l\).

  4. 4.

    \(\textbf{G}^{\textrm{4}} \) also handles the case of verification of initial Macs in addition to homomorphically computed Macs, but we omit this case from our discussion here to simplify presentation.

References

  1. Agrawal, M., SaptharishiI, R.: Classifying polynomials and identity testing. In: Current Trends in Science. Platinum Jubilee Special. Indian Academy of Sciences (2009)

    Google Scholar 

  2. Anthoine, G., Balbás, D., Fiore, D.: Fully-succinct multi-key homomorphic signatures from standard assumptions. In: Annual International Cryptology Conference, pp. 317–351. Springer (2024)

    Google Scholar 

  3. 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_14

  4. Bellare, M., Namprempre, C., Neven, G.: Unrestricted aggregate signatures. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 411–422. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-73420-8_37

  5. Bellare, M., Rogaway, P.: The exact security of digital signatures-how to sign with RSA and Rabin. In: International Conference on the Theory and Applications of Cryptographic Techniques, pp. 399–416. Springer (1996)

    Google Scholar 

  6. Benabbas, S., Gennaro, R., Vahlis, Y.: Verifiable delegation of computation over large datasets. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 111–131. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22792-9_7

  7. Biswas, S., Yerukhimovich, A.: Multi-key fully-homomorphic aggregate MAC for arithmetic circuits. Cryptology ePrint Archive, Paper 2024/1499 (2024). https://eprint.iacr.org/2024/1499

  8. Bitansky, N., Canetti, R., Chiesa, A., Tromer, E.: From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. In: Goldwasser, S. (ed.) ITCS 2012: 3rd Innovations in Theoretical Computer Science, pp. 326–349. Association for Computing Machinery, Cambridge (2012). https://doi.org/10.1145/2090236.2090263

  9. Boneh, D., Freeman, D.M.: Homomorphic signatures for polynomial functions. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 149–168. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20465-4_10

  10. Boneh, D., Gentry, C., Lynn, B., Shacham, H.: Aggregate and verifiably encrypted signatures from bilinear maps. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 416–432. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-39200-9_26

  11. Boneh, D., Lynn, B., Shacham, H.: Short signatures from the Weil pairing. In: International Conference on the Theory and Application of Cryptology and Information Security, pp. 514–532. Springer (2001)

    Google Scholar 

  12. Catalano, D., Fiore, D.: Practical homomorphic MACs for arithmetic circuits. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 336–352. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38348-9_21

  13. 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_26

  14. DeMillo, R.A., Lipton, R.J.: A probabilistic remark on algebraic program testing. Inf. Process. Lett. 7(4), 193–195 (1978)

    Article  Google Scholar 

  15. Desmedt, Y.: Computer security by redefining what a computer is. In: Michael, J.B., Ashby, V., Meadows, C. (eds.) Proceedings on the 1992–1993 Workshop on New Security Paradigms, 22–24 September 1992; and 3–5 August 1993, Little Compton, pp. 160–166. ACM (1993). https://doi.org/10.1145/283751.283834

  16. Dutta, P., Dwivedi, P., Saxena, N.: Demystifying the border of depth-3 algebraic circuits. In: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 92–103. IEEE (2022)

    Google Scholar 

  17. Fiore, D., Gennaro, R.: Publicly verifiable delegation of large polynomials and matrix computations, with applications. In: Proceedings of the 2012 ACM Conference on Computer and Communications Security, pp. 501–512 (2012)

    Google Scholar 

  18. Fiore, D., Mitrokotsa, A., Nizzardo, L., Pagnin, E.: Multi-key homomorphic authenticators. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10032, pp. 499–530. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53890-6_17

  19. 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_25

  20. 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_37

  21. Gennaro, R., Wichs, D.: Fully homomorphic message authenticators. In: International Conference on the Theory and Application of Cryptology and Information Security, pp. 301–320. Springer (2013)

    Google Scholar 

  22. Gentry, C., Wichs, D.: Separating succinct non-interactive arguments from all falsifiable assumptions. In: Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, pp. 99–108 (2011)

    Google Scholar 

  23. Goldwasser, S., Kalai, Y.T., Rothblum, G.N.: Delegating computation: interactive proofs for muggles. In: Ladner, R.E., Dwork, C. (eds.) 40th Annual ACM Symposium on Theory of Computing, pp. 113–122. ACM Press, Victoria (2008). https://doi.org/10.1145/1374376.1374396

  24. Gorbunov, S., Vaikuntanathan, V., Wichs, D.: Leveled fully homomorphic signatures from standard lattices. In: Servedio, R.A., Rubinfeld, R. (eds.) 47th Annual ACM Symposium on Theory of Computing, pp. 469–477. ACM Press, Portland (2015). https://doi.org/10.1145/2746539.2746576

  25. Gorbunov, S., Wee, H.: Digital signatures for consensus. Cryptology ePrint Archive (2019)

    Google Scholar 

  26. Johnson, R., Molnar, D., Song, D., Wagner, D.: Homomorphic signature schemes. In: Preneel, B. (ed.) CT-RSA 2002. LNCS, vol. 2271, pp. 244–262. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45760-7_17

  27. Katz, J., Lindell, A.Y.: Aggregate message authentication codes. In: Cryptographers’ Track at the RSA Conference, pp. 155–169. Springer (2008)

    Google Scholar 

  28. Katz, J., Lindell, Y.: Introduction to Modern Cryptography: Principles and Protocols. Chapman and Hall/CRC (2007)

    Google Scholar 

  29. Kilian, J.: A note on efficient zero-knowledge proofs and arguments (extended abstract). In: 24th Annual ACM Symposium on Theory of Computing, pp. 723–732. ACM Press, Victoria (1992). https://doi.org/10.1145/129712.129782

  30. Lai, R.W., Tai, R.K., Wong, H.W., Chow, S.S.: Multi-key homomorphic signatures unforgeable under insider corruption. In: International Conference on the Theory and Application of Cryptology and Information Security, pp. 465–492. Springer (2018)

    Google Scholar 

  31. Micali, S.: CS proofs (extended abstracts). In: 35th Annual Symposium on Foundations of Computer Science, pp. 436–453. IEEE Computer Society Press, Santa Fe (1994). https://doi.org/10.1109/SFCS.1994.365746

  32. Parno, B., Howell, J., Gentry, C., Raykova, M.: Pinocchio: nearly practical verifiable computation. Commun. ACM 59(2), 103–112 (2016)

    Article  Google Scholar 

  33. Parno, B., Raykova, M., Vaikuntanathan, V.: How to delegate and verify in public: verifiable computation from attribute-based encryption. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 422–439. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-28914-9_24

  34. Rivest, R.: Two new signature schemes, 2001. In: Cambridge Seminar (2001)

    Google Scholar 

  35. Rückert, M., Schröder, D.: Aggregate and verifiably encrypted signatures from multilinear maps without random oracles. In: International Conference on Information Security and Assurance, pp. 750–759. Springer (2009)

    Google Scholar 

  36. Waters, B., Wu, D.J.: Batch arguments for np and more from standard bilinear group assumptions. In: Annual International Cryptology Conference, pp. 433–463. Springer (2022)

    Google Scholar 

  37. Zippel, R.: Probabilistic algorithms for sparse polynomials. In: International Symposium on Symbolic and Algebraic Manipulation, pp. 216–226. Springer (1979)

    Google Scholar 

Download references

Acknowledgements

We would like to thank Adam O’Neill, Ojaswi Acharya, Weiqi Feng for valuable discussions that led to the problem studied here. Arkady Yerukhimovich is supported in part by NSF grants CNS-1955620 and CNS-2144798 (CAREER).

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Suvasree Biswas .

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2025 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Biswas, S., Yerukhimovich, A. (2025). Multi-key Fully-Homomorphic Aggregate MAC for Arithmetic Circuits. In: Mukhopadhyay, S., Stănică, P. (eds) Progress in Cryptology – INDOCRYPT 2024. INDOCRYPT 2024. Lecture Notes in Computer Science, vol 15495. Springer, Cham. https://doi.org/10.1007/978-3-031-80308-6_10

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-80308-6_10

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-80307-9

  • Online ISBN: 978-3-031-80308-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics