Algorithm for tracking violators in multi-address key distribution schemes
DOI:
https://doi.org/10.20535/2411-1031.2025.13.2.344838Keywords:
cybersecurity, cyber defense, cryptography, traitor tracing, multi-address key distribution schemeAbstract
The article is devoted to the study of randomized multi-address key distribution schemes based on code constructions and their application for implementing traitor tracing schemes. A multi-address key distribution scheme is a cryptographic protocol in which a key distribution center transmits certain auxiliary information (to which only authorized users should have access) to subscribers of a communication network so that, over time, in the event of compromise of the cryptographic keys of some subscribers, whose list the key distribution center has managed to establish, other subscribers will be able to restore the shared cryptographic key, which is transmitted in encrypted form from the key distribution center via a broadcast communication channel. At the same time, subscribers whose keys have been compromised will not be able to decrypt the broadcast message. As can be seen, for such schemes to function successfully, there is a need for approaches and tools to establish a list of compromised subscribers (for different tasks, there may be a need for either a complete list of such subscribers or at least one of them). Classic traitor tracing schemes can be the basis for building such tools because they were created to identify a user or group of unscrupulous users who transferred their keys to create an array of compromised keys that can be used for malicious purposes (the so-called “violators decoder”). However, with the growing number of subscribers, the rapid development of computing resources, the creation of adaptive attacks, and increasing privacy requirements, such schemes are becoming less effective. The approach proposed in the article aims to combine the capabilities of multi-address key distribution schemes and intruder tracking schemes while maintaining a balance between the accuracy of intruder tracking and the efficiency of available computing resources. Thanks to the use of Geffding's estimates, the algorithm constructed in the article is -identifying, i.e., it is capable of guaranteeing the identification of at least one participant in any coalition that does not exceed violators. The sufficient conditions given for the code parameters provide a significant improvement over the classical ones. It is demonstrated that the randomized approach preserves the stability of the system and does not degrade the security properties of the original scheme, but significantly enhances its ability to distinguish users in case of key compromise. The analytical expressions obtained in the article allow obtaining accurate lower bounds on the reliability of the traitor tracing algorithm, which, in turn, can be used in the practical construction of randomized traitor tracing protocols with a given required (high) reliability.
References
B. Chor, A. Fiat, and M. Naor, “Tracing Traitors”, in Advances in Cryptology – CRYPTO ’94: 14th Ann. Int. Crypt. Conf., Y.G. Desmedt, Ed. Berlin, Heidelberg, Germany: Springer, 1994, pp. 257-270, doi: https://doi.org/10.1007/3-540-48658-5_25.
Fiat, and M. Naor, “Broadcast Encryption”, in Advances in Cryptology – CRYPTO ’93: 13th Ann. Int. Crypt. Conf., D.R Stinson, Ed. Berlin, Heidelberg, Germany: Springer, 1994, pp. 480-491, doi: https://doi.org/10.1007/3-540-48285-7_33.
D. Boneh, and M. Franklin, “An Efficient Public Key Traitor Tracing Scheme”, in Advances in Cryptology – CRYPTO ’99: 19th Ann. Int. Crypt. Conf., M. Wiener, Ed. Berlin, Heidelberg, Germany: Springer, 1999, pp. 358-371, doi: https://doi.org/10.1007/3-540-48405-1_22.
K. Kurosawa, and Y. Desmedt, “Optimum Traitor Tracing and Asymmetric Schemes”, in Advances in Cryptology – EUROCRYPT ’98, K. Nyberg, Ed. Berlin, Heidelberg, Germany: Springer, 1998, pp. 145-157, doi: https://doi.org/10.1007/BFb0054123.
G. Tardos, “Optimal Probabilistic Fingerprint Codes”, in Proc. 35th Ann. ACM Symp. on Theory of Comp. (STOC ’03), New York, NY, USA: ACM, 2003, pp. 116-125, doi: https://doi.org/10.1145/779928.779941.
D. Boneh, and J. Shaw, “Collusion-Secure Fingerprinting for Digital Data”, IEEE Transactions on Information Theory, vol. 44, no. 5, pp. 1897-1905, 1998, doi: https://doi.org/10.1109/18.720541.
S. Ling, R.C.-W. Phan, and D. Stehlé, “A Lattice-Based Traitor Tracing Scheme”, IACR Cryptology ePrint Archive, paper 2012/088, 2012. [Online]. Available: https://eprint.iacr.org/2012/088. Accessed on: Nov. 05, 2025.
N. Attrapadung, and H. Imai, “Conjunctive Broadcast and Attribute-Based Encryption”, in Pairing-Based Cryptography – Pairing 2009, H. Shacham and B. Waters, Eds. Berlin, Heidelberg, Germany: Springer, 2009, pp. 248-265. doi: https://doi.org/10.1007/978-3-642-03298-1_1.
P. Ananth, S. Garg, A. Sahai, and A. Srinivasan, “New Techniques for Traitor Tracing: Size and More from Pairings”, IACR Cryptology ePrint Archive, paper 2020/954, 2020. [Online]. Available: https://eprint.iacr.org/2020/954. Accessed on: Nov. 05, 2025.
A. Kiayias, and Q. Tang, “How to keep a secret: leakage deterring public-key cryptosystems”, in Proc. 2013 ACM SIGSAC Conf. on Comp. & Comm. Sec. (CCS '13), Berlin, Germany, pp. 943-954, 2013. doi: https://doi.org/10.1145/2508859.2516691.
A.N. Alekseichuk, and S.N. Konyushok, “Multicast key distribution schemes based on Stinson-Van Trung designs”, Cybernetics and Systems Analysis, vol. 43, no. 3, pp. 397-406, 2007. [Online]. Available: http://link.springer.com/article/10.1007/s10559-007-0062-6. Accessed on: Nov. 05, 2025.
E. Gafni, J. Staddon, and Y.-L. Yin, “Efficient methods for integrating traceability and broadcast encryption”, in Proc., 19th Annual International Cryptology Conference (CRYPTO '99), Santa Barbara, California, USA, 1999, pp. 372-387. doi: https://doi.org/10.1007/3-540-48405-1_24.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Collection "Information Technology and Security"
This work is licensed under a Creative Commons Attribution 4.0 International License.
The authors that are published in this collection, agree to the following terms:
- The authors reserve the right to authorship of their work and pass the collection right of first publication this work is licensed under the Creative Commons Attribution License, which allows others to freely distribute the published work with the obligatory reference to the authors of the original work and the first publication of the work in this collection.
- The authors have the right to conclude an agreement on exclusive distribution of the work in the form in which it was published this anthology (for example, to place the work in a digital repository institution or to publish in the structure of the monograph), provided that references to the first publication of the work in this collection.
- Policy of the journal allows and encourages the placement of authors on the Internet (for example, in storage facilities or on personal web sites) the manuscript of the work, prior to the submission of the manuscript to the editor, and during its editorial processing, as it contributes to productive scientific discussion and positive effect on the efficiency and dynamics of citations of published work (see The Effect of Open Access).
