Схема Карнина

Схема Карнина — Грина — Хеллмана — пороговая схема разделения секрета на основе скалярного произведения. Авторы — Эхуд Карнин (англ. Ehud D. Karnin), Йонатан Грин (Jonathan W. Greene) и Мартин Хеллман.

Описание

Пусть нужно разделить секрет между $n$ сторонами таким образом, чтобы любые $t$ сторон могли восстановить секрет, но $t-1$ — не могли. То есть нужно реализовать (t, n)-пороговую схему.

Выбирается $n+1$ векторов $\vec v_0, \vec v_1, \dots, \vec v_n$ размерности $m$ таким образом, чтобы ранг любой матрицы, составленной из $m$ данных векторов, был равен $m$.

Вектор $\vec v_0$ известен всем участникам. Секретом является скалярное произведение $\langle \vec u, \vec v_0\rangle$, долями — скалярные произведения $\langle \vec u, \vec v_i\rangle$ и векторы $\vec v_i$.

Для восстановления секрета по известным долям (и набору векторов $\vec v_1, \vec v_2, \dots, \vec v_n$) решается система из $m$ уравнений для нахождения вектора $\vec u$. Сделать это, имея меньшее число долей, невозможно.

Литература

• Шнайер Б. 23.2 Алгоритмы разделения секрета. Karnin — Greene — Hellman // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — С. 590. — 816 с. — 3000 экз. — ISBN 5-89392-055-4
• Karnin, E., Greene, J., Hellman, M. On secret sharing systems (англ.) // Information Theory, IEEE Transactions on. — 1983. — В. 1. — Т. 29. — С. 35—41. — ISSN 0018-9448. — DOI:10.1109/TIT.1983.1056621