Пользователь
0,0
рейтинг
3 марта 2010 в 22:11

Разработка → Гомоморфное шифрование/ (Fully) Homomorphic Encryption

Так и подмывало озаглавить тему: «Закат компании Гугл близок!», но все-таки слишком уж «желто» было бы.

Теперь к делу. Что такое «гомоморфное шифрование» и причем тут Гугл?

Гомоморфным шифрованием называют такую криптосистему, которая позволяет совершать некоторые математические действия с открытым текстом путем произведения операций с зашифрованным (возможно другое математическое действие или даже ряд операций). Например, RSA гомоморфна для операции умножения (тривиально из самого шифрования).

Удивительно, но до недавних пор не существовало криптосистемы гомоморфной для операций умножения и суммирования одновременно, так называемого полностью гомоморфного шифрования (fully homomorphic encryption), т.к. суммы и умножения хватит, чтобы выразить любую математическую функцию. Главная проблема с предыдущими схемами была в том, что каждая операция добавляет некоторый «шум» в криптотекст (посмотрите на формулу RSA и вспомните определение mod), поэтому через некоторое количество шагов накопленный шум делает расшифровку невозможной. Насколько я помню из презентации, говорилось, что подобные схему все же существуют, но они экспоненциональны по «эффективности».

Крэйг Гэнтри (Craig Gentry, PhD Stanford, IBM Research) опубликовал пример первой такой функции в своей PhD диссертации. Не вдаваясь в подробности (да и не буду делать вид, что на 100% понял все математические выкладки), смысл его решения заключается в том, что он использует двойное шифрование. Т.е. через определенное количество шагов он «снимает верхний слой» (первое шифрование) и «убирает» накопившийся «шум».

Как это работает, я расскажу общими словами и примерами, которые он сам использовал в своей презентации. Кому интересна математика и более формальное объяснение — читать диссертацию.




Пример, который он приводил довольно прост. Представьте, что ювелир работает с драгоценностями. Чтобы исключить воровство, эти драгоценности ему даются в прозрачном ящике с перчатками, чтобы он мог работать. Кроме того, к сожалению данные перчатки портятся после определенного промежутка времени (вспомним, про накопление «шума»), поэтому каждый раз когда перчатки вот-вот должны испортиться, этот первоначальный ящик вставляют внутрь идентичного ящика. И так продолжается до тех пор, пока работа не завершена.

Конечно, данный пример не идеален, но он дает некоторое представление о работе полной гомоморфной функции Гэнтри.

Теперь вспомним причем же тут Гугл? А смысл в том, что если этот алгоритм внедрить, например, в Гугл, то они не смогут узнать ваш запрос и даже ответ. Зачем им это делать, это, конечно, уже другой вопрос. Более интересный пример, это налоговые декларации. Представьте, что вы отсылаете зашифрованную вашим закрытым ключом декларацию и получаете также зашифрованный результат от налогового специалиста, который не узнал ни бита информации о ваших доходах.

К сожалению, хоть и текущая реализация полной гомоморфной системы работает за полиномиальное время, константы там «неприлично огромные», поэтому в ближайшее будущее Гугл может спать спокойно.

UPDХотелось бы упомянуть интересный факт из биографии Крэйга. Он получил бакалавра математики в университете Дьюка, потом закончил юридическую школу Гарварда, а потом решил, что для полного счастья ему не хватает PhD в computer science! Решение проблемы, описанной в статье, он нашел будучи на стажировке в IBM Research.
vimmer @vimmer
карма
130,2
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (58)

  • +9
    тем кому не лень минусовать карму >> пожалуйста, учтите, что не все понятия, содержащие корень «гомо» — враждебны :) хехе
    • НЛО прилетело и опубликовало эту надпись здесь
      • 0
        не знаю =) вдруг есть какие-то.
    • +4
      Честное слово, я абсолютно не представляю себе ход мыслей людей, минусующих такую статью. Спасибо, было интересно.
    • –10
      Только раза с третьего понял, что не «ГОМОФОБНОЕ шифрование» (-: Чуть глаза не вывихнул.
  • +4
    Хотелось бы упомянуть интересный факт из биографии Крэйга. Он получил бакалавра математики в университете Дьюка, потом закончил юридическую школу Гарварда, а потом решил, что для полного счастья ему не хватает PhD в computer science! Решение проблемы, описанной в статье, он нашел будучи на стажировке в IBM Research.
  • +9
    Ничего не понял, но ваш энтузиазм по поводу сабжа меня радует )
    • +2
      простите, видимо слабо мотивировал проблему =) или вы не поняли решение?

      если мотивация, то смысл в том, что можно производить осознанные действия над зашифрованным текстом без знания, что за этим текстом скрывается.

      Если же вы про решение, то там алгебра (группы, кольца). Мне перчаток и коробок хватило =)
      • +4
        Да не в том дело.
        Вот я, например, в курсе существования групп и колец. Но из текста не понял, зачем нам производить действия над зашифрованным текстом. (RSA позволяет умножение текста! Круто! Но зачем?)
        Кроме того, вот это, например: «позволяет совершать некоторые математические действия с открытым текстом путем произведения операций с зашифрованным» я и вовсе не понял. У нас есть открытый текст и есть зашифрованный. Мы что-то делаем над одним, но гомоморфность операции позволяет сделать это и над другим…

        Короче, пока картинку не рассмотрел, не понял ничего. 8)
        • +2
          спасибо, я понял, что мне надо работать над презентацией мыслей =)
      • 0
        Читал в первый раз в Opera Mini с выключенными картинками, сейчас уже яснее стало :)
  • +1
    > криптосистемы гомоморфной для операций умножения и суммирования одновременно, так называемого полностью гомоморфного шифрования (fully homomorphic encryption)

    Смотрим страницы 5 и 28, там другое определение. То, что Вы говорите, это обычный кольцевой гомоморфизм, а что касается fully homomorphic encryption, там появляются слова типа compactly evaluates.
    Не могу сказать, насколько сильно различие, потому как много специфичных для данной области терминов. Тут требуется специалист.
    • 0
      вы правы, что это не самое точное определение.

      Определение с 5 страницы
      At a high-level, the essence of fully homomorphic encryption is simple: given ciphertexts that encrypt π1,..., πt, fully homomorphic encryption should allow anyone (not just the key-holder) to output a ciphertext that encrypts f (π1,..., πt ) for any desired function f, as long as that function can be efficiently computed.

      Это практически тоже самое, если учесть, что с помощью + и * можно построить схему (circuit) для определения практически любой функции за «конечное время» (если ничего не путаю). Для более точной формулировки нужно привлечь некоторые определения со стр 28 по поводу «осуществимости» построения такой схемы.

      Но все же смысл, думаю, исказил не слишком сильно =)
      • +1
        А, понятно! Я просто малость испугался незнакомого «circuit», а так становится действительно практически то же самое, только требуют, чтобы можно было реально вычислить за приемлемое время. Кажется, даже за полиномиальное, если я правильно понимаю определение 2.1.2 Compact Homomorphic Encryption.
        • 0
          абсолютно верно, нужно полиномиальное (даже с «ужасными константами» :)).
  • 0
    как считаете, будет такое где-то применяться на практике? где и как скоро?
    • 0
      если как концепт в принципе, то обязательно будет.

      если про именно эту реализацию, то только при условии скачка в технологии, т.к. пока слишком медленно.
  • +1
    Самое интересное, что налоговому инспектору как раз НАДО знать информацию о ваших доходах :) ну и деклАрация :)
    • 0
      упс, я неправильно нашел синоним такому понятию, как tax return.

      ну и проверочное слово declaration, Вы безусловно правы :)
      • 0
        >Представьте, что вы отсылаете зашифрованную вашим закрытым ключом декларацию и получаете также зашифрованный результат от налогового специалиста, который не узнал ни бита информации о ваших доходах.

        Да, мне тоже непонятно. Как специалист может анализировать данные, не расшифровывая их?
        И какого рода результат он отправит мне в этом случае?
        • 0
          если у него есть автоматизированный софт (например, как turbotax), то все делается без человека в цикле. Тоже самое можно сказать про «поиск» и т.д.
          • 0
            Ну так софт-то все равно расшифровывать будет, а это значит, что специалист, в принципе, тоже может прочитать открытый текст. Механизм с автоматизированным софтом был доступен и раньше, без гомоморфного шифрования. Или я чего-то недопонял?
            • +3
              если разрешите, то я приведу ну совсем дурацкий пример =)

              допустим, вам надо придать форму некоторой субстанции, но (1) у вас самого нет кузнеческих навыков, и (2) вы не хотите, чтобы кузнец узнал какой материал вы ему подсунули. Вот если вы сможете найти такой метал, который легко нанести на вашу субстанцию (и соскрести впоследствие), и который бы не мешал кузнецу, то можно считать, что этот метал гомоморфен для кузнеческого дела.

              Если у кого-то есть лучший пример, то буду рад услышать, т.к., знаю, что мой suck =)
              • +5
                Sucks, да :)

                Предположим, что некий умник владеет секретной формулой, которая по куче показателей из бизнес-плана позволяет вычислить предполагаемую прибыль. Гомоморфное шифрование позволяет мне взять мои текущие показатели, зашифровать, отправить ему, он выполнит на них свою функцию, вернет мне результат, который я смогу расшифровать и получить вычисленное значение прибыли.

                Но умник так и не узнает значений моих показателей — равно как и промежуточные результаты. Он даже не узнает получившуюся прибыль. Ее расшифрую только я.

                wiki: "..A cryptosystem which supports both addition and multiplication (thereby preserving the ring structure of the plaintexts) would be far more powerful. Using such a scheme, one could homomorphically evaluate any circuit, effectively allowing the construction of programs which may be run on encryptions of their inputs to produce an encryption of their output. Since such a program never decrypts its input, it could be run by an untrusted party without revealing its inputs and internal state. The existence of a fully homomorphic cryptosystem would have great practical implications in the outsourcing of private computations, for instance, in the context of cloud computing.."
                • 0
                  точно! для облачных вычислений самое оно!
                  • +1
                    Я ниже сбросил ссылку на Шнаера, который пока не верит в практичность этой схемы.
                    Ну, подождем-увидим :)
                    • 0
                      если «завтра» квантовый компьютер доделают другие светлые умы, то заработает.

                      я тоже со скептицизмом отношусь к данной реализации (в комментах до этого уже говорил), но сама идея просто крутая :)
                      • 0
                        Квантовый компьютер-то тут причем? У вас есть реализация квантово-гомоморфного шифрования?
            • 0
              Софт сможет выполнить операции над данными без их расшифровки.
              • 0
                Не пойму и я при чем налоговая? Ведь она не сервис, который преобразует мои данные, она их накапливает и анализирует «для себя».
        • 0
          а вообще, в этом и весь «срыв башки», что так просто и не укладывается, как такое возможно :)
  • +3
    Вот пример использования гомоморфного шифрования в системе электронных выборов. Очень интересно кстати.
    • 0
      отлично! огромное спасибо.
    • 0
      вернее не сам алгоритм использования, а просто сфера применения.
  • 0
    деклорации — не опечатка? как-то не так))
    • 0
      спасибо, исправил
  • 0
    Нет, круто конечно, но вот при чем тут налоговые декларации и гугл не очень понял.
    Здорово, я теперь смогу умножать и складывать зашифрованный текст, счастье-то какое! :)
    • 0
      Спасибо!

      Кому интересно, еще пара линков нашлась

      en.wikipedia.org/wiki/Homomorphic_encryption (раздел про «Fully»..)

      www.fields.utoronto.ca/audio/08-09/crypto/gentry/index.html (презентация автора)

      потому что если все так — ему надо ставить памятник, а не PhD давать! это обалденно.

      (пример с Гуглом не пройдет, кстати, ему нужны открытые слова, чтобы сделать запрос по базам — если мы про поисковик)
    • +1
      Комментарий про Гугл снимаю (пока читаю презентацию :)
      • 0
        просто пример с Гуглом был на объявлениях о его презентации, поэтому «зацепило».
  • +4
    Отзыв Брюса Шнайера: www.pgpru.com/biblioteka/statji/gomomorfnoeshifrovanie
    • +1
      ну автор это открыто признает и смущенно улыбался на вопросы о производительности.
  • +1
    «Главная проблема с предыдущими схемами была в том, что каждая операция добавляет некоторый «шум» в криптотекст»

    Что за чушь?! Все операции в RSA выполняются над числами, меньшими N, поэтому операция mod ничего не меняет (кроме того, что позволяет числам остаться внутри заданной области).

    Что это ещё за «шум», который мешает нам расшифровывать? Любая современная функция шифрования — однозначна и обратима на 100%, а значит никакого шума ни в одной современной функции шифрования нет. Если бы подобный шум был бы — однозначное шифрование было бы невозможно даже бы на первой итерации.
    • +1
      хех, прошу прощения, если вызвал негативные эмоции :)
      надо было более внмательно прочитать статью, а так пересказывал большей частью по памяти.

      в действительности, несколько запутался со всеми схемами, но в целом все же передал суть верно: я же не написал, что RSA «добавляет шум». В lattice encryption системе операция «суммирования» накапливает ошибку (вам не нравится термин «шум»?) и после определенного количества шагов делает невозможным декриптование. Накопленная ошибка также связана с операцией mod, поэтому почему-то в голове отложилось, что RSA тоже тут причастна.

      >> Любая современная функция шифрования — однозначна и обратима на 100%, а значит никакого шума
      >> ни в одной современной функции шифрования нет. Если бы подобный шум был бы — однозначное
      >> шифрование было бы невозможно даже бы на первой итерации.

      Так с этим никто и не спорит, речь идет об операциях (AND, XOR) над зашифрованными данными. О каких «итерациях» в современных функциях шифрования вы говорите?
      • 0
        «после определенного количества шагов делает невозможным декриптование»
        Если всё делать руками, то дешифрование возможно. Нужно только помнить, что исходный кодовой вектор нужно искать на каждой итерации. Разумеется, если вы попытаетесь одним шагом исправить ошибку, вызванную двумя и более операциями — скорее всего ничего не выйдет.

        «О каких «итерациях» в современных функциях шифрования вы говорите?»
        Я имел ввиду повторное применение операции шифрования к тексту. (Я надеюсь, вы не имеете ввиду итерации в смысле DES/AES, которые тоже однозначны)
  • 0
    Если я правильно понимаю, то отослав налоговику зашифрованный отчёт и получив ответ при расшифровке применит для исходных данных те же функции, которые применялись к зашифрованным:

    То есть у меня есть 100 «денег» дохода, я шифрую и получаю 350. Налоговая получает 350 и высчитывает, что я из этой суммы должен заплатить 5% от прибыли и 17.5 денег фиксированной ставки, то есть 35 денег. Я получаю 35, высчитывается действие получения из 350 35, то есть умножение на 0.1. Исходная сумма умножается на 0.1 и получается, что я должен заплатит 10 денег налога. Таким образом ни налоговая не знает какой у меня доход, ни я не знаю всех формул и процесса (только что результат всех их действий равен умножению на 0.1)

    Я всё правильно сделал? Ведь 5% от 100 + 17.5 не равно 10% от 100…
    • +1
      не все. Операция умножения, использованая вами в качестве примера оператора шифрования, не гомогенна по отношению к сложению.
      • 0
        А можно тогда правильный пример работы «криптосистемы гомоморфной для операций умножения и суммирования одновременно»?
        • +1
          «Крэйг Гэнтри (Craig Gentry, PhD Stanford, IBM Research) опубликовал пример первой такой функции в своей PhD диссертации.»
          • –2
            Петросян на моих Хабрах?
            • +2
              Сарказм неуместен. Если б это было так просто — им бы все уже давно пользовались.
              • 0
                Если вы всё таки не поняли, то я не просил привести мне пример функции, а теоретический пример работы такой функции. То есть если вы говорите, что «Операция умножения, использованая вами в качестве примера оператора шифрования, не гомогенна по отношению к сложению», то будьте любезны объяснить почему и дать правильный пример.

                Я, как бы, и сам знаю что то, что я написал в качестве примера не верно, так как ответы не сошлись. Возможно правильно было написать, что обратно возвращается не 35, а f(350)+с или как то в этом духе? Но тогда получается, что при малом количестве операции (в данном случае 2) получатель (владелец исходных данных) сможет восстановить процесс (то есть 5% + 17.5) и промежуточные данные/результаты. Мне не важно как, мне интересно что — для интуитивного восприятия, а не технической реализации.
                • 0
                  насколько понял лично я — идея состоит в произведении некоей операции над зашифрованной сообщением, в результате чего оригинальное сообщение изменяется предсказанным образом. Пускай у нас есть:

                  исходное сообщение — число М
                  ключ K
                  Алгоритм шифрования E(M, K)=M'
                  Алгоритм дешифрования D(M', K)=M

                  Задача — найти такие функции f1 и f2 независимые от K, что для любых a и b:
                  D(f1(M', a), K) = a * M
                  и
                  D(f2(M', b), K) = M + b,

                  Тогда, оперируя f1 и f2 мы сможем проделывать любые (математические)операции над исходными данными.

                  Относительности возможности провести реверс инжиниринг подобных превращений — вопрос, а зачем? Например запросы к защищенной базе данных. Вам действительно интересно знать каким образом она их исполняет? Давайте отбросим шифрование, вы отправляете х, получаете f(x). Вопрос, достаточно ли этого чтобы узнать f, если вы понятия не имеете о ее природе? Да, если f вида a*x+b, нам хватит трех-четырех пар x-f(x) для того чтобы понять что функция похожа на линейную, независимо от использования каких-либо алгоритмов. Если же преобразования сложнее (а любую функцию можно загнать в ряд Тейлора), шансов у вас мало. Но насколько я понял — основная цель вообще не в том чтобы защитить алгоритм обработки. Задача в том, чтобы провести его где-угодно не опасаясь за сохранность данных.
                  • 0
                    У палки всегда два конца. Мне как пользователю желательно, чтоб мои данные были скрыты от чужих глаз. Мне как разработчику желательно, чтоб мои разработки и алгоритмы были скрыты от чужих глаз. Хотя даже одно из двух уже прорыв вперёд.
                    • 0
                      Все равно не могу понять, каким образом работа над пользовательскими данными открывает ваш алгоритм, если он сложнее a*x+b?
                      • 0
                        Глупый вопрос, a и b, конечно. В большинстве случаев сама функция известна, а вот параметры и коэффициенты — это и есть «know how». Допустим обучение нейронной сети — это и есть подбор коэффициента. Промежуточный результат и пара намёков на действие — всё что надо для начала игры с параметрами и воссоздания алгоритма. Особенно это актуально для revers engineering какого-нибудь алгоритма data mining аля Google…
  • НЛО прилетело и опубликовало эту надпись здесь
  • 0
    > «суммы и умножения хватит, чтобы выразить любую математическую функцию»

    Это не правда.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.