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

Daniel

1/30/23, 11:49 AM

Several papers in, for example, the domain of Secure Multiparty Computation, are set in the context in which the computation domain is a finite field $\mathbb{F}_p$, while some more recent works (e.g. SPDZ2k [1]) are set over a (non-field) ring $\mathbb{Z}_{2^k}$. In some cases, however, the latter-type of protocols carry some overheads.

I wonder:

What would be the cost of emulating arithmetic modulo $2^k$, when having access to arithmetic modulo a prime $p$?

I don't even know what would be a natural approach to such task, even though every computation can be emulated with field arithmetic. I would split this into two cases: $p=2$ and $p>2^k$. In the former, a $k$-bit adder can be used, whose complexity is well known. For the latter, the situation is more unclear.

[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

multiparty-computation

Sam Jaques

1/30/23, 5:01 PM

I spent some time looking at this problem this summer and found nothing. The best I could find is to emulate $p=2$ with arbitrary $p$: If you restrict to $\{0,1\}$ values, then you can implement AND$(x,y)=xy$, XOR$(x,y)=x+y-xy$, and NOT$(x)=1-x$. All of these work for $x,y$ modulo $p$ for arbitrary $p$. From there you can build any circuit, but of course very inefficiently. A major obstacle to using a $p$-ary decomposition (like in binary) is carry bits: in binary these are easy to calculate, but not for $p>2$ because comparators don't exist.

Fractalice

1/30/23, 7:38 PM

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

Elon Musk

I sit in a Tesla and translated this thread with Ai:

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?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.