Безумовно стійкі схеми розподілу ключів в інформаційних та телекомунікаційних системах з великою кількістю абонентів: I. Схеми попереднього розподілу й узгодження ключів PDF

Автори:С.М. Конюшок, А.М. Олексійчук

С.М. Конюшок, А.М. Олексійчук

Проблеми створення криптографічно стійких та ефективних протоколів розподілу ключів криптосистем, що використовуються для захисту інформації в спеціальних телекомунікаційних системах (СТКС), займають центральне місце в сучасній криптографії. Незважаючи на відчутний прогрес, що досягнутий в цьому напрямі за останнє десятиріччя, більшисть актуальних наукових задач залишаються невирішеними, стимулюючи продовження активних досліджень у різних галузях науки й техніки, що пов’язані з розробкою, застосуванням та аналізом криптографічних протоколів розподілу ключів.

Стримкий розвиток засобів зв’язку та телекомунікацій, ускладнення топології інформаційних і обчислювальних мереж, поява нових інформаційних технологій, поряд з розширенням сфери застосування та підвищенням можливостей засобів криптографічного захисту інформації, призводять до перегляду традиційних концепцій і методології вирішення задач захисту інформації в СТКС, розробки нових наукових та технологічних рішень як у самої криптографії, так і в її застосуваннях.

Одним з таких перспективних застосувань, що активно розвиваються протягом останнього часу, є системи захищеного багатоадресного зв’язку, абоненти яких здійснюють сумісне виконання певних завдань шляхом інтерактивної взаємодії. Даними завданнями можуть бути звичайний обмін інформацієй між змінною за своїм складом групою користувачив, сеанс конференс-зв’язку (наприклад, інтерактивне обговорення порядку денного майбутнього засідання), відеоконференція з участю формальних представників різних країн або сумісне виконання групою користувачив розподіленої обчислювальної мережі алгоритму розв’язання деякої складної задачі [1 – 6]. За виконанням будь-якого з перерахованих завдань для забезпечення надійного криптографічного захисту інформації, що циркулює в системі багатоадресного зв’язку, необхідно враховувати специфічні особливості даної системи, які пов’язані з наявністю в ній великої кількості авторизованих користувачів, що утворюють наділені різними правами групи, склад яких може динамічно змінюватись протягом часу [7, 8].

Серед різноманітних криптографічних протоколів, які використовуються для розподілу секретних ключів, наибільш перпективними для застосування в системах захищеного багатоадресного зв’язку вважаються безумовно стійкі схеми розподілу ключів (БССРК) [1, 9 – 12].

Неформально схема розподілу ключів (СРК) являє собою метод, з використанням якого довірена сторона, що виконує функції центру розподілу ключів (ЦРК), здійснює передачу деякої допоміжної інформації абонентам спеціальної телекомунікаційної системи таким чином, що згодом абоненти, які належать кожній заздалегідь визначеній групі, здатні відновити за цією (та, можливо, певною іншою) інформацією спільний секретний ключ. Схема розподілу ключів, криптографічна стійкість якої не залежить від обчислювальних можливостей противника, називається безумовно стійкою [1, 10, 13].

На сьогодні задачі розробки методів синтезу, аналізу математичних моделей та дослідження властивостей різноманітних класів безумовно стійких схем розподілу ключів складають один із перспективних напрямів сучасної криптографії та включають у себе широке коло окремих задач, які характеризуються різною прикладною спрямованістю. Спектр можливих застосувань БССРК є надзвичайно широким, починаючи від систем платного телемовлення, захисту від несанкціонованого копіювання та безпечного розподілу відкритими мережами зв’язку аудіо- й відеопродукції, і закінчуючи криптографічним захистом інформації в системах багатоадресного зв’язку та розподілених сенсорних мережах (див. нижче пункти 1 – 3). Свідченням про зростаючий інтерес до цього напряму з боку зарубіжних фахівців-криптографів є велика кількість публікацій та доповідей на міжнародних наукових конференціях, що присвячені як теоретичним аспектам безумовно стійких схем розподілу ключів, так і їх численним застосуванням (див. перелік джерел, що приведено нижче). Нажаль, слід констатувати, що для вітчизняної криптографічної науки згаданий напрям залишається на сьогодні terra incognita, про що свідчить практично повна відсутність наукових публікацій за даною тематикою українською або російською мовами.

Автори даної статті здійснили спробу надати перше систематичне викладення українською основ та нещодавніх досягнень теорії БССРК. (Відмітимо, що остання велика оглядова праця за цією темою, написана англійською [10], опублікована в 1997 році).

Стаття складається з двох частин. У першій частині приведена загальна класифікація існуючих протоколів розподілу ключів та викладені результати аналізу сучасного стану, проблематики і напрямів досліджень у галузі побудови безумовно стійких схем попереднього розподілу й узгодження ключів в інформаційних та телекомунікаційних системах з великою кількістю абонентів. Друга частина статті присвячена детальному викладенню перспективних методів синтезу безумовно стійких схем багатоадресного розподілу ключів (СБРК).  

Слід відзначити, що при роботі над оглядом головна увага приділялась конструктивним методам побудови та аналізу ефективності безумовно стійких схем розподілу ключів, які основуються на різних комбінаторних конфігураціях. Зокрема, за межами викладення залишились методи синтезу БССРК на основі орієнтованих графів [8], стислий огляд яких подано в нещодавній роботі [14], та аналітичні нижні границі інформаційних показників ефективності БССРК (див. [1]). Лише мимохідь згадані обчислювально стійкі схеми розподілу ключів (ОССРК) [14, 15], аналіз відомих методів побудови яких заслуговує окремого огляду.

Автори сподіваються, що з’явлення цієї роботи допоможе вітчизняним фахівцям глибше ознайомитись із безумовно стійкими схемами розподілу ключів, які складають важливий та перспективний об’єкт досліджень у сучасній криптографії.

References

1.Cimato S., D’Arco P., Cresti A. A unified model for unconditional secure key distribution // http://www.dia.unisa.it/paodar.dir.

2.Canetti R., Garay J., Itkis G., Micciancio D., Naor M., Pinkas B. Issue in multicast security: a taxonomy and efficient constructions // INFOCOM’99. – 1999. – P. 708 – 716.

3. Canetti R., Malkin T., Nissim K. Effcient communication-storage tradeoffs for multicast encryption // Advances in Cryptology – EUROCRYPT’99, Lecture Notes in Computer Science. – 1999. – P. 459 – 474.

4. Poovendran R., Baras J.S. An information theoretic analysis of rooted-tree based secure multicast key distribution schemes // Advances in Cryptology – CRYPTO’99. – 1999. – P. 624 – 638.

5. Safavi-Naini R., Wang H. New constructions for multicast re-keying schemes using perfect hash families // 7th ACM Conf. on Computer and Communication Security, ACM Press. – 2000. –  P. 228 – 234.

6. Wallner D.M., Harder E.J., Agee R.C. Key management for multicast: issues and architectures // ftp://ftp.ieft.org/internet-drafts/draft-wallner-key-arch-01.txt.

7. Mittra S. Iolus: a framework for scalable secure multicasting // ACM SIGCOMM’97, 1997.

8. Wong С.K, Gauda M., Lam S.S. Secure group communications using key graphs // ACM SIGCOMM’98, 1998.

9. Fiat A., Naor M. Broadcast encryption // Advances in Cryptology – EUROCRYPT’93, Lecture Notes in Computer Science. – 1994. – P. 480 – 491.

10. Stinson D.R. On some methods for unconditionally secure key distribution and broadcast encryption // Designs, Codes and Cryptography. – 1997. – Vol. 12. – P. 215 – 243.

11. Blundo C., D'Arco P., Daza V., Padro C. Bounds and constructions for unconditionally secure distributed key distribution schemes for general access structures // ISC’01, Lecture Notes in Computer Science, Springer-Verlag. – 2001. – P. 1 – 17.

12. Luby M., Staddon J. Combinatorial bounds for broadcast encryption // Advances in Cryptology – EUROCRYPT’98, Lecture Notes in Computer Science. – 1998. – P. 512 – 527.

13. Padro C., Gracio I., Martin S., Morillo P. Linear broadcast encryption schemes // Discrete Appl. Math. – 2003. – Vol. 128. – P. 223 – 238.

14. Attrapadung N., Kobara K., Imai H. Sequential key derivation patterns for broadcast encryption and key predistribution schemes // ASIACRYPT’03, Lecture Notes in Computer Science. – 2003. – P. 374 – 391.

15. Naor D., Naor M., Lotspiech J. Revocation and tracing schemes for stateless receivers // Advances in Cryptology – CRYPTO’01, Lecture Notes in Computer Science. – 2001. – P. 41 – 62.

16. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии. – М.: Гелиос АРВ, 2001. – 480 с.

17. Погорелов БА., Черемушкин А.В., Чечета С.И. Об определении основных криптографических понятий // Математика и безопасность информационных технологий. Материалы конференции в МГУ 23 – 24 октября 2003 г. – М.: МЦНМО, 2003. – С. 75 – 85.

18. Фомичев В.М. Дискретная математика и криптология. Курс лекций. – М.: Диалог-МИФИ, 2003. – 400 с.

19. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. – М.: Триумф, 2002. – 816 с.

20. Diffie W., Hellman M.E. New directions in cryptography // IEEE Trans. оn Inform. Theory. – 1976. – Vol. 22, № 6. – P. 644 – 654.

21. Maurer U. Information-theoretic cryptography // Advances in Cryptology – CRYPTO’99, Lecture Notes in Computer Science. – 1999. – P. 47 – 64.

22. Cachin C. Entropy measures and unconditional security in cryptography: Diss. … doc. Tech. Sciences. – Zurich, 1997. – 155 p.

23. Wolf S. Information-theoretically and unconditionally secure key agreement in cryptography: Ph. D. Thesis № 13138. – ETH Zurich, 1999.

24. Dziembowski S., Maurer U. Optimal randomized efficiency in the bounded-storage model // J. of Cryptology. – 2004. – Vol. 17, № 1. – P. 5 – 26.

25. Bennett C.H., Brassard G., Ekert A.K. Quantum cryptography // Scientific American. – 1992. – P. 50 – 57.

26. Brassard G. Recent developments in quantum cryptography // PRAGOCRYPT’96. – Prague. – 1996.

27. Needham R.M., Shroeder M.D. Using encryption for authentication in large networks of computers // Communications of ACM. – 1978. – Vol. 21, № 12. – P. 993 – 999.

28. Чмора А.Л. Современная прикладная криптография. – М.: Гелиос АРВ, 2002. – 256 с.

29. Bennett C.H., Brassard G. Quantum cryptography and its application to provably secure key expansion, public-key distribution, and coin-tossing // IEEE International Symposium on Inform. Theory. – 1983. – P. 91.

30. Bennett C.H., Brassard G. Quantum cryptography: Public-key distribution and coin tossing // Proc. of IEEE International Conf. on Computers, Systems and Signal Processing. – Bangalore (India), 1984. – P. 175 – 179.

31. Bennett C.H., Brassard G. Quantum public key distribution reinvented // Sigact News. – 1987. – Vol.18, № 4. – P. 51 – 53.

32. Bennett C.H., Bessette F., Brassard G., Salvail L., Smolin J. Experimental quantum cryptography // J.of Cryptology. – 1992. – Vol. 5, № 1. – P. 3 – 28.

33. Wyner A.D. The wire-tap channel // Bell Syst. Techn. J. – 1975. – Vol. 54, № 8. – P. 1335 – 1368.

34. Csiszar I., Korner J. Broadcast channels with confidential messages // IEEE Trans. on Inform. Theory. – 1978. – Vol. 24, № 3. – P. 339 – 348.

35. Горицкий В.М. Вероятностная криптография в системах защиты информации: кодовая защита // Электроника и связь. – 1998. – Вып. 5. – С. 140 – 145.

36. Maurer U. Secret key agreement by public discussion from common information // IEEE Trans. on Inform. Theory. – 1993. – Vol. 39. – № 3. – P. 733 – 742.

37. Ahlswede R., Csiszar I. Common randomness in information theory and cryptography. – Patr. 1: Secret scharing // IEEE Trans. on Inform. Theory. – 1993. – Vol. 39, № 4. – P. 1121 – 1132.

38. Bennett C.M., Brassard G., Crepeau C., Maurer U. Generalized privacy amplification // IEEE Trans. on Inform. Theory. – 1995. – Vol. 41, № 26. – P. 1915 – 1923.

39. Maurer U., Wolf S. Towards characterizing when information-theoretic key agreement is possible // ASIACRYPT’96, Lecture Notes in Computer Science. – 1996. – P. 196 – 209.

40. Чисар И. Почти независимость случайных величин и пропускная способность криптостойкого канала // Проблемы передачи информации. – 1996. – Т. 32, Вып. 1. – С. 48 – 57.

41. Maurer U. Information-theoretically secure secret-key agreement by not authenticated public discussion // Advances in Cryptology. – EUROCRYPT’97, Lecture Notes in Computer Science. – 1997. – P.209 – 225.

42. Maurer U., Wolf S. Information-theoretic key agreement: from weak to strong secrecy for free // Advances in Cryptology – EUROCRYPT’00, Lecture Notes in Computer Science. – 2000. – P. 351 – 368.

43. Maurer U., Wolf S. Secret-key agreement over unauthenticated public channels. – Part I – III // IEEE Trans. on Inform. Theory. – 2003. – Vol. 49, № 4. – P. 822 – 851.

44. Maurer U. A provable-secure strongly randomized cipher // Advances in Cryptology – EUROCRYPT’90, Lecture Notes in Computer Science. – 1990. – P. 361 – 373.

45. Cachin С., Maurer U. Unconditional security against memory-bounded adversaries // Advances in cryptology – CRYPTO’97, Lecture Notes in Computer Science. – 1997. – P. 292 – 306.

46. Koenig R., Maurer U., Renner R. Privacy amplification secure against an adversary with selectable knowlege // IEEE International Symp. on Inform. Theory. – 2004. – P. 231.

47. Blom R. An optimal class of symmetric key generation systems // Advances in Cryptology – EUROCRYPT’84, Lecture Notes in Computer Science. – 1994. – P. 335 – 338.

48. Anzai J., Matsuzaki N., Matsumoto T. A quick group key distribution scheme with entity revocation // ASIACRYPT’99, Lecture Notes in Computer Science. – 1999.– P. 333 – 347.

49. Asano T. A revocation Scheme with minimal storage at receivers. // ASIACRYPT’02, Lecture Notes in Computer Science. – 2002. – P. 433 – 450.

50. Dodis Y., Fazio N. Public key broadcast encryption for stateless receivers // ACM Workshop on digital rights management. – 2002.

51. Dodis Y., Fazio N., Kiayias A., Yung M. Fully scalable public-key traitor tracing // PODC’03. – 2003.

52. Naor M., Pincas B. Efficient trace and revoke schemes // FC’00, Lecture Notes in Computer Science. – 2000. – P. 1 – 20.

53. Halevy D., Shamir A. The LSD broadcast encryption scheme // Advances in Cryptology – CRYPTO’02, Lecture Notes in Computer Science. – 2002. – P. 47 – 60.

54. Вербіцький О.В. Вступ до криптології. – Львів: ВНТЛ, 1998. – 247с.

55. Chor B., Fiat A., Naor M., Pinkas B. Traitor tracing // IEEE Trans. on Inform. Theory. – 2000. – Vol.46, №. 3. – P. 893 – 910.

56. Pfitzmann B. Trials of traced traitors // Information Hiding, Lecture Notes in Computer Science. – 1996. – Vol. 1174. – P. 49 – 64.

57. Dwork C., Lotspiech J., Naor M. Digital signets: self-enforcing protection of digital information // 28-th Symposium on the Theory of Computation. – 1996. – P. 489 – 498.

58. Boneh D. Franklin M. An efficient public key traitor scheme // Advances in Cryptology – CRYPTO’99, Lecture Notes in Computer Science. – 1999.  – P. 338 – 353.

59. Stinson D.R., Wei R. Combinatorial properties and constructions of traceability schemes and frameproof codes // SIAM J. on Discrete Mathematics. – 1998. – Vol. 11. – P. 41 – 53.

60. Berkman O., Parnas M., Sgall J. Efficient dynamic traitor tracing // SODA’00. – 2000. – P. 586 – 595.

61. Garay J., Staddon J., Wool A. Long-lived broadcast encryption // Advances in Cryptology – CRYPTO’00, Lecture Notes in Computer Science. – 2000.– P. 333 – 352.

62. Fiat A., Tessa T. Dynamic traitor tracing // J. of Cryptology. – 2001. – Vol. 14. – P. 211 – 223.

63. Safavi-Naini R., Wang Y. Sequential traitor tracing // Lecture Notes in Computer Science. – 2000. – Vol. 1880. – P. 316 – 332.

64. Staddon J.N., Stinson D.R., Wei R. Combinatorial properties of frameproof and traceability codes // IEEE Trans. on Inform. Theory. – 2001. – Vol. 47. – P. 1042 – 1049.

65. Kiayias A., Yung M. Self protecting pirates and black-box traitor tracing // Advances in Cryptology – CRYPTO’01, Lecture Notes in Computer Science. – 2001. – P. 63 – 79.

66. Kiayias A., Yung M. Traitor tracing with constant transmission rate // Advances in Cryptology – EUROCRYPT’02, Lecture Notes in Computer Science. – 2002. – P. 450 – 465.

67. Bennett C.H., Brassard G., Robert J. – M. Privacy amplification by public discussion // SIAM J. on Comput. – 1988. – Vol. 17, № 2. – P. 210 – 229.

68. Kumar R., Rajagopalan S., Sahai A. Coding constructions for blacklisting problems without computational assumptions // Advances in Cryptology – CRYPTO’99, Lecture Notes in Computer Science. – 1999. – P. 609 – 623.

69. Kurnio H., Safani-Naini R., Wang H. A Group key distribution scheme with decentralised user join // SCN’02, Lecture Notes in Computer Science. – 2002.

70. Gafni E., Staddon J., Yin Y.L. Efficient methods for integrating traceability and broadcast encryption // Advances in Cryptology – CRYPTO’99, Lecture Notes in Computer Science. – 1999. – P. 372 – 387.

71. Stinson D.R., Wei R. Key preassigned traceability schemes for broadcast encryption // SAC’98, Lecture Notes in Computer Science. – 1999. – Vol. 1556. – P. 144 – 156.

72. Stinson D.R., Wei R. An application of ramp schemes to broadcast encryption // Information Processing Letters. – 1999. – Vol. 69. – P. 131 – 135.

73. Blundo C., Frota Mattos L.A., Stinson D.R. Trade-offs between communication and storage in unconditionally secure schemes for broadcast encryption and interactive key distribution // Advances in Cryptology – CRYPTO’96, Lecture Notes in Computer Science. – 1996. – P. 387 – 400.

74. Blundo C., de Santis A., Herzberg A., Kutten S., Vaccaro U., Yung M. Perfectly-secure key distribution for dynamic conferences // Advances in cryptology – CRYPTO’92, Lecture Notes in Computer Science. – 1993. – P. 471 – 486.

75. Stinson D.R., van Trung T. Some new results on key distribution patterns and broadcast encryption // Designs, Codes and Cryptography. – 1998. – Vol. 15. – P. 261 – 279.

76. D'Arco P., Stinson R.D. On unconditionally secure robust distributed key distribution centers // ASIACRYPT’02, Lecture Notes in Computer Science. – 2002. – P. 346 – 363.

77. Korjik V., Ivkov M., Merinovich Y., Bang A., van Tilborg H. A broadcast key distribution scheme based on block designs // Lecture Notes in Computer Science. – 1995. – № 1025. – P. 12 – 21.

78. Шеннон К. Теория связи в секретных системах / Работы по теории информациии кибернетике. – М.: ИЛ., 1963. – С. 333 – 402.

79. Padro C., Gracia I., Martin S., Morillo P. Linear key predistribution schemes // Designs, Codes and Cryptography. – 2002. – Vol. 25. – P. 281 – 298.

80. Beimel A. Secure schemes for secret sharing and key distribution: Diss. … doctor of sciences. – Haifa, 1996. – 115 p.

81. Blundo C., Cresti A. Space requirements for broadcast encryption // Advances in Cryptology – EUROCRYPT’94, Lecture Notes in Computer Science. – 1994. – P. 287 – 298.

82. Gracia I., Martin S., Padro C. Improving the trade-off betveen storage and communication in broadcast encryption schemes // http://www.iacr.org/2001/088.

83. Matsumoto T., Imai H. On the key predistribution system: a practical solution to the key distribution problem // Advances in Cryptology – CRYPTO’87, Lecture Notes in Computer Science. – 1987. – P.185–193.

84. Gong L., Wheeler D.J. A Matrix key-distribution scheme // J. of Cryptology. – 1990. – Vol. 2. – P.51– 59.

85. Saez G. Generation of key predistribution schemes using secret sharing schemes // WCC’01. – France. – 2001. – P. 435 – 444.

86. Blundo C., de Santis A., Vaccaro U. Randomness in distribution protocols // Advanced in Cryptology – CRYPTO’92, Lecture Notes in Computer Science. – 1993. – P. 471 – 486.

87. O’Keefe C.M. Applications to information security // Australasian J. combinatorics. – 1993. – № 7. – P. 195 – 212.

88. Quinn K.A.S. Some constructions for key distribution patterns // Designs, Codes and Cryptography. – 1994, № 4. – P. 177 – 191.

89. Kurosawa K., Yoshida T., Desmedt Y., Burmester M. Some bounds and a construction for secure broadcast encryption // ASIACRYPT’98, Lecture Notes in Computer Science. – 1998. – P. 420 – 433.

90. Beimel A., Chor B. Interaction in key distribution schemes // Advances in Cryptology – CRYPTO’93, Lecture Notes in Computer Science. – 1993. – P. 444 – 455.

91. Beimel A., Chor B. Communication in key distribution schemes // IEEE Trans. on Inform. Theory. – 1996. – Vol. 42. – P. 19 – 28.

92. Blundo C., D'Arco P., Giorgio Gaggia A. A -restricted key agreement scheme // The Comp. J. – 1999. – Vol. 42, № 1. – P. 51 – 61. 

Сайт видання:anpre.org.ua/?q=aboutj