Гомоморфизмы и изоморфизмы

2009 год. Крейг Джентри, Стэнфорд. Первая в истории схема полностью гомоморфного шифрования (FHE). Медицинские данные можно отдать в облако зашифрованными - и попросить облако провести анализ, не раскрывая данные. Как? Шифрование - гомоморфизм кольца: phi(a+b) = phi(a)+phi(b), phi(a*b) = phi(a)*phi(b). Операции на зашифрованных данных = операции через гомоморфизм. Microsoft SEAL и Google's FHE Transpiler используют это в продакшне. Одна теорема абстрактной алгебры - основа конфиденциальных вычислений.

• FHE (Gentry 2009) - гомоморфизм кольца Z/qZ позволяет вычислять на зашифрованных данных
• AES S-box - биекция (изоморфизм) на поле GF(2^8), простое ядро обеспечивает инъективность
• Линейный слой нейросети: W*x - гомоморфизм (R^n,+)->(R^m,+), критично для backprop
• SE(3)-эквивариантные сети (AlphaFold2): гомоморфизмы из группы симметрий в пространство признаков

Нётер и первая теорема

Эмми Нётер сформулировала три теоремы об изоморфизме в 1927 году - в период, когда абстрактная алгебра только оформлялась как дисциплина. Первая теорема стала центральным результатом: она объясняет, почему факторгруппа G/ker(phi) имеет именно такую структуру. До Нётер это было набором разрозненных наблюдений. После - единой теорией. Те же идеи позже перешли в теорию модулей, теорию колец и в конечном счёте в гомологическую алгебру.

Гомоморфизм: сохранение структуры

2009 год. Крейг Джентри публикует диссертацию в Стэнфорде. Впервые в истории - схема шифрования, позволяющая вычислять на зашифрованных данных, не расшифровывая их. Это FHE - полностью гомоморфное шифрование. За названием стоит одна формула: $\phi(a \cdot b) = \phi(a) \circ \phi(b)$. Операции на зашифрованных данных проходят через гомоморфизм кольца - и результат совпадает с зашифрованным ответом на открытых данных. Microsoft SEAL, Google's FHE Transpiler, IBM HElayers - все они реализуют именно это.

**Гомоморфизм групп** - отображение $\phi: G \to H$ такое, что $\phi(a * b) = \phi(a) \circ \phi(b)$ для всех $a, b \in G$. Операции в $G$ и $H$ могут быть разными. Гомоморфизм переносит структуру $G$ в $H$, сохраняя таблицу умножения - дословно.

Линейный слой $W \in \mathbb{R}^{m \times n}$ - гомоморфизм аддитивных групп $(\mathbb{R}^n, +) \to (\mathbb{R}^m, +)$: $W(x + y) = Wx + Wy$. Именно поэтому линейность в нейросетях критична для градиентного потока: гомоморфизм переносит структуру суммы в структуру суммы, и backprop работает.

Ядро и образ: две стороны гомоморфизма

AES S-box - замена байт в каждом раунде шифрования. Внутри - биекция на поле $GF(2^8)$: изоморфизм аддитивной группы байт. Фиксированная точка - только нулевой байт (ядро просто: $\{0\}$), образ - всё поле. Не случайность: это алгебраическое свойство, устойчивое к дифференциальному криптоанализу. Структура ядра определяет инъективность - и в S-box, и в любом другом гомоморфизме.

Для гомоморфизма $\phi: G \to H$ определяют два ключевых объекта: - **Ядро** $\ker(\phi) = \{g \in G \mid \phi(g) = e_H\}$ - прообраз нейтрального элемента - **Образ** $\operatorname{im}(\phi) = \{\phi(g) \mid g \in G\}$ - множество значений $\phi$ Ядро - **нормальная** подгруппа $G$. Образ - подгруппа $H$.

SHA-256 и Merkle-Damgard конструкция - структуросохраняющее отображение: каждый блок применяется через функцию сжатия последовательно. Это не гомоморфизм групп в строгом смысле, но именно алгебраическая идея сохранения структуры делает доказательство стойкости через reduction возможным. Ядро функции сжатия (прообраз фиксированной точки) - главная цель при поиске коллизий.

Первая теорема об изоморфизме

**Первая теорема об изоморфизме (Нётер, 1927):** если $\phi: G \to H$ - гомоморфизм, то $G/\ker(\phi) \cong \operatorname{im}(\phi)$. Факторгруппа по ядру изоморфна образу. Это не просто утверждение о структуре - это объяснение, почему гомоморфное шифрование вообще возможно. Зашифрованное пространство и открытое изоморфны как кольца. Первая теорема гарантирует: такой изоморфизм существует и единственен.

**Изоморфизм** - биективный гомоморфизм ($\phi$ инъективно и сюръективно). Два изоморфных объекта неразличимы с точки зрения теории групп - одна структура с разными именами. $(\mathbb{Z}_4, +) \cong$ (вращения квадрата на $0^\circ, 90^\circ, 180^\circ, 270^\circ$). AES S-box - изоморфизм аддитивной группы $(GF(2^8), +)$ с собой.

Ключевые идеи

• Гомоморфизм $\phi: G \to H$: $\phi(ab) = \phi(a)\phi(b)$ - сохраняет таблицу умножения
• Ядро $\ker(\phi) = \phi^{-1}(e_H)$ - нормальная подгруппа $G$; $\ker(\phi) = \{e\}$ iff инъективность
• Образ $\operatorname{im}(\phi)$ - подгруппа $H$; для конечных групп $|G| = |\ker|\cdot|\operatorname{im}|$
• Изоморфизм = биективный гомоморфизм; $G \cong H$ означает одинаковую структуру
• Первая теорема Нётер (1927): $G/\ker(\phi) \cong \operatorname{im}(\phi)$
• FHE: шифрование - гомоморфизм кольца; первая теорема гарантирует изоморфизм зашифрованного и открытого пространства

Что дальше

Гомоморфизмы ведут к кольцам - структурам с двумя операциями. Гомоморфизмы колец уважают и сложение, и умножение. Первая теорема работает там же - и именно на ней строится FHE.

• Кольца — Кольцо - группа по сложению с умножением; гомоморфизмы колец = основа FHE
• Факторгруппы — G/ker(phi) из первой теоремы - центральный пример факторгруппы
• Теория представлений — Гомоморфизмы групп в GL(V) - основа квантовой механики и ML-эквивариантности

Вопросы для размышления

• FHE работает потому что зашифрованное пространство и открытое изоморфны как кольца. Первая теорема гарантирует существование этого изоморфизма - но где в схеме Джентри роль ker(phi)?
• Если phi: G -> H - гомоморфизм и G циклическая, обязательно ли im(phi) циклическая? Почему?
• Как первая теорема помогает вычислять факторгруппы, не зная явного умножения в них?

Связанные уроки

• aa-06-quotient — Первая теорема напрямую строит факторгруппу G/ker(phi)
• aa-04-rings — Гомоморфизмы колец - та же схема, но для двух операций
• aa-14-representations — Теория представлений - гомоморфизмы групп в GL(V)
• aa-21-algebra-crypto — FHE и RSA опираются на гомоморфизмы колец
• aa-30-algebra-ml — Линейный слой - гомоморфизм аддитивных групп; SE(3)-эквивариантность
• crypto-43-homomorphic