Comments 58
тем кому не лень минусовать карму >> пожалуйста, учтите, что не все понятия, содержащие корень «гомо» — враждебны :) хехе
Хотелось бы упомянуть интересный факт из биографии Крэйга. Он получил бакалавра математики в университете Дьюка, потом закончил юридическую школу Гарварда, а потом решил, что для полного счастья ему не хватает PhD в computer science! Решение проблемы, описанной в статье, он нашел будучи на стажировке в IBM Research.
Ничего не понял, но ваш энтузиазм по поводу сабжа меня радует )
простите, видимо слабо мотивировал проблему =) или вы не поняли решение?
если мотивация, то смысл в том, что можно производить осознанные действия над зашифрованным текстом без знания, что за этим текстом скрывается.
Если же вы про решение, то там алгебра (группы, кольца). Мне перчаток и коробок хватило =)
если мотивация, то смысл в том, что можно производить осознанные действия над зашифрованным текстом без знания, что за этим текстом скрывается.
Если же вы про решение, то там алгебра (группы, кольца). Мне перчаток и коробок хватило =)
Да не в том дело.
Вот я, например, в курсе существования групп и колец. Но из текста не понял, зачем нам производить действия над зашифрованным текстом. (RSA позволяет умножение текста! Круто! Но зачем?)
Кроме того, вот это, например: «позволяет совершать некоторые математические действия с открытым текстом путем произведения операций с зашифрованным» я и вовсе не понял. У нас есть открытый текст и есть зашифрованный. Мы что-то делаем над одним, но гомоморфность операции позволяет сделать это и над другим…
Короче, пока картинку не рассмотрел, не понял ничего. 8)
Вот я, например, в курсе существования групп и колец. Но из текста не понял, зачем нам производить действия над зашифрованным текстом. (RSA позволяет умножение текста! Круто! Но зачем?)
Кроме того, вот это, например: «позволяет совершать некоторые математические действия с открытым текстом путем произведения операций с зашифрованным» я и вовсе не понял. У нас есть открытый текст и есть зашифрованный. Мы что-то делаем над одним, но гомоморфность операции позволяет сделать это и над другим…
Короче, пока картинку не рассмотрел, не понял ничего. 8)
Читал в первый раз в Opera Mini с выключенными картинками, сейчас уже яснее стало :)
> криптосистемы гомоморфной для операций умножения и суммирования одновременно, так называемого полностью гомоморфного шифрования (fully homomorphic encryption)
Смотрим страницы 5 и 28, там другое определение. То, что Вы говорите, это обычный кольцевой гомоморфизм, а что касается fully homomorphic encryption, там появляются слова типа compactly evaluates.
Не могу сказать, насколько сильно различие, потому как много специфичных для данной области терминов. Тут требуется специалист.
Смотрим страницы 5 и 28, там другое определение. То, что Вы говорите, это обычный кольцевой гомоморфизм, а что касается fully homomorphic encryption, там появляются слова типа compactly evaluates.
Не могу сказать, насколько сильно различие, потому как много специфичных для данной области терминов. Тут требуется специалист.
вы правы, что это не самое точное определение.
Определение с 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 по поводу «осуществимости» построения такой схемы.
Но все же смысл, думаю, исказил не слишком сильно =)
Определение с 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 по поводу «осуществимости» построения такой схемы.
Но все же смысл, думаю, исказил не слишком сильно =)
как считаете, будет такое где-то применяться на практике? где и как скоро?
Самое интересное, что налоговому инспектору как раз НАДО знать информацию о ваших доходах :) ну и деклАрация :)
упс, я неправильно нашел синоним такому понятию, как tax return.
ну и проверочное слово declaration, Вы безусловно правы :)
ну и проверочное слово declaration, Вы безусловно правы :)
>Представьте, что вы отсылаете зашифрованную вашим закрытым ключом декларацию и получаете также зашифрованный результат от налогового специалиста, который не узнал ни бита информации о ваших доходах.
Да, мне тоже непонятно. Как специалист может анализировать данные, не расшифровывая их?
И какого рода результат он отправит мне в этом случае?
Да, мне тоже непонятно. Как специалист может анализировать данные, не расшифровывая их?
И какого рода результат он отправит мне в этом случае?
если у него есть автоматизированный софт (например, как turbotax), то все делается без человека в цикле. Тоже самое можно сказать про «поиск» и т.д.
Ну так софт-то все равно расшифровывать будет, а это значит, что специалист, в принципе, тоже может прочитать открытый текст. Механизм с автоматизированным софтом был доступен и раньше, без гомоморфного шифрования. Или я чего-то недопонял?
если разрешите, то я приведу ну совсем дурацкий пример =)
допустим, вам надо придать форму некоторой субстанции, но (1) у вас самого нет кузнеческих навыков, и (2) вы не хотите, чтобы кузнец узнал какой материал вы ему подсунули. Вот если вы сможете найти такой метал, который легко нанести на вашу субстанцию (и соскрести впоследствие), и который бы не мешал кузнецу, то можно считать, что этот метал гомоморфен для кузнеческого дела.
Если у кого-то есть лучший пример, то буду рад услышать, т.к., знаю, что мой suck =)
допустим, вам надо придать форму некоторой субстанции, но (1) у вас самого нет кузнеческих навыков, и (2) вы не хотите, чтобы кузнец узнал какой материал вы ему подсунули. Вот если вы сможете найти такой метал, который легко нанести на вашу субстанцию (и соскрести впоследствие), и который бы не мешал кузнецу, то можно считать, что этот метал гомоморфен для кузнеческого дела.
Если у кого-то есть лучший пример, то буду рад услышать, т.к., знаю, что мой suck =)
UFO just landed and posted this here
а вообще, в этом и весь «срыв башки», что так просто и не укладывается, как такое возможно :)
Вот пример использования гомоморфного шифрования в системе электронных выборов. Очень интересно кстати.
деклорации — не опечатка? как-то не так))
Нет, круто конечно, но вот при чем тут налоговые декларации и гугл не очень понял.
Здорово, я теперь смогу умножать и складывать зашифрованный текст, счастье-то какое! :)
Здорово, я теперь смогу умножать и складывать зашифрованный текст, счастье-то какое! :)
UFO just landed and posted this here
«Главная проблема с предыдущими схемами была в том, что каждая операция добавляет некоторый «шум» в криптотекст»
Что за чушь?! Все операции в RSA выполняются над числами, меньшими N, поэтому операция mod ничего не меняет (кроме того, что позволяет числам остаться внутри заданной области).
Что это ещё за «шум», который мешает нам расшифровывать? Любая современная функция шифрования — однозначна и обратима на 100%, а значит никакого шума ни в одной современной функции шифрования нет. Если бы подобный шум был бы — однозначное шифрование было бы невозможно даже бы на первой итерации.
Что за чушь?! Все операции в RSA выполняются над числами, меньшими N, поэтому операция mod ничего не меняет (кроме того, что позволяет числам остаться внутри заданной области).
Что это ещё за «шум», который мешает нам расшифровывать? Любая современная функция шифрования — однозначна и обратима на 100%, а значит никакого шума ни в одной современной функции шифрования нет. Если бы подобный шум был бы — однозначное шифрование было бы невозможно даже бы на первой итерации.
хех, прошу прощения, если вызвал негативные эмоции :)
надо было более внмательно прочитать статью, а так пересказывал большей частью по памяти.
в действительности, несколько запутался со всеми схемами, но в целом все же передал суть верно: я же не написал, что RSA «добавляет шум». В lattice encryption системе операция «суммирования» накапливает ошибку (вам не нравится термин «шум»?) и после определенного количества шагов делает невозможным декриптование. Накопленная ошибка также связана с операцией mod, поэтому почему-то в голове отложилось, что RSA тоже тут причастна.
>> Любая современная функция шифрования — однозначна и обратима на 100%, а значит никакого шума
>> ни в одной современной функции шифрования нет. Если бы подобный шум был бы — однозначное
>> шифрование было бы невозможно даже бы на первой итерации.
Так с этим никто и не спорит, речь идет об операциях (AND, XOR) над зашифрованными данными. О каких «итерациях» в современных функциях шифрования вы говорите?
надо было более внмательно прочитать статью, а так пересказывал большей частью по памяти.
в действительности, несколько запутался со всеми схемами, но в целом все же передал суть верно: я же не написал, что RSA «добавляет шум». В lattice encryption системе операция «суммирования» накапливает ошибку (вам не нравится термин «шум»?) и после определенного количества шагов делает невозможным декриптование. Накопленная ошибка также связана с операцией mod, поэтому почему-то в голове отложилось, что RSA тоже тут причастна.
>> Любая современная функция шифрования — однозначна и обратима на 100%, а значит никакого шума
>> ни в одной современной функции шифрования нет. Если бы подобный шум был бы — однозначное
>> шифрование было бы невозможно даже бы на первой итерации.
Так с этим никто и не спорит, речь идет об операциях (AND, XOR) над зашифрованными данными. О каких «итерациях» в современных функциях шифрования вы говорите?
«после определенного количества шагов делает невозможным декриптование»
Если всё делать руками, то дешифрование возможно. Нужно только помнить, что исходный кодовой вектор нужно искать на каждой итерации. Разумеется, если вы попытаетесь одним шагом исправить ошибку, вызванную двумя и более операциями — скорее всего ничего не выйдет.
«О каких «итерациях» в современных функциях шифрования вы говорите?»
Я имел ввиду повторное применение операции шифрования к тексту. (Я надеюсь, вы не имеете ввиду итерации в смысле DES/AES, которые тоже однозначны)
Если всё делать руками, то дешифрование возможно. Нужно только помнить, что исходный кодовой вектор нужно искать на каждой итерации. Разумеется, если вы попытаетесь одним шагом исправить ошибку, вызванную двумя и более операциями — скорее всего ничего не выйдет.
«О каких «итерациях» в современных функциях шифрования вы говорите?»
Я имел ввиду повторное применение операции шифрования к тексту. (Я надеюсь, вы не имеете ввиду итерации в смысле DES/AES, которые тоже однозначны)
Если я правильно понимаю, то отослав налоговику зашифрованный отчёт и получив ответ при расшифровке применит для исходных данных те же функции, которые применялись к зашифрованным:
То есть у меня есть 100 «денег» дохода, я шифрую и получаю 350. Налоговая получает 350 и высчитывает, что я из этой суммы должен заплатить 5% от прибыли и 17.5 денег фиксированной ставки, то есть 35 денег. Я получаю 35, высчитывается действие получения из 350 35, то есть умножение на 0.1. Исходная сумма умножается на 0.1 и получается, что я должен заплатит 10 денег налога. Таким образом ни налоговая не знает какой у меня доход, ни я не знаю всех формул и процесса (только что результат всех их действий равен умножению на 0.1)
Я всё правильно сделал? Ведь 5% от 100 + 17.5 не равно 10% от 100…
То есть у меня есть 100 «денег» дохода, я шифрую и получаю 350. Налоговая получает 350 и высчитывает, что я из этой суммы должен заплатить 5% от прибыли и 17.5 денег фиксированной ставки, то есть 35 денег. Я получаю 35, высчитывается действие получения из 350 35, то есть умножение на 0.1. Исходная сумма умножается на 0.1 и получается, что я должен заплатит 10 денег налога. Таким образом ни налоговая не знает какой у меня доход, ни я не знаю всех формул и процесса (только что результат всех их действий равен умножению на 0.1)
Я всё правильно сделал? Ведь 5% от 100 + 17.5 не равно 10% от 100…
не все. Операция умножения, использованая вами в качестве примера оператора шифрования, не гомогенна по отношению к сложению.
А можно тогда правильный пример работы «криптосистемы гомоморфной для операций умножения и суммирования одновременно»?
«Крэйг Гэнтри (Craig Gentry, PhD Stanford, IBM Research) опубликовал пример первой такой функции в своей PhD диссертации.»
Петросян на моих Хабрах?
Сарказм неуместен. Если б это было так просто — им бы все уже давно пользовались.
Если вы всё таки не поняли, то я не просил привести мне пример функции, а теоретический пример работы такой функции. То есть если вы говорите, что «Операция умножения, использованая вами в качестве примера оператора шифрования, не гомогенна по отношению к сложению», то будьте любезны объяснить почему и дать правильный пример.
Я, как бы, и сам знаю что то, что я написал в качестве примера не верно, так как ответы не сошлись. Возможно правильно было написать, что обратно возвращается не 35, а f(350)+с или как то в этом духе? Но тогда получается, что при малом количестве операции (в данном случае 2) получатель (владелец исходных данных) сможет восстановить процесс (то есть 5% + 17.5) и промежуточные данные/результаты. Мне не важно как, мне интересно что — для интуитивного восприятия, а не технической реализации.
Я, как бы, и сам знаю что то, что я написал в качестве примера не верно, так как ответы не сошлись. Возможно правильно было написать, что обратно возвращается не 35, а f(350)+с или как то в этом духе? Но тогда получается, что при малом количестве операции (в данном случае 2) получатель (владелец исходных данных) сможет восстановить процесс (то есть 5% + 17.5) и промежуточные данные/результаты. Мне не важно как, мне интересно что — для интуитивного восприятия, а не технической реализации.
насколько понял лично я — идея состоит в произведении некоей операции над зашифрованной сообщением, в результате чего оригинальное сообщение изменяется предсказанным образом. Пускай у нас есть:
исходное сообщение — число М
ключ 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) для того чтобы понять что функция похожа на линейную, независимо от использования каких-либо алгоритмов. Если же преобразования сложнее (а любую функцию можно загнать в ряд Тейлора), шансов у вас мало. Но насколько я понял — основная цель вообще не в том чтобы защитить алгоритм обработки. Задача в том, чтобы провести его где-угодно не опасаясь за сохранность данных.
исходное сообщение — число М
ключ 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) для того чтобы понять что функция похожа на линейную, независимо от использования каких-либо алгоритмов. Если же преобразования сложнее (а любую функцию можно загнать в ряд Тейлора), шансов у вас мало. Но насколько я понял — основная цель вообще не в том чтобы защитить алгоритм обработки. Задача в том, чтобы провести его где-угодно не опасаясь за сохранность данных.
У палки всегда два конца. Мне как пользователю желательно, чтоб мои данные были скрыты от чужих глаз. Мне как разработчику желательно, чтоб мои разработки и алгоритмы были скрыты от чужих глаз. Хотя даже одно из двух уже прорыв вперёд.
Все равно не могу понять, каким образом работа над пользовательскими данными открывает ваш алгоритм, если он сложнее a*x+b?
Глупый вопрос, a и b, конечно. В большинстве случаев сама функция известна, а вот параметры и коэффициенты — это и есть «know how». Допустим обучение нейронной сети — это и есть подбор коэффициента. Промежуточный результат и пара намёков на действие — всё что надо для начала игры с параметрами и воссоздания алгоритма. Особенно это актуально для revers engineering какого-нибудь алгоритма data mining аля Google…
UFO just landed and posted this here
> «суммы и умножения хватит, чтобы выразить любую математическую функцию»
Это не правда.
Это не правда.
Sign up to leave a comment.
Гомоморфное шифрование/ (Fully) Homomorphic Encryption