Похоже, в криптографии появились интересные вещи: первая схема homomorphic encryption появилась недавно (explanation, HT). Грубо говоря, это способ кодирования x
в f(x)
таким образом, что вы можете вычислить f(x+y)
легко зная f(x)
и f(y)
, даже если вы не можете легко восстановить x
и y
(и то же самое для f(x*y)
).Практические применения гомоморфных алгоритмов шифрования?
Каковы практические применения для схем такого типа (как только их безопасность была установлена)? Для меня, похоже, они могут значительно упростить алгоритмы написания для управления частными данными.
Вот мои мысли:
- электронное голосование
- проверки целостности личных данных
- есть шанс, что помогло бы приватность в целом?
Пример: У меня есть счета в банках A, B, C. Entity X хочет, чтобы подтвердить у меня есть более $ 1000 общей суммы; он с радостью согласится с заявлениями из банков A, B, C или D, но, к сожалению, у меня недостаточно денег на какой-либо одной учетной записи. Банк А зашифровывает информацию о моих 500 долларов США моим открытым ключом; Аналогично, Banks B и C шифруют информацию, что у меня есть 200 и 300 долларов соответственно. Они отправляют эти данные в X, который добавляет их к некоторому числу, которое, как я доказываю, фактически зашифровано в 1000 долларов (путем шифрования 1000 долларов с помощью открытого ключа и демонстрации того, что результат одинаков). Я доказал что-то, не раскрывая X
, сколько денег у меня есть в каждом аккаунте.
Другого пример: Хорошие граждане X_1, ..., X объединяются, чтобы выбрать один из двух кандидатов, один из которых является латте пьющего луба л, а другой является B кого-подшипник (все имена вымышлены). Они решают, что они хотят, чтобы голосование было закрытым, но быстрым. Они отправляют свои голоса в векторном формате (1, vote_A, vote_B, vote_None)
, зашифрованном в Избирательную комиссию, который публично добавляет их и получает результат в форме (count, count_A, count_B, count_None)
. После проверки этого count = count_A + count_B + count_None
официальные лица заявляют о победе одного из кандидатов, после чего судья по какой-либо причине признается недействительным, не связанным с электронным голосованием, и в течение следующих 10 лет боролся в суде, но, эй, это не моя проблема в любом случае.
Примечания: - Я считаю, что этот конкретный пример был возможен с RSA еще раньше, поскольку для одной операции требуется только гомоморфность. Надежда состоит в том, что у нас могут быть более интересные вещи с большим количеством операций - так что придумайте примеры!
Я особенно хотел бы видеть ответы, содержащие код и/или разработке систем, которые имеют шанс быть использованы на практике, по той причине, SO это не теоретическая информатика доски обсуждений.
Гомоморфный алгоритм, чтобы повторить сказанное ниже в комментариях, позволяет создать программу, которая будет управлять данными, не зная их.К сожалению, типы программ несколько ограничены: у вас не может быть
if (x=0) ...
, потому чтоx
зашифрован, и каждый шаг очень медленный (есть некоторые решетки).
Хорошая идея, но довольно сложная. Это проблема «все или ничего» для X. Он должен доверять A, B и C. Если он не доверяет C, он все равно должен быть не в состоянии определить, что у меня есть 700 @ Banks A и B. – MSalters
Правда, но это то, как обычно работают вещи в реальном мире - в вопросах денег всем банкам достаточно доверяют. Если вас попросят представить доказательства того, что вы заплатили за gizmo XXX из магазина YYY, то заявление о кредитной карте из * любого * банка будет считаться доказательством. Более того, если в банке C указано, что у меня есть 300 долларов, но для этого мне недостаточно денег, FDIC покрывает его. –
Я что-то упустил, или почему у банков в вашем примере есть ваш секретный ключ? Если у вас есть свой секретный ключ, он действительно личный? Или у них есть закрытый ключ для вас (и отдельный для каждого другого клиента), для которого доступен открытый ключ? Или вы имели в виду, что банки шифруют ваш баланс своим личным ключом, открытый ключ для которого хорошо известен? –