Американский исследователь Крэг Джентри (Craig Gentry) решил математическую задачу, которая три десятилетия не давала покоя криптографам. Применив нетрадиционный подход, он создал схему, позволяющую всесторонне обрабатывать зашифрованные данные, не искажая и не расшифровывая их.
В представленном протоколе гомоморфного шифрования Джентри использовал свои наработки в области шифрования методом решетки. Он оперирует понятием «идеальной решетки», которая обеспечивает гомоморфность относительно сложения и умножения. Конечно, схема пока далека от практической реализации, не проверена на безопасность и в нынешнем ее виде требует колоссальных затрат вычислительных ресурсов. Однако открытие, совершенное 36-летним исследователем, является важным прорывом в области математических методов защиты информации.
Комментарии (8)
старые сверху
«дерево»
Phoenix06 июл 2009, 00:35
|
|
2 |
|
|
Re:
не зная сути "гомоморфного шифрования" могу сказать: операции сложения и умножения это уже много. например процессор ПК это сильно продвинутое АЛУ. что может АЛУ? складывать и логические операции. проинвентировав число и сложив с другим получаем вычитание. сдвиг это умножение(деление) на 2. умножение это суммирование числа с другим многократно подвергаемым сдвигу. корни, логарифмы и т.д. и т.п. математика как раз для того и развивается чтобы сложные операции делать элементрарными дейсвиями.
|
|
|
Анонимно06 июл 2009, 01:26
|
|
0 |
|
|
Re: свойство гомоморфности, сложение и умножение
Гомоморфное шифрование обеспечивает безошибочную обработку зашифрованных данных без их расшифровки. До сих пор гомоморфные криптосистемы допускали лишь несколько операций над данными - или сложения, или умножения. А ведь сложные алгоритмы, на которых основана работа прикладных программ, включают много операций и сложения, и умножения. Джентри доказал возможность выполнения неограниченного числа любых операций над шифротекстом без его искажения и расшифровки.
|
|
Constantin E. Climentieff06 июл 2009, 13:48
|
|
0 |
|
|
И все равно, "всесторонне обрабатывать" - слишком сильное заявление. В моем представлении "обработка данных" - это полный спектр арифметических и логических операций, преобразований, сравнений, линейных, нелинейных и т.п. Кстати, насчет "неограниченного числа ЛЮБЫХ операций"... гм-гм... все-таки, по тексту статьи - только сложения и умножения, и не более того. Я не ставлю под сомнение выводы автора открытия, он молоток, и его работа принесет много пользы. Мне не нравятся русскоязычные формулировки, искажающие, на мой взгляд, суть. Речь идет о возможности линейных ПРЕОБРАЗОВАНИЙ зашифрованных данных без их расшифрования. Нет?
|
|
|
Анонимно06 июл 2009, 17:26
|
|
0 |
|
|
Re: При чем здесь линейное преобразование?
Давайте определимся с терминологией. Под обработкой данных в данном случае понимается выполнение компьютером последовательности операций, определяемой алгоритмом (прикладной) программы. Все операции обработки данных разделяются на логические и арифметические. И те, и другие, как бы сложен ни был алгоритм, сводятся к элементарным действиям над данными - в большинстве случаев это сложение или умножение.
|
|
Sassa27 июл 2009, 23:52
|
|
0 |
|
|
Re: Re: При чем здесь линейное преобразование?
...и еще деление и остаток от деления. если ограничиваться конечными полями, то в RSA такие же операции тоже можно делать с 1979-го. И ШО?
Не забываем об аналитических функциях сравнения чисел (цикл без этого не построишь). Если кто-то может построить функцию сравнения на гомоморфной криптографии, тогда эту криптографию придется выбросить за окошко.
|
|
Constantin E. Climentieff06 июл 2009, 23:44
|
|
0 |
|
|
Re: при том :)
Т.е. вы ставите знак равенства между "обработкой" и "набором операций над данными"? Спорно, ибо первое всегда является вторым, но второе не всегда является первым, - вот за это мой глаз и зацепился. И далее, из статьи Гентри следует, что под гомоморфной схемой шифрования он понимает: пусть X, Y и Z - шифротексты, зашифрованные на одном ключе, тогда без расшифрования их можно выполнять X*Y+Z - линейные преобразования над шифротекстами, а еще, видимо, некоторый класс нелинейностей вида X*X. Да, это большой класс преобразований, но говорить от том, что этот класс составляет "большинство" от всевозможных используемых преобразований, вряд ли стоит. По крайней мере, утверждение, что логические операции сводятся к умножению и сложению, вызывает очень большое сомнение. Да и вообще, все это очень сильно зависит от интерпретации данных, подвергаемых обработке: текст ли это, целое ли число, вещественное ли и т.п. Вот тут и проявляется терминологическая неточность: вроде бы, операции можно выполнять - какие хочешь, а желаемый результат "обработки", даже самый простой, окажется недостижим. А "обработка" - это, все таки, преобразование с целью получения определенного результата: http://dic.academic.ru/dic.nsf/ruwiki/372393. Думаю, надо искать более точный и конкретный перевод для термина "evaluate circuits", чем "обработка данных".
|
|
|
Анонимно07 июл 2009, 04:35
|
|
1 |
|
|
Re: обработка, преобразование, вычисления, операции
Простите, по Вашей ссылке цитируемого Вами определения обработки нет. Зато там есть ссылка на статью в Научно-техническом энциклопедическом словаре: "ОБРАБОТКА ДАННЫХ - систематизированная последовательность операций, совершаемых с данными, прежде всего в компьютере, для получения новой информации путем вычислений, пересмотра и уточнения имеющейся информации..." А Wiki не люблю.
"Обработка" по-английски вообще-то будет data processing.
В источниках http://www-03.ibm.com/press/us/en/pressrelease/27840.wss и http://www.forbes.com/forbes/2009/0713/breakthroughs-privacy-super-secret-encryption.html употребляется словосочетание perform computations, "проводить вычисления", т.е. осуществлять процессы обработки данных (= последовательные операции) с преобразованием входных значений в выходные. "Evaluate circuits" мне уже встречалось в современных текстах. Видимо, это неологизм. Могу предложить примерный перевод: "проводить вычисления в соответствии с заданными схемами".
Давайте закончим терминологические прения, заменив "любые операции" на "произвольные" (см. аннотацию к статье Джентри - arbitrary circuits).
исправлено: tatnik, 07 июл 2009, 05:01
|
|
|
|