A criptografia tem um custo termodinâmico inerente?

19

A computação reversível é um modelo computacional que permite apenas operações termodinamicamente reversíveis. De acordo com o princípio de Landauer, que afirma que apagar um pouco de informação libera joules de calor, isso exclui as funções de transição que não são individuais (por exemplo, os operadores booleanos AND e OR). É sabido que a computação quântica é inerentemente reversível porque as operações permitidas na computação quântica são representadas por matrizes unitárias.kTln(2)

Esta pergunta é sobre criptografia. Informalmente, a noção de "reversibilidade" parece anátema aos objetivos fundamentais da criptografia, sugerindo a pergunta: "A criptografia tem um custo termodinâmico inerente?"

Acredito que essa é uma pergunta diferente de "Tudo pode ser feito em quantum?"

Em suas notas de aula , o Dr. Preskill afirma: "Existe uma estratégia geral para simular uma computação irreversível em um computador reversível. Cada porta irreversível pode ser simulada por uma porta de Toffoli, fixando entradas e ignorando saídas. Acumulamos e salvamos todo o lixo" 'bits de saída necessários para reverter as etapas da computação ".

Isso sugere que essas simulações quânticas reversíveis de operações irreversíveis exigem uma entrada, além de algum espaço "zero". Em seguida, a operação gera saída juntamente com alguns bits de rascunho "sujos". As operações são todas reversíveis em relação à saída mais bits de lixo, mas em algum momento, os bits de lixo são "jogados fora" e não são considerados mais.

Como a criptografia depende da existência de funções unidirecionais de alçapão, uma declaração alternativa da pergunta pode ser: "Existem funções unidirecionais de alçapão que podem ser implementadas usando apenas operações lógicas reversíveis, sem espaço adicional?" Em caso afirmativo, também é possível COMPUTAR uma função unidirecional arbitrária de alçapão usando apenas operações reversíveis (e sem espaço para riscos)?

rphv
fonte
2
uma pergunta interessante.
Suresh Venkat
4
Presumivelmente, essa pergunta se aplica apenas à criptografia de chave pública. Os sistemas de criptografia simétricos (como o DES) não podem ser totalmente reversíveis?
quer
11
Porra, escrevi esse último comentário tarde da noite e fiz uma bagunça. O que eu deveria ter dito foi que o custo termodinâmico é independente do tamanho do espaço temporário para sistemas de chave pública e privada, pois você pode simplesmente executar a computação reversível, copiando os bits de saída (mas não o espaço temporário) para uma ancilla registre e inverta a computação original (desconectando tudo no espaço de trabalho).
Joe Fitzsimons

Respostas:

14

Como mencionei no meu comentário acima, e como você menciona na pergunta, todo cálculo pode ser reversível e, simplesmente mantendo os bits extras, não há custo termodinâmico inerente.

Todo circuito gerado usando portões e ancillas Toffoli para substituir portões irreversíveis se torna tão eficiente para reverter quanto para calcular, assumindo que você tenha acesso a todos os bits de saída. Claramente, este não é o caso das funções consideradas na criptografia, uma vez que muitas ancilares são usadas e descartadas. É mantendo em segredo esses bits extras que dificultam a reversão da computação.

No entanto, computando a função de forma reversível, fazendo uma cópia do subconjunto de bits correspondente à saída e, em seguida, invertendo a função, o custo total de energia para computar e inverter a função será zero, enquanto o único custo incorrido será em fazer o cópia dos bits de saída, que depende apenas do número de bits de saída e não da função sendo calculada. Isso é claramente o melhor que você pode fazer, pois custa a mesma energia que simplesmente gravar a sequência de saída em um registro vazio.

Voltando à sua pergunta atualizada:

"Existem funções de mão única de alçapão que podem ser implementadas usando apenas operações lógicas reversíveis, sem espaço adicional?"

A resposta é trivialmente não. Se você aplicar o inverso de cada porta na ordem inversa, calculará o inverso da função. Assumindo um modelo em que os portões atuam em um número fixo de qubits por vez, o inverso de cada porta reversível elementar pode ser aplicado em tempo constante. Portanto, essa função é tão fácil de inverter quanto de calcular (até uma constante multiplicativa) e, portanto, não é uma função de alçapão.

Joe Fitzsimons
fonte
11
ff
4
f
@ Mikero: você precisa de energia para inicializar todos os bits ancilla para um estado inicial conhecido, mas, como no final do cálculo, todos os bits ancilla retornaram ao mesmo estado inicial conhecido, você pode recuperar essa energia.
Antonio Valerio Miceli-Barone