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.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
In what follows we abuse notation to use symbol x both for indeterminate and a scalar point.
- 2.
Labels are used to identify the input wires in an arithmetic circuit describing a homomorphic computation.
- 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.
\(\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
Agrawal, M., SaptharishiI, R.: Classifying polynomials and identity testing. In: Current Trends in Science. Platinum Jubilee Special. Indian Academy of Sciences (2009)
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)
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
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
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)
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
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
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
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
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
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)
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
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
DeMillo, R.A., Lipton, R.J.: A probabilistic remark on algebraic program testing. Inf. Process. Lett. 7(4), 193–195 (1978)
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
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)
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)
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
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
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
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)
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)
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
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
Gorbunov, S., Wee, H.: Digital signatures for consensus. Cryptology ePrint Archive (2019)
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
Katz, J., Lindell, A.Y.: Aggregate message authentication codes. In: Cryptographers’ Track at the RSA Conference, pp. 155–169. Springer (2008)
Katz, J., Lindell, Y.: Introduction to Modern Cryptography: Principles and Protocols. Chapman and Hall/CRC (2007)
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
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)
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
Parno, B., Howell, J., Gentry, C., Raykova, M.: Pinocchio: nearly practical verifiable computation. Commun. ACM 59(2), 103–112 (2016)
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
Rivest, R.: Two new signature schemes, 2001. In: Cambridge Seminar (2001)
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)
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)
Zippel, R.: Probabilistic algorithms for sparse polynomials. In: International Symposium on Symbolic and Algebraic Manipulation, pp. 216–226. Springer (1979)
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
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2025 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
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)