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

Daniel

30.01.2023, 11:49

Несколько статей, например, в области безопасных многосторонних вычислений, изложены в контексте, в котором область вычислений является конечным полем. $\mathbb{F}_p$, в то время как некоторые более поздние работы (например, SPDZ2k [1]) устанавливаются над (не полевым) кольцом $\mathbb{Z}_{2^k}$. Однако в некоторых случаях протоколы последнего типа несут некоторые накладные расходы.

Я думаю:

Сколько будет стоить эмуляция арифметики по модулю $2^к$, имея доступ к арифметике по простому модулю $р$?

Я даже не знаю, какой был бы естественный подход к такой задаче, хотя любое вычисление можно эмулировать с помощью полевой арифметики. Я бы разделил это на два случая: $р=2$ и $р>2^к$. В первом случае $к$Можно использовать -битный сумматор, сложность которого хорошо известна. С последним ситуация более неясная.

[1] Р. Крамер, И. Дамгард, Д. Эскудеро, П. Шолль и К. Син, «SPDZ2k: Эффективный мод MPC 2^k для нечестного большинства», в «Достижениях в области криптологии» — КРИПТО 2018, 2018, стр. 769–798.

0 + 0

многопартийное вычисление

Sam Jaques

30.01.2023, 17:01

Этим летом я потратил некоторое время на изучение этой проблемы и ничего не нашел. Лучшее, что я смог найти, это эмулировать $p=2$ с произвольным $p$: если вы ограничитесь значениями $\{0,1\}$, тогда вы можете реализовать AND$(x,y)=xy$, XOR $(x,y)=x+y-xy$ и НЕ$(x)=1-x$. Все они работают для $x,y$ по модулю $p$ для произвольного $p$. Оттуда можно построить любую схему, но конечно очень неэффективно. Основным препятствием для использования $p$-арной декомпозиции (как в двоичной системе) являются биты переноса: в двоичной системе их легко вычислить, но не для $p>2$, поскольку компараторов не существует.

Ответить

Fractalice

30.01.2023, 19:38

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

Ответить

Admin

Этот вопрос на других языках:

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?

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

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