Permutação finita de mão única com domínio infinito

10

Seja uma permutação. Observe que enquanto atua em um domínio infinito, sua descrição pode ser finita. Por descrição , quero dizer um programa que descreve a funcionalidade do \ pi . (Como na complexidade de Kolmogorov.) Veja as explicações abaixo.π:{0,1}{0,1}ππ

Por exemplo, a função NOT é uma dessas permutações:

função NÃO (x)
    Seja y = x
    Para i = 1 a | x |
        Virar o i-ésimo pedaço de y
    retornar y

πk() , definido abaixo, é outro caso:

função pi_k (x)
    retornar x + k (mod 2 ^ | x |)

Minha pergunta é sobre uma classe especial de permutações, chamada permutações de mão única . Informalmente, são permutações fáceis de calcular, mas difíceis de inverter (para uma máquina BPP ). A mera existência de permutações unidirecionais é um problema aberto de longa data na criptografia e na teoria da complexidade; no entanto, no restante, assumiremos que elas existem.

Como exemplo de uma permutação unidirecional conjecturada, pode-se considerar o RSA : Seja n=pq um número inteiro de Blum e seja e=65537 . A permutação unidirecional é definida por: πn(x)=xemodn .

Observe que o RSA é definido sobre o domínio finito . De fato, para obter uma permutação de domínio infinito, é preciso considerar uma família de permutações de RSA , em que é um conjunto infinito de números inteiros de Blum. Observe que é a descrição da família e, por definição, é infinita.Zn{πn}nDDD

Minha pergunta é (assumindo a existência de permutações unidirecionais):

Existem permutações unidirecionais de descrição finita sobre um domínio infinito ?

A resposta pode variar: Pode ser positiva, negativa ou aberta (com probabilidade de ser positiva ou com probabilidade de ser negativa ).

fundo

A questão surgiu quando eu estava lendo um artigo da ASIACRYPT 2009 . Lá, o autor implicitamente (e no contexto de alguma prova) assumiu que tais permutações unidirecionais existem.

Ficarei feliz se esse for realmente o caso, embora não tenha conseguido encontrar uma prova.

MS Dousti
fonte
Não podemos descrever finitamente ? Existe um algoritmo finito procurando um menor número de Blum maior que algum número de entrada, de modo que a computação possa ser descrita, por exemplo, como "encontre o menor número Blum maior que , depois calcule ". Ainda assim, não é óbvio para mim que a função que você obterá colando um número infinito de 's será necessariamente uma permutação. Você poderia explicar? Dπ(x)bxπb(x)πb
Karolina Sołtys 6/11/10
@Karolina: Obrigado pela resposta. Eu acho que o algoritmo "encontre o menor número de Blum maior que , depois calcule " necessariamente exibirá informações extras sobre , como sua fatoração. Portanto, esse algoritmo não pode ser usado para descrever permutações unidirecionais . Você concorda? bxπb(x)b
MS Dousti 6/11/10
Ok, acho que entendi - você deseja que a descrição finita descreva a função de uma maneira fácil de calcular. Penso que poderíamos codificar a parte "encontre o menor número de Blum ..." sem revelar qualquer informação sobre (basta implementar a pesquisa de força bruta para ), mas não seria computável com eficiência. bb
Karolina Sołtys 6/11/10
Talvez esta pergunta vai ajudar com ideias: cstheory.stackexchange.com/questions/1378
Matt Groff
@ Matt: Obrigado. Nessa questão, a condição "fácil de calcular, mas difícil de inverter" não se aplica às máquinas com limite de tempo poli.
MS Dousti

Respostas:

14

O artigo Sobre a construção de 1-1 Funções unidirecionais, de Goldreich, Levin e Nisan, mostra como construir funções de preservação de comprimento 1-1 com domínios infinitos e descrição finita. A dureza de inverter as funções é baseada em suposições populares, como a dureza de inverter o RSA ou encontrar logaritmos discretos.

Sua construção é uma torção da idéia direta de converter uma família, , de funções unidirecionais em uma única função unidirecional, definindo onde é o aleatoriedade usado para escolher o índice e é a aleatoriedade utilizado para seleccionar a entrada (dado o índice ).{fi}if(r,s)=fi(x)risxi

O problema com a idéia acima é que não é necessariamente 1-1. Eles corrigem esse problema modificando levemente e argumentando que, sob certas condições da família , a nova construção é realmente 1-1. Eles então mostram que essas condições são satisfeitas pelas funções baseadas em RSA / Discrete-log.f(r,s)f(r,s){fi}i

Alon Rosen
fonte
11
Obrigado Alon pela sua excelente resposta. Fora do tópico: estou muito feliz em vê-lo aqui. Adoro o seu livro e documentos sobre conhecimento zero simultâneo !
MS Dousti 10/11/10
Thans, Sadeq. Fico feliz em ouvir que você gosta :-)
Alon Rosen