Algumas questões sobre a construção de permutações a partir de funções booleanas
Já vi vários exemplos de funções booleanas sendo usadas como uma permutação.
Por exemplo, a função Keccak Chi: 2.3.1 :
a partir dehttps://keccak.team/figures.html
Ou como uma fórmula: para$i=\{0..4\}$ $A_i=a_i \oplus (\neg a_{i+1} \wedge a_{i+2})$com índices calculados módulo 5
A primeira pergunta seria: qual é a razão (ou prova) de por que isso é uma permutação?
A segunda, relacionada: Quais são as propriedades que a função booleana deve satisfazer para que resulte em uma permutação?
E agora em relação ao inverso de tal permutação.
Existem métodos/algoritmos genéricos para encontrar o inverso de tal construção?
Além disso, quais são os principais fatores que contribuem para a complexidade do inverso (número de variáveis, grau algébrico etc.)?
E se tal método for aplicado a uma entrada maior - digamos$i=\{0..127\}$, o inverso é mais difícil de calcular, se a função tiver apenas algumas (como o 3 para Chi) ou muitas, digamos 128, variáveis de entrada?
Quaisquer respostas/ponteiros são apreciados.
Respostas
A questão algébrica geral é multifacetada e pode ser bastante complicada. Alguns dependem do espaço vetorial, outros das propriedades do campo de extensão.
Conforme mencionado nos comentários, a verificação da propriedade pode ser mais simples.
Respondi a uma pergunta relacionada Exemplos de funções booleanas com balanceamento de bits com várias saídas
Os artigos de Nyberg mencionados lá são
K. Nyberg, Mapeamentos diferencialmente uniformes para criptografia , 1993 e
K Nyberg, caixas S não lineares perfeitas , 1992
ambos facilmente localizáveis no Google Scholar.
Editado : O keccak$\chi$mapas$\{0,1\}^5$para si mesmo.
usarei$a_i$como entrada e$A_i$como variáveis de saída como na pergunta editada.
Índices de contagem módulo 5, se não houver$i$de tal modo que$(a_i,a_{i+2})=(0,1)$então$\chi$tem um ponto fixo para essa entrada. Deixar$W=\{i: (a_i,a_{i+2})=(0,1)\},$então o mapeamento geral apenas inverte os bits pertencentes a$i.$
Note que os conjuntos$J_i,J_j$Onde$J_i=\{i,i+2\}$são disjuntos, exceto quando$j=i+2$ou$i=j+2.$Portanto, não há ambiguidade para determinar o inverso, a menos que estejamos neste caso especial, portanto, o inverso existe, exceto neste caso especial. Mas mesmo neste caso os padrões$(a_i,a_{i+2},a_{i+4})$que resultam em bitflips são inequívocos.
Se$(a_i,a_{i+2},a_{i+4})=(1,0,0)$então$a_{i+1}$vai virar mas não$a_{i+3}$. Então$A_{i+1}=1\oplus a_{i+1},$e$A_{i+3}=a_{i+3}.$
Se$(a_i,a_{i+2},a_{i+4})=(1,0,1)$então$a_{i+1}$será invertido, mas não necessariamente$a_{i+3}$, que vai depender do valor de$a_{i+6}=a_{i+1}$. Mas esse bit não é afetado pelo argumento anterior, pois$J_i$e$J_j$são disjuntos se$i=j+1\pmod 2.$
Portanto, existe um mapeamento inverso exclusivo.
Observação : Em geral, ir entre formulações de campos de extensão "independentes da base" de permutações e permutações de vetores de bits "dependentes da base" dificilmente é direto. Não vejo uma formulação de campo de extensão independente de base imediata para esta permutação e, como apontado nos comentários à questão, tais formulações obtidas (digamos) por interpolação de Lagrange podem ser bastante complicadas e de alto grau.
o$\chi$função é definida e analisada em Joan Daemen Ph.D. Tese
- Estratégias de design de funções de cifra e hash baseadas em criptoanálise linear e diferencial, 1995
O Capítulo 6: Transformações invariantes com deslocamento (SIT) é onde a teoria é mencionada. Vou dar uma olhada nisso (muitas definições e resultados).
As propriedades do SIT que os tornam úteis;
- No hardware, essas transformações podem ser implementadas como uma matriz interconectada de “processadores” de saída de 1 bit idênticos.
- A invariância de deslocamento garante que a carga computacional seja distribuída de maneira otimizada.
- Em software, sua regularidade permite implementações eficientes empregando operações lógicas bit a bit.
- Além disso, transformações invariantes binárias podem ser especificadas por uma única função booleana.
SITs são muito relacionados a autômatos celulares finitos que se concentram na estrutura e padrão de longo prazo ao longo do tempo. Este trabalho concentra-se nos aspectos de curto prazo da invertibilidade e propriedades de correlação e propagação local.
Definição 6.1: Uma transformação$\phi: \mathcal{A} \to \mathcal{A}$é invariante ao deslocamento se
$$\forall a \in \mathcal{A}, \forall r\in\mathbb{Z}: \phi(\tau_r(a)) = \tau(\phi(a))$$Onde$\mathcal{A}$são todos os estados possíveis.
Em seguida, definiu os mapas locais onde a imagem depende apenas de algumas das entradas.
Teorema 6.1 (D. Richardson ) Se uma transformação$\phi$com finito$\nu$é invertível, então sua inversa$\phi^{−1}$é uma transformação invariante ao deslocamento com finito$\nu$.
Onde$\nu$define a vizinhança, consulte 6.3 Mapas locais . Este teorema não fornece uma construção do inverso explicitamente.
Seção 6.6 Transformações não lineares com finito$\nu$é onde a ação é iniciada.
Aqui o mapa local é especificado por um conjunto de padrões, chamados de paisagens complementares (CL). O valor de um componente é complementado se sua vizinhança assumir um desses padrões. Uma paisagem é um padrão que consiste em símbolos$1, 0$, e$\textbf{-}$denotando "não me importo", posicionado em relação a uma origem, denotado por$∗$. Neste contexto, o estado totalmente zero será denotado por$0^*$e o estado unificado por$1^*$.
O inverso de$\chi$é falado em seções de invertibilidade local e global que requerem um aprofundamento na teoria. Uma boa leitura para aprender, se você quiser.
Então, como eu disse nos comentários, pode-se procurar todas as permutações possíveis para ver a propriedade desejada, ou procurar na teoria como Daemen fez. Eles usaram essa teoria anos depois na construção da esponja, onde$\chi$é a única parte não linear do SHA-3.
Como minha primeira pergunta foi respondida em detalhes nas respostas de kodlu e kelalaka, gostaria de compartilhar os resultados que obtive em minha segunda pergunta desde a postagem:
Quais são as propriedades que a função booleana deve satisfazer para que resulte em uma permutação?
Durante muitas leituras adicionais, descobri que esta parece ser uma propriedade bem (mas não amplamente) conhecida. Por exemplo declarado e comprovado em Vectorial Boolean Functions for Cryptography capítulo 2.3.1 como Proposição 2:
Uma (n, m)-função é balanceada se e somente se suas funções componentes são balanceadas, isto é, se e somente se, para todo v diferente de zero$F^2_m$, a função booleana v · F é balanceada.
com o fato adicional do capítulo 2.3:
funções balanceadas (n, n) são as permutações em$F^2_n$
Portanto, uma função (n, n) é uma permutação, se e somente se for balanceada de acordo com a definição acima.
Em outras palavras, cada função do componente deve ser balanceada, bem como qualquer combinação possível de funções do componente, incl. todas as funções ao mesmo tempo, têm de ser equilibradas.
A propósito, essa propriedade também é declarada, menos obviamente, em Cipher and Hash Function Design Strategies based on linear and diferencial cryptanalysis, 1995 Theorem 5.1
Isso também significa que verificar essa propriedade para o caso geral de funções maiores, por exemplo, largura de 64 bits (n = 64), não é viável, pois exigiria a verificação do balanceamento para 2 ^ 64 - 1 combinações diferentes (para 2 ^ 64 entradas possíveis cada) . Portanto, alguns truques ou atalhos provavelmente serão necessários.