Document Open Access Logo

Property-Preserving Hash Functions and Combinatorial Group Testing

Author Kazuhiko Minematsu

PDF
Thumbnail PDF

File

LIPIcs.ITC.2022.2.pdf
  • Filesize: 0.86 MB
  • 14 pages

Document Identifiers

Author Details

Kazuhiko Minematsu
  • NEC, Tokyo, Japan
  • Yokohama National University, Japan

Cite As Get BibTex

Kazuhiko Minematsu. Property-Preserving Hash Functions and Combinatorial Group Testing. In 3rd Conference on Information-Theoretic Cryptography (ITC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 230, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ITC.2022.2

Abstract

Property-preserving hash (PPH) function is a class of hash functions that allows an evaluation of the property of inputs from their hash values. Boyle {et al}. at ITCS 2019 recently introduced it and considered the robustness of PPH against an adversary who accesses the internal randomness of PPH, and proposed two robust PPH constructions for a weak form of Hamming distance predicate. The second construction received attention for its short hash value, although it relies on an ad-hoc security assumption. The first construction, which is entirely hash-based and based on the classical collision-resistance assumption, has been largely overlooked. We study their first construction and discover its close connection to a seemingly different field of hash/MAC-based (adversarial) error detection using the theory of Combinatorial Group Testing (CGT). We show some consequences of this discovery. In particular, we show that some existing proposals in the field of CGT-based error detection can be converted into a PPH for the Hamming distance property, and they immediately improve and generalize Boyle {et al}. ’s hash-based PPH proposal. We also show that the idea of Boyle {et al}. is useful in the context of a variant of CGT problem.

Subject Classification

ACM Subject Classification
  • Security and privacy → Hash functions and message authentication codes
Keywords
  • Hash function
  • Property-Preserving Hash
  • Combinatorial Group Testing
  • Provable Security

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. John Black and Phillip Rogaway. A block-cipher mode of operation for parallelizable message authentication. In Lars R. Knudsen, editor, EUROCRYPT 2002, volume 2332 of LNCS, pages 384-397. Springer, Heidelberg, April / May 2002. URL: https://doi.org/10.1007/3-540-46035-7_25.
  2. Burton H. Bloom. Space/Time Trade-offs in Hash Coding with Allowable Errors. Commun. ACM, 13(7):422-426, 1970. Google Scholar
  3. Annalisa De Bonis and Giovanni Di Crescenzo. Combinatorial Group Testing for Corruption Localizing Hashing. In COCOON, volume 6842 of Lecture Notes in Computer Science, pages 579-591. Springer, 2011. Google Scholar
  4. Elette Boyle, Rio LaVigne, and Vinod Vaikuntanathan. Adversarially robust property-preserving hash functions. In Avrim Blum, editor, ITCS 2019, volume 124, pages 16:1-16:20. LIPIcs, January 2019. URL: https://doi.org/10.4230/LIPIcs.ITCS.2019.16.
  5. Nader H. Bshouty, Vivian E. Bshouty-Hurani, George Haddad, Thomas Hashem, Fadi Khoury, and Omar Sharafy. Adaptive Group Testing Algorithms to Estimate the Number of Defectives. In ALT, volume 83 of Proceedings of Machine Learning Research, pages 93-110. PMLR, 2018. Google Scholar
  6. Nader H. Bshouty, George Haddad, and Catherine A. Haddad-Zaknoon. Bounds for the Number of Tests in Non-adaptive Randomized Algorithms for Group Testing. In SOFSEM, volume 12011 of Lecture Notes in Computer Science, pages 101-112. Springer, 2020. Google Scholar
  7. Nader H. Bshouty and Catherine A. Haddad-Zaknoon. Optimal deterministic group testing algorithms to estimate the number of defectives. Theor. Comput. Sci., 874:46-58, 2021. Google Scholar
  8. Chao L. Chen and William H. Swallow. Using Group Testing to Estimate a Proportion, and to Test the Binomial Model. Biometrics, 46(4):1035-1046, 1990. Google Scholar
  9. Mahdi Cheraghchi and Vasileios Nakos. Combinatorial group testing and sparse recovery schemes with near-optimal decoding time. In 61st FOCS, pages 1203-1213. IEEE Computer Society Press, November 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00115.
  10. Graham Cormode and S. Muthukrishnan. What’s hot and what’s not: tracking most frequent items dynamically. ACM Trans. Database Syst., 30(1):249-278, 2005. Google Scholar
  11. Giovanni Di Crescenzo and Gonzalo R. Arce. Data Forensics Constructions from Cryptographic Hashing and Coding. In IWDW, volume 7128 of Lecture Notes in Computer Science, pages 494-509. Springer, 2011. Google Scholar
  12. Peter Damaschke and Azam Sheikh Muhammad. Competitive Group Testing and Learning Hidden Vertex Covers with Minimum Adaptivity. Discret. Math. Algorithms Appl., 2(3):291-312, 2010. Google Scholar
  13. Peter Damaschke, Azam Sheikh Muhammad, and Gábor Wiener. Strict group testing and the set basis problem. J. Comb. Theory, Ser. A, 126:70-91, 2014. Google Scholar
  14. Giovanni Di Crescenzo, Shaoquan Jiang, and Reihaneh Safavi-Naini. Corruption-localizing hashing. In Michael Backes and Peng Ning, editors, ESORICS 2009, volume 5789 of LNCS, pages 489-504. Springer, Heidelberg, September 2009. URL: https://doi.org/10.1007/978-3-642-04444-1_30.
  15. D. Du and F. Hwang. Combinatorial Group Testing and Its Applications. Applied Mathematics. World Scientific, 2000. Google Scholar
  16. Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, Venkatadheeraj Pichapati, and Ananda Theertha Suresh. Estimating the number of defectives with group testing. In ISIT, pages 1376-1380. IEEE, 2016. Google Scholar
  17. Nils Fleischhacker, Kasper Green Larsen, and Mark Simkin. Property-Preserving Hash Functions from Standard Assumptions. CoRR, abs/2106.06453, 2021. URL: http://arxiv.org/abs/2106.06453.
  18. Nils Fleischhacker and Mark Simkin. Robust property-preserving hash functions for hamming distance and more. In Anne Canteaut and François-Xavier Standaert, editors, EUROCRYPT 2021, Part III, volume 12698 of LNCS, pages 311-337. Springer, Heidelberg, October 2021. URL: https://doi.org/10.1007/978-3-030-77883-5_11.
  19. Michael T. Goodrich, Mikhail J. Atallah, and Roberto Tamassia. Indexing information for data forensics. In John Ioannidis, Angelos Keromytis, and Moti Yung, editors, ACNS 05, volume 3531 of LNCS, pages 206-221. Springer, Heidelberg, June 2005. URL: https://doi.org/10.1007/11496137_15.
  20. Shoichi Hirose and Junji Shikata. Aggregate Message Authentication Code Capable of Non-Adaptive Group-Testing. IEEE Access, 8:216116-216126, 2020. Google Scholar
  21. Edwin S. Hong and Richard E. Ladner. Group testing for image compression. IEEE Trans. Image Process., 11(8):901-911, 2002. Google Scholar
  22. Piotr Indyk and Rajeev Motwani. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. In STOC, pages 604-613. ACM, 1998. Google Scholar
  23. Piotr Indyk, Hung Q. Ngo, and Atri Rudra. Efficiently Decodable Non-adaptive Group Testing. In SODA, pages 1126-1142. SIAM, 2010. Google Scholar
  24. Moses Liskov, Ronald L. Rivest, and David Wagner. Tweakable block ciphers. In Moti Yung, editor, CRYPTO 2002, volume 2442 of LNCS, pages 31-46. Springer, Heidelberg, August 2002. URL: https://doi.org/10.1007/3-540-45708-9_3.
  25. Kazuhiko Minematsu. Efficient message authentication codes with combinatorial group testing. In Günther Pernul, Peter Y. A. Ryan, and Edgar R. Weippl, editors, ESORICS 2015, Part I, volume 9326 of LNCS, pages 185-202. Springer, Heidelberg, September 2015. URL: https://doi.org/10.1007/978-3-319-24174-6_10.
  26. Kazuhiko Minematsu and Norifumi Kamiya. Symmetric-key corruption detection: When XOR-MACs meet combinatorial group testing. In Kazue Sako, Steve Schneider, and Peter Y. A. Ryan, editors, ESORICS 2019, Part I, volume 11735 of LNCS, pages 595-615. Springer, Heidelberg, September 2019. URL: https://doi.org/10.1007/978-3-030-29959-0_29.
  27. Leon Mutesa, Pacifique Ndishimye, Yvan Butera, Jacob Souopgui, Annette Uwineza, Robert Rutayisire, Ella Larissa Ndoricimpaye, Emile Musoni, Nadine Rujeni, Thierry Nyatanyi, Edouard Ntagwabira, Muhammed Semakula, Clarisse Musanabaganwa, Daniel Nyamwasa, Maurice Ndashimye, Eva Ujeneza, Ivan Emile Mwikarago, Claude Mambo Muvunyi, Jean Baptiste Mazarati, Sabin Nsanzimana, Neil Turok, and Wilfred Ndifon. A pooled testing strategy for identifying sars-cov-2 at low prevalence. Nature, 589(7841):276-280, January 2021. URL: https://doi.org/10.1038/s41586-020-2885-5.
  28. Hung Q. Ngo and Ding-Zhu Du. A Survey on Combinatorial Group Testing Algorithms with Applications to DNA Library Screening. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 2000. Google Scholar
  29. Hung Q. Ngo, Ely Porat, and Atri Rudra. Efficiently Decodable Error-Correcting List Disjunct Matrices and Applications - (Extended Abstract). In ICALP (1), volume 6755 of Lecture Notes in Computer Science, pages 557-568. Springer, 2011. Google Scholar
  30. Yoshinori Ogawa, Shingo Sato, Junji Shikata, and Hideki Imai. Aggregate message authentication codes with detecting functionality from biorthogonal codes. In ISIT, pages 868-873. IEEE, 2020. Google Scholar
  31. Rasmus Pagh and Flemming Friche Rodler. Cuckoo hashing. J. Algorithms, 51(2):122-144, 2004. Google Scholar
  32. Ely Porat and Amir Rothschild. Explicit Nonadaptive Combinatorial Group Testing Schemes. IEEE Trans. Inf. Theory, 57(12):7982-7989, 2011. Google Scholar
  33. Phillip Rogaway. Efficient instantiations of tweakable blockciphers and refinements to modes OCB and PMAC. In Pil Joong Lee, editor, ASIACRYPT 2004, volume 3329 of LNCS, pages 16-31. Springer, Heidelberg, December 2004. URL: https://doi.org/10.1007/978-3-540-30539-2_2.
  34. Phillip Rogaway and Thomas Shrimpton. A provable-security treatment of the key-wrap problem. In Serge Vaudenay, editor, EUROCRYPT 2006, volume 4004 of LNCS, pages 373-390. Springer, Heidelberg, May / June 2006. URL: https://doi.org/10.1007/11761679_23.
  35. Mark N. Wegman and Larry Carter. New hash functions and their use in authentication and set equality. Journal of Computer and System Sciences, 22:265-279, 1981. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact