înregistrare Logare
Puncte:3
avatar Crypto

Dovada că familia Matricelor Toeplitz este XOR-Universală

drapel us
Hernichtocles

Definiția funcțiilor hash XOR-Universal de către Abidin[1]:

O clasa $H$ a funcţiilor hash din $M$ la $T$ este XOR-Universal$_2$ ($XU_2$) dacă există cel mult $|H|/|T|$ funcții hash $h$ $\în$ $H$ astfel încât $(h(m_1) = h(m_2$) $\oplus t)$ pentru oricare două distincte $m_1$, $m_2$ $\în$ $M$ și orice $t \în T$.

Dacă există cel mult $\epsilon|H|$ funcții hash în schimb, pentru $\epsilon > 1/|T|$, clasa $H$ este $\epsilon$-Aproape-XOR-Universal$_2$ ($\epsilon-AXU_2$).

$M$ este setul care conține toate mesajele (toate șirurile de biți de lungime m în acest caz)

$T$ este setul tuturor etichetelor posibile (toate șirurile de biți de lungime n în acest caz)

$H$ este setul care conține toate funcțiile hash posibile

$|H|$ se referă la numărul de funcții hash (Pentru $n$ X $m$ Matrice Toeplitz $|H|$ = $2^{m + n-1}$).

$|T|$ se referă la dimensiunea setului $T$.

Toeplitz-Matrici pentru autentificare

Matricele Toeplitz sunt matrici binare cu diagonale constante, astfel încât doar primul rând și coloana sunt necesare pentru a specifica orice astfel de matrice (lungimea cheii a $m+n-1$ biți).

de exemplu.

$$ T_{3\times5}= \left[{\begin{array}{ccccc} 0 & 1&0&0&1 \ 1&0&1&0&0\ 0& 1&0&1&0 \ \end{matrice} } \right] $$

Pentru autentificare, fiecare mesaj este reprezentat ca un vector coloană binar de lungime m și înmulțit cu o matrice Toeplitz și vectorului rezultat se aplică operația XOR pe biți pentru a primi un vector binar de lungime n. Dacă această operațiune ar fi XOR-universală, ar putea fi utilizată într-o schemă de autentificare necondiționată sigură, efectuând, de asemenea, următorul pas: Rezultatul este XOR cu un șir de biți uniform de lungime n (criptare One-Time-Pad (OTP). )) pentru a ajunge cu eticheta. A doua parte cunoaște cheia pentru a identifica matricea Toeplitz și cheia OTP. Pentru a verifica autenticitatea, ea efectuează aceleași calcule pe m și îl compară cu eticheta primită

Întrebare

Vreau să demonstrez că matricele Toeplitz sunt XOR-universale în schema descrisă mai sus pentru a afla dacă pot fi utilizate într-o schemă de autentificare Wegman-Carter One-Time-Pad, așa cum este descris în [2]. În lucrarea sa din 94, Krawczyk [3] a arătat că matricele Toeplitz construite cu un LFSR sunt într-adevăr XOR-universale. Dar, din câte îmi pot da seama, construcția lui dă doar anumite matrici Toeplitz limitate și demonstrația sa nu este aplicabilă cazului general. În plus, orice lucrare pe care am găsit-o până acum îl citează pe Mansour [4] pentru o astfel de dovadă, care nu menționează matrice Toeplitz în lucrarea sa. Prin urmare, întrebarea mea este dacă cineva cunoaște o dovadă care să arate că familia de matrici Toeplitz este într-adevăr XOR-Universal sau o lucrare care conține o astfel de dovadă.

[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
Puncte:4
Daniel S avatar Crypto
drapel ru
Daniel S

Nu este adevărat, deoarece setul complet de matrici Toeplitz include matrici cu deficiențe de rang. Matricele Toeplitz cu rang deficitar pot fi identificate prin intrările citite vertical de la stânga jos la stânga sus și apoi orizontal la dreapta sus, satisfac o recursivitate de lungime mai mică decât $n$. Prin generarea de matrici folosind un LFSR, Krawczyk a evitat cazurile de rang deficitar.

Pentru a vedea non-universalitatea, observăm că toate $h$ în această familie sunt liniare și astfel întrebarea este echivalentă cu a arăta că pentru oricare $t$, $x$ avem asta $h(x)=t$ este valabil pentru cel mult $2^{m+n-1}/2^n=2^{m-1}$ funcții $h$. Luați în considerare acum cazul $t=0$. Aceasta va fi o soluție dacă și numai dacă $x$ se află în spațiul nul al matricei. Numărăm numărul de $(h,x)$ perechi pentru care acest lucru este adevărat. Fiecare matrice are cel puțin un spațiu nul de dimensiune $2^{m-n}$ astfel încât să existe măcar $|H|2^{m-n}$ $(h,x)$ perechi. Cu toate acestea, fiecare matrice cu deficit de rang va avea cel puțin un spațiu nul de dimensiune $2^{m-n+1}$ făcând cel puțin $(|H|+|R|)2^{m-n}$ $(h,x)$ perechi unde $|R|$ este numărul de matrice cu deficit de rang în $H$. (Există mai mulți termeni pentru matrice cu deficiență de rang de cel puțin 2 și așa mai departe, dar nu avem nevoie de aceștia pentru a finaliza demonstrația). Principiul porumbeilor ne spune acum că există cel puțin unul $x$ astfel încât există cel mult $(1+|R|/|H|)2^{m+n-1}2^{m-n}2^{-m}=(1+|R|/|H|)2^{m-1 }$ funcţii unde $h(x)=0$ şi astfel familia nu este universală decât dacă $|R|=0$.

După cum s-a menționat anterior, matricele Toeplitz cu deficiențe de rang corespunde secvențelor de biți de lungime $m+n-1$ care satisfac o recursivitate mai mică decât $n$ și există cel puțin $2^{n-1}-1$ astfel de secvențe pentru fiecare polinom binar ireductibil de grad $n-1$, oferindu-ne un non-gol $R$.

0 + 0
drapel us
Hernichtocles
Multumesc foarte mult pentru raspuns. Sunt puțin sigur de dimensiunea spațiului nul. De unde știm că are cel puțin $2^{m-1}$ elemente în general și cel puțin $2^m$ pentru matricele deficitare de rang? De asemenea, este posibil să găsim niște $\epsilon$ astfel încât familia de matrici Toeplitz să fie $\epsilon$-Almost-XOR-Universal$_2$? Pentru $\epsilon = 1+|R|/|H|$ poate?
0
Răspunde
Daniel S avatar
drapel ru
Daniel S
Se poate întări argumentul pentru a arăta că există cel mult $(|R_0|+2|R_1|+4|R_2|+\cdots+2^n|R_n|)2^{m-1}$ perechi unde $| R_0|$ este numărul de matrici de rang complet și $|R_i|$ este numărul de matrici de rang $n-i$. Acest lucru v-ar permite să calculați un $\epsilon# adecvat care ar tinde spre $1/|T|$ pe măsură ce $m$ crește față de $n$.
0
Răspunde
drapel us
Hernichtocles
Nu pot să-mi dau seama de ce dim(Im($h$))+dim(ker($h$))=m+n-1. Conform teoremei de nulitate Rank, nu ar trebui acea expresie să fie egală cu dim(M) care este m?
0
Răspunde
Daniel S avatar
drapel ru
Daniel S
Scuze, recitind originalul grăbit, a devenit deranjat spre final. Am actualizat acum o versiune corectată care sper că este clară.
1
Răspunde
drapel romania
SEF 777
întrebarea această in alte limbi:

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.