Efficient message authentication codes with combinatorial group testing. (English) Zbl 1504.94220

Pernul, Günther (ed.) et al., Computer security – ESORICS 2015. 20th European symposium on research in computer security, Vienna, Austria, September 21–25, 2015. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 9326, 185-202 (2015).
Summary: Message authentication code, MAC for short, is a symmetric-key cryptographic function for authenticity. A standard MAC verification only tells whether the message is valid or invalid, and thus we can not identify which part is corrupted in case of invalid message. In this paper we study a class of MAC functions that enables to identify the part of corruption, which we call group testing MAC (GTM). This can be seen as an application of a classical (non-adaptive) combinatorial group testing to MAC. Although the basic concept of GTM (or its keyless variant) has been proposed in various application areas, such as data forensics and computer virus testing, they rather treat the underlying MAC function as a black box, and exact computation cost for GTM seems to be overlooked. In this paper, we study the computational aspect of GTM, and show that a simple yet non-trivial extension of parallelizable MAC (PMAC) enables \(O(m+t)\) computation for \(m\) data items and \(t\) tests, irrespective of the underlying test matrix we use, under a natural security model. This greatly improves efficiency from naively applying a black-box MAC for each test, which requires \(O(mt)\) time. Based on existing group testing methods, we also present experimental results of our proposal and observe that ours runs as fast as taking single MAC tag, with speed-up from the conventional method by factor around 8 to 15 for \(m=10^4\) to \(10^5\) items.
For the entire collection see [Zbl 1492.68028].


94A62 Authentication, digital signatures and secret sharing
94A60 Cryptography
68M25 Computer security
Full Text: DOI


[1] CAESAR : competition for authenticated encryption: security, applicability, and robustness. http://competitions.cr.yp.to/index.html/
[2] Recommendation for block cipher modes of operation: the CMAC mode for authentication. NIST special publication 800-38B (2005), national institute of standards and technology
[3] Bellare, M., Desai, A., Jokipii, E., Rogaway, P.: A concrete security treatment of symmetric encryption. In: FOCS 1997, pp. 394-403. IEEE Computer Society (1997). doi:10.1109/SFCS.1997.646128
[4] Bellare, M., Goldreich, O., Mityagin, A.: The Power of verification queries in message authentication and authenticated encryption. Cryptology ePrint Archive, Report 2004/309 (2004). http://eprint.iacr.org/
[5] Bellare, M.; Kilian, J.; Rogaway, P., The security of the cipher block chaining message authentication code, J. Comput. Syst. Sci., 61, 3, 362-399, 2000 · Zbl 0970.68054 · doi:10.1006/jcss.1999.1694
[6] Black, JA; Rogaway, P.; Bellare, M., CBC MACs for arbitrary-length messages: the three-key constructions, Advances in Cryptology - CRYPTO 2000, 197-215, 2000, Heidelberg: Springer, Heidelberg · Zbl 0995.94545 · doi:10.1007/3-540-44598-6_12
[7] Black, JA; Rogaway, P.; Knudsen, LR, A block-cipher mode of operation for parallelizable message authentication, Advances in Cryptology - EUROCRYPT 2002, 384-397, 2002, Heidelberg: Springer, Heidelberg · Zbl 1056.94520 · doi:10.1007/3-540-46035-7_25
[8] De Bonis, A.; Di Crescenzo, G.; Fu, B.; Du, D-Z, Combinatorial group testing for corruption localizing hashing, Computing and Combinatorics, 579-591, 2011, Heidelberg: Springer, Heidelberg · Zbl 1353.94046 · doi:10.1007/978-3-642-22685-4_50
[9] Cheraghchi, M., Noise-resilient group testing: limitations and constructions, Discrete Appl. Math., 161, 1-2, 81-95, 2013 · Zbl 1253.68256 · doi:10.1016/j.dam.2012.07.022
[10] Di Crescenzo, G.; Arce, G.; Shi, YQ; Kim, H-J; Perez-Gonzalez, F., Data forensics constructions from cryptographic hashing and coding, Digital Forensics and Watermarking, 494-509, 2012, Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-642-32205-1_39
[11] Di Crescenzo, G.D., Ge, R., Arce, G.R.: Design and analysis of DBMAC, an error localizing message authentication code. In: GLOBECOM 2004, pp. 2224-2228. IEEE (2004). doi:10.1109/GLOCOM.2004.1378404
[12] Di Crescenzo, G.; Jiang, S.; Safavi-Naini, R.; Backes, M.; Ning, P., Corruption-localizing hashing, Computer Security - ESORICS 2009, 489-504, 2009, Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-642-04444-1_30
[13] Di Crescenzo, G.D., Vakil, F.: Cryptographic hashing for virus localization. In: Jahanian, F. (ed.) WORM 2006. pp. 41-48. ACM Press (2006). doi:10.1145/1179542.1179550
[14] Dorfman, R., The detection of defective members of large populations, Ann. Math. Stat., 14, 4, 436-440, 1943 · doi:10.1214/aoms/1177731363
[15] Du, D.; Hwang, F., Combinatorial Group Testing and Its Applications: Series on Applied Mathematics, 2000, Singapore: World Scientific, Singapore · Zbl 0952.90001
[16] Eppstein, D.; Goodrich, MT; Hirschberg, DS, Improved combinatorial group testing algorithms for real-world problem sizes, SIAM J. Comput., 36, 5, 1360-1375, 2007 · Zbl 1124.68043 · doi:10.1137/050631847
[17] Fang, J., Jiang, L.Z., Yiu, S., Hui, L.C.: Hard disk integrity check by hashing with combinatorial group testing. In: CSA 2009, pp. 1-6 (2009). doi:10.1109/CSA.2009.5404206
[18] Ferguson, N., Lucks, S., Schneier, B., Whiting, D., Bellare, M., Kohno, T., Callas, J., Walker, J.: Skein hash function. SHA-3 Submission (2008). http://www.skein-hash.info/
[19] Goldreich, O., Modern Cryptography, Probabilistic Proofs and Pseudorandomness, 1998, Heidelberg: Springer, Heidelberg
[20] Goodrich, MT; Atallah, MJ; Tamassia, R.; Ioannidis, J.; Keromytis, AD; Yung, M., Indexing information for data forensics, Applied Cryptography and Network Security, 206-221, 2005, Heidelberg: Springer, Heidelberg · Zbl 1126.68395 · doi:10.1007/11496137_15
[21] Iwata, T.; Kurosawa, K.; Johansson, T., OMAC: one-key CBC MAC, Fast Software Encryption, 129-153, 2003, Heidelberg: Springer, Heidelberg · Zbl 1254.94033 · doi:10.1007/978-3-540-39887-5_11
[22] Jean, J.; Nikolic, I.; Peyrin, T.; Sarkar, P.; Iwata, T., Tweaks and keys for block ciphers: the TWEAKEY framework, Advances in Cryptology-ASIACRYPT 2014, 274-288, 2014, Heidelberg: Springer, Heidelberg · Zbl 1317.94113
[23] Liskov, M.; Rivest, RL; Wagner, D.; Yung, M., Tweakable block ciphers, Advances in Cryptology - CRYPTO 2002, 31-46, 2002, Heidelberg: Springer, Heidelberg · Zbl 1026.94533 · doi:10.1007/3-540-45708-9_3
[24] Ngo, H.Q., Du, D.Z.: A Survey on combinatorial group testing algorithms with applications to DNA library screening. DIMACS Series in Discrete Mathematics and Theoretical Computer Science (2000)
[25] Ngo, HQ; Porat, E.; Rudra, A.; Aceto, L.; Henzinger, M.; Sgall, J., Efficiently decodable error-correcting list disjunct matrices and applications (Extended Abstract), Automata, Languages and Programming, 557-568, 2011, Heidelberg: Springer, Heidelberg · Zbl 1334.68298 · doi:10.1007/978-3-642-22006-7_47
[26] Rogaway, P.; Lee, PJ, Efficient instantiations of tweakable blockciphers and refinements to modes OCB and PMAC, Advances in Cryptology - ASIACRYPT 2004, 16-31, 2004, Heidelberg: Springer, Heidelberg · Zbl 1094.94035 · doi:10.1007/978-3-540-30539-2_2
[27] Thierry-Mieg, N.: A new pooling strategy for high-throughput screening: the shifted transversal design. BMC Bioinform. 7, 28 (2006). http://www.biomedcentral.com/content/pdf/1471-2105-7-28.pdf
[28] Thierry-Mieg, N.; Bailly, G., Interpool: interpreting smart-pooling results, Bioinformatics, 24, 5, 696-703, 2008 · doi:10.1093/bioinformatics/btn001
[29] Wagner, D.; Yung, M., A generalized birthday problem, Advances in Cryptology - CRYPTO 2002, 288-304, 2002, Heidelberg: Springer, Heidelberg · Zbl 1026.94541 · doi:10.1007/3-540-45708-9_19
[30] Zaverucha, GM; Stinson, DR; Kurosawa, K., Group testing and batch verification, Information Theoretic Security, 140-157, 2010, Heidelberg: Springer, Heidelberg · Zbl 1282.94073 · doi:10.1007/978-3-642-14496-7_12
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.