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

Доказательство того, что семейство теплицевых матриц XOR-универсально

флаг us
Hernichtocles

Определение XOR-универсальных хэш-функций Абидина [1]:

Класс $Ч$ хеш-функций из $ млн $ к $Т$ является XOR-универсальным$_2$ ($XU_2$), если существует не более $|Ч|/|Т|$ хеш-функции $ч$ $\in$ $Ч$ такой, что $(ч(м_1) = ч(м_2$) $\оплюс т)$ для любых двух различных $m_1$, $m_2$ $\in$ $ млн $ и любой $т \в Т$.

Если есть не более $\эпсилон|Н|$ вместо этого хэш-функции для $\эпсилон > 1/|T|$, класс $Ч$ является $\эпсилон$-Почти XOR-Универсальный$_2$ ($\эпсилон-AXU_2$).

$ млн $ это набор, содержащий все сообщения (в данном случае все битовые строки длины m)

$Т$ это набор всех возможных тегов (в данном случае все битовые строки длины n)

$Ч$ множество, содержащее все возможные хеш-функции

$|Ч|$ относится к количеству хеш-функций (для $n$ Икс $м$ Матрицы Теплица $|Ч|$ = $2^{м + п-1}$).

$|Т|$ относится к размеру набора $Т$.

Матрицы Теплица для аутентификации

Матрицы Теплица — это бинарные матрицы с постоянными диагоналями, так что для определения любой такой матрицы необходимы только первая строка и первый столбец (длина ключа равна $m+n-1$ биты).

например

$$ T_{3\times5}= \ влево [{\ начать {массив} {ccccc} 0 и 1&0&0&1 \ 1&0&1&0&0\ 0& 1&0&1&0 \ \end{массив} } \right] $$

Для аутентификации каждое сообщение представляется как двоичный вектор-столбец длины m и умножается на матрицу Теплица, а к полученному вектору применяется побитовая операция XOR для получения двоичного вектора длины n. Если бы эта операция была универсальной XOR-универсальной, ее можно было бы использовать в безусловно безопасной схеме аутентификации, выполнив также следующий шаг: )) чтобы закончить с тегом. Вторая сторона знает ключ для идентификации матрицы Теплица и ключ OTP. Для проверки подлинности она выполняет те же вычисления над m и сравнивает его с полученным тегом.

Вопрос

Я хочу доказать, что матрицы Теплица являются универсальными XOR в описанной выше схеме, чтобы выяснить, можно ли их использовать в схеме аутентификации Wegman-Carter One-Time-Pad, как описано в [2]. В своей 94-й статье Кравчик [3] показали, что матрицы Теплица, построенные с помощью LFSR, действительно являются XOR-универсальными. Но, насколько я могу судить, его конструкция дает только некоторые ограниченные тёплицевые матрицы, а его доказательство неприменимо к общему случаю. Кроме того, во всех работах, которые я пока нашел, такое доказательство цитируется Мансуром [4], который не упоминает теплыелицевые матрицы в своей статье. Поэтому мой вопрос заключается в том, знает ли кто-нибудь доказательство того, что семейство теплицевых матриц действительно является XOR-универсальным, или статью, содержащую такое доказательство.

[1]:http://liu.diva-portal.org/smash/record.jsf?pid=diva2%3A616704&dswid=3813

[2]:https://dl.acm.org/doi/10.1145/800105.803400

[3]:https://link.springer.com/chapter/10.1007/3-540-48658-5_15

[4]:https://www.sciencedirect.com/science/article/pii/030439759390257T?via%3Dihub

109
0 + 0
xor
Рейтинг:4
Daniel S avatar Crypto
флаг ru
Daniel S

Это неверно, потому что полный набор теплицевых матриц включает матрицы с недостаточным рангом. Матрицы Теплица с недостаточным рангом могут быть идентифицированы по элементам, прочитанным по вертикали снизу слева до верхнего левого угла, а затем по горизонтали вверху справа, удовлетворяющим рекурсии длины менее $n$. Генерируя матрицы с помощью LFSR, Кравчик избегал случаев недостаточного ранга.

Чтобы увидеть неуниверсальность, заметим, что все $ч$ в этом семействе линейны, поэтому вопрос эквивалентен тому, чтобы показать, что для любого $t$, $х$ у нас есть это $ч(х)=t$ верно для не более $2^{м+n-1}/2^n=2^{м-1}$ функции $ч$. Рассмотрим теперь случай $т=0$. Это будет решением тогда и только тогда, когда $х$ лежит в нулевом пространстве матрицы. Мы считаем количество $(ч, х)$ пар, для которых это верно. Каждая матрица имеет нулевое пространство размером не менее $2^{мин}$ так что есть хотя бы $|Ч|2^{м-п}$ $(ч, х)$ пары. Однако каждая матрица с недостаточным рангом будет иметь нулевое пространство размером не менее $2^{м-п+1}$ сделать по крайней мере $(|H|+|R|)2^{m-n}$ $(ч, х)$ пары где $|Р|$ — количество матриц без ранга в $Ч$. (Для матриц с недостатком ранга не менее 2 и т. д. есть еще термины, но они нам не нужны для завершения доказательства). Теперь принцип «ячейки» говорит нам, что существует по крайней мере один $х$ такие, что существует не более $(1+|R|/|H|)2^{m+n-1}2^{m-n}2^{-m}=(1+|R|/|H|)2^{m-1 }$ функции, где $ч(х)=0$ и поэтому семья не универсальна, если $|R|=0$.

Как отмечалось ранее, матрицы Теплица с недостаточным рангом соответствуют битовым последовательностям длины $m+n-1$ которые удовлетворяют рекурсии меньше, чем $n$ и есть по крайней мере $2^{n-1}-1$ такие последовательности для каждого бинарного неприводимого полинома степени $n-1$, что дает нам непустое $R$.

0 + 0
флаг us
Hernichtocles
Спасибо вам большое за ваш ответ. Я немного не уверен в размере нулевого пространства. Откуда мы знаем, что она имеет не менее $2^{m-1}$ элементов вообще и не менее $2^m$ для матриц с недостаточным рангом? Кроме того, можно ли найти некоторое $\epsilon$ такое, что семейство теплицевых матриц является $\epsilon$-почти XOR-универсальным$_2$ ? Для $\epsilon = 1+|R|/|H|$ может быть?
0
Ответить
Daniel S avatar
флаг ru
Daniel S
Можно ужесточить аргумент, чтобы показать, что существует не более $(|R_0|+2|R_1|+4|R_2|+\cdots+2^n|R_n|)2^{m-1}$ пар, где $| R_0|$ — количество матриц полного ранга, а $|R_i|$ — количество матриц ранга $n-i$. Это позволит вам вычислить соответствующий $\epsilon#, стремящийся к $1/|T|$ по мере роста $m$ относительно $n$.
0
Ответить
флаг us
Hernichtocles
Я не могу понять, почему dim(Im($h$))+dim(ker($h$))=m+n-1. Согласно теореме Ранка о ничтожности, разве это выражение не должно быть равно dim(M), которое равно m?
0
Ответить
Daniel S avatar
флаг ru
Daniel S
Извиняюсь, перечитал наспех оригинал, к концу исказился. Теперь я обновился до исправленной версии, которая, надеюсь, ясна.
1
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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