Регистрация Войти
Рейтинг:2
Sean avatar Crypto

Элемент поля как показатель группового элемента

флаг yt
Sean

Ограничения R1CS выражаются для конечных полей. Многие системы проверки, такие как zk-SNARK, используют ключи проверки, такие как $ г ^ {\ альфа ^ 0}, г ^ {\ альфа ^ 1}, ..., г ^ {\ альфа ^ п} $ куда $\альфа$ является элементом поля. Являются ли эти элементы поля целыми числами?

171
0 + 0
fgrieu avatar
флаг ng
fgrieu
R1CS означает систему ограничений ранга 1. Мне пришлось гуглить это.
0
Ответить
флаг ck
Peter Mortensen
Язык? Какой язык? *"[Предварительная обработка zk-SNARK для NP-полного языка "R1CS" (системы ограничений ранга 1), который представляет собой язык, аналогичный выполнимости арифметических схем... NP-полный язык R1CS](https:/ /github.com/scipr-lab/libsnark)"*
0
Ответить
Рейтинг:3
kodlu avatar Crypto
флаг sa
kodlu

Если $\alpha \in\mathbb{F}_p$ т. е. поле является простым полем, тогда показатели степени являются целыми числами по модулю $p-1$ так как примитивный элемент $\альфа$ генерирует мультипликативную группу $\mathbb{F}_p^{\ast}$ порядка $p-1$.

0 + 0
Fractalice avatar
флаг in
Fractalice
показатели определяются по модулю p-1
2
Ответить
fgrieu avatar
флаг ng
fgrieu
Подзаголовок к ответу и комментарию выше [исправлено и дополнено]: да, $\alpha^i$ являются целыми числами. Мы можем эквивалентно рассматривать их как в $\mathbb Z$, или как целые числа в диапазоне $[0,p)$, где $p$ — порядок (количество элементов) группы степеней $g$, или когда/ поскольку $p$ является простым как элементы конечного поля $\mathbb F_p$, также отмечены $\operatorname{GF}(p)$ или $\mathbb Z/p\mathbb Z$. Сам показатель степени $i$ является целым числом, определенным по модулю $p-1$, то есть в $\mathbb Z/(p-1)\mathbb Z$, поскольку $p-1$ — это порядок мультипликативной группы $\ матбб F_p^*$.
1
Ответить
Sean avatar
флаг yt
Sean
Большое спасибо за разъяснения.
0
Ответить
Sean avatar
флаг yt
Sean
Просто из любопытства. Так как $F_p$ может быть определена над другой областью, например конечными полями над многочленами, которая гомоморфна своей эквивалентной части в целочисленной области. Но тогда, учитывая элемент в таком поле, я думаю, трудно «сопоставить» его обратно с его целочисленной копией. В этом случае, когда люди определяют R1CS, почему бы прямо не сказать, что домен представляет собой поле целых чисел, например $Z_p^*$?
0
Ответить
Vadym Fedyukovych avatar
флаг in
Vadym Fedyukovych
Единственная известная известная реализация - это поля простого порядка, без расширений полей (многочленов). Причина в том, что операция сопряжения на эллиптических кривых требуется для основного уравнения проверки с популярной системой Groth 2016.
1
Ответить
fgrieu avatar
флаг ng
fgrieu
@Sean: насколько я знаю, если мы хотим сохранить это $$g^{\left(\alpha^{i+j}\right)}=\left(g^{\left(\alpha^i\ right)}\right)^{\left(\alpha^j\right)}$$ и $\alpha$ в конечном поле, то $\mathbb F_p$ с $g$ простого порядка $p$ является единственным вариант для указанного поля.
1
Ответить
Рейтинг:1
Vadym Fedyukovych avatar Crypto
флаг in
Vadym Fedyukovych

Групповой элемент, например $ г ^ {\ альфа ^ к} $ куда $г$ является генератором подгруппы и элементом поля $\альфа$ сравнима с задачей протокола Verifier of Schnorr, используемого для оценки полиномов. В частности, $г$ будет точкой эллиптической кривой начального порядка $q$, и $\alpha \in\mathbb{F}_q$ будет вычетом по модулю $q$. Что ж, остаток можно считать целым числом во всех практических аспектах.

Я продвинул эту идею еще дальше с помощью примера начальной школы «умножение на 3» системы R1CS без напоминаний об остатках, просто чтобы сделать это чрезвычайно простым и дружелюбным. Это можно было увидеть в разделе C Бумага "Судоку" за которым следует код C++/libsnark начального уровня, полезный для новичков в SNARK.Эта статья посвящена моей повторной реализации частной проверки секретного решения судоку, первоначально представленного на Financial Cryptography 2016, начиная с метода проверки Наора и представления полиномиального набора.

0 + 0
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

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