Так и подмывало озаглавить тему: «Закат компании Гугл близок!», но все-таки слишком уж «желто» было бы.
Теперь к делу. Что такое «гомоморфное шифрование» и причем тут Гугл?
Гомоморфным шифрованием называют такую криптосистему, которая позволяет совершать некоторые математические действия с открытым текстом путем произведения операций с зашифрованным (возможно другое математическое действие или даже ряд операций). Например, RSA гомоморфна для операции умножения (тривиально из самого шифрования).
Удивительно, но до недавних пор не существовало криптосистемы гомоморфной для операций умножения и суммирования одновременно, так называемого полностью гомоморфного шифрования (fully homomorphic encryption), т.к. суммы и умножения хватит, чтобы выразить любую математическую функцию. Главная проблема с предыдущими схемами была в том, что каждая операция добавляет некоторый «шум» в криптотекст (
посмотрите на формулу RSA и вспомните определение mod), поэтому через некоторое количество шагов накопленный шум делает расшифровку невозможной. Насколько я помню из презентации, говорилось, что подобные схему все же существуют, но они экспоненциональны по «эффективности».
Крэйг Гэнтри (Craig Gentry, PhD Stanford, IBM Research) опубликовал пример первой такой функции в своей PhD диссертации. Не вдаваясь в подробности (да и не буду делать вид, что на 100% понял все математические выкладки), смысл его решения заключается в том, что он использует двойное шифрование. Т.е. через определенное количество шагов он «снимает верхний слой» (первое шифрование) и «убирает» накопившийся «шум».
Как это работает, я расскажу общими словами и примерами, которые он сам использовал в своей презентации. Кому интересна математика и более формальное объяснение — читать
диссертацию.
В обсуждении моего недавнего 
