Peut-on construire une permutation indépendante k-sage sur [n] en utilisant uniquement le temps et l'espace constants?

Soit $k>0$ une constante fixe. Etant donné un entier $n$ , nous voulons construire une permutation $\sigma \in S_n$ telle que:

1. La construction utilise un temps et un espace constants (c'est-à-dire que le prétraitement prend un temps et un espace constants). Nous pouvons utiliser la randomisation.

2. Étant donné $i\in[n]$ , $\sigma(i)$ peut être calculé en temps et en espace constants.

3. La permutation $\sigma$ est indépendante de $k$ , c'est-à-dire que pour tout $i_1, \ldots, i_k$ , les variables aléatoires $\sigma(i_1), \ldots, \sigma(i_k)$ sont indépendantes et uniformément réparties sur $[n]$ .

La seule chose que je connaisse actuellement utilise l'espace logarithmique et le temps de calcul polynomial par valeur de $\sigma(i)$ aide de générateurs pseudo-aléatoires.

Contexte

J'avais besoin de quelque chose comme ce qui précède pour certains travaux récents, et j'ai fini par utiliser quelque chose de plus faible: j'ai autorisé des entrées répétées et vérifié que tous les numéros dont j'avais besoin étaient couverts (c'est-à-dire un gâchis). Plus précisément, j'ai obtenu une séquence indépendante dans le sens $k$ qui peut être calculée en temps $O(1)$ et en utilisant un espace constant. Ce serait bien d'avoir quelque chose de plus simple, ou simplement de savoir ce qui est connu.

Hypothèses

Je suppose que le modèle de RAM à coût unitaire. Chaque mot dans la mémoire / le registre est de taille , et chaque opération arithmétique de base prend O ( 1 ) . Je suis prêt à assumer toute hypothèse cryptographique raisonnable (fonction unidirectionnelle, journal discret, etc.).$O(\log n)$$O(1)$

Actuel truc

p p n a 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]$ apparaît dans cette séquence. Notez, cependant, que puisque les nombres se répètent dans cette séquence, ce n'est pas une permutation.

Si vous êtes prêt à utiliser des techniques cryptographiques et à vous fier à des hypothèses cryptographiques et à accepter une notion informatique d' indépendance -wise, il est possible que le chiffrement préservant le format (FPE) puisse être utile. Permettez-moi d'esquisser quelques constructions différentes de ce genre.$k$

(Par "notion de calcul de l' indépendance sensée", je veux dire qu'aucun adversaire avec un temps d'exécution raisonnable ne peut distinguer σ d'une permutation indépendante k- sens, sauf avec un avantage négligeable. Ces schémas ne seront théoriquement pas k- sens indépendants, mais ils seront "essentiellement aussi bons que k -wise indépendants", en supposant que tout le calcul en vue est borné par le calcul.)$k$$\sigma$$k$$k$$k$

Un schéma pratique, pour les petits $n$

En particulier, utilisez une construction FPE pour construire un chiffrement par blocs (permutation pseudo-aléatoire, PRP) avec la signature . Pour des valeurs de n inférieures à 2 128 , le meilleur schéma est probablement d'utiliser une construction de Feistel avec un nombre fixe de tours (disons, 10) et une fonction de tour qui est un PRF dérivé d'AES. Le temps d'exécution pour évaluer σ k ( i ) pour une seule valeur de i sera O ( 1 ) invocations AES. Chaque appel AES s'exécute en temps constant.$\sigma_k : [n] \to [n]$$n$$2^{128}$$\sigma_k(i)$$i$$O(1)$

Enfin, notez que toute permutation pseudo-aléatoire est automatiquement indépendante dans le sens . En particulier, le théorème Luby-Rackoff garantit au moins 3 tours, vous obtenez (environ) k L' indépendance -wise si k « n 1 / 4 , en supposant AES est sécurisé. Avec plus de tours, il est probable qu'il y aura un résultat plus fort, mais les théorèmes sont plus difficiles à prouver et deviennent plus techniques, bien qu'il soit largement admis qu'un nombre constant de tours devrait suffire pour obtenir une sécurité extrêmement élevée (et donc essentiellement parfait k - sage indépendance pour toutes les valeurs raisonnables de k ).$k$$k$$k \ll n^{1/4}$$k$$k$

Généraliser ceci à un n plus grand$n$

Lorsque est plus grand, les choses deviennent plus étranges, car le modèle de RAM à coût unitaire autorise implicitement jusqu'à O ( lg n ) parallélisme gratuitement. Ce n'est pas clair pour moi quel devrait être le coût des PRP dans ce modèle (constant? Croissant avec n ? Je ne sais pas).$n$$O(\lg n)$$n$

Une troisième construction possible

Soit un module RSA légèrement supérieur à 2 n . Définissez G comme le sous-groupe de ( Z / m Z ) ∗ contenant les éléments dont le symbole Jacobi est + 1 . Définissez π : G → G par$m$$2n$$G$$(\mathbb{Z}/m\mathbb{Z})^*$$+1$$\pi : G \to G$

Ensuite, définissez par$\sigma$

où sont des fonctions de hachage indépendantes bijectives aléatoires 2.$f,g$

Je soupçonne que cette construction a une chance d'être (approximativement) indépendante dans le sens , sous une hypothèse de type RSA. Je n'ai aucune preuve, juste une intuition. La principale régularité connue de π est qu'elle est homomorphique multiplicative: π ( x y ) = π ( x ) π ( y ) . Je ne connais aucune autre régularité pertinente, même une dépendance k -wise. L'application d'un hachage indépendant de 2 avant et après π élimine de façon prouvée cette régularité: si π est $k$$\pi$$\pi(xy) = \pi(x) \pi(y)$$k$$\pi$$\pi$$k$indépendance dans le sens des deux sauf pour l'homomorphicité multiplicative, alors les hachages indépendants sur 2 semblent devoir fournir une indépendance complète dans le sens . Mais c'est super-sommaire et des années-lumière d'une preuve d' indépendance k -wise.$k$$k$

Notez que vous devrez utiliser des techniques de chiffrement préservant le format (par exemple, la technique de cyclage) pour vous assurer que fonctionne sur G plutôt que sur ( Z / m Z ) . Ce schéma devrait avoir un temps d'exécution O ( 1 ) (prévu) pour évaluer σ ( i ) à une entrée donnée i , avec un choix approprié de f , g .$f,g$$G$$(\mathbb{Z}/m\mathbb{Z})$$O(1)$$\sigma(i)$$i$$f,g$

En outre, dans un certain sens, cette construction candidate abuse du modèle de RAM à coût unitaire en s'appuyant sur la capacité à fonctionner sur des nombres bits en temps O ( 1 ) , pour des valeurs élevées de n , ce qui n'est pas vraiment raisonnable en pratique . (Cette dernière construction ne sera pas sécurisée pour les petites valeurs de n , donc cette dernière approche repose fondamentalement sur le grand régime n pour qu'il ait une chance de fonctionner ... exactement le régime où le modèle de RAM à coût unitaire est le plus douteux.)$\lg n$$O(1)$$n$$n$$n$

J'admets librement que celui-ci est assez extensible, mais je le mentionne au cas où il déclencherait une inspiration pour une meilleure solution.

Par exemple, il pourrait être possible de remplacer par un groupe de courbes elliptiques approprié, de sorte que nous ayons π ( x ) = e x sur G (rappelons que les groupes de courbes elliptiques utilisent généralement la notation additive plutôt que la notation multiplicative). La bonne chose à ce sujet est qu'il n'est pas totalement déraisonnable de conjecturer que, si le groupe de courbes elliptiques G est choisi correctement, G se comportera comme un "groupe de boîtes noires", ce qui, je pense, pourrait effectivement impliquer que π sera $G$$\pi(x) = e x$$G$$G$$G$$\pi$$k$indépendant des sens "sauf pour les effets induits par l'homomorphisme multiplicatif". Je n'ai pas de construction complète prête à proposer (la pièce manquante est de savoir comment choisir et comment construire f , g et comment prouver l' indépendance k par rapport à cela), mais il pourrait être possible de rassembler les pièces d'une manière ou d'une autre .$G$$f,g$$k$