Estou revisando algum modelo criptográfico. Para mostrar sua inadequação, desenvolvi um protocolo artificial baseado no isomorfismo gráfico.
É "comum" (ainda controverso!) Supor a existência de algoritmos BPP capazes de gerar "instâncias concretas do problema do isomorfismo gráfico". (Juntamente com uma testemunha de isomorfismo.)
No meu protocolo artificial, assumirei a existência de tais algoritmos BPP, que atendem a um requisito adicional:
- Deixe os gráficos gerados ser e . Há apenas uma testemunha (permutação) que mapeia para .
Isso implica que possui apenas automorfismos triviais . Em outras palavras, estou assumindo a existência de algum algoritmo BPP, que funciona da seguinte maneira:
- Na entrada , gere um gráfico vertex , de modo que ele tenha apenas automorfismos triviais.
- Escolha uma permutação aleatória sobre [ n ] = { 1 , 2 , … , n } e aplique-a em G 1 para obter G 2 .
- Saída .
Eu vou assumir que, no Passo 1, podem ser gerados quando necessário, e ⟨ G 1 , G 2 ⟩ é um duro instância do problema Graph Isomorfismo. (Por favor, interprete a palavra "hard" naturalmente; uma definição formal é dada por Abadi et al. Veja também o artigo de Impaliazzo & Levin .)
Minha suposição é razoável? Alguém poderia me indicar algumas referências?
fonte
Respostas:
Pelo menos a primeira abordagem ingênua em que se possa pensar não funciona. A abordagem que tenho em mente é simplesmente gerar puramente aleatoriamente. Como quase todos os gráficos não têm simetrias (ou seja, a proporção de gráficos em n vértices sem automorfismos não triviais se aproxima de 1 como n → ∞ ), G 1 não terá automorfismos não triviais com alta probabilidade, que é o que queremos. No entanto, a versão de caso médio do isomorfismo de gráfico, onde os gráficos são escolhidos uniformemente aleatoriamente, pode ser resolvida em tempo linear [BK], de modo que isso não gera uma distribuição de instâncias concretas.G1 n n → ∞ G1
Mas uma segunda abordagem ingênua tem uma chance de funcionar: gerar um gráfico regular aleatório (de grau não constante, pois o isomorfismo do gráfico de grau constante está em P). Isso também não possui automorfismos não triviais com alta probabilidade [KSV], mas o resultado de Babai-Kucera não se aplica (como apontam no artigo). Provar que este é um gerador invulnerável obviamente requer algumas suposições, mas alguém poderia imaginar provar incondicionalmente que o isomorfismo de gráfico regular de caso médio é tão difícil quanto o isomorfismo de gráfico de pior caso, embora eu não saiba qual é a probabilidade. (Observe que o isomorfismo regular do pior caso é equivalente ao isomorfismo geral do pior caso.)
[BK] Laszlo Babai, Ludik Kucera, rotulagem canônica de gráficos em tempo médio linear . FOCS 1979, pp.39-46.
[KSV] Jeong Han Kim, Benny Sudakov e Van H. Vu. Sobre a assimetria de gráficos regulares aleatórios e gráficos aleatórios . Random Structures & Algorithms, 21 (3-4): 216–224, 2002. Também disponível aqui .
fonte