Partial integrity, authenticity and belongingness using modification-tolerant signature schemes

Anthony Bernardo Kamers; Gustavo Zambonin; Thaís Bardini Idalino; Paola de Oliveira Abel; Jean Everson Martina

doi:10.5753/jbcs.2026.5565

Authors

Anthony Bernardo Kamers Federal University of Santa Catarina https://orcid.org/0009-0006-9490-9822
Gustavo Zambonin Federal University of Santa Catarina https://orcid.org/0000-0002-6962-9347
Thaís Bardini Idalino Federal University of Santa Catarina https://orcid.org/0000-0002-8836-1104
Paola de Oliveira Abel Federal University of Santa Catarina https://orcid.org/0009-0009-7480-0565
Jean Everson Martina Federal University of Santa Catarina https://orcid.org/0000-0003-4104-1741

DOI:

https://doi.org/10.5753/jbcs.2026.5565

Keywords:

Digital signatures, Cryptography, modification-tolerant signatures, partial integrity, big data

Abstract

Digital signatures allow us to ensure that the signed digital data is authentic and has not been modified. However, even a single bit modification in the data invalidates the entire signature. In INDOCRYPT '19, Idalino et al. presented an efficient modification-tolerant signature scheme (MTSS) framework using combinatorial group testing techniques, allowing the location and correction of modified parts of the signed data. In this work, we implement their framework and discuss the practical performance of the solution. We also propose various necessary auxiliary algorithms not explored in the initial work, such as the division of data into blocks and the generation of the underlying combinatorial structure needed for the signature generation. Moreover, we propose a novel use case of the framework, which we call the belongingness framework. This scheme allows the verification of the integrity and authenticity of a subset of the signed data without having access to the whole data. This is particularly interesting in big data applications, where access to the whole signed data is prohibitive due to storage limitations.

Downloads

Download data is not yet available.

Author Biographies

Anthony Bernardo Kamers, Federal University of Santa Catarina

I am a Master’s student at Universidade Federal de Santa Catarina with theme about partial integrity of digital signatures. I am also a researcher, software developer, and project manager of the Brazilian Digital
Signature Standard. My research interests cover cryptography, post-quantum cryptography, cryptanalysis,
digital signatures, and cyber security in general.

Gustavo Zambonin, Federal University of Santa Catarina

I am a PhD student at the Computer Security Lab of the Universidade Federal de Santa Catarina, researching novel combinatorial (un)ranking algorithms to generate random objects in quantum-safe cryptosystems.

Thaís Bardini Idalino, Federal University of Santa Catarina

I am a professor of Computer Science at the Federal University of Santa Catarina, Brazil. I was previously a Postdoctoral Fellow in the Department of Mathematics at Simon Fraser University and completed my Ph.D. in Computer Science at the University of Ottawa. I place myself at the intersection of Combinatorics and Cryptography, with a special focus on developing new combinatorial objects with nice applications in cryptography.

Paola de Oliveira Abel, Federal University of Santa Catarina

It is a computer scientist by Universidade Federal de Santa Catarina. Her interest abroads combinatorial structures and cryptography.

Jean Everson Martina, Federal University of Santa Catarina

Jean Everson Martina is a Senior Lecturer at the Federal University of Santa Catarina (UFSC) and holds a Ph.D. in Computer Science from the University of Cambridge. His research focuses on information security, cryptographic protocols, blockchain technology, and digital identity management. He has led and contributed to multiple international initiatives on secure digital document frameworks, electronic signature standards, and trust infrastructures, shaping policies and technologies in these areas. His work combines theoretical rigor with practical impact, addressing critical challenges in secure computing, interoperability, and digital governance.

References

Bellare, M. and Rogaway, P. (2004). Code-based game-playing proofs and the security of triple encryption. Cryptology ePrint Archive, Paper 2004/331. Available at:[link].

Bilzhause, A., Pöhls, H. C., and Samelin, K. (2017). Position Paper: The Past, Present, and Future of Sanitizable and Redactable Signatures. In International Conference on Availability, Reliability and Security (ARES '17), pages 87:1-87:9. DOI: 10.1145/3098954.3104058.

Bshouty, N. H. (2015). Linear Time Constructions of Some d-Restriction Problems. In Paschos, V. T. and Widmayer, P., editors, Algorithms and Complexity (CIAC 2015), volume 9079 of Lecture Notes in Computer Science, pages 74-88. DOI: 10.1007/978-3-319-18173-8_5.

Chen, H., Zhou, H., Yu, J., Wu, K., Liu, F., Zhou, T., and Cai, Z. (2021). Trusted audit with untrusted auditors: A decentralized data integrity crowdauditing approach based on blockchain. International Journal of Intelligent Systems, 36:6213-6239. DOI: 10.1002/int.22548.

Crawl, C. (2024). Common Crawl - Open Repository of Web Crawl Data. Available at:[link].

de Bonis, A. and di Crescenzo, G. (2011a). A Group Testing Approach to Improved Corruption Localizing Hashing. Available at:[link].

de Bonis, A. and di Crescenzo, G. (2011b). Combinatorial Group Testing for Corruption Localizing Hashing. In Fu, B. and Du, D.-Z., editors, Computing and Combinatorics (COCOON 2011), volume 6842 of Lecture Notes in Computer Science, pages 579-591. DOI: 10.1007/978-3-642-22685-4_50.

di Crescenzo, G., Ge, R., and Arce, G. R. (2004). Design and analysis of DBMAC, an error localizing message authentication code. In IEEE Global Telecommunications Conference (GLOBECOM 2004), pages 2224-2228. DOI: 10.1109/GLOCOM.2004.1378404.

Du, D. Z. and Hwang, F. K. (2000). Combinatorial group testing and its applications. World Scientific, 2 edition. Book.

Erdős, P., Frankl, P., and Füredi, Z. (1985). Families of finite sets in which no set is covered by the union of r others. Israel Journal of Mathematics, 51(1-2):79-89. DOI: 10.1007/BF02772959.

Füredi, Z. (1996). On r-cover-free families. Journal of Combinatorial Theory, Series A, 73(1):172-173. DOI: 10.1006/jcta.1996.0012.

Gargano, L., Rescigno, A. A., and Vaccaro, U. (2020). Low-weight superimposed codes and related combinatorial structures: Bounds and applications. Theoretical Computer Science, 806:655-672. DOI: 10.1016/j.tcs.2019.10.032.

Goodrich, M. T., Atallah, M. J., and Tamassia, R. (2005). Indexing Information for Data Forensics. In Ioannidis, J., Keromytis, A., and Yung, M., editors, Applied Cryptography and Network Security (ACNS 2005), number 3531 in Lecture Notes in Computer Science, pages 206-221. DOI: 10.1007/11496137_15.

Goyal, R. and Vaikuntanathan, V. (2022). Locally Verifiable Signature and Key Aggregation. In Dodis, Y. and Shrimpton, T., editors, Advances in Cryptology (CRYPTO 2022), volume 13508 of Lecture Notes in Computer Science, pages 761-791. DOI: 10.1007/978-3-031-15979-4_26.

Haber, S., Hatano, Y., Honda, Y., Horne, W., Miyazaki, K., Sander, T., Tezoku, S., and Yao, D. (2008). Efficient signature schemes supporting redaction, pseudonymization, and data deidentification. In Abe, M. and Gligor, V. D., editors, ACM Symposium on InformAtion, Computer and Communications Security (ASIACCS '08), pages 353-362. DOI: 10.1145/1368310.1368362.

Han, H., Shiwakoti, R. K., Jarvis, R., Mordi, C., and Botchie, D. (2023). Accounting and auditing with blockchain technology and artificial intelligence: A literature review. International Journal of Accounting Information Systems, 48:100598. DOI: 10.1016/j.accing.20222.100598.

Idalino, T. B. and Moura, L. (2022). A Survey of Cover-Free Families: Constructions, Applications, and Generalizations. In Colbourn, C. J. and Dinitz, J. H., editors, New Advances in Designs, Codes and Cryptography (NADCC 2022), volume 86 of Fields Institute Communications, pages 195-239. DOI: 10.1007/978-3-031-48679-1_11.

Idalino, T. B., Moura, L., and Adams, C. (2019). Modification Tolerant Signature Schemes: Location and Correction. In Hao, F., Ruj, S., and Gupta, S. S., editors, Progress in Cryptology (INDOCRYPT 2019), volume 11898 of Lecture Notes in Computer Science, pages 23-44. DOI: 10.1007/978-3-030-35423-7_2.

Idalino, T. B., Moura, L., Custódio, R. F., and Panario, D. (2015). Locating modifications in signed data for partial data integrity. Information Processing Letters, 115(10):731-737. DOI: 10.1016/j.ipl.2015.02.014.

ISO/TC 171/SC 2 (2008). Document management -- Portable document format -- Part 1: PDF 1.7. Standard 32000-1:2008, International Organization for Standardization. Available at:[link].

Johnson, D. (2021). PDF’s popularity online. Available at:[link].

Johnson, R., Molnar, D., Song, D., and Wagner, D. (2002). Homomorphic signature schemes. In Preneel, B., editor, Topics in Cryptology (CT-RSA 2002), number 2288 in Lecture Notes in Computer Science, pages 244-262. DOI: 10.1007/3-540-45760-7_17.

Kamers, A. B., de Oliveira Abel, P., Idalino, T. B., Zambonin, G., and Martina, J. E. (2024). Practical algorithms and parameters for modification-tolerant signature scheme. In Santin, A. and Machado, R., editors, Brazilian Symposium on Information and Computational Systems Security (SBSeg 2024), pages 522-537. DOI: 10.5753/sbseg.2024.241677.

Koreeda, Y. and Manning, C. D. (2021). Capturing Logical Structure of Visually Structured Documents with Multimodal Transition Parser. pages 144-154. DOI: 10.18653/v1/2021.nllp-1.15.

Laurie, B., Messeri, E., and Stradling, R. (2021). Certificate Transparency Version 2.0. (9162). DOI: 10.17487/RFC9162.

Lim, S. and Lee, H.-S. (2011). A Short and Efficient Redactable Signature Based on RSA. ETRI Journal, 33(4):621-628. DOI: 10.4218/etrij.11.0110.0530.

Lu, Z., Xue, Q., Zhang, T., Cai, J., Han, J., He, Y., and Li, Y. (2024). Locally verifiable approximate multi-member quantum threshold aggregation digital signature scheme. Computer Communications, 228:107934:1-107934:13. DOI: 10.1016/j.comcom.2024.107934.

Luo, D. (2024). Modification-Tolerant Signature Schemes using Combinatorial Group Testing: Theory, Algorithms, and Implementation. Master's thesis, University of Ottawa. Available at:[link].

Mlynkova, I., Toman, K., and Pokornỳ, J. (2006). Statistical Analysis of Real XML Data Collections. In Lakshmanan, L. V. S., Roy, P., and Tung, A. K. H., editors, International Conference on Management of Data (COMAD 2006), pages 15-26. Available at:[link].

NIST (2016). Submission Requirements and Evaluation Criteria for the Post-Quantum Cryptography Standardization Process. Technical report, National Institute of Standards and Technology. Available at:[link].

NIST (2023). Module-Lattice-Based Digital Signature Standard. (204). DOI: 10.6028/nist.fips.204.

Porat, E. and Rothschild, A. (2011). Explicit Nonadaptive Combinatorial Group Testing Schemes. IEEE Transactions on Information Theory, 57(12):7982-7989. DOI: 10.1109/TIT.2011.2163296.

Pöhls, H. C. (2018). Increasing the Legal Probative Value of Cryptographically Private Malleable Signatures. PhD thesis, Universität Passau. Available at:[link].

Rescigno, A. A. and Vaccaro, U. (2023). Bounds and algorithms for generalized superimposed codes. Information Processing Letters, 182:106365:1-106365:5. DOI: 10.1016/j.ipl.2023.106365.

Rodríguez, C., Baez, M., Daniel, F., Casati, F., Trabucco, J. C., Canali, L., and Percannella, G. (2016). REST APIs: A Large-Scale Analysis of Compliance with Principles and Best Practices. In Bozzon, A., Cudre-Maroux, P., and Pautasso, C., editors, Web Engineering (ICWE 2016), volume 9671 of Lecture Notes in Computer Science, pages 21-39. DOI: 10.1007/978-3-319-38791-8_2.

Ruszinkó, M. (1994). On the upper bound of the size of the r-cover-free families. Journal of Combinatorial Theory, Series A, 66(2):302-310. DOI: 10.1016/0097-3165(94)90067-1.

Sperner, E. (1928). Ein Satz über Untermengen einer endlichen Menge. Mathematische Zeitschrift, 27:544-548. DOI: 10.1007/BF01171114.

Steinfeld, R., Bull, L., and Zheng, Y. (2001). Content Extraction Signatures. In Kim, K., editor, Information Security and Cryptology (ICISC 2001), number 2288 in Lecture Notes in Computer Science, pages 285-304. DOI: 10.1007/3-540-45861-1_22.

Wang, J., Krumdick, M., Tong, B., Halim, H., Sokolov, M., Barda, V., Vendryes, D., and Tanner, C. (2023). A Graphical Approach to Document Layout Analysis. In Fink, G. A., Jain, R., Kise, K., and Zanibbi, R., editors, Document Analysis and Recognition (ICDAR 2023), volume 14191 of Lecture Notes in Computer Science, pages 53-69. DOI: 10.1007/978-3-031-41734-4_4.

Wei, R. (2006). On Cover-Free Families. DOI: 10.48550/arXiv.2303.17524.

Xiong, E. (2020). Why PDF Technology Is More Relevant Than Ever. Available at:[link].

Yan, H., Hu, H., and Ye, Q. (2023). Partial message verification in fog-based industrial Internet of things. Computers & Security, 135:103530:1-103530:11. DOI: 10.1016/j.cose.2023.103530.