Мультилинейное отображение

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

Определение и формальное описание

Пусть \( V_1, V_2, \dots, V_k \) и \( W \) — векторные пространства над одним и тем же полем \( \mathbb{F} \) (например, полем действительных чисел \( \mathbb{R} \) или комплексных чисел \( \mathbb{C} \)). Отображение

\[ f: V_1 \times V_2 \times \cdots \times V_k \to W \]

называется мультилинейным (или k-линейным), если для любого индекса \( i = 1, \dots, k \) и любых фиксированных векторов \( v_j \in V_j \) (где \( j \neq i \)) отображение

\[ v_i \mapsto f(v_1, \dots, v_{i-1}, v_i, v_{i+1}, \dots, v_k) \]

является линейным. Это означает, что для всех \( a, b \in \mathbb{F} \) и \( x, y \in V_i \) выполняется:

\[ f(v_1, \dots, a x + b y, \dots, v_k) = a f(v_1, \dots, x, \dots, v_k) + b f(v_1, \dots, y, \dots, v_k). \]

Частные случаи

• Билинейное отображение — мультилинейное отображение с двумя аргументами (\( k = 2 \)). Пример: скалярное произведение в евклидовом пространстве.
• Трилинейное отображение — с тремя аргументами (\( k = 3 \)). Пример: определитель матрицы \( 3 \times 3 \), рассматриваемый как функция от трёх строк (или столбцов).
• Полилинейное отображение — общий термин для любого числа аргументов, часто используется как синоним мультилинейного, но в некоторых контекстах под полилинейным понимают отображение с переменным числом аргументов.

Свойства

Линейность по каждому аргументу

Основное свойство — линейность по каждому аргументу в отдельности. Однако мультилинейное отображение не является линейным отображением из декартова произведения пространств в \( W \), так как, например, для билинейного отображения \( f(u+v, w) = f(u, w) + f(v, w) \), но \( f(u, v+w) = f(u, v) + f(u, w) \), и при этом \( f(\lambda u, v) = \lambda f(u, v) = f(u, \lambda v) \). В то же время \( f(u+v, w+x) = f(u, w) + f(u, x) + f(v, w) + f(v, x) \), что не является линейным по паре аргументов.

Симметричность и антисимметричность

Мультилинейное отображение может обладать дополнительными свойствами симметрии:

• Симметричное, если перестановка любых двух аргументов не меняет значения: \( f(\dots, v_i, \dots, v_j, \dots) = f(\dots, v_j, \dots, v_i, \dots) \).
• Антисимметричное (или кососимметричное), если перестановка двух аргументов меняет знак: \( f(\dots, v_i, \dots, v_j, \dots) = - f(\dots, v_j, \dots, v_i, \dots) \). Пример: определитель матрицы — антисимметричное мультилинейное отображение строк.

Связь с тензорами

Мультилинейные отображения тесно связаны с тензорами. Пространство всех мультилинейных отображений \( V_1 \times \dots \times V_k \to \mathbb{F} \) (где \( W = \mathbb{F} \)) изоморфно тензорному произведению сопряжённых пространств \( V_1^ \otimes \dots \otimes V_k^ \). Если \( V_i \) конечномерны, то размерность пространства мультилинейных форм равна произведению размерностей \( \dim V_1 \cdot \dots \cdot \dim V_k \).

Примеры

1. Скалярное произведение в \( \mathbb{R}^n \): \( \langle \cdot, \cdot \rangle: \mathbb{R}^n \times \mathbb{R}^n \to \mathbb{R} \) — билинейное отображение.
2. Определитель матрицы \( n \times n \): \( \det: \mathbb{R}^n \times \dots \times \mathbb{R}^n \to \mathbb{R} \) (n аргументов) — антисимметричное мультилинейное отображение по строкам или столбцам.
3. Векторное произведение в \( \mathbb{R}^3 \): \( \times: \mathbb{R}^3 \times \mathbb{R}^3 \to \mathbb{R}^3 \) — билинейное отображение.
4. Смешанное произведение трёх векторов в \( \mathbb{R}^3 \): \( (a, b, c) \mapsto a \cdot (b \times c) \) — трилинейное отображение, антисимметричное по всем аргументам.

Применение в криптографии

Мультилинейные отображения нашли важное применение в современной криптографии, особенно в контексте построения схем с открытым ключом, таких как мультилинейные обмены ключами и мультилинейные карты (multilinear maps). В отличие от билинейных отображений (например, спаривания Вейля или Тейта на эллиптических кривых), мультилинейные отображения для \( k > 2 \) долгое время были труднодостижимы.

Мультилинейные карты

Мультилинейная карта (или мультилинейное спаривание) — это отображение \( e: G_1 \times G_2 \times \dots \times G_k \to G_T \), где \( G_i \) и \( G_T \) — циклические группы (часто одного порядка), удовлетворяющее мультилинейности:

\[ e(g_1^{a_1}, g_2^{a_2}, \dots, g_k^{a_k}) = e(g_1, g_2, \dots, g_k)^{a_1 a_2 \dots a_k}. \]

Такие отображения являются обобщением билинейных спариваний. Первые конструкции мультилинейных карт были предложены в 2003 году Дэном Боне и Алисой Сильверберг (схема на основе эллиптических кривых), но они оказались неэффективными для \( k > 2 \). В 2013 году группа исследователей (Санжей Гарг, Крейг Джентри, Шай Халеви и др.) предложила первую практическую реализацию мультилинейных карт на основе теории решёток (схема GGH13). Однако впоследствии были найдены атаки на эту и последующие схемы (CLT13, GGH15), что поставило под сомнение их безопасность.

Применение

• Мультилинейный обмен ключами (аналог протокола Диффи — Хеллмана для \( k \) сторон). Позволяет \( k \) участникам выработать общий секретный ключ, используя мультилинейное отображение.
• Шифрование с открытым ключом с функциональными возможностями (functional encryption), в том числе шифрование с внутренним произведением и атрибутное шифрование.
• Доказательства с нулевым разглашением (zero-knowledge proofs) и схемы подписи.

Критика и ограничения

Основная проблема — отсутствие полностью безопасных и эффективных реализаций мультилинейных карт для \( k > 2 \). Все известные кандидаты были взломаны или имеют экспоненциальную сложность. Кроме того, мультилинейные отображения требуют больших размеров ключей и вычислительных затрат по сравнению с билинейными. В связи с этим, в криптографии активно исследуются альтернативные подходы, такие как гомоморфное шифрование и решёточные криптосистемы.

Мультилинейные отображения в математике

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

• Тензор кривизны Римана — мультилинейное отображение, принимающее четыре векторных поля и возвращающее векторное поле.
• Формы объёма на многообразиях — антисимметричные мультилинейные отображения, задающие интегрирование.
• Полилинейная алгебра изучает свойства мультилинейных отображений и их связь с тензорными произведениями.

Источники

1. Кострикин А. И., Манин Ю. И. Линейная алгебра и геометрия. — М.: Наука, 1986.
2. Ленг С. Алгебра. — М.: Мир, 1968.
3. Boneh D., Silverberg A. Applications of Multilinear Forms to Cryptography // Contemporary Mathematics, 2003.
4. Garg S., Gentry C., Halevi S. Candidate Multilinear Maps from Ideal Lattices // Advances in Cryptology — EUROCRYPT 2013.
5. Coron J.-S., Lepoint T., Tibouchi M. Practical Multilinear Maps over the Integers // Advances in Cryptology — CRYPTO 2013.
6. Шнайер Б. Прикладная криптография. — М.: Вильямс, 2002.