Gerando gráficos com automorfismos triviais

14

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 .G1G2G1G2

Isso implica que possui apenas automorfismos triviais . Em outras palavras, estou assumindo a existência de algum algoritmo BPP, que funciona da seguinte maneira:G1

  1. Na entrada , gere um gráfico vertex , de modo que ele tenha apenas automorfismos triviais.1nnG1
  2. Escolha uma permutação aleatória sobre [ n ] = { 1 , 2 , , n } e aplique-a em G 1 para obter G 2 .π[n]={1,2,,n}G1G2
  3. Saída .G1,G2,π

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 .)G1G1,G2

Minha suposição é razoável? Alguém poderia me indicar algumas referências?

MS Dousti
fonte
1
Apenas algumas terminologias alternativas: Um gráfico cujo único automorfismo é a identidade é frequentemente chamado de gráfico rígido . Pode ajudar na busca de ...
Joseph O'Rourke
@ Joseph: Obrigado. Certamente ajudará!
MS Dousti 8/10/10

Respostas:

9

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.G1nnG1

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 .

Joshua Grochow
fonte
1
Obrigado Joshua. Eu tenho uma pergunta. CITAÇÃO: "o isomorfismo de gráfico regular no pior dos casos é equivalente ao isomorfismo de gráfico (no geral) no pior caso". Isso significa que, dado um oráculo que decide o isomorfismo regular do gráfico, pode-se decidir o isomorfismo do pior caso (geral) do gráfico em tempo polinomial? Você pode me fornecer algumas dicas?
MS Dousti 9/10/10
É exatamente o que isso significa. A construção não é muito difícil. Aqui está uma referência; Não sei se é o primeiro: dx.doi.org/10.1016/0022-0000(79)90043-6 também disponível em cs.cmu.edu/~glmiller/Publications/Papers/Mi79.pdf
Joshua Grochow