Що це таке?
Повністю гомоморфне шифрування (Fully Homomorphic Encryption) дуже довго було найяскравішим відкриттям в молодій області Computer Science, що бурхливо розвивається. Коротко, такий тип шифрування дозволяє робити довільні обчислення на зашифрованих даних без їх розшифровки. Наприклад, гугл може здійснювати пошук за запитом не знаючи, що це за запит, можна фільтрувати спам, не читаючи листів, підраховувати голоси, не розкриваючи конверти з голосами, робити DNA тести, не читаючи DNA і багато чого іншого.
Тобто, людина/машина/сервер, що виробляє обчислення, робить механічні операції з шифрами, виконуючи свій алгоритм (пошук у базі даних, аналіз на спам, тощо), але при цьому не має жодного поняття про зашифровану всередині інформацію. Тільки користувач, який зашифрував свої дані, може розшифрувати результат обчислення.
Здорово, правда? І це не з області фантастики - це те, що вже можна «теоретично» втілити в життя.
Від теорії до практики не завжди, правда, рукою подати і іноді на це йдуть десятиліття. Операції в сучасних схемах гомоморфного шифрування набагато повільніше звичайних і за законом Мура стануть порівняні зі швидкістю обчислень на сьогоднішній день років через 40. Але з кожним роком схеми стають простішими і швидшими, так що, хто знає, може вже не за горами нова віха в розвитку IT технологій.
Історія створення
Історія створення першої схеми досить незвичайна: професор стенфордського університету Dan Boneh взяв за правило всім новоприбулим аспірантам пропонувати «Automatic PhD problem». Як правило, це дуже складне (але не гробове) завдання з криптографії, над якою вчені б'ються хоча б ось уже з десяток років. У 2006 році Dan запропонував придумати схему для Fully Homomorphic Encryption своєму новому студенту, Craig Gentry. Через два роки Craig її вирішив. Dan дотримав обіцянки і Craig став одним з перших студентів хто так швидко отримав доктора наук. Маючи давню пристрасть до математики, Craig отримав спочатку юридичну освіту і деякий час працював юристом, поки в досить свідомому віці не вирішив знову повернутися до математики і вступив до аспірантури Стенфорда.
Проста ідея
Схеми для повністю гомоморфного шифрування були спочатку доступні для розуміння тільки фахівцям в теорії чисел, але за останні 5 років вони настільки спростилися, що їх основну ідею можна пояснити школяреві.
Отже, уявіть, що ви хочете зашифрувати число x (може бути це лише черговий біт ваших даних, може бути невелике натуральне число). Виберіть довільний вектор v (він буде вашим секретним ключем). Можливо знайти таку матрицю A, що буде вірно Av ауд = xv, тобто твір A на v дасть приблизно вектор v помножений на число x (для тих хто пам'ятає трошки алгебру, v буде «зразковим» власним вектором, а x «приблизним» власним числом матриці A). Якщо ви захочете зашифрувати нове число y, то знову ж таки можна буде знайти матрицю B, таку що Bv ауд = yv. Таким чином ви можете, маючи тільки один секретний ключ v, зашифрувати скільки завгодно чисел, де шифром кожного числа буде матриця. Щоб розшифрувати число, ми помножимо матрицю на секретний вектор v.
Можна довести, припускаючи складність одного архаїчного завдання про пошук короткого вектора в решітці, що також складно, маючи матриці A і B, зі значущою ймовірністю (відмінною від випадкового вгадування) сказати які числа x і y вони шифрують (не знаючи, зрозуміло, секретного вектора v).
Таким чином, це дійсно шифрувальна схема, але вона також є гомоморфною! Тобто, оперуючи з матрицями A і B, а саме множачи і складаючи їх, ми будемо множити і складати ті числа, які вони шифрують. Дійсно, подивимося, що дасть розшифровка твору A і B:
(AB) v = A (Bv) {= A xv = x (Av) ауд = (xy) v, вона дає твір x і y!
А розшифровка суми A і B дасть
(A + B) v = Av + Bv {= xv + yv ауд = (x + y) v, суму x і y!
Звичайно, тут потрібен більш точний аналіз, щоб переконатися, що зразкова рівність зберігається. Також, знаходження шифруючої матриці не зовсім тривіальне завдання, але в усьому цьому цілком реально розібратися, якщо ненадовго зануритися в кілька хороших статей, як наприклад ось ця:
[GSW'13] «Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based» (pdf)
Вікно в новий світ
Craig відкрив дверцята у свого роду новий світ. Сьогодні ми маємо величезну кількість варіацій гомоморфного шифрування і найцікавіше, що одна з варіацій може дати найкращий з можливих, теоретично найстійкіший спосіб обфускації програм, а це відкриє ще більше можливостей для фантазії! Але про це в інший раз. Якщо вам цікаве поточне завдання, за вирішення якого Dan дає PhD автоматично, пишіть у коментарях;)