» » Схемы разделения секрета для произвольных структур доступа

Схемы разделения секрета для произвольных структур доступа

26.07.2021


Схемы разделения секрета для произвольных структур доступа (англ. Secret sharing with generalized access structure) — схемы разделения секрета, которые позволяют задать произвольный набор групп участников (квалифицированных подмножеств), имеющих возможность восстановить секрет (структуру доступа).

История

В 1979 году израильский криптоаналитик Ади Шамир предложил пороговую схему разделения секрета между n {displaystyle n} сторонами, обладающую следующими свойствами:

  • Для восстановления секрета достаточно k {displaystyle k} и больше сторон.
  • Никакие k − 1 {displaystyle k-1} и меньше сторон не смогут получить никакой информации о секрете.

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

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

Японские ученые Мицуро Ито, Акиро Саито и Такао Нишизеки первые начали изучать разделение секрета для произвольных структур доступа и в 1987 году предложили свою схему. Их мысль развили Джош Бенало и Джерри Лейхтер, предложив в 1988 году схему разделения для монотонных структур. В 1989 Эрнест Бриккелл предложил схему, в которой участникам раздаются не доли секрета, а их линейные комбинации.

Определение используемых терминов

Дилер — участник процедуры (протокола), который, зная секрет, вычисляет доли секрета и раздаёт эти доли остальным участникам.

Квалифицированное подмножество — множество участников группы, для которого разрешено восстановление секрета.

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

Структура доступа — перечисление квалифицированного и неквалифицированных подмножеств.

Пусть A {displaystyle A} — множество участников группы, n {displaystyle n} — количество участников группы, 2 [ n ] {displaystyle 2^{[n]}} — множество, состоящее из всех возможных подмножеств участников группы. Пусть Γ {displaystyle Gamma } — множество, состоящее из подмножеств участников, которым разрешено восстановление секрета (квалифицированные множества участников), Δ {displaystyle Delta } — множество, состоящее из подмножеств участников, которые не могут восстановить секрет. Структура доступа обозначается как ( Γ {displaystyle Gamma } , Δ {displaystyle Delta } ).

Структура доступа называется монотонной, если все надмножества квалифицированных подмножеств также входят в Γ {displaystyle Gamma } , то есть A ∈ Γ , A ⊆ B ⊆ P ⇒ B ∈ Γ {displaystyle Ain Gamma ,Asubseteq Bsubseteq PRightarrow Bin Gamma }

Предположим ( Γ {displaystyle Gamma } , Δ {displaystyle Delta } ) — структура доступа на A {displaystyle A} . B ∈ Γ {displaystyle Bin Gamma } называют минимальным квалифицированным подмножеством, если C ∉ Γ {displaystyle C ot in Gamma } всегда, когда C ⊂ B {displaystyle Csubset B} . Множество минимальных квалифицированных подмножеств Γ {displaystyle Gamma } обозначается как Γ m i n {displaystyle Gamma _{min}} и называется базисом Γ {displaystyle Gamma } . Минимальное квалифицированное подмножество однозначно задает структуру доступа.

Схема Бенало-Лейхтера

Пусть задана монотонная структура доступа A {displaystyle A} и Γ m i n {displaystyle Gamma _{min}} — множество минимальных квалифицированных подмножеств, соответствующее A {displaystyle A} . Пусть Γ m i n = { A 1 , A 2 , . . . , A m } {displaystyle Gamma _{min}={A_{1},A_{2},...,A_{m}}} . Для каждого A i {displaystyle A_{i}} вычисляются доли секрета для участников этого подмножества s i 1 , s i 2 , . . . , s i | A | {displaystyle s_{i1},s_{i2},...,s_{i|A|}} с помощью любой ( | A i | , | A i | ) {displaystyle (|A_{i}|,|A_{i}|)} — пороговой схемы разделения секрета.

Доля секрета s i , j {displaystyle s_{i,j}} передается соответствующему участнику. В результате каждый участник получает набор долей секрета. Восстановление секрета происходит по выбранной (n, n)-пороговой схеме.

Пример:

Γ m i n = { { 1 , 2 , 3 } , { 1 , 4 } , { 2 , 4 } , { 3 , 4 } } {displaystyle Gamma _{min}={{1,2,3},{1,4},{2,4},{3,4}}}

A 1 = { 1 , 2 , 3 }           A 2 = { 1 , 4 }           A 3 = { 2 , 4 }           A 4 = { 3 , 4 } {displaystyle A_{1}={1,2,3} A_{2}={1,4} A_{3}={2,4} A_{4}={3,4}}

Здесь, например, P 4 {displaystyle P_{4}} является вторым в A 2 , A 3 , A 4 {displaystyle A_{2},A_{3},A_{4}} , поэтому он получает доли секрета s 2 , 2 , s 3 , 2 , s 4 , 2 {displaystyle s_{2,2},s_{3,2},s_{4,2}}

Аналогично для остальных участников

P 1 ← s 1 , 1 , s 2 , 1     P 2 ← s 1 , 2 , s 3 , 1     P 3 ← s 1 , 3 , s 4 , 1     {displaystyle P_{1}leftarrow s_{1,1},s_{2,1} P_{2}leftarrow s_{1,2},s_{3,1} P_{3}leftarrow s_{1,3},s_{4,1} }

Недостаток данной схемы — возрастающий объём долей секрета для каждого участника при увеличении Γ m i n {displaystyle Gamma _{min}} .

Схема Ито-Саито-Нишизеки

Ито, Саито, Нишизеки представили так называемую технику кумулятивного массива для монотонной структуры доступа.

Пусть A {displaystyle A} — монотонная структура доступа размером n {displaystyle n} и пусть A 1 , . . . , A m {displaystyle A_{1},...,A_{m}} — соответствующие ей максимальные неквалифицированные подмножества участников.

Кумулятивный массив структуры доступа A {displaystyle A} есть матрица размеров n × m {displaystyle n imes m} ( C i , j A ) 1 ≤ i ≤ n , 1 ≤ j ≤ m {displaystyle (C_{i,j}^{A})_{1leq ileq n,1leq jleq m}} , где C i , j A = { 0 , если  i ∈ A j 1 , если  i ∉ A j {displaystyle C_{i,j}^{A}={egin{cases}0,&{ ext{если }}iin A_{j}1,&{ ext{если }}i ot in A_{j}end{cases}}} и обозначается как C A {displaystyle C^{A}} . То есть столбцы матрицы отвечают неквалифицированным подмножествам, а значение по строкам внутри столбца будет единицей, если элемент не входит в данное подмножество.

В данной схеме можно использовать любую ( m , m ) {displaystyle (m,m)} — пороговую схему разделения секрета с секретом S {displaystyle S} и соответствующими долями s 1 , . . . , s m {displaystyle s_{1},...,s_{m}}

Доли I 1 , . . . , I n {displaystyle I_{1},...,I_{n}} соответствующие секрету S {displaystyle S} будут определятся как множество s j {displaystyle s_{j}} : I i = { s j | C i , j A = 1 } {displaystyle I_{i}={s_{j}|C_{i,j}^{A}=1}}

Восстановление секрета происходит по выбранной ( m , m ) {displaystyle (m,m)} — пороговой схеме.

Сложность реализации данной схемы, достигнутая в 2016 году составляет O ( n ) {displaystyle O(n)} .

Пример:

Пусть n = 4 {displaystyle n=4} , Γ = { { 1 , 2 } , { 3 , 4 } , { 1 , 2 , 3 } , { 1 , 2 , 4 } , { 1 , 3 , 4 } , { 2 , 3 , 4 } } {displaystyle Gamma ={{1,2},{3,4},{1,2,3},{1,2,4},{1,3,4},{2,3,4}}} .

Соответствующее A {displaystyle A} множество минимальных квалифицированных подмножеств Γ m i n = { { 1 , 2 } , { 3 , 4 } } {displaystyle Gamma _{min}={{1,2},{3,4}}}

В этом случае Δ m a x = { { 1 , 3 } , { 1 , 4 } , { 2 , 3 } , { 2 , 4 } } {displaystyle Delta _{max}={{1,3},{1,4},{2,3},{2,4}}} и m = 4 {displaystyle m=4} .

Кумулятивный массив структуры доступа A {displaystyle A} имеет вид C A = ( 0 0 1 1 1 1 0 0 0 1 0 1 1 0 1 0 ) {displaystyle C^{A}={egin{pmatrix}0&0&1&11&1&0&0&1&0&11&0&1&0end{pmatrix}}}

Доли секрета участников равны I 1 = { s 3 , s 4 } ;     I 2 = { s 1 , s 2 } ;     I 3 = { s 2 , s 4 } ;     I 4 = { s 1 , s 3 } {displaystyle I_{1}={s_{3},s_{4}}; I_{2}={s_{1},s_{2}}; I_{3}={s_{2},s_{4}}; I_{4}={s_{1},s_{3}}}

Восстановление секрета аналогично восстановлению секрета в ( 4 , 4 ) {displaystyle (4,4)} — пороговой схеме Шамира.

Линейная схема разделения секрета Брикелла

Для структуры доступа A {displaystyle A} и набора участников P = { P 1 , . . . , P n } {displaystyle P={P_{1},...,P_{n}}} составляется матрица M {displaystyle M} размера n × m {displaystyle n imes m} , в которой строка M [ i ] {displaystyle M[i]} длины m {displaystyle m} ассоциируется с участником i {displaystyle i} . Для подмножества участников x ⊂ Γ {displaystyle xsubset Gamma } , которому соответствует набор строк матрицы M {displaystyle M} — M x {displaystyle M_{x}} , должно выполняться условие, что вектор ( 1 , 0 , . . . , 0 ) {displaystyle (1,0,...,0)} принадлежит линейной оболочке, натянутой на M x {displaystyle M_{x}} .

Дилер выбирает вектор r = ( r 0 , . . . , r m ) {displaystyle r=(r_{0},...,r_{m})} , где разделяемый секрет s = r 0 {displaystyle s=r_{0}} . Доля секрета участника i {displaystyle i} : s i = M [ i ] r {displaystyle s_{i}=M[i]r}

Восстановление секрета.

Выбирается вектор α {displaystyle alpha } , длины m {displaystyle m} , α x {displaystyle alpha _{x}} — вектор, составленный из координат α {displaystyle alpha } , соответствующих набору участников x ⊂ Γ {displaystyle xsubset Gamma } .

Для каждого x ⊂ Γ {displaystyle xsubset Gamma } должно выполняться условие: α x M x = ( 1 , 0 , . . . . , 0 ) {displaystyle alpha _{x}M_{x}=(1,0,....,0)} . Тогда секрет можно восстановить по формуле:

∑ i ∈ x s i α i = ∑ i ∈ x ( M [ i ] r ) α i = ( ∑ i ∈ x α i M [ i ] ) r = ( 1 , 0 , . . . , 0 ) r = s {displaystyle sum _{iin x}s_{i}alpha _{i}=sum _{iin x}(M[i]r)alpha _{i}=(sum _{iin x}alpha _{i}M[i])r=(1,0,...,0)r=s}

Пример:

Множество минимальных квалифицированных подмножество Γ = { { 1 , 2 , 3 } , { 1 , 4 } } {displaystyle Gamma ={{1,2,3},{1,4}}} .

Подходящая матрица:

( 0 1 0 1 0 1 0 1 − 1 1 1 0 ) {displaystyle {egin{pmatrix}0&1&01&0&1&1&-11&1&0end{pmatrix}}}

M {displaystyle M} удовлетворяет требованию схемы:

Для { 1 , 2 , 3 } {displaystyle {1,2,3}} : ( 1 , 0 , 0 ) = − ( 0 , 1 , 0 ) + ( 1 , 0 , 1 ) + ( 0 , 1 , − 1 ) {displaystyle (1,0,0)=-(0,1,0)+(1,0,1)+(0,1,-1)}

Для { 1 , 4 } {displaystyle {1,4}} : ( 1 , 0 , 0 ) = − ( 0 , 1 , 0 ) + ( 1 , 1 , 0 ) {displaystyle (1,0,0)=-(0,1,0)+(1,1,0)}

Доли секрета каждого участника:

P 1 ← r 1 ; P 2 ← s + r 2 ; P 3 ← r 1 − r 2 ; P 4 ← s + r 1 {displaystyle P_{1}leftarrow r_{1};qquad P_{2}leftarrow s+r_{2};qquad P_{3}leftarrow r_{1}-r_{2};qquad P_{4}leftarrow s+r_{1}qquad }

Восстановление секрета:

Для восстановления секрета выбирается α = ( − 1 , 1 , 1 , 1 ) {displaystyle alpha =(-1,1,1,1)}

Тогда для x = { 1 , 2 , 3 } {displaystyle x={1,2,3}} : α x = ( − 1 , 1 , 1 ) {displaystyle alpha _{x}=(-1,1,1)}

( − 1 , 1 , 1 ) ( 0 1 0 1 0 1 0 1 − 1 ) = ( 1 , 0 , 0 ) {displaystyle (-1,1,1){egin{pmatrix}0&1&01&0&1&1&-1end{pmatrix}}=(1,0,0)}

А для x = { 1 , 4 } {displaystyle x={1,4}} : α x = ( − 1 , 1 ) {displaystyle alpha _{x}=(-1,1)}

( − 1 , 1 ) ( 0 1 0 1 1 0 ) = ( 1 , 0 , 0 ) {displaystyle (-1,1){egin{pmatrix}0&1&01&1&0end{pmatrix}}=(1,0,0)}

Применение

Данные схемы применяются в протоколах условного раскрытия секрета (англ. conditional disclosure of secrets, CDS), безопасных распределенных вычислениях, задачах распределения ключей и схемах аутентификации нескольких приемников.