Подписи на основе MPCitH из задач ограниченного декодирования

Основная информация

• ID статьи: 2510.11224
• Название: MPCitH-based Signatures from Restricted Decoding Problems
• Авторы: Michele Battagliola (Политехнический университет Марке), Sebastian Bitzer, Antonia Wachter-Zeh, Violetta Weger (Технический университет Мюнхена)
• Классификация: cs.CR (Криптография и безопасность), cs.IT (Теория информации), math.IT (Теория информации)
• Дата публикации: 13 октября 2025 г. (препринт arXiv)
• Ссылка на статью: https://arxiv.org/abs/2510.11224

Аннотация

В данной работе задачи ограниченного декодирования (E-SDP) встраиваются в фреймворки Threshold-Computation-in-the-Head (TCitH) и VOLE-in-the-Head (VOLEitH), которые являются последними разработками парадигмы MPC-in-the-Head (MPCitH), значительно улучшающими производительность схем цифровой подписи. Авторы предлагают метод моделирования с простой структурой, достигающий конкурентоспособного размера подписи. Путём использования того же предположения о сложности, что и в CROSS, размер подписи сокращается более чем в два раза по сравнению с версией, поданной в NIST. Кроме того, авторы обнаруживают тесную связь между тернарным полнозвёздным декодированием и предположением о сложности, лежащим в основе WAVE, при этом размер подписи, полученный с использованием этого метода, сравним с размерами наименьших кандидатов MPCitH в конкурсе NIST.

Исследовательский контекст и мотивация

Предпосылки проблемы

1. Необходимость стандартизации постквантовой криптографии: После стандартизации CRYSTALS-Dilithium, FALCON и SPHINCS+ NIST в сентябре 2022 года объявил о сборе дополнительных схем цифровой подписи с целью диверсификации набора постквантовых стандартов подписи.
2. Развитие парадигмы MPCitH: С момента предложения Ishai и соавторами в 2007 году технология MPCitH переформатировала ландшафт постквантовых цифровых подписей. TCitH и VOLEitH как последние специализации MPCitH обеспечивают значительные улучшения производительности по сравнению с предыдущими конструкциями.
3. Применение теории кодирования в криптографии: Сложные задачи, основанные на теории кодирования (такие как задачи декодирования в метрике Хэмминга и метрике ранга), обеспечивают теоретическую основу для построения эффективных постквантовых подписей.

Исследовательская мотивация

1. Потребность в оптимизации производительности: Хотя существующая схема подписи CROSS основана на задачах ограниченного декодирования, она использует относительно простой протокол CVE, оставляя место для оптимизации размера подписи.
2. Унификация фреймворков: Объединение задач ограниченного декодирования в передовые фреймворки TCitH/VOLEitH для полного использования преимуществ производительности этих фреймворков.
3. Повышение конкурентоспособности: Значительное сокращение размера подписи при сохранении безопасности для повышения конкурентоспособности в конкурсе NIST.

Основные вклады

1. Предложен метод полиномиального моделирования E-SDP: Разработано простое, но эффективное полиномиальное соотношение для встраивания задачи ограниченного синдромного декодирования в фреймворки TCitH и VOLEitH.
2. Значительное сокращение размера подписей типа CROSS: Для одной и той же задачи декодирования размер подписи сокращается более чем на 50% по сравнению с поданной в NIST схемой CROSS (с 12,4 кБ до 5,5 кБ).
3. Обнаружен потенциал применения тернарного полнозвёздного декодирования: Доказано, что тернарное полнозвёздное декодирование, связанное с WAVE, является задачей ограниченного декодирования, и достигнут размер подписи, сравнимый с наименьшими кандидатами MPCitH (3,1 кБ).
4. Предоставлена полная параметризованная схема: Даны конкретные выборы параметров и анализ производительности для классов безопасности NIST 1, 3 и 5.

Описание методов

Определение задачи

Целью исследования является представление задачи ограниченного синдромного декодирования (E-SDP) как полиномиального соотношения, позволяющего построить схему цифровой подписи в фреймворках TCitH и VOLEitH.

Определение E-SDP: Дано множество ограничений E ⊂ F, проверочная матрица H ∈ F^(r×n) и синдром s ∈ F^r, найти e ∈ E^n такой, что eH^T = s.

Основной метод моделирования

1. Построение полиномиальных ограничений

Для проверочной матрицы в систематической форме H = (A, I_r), где A ∈ F^(r×k), I_r — единичная матрица:

• Вектор-свидетель: w ∈ F^k (вектор частичной ошибки)
• Расширенный вектор ошибки: e = (w, s - wA^T)
• Полином ограничения: f_E(x) = ∏_{e∈E}(x - e)

Система полиномиальных соотношений:

F(x) = (f_1, ..., f_n) ∈ F[x_1, ..., x_k]^n

где:

• f_i(x) = f_E(x_i) для i ∈ k
• f_{k+i}(x) = f_E(s_i - ⟨a_i, x⟩) для i ∈ r

2. Анализ степени

Предложение 1: Данное полиномиальное соотношение обеспечивает моделирование E-SDP со степенью z = |E|. Если w ∈ F^k удовлетворяет F(w) = 0, то вектор ошибки e = (w, s - wA^T) решает экземпляр E-SDP (H, s).

Конкретные реализации

CROSS-SDP

• Множество ограничений: E = {2^i | i ∈ 7} ⊆ F_{127}
• Параметры: |E| = 7, p = 127
• Безопасность: На основе детального анализа 7,15

Ternary-SDP

• Множество ограничений: E = {1, 2} ⊆ F_3
• Параметры: |E| = 2, p = 3
• Сложность: O(2^{0.247·n}) операций (с полиномиальным множителем)

Экспериментальная установка

Стратегия выбора параметров

На основе требований безопасности и целей оптимизации производительности выбраны следующие ключевые параметры:

1. Параметры фреймворка TCitH:
   • τ: количество параллельных повторений
   • N: размер области оценки
   • μ: степень расширения поля K : F
   • η: параметр пакетной обработки
2. Параметры фреймворка VOLEitH:
   • ρ: параметр расширения поля
   • B: параметр проверки согласованности
   • T_open: параметр схемы VC

Ограничения безопасности

Удовлетворяют следующим требованиям безопасности:

• TCitH: N ≤ p^μ, p^{μ·η} ≥ 2^λ, (N/d)^τ ≥ 2^{λ-w}
• VOLEitH: N^τ/d ≥ 2^{λ-w}, p^ρ ≥ 2^λ

Показатели оценки

Основной оценкой является размер подписи, включающий три компонента:

• |σ_sym|: связанный со схемой VC
• |σ_w|: связанный со свидетелем
• |σ_F|: связанный с OWF

Экспериментальные результаты

Основные результаты

Производительность фреймворка TCitH

| Уровень безопасности | Тип E-SDP | |F| | |E| | n | k | τ | N | μ | η | Размер подписи (Б) | |---------|-----------|-----|-----|---|---|---|---|---|---|-----------| | NIST 1 | CROSS-SDP | 127 | 7 |127| 76| 15|2048| 2| 10| 5 533 | | NIST 1 | Ternary-SDP| 3 | 2 |579|213| 12|2048| 7| 12| 3 095 | | NIST 3 | CROSS-SDP | 127 | 7 |187|111| 23|2048| 2| 14| 12 354 | | NIST 3 | Ternary-SDP| 3 | 2 |839|309| 18|2048| 7| 18| 6 860 |

Производительность фреймворка VOLEitH

Сравнение с кандидатами NIST

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

1. Значительное сокращение размера: CROSS-SDP сокращает размер подписи на 64,5% по сравнению с исходной CROSS
2. Влияние выбора фреймворка: Для задач высокой степени VOLEitH имеет преимущество перед TCitH
3. Конкурентоспособность: Ternary-SDP достигает производительности, сравнимой с лучшими кандидатами MPCitH

Связанные работы

Развитие парадигмы MPCitH

1. Исходная MPCitH 23: Предложена в 2007 году, объединяет безопасные многосторонние вычисления с преобразованием Фиат-Шамира
2. Фреймворк TCitH 21: Реализация с использованием ℓ-из-n пороговой секретной передачи
3. Фреймворк VOLEitH 13: Компиляция протоколов нулевого знания на основе VOLE в публично проверяемые протоколы

Применение теории кодирования

1. Декодирование в метрике Хэмминга: Основа схем SDitH и других
2. Декодирование в метрике ранга: Схемы RYDE, Mirath и другие
3. Задача ядра перестановки: Предположение о сложности схемы PERK

Задачи ограниченного декодирования

1. Схема CROSS 6: Ограниченное декодирование с использованием простого протокола CVE
2. Схема WAVE 10,19: На основе тернарного синдромного декодирования высокого веса
3. Теоретический анализ 8,9: NP-полнота и конкретная сложность E-SDP

Заключение и обсуждение

Основные выводы

1. Успешная интеграция фреймворков: Доказано, что задачи ограниченного декодирования могут быть эффективно интегрированы в передовые фреймворки MPCitH
2. Значительное улучшение производительности: Путём замены простого протокола CVE на конструкции TCitH/VOLEitH значительно сокращается размер подписи
3. Широкая применимость: Метод применим к различным типам задач ограниченного декодирования

Ограничения

1. Увеличение сложности: По сравнению с простым протоколом CVE исходной CROSS конструкции TCitH/VOLEitH значительно более сложны
2. Вычислительные затраты: Хотя размер подписи сокращается, это может увеличить вычислительную сложность генерации и проверки подписи
3. Зависимость от параметров: Производительность в высокой степени зависит от конкретного выбора параметров и стратегии оптимизации

Направления будущих исследований

1. Дальнейшая оптимизация: Исследование более эффективных методов полиномиального моделирования
2. Другие ограниченные задачи: Расширение метода на другие типы задач ограниченного декодирования
3. Оптимизация реализации: Разработка эффективных реализаций для снижения вычислительных затрат

Глубокая оценка

Преимущества

1. Техническая инновация: Предложен лаконичный и эффективный метод полиномиального моделирования задач ограниченного декодирования
2. Значительные улучшения: Значительное сокращение размера подписи при сохранении той же безопасности
3. Теоретический вклад: Установлена связь между задачами ограниченного декодирования и передовыми фреймворками MPCitH
4. Практическая ценность: Предоставляет новые идеи проектирования для схем постквантовой подписи

Недостатки

1. Компромисс сложности: Сокращение размера подписи достигается за счёт увеличения сложности конструкции
2. Ограниченная новизна: В основном представляет собой умелую комбинацию существующих методов с ограниченными теоретическими инновациями
3. Отсутствие деталей реализации: Недостаток детального анализа производительности и сравнения фактических реализаций

Влияние

1. Академическая ценность: Предоставляет новый пример применения фреймворка MPCitH
2. Практическое значение: Может повлиять на выбор схем в будущем процессе стандартизации NIST
3. Методологический вклад: Служит справочником для аналогичного моделирования других сложных задач

Сценарии применения

1. Среды с ограниченными ресурсами: Приложения, чувствительные к размеру подписи
2. Развёртывание постквантовой криптографии: Системы, требующие разнообразия предположений о безопасности
3. Исследовательские прототипы: Основа для дальнейшей оптимизации и улучшения

Библиография

Статья цитирует 24 важных справочных источника, охватывающих развитие фреймворка MPCitH, применение теории кодирования и связанные кандидаты NIST, обеспечивая прочную теоретическую основу для исследования.