Как улучшение proximity gaps для случайных кодов усиливает SNARK и IOP

Исследователи добились значительного прогресса в улучшении показателей расстояния для рандомизированных кодов, что напрямую влияет на эффективность криптографических протоколов, таких как интерактивные оракульные доказательства (IOP) и сжатые неинтерактивные аргументы с нулевым разглашением (SNARK). В новой работе, опубликованной в архиве препринтов (arXiv:2607.08516), авторы смогли улучшить так называемые proximity gaps для случайных ансамблей кодов, включая случайные линейные коды, коды Рида-Соломона со случайными точками оценки и ансамбль Галлагера LDPC-кодов. Эти результаты теперь соответствуют показателям, которые ранее были достигнуты только для более сложных конструкций, таких как subspace design коды. Улучшение proximity gaps делает случайные коды более привлекательными для практического использования в криптографии и теории кодирования.

Что такое proximity gaps и почему они важны

Proximity gaps — это фундаментальное свойство кодов, которое определяет, насколько близко два кодовых слова могут находиться друг к другу, оставаясь при этом различными. В контексте криптографических протоколов, таких как IOP и SNARK, proximity gaps играют ключевую роль: они позволяют верификатору эффективно проверять, что доказательство корректно, не просматривая его целиком. Чем лучше proximity gaps, тем меньше вычислительных ресурсов требуется для проверки, что напрямую повышает производительность протоколов.

До недавнего времени наилучшие показатели proximity gaps были достигнуты для специально сконструированных кодов, таких как subspace design коды. Однако эти коды сложны в построении и не всегда удобны для практического применения. Случайные коды, напротив, легко генерируются и широко используются, но их proximity gaps были хуже. Новая работа устраняет этот разрыв, показывая, что случайные коды могут быть столь же эффективны, как и специальные конструкции.

Как авторы добились улучшения

Ключевым техническим достижением стало расширение фреймворка Local Coordinate-wise Linear (LCL) свойств. Этот фреймворк был ранее разработан Леви, Мошейффом и Шагритаей, а также Бракенсиком, Ченом, Дхаром и Чжаном. В оригинальной версии LCL позволял анализировать некоторые свойства кодов, но не мог напрямую работать с proximity gaps. Авторы новой работы модифицировали фреймворк, добавив возможность ограничения на строки (row-constrained version). Это позволило напрямую представить curve-decodability — свойство, которое влечет за собой хорошие proximity gaps, — как LCL-свойство.

Ранее исследователи использовали прокси-свойства, которые не давали точной оценки и приводили к потере параметров. Новый подход позволяет избежать этих потерь и получить точные границы для случайных кодов. В результате proximity gaps для случайных линейных кодов, кодов Рида-Соломона со случайными точками оценки и ансамбля Галлагера LDPC-кодов теперь соответствуют лучшим известным показателям.

Какие коды были улучшены

Работа охватывает три основных типа случайных кодов. Первый — случайные линейные коды, которые являются классическим объектом теории кодирования. Второй — коды Рида-Соломона со случайными точками оценки; эти коды широко используются в системах хранения данных и коммуникациях. Третий — ансамбль Галлагера LDPC-кодов, которые известны своей эффективностью в каналах с шумом. Для всех этих кодов авторы показали, что proximity gaps могут быть столь же хороши, как и для subspace design кодов, что открывает путь к их использованию в криптографических протоколах.

Какие практические последствия это имеет

Разработчики криптографических протоколов, таких как IOP и SNARK, теперь могут использовать случайные коды вместо специально сконструированных, не жертвуя эффективностью. Это упрощает реализацию протоколов и снижает требования к генерации кодов. Например, в системах SNARK, используемых в блокчейне и конфиденциальных вычислениях, улучшение proximity gaps может сократить время проверки доказательств и уменьшить размер доказательств.

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

Что пока остается неизвестным

Несмотря на теоретический прорыв, практическая реализация результатов может потребовать дополнительных усилий. Авторы не проводили экспериментов по внедрению улучшенных proximity gaps в существующие системы SNARK. Кроме того, остается открытым вопрос, можно ли еще улучшить показатели для subspace design кодов или достичь еще более высоких значений для случайных кодов. Будущие работы могут быть направлены на адаптацию фреймворка LCL для других типов кодов и свойств.

Какие перспективы открываются перед технологией

Улучшение proximity gaps для случайных кодов — это важный шаг на пути к более эффективным и практичным криптографическим протоколам. В ближайшие годы можно ожидать появления новых систем IOP и SNARK, использующих случайные коды, что упростит их внедрение в реальные приложения. Кроме того, техника LCL может быть применена для анализа других свойств кодов, что расширит теоретическую базу теории кодирования.

Как это влияет на безопасность и производительность

Повышение proximity gaps напрямую улучшает безопасность протоколов: чем больше gap, тем сложнее злоумышленнику подделать доказательство. Одновременно улучшается производительность, так как верификатор может быстрее проверять доказательства. Таким образом, новые результаты способствуют созданию более надежных и быстрых криптографических систем.

Заключение

Работа исследователей демонстрирует, что случайные коды могут быть столь же эффективны, как и специальные конструкции, в контексте proximity gaps. Расширение фреймворка LCL до row-constrained версии позволило достичь показателей, ранее доступных только для subspace design кодов. Это открывает новые возможности для разработчиков криптографических протоколов и теоретиков, упрощая использование случайных кодов в IOP и SNARK. Дальнейшие исследования могут быть направлены на практическую реализацию и поиск еще более эффективных конструкций.