Комментарии 34
Интересно. Скажите, а практическое применение этому какое?
Подпись платежей без раскрытия суммы.
Изменение суммы платежа без раскрытия подписи? :)
Вижу два интересных направления на поиск уязвимости:
* Man in the Middle
* Выполнение операций над исходным сообщением для приведения его в состоянее, позволяющее быстро вычислить ключ.
Похоже, всю эту гомоморфную крипту придется все равно подписывать старой доброй ЭЦП.
Вижу два интересных направления на поиск уязвимости:
* Man in the Middle
* Выполнение операций над исходным сообщением для приведения его в состоянее, позволяющее быстро вычислить ключ.
Похоже, всю эту гомоморфную крипту придется все равно подписывать старой доброй ЭЦП.
Конкретно этой схемы никакого:)
А если говорить вообще о гомоморфном шифровании, то оно открывает большие возможности для облачных вычислений. Ведь используя такой способ шифрования, вы сможете отправить данные в облако в зашифрованном виде. И чтобы обработать эти данные и вернуть результат вычислений облаку даже не нужно будет знать ваш секретный ключ, т.е. никто кроме вас даже теоретически не сможет получить доступ к вашим секретным данным, хотя при этом вы сможете пользоваться всеми прелестями облачных технологий.
А если говорить вообще о гомоморфном шифровании, то оно открывает большие возможности для облачных вычислений. Ведь используя такой способ шифрования, вы сможете отправить данные в облако в зашифрованном виде. И чтобы обработать эти данные и вернуть результат вычислений облаку даже не нужно будет знать ваш секретный ключ, т.е. никто кроме вас даже теоретически не сможет получить доступ к вашим секретным данным, хотя при этом вы сможете пользоваться всеми прелестями облачных технологий.
Я правильно понимаю, что мы можем изменить сообщение не зная секретного ключа?
Функция E гомоморфна относительно операции op над открытыми текстами, если существует эффективный алгоритм M, который получив на вход любую пару криптограмм вида E(k, m1), E(k, m2), выдает криптограмму c такую, что при дешифрировании c будет получен открытый текст m1 op m2.
Да.
Есть книга Malicious Cryptography, где в качестве примера указывали применение для автора вируса:
Каждый экземпляр перед размножением увеличивает счётчик на единицу и только автор потом может анализировать результаты.
Есть книга Malicious Cryptography, где в качестве примера указывали применение для автора вируса:
Каждый экземпляр перед размножением увеличивает счётчик на единицу и только автор потом может анализировать результаты.
Например, некий «dropbox» хранит ваши данные зашифрованные вашим ключем (т.е. сам прочитать их не может), а нечто вроде полнотекстовой индексации по ним делать может.
Как он сделает индексацию если исходные данные недоступны?
Будет искать в зашифрованных данных заданные ключевые слова. В терминах статьи, f_W(M) = if (M contains W) then 1 else 0;.
Кхм, простите, у меня какой-то когнитивный диссонанс. Каким это образом третья сторона будет что-то искать в зашифрованных данных?
Наверное он хочет сказать, что третья сторона сделает индексацию обработку внутри самого контейнера.
При этом данные прочесть так и не сможет
При этом данные прочесть так и не сможет
Рассмотрим утрированный вариант: шифрование осуществляется XOR-ом каждого байта сообщения с однобайтовым ключом K, известным только клиенту. Сервер хранит зашифрованные данные. «Индексируем» однобайтовые «ключевые слова». Каждому такому ключевому байту W, соответствует функция f_W(M) = if (M contains W) then 1 else 0, которая ищет ключевой байт в clear-text. Ей соответствует функция Enc(f_W), которая ищет ключевой байт W в зашифрованном тексте. В нашем случае Enc(f_W) можно выписать явно: Enc(f_W)(S) = if (S contains (W XOR K)) then 1 else 0 (где S зашифрованный текст).
Для индексации, клиент передает серверу список ключевых слов и соответствующих функций: ((W XOR K), Enc(f_W)), ((Y XOR K), Enc(f_Y)), ...). Сервер запускает функции и строит индекс, не зная ключа. Понятно, что вместо передачи собственно функций их можно как-то параметризовать и передавать параметр. В нашем случае, никакого параметра вообще не требуется: (W XOR K) однозначно определяет функцию поиска в зашифрованном тескте.
В общем случае, метод остается тем же: ключевому слову сопоставляется функция поиска, ей сопоставляется функция поиска в зашифрованном тексте. То, что это будет именно функция поиска (а не расшифровка с последующим поиском в clear-text), гарантируется гомоморфностью алгоритма шифрования.
Для индексации, клиент передает серверу список ключевых слов и соответствующих функций: ((W XOR K), Enc(f_W)), ((Y XOR K), Enc(f_Y)), ...). Сервер запускает функции и строит индекс, не зная ключа. Понятно, что вместо передачи собственно функций их можно как-то параметризовать и передавать параметр. В нашем случае, никакого параметра вообще не требуется: (W XOR K) однозначно определяет функцию поиска в зашифрованном тескте.
В общем случае, метод остается тем же: ключевому слову сопоставляется функция поиска, ей сопоставляется функция поиска в зашифрованном тексте. То, что это будет именно функция поиска (а не расшифровка с последующим поиском в clear-text), гарантируется гомоморфностью алгоритма шифрования.
Тут понимаете какое ограничение есть. Схема то гомоморфна относительно двух операций: умножения и сложения. Полностью гомоморфной ее называют из-за того что с помощью этих двух операций можно выразить любую другую математическую операцию. Т.е. если вашу функцию F_W() можно будет описать только с помощью умножения и сложение, то тогда да, то о чем вы говорите будет возможно.
Причем, например, для RSA мы ограничены только умножением.
Если я не путаю, умножение и сложение не является базисом без отрицания.
Так что любую функцию выразить не получится
Так что любую функцию выразить не получится
Полностью гомоморфное шифронание (fully homomorphic encryption), описанное Craig Gentry, гомоморфно относительно цепей (circuits), составленных из NAND, в которых можно выразить любую операцию. См. ссылку на его диссертацию выше.
НЛО прилетело и опубликовало эту надпись здесь
Да уж… это очень клёво когда можно модифицировать подписанные данные, при сохранении их валидности.
— электронное голосование
— проверка целостности данных
— разграничение доступа (совмесный доступ без раскрытия)
…
возможных прменений много… проблема только в том, что текущие реализации далеки от совершенства
— проверка целостности данных
— разграничение доступа (совмесный доступ без раскрытия)
…
возможных прменений много… проблема только в том, что текущие реализации далеки от совершенства
С теоретической точки зрения гомоморфное шифрование — это круто, просто нирвана для криптографа, то, о чем они мечтают уже три десятка лет. Но с практической — это бич криптографии, и то, с чем предстоит еще очень много работы.
Только вот вычислительная сложность при работе с зашифрованным сообщением значительно выше, чем сложность при работе с исходным, или я неправильно понял статью?
Так как с темой гомоморфного шифрования я знаком не понаслышке, добавлю немного информации по теме.
Схема шифрования, представленная в этом посте на самом деле не является честным гомоморфным шифрованием, так как не порождает гомоморфизма в математическом понимании этого термина. Это легко понять, взглянув на наличие ограниченное количество операций до того как шифротекст потеряет возможность расшифровки в силу роста шума, о чем автор поста справедливо упомянул. По этой причине Гентри назвал эту схему Somewhat Homomorphic Encryption.
На самом деле истинная заслуга Гентри в том, что он на основе этой схемы сумел построить настоящее гомоморфное шифрование без ограничения числа операций, применив процедуру, названную им Bootstrapping. Единственное, почему данная схема не применяется на практике — она очень требовательна к ресурсам процессора и памяти. Но принципиальное существование грааля криптографии он доказал, за что ему честь и хвала.
После этой работы появилась целая серия работ, развивающих идеи Гентри, но практически все они унаследовали потребность в bootstrapping'е, что оставило их в статусе лабораторных экспериментов.
После сей исторической справки я хочу сказать пару слов о схемах гомоморфного шифрования, над которыми работаем мы в лаборатории НГУ-Parallels.
В основе лежит очень простая идея. Пусть мы хотим защифровать числа a и b. Тогда мы берем и строим полиномы A(x) и B(x) такие, чтобы числа a и b были их свободными членами. Фокус первый: если перемножить или сложить эти полиномы, в свободном члене результата окажутся числа a*b и a+b соответственно. Фокус второй: надо построить секретный полином P(x) такой, чтобы он задавал обратимую замену переменных, тогда шифрование будет осуществляться подстановкой замены переменных: A'(x)=A(P(x)) и B'(x)=B(P(x)). Расшифрование — подстановкой обратной замены переменных, т.е. A(x)=A(P(Q(x))), где Q(x) — как раз полином обратной замены. Нетрудно доказать, что выполненные над зашифрованными полиномами операции сложения и умножения будут операциями гомоморфного шифрования.
Я отдаю себе отчет, что из этого сжатого изложения непросто понять, как это работает, и, тем более, почему. Поэтому даю ссылку на более аккуратное изложение этой информации — тезисы моего доклада на Positive Hack Days от сего года и на презентацию от него же.
Выполненная мною реализация одной из этих схем на C++ показала, что проседание производительности сложения и умножения целых чисел в данной схеме по сравнению и простым незашифрованным сложением и умножением — примерно на три порядка, что почти приемлемо для практического использования и куда лучше схемы Гентри.
Если тема интересна, могу написать отдельный пост по данным схемам шифрования — материала у меня навалом :-)
Схема шифрования, представленная в этом посте на самом деле не является честным гомоморфным шифрованием, так как не порождает гомоморфизма в математическом понимании этого термина. Это легко понять, взглянув на наличие ограниченное количество операций до того как шифротекст потеряет возможность расшифровки в силу роста шума, о чем автор поста справедливо упомянул. По этой причине Гентри назвал эту схему Somewhat Homomorphic Encryption.
На самом деле истинная заслуга Гентри в том, что он на основе этой схемы сумел построить настоящее гомоморфное шифрование без ограничения числа операций, применив процедуру, названную им Bootstrapping. Единственное, почему данная схема не применяется на практике — она очень требовательна к ресурсам процессора и памяти. Но принципиальное существование грааля криптографии он доказал, за что ему честь и хвала.
После этой работы появилась целая серия работ, развивающих идеи Гентри, но практически все они унаследовали потребность в bootstrapping'е, что оставило их в статусе лабораторных экспериментов.
После сей исторической справки я хочу сказать пару слов о схемах гомоморфного шифрования, над которыми работаем мы в лаборатории НГУ-Parallels.
В основе лежит очень простая идея. Пусть мы хотим защифровать числа a и b. Тогда мы берем и строим полиномы A(x) и B(x) такие, чтобы числа a и b были их свободными членами. Фокус первый: если перемножить или сложить эти полиномы, в свободном члене результата окажутся числа a*b и a+b соответственно. Фокус второй: надо построить секретный полином P(x) такой, чтобы он задавал обратимую замену переменных, тогда шифрование будет осуществляться подстановкой замены переменных: A'(x)=A(P(x)) и B'(x)=B(P(x)). Расшифрование — подстановкой обратной замены переменных, т.е. A(x)=A(P(Q(x))), где Q(x) — как раз полином обратной замены. Нетрудно доказать, что выполненные над зашифрованными полиномами операции сложения и умножения будут операциями гомоморфного шифрования.
Я отдаю себе отчет, что из этого сжатого изложения непросто понять, как это работает, и, тем более, почему. Поэтому даю ссылку на более аккуратное изложение этой информации — тезисы моего доклада на Positive Hack Days от сего года и на презентацию от него же.
Выполненная мною реализация одной из этих схем на C++ показала, что проседание производительности сложения и умножения целых чисел в данной схеме по сравнению и простым незашифрованным сложением и умножением — примерно на три порядка, что почти приемлемо для практического использования и куда лучше схемы Гентри.
Если тема интересна, могу написать отдельный пост по данным схемам шифрования — материала у меня навалом :-)
Спасибо за такой интересный комментарий. Да я понимаю что описанная в топике схема всего лишь Somewhat Homomorphic Encryption, просто честно говоря отсутсвие времени да и слабое знания английского языка не позволили рассмотреть чтоже скрывается под этой идеей, в частности что такое Bootstrapping и как она работает.
Поэтому лично мне ваш пост было бы вдвойне интересно почитать. Просим, просим.:)
Поэтому лично мне ваш пост было бы вдвойне интересно почитать. Просим, просим.:)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Публикации
Гомоморфное шифрование своими руками