kiev-security.org.ua-Криптография.Секретные распределенные системы

E.D.Karnin, J.W.Greene, M.E.Hellman. On Secret Sharing Systems. IEEE Transactions on Information Theory, vol. IT-29, N1, 1983. Аннотация. Секретные распределгнные системы (СРС) позволяют распределить секрет между n доверенными лицами таким образом, что k из них могут его восстановить, а для k-1 сохраняется полная неопределгнность. Представлен метод линейного кодирования, сочетающий метод полиномиальной интерполяции, предложенный Шамиром, и вероятностный метод Блейкли, рассматриваемый детерминистически. Получены границы для наибольшего значения n при заданных k и величине секрета для любой системы, линейной или нелинейной. Предложенный метод позволяет достигнуть нижней границы, которая на практике незначительно отличается от верхней. Метод может быть использован для защиты нескольких секретов. Представлен способ защиты от обмана одним из доверенных лиц. 1. ВВЕДЕНИЕ. Криптография чрезвычайно полезна для защиты файлов данных от лиц, которым не известен секретный ключ шифрования. Но что произойдгт, если законный владелец файлов утратит ключ или потеряет трудоспособность? Возникает проблема создания копий ключа для предотвращения таких ситуаций. Копии можно хранить в сейфе в виде перфокарт и т.п., поскольку длина ключей обычно от 50 до 1000 бит. Но даже сейф небезопасен (например, известно насекомое, поедающее перфокарты); следовательно, предпочтительно создавать несколько копий. Для защиты от одновременного разрушения эти копии хранятся в разных сейфах. Пусть v означает информацию, хранимую в i-том сейфе, а s означает секретный ключ. v = v = ... = v = s. Секрет s можно восстановить, если n-1 частей были уничтожены, но он будет скомпрометирован при воровстве хотя бы одной из частей. Существует способ, защищающий от воровства, но уязвимый для "угрозы насекомого". Разделим ключ s на n частей v , v ,. . ., v таким образом, чтобы нельзя было получить информацию об s из любых n-1 частей. Это возможно, если все v - случайные переменные, равномерно распределгнные по S, множеству всех возможных секретных ключей, и пусть v = s + (v + v + ... + v ) (mod q), где q =|S| - мощность множества S. Например, когда q=2, v - это сумма по модулю 2 s со всеми v. Поскольку 1-битный ключ не имеет применения, этот метод применим к последовательности битов ключа. Преимущество метода является его же недостатком: если хотя бы одно из v уничтожено, законный владелец не сможет восстановить ключ из оставшихся частей. С целью защиты от рассмотренных угроз ряд исследователей рассмотрели проблему распределения секрета. Разделим секрет s на n частей v , v ,..., v , каждая из которых выбирается из множества V. При этом выполняются следующие условия: С1) секрет s восстанавливается из любых k частей (k <= n); C2) знание k-1 или меньшего числа частей не дагт информации об s; Если не используется восстановление данных после сжатия, то С3) |V| <= |S|, т.е. каждая часть v не длиннее s. Назовгм такую систему " k-из-n секретная распределгнная система". Предложенный метод можно использовать не только для защиты копий ключа в сейфах, но и для распределения некоторого секрета среди n доверенных лиц так, что любые k из них могут восстановить секрет, а k-1 или меньше не могут. В терминах теории информации эти требования для любого множества k индексов { i , i ,..., i } запишем так: H( s| v , v ,..., v )=0 (1) H( s| v , v ,..., v )=H(s) (2) Теорема 1: для выполнения условий С1) и С2) необходимо, чтобы H(v ) >= H(s), i=1,2,..,n. Примечание: если s равномерно распределено по S, то теорема 1 означает, что |V| >= |S|, и условие С3) можно заменить на |V|=|S|. Для произвольного распределения С3) и теорема 1 означают, что H(v )=H(s), i=1,2,..,n. (3) Док-во: имеем H(v ) >= I(s; v |v ,...,v ), так как случайная переменная не может обеспечить информации больше,чем ег неопределенность. Из (1) и (2) видим, что I(s;v ,...,v ) = H(s). В заключение комбинируем 2 последних выражения и заменяем i на i. ч.и.т.д. Блейкли [1] первым опубликовал подход к решению проблемы СРС. Это вероятностный подход на базе линейной проекционной геометрии. Каждое v определяет гиперплоскость, а секрет s - единственная точка пересечения n гиперплоскостей. При этом выполняется С1), так как определено больше гиперплоскостей, чем необходимо. Блейкли привгл довод в пользу выполнения С2). Шамир [2] также опубликовал решение, основанное на том свойстве, что достаточно k любых точек (x,y) для определения коэффициентов полинома (k-1)-ой степени y = a + a x + ...... + a x . (4) Если доверенные лица имеют различные точки (x,y), v =( i, y(i)), и a =y(0)=s, то выполняется С1). Поскольку операции ведутся в конечном поле F , для которого |F|=|S|, то выполняется и С2). Поскольку имеется только |F| различных значений х и s=y(0), в системе ограничено число доверенных лиц (или частей) n <= |F|-1 . (5) Иначе одно из v было бы равно s, или два v были бы математически эквивалентны; при этом не выполнялись бы С1) и С2). ( Исключение, если к=1. Тогда каждое доверенное лицо знает весь секрет, каждое v равно s, а n может быть неограниченно большим, независимо от |F|). Метод распределения секрета, предложенный в главе II, можно рассматривать как детерминистическую версию метода Блейкли, включающую как специальный случай метод Шамира. В главе III определяются верхняя и нижняя границы максимального значения n при заданных k и |S| для любой системы, линейной или нелинейной. В главе IV обобщаются С1) и С2) на случай, когда необходимо защитить l секретов s , s ,.., s . При этом требуется, чтобы для любого 1 <= j <= l и для любого множества k индексов (i ,i ,..,i ) H(s |v ,v ,...,v )=0 (6) и H(s |v ,v ,...,v )=H(s ). (7) Таким образом, k доверенных лиц могут определить все l секретов, а любые (k-1) лиц не имеют информации ни об одном определгнном секрете. (k-1 доверенных лиц могут иметь значительную информацию о двух или более секретах, взятых попарно.) Благодаря этому обобщению возможно защитить несколько секретов таким количеством информации, которое обычно требуется лишь для защиты одного секрета. Возможно разбить большой секрет на l частей и защитить их меньшим количеством данных, чем требуется для защиты целого секрета. В главе V показано, что по ряду параметров наша система более эффективна, чем предыдущие методы. В главе VI обсуждается проблема обнаружения обмана со стороны одного из доверенных лиц. Предлагается решение на основе односторонней функции. II. ТРЕБОВАНИЯ К СРС. Наш метод распределения секрета возник на основе следующего вероятностного рассуждения: пусть u являяется полностью случайным 300-битным двоичным вектором-строкой. Пусть каждое v является 100-битным двоичным вектором-строкой, состоящим из 100 случайных проверок на чгтность для u. Это означает, что каждый бит проверки на чгтность является сложением по модулю 2 случайного подмножества 300 бит из u. Тогда любые три v связаны с u случайной двоичной матрицей размерности 300х300. Как показано в [3], приблизительно 29% nxn-матриц несингулярны над двоиным полем GF(2), а большинство остальных имеют малый дефект ранга. Следовательно, можно ожидать, что из любых тргх v возможно почти полностью восстановить u. Любые два v должны сохранить по меньшей мере 100 бит неопределгнности относительно u: 200 бит информации (два v ) должны сохранить по меньшей мере 100 бит неопределгнности относительно 300-битного вектора u. Это порождает "3-из-n СРС", если бы не два факта: 1) условие С1) не выполняется полностью, так как u не всегда полностью восстанавливается из тргх v ; 2) условие С2) не выполняется. Любые две части v и v сохраняют по меньшей мере 100 бит неопределгнности относительно u, но длина u - 300 бит. Перед рассмотрением этих проблем заметим, что метод обобщгн для любых "k-из-n" систем и для любого размера секрета. Например, при необходимости создать 7-из-10 систему с 40 битами неопределгнности, если известны шесть или меньше частей, то длина u выбирается (7*40=280)-бит, а каждое v - это 40 проверок на чгтность относительно u. Для выполнения условия С1) будем применять детерминированные коды, а не случайное кодирование. Однако в отличие от других областей теории информации случайное кодирование используется на практике, так как декодирование случайно выбранного кода сводится только к обратному преобразованию матрицы. Можно сравнить усилия требуемые для декодирования случайного линейного кода, испрапвляющего ошибки [5]. Выполнение условия С2) сводится к проблеме "дистилляции" ключа, решгнной в [3] и [4]. При дистилляции ключа имеется частично неопределгнная случайная переменная (u в нашем случае), и требуется найти новую, полностью неопределгнную случайную переменную (секрет s), которая явлалась бы функцией от u. Более того, неопределгнность новой случайной переменной должна быть такой же, как у частично неопределгнной переменной. Новая переменная обладает всей неопределгнностью исходной переменной, но в концентрированной или "дистиллированной" форме. Для проблемы распределения секрета потребуем H(s |v ,v ,...,v )=H(u |v ,v ,...,v ) (8) и H(u |v ,v ,...,v )=H(s). (9) В [3] и [4] показано, что случайные линейные проекции u часто обладают желаемым свойством дистилляции. Каждое из v является также линейной проекцией u, следовательно, можем рассматривать s как новую (n+1)-ую часть u, которую обозначим v . Если дистилляция ключа полная, то s имеет ту же длину, что и v . Теорема 2. Ассоциируя s c v и переходя от GF(2) к общему случаю - конечному полю GF(q), задача нахождения СРС вида v =u A (10) эквивалентна следующему. Найти множество n+1 матриц над GF(q), {A ,A ,A ,...,A }, каждая размерности km x m, такое, что для каждого множества из k матриц A имеет полный ранг km. (m - это размер секрета, а k - число частей, требуемых для восстановления секрета. Размерность u - km.) Примечание. Хотя обычно q рассматривается как простое число, эта теорема и все последующие выводы верны и для случая, когда q - степень простого числа. Пример. имеется 2-из-4 система с двухбитным секретом s: °10° °00° °10° А = °01° А = °00° А = °11° °00° °10° °10° °00° °01° °01° °01° °10° А = °10° А = °01° °10° °11° °01° °01