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

07-5

1162

На правах рукописи

Фомин Алексей Дмитриевич

Разработка и исследование надежных методов агрегации данных в сенсорных сетях

Специальность: 05.13.01 «Системный анализ, управление и обработка информации (в технике и технологиях)

Автореферат диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург 2007

Работа выполнена на кафедре безопасности информационных систем Государственного образовательного учреждения высшего профессионального образования «Санкт-Петербургский государственный университет аэрокосмического приборостроения» (ГУАП).

Научный руководитель:

доктор технических наук, профессор Крук Евгений Абрамович

Официальные оппоненты:

доктор технических наук, профессор Яковлев Сергей Алексеевич кандидат технических наук, доцент Мошак Николай Николаевич

Ведущая организация:

Санкт-Петербургский институт информатики и автоматизации РАН

Защита состоится « -» 2007 г. в /V часов на засе-

дании диссертационного совета Д 212.^33.02 при Государственном образовательном учреждении высшего профессионального образования «Санкт-Петербургский государственный университет аэрокосмического приборостроения» но адресу: 190000, г. Санкт-Петербург, ул. Большая Морская,

д.67.

С диссертацией можно ознакомиться в библиотеке ГУАП.

Автореферат разослан «±1>

г.

Ученый секретарь диссертационного совета доктор технических наук, профессор

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы Сенсорные сети представляют собой новое семейство беспроводных сетей со своими задачами и особенностями. Они используются для таких задач как мониторинг окружающей среды и среды естественного обитания, контроль производственных процессов, регулирование дорожного движения, охрана объектов и т.д. Обычно сенсорная сеть состоит из множества сенсоров, которые помещены в контролируемую среду. Каждый сенсор оснащен специальным датчиком, который позволяет совершить необходимые измерения параметров окружающей среды, и передатчиком для передачи этих данных на базовую станцию. При этом ресурсы сенсора сильно ограничены, прежде всего, небольшой емкостью его батарейки, а значит, передача данных напрямую к базовой станции энергетически невыгодна. Использование агрегации в сенсорной сети позволяет значительно повысить экономичность и живучесть этой сети. В том случае, когда базовой станции требуется определить интегральную характеристику для какого-либо участка сети, один из узлов этого участка назначается агрегатором. Агрегатор собирает с остальных узлов этого участка частные значения определяемой характеристики, вычисляет агрегатную функцию (среднее, минимум, максимум и т.д.) и передает это значение базовой станции. При этом общие затраты на передачу информации существенно ниже, чем при отсутствии агрегатора. Однако, при ошибках в работе сенсоров требуются специальные надежные алгоритмы агрегации. Например, в присутствии злоумышленника, способного захватывать узлы и менять их функциональность, захват агрегатора полностью разрушает функцию агрегации, т.к. захваченный агрегатор может отправить на базовую станцию фиктивный отчет. Для решения этой проблемы можно использовать специальные криптографические процедуры, которые позволят базовой станции с большой вероятностью определить некорректный результат агрегации. В таком случае агрегация будет называться надежной. Понятно, что обеспечение надежности требует от агрех'атора передачи на базовую станцию каких-то дополнительных данных, объем которых при заданной надежности должен быть минимизирован. В известных протоколах надежной агрегации объем дополнительных данных достаточно высок, что обуславливает дальнейший интерес к разработке протоколов надежной агрегации.

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

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

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

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

Для достижения доставленной цели в работе решались следующие основные задачи:

• исследование методов надежной агрегации данных в сенсорных сетях;

• разработка нового протокола надежной агрегации;

• исследование и разработка протокола управления ключами в сенсорных сетях;

• исследование и разработка схемы распределенной подписи RSA.

Методы исследования: для решения поставленных задач в работе

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

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

» протокол надежной агрегации данных для сенсорных сетей;

в протокол управления ключами в сенсорных сетях;

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

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

Результаты работы использовались в разработках ООО «Техноком:» и в учебном процессе Санкт-Петербургского государственного политехнического университета,

Апробация результатов работы. Основные положения и результаты диссертации докладывались и обсуждались на VI, VII, X научных сессиях аспирантов ГУАП (г. Санкт-Петербург 2003, 2004, 2007), а также на семинарах кафедры «Безопасности информационных систем» ГУАП и кафедры «Распределенных вычислений и компьютерных сетей» СПбГПУ. Зарегистрированы программные разработки в отраслевом фонде алгоритмов и программ: регистрационный номер Гос. ФАП 50200601950, 2006 г.; регистрационный номер Гос. ФАП 50200601951, 2006 г.

Публикации. По теме диссертации опубликовано 8 печатных работ, в том числе 2 статьи в рецензируемом журнале по перечню ВАК.

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

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

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

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

Структура работы. Диссертационная работа изложена на 122 странице и состоит из введения, 3-х глав с выводами, заключения и списка использованных источников литературы, включающего 59 наименований. Основное содержание работы включает 16 рисунков и 5 таблиц.

Во введении обоснована актуальность темы диссертации, сформулированы цели диссертационной работы и основные задачи, основные положения, выносимые на защиту, кратко изложено содержание работы но разделам.

Первый раздел посвящен методам надежной агрегации данных в сенсорных сетях. В подразделе 1.1 приводится постановка задачи надежной агрегации. В подразделе 1.2 приводится обзор известных протоколов надежной агрегации. Подраздел 1.3 содержит описание разработанного протокола надежной агрегации, анализ которого приводится в подразделе 1.4.

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

Использование агрегации в сенсорной сети позволяет значительно повысить экономичность и живучесть сети. В том случае, когда базовой станции требуется определить интегральную характеристику для какого-либо участка сети, один из узлов этого участка назначается агрегатором. Он собирает с остальных узлов этого участка частные значения определяемой характеристики, вычисляет агрегатную функцию от них (среднее, минимум, максимум и т.д.) и передает это значение базовой станции. При этом общие затраты на передачу информации существенно ниже, чем при отсутствии агрегатора. Если количество сенсоров в сети достаточно велико, сеть обычно разбивается на кластеры и агрегация выполняется в каждом кластере независимо.

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

Защита передаваемой информации от преднамеренных искажений требует использования методов аутентификации передаваемых сообщений. Для этого используются коды проверки подлинности сообщений (МАС-коды).

Это требует наличия протокола управления ключами.

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

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

Другое решение основано на использовании так называемых узлов-свидетелей, которые фактически дублируют действия агрегатора. Если результат агрегации, полученный свидетелями, совпадает' с результатом агрегатора, то они подписывают результат. После этого агрегатор отправляет результат и подписи свидетелей на базовую станцию. Недостатком данного решения является то, что объем передаваемых сенсорами данных линейно возрастает при увеличении числа узлов-свидетелей.

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

Для достижения надежной агрегации предлагается протокол, основанный на распределенной верификации результата агрегации. В протоколе участвуют следующие стороны: базовая станция (bs), агрегатор (а), сенсоры (sj), и t узлов-верификаторов (ц). Агрегатор и верификаторы - это обычные сенсоры, выбираемые базовой станцией внутри кластера случайным образом. Периодически базовая станция переназначает агрегатора и верификаторов.

Протокол состоит из трех этапов: вычисление результата агрегации, проверка полученного результата t узлами-верификаторами и отправка результата агрегации вместе с подписями верификаторов базовой станции.

На первом этапе все сенсоры отправляют свои данные агрегатору:

sj ~> а : {datcij, mac(kss,д, dataj)}, где datcij - данные, измеренные сенсором sj, ksjta ~ общий ключ сенсо-

pa Sj и агрегатора А. Агрегатор собирает все данные, проверяет их подлинность, используя соответствующие МАС-коды, и вычисляет результат агрегации.

На втором этапе производится распределенная проверка результата агрегации, состоящая из двух шагов.

1). Агрегатор предоставляет верификаторам все собранные данные:

а Verifiers : {d, mac(kvua, d),..., mac{kvt¡a, d)}, где D — {datai, —, datan}.

2). Каждый верификатор V¿ (i = 1 ,í) aHajui3HpyeT соответствующее значение кода проверки подлинности в полученном пакете. Если MAC правильный, верификатор случайным образом выбирает к сенсоров и запрашивает у них данные. Каждый сенсор sj, получив запрос от Vi, высылает ответ:

Sj Vi : {dataj,MAC{Ks}¡Vi, datctj)}.

После того как верификатор V¡ проверил подлинность MAC от сенсора sj, он сравнивает соответствующие данные, полученные от агрегатора и от сенсора. Если эти значения различаются, то верификатор высылает базовой станции предупреждающее сообщение. Если во время верификации узел Vi не находит несоответствия данных, то он подписывает результат агрегации ключом, общим с базовой станцией:

vi—* a: {snvi,mac(kvi,a,snvi)}, где snví — m ас {к vuв s, ar) и ar - результат агрегации.

На третьем этапе агрегатор собирает подписи от всех узов-верификаторов, формирует отчет, подписывает его и отправляет на базовую станцию:

А -> BS : {AR, SNVl © ... 0 SNVt © MAC{Ka>Bs, AR)}.

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

Для данного протокола можно определить вероятность принятия базовой станцией искаженного результата агрегации:

где п - количество сенсоров в кластере, t - количество узлов-верификаторов, к - количество запросов от каждого узла-верификатора, m — количество

Таблица 1. Сравнение коммуникационных издержек в различных протоколах надежной агрегации

Тип издержек/Протокол Б1А Свидетели Предложенный

Передача сенсора (байт) 22 42 36

Передача вне кластера (байт) 992 22 22

Общее количество данных передаваемых внутри кластера (байт) 2200 4230 3916

Общее количество данных получаемых внутри клаг-стера (байт) 2200 16830 4432

Максимальная погрешность получаемого результата агрегации (%) 40 5 5

искаженных отчетов в пакете, предоставленном верификаторам для проверки, р - вероятность некорректной работы узла-верификатора.

В таблице 1 показано сравнение коммуникационных издержек для разработанного и известных протоколов. Сравнение производилось для кластера из ста узлов, с вероятностью некорректной работы узла-верификатора 0,1 и с вероятностью принятия базовой станцией искаженного результата агрегации, меньшей или равной 0,05. В пакете, отправляемом сенсором, данные занимают два байта, а код проверки подлинности - десять байт. Сравнение коммуникационных издержек показывает существенное преимущество разработанного протокола в сравнении с известными.

Второй раздел посвящен протоколам управления ключами в сенсор-пых сетях. В подразделе 2.1 рассматриваются особенности сенсорных сетей с точки зрения протокола управления ключами. В подразделе 2.2 приводится обзор известных протоколов управления ключами. Подраздел 2.3 содержит описание предлагаемого протокола управления ключами в сенсорных сетях. Анализ этого протокола приводится в подразделе 2.4.

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

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

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

2), В сети нет надежных узлов, кроме базовой станции, однако, ее ис-

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

3). Нет априорной информации о соседних узлах. Часто развертывание сети производится путем случайного разбрасывания сенсоров (например, с самолета), а, следовательно, знание о будущих соседях до развертывания сети отсутствует. Однако, даже в случае развертывания сети вручную большое количество узлов делает затруднительным определение собственного положения и множества соседей для каждого отдельного узла.

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

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

Существенно более эффективный подход был предложен в протоколе LEAP. Авторы использовали два допущения: ключи не могут быть скомпрометированы в течение первых Ттщ секунд после добавления сенсора в сети и все узлы в сети неподвижны. В рамках данного протокола на все сенсоры предустанавливается один и тот же мастер ключ Kj. При добавлении нового узла и в сеть он вычисляет свой индивидуальный ключ как Ки — f{Ki,idu), где / - односторонняя функция, находит все сенсоры в своем кластере и для каждого сенсора v, принадлежащего кластеру, вычисляет парный ключ как Kuv = f(Kv,u). Узел v также вычисляет ключ Kuv независимо от узла и. По истечении времени Тт'т мастер ключ Ki стирается. Данное решение обладает идеальной стойкостью к компрометации ключей, но при этом количество ключей, хранимых каждым узлом, линейно зависит от количества сенсоров в кластере этого узла. Это делает данное решение неприемлемым для кластеров большого размера.

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

1). Один и тот же ключ может принадлежать более чем двум узлам.

2). Два узла могут иметь более одного общего ключа.

Кроме тох'о, должно выполняться следующее условие: узлы, не являющиеся непосредственными соседями, не должны иметь общих ключей.

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

Каждый узел и использует свое множество ключей Kf, которое состоит из двух подмножеств:

1). Подмножество предустановленных ключей Kf = {Kf}. Это подмножество может быть сгенерировано непосредственно самим узлом или предустановлено перед добавлением узла в сеть.

2). Подмножество собранных ключей Kf = {Kf}. Это подмножество формируется из ключей, присланных соседними узлами.

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

Таким образом, каждый узел и получает некоторое подмножество ключей из множества (J Kf, где Nn ~ соседи узла и. Это множество может

ieWu

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

Таким образом, предлагаемый метод позволяет динамически распределить ключи так, чтобы узлы, расположенные далеко друг от друга, не имели общих ключей. Это свойство и обеспечивает уменьшение количества хранимых ключей до O(log(n)), где п — количество сенсоров в кластере.

В третьем разделе рассматривается задача фильтрации пакетов на основе распределенной подписи. В подразделе 3.1 приводится описание подхода к фильтрации пакетов на базе распределенной подписи и формулируются требования к схеме распределенной подписи. В подразделе 3.2 приводится описание примитивов, используемых для организации распределенной подписи. В подразделе 3.3 приводится обзор известных схем распределенной подписи RSA. В подразделе 3.4 предлагается модификация схемы разделения секрета, предложенной Шамиром, позволяющая обеспечить выполнение всех свойств, требуемых от схемы распределенной подписи. В подразделе 3,5 описана предлагаемая схема распределенной подписи и приведен ее анализ.

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

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

Для сенсорных сетей с более мощными узлами решение данной проблемы может быть основано на использовании распределенной асимметричной подписи. Такая подпись предполагает распределение секретного ключа асимметричного алгоритма цифровой подписи с помощью пороговой схемы разделения секрета между всеми участниками схемы и наличие протокола, позволяющего любой коалиции из заданного числа участников распреде-леино вычислить цифровую подпись для заданного сообщения. Применительно к задаче фильтрации фиктивных пакетов в сенсорных сетях алгоритм распределенной асимметричной подписи может быть использован следующим образом. Дилер выбирает и распределяет между всеми сенсорами секретный ключ выбранного алгоритма цифровой подписи. Кроме того, все сенсоры инициализируются открытым ключом. Отправляя результат агрегации на базовую станцию, его подписывают заданное количество сенсоров с помощью протокола распределенной подписи. При этом каждый сенсор, ретранслирующий данный пакет, используя открытый ключ, в состоянии проверить подпись. Если подпись не прошла проверку, пакет выбрасывается.

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

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

Постановка задачи формулируется следующим образом. Модель сети

предполагает наличие п узлов и злоумышленника. Также предполагается, что существует доверенный дилер, который инициализирует схему: для этого он выбирает секретный шпон RSA и безопасно распределяет этот ключ среди узлов, обеспечивая (4,п)-порошвую схему, после чего его участие не требуется. Будем считать, что злоумышленник может захватить з < t узлов.

Так как атакующий взламывает многократную схему подписи, од может осуществить атаку по выбранному сообщению (chosen-message attack, СМ А), то есть он может запросить кого-нибудь из п участников запустить протокол подписи для любого сообщения, которое выберет. Цель атакующего - либо подделать подпись для сообщения, которое он но просил подписать, либо сорвать подписание чужого сообщения другими участниками.

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

1). Процедура постановки подписи должна обеспечивать независимость действий участников коалиции.

2). Система должна обладать свойством самоорганизации, то есть после инициализации не нуждаться в участии дилера.

3). Процедура выдачи проекции секрета без дилера должна быть неинтерактивна.

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

При первом подходе подразумевается, что секретный ключ d распределяется по схеме разделения секрета Шамира над кольцом Д^л/) (или ZX[N)), где </>(N) (или Л(N)) не опубликованы. Отсутствие информации о фф) (или A(N)) делает невозможной работу системы без участия доверенного дилера.

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

При третьем подходе предполагается разделение секретного ключа d над известным кольцом Zдг вместо и ли zX(n)- Но такое разделение

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

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

Одним из компонентов распределенной схемы подписи является схема разделения секрета. В частности, может быть использована схема Ша-мира. В ней предполагается заданным полином f(x) — /о + fix + ... + mod Р, в котором /0 = S - секрет, /i,—,/t-i - случайные значения, а Р - простое число. Каждый участник протокола получает проекцию секрета в виде s s = f(id), где id - идентификатор участника. Любая коалиция К- из i участников сможет восстановить секрет /о = / (0), используя интерполяцию по Лагранжу: /(0) = J2 ssuîu(0)(moâP), где 1и(х) - коэффициенты Лагранжа.

Чтобы использовать схему Шамира для распределенной подписи RSA, необходимо выбрать секрет S и модуль Р. Для распределенной подписи RSA секретом является секретный ключ d. Относительно модуля Р имеется две возможности: либо сделать его публичным, например Р = N, либо сделать его секретным, положив Р — <f>(N) или Р = A(N). Если Р всем известно (например, модуль RSA N), это приведет к утечке информации и взаимозависимости действий участников коалиции во время выполнения нроцедуры постановки распределенной подписи. Если Р - секретное значение (например, Р = A(N) или Р = $(iV)), это приведет к невозможности самоорганизации системы, что вытекает из следующего утверждения. Утверждение 1 Если используется модуль Р, не известный участником, то обеспечение безопасности при выдаче проекции новому участнику требует наличия доверенного дилера.

Для устранения вышеуказанных недостатков необходимо отказаться от использования модуля Р. Однако, процедура выдачи проекций без дилера остается интерактивной. Кроме того, отказ от Р приводит к росту размера проекций, а следовательно и сложности постановки подписи. Для размера проекции секрета R легко получить верхнюю оценку: R < log{N)+(t—l)k+ 1, где N - модуль RSA, t - размер коалиции, к - длина идентификатора пользователя.

Например, при длине идентификатора участника к = 48 бит и размере коалиции t — 10 размер проекции не будет превосходить log(N) + 48 • (t -1) +1 « 1500 бит, что означает увеличение сложности постановки подписей приблизительно в полтора раза.

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

Вводится в рассмотрение простое число Q > max(idj). Проекции секрета вычисляются по формуле:

t-i t-i

f(x, у) = £ £ fij(x* mod W mod Q).

¿=0 i=0

При таком задании функции разделения секрета нельзя использовать

интерполяцию по Лагранжу. Вместо этого необходимо решать систему линейных уравнений.

Для восстановления секрета каждый участник коалиции и вычисляет значение своей функции в точке х - 0, получая f{0,idu) = /0 + mod Q) + - •■ + ft(yt Q) в точке y = idu. При этом /о = /о,о- Имея t значений данной функции, можно восстановить секрет, решив следующую систему уравнений:

" îM " /0

Дя»2) = G /1

. /¿.ч) . ft-1

где

G ■

(ffiij^modQ (zjj1 mod Q ... (ijj4-1 mod Q (xh)° mod Q (xh)1 mod Q ... mod Q

mod Q (ж»,)1 mod Q ... (a^)4"1 mod Q

Для выдачи проекции новому участнику без дилера каждый участник коалиции и вычисляет значение своей функции в точке х = idnew, получая J{idneW)idu) = sncw(idu) = s0-Mi(2/ mod Q) + .. .-Mi-ife'-1 mod Q) в точке у = idu.

Проекция секрета (so, si,..., St-i) Для нового абонента находится из системы уравнений:

^newip^ii ) so

= G si

Snewfait")

Для предложенной схемы разделения секрета справедливо следующее утверждение.

Утверждение 2 Для модифицированной схемы разделения секрета верно, что:

1. схема является пороговой и безопасной;

процедура выдачи проекции в схеме неинтерактивна и не требует присутствия дилера;

3. процедура выдачи проекции в схеме безопасна;

4. размеры используемой для подписи части проекции в схеме ограничены сверху величиной 1од(М) + к -1-1.

На основе предложенной модифицированной схемы разделения секрета разработана следующая распределенная схема подписи ИБА.

1. Инициализация схемы

(a) Дилер генерирует простое число Q > max(idj).

(b) Дилер генерирует публичный ключ RSA N=pqze>Q - простое число и вычисляет секретный ключ d: ed = 1 mod Ф(Ы).

(c) Дилер генерирует функцию

t-1 t-1

f(*,y) = EZ-M^ mod W mod 9)'

i=0 j-0

где /о,о — d, а коэффициенты fij € Z^ выбраны случайным образом с соблюдением условия =

(d) Каждый узел и в качестве проекции секретного ключа получает функцию

su(я) = f{x,idu).

2. Распределенная постановка подписи

(a) Выбирается коалиция К. из t участников. Каждый участник коалиции вычисляет частичную подпись по формуле

Su{rn) = m4'"(0) mod N,

где m - значение хэш-функции от нодписываемого сообщения и и 6 К.

(b) После получения t частичных подписей сборщик подписи составляет матрицу G для членов коалиции JC и обращает ее над полем рациональных чисел.

(c) Сборщик подшей вычисляет G' = X-G~l, где Л - наименьшее общее кратное знаменателей всех элементов матрицы G~l. После этого он вычисляет:

S'(m) = (п^М)'4) ™dN-

(d) Используя расширенный алгоритм Евклида, сборщик находит такие х, у, что

хХ + уе — 1.

(e) Подпись вычисляется как S(m) ~ ((S'(m))x • mv) mod N.

3. Выдача проекции ключа новому пользователю

(а) Для получения проекции секретного ключа новый узел и должен найти коалицию /С из t уже нроинициализированных узлов и сообщить им свое idnew.

(b) Каждый участник коалиции и вычисляет значение своей функции в точке х - idnaW) получая f(idnBW,idu) = snew(idu) = so + si{y mod Q) + ... + st-i('j/t_i mod Q) в точке у = idu.

(c) Новый узел находит свою проекцию секрета (s0, аь..., St_1) из системы уравнений:

¿>пеги (^¿i) so

&new (З-гу) Si

¿'new^ic) . st-i .

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

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

Утверждение 3 Предложенная распределенная схема подписи столь же безопасна, как и RSA.

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

В заключении сформулированы основные результаты диссертационной работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

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

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

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

4. А.Д. Фомин. Библиотека алгоритмов для реализации распределенной подписи RS А. Фонд алгоритмов и программ, инвентарный номер ВНТЩ 50200601950, 2006.

5. A.A. Плясов, А.Д. Фомин. Надежная агрегация данных в сенсорных сетях. X Научная сессия аспирантов СП6ГУАП: Тез. докл. - СПб, 2007.

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

7. А.Д. Фомин. Некоторые вопросы управления ключами в сенсорных сетях. VII Научная сессия аспирантов СПбГУАП: Тез. докл. - СПб, 2004.

8. А.Д. Фомин. Управление ключами в ad-hoc сетях. VI Научная сессия аспирантов СПбГУАП: Тез. докл. - СПб, 2003.

Формат 60x84 1\1б .Бумага офсетная. Печать офсетная. Тираж 100. экз. Заказ № Ц^О

Реда1щионно-издатсльский центр ГУАП 190000, Санкт-Петербург, Б. Морская ул., 67

2UU/out i« •

2007504101

Введение

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 с независимым поведением участников коалиции при постановке подписи и неинтерактивным протоколом выдачи проекций секретного ключа без участия дилера.

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.