Podemos construir uma permutação independente k-wise em [n] usando apenas tempo e espaço constantes?

Seja $k>0$ uma constante fixa. Dado um número inteiro $n$ , queremos construir uma permutação $\sigma \in S_n$ tal que:

1. A construção utiliza tempo e espaço constantes (ou seja, o pré-processamento leva tempo e espaço constantes). Nós podemos usar a randomização.

2. Dado $i\in[n]$ , $\sigma(i)$ pode ser calculado em tempo e espaço constantes.

3. A permutação $\sigma$ é independente do sentido $k$ , ou seja, para todo $i_1, \ldots, i_k$ , as variáveis ​​aleatórias $\sigma(i_1), \ldots, \sigma(i_k)$ são independentes e distribuídas uniformemente por $[n]$ .

A única coisa que sei atualmente usa espaço logarítmico e tempo de computação polinomial por valor de $\sigma(i)$ usando geradores pseudo-aleatórios.

fundo

Eu precisava de algo parecido com o descrito acima para alguns trabalhos recentes, e acabei usando algo mais fraco: permiti entradas repetidas e verifiquei que todos os números necessários eram cobertos (por exemplo, uma bagunça). Especificamente, obtive uma sequência independente $k$ -wise que pode ser calculada no tempo $O(1)$ e usando espaço constante. Seria bom ter algo mais simples, ou apenas saber o que é conhecido.

Premissas

Estou assumindo o modelo de RAM de custo unitário. Cada palavra na memória / registro é do tamanho , e toda operação aritmética básica leva O ( 1 ) tempo. Estou disposto a assumir qualquer suposição criptográfica razoável (função unidirecional, log discreto, etc.).$O(\log n)$$O(1)$

Coisa atual

p p n um i [ p ] σ ( 1 ) , σ ( 2 ) , ... , σ ( n ) k N ( 1 - 1 / e ) [ n $\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]$ aparece nesta sequência. Observe, no entanto, que, como os números se repetem nessa sequência, não é uma permutação.

Se você estiver disposto a usar técnicas criptográficas e confiar em suposições criptográficas e aceitar uma noção computacional de independência -wise, é possível que a criptografia de preservação de formato (FPE) possa ser útil. Deixe-me esboçar algumas construções diferentes desse tipo.$k$

(Por "noção computacional de independência -wise", quero dizer que nenhum adversário com um tempo de execução razoável pode distinguir de uma permutação independente -wise, exceto com vantagem insignificante. Esses esquemas não serão teoricamente informações - sábio independente, mas eles serão "essencialmente tão bons quanto independentes do sentido ", supondo que todo o cálculo à vista seja computacionalmente limitado.)$k$$\sigma$$k$$k$$k$

Um esquema prático, para menores$n$

Em particular, use uma construção FPE para criar uma cifra de bloco (permutação pseudo-aleatória, PRP) com a assinatura . Para valores de menores que , provavelmente o melhor esquema é usar uma construção Feistel com um número fixo de rodadas (digamos, 10) e uma função de rodada que é um PRF derivado do AES. O tempo de execução para avaliar para um único valor de será invocações AES. Cada chamada do AES é executada em tempo constante.$\sigma_k : [n] \to [n]$$n$$2^{128}$$\sigma_k(i)$$i$$O(1)$

Finalmente, observe que qualquer permutação pseudo-aleatória é automaticamente -wise independente. Em particular, o teorema de Luby-Rackoff garante que, com pelo menos três rodadas, você obtém independência (aproximada) -wise se , assumindo que o AES seja seguro. Com mais rodadas, é provável que haja um resultado mais forte, mas os teoremas são mais difíceis de provar e se tornam mais técnicos, embora se acredite amplamente que um número constante de rodadas seja suficiente para obter segurança extremamente alta (e, portanto, perfeito - independência sábia para todos os valores razoáveis ​​de ).$k$$k$$k \ll n^{1/4}$$k$$k$

Generalizando isso para maior$n$

Quando é maior, as coisas ficam mais estranhas, porque o modelo de RAM de custo unitário permite implicitamente até paralelismo de graça. Não está claro para mim qual deve ser o custo dos PRPs nesse modelo (constante? Aumentando com ? Não sei).$n$$O(\lg n)$$n$

Uma terceira construção possível

Seja um módulo RSA um pouco maior que . Defina como o subgrupo de contém os elementos cujo símbolo Jacobi é . Definir por$m$$2n$$G$$(\mathbb{Z}/m\mathbb{Z})^*$$+1$$\pi : G \to G$

Em seguida, defina por$\sigma$

onde são funções hash independentes bijetivas 2 aleatórias.$f,g$

Suspeito que essa construção tenha a chance de ser (aproximadamente) independente do sentido , sob uma suposição do tipo RSA. Não tenho provas, apenas uma intuição. A principal regularidade conhecida de é que é multiplicativamente homomórfica: . Não conheço outras regularidades relevantes, nem mesmo a dependência -wise. A aplicação de um hash 2 independente antes e depois de elimina essa regularidade: se é independência -wise, exceto a homomorfia multiplicativa, os hashes independentes bidimensionais parecem fornecer completo$k$$\pi$$\pi(xy) = \pi(x) \pi(y)$$k$$\pi$$\pi$$k$$k$independência senão. Mas isso é super esboçado e anos-luz de uma prova da independência -wise.$k$

Observe que você precisará usar técnicas de criptografia de preservação de formato (por exemplo, a técnica de ciclismo) para garantir que funcione em e não em . Esse esquema deve ter tempo de execução (esperado) para avaliar em uma determinada entrada , com a opção adequada de .$f,g$$G$$(\mathbb{Z}/m\mathbb{Z})$$O(1)$$\sigma(i)$$i$$f,g$

Além disso, em certo sentido, essa construção candidata está abusando do modelo de RAM de custo unitário, confiando na capacidade de operar em números de bits no tempo , para grandes valores de , o que não é realmente razoável em prática. (Esta última construção não será segura para pequenos valores de , assim que esta última abordagem baseia-se fundamentalmente sobre a larga regime para que ele tenha uma chance de trabalhar ... exatamente o regime onde o modelo RAM unidade de custo é mais duvidoso.)$\lg n$$O(1)$$n$$n$$n$

Admito livremente que este é um exagero, mas mencionei no caso de gerar alguma inspiração para uma solução melhor.

Por exemplo, pode ser possível substituir por um grupo de curvas elípticas adequado, para que tenhamos sobre (lembre-se de que os grupos de curvas elípticas geralmente usam notação aditiva em vez de notação multiplicativa). O bom disso é que não é totalmente irracional supor que, se o grupo de curvas elípticas for escolhido corretamente, se comportará como um "grupo de caixa preta", que eu acho que pode implicar efetivamente que será independente do sentido ", exceto pelos efeitos implícitos no homomorfismo multiplicativo". Não tenho uma construção completa pronta para propor (a peça que falta é como escolherπ ( x ) = e x $G$$\pi(x) = e x$$G$G π k G f , g $G$$G$$\pi$$k$$G$e como construir como provar independência -wise disso), mas pode ser possível juntar as peças de alguma maneira.$f,g$$k$