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

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

История

править

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

  • Для восстановления секрета достаточно   и больше сторон.
  • Никакие   и меньше сторон не смогут получить никакой информации о секрете.[1]

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

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

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

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

править

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

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

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

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

Пусть   — множество участников группы,   — количество участников группы,   — множество, состоящее из всех возможных подмножеств участников группы. Пусть   — множество, состоящее из подмножеств участников, которым разрешено восстановление секрета (квалифицированные множества участников),   — множество, состоящее из подмножеств участников, которые не могут восстановить секрет. Структура доступа обозначается как ( , ).

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

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

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

править

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

Доля секрета   передается соответствующему участнику. В результате каждый участник получает набор долей секрета. Восстановление секрета происходит по выбранной (n, n)-пороговой схеме.[3]

Пример:

 

 

Здесь, например,   является вторым в  , поэтому он получает доли секрета  

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

 

Недостаток данной схемы — возрастающий объём долей секрета для каждого участника при увеличении  [5][6].

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

править

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

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

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

В данной схеме можно использовать любую   — пороговую схему разделения секрета с секретом   и соответствующими долями  

Доли   соответствующие секрету   будут определятся как множество  :  

Восстановление секрета происходит по выбранной   — пороговой схеме.

Сложность реализации данной схемы, достигнутая в 2016 году составляет  .[7]

Пример:

Пусть  ,  .

Соответствующее   множество минимальных квалифицированных подмножеств  

В этом случае   и  .

Кумулятивный массив структуры доступа   имеет вид  

Доли секрета участников равны  

Восстановление секрета аналогично восстановлению секрета в   — пороговой схеме Шамира.

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

править

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

Дилер выбирает вектор  , где разделяемый секрет  . Доля секрета участника  :  

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

Выбирается вектор  , длины  ,   — вектор, составленный из координат  , соответствующих набору участников  .

Для каждого   должно выполняться условие:  . Тогда секрет можно восстановить по формуле:

 [4]

Пример:

Множество минимальных квалифицированных подмножество  .

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

 

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

Для  :  

Для  :  

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

 

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

Для восстановления секрета выбирается  

Тогда для  :  

 

А для  :  

 

Применение

править

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

Примечания

править
  1. 1 2 Shamir A. How to share a secret // Commun. ACM — NYC, USA. — 1979. — Т. 22. — С. 612—613.
  2. 1 2 Ito M., Saito A., Nishizeki T. Secret sharing scheme realizing general access structure // Electronics and Communications in Japan (Part III: Fundamental Electronic Science). — 1987. Архивировано 23 апреля 2021 года.
  3. 1 2 Benaloh J., Leichter J. Generalized Secret Sharing and Monotone Functions // Advances in Cryptology - CRYPTO' 88. — 1988. — С. 27—35.
  4. 1 2 Brickell E. F. Some ideal secret sharing schemes // Journal of Combin. Math. and Commbin. Comput. no. 9. — 1989. — С. 105—113.
  5. Sreekumar A., Babusundar S. Secret Sharing Schemes using Visual Cryptography // Cochin University of Science and Technology. — 2009.
  6. Kouya TOCHIKUBO. A Construction Method of Secret Sharing Schemes Based on Authorized Subsets // International Symposium on Information Theory and its Applications. — 2008.
  7. Lein Harna, Hsu Chingfang, Zhang Mingwua, He Tingtingc, Zhang Maoyuanc. Realizing secret sharing with general access structure // Information Sciences. — 2016. — № 367–368. — С. 209—220.
  8. Gertner, Y., Ishai, Y., Kushilevitz, E., Malkin, T. Protecting data privacy in private information retrieval schemes // Journal of Computer and System Sciences. — 2000. — № 60(3). — С. 592–629.
  9. Ben-Or, M., Goldwasser, S., Wigderson, A. Completeness theorems for noncryptographic fault-tolerant distributed computation. In: Proceedings of the 20th annual ACM symposium on Theory of computing // ACM Press. — 1998. — С. 1–10.
  10. Cramer, R., Damg˚ard, I., Maurer, U. General secure multi-party computation from any linear secret-sharing scheme. // Preneel, B. (ed.) EUROCRYPT 2000. — Т. 1807. — С. 316–334.
  11. Cramer, R., Damg˚ard, I., Nielsen, J.B. Secure Multiparty Computation and Secret Sharing: An Information Theoretic Approach.. (недоступная ссылка)
  12. Lee, C.-Y., Wang, Z.-H., Harn, L., Chang, C.-C. Secure key transfer protocol based on secret sharing for group communications // IEICE Trans. Inf. and Syst.. — 2011. — С. 2069–2076.
  13. Zhang, J., Li, X., Fu, F.-W. Multi-receiver authentication scheme for multiple messages based on linear codes // Huang, X., Zhou, J. (eds.) ISPEC 2014. LNCS. — 2014. — Т. 8434. — С. 287–301.