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

10

Seja k>0 uma constante fixa. Dado um número inteiro n , queremos construir uma permutação σSn 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[n] , σ(i) pode ser calculado em tempo e espaço constantes.

  3. A permutação σ é independente do sentido k , ou seja, para todo i1,,ik , as variáveis ​​aleatórias σ(i1),,σ(ik) 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 σ(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(logn)O(1)

Coisa atual

p p n um i [ p ] σ ( 1 ) , σ ( 2 ) , ... , σ ( n ) k N ( 1 - 1 / e ) [ n ]σ(x)=i=0k+2aiximodpppnai[p]σ(1),σ(2),,σ(n)kn(11/e)[n] aparece nesta sequência. Observe, no entanto, que, como os números se repetem nessa sequência, não é uma permutação.

Sariel Har-Peled
fonte
11
Não. Em tempo constante, você só pode fornecer uma quantidade constante de saída; portanto, para qualquer algoritmo de tempo constante, para suficientemente grande , os suportes das variáveis ​​aleatórias na condição 3 serão subconjuntos estritos de . [ n ]n[n]
2
Eu exijo uma quantidade constante de cálculo por entrada da permutação - para que o tempo total de computação possa ser linear para toda a permutação.
Sariel Har-Peled
11
Quanto ao espaço - estou assumindo a palavra modelo -, cada palavra ocupa uma quantidade constante de espaço, mesmo que tenha um número logarítmico de bits.
Sariel Har-Peled
11
Solução parcial: suponha que seja uma potência primária . Seja um campo com . Defina para a aleatória com . Então é uma permutação independente por pares em elementos que podem ser calculados em "tempo constante". Talvez isso generalize. nk=2F|F|=nσ(x)=ax+ba,bFa0σn
Thomas
11
Yeh. Eu sabia disso ;). O problema é que deve ser muito maior, e apenas os polinômios lineares são permutações, não os de maior grau. k
Sariel Har-Peled

Respostas:

3

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σkkk

Um esquema prático, para menoresn

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.σk:[n][n]n2128σk(i)iO(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 ).kkkn1/4kk

Generalizando isso para maiorn

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).nO(lgn)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 porm2nG(Z/mZ)+1π:GG

π(x)=x3modm.

Em seguida, defina porσ

σ(i)=g(π(f(i)),

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 completokππ(xy)=π(x)π(y)kππkkindependê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,gG(Z/mZ)O(1)σ(i)if,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.)lgnO(1)nnn

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 GGπ(x)=exGG π k G f , g kGGπkGe como construir como provar independência -wise disso), mas pode ser possível juntar as peças de alguma maneira.f,gk

DW
fonte
Isso é muito interessante - estou viajando pelas próximas semanas, mas analisaria isso quando voltasse. Obrigado!
Sariel Har-Peled,