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.
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
, 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 ). 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 um número inteiro de Blum e seja . A permutação unidirecional é definida por: .
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.
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.
fonte
Respostas:
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}i f(r,s)=fi(x) r i s x i
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
fonte