Протокол соим(Zi)

Код для процессора P_iна динамическом входеZ_i.

Выполнить для 0rt.

1. Пусть U_i={P_j(_j,z_i,j)Z_i}. Установить (t,r,n,U_i)СОБМ=G.

2. Как толькоGвычислено, вычислять синдромS_G.

2.1. Пусть V- матрица индексов Вандермонда изG. А именно пустьG=k₁...k_G, тогдаV_i,j=(k_j)ⁱ.

2.2. Пусть.

2.3. Для 2t+1<jGустановить ([^V^-1]_j,[n])АВсПр=_j.

2.4. Пусть , где- синдромS_G.

3. Инициализировать алгоритм Берлекампа-Месси для и пусть- выход.

3.1. Если имеет более чемrненулевых элементов, продолжить следующую итерацию (в этом случаеS_G, не является (2t,r)-интерполируемым).

3.2. Если имеет не более чемrненулевых элементов, проверить, чтокорректен.

3.2.1. Пусть G- множество процессоров изG, чьи соответствующие записи вявляются нулевыми. Повторить шаг 2 в отношенииG.

3.2.2. Если синдром S_Gявляется нулевым вектором, выдатьGи остановиться. В противном случае перейти к следующей итерации (S_Gне является (2t,r)-интерполируемым).

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

Протокол ByMul

Код для процессора P_i, на входахa_iиb_i.

1. Рандомизация.

1. Для 1ktвыполнитьАРзПр_i,kпо входуr_k, гдеr_k_RFиP_i- дилер.

2. Для 1jnи для 1ktучаствуют в субпротоколахАРзПр_j,k.

3. Пусть h_i,j,k– выход процессораP_iдля субпротоколаАРзПр_j,k.

4. Пусть U_i={P_jАРзПр_j,kзавершен для всех 1kn}.

5. Установить (n,t,U_i)СОАМ=G.

6. Установить иd_i=a_i^b_i+h_i.

2. Редукция степени.

2.1. Как только d_iвычислено, выполнитьАРзПр_i(d_i), гдеP_i- дилер. Для 1jnучаствовать в субпротоколеАРзПр_j.

2.2. Пусть z_i,j– доля (процессораP_i) общего сP_jсекрета и пустьZ_i={(j,z_i,j)АРзПр_jбыл завершен}. Установить (Z_i)СОИМ=G.

2.3. Пусть - матрица, используемая на шаге умножения дляFS-сбоев и пусть, гдеj₁...j_G- индексы процессоров из G. Для 1jnустановить ([]_j,{j})АРзПр=c_j.

2.4. Как только c_iвычислен, выдатьc_i.

Полная структура протокола для By-сбоев точно такая же, как дляFS-сбоев. А именно, в таком протоколе, обозначаемомByВыч, процессоры выполняют аналогичные инструкции протокола дляFS-сбоев, за исключением того, что протоколыАГРз,MUL, иАГВсзаменены на протоколыАГПРС,ByMULиАВсПрсоответственно.

Теорема 3.9.Пустьf:FⁿFдля некоторой областиFсF>nи пустьА- схема, вычисляющаяf. Тогда протоколByВыч по входуAасинхронно (n/4-1)-безопасно вычисляетfв установке с ограниченно защищенными каналами и в присутствии адаптивных противников.

Доказательство.Приведено в работе [Сa2].

8. RL-прототип модели синхронных конфиденциальных вычислений

Зададимся вопросом «Существует ли реальный вычислительный аналог представленной модели синхронных конфиденциальных вычислений ?». Такой вопрос важен и с прикладной, и с содержательной точки зрения.

Рассмотрим многопроцессорную суперЭВМ семейства S-1на базе сверхбыстродействующих процессоровMARK IIA(MARK V). Такую вычислительную систему назовемRL-прототипом (real-life) модели синхронных конфиденциальных вычислений в реальном сценарии.

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

В указанной многопроцессорной системе используются специально разработанные однопроцессорные машины, образующие семейство, то есть имеющие однотипную архитектуру. В систему может входить до 16 однопроцессорных ЭВМ, сравнимых по производительности с наиболее мощными из существующих суперЭВМ. В дополнение к обычному универсальному оборудованию процессоры семейства S-1оснащены специализированными устройствами, позволяющими выполнять высокоскоростные вычисления в тех прикладных областях, где планируется использование данной многопроцессорной системы. К таким операциям относятся вычисления функций синуса, косинуса, возведения в степень, логарифмирования, операции быстрого преобразования Фурье и фильтрации, операции умножения над матрицами и транспонирования.

Системы семейства S-1предоставляют в распоряжение пользователя большую сегментированную память с виртуальной адресацией в несколько миллиардов 9-разрядных байтов. Процессоры соединены между собой с помощью матричного переключателя, который обеспечивает прямую связь каждого процессора с каждым блоком памяти (см. рис.3.1). При обращениях к той или иной ячейке памяти процессоры всегда получают последнее записанное в ней значение. Команды выполняются в последовательности: «чтение - операция – запись». С целью повышения быстродействия памяти в составе каждого процессора имеются две кэш-памяти: первая – объемом 64 Кбайт для хранения данных, вторая – объемом 16 Кбайт (с перспективой наращивания). В обоих типах кэш-памяти длина набора составляет 4, а длина строки 64 байта.

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

www.kiev-security.org.ua

BEST rus DOC FOR FULL SECURITY

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

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

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

Рис. 3.1. RL-прототип модели синхронных конфиденциальных вычислений

синхронизации. Параметром безопасности системы может являться длина строки (64-256 Кбайт).

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

1. Протоколы византийского соглашения.

2. Протоколы разделения секрета.

3. Протоколы электронного голосования.

4. Протоколы выработки общей случайной строкии многие другие.

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

www.kiev-security.org.ua

BEST rus DOC FOR FULL SECURITY

146

101