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

Визуальное разделение секрета (Naor и Shamir, 1994) разбивает изображение на n прозрачных плёнок так, что наложение k плёнок раскрывает секретное изображение, а любое меньшее количество не раскрывает ничего — даже противнику с неограниченными вычислительными возможностями.

Каждый пиксель секрета преобразуется в блок размером 2x2. Для чёрного пикселя обе доли получают взаимодополняющие узоры (при наложении получается полностью чёрный цвет). Для белого пикселя обе доли получают одинаковый узор (при наложении 50% чёрного цвета дают серый). Глаз воспринимает эту разницу.

Для битовых строк: разделите секрет S, сгенерировав случайные значения R_1, R_2, ..., R_{n-1}. Установите R_n = S XOR R_1 XOR ... XOR R_{n-1}. Побитовая операция XOR над всеми n долями даёт S. Любое подмножество из n-1 долей равномерно случайно и ничего не раскрывает о S.

Разделение с помощью XOR или аддитивное разделение имеет схему n из n: требуются все доли. SSS Шамира имеет схему k из n: подходят любые k долей. Аддитивное разделение проще и быстрее, а Шамир поддерживает произвольные пороги. В протоколах MPC для арифметических операций часто используется аддитивное разделение.

Для целочисленных секретов представьте S как S = s_1 + s_2 + ... + s_n (mod p). Каждое s_i — случайный элемент Z_p. Чтобы сложить два разделённых значения A+B, каждый участник локально складывает свои доли: (a_i + b_i) mod p. Для сложения обмен данными не требуется.

Умножение разделённых между участниками секретных значений требует взаимодействия. Классический метод тройки Бивера: заранее вычислите разделённые случайные значения (a, b, c=ab). Чтобы умножить x*y, раскройте (x-a) и (y-b) всем участникам (эти значения ничего не раскрывают о x и y), а затем вычислите x*y с помощью тройки.

Схема линейного разделения секрета (LSSS) реализует любую монотонную структуру доступа. Схема Шамира является LSSS. LSSS служат строительным блоком для шифрования на основе атрибутов (ABE) и систем управления доступом с несколькими центрами полномочий.

Упакованные доли Шамира содержат несколько секретов в одном многочлене: k секретов кодируются как коэффициенты многочлена степени (n-k). Это позволяет распределять затраты на обмен данными в протоколах MPC, когда множество значений нужно разделить одновременно.

Базовые схемы разделения не защищают от злоумышленников, передающих недействительные доли. Проверяемое разделение секрета (VSS) добавляет обязательства, а устойчивое разделение секрета добавляет исправление ошибок, поэтому восстановление успешно даже при наличии t ошибочных долей.

Визуальная криптография: аутентификация печатных документов и защищённые избирательные бюллетени. Аддитивное разделение: MPC SPDZ и защищённое агрегирование в федеративном машинном обучении (Google). Пороговые схемы: резервное копирование исходной фразы аппаратного кошелька и управление ключами предприятия.

Схема с разрывом (k,n) слабее: менее чем k-d долей раскрывают частичную информацию (d уровней секретности). Она используется, когда совершенная секретность частичных долей не требуется, но критически важна эффективность хранения. Такие схемы позволяют использовать более короткие доли, чем схема Шамира.

В аддитивном разделении n из n на основе XOR сколько долей необходимо для восстановления секрета?

Визуальная криптография разбивает изображения на прозрачные плёнки; аддитивное разделение использует XOR для схем n из n; Шамир поддерживает схемы k из n. MPC использует аддитивное разделение с тройками Бивера для умножения. Далее: пороговые подписи и применение в реальном мире.