Можем ли мы построить k-мудрую независимую перестановку на [n], используя только постоянное время и пространство?

Пусть $k>0$ фиксированная константа. Для целого числа $n$ мы хотим построить перестановку $\sigma \in S_n$ такую, что:

1. Конструкция использует постоянное время и пространство (т.е. предварительная обработка требует постоянного времени и пространства). Мы можем использовать рандомизацию.

2. Учитывая $i\in[n]$ , $\sigma(i)$ может быть вычислено в постоянном времени и пространстве.

3. Перестановки $\sigma$ есть $k$ -wise независимы, то есть, для всех $i_1, \ldots, i_k$ , случайные величины $\sigma(i_1), \ldots, \sigma(i_k)$ независимы и равномерно распределены по $[n]$ .

Единственное, что я в настоящее время знаю, использует логарифмическое пространство и время полиномиального вычисления на значение $\sigma(i)$ с использованием псевдослучайных генераторов.

Фон

Для недавней работы мне понадобилось что-то похожее на вышеприведенное, и в итоге я использовал что-то более слабое: я разрешил повторные записи и убедился, что все числа, которые мне нужны, были покрыты (т.е. беспорядок). В частности, я получил $k$ независимую последовательность, которая может быть вычислена за $O(1)$ времени и с использованием постоянного пространства. Было бы неплохо иметь что-то попроще или просто знать, что известно.

Предположения

Я предполагаю модель оперативной памяти за единицу стоимости. Каждое слово в памяти / регистре имеет размер , и каждая основная арифметическая операция занимает O ( 1 ) время. Я готов принять любое разумное криптографическое предположение (односторонняя функция, дискретный журнал и т. Д.).$O(\log n)$$O(1)$

Ток чтоли

p p n a i [ p ] σ ( 1 ) , σ ( 2 ) , … , σ ( n ) k n ( 1 - 1 / e ) [ п $\sigma(x) = \sum_{i=0}^{k+2} a_i x^i \bmod p$$p$$p$$n$$a_i$$[p]$$\sigma(1), \sigma(2), \ldots, \sigma(n)$$k$$n(1-1/e)$$[n]$ появляются в этой последовательности. Обратите внимание, однако, что, поскольку числа повторяются в этой последовательности, это не перестановка.

Если вы готовы использовать криптографические методы и полагаться на криптографические предположения и принять вычислительное представление о независимости от , возможно, что шифрование с сохранением формата (FPE) может оказаться полезным. Позвольте мне набросать несколько различных конструкций такого рода.$k$

(Под «вычислительным понятием образной независимости» я имею в виду, что ни один злоумышленник с разумным временем выполнения не сможет отличить σ от k- независимой перестановки, кроме как с незначительным преимуществом. Эти схемы не будут теоретически информационными k- образными независимые, но они будут "по существу столь же хороши, как и k- независимые", если предположить, что все вычисления в пределах видимости ограничены в вычислительном отношении.)$k$$\sigma$$k$$k$$k$

Практическая схема, для меньшего $n$

В частности, используйте конструкцию FPE для построения блочного шифра (псевдослучайная перестановка, PRP) с сигнатурой . Для значений n , меньших, чем 2 128 , вероятно, наилучшей схемой является использование конструкции Фейстеля с фиксированным числом циклов (скажем, 10) и функцией округления, которая является PRF, полученной из AES. Время работы , чтобы оценить сг К ( я ) для одного значения буду АЕС вызовы. Каждый вызов AES выполняется в постоянное время.$\sigma_k : [n] \to [n]$$n$$2^{128}$$\sigma_k(i)$O ( 1 $i$$O(1)$

Наконец, отметим, что любая псевдослучайная перестановка автоматически независима. В частности, теорема Луби-Рэкоффа гарантирует, что по крайней мере с 3 раундами вы получите (приблизительную) независимость, если , предполагая, что AES безопасен. С большим количеством раундов, вероятно, будет более сильный результат, но теоремы труднее доказать и они станут более техническими, хотя широко распространено мнение, что для получения чрезвычайно высокого уровня безопасности должно быть достаточно постоянного количества раундов (и, следовательно, по существу идеального - мудрая независимость для всех разумных значений ).к к $k$$k$ к $k \ll n^{1/4}$$k$$k$

Обобщая это на большее$n$

Когда больше, вещи становятся более странными, потому что модель оперативной памяти неявно допускает параллелизм до бесплатно. Мне не ясно, какой должна быть стоимость PRP в этой модели (постоянная, с ростом , не знаю).$n$$O(\lg n)$$n$

Третья возможная конструкция

Пусть будет модулем RSA, который немного больше, чем . Определим как подгруппу содержащую элементы, чей символ Якоби равен . Определить как2 n G ( Z / m Z ) ∗ + 1 π : G → $m$$2n$$G$$(\mathbb{Z}/m\mathbb{Z})^*$$+1$$\pi : G \to G$

Затем определите помощью$\sigma$

где - случайные биективные 2-независимые хеш-функции.$f,g$

Я подозреваю, что эта конструкция имеет шанс быть (приблизительно) независимой в предположении, подобном RSA. У меня нет доказательств, только интуиция. Основная известная регулярность состоит в том, что он мультипликативно гомоморфен: . Я не знаю каких-либо других соответствующих закономерностей, даже зависимость от . Применение 2-независимого хэша до и после доказуемо устраняет эту закономерность: если является зависимой независимостью, за исключением мультипликативной гомоморфности, то 2-мудрые независимые хэши кажутся такими, что должны обеспечить полноеπ π ( x y ) = π ( x ) π ( y ) k π π k k $k$$\pi$$\pi(xy) = \pi(x) \pi(y)$$k$$\pi$$\pi$$k$$k$независимость Но это супер-отрывочные и световые годы от доказательства независимости от .$k$

Обратите внимание, что вам нужно будет использовать методы шифрования, сохраняющие формат (например, метод циклического воспроизведения), чтобы работали с а не с . Эта схема должна иметь (ожидаемое) время выполнения для оценки на заданном входе с подходящим выбором .G ( Z / m Z ) O ( 1 ) σ ( i ) i f , $f,g$$G$$(\mathbb{Z}/m\mathbb{Z})$$O(1)$$\sigma(i)$$i$$f,g$

Кроме того, в некотором смысле эта конструкция-кандидат злоупотребляет моделью ОЗУ с единичной стоимостью, полагаясь на способность работать с битными числами за времени для больших значений , что на самом деле нецелесообразно в практика. (Эта последняя конструкция не будет безопасна для малых значений , поэтому последний подход в основном полагается на режим с большими чтобы у него был шанс работать ... именно тот режим, в котором модель ОЗУ с единичной стоимостью наиболее сомнительное.)O ( 1 $\lg n$$O(1)$N $n$$n$$n$

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

Например, возможно заменить подходящей группой эллиптических кривых, так что мы имеем над (напомним, что группы эллиптических кривых обычно используют аддитивные обозначения, а не мультипликативные обозначения). Хорошая вещь об этом состоит в том, что вполне разумно предположить, что, если группа эллиптической кривой выбрана правильно, будет вести себя как «группа черного ящика», что, я думаю, может эффективно подразумевать, что будет независимый от всех «за исключением эффектов, подразумеваемых мультипликативным гомоморфизмом». У меня нет готовой конструкции, готовой предложить (недостающий фрагмент - как выбратьπ ( x ) = e x G G G π k G f , g $G$$\pi(x) = e x$$G$$G$$G$$\pi$$k$$G$и как построить и как доказать way независимость от этого), но можно было бы как-то собрать кусочки вместе.$f,g$$k$