Practical algorithms and parameters for modification-tolerant signature scheme

• Anthony B. Kamers UFSC
• Paola de Oliveira Abel UFSC
• Thaís B. Idalino UFSC
• Gustavo Zambonin UFSC
• Jean E. Martina UFSC

DOI: https://doi.org/10.5753/sbseg.2024.241677

Resumo

Traditional digital signature schemes are insufficient to identify exactly which part of a signed document had its integrity compromised. In INDOCRYPT ’19, Idalino et al. presented an efficient modification-tolerant signature scheme (MTSS) framework using group testing techniques, enabling the detection and correction of modified parts. However, the authors did not give ideal parameters for real use case scenarios. We implement the framework, discuss the practical consequences of the effort, give several parameter sets, and compare the performance of MTSS against traditional signature schemes. We additionally propose a novel use case of the framework, which allows for the integrity of any part of a signed document to be verified without ownership of the whole message.

Referências

Bernstein, D. J., Duif, N., Lange, T., Schwabe, P., and Yang, B.-Y. (2012). High-speed high-security signatures. Journal of cryptographic engineering, 2(2):77–89.

Bilzhause, A., Pöhls, H. C., and Samelin, K. (2017). Position paper: the past, present, and future of sanitizable and redactable signatures. In Proceedings of the 12th International Conference on Availability, Reliability and Security, pages 1–9.

Bshouty, N. H. (2015). Linear Time Constructions of Some d-Restriction Problems. In Algorithms and Complexity. CIAC 2015. Lecture Notes in Computer Science, volume 9079, pages 74–88.

Cao, Y.-y. and Fu, C. (2008). An efficient implementation of rsa digital signature algorithm. In 2008 International Conference on Intelligent Computation Technology and Automation (ICICTA), volume 2, pages 100–103.

De Bonis, A. and Di Crescenzo, G. (2011a). Combinatorial group testing for corruption localizing hashing. In Computing and Combinatorics: 17th Annual International Conference, COCOON 2011, Dallas, TX, USA, August 14-16, 2011. Proceedings 17, pages 579–591. Springer.

De Bonis, A. and Di Crescenzo, G. (2011b). A group testing approach to improved corruption localizing hashing. Cryptology ePrint Archive.

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, 2004. GLOBECOM’04., volume 4, pages 2224–2228. IEEE.

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):79–89.

Füredi, Z. (1996). On r-Cover-free Families. J. Combin. Theory Ser. A, 73(1):172–173.

Gargano, L., Rescigno, A. A., and Vaccaro, U. (2020). Low-weight superimposed codes and related combinatorial structures: Bounds and applications. Theoret. Comput. Sci., 806:655–672.

Goodrich, M. T., Atallah, M. J., and Tamassia, R. (2005a). Indexing information for data forensics. In Applied Cryptography and Network Security: Third International Conference, ACNS 2005, New York, NY, USA, June 7-10, 2005. Proceedings 3, pages 206–221. Springer.

Goodrich, M. T., Atallah, M. J., and Tamassia, R. (2005b). Indexing information for data forensics. In Applied Cryptography and Network Security: Third International Conference, ACNS 2005, New York, NY, USA, June 7-10, 2005. Proceedings 3, pages 206–221. Springer.

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 Proceedings of the 2008 ACM symposium on Information, computer and communications security, pages 353–362.

Idalino, T. B. and Moura, L. (2024). 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, pages 195–239, Cham. Springer Nature Switzerland.

Idalino, T. B., Moura, L., and Adams, C. (2019). Modification tolerant signature schemes: location and correction. In International Conference on Cryptology in India, pages 23–44. Springer.

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.

Johnson, R., Molnar, D., Song, D., and Wagner, D. (2002). Homomorphic signature schemes. In Cryptographers’ track at the RSA conference, pages 244–262. Springer.

Josefsson, S. and Liusvaara, I. (2017). Edwards-Curve Digital Signature Algorithm (EdDSA). RFC 8032.

Lim, S. and Lee, H.-S. (2011). A short and efficient redactable signature based on rsa. ETRI Journal, 33(4):621–628.

Mlynkova, I., Toman, K., and Pokornỳ, J. (2006). Statistical analysis of real xml data collections. In COMAD, volume 6, pages 20–31.

of Standards, N. I. and Technology (2023). Module-lattice-based digital signature standard. Technical Report Federal Information Processing Standards Publications (FIPS PUBS) 204 (Draft), August 24, 2023, U.S. Department of Commerce, Washington, D.C.

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

Porat, E. and Rothschild, A. (2011). Explicit nonadaptive combinatorial group testing schemes. IEEE Trans. Inf. Theory, 57(12):7982–7989.

Rescigno, A. A. and Vaccaro, U. (2023). Bounds and Algorithms for Generalized Super-imposed Codes Bounds and Algorithms. Inform. Process. Lett., 182.

Ruszinkó, M. (1994). On the upper bound of the size of the r-cover-free families. J. Combin. Theory Ser. A, 66(2):302–310.

Sperner, E. (1928). Ein Satz über Untermengen einer endlichen Menge. Mathematische Zeitschrift, 27:544–548.

Steinfeld, R., Bull, L., and Zheng, Y. (2002). Content extraction signatures. In Information Security and Cryptology—ICISC 2001: 4th International Conference Seoul, Korea, December 6–7, 2001 Proceedings 4, pages 285–304. Springer.

W3C (2008). Canonical xml version.

Wei, R. (2006). On Cover-Free Families. Technical report, Lakehead University. arxiv: [link].