Да, вы очень хорошо сформулировали суть — это удобная абстракция. Схемы для этой обфускации еще более медленные, к сожалению, чем даже для Fully Homomorphic Encryption. Так что пока эта тема представляет только теоретический интерес. Конкретная схема обфускации есть, но она основана на нестандартном предположении (nonstandart assumption), т.е. это не хорошо всеми изученные RSA assumption или discrete log, а новое предположение, которое не очень понятно, как анализировать, потому что оно очень громоздко…
iO решила, например, deniable encryption. Это задача очень долго в теории была открытой. Приложение этого шифрования очень привлекательно: допустим, вас поймали мошенники и хотят, чтобы бы вы предоставить им свои секретные ключи, чтобы они могли расшифровать всю вашу переписку. Если вы пользовались не обычной схемой шифрования, а deniable encryption, вы можете создать фальшивый секретный ключ, который будет неотличим от настоящего, но при этом расшифрует все ваши сообщения во что-нибудь другое что вы подготовите заранее, такой же длины.
iO дает асимптотически самые короткие электронные подписи. Т.е. теоретически довольно долго искали подписи, которые так сложно подделать, как просто напросто угадать все биты подписи. Раньше если мы хотели, чтобы атакующий делал не более 2^λ операций, длины подписи должна была быть 2λ бит — то есть в два раза больше, чем теоретически возможно. А iO дает подписи оптимальной длины — λ.
iO дает возможность n > 2 пользователям согласовать общий ключ, без помощи какой-либо централизованной системы (NIKE — non-interactive key exchange). Каждый пользователь пишет что-то на «доску», после того, как все что-то написали, все пользователи считывают все значения с доски и после произведения некоторых операций, все они должны получить общий ключ, который не будет известен никому, кто ничего не писал на доску.
Есть еще много задач, которые решила iO и которые пока не решены без нее.
Я говорю о сведении задачи построения Witness Encryption к задачи построения indistinguishability Obfuscation. Это теоретический результат. Секретный выполняющий набор может нигде не хранится, его может не знать человек, который шифрует. Но человек, который хочет расшифровать сообщение должен найти этот выполняющий набор. Это просто очень на мой взгляд интересная своего рода связь теории сложности с криптографией.
> Нет. Все знают алгоритм AES. Конечный пользователь знает секретный ключ. Единственное ограничение — третьи лица не знают секретный ключ.
Security by obscurity в отношении к алгоритму — это не имение математического доказательства его устойчивости. AES такого не имеет, AES показывает устойчивость к статистическим тестам и существующим атакам, но никто не гарантирует, что хорошую атаку невозможно или очень сложно найти в принципе.
> Это называется «DRM» и эта идея неполноценна в корне.
DRM — это собирательный термин. Что именно вы считаете «неполноценным в корне»?
Теория доказывает, что приведенный выше мной пример полностью устойчив, т.е. получить доступ к скрытой функциональности, если вы используете обфускацию неразличимости, невозможно.
«Авторские права на все виды программ для ЭВМ (в том числе на операционные системы и программные комплексы), которые могут быть выражены на любом языке и в любой форме, включая исходный текст и объектный код, охраняются так же, как авторские права на произведения литературы.» Статья 1261 Гражданского Кодекса РФ
«Правообладатель в течение срока действия исключительного права на программу для ЭВМ или на базу данных может по своему желанию зарегистрировать такую программу или такую базу данных в федеральном органе исполнительной власти по интеллектуальной собственности.» Статья 1262 Гражданского Кодекса РФ
О, знаете что iO делает… она делает вот какую прикольную штуку: называется Witness Encryption (WE). В WE вы шифруете свое сообщение для, например, SAT формулы и только тот может его расшифровать, кто знает выполняющий набор к этой формуле! (вместо SAT может быть любая другая NP полная задача). Но вам для шифрования необязательно знать выполняющий набор.
Давайте я приведу пример, может быть это многое прояснит (он из одного из предыдущих комментариев):
Вы написали мощную программу — Photoshop Ultimate Edition, но есть пользователь, который хочет минимум функциональности от Photoshop, он хочет делать простейшую обработку своих фотографий, он не хочет платить 700$. Для него вы хотите выпустить Photoshop Light Edition за 300$. Чтобы это сделать сегодня, вам надо удалить всю ненужную функциональность и пересобрать весь проект (это первый вариант программы — P1). Если вы хотите сделать Photoshop Web Edition, вам опять же надо сделать то же самое. Но вместо этого вы можете в начале программы задать права доступа (permissions), закодировать их прямо в код и в самом коде вы будете проверять, если у пользователя есть необходимые права, ему будет доступна та или иная опция, если нет, то нет (это второй вариант программы — P2). Функциональности — идентичны, поэтому обфускация неразличимости второго варианта будет неотличима от обфускации неразличимости первого варианта, и вы не сможете получить доступ к скрытой от вас функциональности, ее как будто в коде нет! Второй вариант, однако, гораздо проще и легче в реализации и породит гораздо меньше ошибок.
> Нет. В криптрографии не занимаются security through obscurity.
Шифр AES — это ни что иное как security by obscurity и этот шифр ваш браузер использует каждый день. Кроме того весь ваш трафик шифруется исключительно AES, «настоящие» криптографические примитивы (RSA или Diffie-Hellman) используются только для того, чтобы установить общий для двух сторон ключ для AES.
> В реальном мире не бывает двух программ с абсолютно идентичной функциональностью
Но вы же сами говорите, что есть программы, которые дают «головную боль тому, кто пытается» разобраться с ними, а есть хорошо написанные программы, с которыми легко разбираться. Вот это и есть пример двух программ с идентичной функциональностью.
Я не утверждаю, что этот обфускатор решит все проблемы, что интересно про этот обфускатор, это, во-первых, на нем можно построить криптографию, а, во-вторых, этот обфускатор раскрывает доказуемо минимум «информации» о программе.
Давайте я лучше приведу пример: вы написали мощную программу — Photoshop Ultimate edition, но есть пользователь, который хочет минимум функциональности от Photoshop, он хочет делать простейшую обработку своих фотографий, он не хочет платить 700$. Для него вы хотите выпустить Photoshop Light за 300$. Чтобы это сделать сегодня, вам надо удалить всю ненужную функциональность и пересобрать весь проект (это первый вариант программы — P1). Если вы хотите сделать Photoshop Web edition, вам опять же надо сделать то же самое. Но вместо этого вы можете в начале программы задать права доступа (permissions), закодировать их прямо в код (hardcore them into the code) и в самом коде вы будете проверять, если у пользователя есть необходимые права, ему будет доступна та или иная опция, если нет, то нет (это второй вариант программы — P2). Функциональности — идентичны (но второй вариант гораздо проще и легче в реализации). Поэтому обфускация неразличимости второго варианта будет неотличима от обфускации неразличимости первого варианта и вы не сможете получить доступ к скрытой от вас функциональности, ее как будто в коде нет!
Обфускацию черного ящика построить нельзя. Обфускация Неразличимости это лучшее, что теоретически возможно воплотить в жизнь на сегодняшний день. Кроме того, из существования ее вытекает существование многих других важных криптографических примитивов. Что бы вы хотели еще о ней узнать? Как она строится? На это не хватит страницы текста и без формул тут не обойтись. Как она строится не так важно, потому что существующая конструкция лишь кандидат, она очень неэффективна. Если вас интересует только практические, а не теоретические аспекты, то надо подождать появления лучших схем прежде чем разбираться.
Да, не в один тык, разумеется, гомоморфное шифрование изменит то, как работает гугл, тем более что размеры его баз данных огромны, а алгоритмы очень трудоемки.
Но самый простой метод делать поиск с ГШ это написать функцию поиска, которая будет просматривать всю базу данных. Это можно сделать арифметическим преобразованием: это можно сделать с помощью NAND операций (что и делают транзисторы в любом компьютере), а NAND(x,y) = 1-xy. Но, естественно, просматривать всю базу данных никто не будет для одного запроса, для этого потребуются оптимизации: может быть агрегация запросов многих пользователей, методами Oblivious RAM или Multi-Party-Computations. Но пока это от нас далеко. Поиск по какой-нибудь небольшой базе, например, сотрудников компании, вполне осуществим простым методом просмотра всей базы.
Шифрование вероятностное (шифрующий алгоритм пользуется случайными числами), поэтому зашифровав символ «a» -> λ1 два раза вы получите две разных матрицы.
Грубо говоря, для одного раза это будет матрица A, такая что Av=λ1v + e1 (где e1 это один маленький вектор), а во второй раз, шифром будет матрица B, такая что Bv=λ1v + e2 (где e2 это ДРУГОЙ маленький вектор). Но имея эти A и B (и не имея вектора v) вы не сможете понять даже, шифруют ли эти две матрицы один и тот же символ (или одно и то же «примерное» собственное число) или нет.
Гугл не знает, какие результаты возвращаются, поскольку они возвращаются в зашифрованном виде.
Я посылаю: pk, Enc(pk, «query»), Гугл вычисляет Enc(pk, search(«query»)) — вычисляет алгоритм «search» на моих данных (на «query») и посылает мне результат обратно. Посколько я знаю sk, я могу дешифровать:
Dec(sk, Enc(pk, search(«query»))) -> search(«query») и узнать результаты поиска.
Нет-нет. Алгоритм ищет слово «спам», но он не получает ответ в чистом виде — только вы можете расшифровать ответ алгоритма. Т.е. вам придут все ваши письма, после фильтра на спам, вы их дешифруете и узнаете (на стороне клиента), какие письма были помечены как спам, а какие нет. И ваш почтовый клиент может их уже локально отсортировать. Бонус в том, что вам не надо будет исполнять потенциально сложный алгоритм проверки на спам самому.
Очень хороший вопрос! Допустим, есть алгоритм/программа, она ищет в тексте слово «реклама» (простой поиск подстроки). Этот алгоритм можно представить в виде набора бинарных операций (используя «или» и «и») или даже с помощью одной операции NAND (Штрих Шеффера), «не и» (то, что собственно вычисляет каждый транзистор). Это будет называется представлением алгоритма в виде булевой схемы.
Этот NAND(x, y) в свою очередь можно представить как набор арифметических операций: NAND(x, y) = (1 — xy) (если входы бинарны — выход будет бинарным), эти операции может делать гомоморфная схема — это просто вычитание и умножение. Т.е. весь алгоритм поиска подстроки можно осуществить гомоморфными операциями.
Но все не совсем так просто: вы, наверное, подумали, «а что же делать с циклами и ветвлениями (if/else)? Ведь если переводить это в лоб, то надо будет раскрывать/линеаризировать эти циклы и ветвления.» На этот счет есть ряд потрясающих результатов, которые говорят что это можно очень эффективно сделать, спровоцировав увеличение длины программы только в логарифмическое число раз. Т.е. была программа длины n, а стала схема размера n log n. (Число атомов во вселенной 2^300, а поэтому логарифм можно считать константой… это шутка :) )
Статьи по ГШ обычно публикуются (по крайней мере на конференциях), тем более у этой статьи только 8 сомнительных цитирований, а у статьи на которую дана ссылка в посте — 83. И статьи по ГШ обычно публикуются на архиве eprint.iacr.org.
Но это ничего не значит, возможно, авторы действительно просто поленились :) Хотя статью написать это бОльшая часть дела, так что уж грех не послать ее хоть куда-то.
Да, совершенно верно, очень хорошее наблюдение! Именно поэтому эта простая идея работает для конечного числа перемножений. А чтобы добиться произвольного числа перемножений надо делать то что называется «bootstrapping», т.е. зашифровать секретный ключ гомоморфной схемой (предполагая «circular security», т.е. что можно зашифровать секретный ключ его публичным ключом и что это его не выдаст) и исполнить дешифрующий алгоритм используя гомоморфное шифрование. Это перешифрует информацию, уменьшив в ней шум до размеров исходного.
Выглядеть это будет так примерно:
Гомоморфное шифрование позволяет сделать преобразование: E(pk, x) -> E(pk, f(x))
Boostrapping, соответственно, будет выглядеть так: допустим у вас есть шифр ct, в котором вы хотите уменьшить шум, допустим ct шифрует y, тогда
[ct, Enc(pk, sk)] => Enc(pk, Dec(sk, ct)) ct воспринимается как константа или набор констант, т.е. гомоморфная функция, которую мы считаем параметризована ct: f_{ct}(sk) = Dec(sk, ct). Перешифровка уменьшит шум.
Но эта статья не опубликована ни в каком авторитетном источнике (на сколько я понимаю), а это скорее всего означает, что она имеет какие-то проблемы с правильностью доказательств или результатов.
iO решила, например, deniable encryption. Это задача очень долго в теории была открытой. Приложение этого шифрования очень привлекательно: допустим, вас поймали мошенники и хотят, чтобы бы вы предоставить им свои секретные ключи, чтобы они могли расшифровать всю вашу переписку. Если вы пользовались не обычной схемой шифрования, а deniable encryption, вы можете создать фальшивый секретный ключ, который будет неотличим от настоящего, но при этом расшифрует все ваши сообщения во что-нибудь другое что вы подготовите заранее, такой же длины.
iO дает асимптотически самые короткие электронные подписи. Т.е. теоретически довольно долго искали подписи, которые так сложно подделать, как просто напросто угадать все биты подписи. Раньше если мы хотели, чтобы атакующий делал не более 2^λ операций, длины подписи должна была быть 2λ бит — то есть в два раза больше, чем теоретически возможно. А iO дает подписи оптимальной длины — λ.
iO дает возможность n > 2 пользователям согласовать общий ключ, без помощи какой-либо централизованной системы (NIKE — non-interactive key exchange). Каждый пользователь пишет что-то на «доску», после того, как все что-то написали, все пользователи считывают все значения с доски и после произведения некоторых операций, все они должны получить общий ключ, который не будет известен никому, кто ничего не писал на доску.
Есть еще много задач, которые решила iO и которые пока не решены без нее.
Security by obscurity в отношении к алгоритму — это не имение математического доказательства его устойчивости. AES такого не имеет, AES показывает устойчивость к статистическим тестам и существующим атакам, но никто не гарантирует, что хорошую атаку невозможно или очень сложно найти в принципе.
> Это называется «DRM» и эта идея неполноценна в корне.
DRM — это собирательный термин. Что именно вы считаете «неполноценным в корне»?
Теория доказывает, что приведенный выше мной пример полностью устойчив, т.е. получить доступ к скрытой функциональности, если вы используете обфускацию неразличимости, невозможно.
«Правообладатель в течение срока действия исключительного права на программу для ЭВМ или на базу данных может по своему желанию зарегистрировать такую программу или такую базу данных в федеральном органе исполнительной власти по интеллектуальной собственности.» Статья 1262 Гражданского Кодекса РФ
Вы написали мощную программу — Photoshop Ultimate Edition, но есть пользователь, который хочет минимум функциональности от Photoshop, он хочет делать простейшую обработку своих фотографий, он не хочет платить 700$. Для него вы хотите выпустить Photoshop Light Edition за 300$. Чтобы это сделать сегодня, вам надо удалить всю ненужную функциональность и пересобрать весь проект (это первый вариант программы — P1). Если вы хотите сделать Photoshop Web Edition, вам опять же надо сделать то же самое. Но вместо этого вы можете в начале программы задать права доступа (permissions), закодировать их прямо в код и в самом коде вы будете проверять, если у пользователя есть необходимые права, ему будет доступна та или иная опция, если нет, то нет (это второй вариант программы — P2). Функциональности — идентичны, поэтому обфускация неразличимости второго варианта будет неотличима от обфускации неразличимости первого варианта, и вы не сможете получить доступ к скрытой от вас функциональности, ее как будто в коде нет! Второй вариант, однако, гораздо проще и легче в реализации и породит гораздо меньше ошибок.
Шифр AES — это ни что иное как security by obscurity и этот шифр ваш браузер использует каждый день. Кроме того весь ваш трафик шифруется исключительно AES, «настоящие» криптографические примитивы (RSA или Diffie-Hellman) используются только для того, чтобы установить общий для двух сторон ключ для AES.
> В реальном мире не бывает двух программ с абсолютно идентичной функциональностью
Но вы же сами говорите, что есть программы, которые дают «головную боль тому, кто пытается» разобраться с ними, а есть хорошо написанные программы, с которыми легко разбираться. Вот это и есть пример двух программ с идентичной функциональностью.
Я не утверждаю, что этот обфускатор решит все проблемы, что интересно про этот обфускатор, это, во-первых, на нем можно построить криптографию, а, во-вторых, этот обфускатор раскрывает доказуемо минимум «информации» о программе.
Давайте я лучше приведу пример: вы написали мощную программу — Photoshop Ultimate edition, но есть пользователь, который хочет минимум функциональности от Photoshop, он хочет делать простейшую обработку своих фотографий, он не хочет платить 700$. Для него вы хотите выпустить Photoshop Light за 300$. Чтобы это сделать сегодня, вам надо удалить всю ненужную функциональность и пересобрать весь проект (это первый вариант программы — P1). Если вы хотите сделать Photoshop Web edition, вам опять же надо сделать то же самое. Но вместо этого вы можете в начале программы задать права доступа (permissions), закодировать их прямо в код (hardcore them into the code) и в самом коде вы будете проверять, если у пользователя есть необходимые права, ему будет доступна та или иная опция, если нет, то нет (это второй вариант программы — P2). Функциональности — идентичны (но второй вариант гораздо проще и легче в реализации). Поэтому обфускация неразличимости второго варианта будет неотличима от обфускации неразличимости первого варианта и вы не сможете получить доступ к скрытой от вас функциональности, ее как будто в коде нет!
Но самый простой метод делать поиск с ГШ это написать функцию поиска, которая будет просматривать всю базу данных. Это можно сделать арифметическим преобразованием: это можно сделать с помощью NAND операций (что и делают транзисторы в любом компьютере), а NAND(x,y) = 1-xy. Но, естественно, просматривать всю базу данных никто не будет для одного запроса, для этого потребуются оптимизации: может быть агрегация запросов многих пользователей, методами Oblivious RAM или Multi-Party-Computations. Но пока это от нас далеко. Поиск по какой-нибудь небольшой базе, например, сотрудников компании, вполне осуществим простым методом просмотра всей базы.
class.coursera.org/crypto-preview/lecture
Грубо говоря, для одного раза это будет матрица A, такая что Av=λ1v + e1 (где e1 это один маленький вектор), а во второй раз, шифром будет матрица B, такая что Bv=λ1v + e2 (где e2 это ДРУГОЙ маленький вектор). Но имея эти A и B (и не имея вектора v) вы не сможете понять даже, шифруют ли эти две матрицы один и тот же символ (или одно и то же «примерное» собственное число) или нет.
Я посылаю: pk, Enc(pk, «query»), Гугл вычисляет Enc(pk, search(«query»)) — вычисляет алгоритм «search» на моих данных (на «query») и посылает мне результат обратно. Посколько я знаю sk, я могу дешифровать:
Dec(sk, Enc(pk, search(«query»))) -> search(«query») и узнать результаты поиска.
Этот NAND(x, y) в свою очередь можно представить как набор арифметических операций: NAND(x, y) = (1 — xy) (если входы бинарны — выход будет бинарным), эти операции может делать гомоморфная схема — это просто вычитание и умножение. Т.е. весь алгоритм поиска подстроки можно осуществить гомоморфными операциями.
Но все не совсем так просто: вы, наверное, подумали, «а что же делать с циклами и ветвлениями (if/else)? Ведь если переводить это в лоб, то надо будет раскрывать/линеаризировать эти циклы и ветвления.» На этот счет есть ряд потрясающих результатов, которые говорят что это можно очень эффективно сделать, спровоцировав увеличение длины программы только в логарифмическое число раз. Т.е. была программа длины n, а стала схема размера n log n. (Число атомов во вселенной 2^300, а поэтому логарифм можно считать константой… это шутка :) )
Но это ничего не значит, возможно, авторы действительно просто поленились :) Хотя статью написать это бОльшая часть дела, так что уж грех не послать ее хоть куда-то.
Выглядеть это будет так примерно:
Гомоморфное шифрование позволяет сделать преобразование: E(pk, x) -> E(pk, f(x))
Boostrapping, соответственно, будет выглядеть так: допустим у вас есть шифр ct, в котором вы хотите уменьшить шум, допустим ct шифрует y, тогда
[ct, Enc(pk, sk)] => Enc(pk, Dec(sk, ct)) ct воспринимается как константа или набор констант, т.е. гомоморфная функция, которую мы считаем параметризована ct: f_{ct}(sk) = Dec(sk, ct). Перешифровка уменьшит шум.