Tail exponents of conditional guesswork via the method of types

Enunciado do Problema
O artigo aborda o problema de adivinhar uma realização de uma sequência aleatória de alfabeto finito $X$ de comprimento $n$, gerada i.i.d. a partir de uma distribuição $P_X$, dado acesso a informação lateral correlacionada elemento a elemento $Y$. O par $(X, Y)$ é gerado i.i.d. a partir de uma distribuição conjunta $P_{XY}$. O "esforço de adivinhação" (guesswork), denotado por $G(X|Y)$, é definido como o número de tentativas necessárias para adivinhar corretamente $X$ quando o adivinhador emprega a estratégia ótima: adivinhar sequências em ordem decrescente de sua probabilidade condicional $P_{X|Y}(x|y)$.

Embora a taxa de crescimento exponencial dos momentos do esforço de adivinhação (caracterizada por Arikan via entropia de Rényi condicional) seja conhecida, este artigo foca nas probabilidades de cauda do esforço de adivinhação. Especificamente, busca determinar as taxas de decaimento exponencial (exponentes de cauda) para as probabilidades $\Pr\{G(X|Y) < 2^{nh}\}$ e $\Pr\{G(X|Y) > 2^{nh}\}$ conforme $n \to \infty$, para um dado limiar $h$.

Metodologia
Os autores empregam o método dos tipos para derivar esses expoentes. A abordagem deles envolve:

1. Contagem de Tipos: Em vez de depender de princípios de grandes desvios (LDP) que exigem suposições sobre funções geradoras de cumulantes escalonadas (sCGF) que são difíceis de verificar para fontes gerais, os autores utilizam limites explícitos na cardinalidade das classes de tipos e classes de tipos condicionais.
2. Ordenação em Tipos: Eles definem uma ordem total em distribuições de probabilidade (tipos) baseada em sua entropia cruzada relativa à distribuição da fonte. Para o caso condicional, eles definem uma ordem em tipos condicionais $Q_{X|Y}$ relativa a um tipo específico observado de $Y$.
3. Otimização: O expoente de cauda é derivado resolvendo um problema de otimização: encontrar a distribuição (ou distribuição condicional) que minimiza a divergência de Kullback-Leibler (KL) da verdadeira distribuição da fonte, sujeito a uma restrição na entropia (ou entropia condicional) da distribuição.
4. Distribuições Inclinadas (Tilted Distributions): As soluções para esses problemas de minimização restrita mostram-se como distribuições inclinadas (famílias exponenciais). No caso condicional, estas são distribuições inclinadas condicionais.

Principais Contribuições e Resultados

1. Recuperação do Caso Incondicional: O artigo primeiro re-deriva os expoentes de cauda conhecidos para o esforço de adivinhação incondicional $\Pr\{G(X) \gtrless 2^{nh}\}$ (previamente caracterizados por Beirami et al.). Eles mostram que o expoente é dado pela divergência KL entre a distribuição da fonte $P$ e uma distribuição inclinada $P^{(\lambda_h)}$, onde o parâmetro de inclinação $\lambda_h$ é escolhido de tal forma que a entropia da distribuição inclinada seja igual a $h$. Isso fornece uma prova direta e curta usando contagem de tipos.

2. Expoentes de Esforço de Adivinhação Condicional (Dado o tipo de $Y$): Os autores derivam uma expressão explícita para os expoentes de cauda de $\Pr\{G(X|Y) \gtrless 2^{nh} \mid Y = y^{(n)}\}$, onde o tipo da sequência de informação lateral $y^{(n)}$ converge para uma distribuição $Q$.

   • O expoente é dado pela divergência KL condicional $D(P_{X|Y}^{(\lambda_{h,Q})} \| P_{X|Y} \mid Q)$, onde $P_{X|Y}^{(\lambda_{h,Q})}$ é a distribuição inclinada condicional.
   • O ponto de transição para o expoente (onde ele se torna zero) é a entropia condicional $H_Q(X|Y)$.

3. Expoentes de Esforço de Adivinhação Condicional (Médios sobre $Y$): O artigo fornece uma nova expressão explícita para os expoentes de cauda da probabilidade incondicional $\Pr\{G(X|Y) \gtrless 2^{nh}\}$, média sobre todas as possíveis sequências de informação lateral.

   • O expoente é caracterizado como $D(Q_{Y, \lambda_h} P_{X|Y}^{(\lambda_h)} \| P_{XY})$.
   • Crucialmente, a distribuição conjunta otimizadora não é uma simples versão inclinada da distribuição conjunta da fonte $P_{XY}$. Em vez disso, é uma distribuição conjunta formada por uma marginal específica $Q_{Y, \lambda_h}$ e a distribuição inclinada condicional $P_{X|Y}^{(\lambda_h)}$.
   • A marginal $Q_{Y, \lambda_h}$ é derivada explicitamente como uma função da marginais da fonte $P_Y$ e da distribuição condicional $P_{X|Y}$.

4. Implicações para $n$ Finito: Os autores observam que, como sua derivação depende de limites explícitos de classe de tipos em vez de maquinário LDP assintótico, o método inerentemente fornece limites superiores e inferiores de $n$ finito para as probabilidades de cauda que coincidem até fatores polinomiais em $n$. No entanto, o artigo foca nos expoentes assintóticos.

Significância e Aplicação
O artigo afirma ter significância ao fornecer uma caracterização direta e explícita dos expoentes de cauda do esforço de adivinhação condicional para fontes i.i.d. sem as suposições restritivas exigidas pelos resultados gerais de LDP anteriores (como os de Christiansen & Duffy ou Li). Os resultados são expressos em termos de quantidades informacional-teóricas (divergências envolvendo distribuições inclinadas) que são computáveis.

Os autores ilustram a utilidade desses resultados através de uma aplicação à adivinhação de senhas por força bruta com informação lateral. Eles modelam um cenário onde uma senha é gerada a partir de uma distribuição Zipf e um atacante observa a informação lateral através de um canal de apagamento sem memória. Usando os expoentes derivados, eles calculam o comprimento de senha $n$ necessário para garantir que a probabilidade de um atacante adivinhar a senha dentro de um pequeno número de tentativas permaneça abaixo de um limiar especificado, mesmo quando uma parte significativa dos caracteres da senha é vazada.

Conclusão
O artigo conclui que o método dos tipos oferece um framework robusto para analisar o comportamento de cauda do esforço de adivinhação. Os expoentes derivados são determinados por problemas de minimização de divergência com restrição de entropia, resultando em soluções envolvendo distribuições inclinadas condicionais. Este framework permite a avaliação quantitativa de riscos de segurança em sistemas de senhas sujeitos a vazamento de informação lateral.