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

Описание

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

Выбирается векторов размерности таким образом, чтобы ранг любой матрицы, составленной из данных векторов, был равен .

Вектор известен всем участникам. Секретом является скалярное произведение , долями — скалярные произведения и векторы .

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

Литература

• Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = 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. — 0018-9448. — 10.1109/TIT.1983.1056621