Разработка и исследование надежных методов агрегации данных в сенсорных сетях тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Фомин, Алексей Дмитриевич

• Фомин, Алексей Дмитриевич
• кандидат технических наук
• 2007

Оглавление диссертации кандидат технических наук Фомин, Алексей Дмитриевич

Введение

1 Агрегация данных в сенсорных сетях

1.1 Сенсорные сети.

1.2 Известные подходы к надежной агрегации

1.3 Обеспечение надежности с использованием распределенной верификации

1.4 Анализ предложенного протокола.

Введение диссертации (часть автореферата) на тему «Разработка и исследование надежных методов агрегации данных в сенсорных сетях»

Актуальность темы. Сенсорные сети представляют собой новое семейство беспроводных сетей со своими задачами и особенностями. Они используются для таких задач как мониторинг окружающей среды и среды естественного обитания, контроль производственного процесса, регулирование дорожного движения, охрана объектов и др [37, 12, 6]. Обычно сенсорная сеть состоит из множества сенсоров, которые распределены произвольным образом по изучаемой среде. Каждый сенсор оснащен специальным датчиком, который позволяет совершить необходимые измерения параметров окружающей среды, и передатчиком, для передачи этих данных на базовую станцию. При этом ресурсы сенсора сильно ограничены, прежде всего, небольшой емкостью его батарейки, а значит, передача данных напрямую к базовой станции энергетически невыгодна [20, 41]. Использование агрегации в сенсорной сети позволяет значительно повысить экономичность и живучесть этой сети [49, 22, 43, 29]. В том случае, когда базовой станции требуется определить интегральную характеристику для какого-либо участка сети, один из узлов этого участка назначается агрегатором. Агрегатор собирает с остальных узлов этого участка частные значения определяемой характеристики, вычисляет агрегатную функцию (среднее, минимум, максимум и т.д.) и передает это значение базовой станции. При этом общие затраты на передачу информации существенно ниже, чем при отсутствии агрегатора. Однако при ошибках в работе сенсоров требуются специальные надежные алгоритмы агрегации. Например, в присутствии злоумышленника, способного захватывать узлы и менять их функциональность, захват агрегатора полностью разрушает функцию агрегации, т.к. захваченный агрегатор может отправить на базовую станцию фиктивный отчет. Для решения этой проблемы можно использовать специальные криптографические процедуры, которые позволят базовой станции с большой вероятностью определить некорректный результат агрегации. В таком случае агрегация будет называться надежной. Понятно, что обеспечение надежности требует от агрегатора передачи на базовую станцию каких-то дополнительных данных, объем которых при заданной надежности должен быть минимизирован. В известных протоколах надежной агрегации [42, 25, 54] объем дополнительных данных достаточно высок, что обуславливает дальнейший интерес к разработке протоколов надежной агрегации.

Для обеспечения работы протокола надежной агрегации в сети также должен быть реализован протокол управления ключами. При этом решения, используемые в классических сетях, в силу ограниченности сенсоров и невозможности использования инфраструктуры не могут быть применены для сенсорных сетей. Протоколы, специально разработанные для сенсорных сетей [28, 60, 21, 24], также обладают недостатками, главный из которых - большое количество ключей, хранящихся каждым сенсором.

При разработке надежного метода агрегации данных также необходимо решить задачу фильтрации фиктивных пакетов внутри сети. Это означает, что узлы, задействованные в передаче финального отчета на базовую станцию, должны иметь возможность определить, является ли пакет фиктивным или нет. Наличие такого механизма позволит существенно уменьшить потребление энергии на передачу фиктивных пакетов в сети. Решение задачи фильтрации пакетов может быть основано на схеме распределенной подписи RSA.

Основной целью работы является: разработка и исследование протоколов надежной агрегации данных в сенсорных сетях.

Методы исследования. Для достижения цели в работе используются методы теории кодирования, комбинаторного анализа, алгебры и теории сложности алгоритмов.

Научная новизна диссертационной работы заключается в следующем:

1. Предложен протокол надежной агрегации данных для сенсорных сетей, позволяющий снизить объем передаваемых данных внутри сети и повысить надежность полученного результата.

2. Предложен протокол управления ключами в сенсорных сетях, позволяющий уменьшить количество хранимых ключей.

3. Предложена схема распределенной подписи RSA с независимым поведением участников коалиции при постановке подписи и неинтерактивным протоколом выдачи проекций секретного ключа без участия дилера.

Практическая ценность и реализация результатов. Практическая ценность работы определяется тем, что предложенный метод надежной агрегации способствует как снижению объема передаваемых данных внутри сети, так и повышению надежности получаемых данных.

Публикации. Материалы, отражающие основное содержание и результаты диссертационной работы, опубликованы в 8 печатных работах ([9, 10, 11, 1, 4, 2, 3, 5]).

Основные положения, выносимые на защиту:

1. Протокол надежной агрегации данных в сенсорных сетях, позволяющий снизить объем передаваемых данных внутри сети, и повысить надежность полученного результата.

2. Протокол управления ключами в больших сенсорных сетях, позволяющий уменьшить количество хранимых ключей.

3. Схема распределенной подписи RSA с независимым поведением участников коалиции при постановке подписи и неинтерактивным протоколом выдачи проекций секретного ключа без участия дилера.

Объем и структура работы.

Диссертационная работа состоит из введения, 3 разделов, заключения и списка использованных источников. Работа содержит 122 страницы, в том числе 120 страниц машинописного текста, включая 5 таблиц и 12 рисунков, и 4 рисунка на 2 страницах. В списке используемой литературы 61 наименование.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Фомин, Алексей Дмитриевич

Основные результаты работы можно сформулировать следующим образом:

1. Предложен протокол надежной агрегации данных в сенсорных сетях, позволяющий снизить объем передаваемых данных внутри сети и повысить надежность полученного результата;

2. Предложен протокол управления ключами в больших сенсорных сетях, позволяющий уменьшить количество хранимых ключей;

3. Предложена схема распределенной подписи RSA с независимым поведением участников коалиции при постановке подписи и неинтерактивным протоколом выдачи проекций секретного ключа без участия дилера.

Заключение

В данной работе рассматривалась задача надежной агрегации данных в сенсорных сетях. Была предложена новая схема надежной агрегации данных, основанная на идее распределенной верификации. Предложенный подход способствует и снижению объема передаваемых данных внутри сети, и повышению надежности агрегации.

Протокол защищенной агрегации требует наличия протокола управления ключами в сети. Поэтому кроме непосредственно протокола защищенной агрегации данных был также предложен протокол управления ключами в сенсорных сетях.

Также в работе описан метод фильтрации пакетов, посылаемых на базовую станцию, на основе распределенной подписи RSA. Для реализации данного метода была разработана схема распределенной подписи RSA с независимым поведением участников коалиции при постановке подписи и неинтерактивным протоколом выдачи проекций секретного ключа без участия дилера.

Список литературы диссертационного исследования кандидат технических наук Фомин, Алексей Дмитриевич, 2007 год

1. Фомин А.Д. "Некоторые вопросы управления ключами в сенсорных сетях". Сборник докладов научной сессии аспирантов ГУАП 2004, Санкт-Петербург.

2. А.А. Плясов, А.Д. Фомин. "Надежная агрегация данных в сенсорных сетях". Сборник докладов научной сессии аспирантов ГУАП 2007, Санкт-Петербург.

3. Е.А. Крук, А.Д. Фомин. "Распределенная верификация результата агрегации данных в сенсорных сетях". Программные продукты и системы, №2, 2007.

4. Фомин А.Д. "Управление ключами в ad-hoc сетях". Сборник докладов научной сессии аспирантов ГУАП 2003, Санкт-Петербург.

5. А.Д. Фомин. "Распределенная подпись RSA". Программные продукты и системы, №2, 2007.

6. Дэвид Каллер, Ханс Малдер. Сенсорные сети. В МИРЕ НАУКИ, (10), Октябрь 2004.

7. Р. Блейхут. Теория и практика кодов, контролирующих ошибки. Мир, Москва, 1986.

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

9. Фомин А.Д. "Библиотека алгоритмов управления ключами в сенсорных сетях". Фонд алгоритмов и программ, инвентарный номер ВНТИЦ 50200601951, 2006.

10. Фомин А.Д. "Библиотека алгоритмов для реализации распределенной подписи rsa". Фонд алгоритмов и программ, инвентарный номер ВН-ТИЦ 50200601950, 2006.

11. Фомин А.Д. DPS: Эффективная схема управления ключами в больших сенсорных сетях. Вопросы передачи и защиты информации: Сборник статей / СПбГУАП. СПб., 2006.

12. Алекс Карабуто. Сенсорные сети: как скоро? 25 августа 2004 года.

13. I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci. A survey on sensor networks. August 2002.

14. B. Blakley and G. R. Blakley. Security of number-theoretic public key cryptosystems against random attack. I. Cryptologia, 2(4) :305—321, 1978.

15. G. R. Blakley. Safeguarding cryptographic keys. In Proc. AFIPS 1979 National Computer Conference, pages 313-317. AFIPS, 1979.

16. G. R. Blakley and I. Borosh. Rivest-Shamir-Adleman public key cryptosystems do not always conceal messages. Computers and Mathematics with Applications, 5:169-178, 1979.

17. C. Blundo, A. D. Santis, A. Herzberg, S. Kutten, U. Yaccaro, and M. Yung. Perfectly-secure key distribution for dynamic conferences. In E. F. Brickell,editor, CRYPTO, volume 740 of Lecture Notes in Computer Science, pages 471-486. Springer, 1992.

18. G. Brassard, editor. Advances in Cryptology CRYPTO '89, 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings, volume 435 of Lecture Notes in Computer Science. Springer, 1990.

19. H. Chan, A. Perrig, and D. X. Song. Random key predistribution schemes for sensor networks. In IEEE Symposium on Security and Privacy, pages 197-. IEEE Computer Society, 2003.

20. A. Deshpande, S. Nath, P. B. Gibbons, and S. Seshan. Cache-and-query for wide area sensor databases. SIGMOD 2003, 2003.

21. Y. Desmedt and Y. Frankel. Threshold cryptosystems. In Brassard 19], pages 307-315.

22. W. Du, J. Deng, Y. S. Han, and P. K. Varshney. A pairwise key pre-distribution scheme for wireless sensor networks. In Jajodia et al. 44], pages 42-51.

23. W. Du, J. Deng, Y. S. Han, and P. K. Varshney. A witness-based approach for data fusion assurance in wireless sensor networks. In Proc. of IEEE Global

24. Telecommunications Conference (GLOBECOM '03), volume 3, pages 14351439, San Francisco, CA, USA, December 1-5 2003.

25. M. E. Dyer, Т. I. Fenner, A. M. Frieze, and A. Thomason. On key storage in secure networks. J. Cryptology, 8(4): 189-200, 1995.

26. F. Ergtin, S. Kannan, R. Kumar, R. Rubinfeld, and M. Viswanathan. Spot-checkers. J. Comput. Syst. Sci, 60(3):717-751, 2000.

27. L. Eschenauer and V. D. Gligor. A key-management scheme for distributed sensor networks. In V. Atluri, editor, A CM Conference on Computer and Communications Security, pages 41-47. ACM, 2002.

28. P. Feldman. A practical scheme for non-interactive verifiable secret sharing. In Proc. 28th IEEE Symp. on Foundations of Сотр. Science, pages 427-438, Los Angeles, 1987. IEEE.

29. A. Fiat and M. Naor. Broadcast encryption. In D. R. Stinson, editor, CRYPTO, volume 773 of Lecture Notes in Computer Science, pages 480491. Springer, 1993.

30. Y. Frankel. A practical protocol for large group oriented networks. In EUROCRYPT, pages 56-61, 1989.

31. Y. Frankel and Y. Desmedt. Parallel reliable threshold multisignature. Technical Report TR-92-04-02, Univ. of Wisconsin-Milwaukee, 1992.

32. Y. Frankel, P. Gemmell, P. D. MacKenzie, and M. Yung. Optimal resilience proactive public-key cryptosystems. In FOCS, pages 384-393, 1997.

33. Y. Frankel, P. Gemmell, P. D. MacKenzie, and M. Yung. Proactive rsa. In B. S. K. Jr., editor, CRYPTO, volume 1294 of Lecture Notes in Computer Science, pages 440-454. Springer, 1997.

34. R. Gennaro, S. Jarecki, H. Krawczyk, and T. Rabin. Robust threshold dss signatures. In EUROCRYPT, pages 354-371, 1996.

35. C.-Y. Ghong and S. P.Kumar. Sensor networks: Evolution, opportunities, and challenges. March 2003.

36. L. Gong and D.J. Wheeler. A matrix key-distribution scheme. J. Cryptology, 2(l):51-59, 1990.

37. L. C. Guillou, J.-J. Quisquater, M. Walker, P. Landrock, and C. Shafer. Precautions taken against various potential attacks in iso/iec dis 9796 "digital signature scheme giving message recovery". In EUROCRYPT, pages 465-473, 1990.

38. L. Harn. Group-oriented (t, n) threshold digital signature scheme and digital multisignature. IEE Proceedings Computers and Digital Techniques, 141(5):307-313, 1994.

39. J. Hill, M. Horton, R. Kling, and L. Krishnamurthy. The platforms enabling wireless sensor networks. Communications of the ACM, 47(6):41-46, 2004.

40. L. Hu and D. Evans. Secure aggregation for wireless networks. In SAINT-W '03: Proceedings of the 2003 Symposium on Applications and the Internet Workshops (SAINT'03 Workshops), page 384, Washington, DC, USA, 2003. IEEE Computer Society.

41. С. Intanagonwiwat, D. Estrin, R. Govindan, and J. Heidemann. Impact of network density on data aggregation in wireless sensor networks. Technical Report 01-750, University of Southern California, Nov. 2001.

42. S. Jajodia, V. Atluri, and T. Jaeger, editors. Proceedings of the 10th ACM Conference on Computer and Communications Security, CCS 2003, Washington, DC, USA, October 27-30, 2003. ACM, 2003.

43. S. Jarecki and N. Saxena. Further simplifications in proactive rsa signatures. In J. Kilian, editor, TCC, volume 3378 of Lecture Notes in Computer Science, pages 510-528. Springer, 2005.

44. S. Jarecki, N. Saxena, and J. H. Yi. An attack on the proactive rsa signature scheme in the ursa ad hoc network access control protocol. In S. Setia and V. Swarup, editors, SASN, pages 1-9. ACM, 2004.

45. J. M. Kahn, R. H. Katz, and K. S. J. Pister. Next century challenges: Mobile networking for "smart dust". In International Conference on Mobile Computing and Networking (MOBICOM'), pages 271-278, 1999.

46. H. Luo and S. Lu. Ubiquitous and robust authentication services for ad hoc wireless networks, 2000.

47. S. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong. TAG: a Tiny AGgregation service for ad-hoc sensor networks. SIGOPS Oper. Syst. Rev., 36(SI): 131—146, 2002.

48. R. C. Merkle. Protocols for public key cryptosystems. In IEEE Symposium on Security and Privacy, pages 122-134, 1980.

49. R. C. Merkle. A certified digital signature. In Brassard 19], pages 218-238.

50. Т. P. Pedersen. Non-interactive and information-theoretic secure verifiable secret sharing. In J. Feigenbaum, editor, CRYPTO, volume 576 of Lecture Notes in Computer Science, pages 129-140. Springer, 1991.

51. A. Perrig, R. Szewczyk, J. D. Tygar, V. Wen, and D. E. Culler. Spins: security protocols for sensor networks. Wirel. Netw., 8(5):521-534, 2002.

52. B. Przydatek, D. X. Song, and A. Perrig. Sia: secure information aggregation in sensor networks. In I. F. Akyildiz, D. Estrin, D. E. Culler, and M. B. Srivastava, editors, SenSys, pages 255-265. ACM, 2003.

53. T. Rabin. A simplified approach to threshold and proactive rsa. In H. Krawczyk, editor, CRYPTO, volume 1462 of Lecture Notes in Computer Science, pages 89-104. Springer, 1998.

54. R. L. Rivest, A. Shamir, and L. M. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM, 21 (2): 120-126, 1978.

55. N. Saxena, G. Tsudik, and J. H. Yi. Efficient node admission for short-lived mobile ad hoc networks. In ICNP, pages 269-278. IEEE Computer Society, 2005.

56. A. Shamir. How to share a secret. Communications of the ACM, 22:612-613, Nov. 1979.

57. V. Shoup. Practical threshold signatures. In EUROCRYPT, pages 207-220, 2000.

58. S. Zhu, S. Setia, and S. Jajodia. LEAP: efficient security mechanisms for large-scale distributed sensor networks. In Jajodia et al. 44], pages 62-72.