Секретные вычисления: существует ли такое животное?

Вопрос по теории информатики

Сегодня я могу тайно хранить файлы в облаке (скажем, на amazon s3), зашифровав их перед сохранением и расшифровав после загрузки. Провайдер хранилища не может получить никакой информации из хранимых файлов — все надежно зашифровано, и здесь подойдет даже симметричный шифр.

Мой вопрос заключается в том, можно ли сделать то же самое с вычислениями в облаке. В облаке есть провайдер вычислений (скажем, amazon ec2). Могу ли я загрузить «зашифрованную программу» вместе с «зашифрованным вводом» для программы, и пусть мой провайдер облачных вычислений выполнит за меня все вычисления и сгенерирует для меня «зашифрованный вывод» — с теми же гарантиями безопасности, что и в «секретном файле хранить"?

Обратите внимание, что я говорю не об обфускации и обратном инжиниринге, а о секретных вычислениях с сильными криптографическими гарантиями.

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

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

Приветствуются ссылки на академическую литературу и разъяснения относительно описанных выше концепций.

Отвечать:

Похоже, что:

  • секретный ввод и вывод, несекретная программа: только в теории

  • Секретный ввод, секретный вывод и секретная программа: даже не в теории. (Обновление: возможно, да, см. комментарий Артелиуса)


security cloud cryptography computer-science theory
person flybywire    schedule 01.10.2009    source источник
comment
Я думаю, что это возможно, но очень очень... сложно.   -  person Pratik Deoghare    schedule 01.10.2009
comment
Что вы подразумеваете под зашифрованной программой?   -  person MAK    schedule 01.10.2009
comment
Возможны также секретный ввод, секретный вывод и секретная программа. Предположим, вы можете запустить интерпретатор (или машину Тьюринга или что-то еще) в секретном вводе и выводе, несекретной программной среде. Тогда программа, которую выполняет интерпретатор, является секретной.   -  person Artelius    schedule 02.10.2009

Ответы (4)


arrow_upward
12
arrow_downward

Да, такая вещь вроде как существует, хотя на данный момент она очень теоретическая. Это называется гомоморфным шифрованием. Вот статья о прорывах, сделанных в IBM и об этом есть комментарий в блоге Брюса Шнайера.

По сути, система гомоморфного шифрования — это система, в которой:

decrypt (f (encrypt (plaintext))) = f (plaintext)
person Skizz    schedule 01.10.2009
comment
+1 Вау! Я хорошо прочитаю об этом. Время удалить мой ответ, говорящий нет :) - person Robin Day; 01.10.2009
comment
Пожалуйста, поправьте меня, если я неправильно понял блог Шейнера: алгоритм не является секретным, только ввод и вывод. - person flybywire; 01.10.2009
comment
Вы правы, алгоритм не является секретным или зашифрованным, и он никогда не может быть секретным. Код должен выполняться чем-то незашифрованным способом. Поставщик услуг всегда сможет получить код, который запускается на серверах. Обычно с точки зрения безопасности лучше всего иметь открытые алгоритмы, которые сообщество может проверять и тестировать на наличие уязвимостей — запутывание — это не безопасность! Если у вас есть «магический алгоритм», который никто не разработал (и я ненавижу это говорить), всегда есть патентная защита. - person Skizz; 01.10.2009
comment
Разве Шнайер не говорил, что эта идея принципиально непрактична? - person zebrabox; 06.10.2009

arrow_upward
3
arrow_downward

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

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

Конечно, во всем этом есть проблема: она все еще совершенно непрактична, несмотря на то, что ее решили.

Если вы хотите узнать больше об этом, я рекомендую статью в Википедии, а также статью Брюса Шнайера "Прорыв в гомоморфном шифровании".

person Edan Maor    schedule 01.10.2009

arrow_upward
1
arrow_downward

Вот еще несколько вещей, которые вы, возможно, захотите прочитать:

http://en.wikipedia.org/wiki/Secure_multi-party_computation

http://www.cs.uiuc.edu/homes/rosulek/pubs/enc-data/enc-data.pdf

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.35.5151

person Artelius    schedule 01.10.2009

arrow_upward
1
arrow_downward

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

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

person Rasmus Faber    schedule 01.10.2009