Care este costul emulării aritmeticii inelare (să spunem modulo $2^k$) pe un câmp finit prim?

Daniel

30.01.2023, 11:49

Mai multe lucrări din, de exemplu, domeniul Secure Multiparty Computation, sunt stabilite în contextul în care domeniul de calcul este un câmp finit $\mathbb{F}_p$, în timp ce unele lucrări mai recente (de exemplu, SPDZ2k [1]) sunt setate pe un inel (fără câmp) $\mathbb{Z}_{2^k}$. În unele cazuri, totuși, acest din urmă tip de protocoale implică unele cheltuieli generale.

Ma intreb:

Care ar fi costul emulării modulo aritmetic $2^k$, când aveți acces la aritmetică modulo un prim $p$?

Nici măcar nu știu care ar fi o abordare naturală a unei astfel de sarcini, chiar dacă fiecare calcul poate fi emulat cu aritmetica câmpului. Aș împărți asta în două cazuri: $p=2$ și $p>2^k$. În primul, a $k$Se poate folosi -bit adder, a cărui complexitate este binecunoscută. Pentru cei din urmă, situația este mai neclară.

[1] R. Cramer, I. DamgÃ¥rd, D. Escudero, P. Scholl, and C. Xing, âSPDZ2k: Efficient MPC mod 2^k for Dishonest Majority,â in Advances in Cryptology â CRYPTO 2018, 2018, pp. 769–798.

0 + 0

multipartid-calculator

Sam Jaques

30.01.2023, 17:01

Am petrecut ceva timp la această problemă vara aceasta și nu am găsit nimic. Cel mai bun lucru pe care l-am putut găsi este să emulez $p=2$ cu $p$ arbitrar: dacă restricționați la valori $\{0,1\}$, atunci puteți implementa AND$(x,y)=xy$, XOR $(x,y)=x+y-xy$ și NU$(x)=1-x$. Toate acestea funcționează pentru $x,y$ modulo $p$ pentru $p$ arbitrar. De acolo poți construi orice circuit, dar bineînțeles foarte ineficient. Un obstacol major în calea utilizării unei descompunere $p$-ary (ca în binar) este biții de transport: în binar aceștia sunt ușor de calculat, dar nu pentru $p>2$ deoarece comparatorii nu există.

Răspunde

Fractalice

30.01.2023, 19:38

@SamJaques $XOR(x,y) = x+y-2xy$

Răspunde

SEF 777

întrebarea această in alte limbi:

EN: What is the cost of emulating ring arithmetic (say modulo $2^k$) over a prime finite field?

TH: ค่าใช้จ่ายในการจำลองวงแหวนเลขคณิต (เช่น modulo $2^k$) บนฟิลด์จำกัดเฉพาะมีค่าเท่าใด

RO: Care este costul emulării aritmeticii inelare (să spunem modulo $2^k$) pe un câmp finit prim?

RU: Какова стоимость эмуляции кольцевой арифметики (скажем, по модулю $2^k$) над простым конечным полем?

VI: Chi phí mô phỏng số học vòng (giả sử modulo $2^k$) trên một trường hữu hạn nguyên tố là bao nhiêu?

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.