Proteger o MAC quando o adversário tiver um oráculo de verificação

Um código de autenticação de mensagem (MAC) é definido por um triplo de algoritmos eficientes , que satisfazem o seguinte (a definição é a da secção 4.3 dolivro Katz-Lindell) :$(\mathsf{Gen}, \mathsf{MAC}, \mathsf{Verif})$

• Na entrada , o algoritmo G e n gera uma chave$1^n$$\mathsf{Gen}$ .$k \ge n$
• Na entrada gerada por G e n , e em alguma mensagem m ∈ { 0 , 1 } ∗ , o algoritmo M A C gera um tag t . Escrevemos t ← M A C k ( m ) .$k$$\mathsf{Gen}$$m \in \{0,1\}^*$$\mathsf{MAC}$$t$$t \gets \mathsf{MAC}_k(m)$
• Na entrada a triplo , o algoritmo V e r i f gera um único bit b . Escrevemos b ← V e r i f k ( m , t ) .$(k,m,t)$$\mathsf{Verif}$$b$$b \gets \mathsf{Verif}_k(m,t)$

É necessário que, para toda saída de G e n e todos m ∈ { 0 , 1 } ∗ , tenhamos V e r i f k ( m , M A C k ( m ) $k$$\mathsf{Gen}$$m \in \{0,1\}^*$ .$\mathsf{Verif}_k(m, \mathsf{MAC}_k(m)) = 1$

O requisito de segurança é definido através do seguinte experimento, entre o desafiante e o adversário $A$ :

1. .$k \gets \mathsf{Gen}(1^n)$
2. .$(m,t) \gets A^{\mathsf{MAC}_k(\cdot)}(1^n)$
3. Deixe denotar o conjunto de todas as consultas que A pediu ao seu oráculo.$Q$$A$
4. O resultado da experiência é definido como 1 se e somente se:
   • , e$\mathsf{Verif}_k(m, t) = 1$
   • .$m \notin Q$

O MAC é considerado seguro se a probabilidade de que o experimento produz 1 seja insignificante em .$n$

O experimento acima se assemelha a um experimento de "texto simples escolhido" em relação a um esquema de criptografia simétrica, onde o adversário pode obter textos cifrados correspondentes às mensagens de sua escolha. Em um ataque mais poderoso, chamado de "texto cifrado escolhido", o adversário também tem acesso a um oráculo de descriptografia.

Então, minha pergunta é:

O que acontece se permitirmos que o adversário do MAC acesse também um oráculo de verificação? Em outras palavras, e se a linha 2 do experimento for substituída pelo seguinte:

.$(m,t) \gets A^{\mathsf{MAC}_k(\cdot),\ \ \mathsf{Verif}_k(\cdot, \cdot)}(1^n)$

Observe que, no novo experimento, inclui apenas as consultas A feitas pelo oráculo M A C k .$Q$$A$$\mathsf{MAC}_k$

Se houver um código de autenticação de mensagem segura de acordo com uma das definições,
existe um sistema que a definição do livro classifica como segura
código de autenticação de mensagens e sua definição como insegura.

Deixei $\:\langle \operatorname{Gen}\hspace{.02 in},\hspace{-0.02 in}\operatorname{MAC}\hspace{.02 in},\hspace{-0.05 in}\operatorname{Verif}\hspace{.02 in}\rangle\:$ esteja seguro de acordo com qualquer uma das definições. $\;\;$Como a definição do livro
é mais fraca que a sua definição, ela é particularmente segura de acordo com a definição do livro.
Corrija uma codificação eficientemente computável e invertível de
pares ordenados, por exemplo, concatenando uma representação livre de prefixos, computável de forma
eficiente e invertível de forma eficiente, da entrada esquerda para a entrada direita. Deixe o MAC k
$\operatorname{MAC}_k\hspace{-0.09 in}'$ Trabalhe emparelhando a saída do com a string vazia. Vamos Verif $\operatorname{MAC}_k$
Aceite se e somente se [[o Verif k aceitaria a mensagem e a entrada esquerda da tag] e [a entrada direita da entrada é um prefixo de k ]].$\operatorname{Verif}_k\hspace{-0.09 in}'$$\operatorname{Verif}_k$
$k$$\;\;$ $\:\langle \operatorname{Gen}\hspace{.02 in},\hspace{-0.02 in}\operatorname{MAC}\hspace{.01 in}\hspace{-0.03 in}'\hspace{-0.02 in},\hspace{-0.04 in}\operatorname{Verif}\hspace{.01 in}\hspace{-0.03 in}'\hspace{.02 in}\rangle\:$ é claramente eficiente e satisfaz a exigência. $\;\;\;$Desde [emparelhar as tags com a string vazia para]
e [pegar a entrada esquerda da saída de] um adversário viável atacando a
definição do livro de segurança de$\:\langle \operatorname{Gen}\hspace{.02 in},\hspace{-0.02 in}\operatorname{MAC}\hspace{.01 in}\hspace{-0.03 in}'\hspace{-0.02 in},\hspace{-0.04 in}\operatorname{Verif}\hspace{.01 in}\hspace{-0.03 in}'\hspace{.02 in}\rangle\:$não pode ter uma probabilidade não negligenciável
de violar a definição de segurança do livro para$\:\langle \operatorname{Gen}\hspace{.02 in},\hspace{-0.02 in}\operatorname{MAC}\hspace{.02 in},\hspace{-0.05 in}\operatorname{Verif}\hspace{.03 in}\rangle\:$, $\:$a
definição do livro também classifica$\:\langle \operatorname{Gen}\hspace{.02 in},\hspace{-0.02 in}\operatorname{MAC}\hspace{.01 in}\hspace{-0.03 in}'\hspace{-0.02 in},\hspace{-0.04 in}\operatorname{Verif}\hspace{-0.01 in}\hspace{-0.03 in}'\hspace{.02 in}\rangle\:$como um código de autenticação de mensagem segura.
No entanto, quando um adversário obtém um par válido de tag de mensagem para ,$k$$\:2\hspace{-0.03 in}\cdot \hspace{-0.03 in}(\operatorname{length}(k)\hspace{-0.04 in}+\hspace{-0.05 in}1)\:$
consultas adaptáveis ​​ao É suficiente para aprender$\operatorname{Verif}_k\hspace{-0.09 in}'$$k\hspace{.01 in}$, o que permitiria falsificações em qualquer mensagem.
Assim, sua definição classifica$\:\langle \operatorname{Gen}\hspace{.02 in},\hspace{-0.02 in}\operatorname{MAC}\hspace{.01 in}\hspace{-0.03 in}'\hspace{-0.02 in},\hspace{-0.04 in}\operatorname{Verif}\hspace{-0.01 in}\hspace{-0.03 in}'\hspace{.02 in}\rangle\:$ inseguro. $\;\;\;$ QED

As fortes versões de imperdoabilidade das duas definições são equivalentes.

(As versões "forte unforgeability" são obtidos através da substituição de com o conjunto Q + dado na minha próxima frase, e que é necessário para tornar a cifrar-then-mac$Q$
$Q^+$
construção fornecer integridade texto cifrado e ser IND-CCA2.)

Inicializar $\:Q^+\:$ como o conjunto vazio e coloque $\: \langle m,\hspace{-0.03 in}t\rangle \:$ para dentro cada vez que o MAC k gera t em uma consulta de m . Defina uma consulta paratentarse, e somente se, estiver enviando para$\:Q^+$
$\operatorname{MAC}_k$$t$$m$

$\:\operatorname{Verif}_{\hspace{-0.02 in}k}\:$ um par que já foi colocado $\:Q^+\:$.
Defina uma consulta para tentar com antecedência se, e somente se, estiver tentando e
não veio depois de qualquer consulta de tentativa que$\:\operatorname{Verif}_{\hspace{-0.02 in}k}\:$aceitaram.


$B^{\hspace{.02 in}\operatorname{MAC}_k(\cdot)}\hspace{-0.02 in}\left(\hspace{-0.03 in}1^n,\hspace{-0.02 in}q,\hspace{.02 in}j\hspace{-0.01 in}\right) \;$interage com seguinte maneira:$A$

Usando menos de bits aleatórios, escolha$\hspace{.02 in}j$$\;\; r \: \in \: \left\{\hspace{-0.03 in}1,\hspace{-0.03 in}2\hspace{.02 in},\hspace{-0.03 in}3,...,\hspace{-0.02 in}q\hspace{-0.04 in}-\hspace{-0.04 in}2\hspace{.02 in},\hspace{-0.02 in}q\hspace{-0.04 in}-\hspace{-0.05 in}1,\hspace{-0.02 in}q\hspace{-0.02 in}\right\} \;\;$quase uniformemente.
"Encaminhar" todos os 's$A$$\:\operatorname{MAC}_k(\cdot)\:$ consultas para $\:\operatorname{MAC}_k(\cdot)\:$e dê a
saída (real) desse oráculo para , dê 0 como as saídas no primeiro até $A$$0$ tentando consultas e forneça 1 como as saídas de$r\hspace{-0.04 in}-\hspace{-0.05 in}1$
$1$$\:\operatorname{Verif}_{\hspace{-0.02 in}k}\:$em consultas que não estão tentando.
E se$\:A^{\operatorname{MAC}_k(\cdot),\operatorname{Verif}_k(\cdot,\cdot)}\hspace{-0.03 in}\left(\hspace{-0.03 in}1^n\hspace{-0.02 in}\right)\:$faz uma ésima tentativa de consulta e depois gera o que era essa consulta. E se$r$
$\:A^{\operatorname{MAC}_k(\cdot),\operatorname{Verif}_k(\cdot,\cdot)}\hspace{-0.03 in}\left(\hspace{-0.03 in}1^n\hspace{-0.02 in}\right)\:$dá saída, então dê a mesma saída.


Com a aleatoriedade de tudo fixa, se$\:A^{\operatorname{MAC}_k(\cdot),\operatorname{Verif}_k(\cdot,\cdot)}\hspace{-0.03 in}\left(\hspace{-0.03 in}1^n\hspace{-0.02 in}\right)\:$ faz exatamente $\:r\hspace{-0.03 in}-\hspace{-0.04 in}1\:$ tentativas antecipadas e obtém sucesso na versão forte e imperdoável de sua experiência,
$B^{\hspace{.02 in}A,\operatorname{MAC}_k(\cdot)}\hspace{-0.03 in}\left(\hspace{-0.03 in}1^n,\hspace{-0.02 in}q,\hspace{.02 in}j\hspace{-0.01 in}\right)\:$ consegue o experimento do livro da versão imperdoável.

Portanto, é uma redução linear construtiva do êxito na versão forte da imperdoabilidade de seu experimento com probabilidade de pelo menos ϵ de uma maneira que faz menos de q consultas de tentativa inicial, para o sucesso na versão forte de imperdoabilidade do experimento do livro com probabilidade Maior que$B$$\epsilon$
$q$
$\;\; \left(\hspace{-0.03 in}\frac1q\hspace{-0.03 in}-\hspace{-0.03 in}\frac{q}{2\text{^}j}\hspace{-0.04 in}\right)\cdot \epsilon \;\;\;$.
$B$ usa menos de bits aleatórios, tem que lidar com inserções e testes deassociação para [um conjunto com menos de q elementos, cada um dos quais é um par ordenado cuja entrada esquerda é uma das consultas do algoritmo interno para$\hspace{.02 in}j$
$q$
$\:\operatorname{MAC}_k\:$e cuja entrada direita é
$\operatorname{MAC}_k\hspace{-0.02 in}$é$\:$ resposta a essa consulta] e possui apenas complexidade adicional trivial além disso.

Claramente, "ignorar o oráculo da " é uma redução linear construtiva, de suceder na versão forte de imperdoabilidade do experimento do livro para suceder na versão forte de imperdoabilidade de seu experimento, e essa redução é quase perfeita. Portanto, a versão forte e imperdoável de sua definição fornece os mesmos MACs assintóticos que a versão forte e imperdoável do experimento do livro. $\operatorname{Verif}_k$