La conversión de expresiones booleanas a ecuaciones lineales, desigualdades y penalizaciones QUBO para criptoanálisis
Autores: Pakhomchik, Aleksey I.; Voloshinov, Vladimir V.; Vinokur, Valerii M.; Lesovik, Gordey B.
Idioma: Inglés
Editor: MDPI
Año: 2022
Acceso abierto
Artículo científico
2022
La conversión de expresiones booleanas a ecuaciones lineales, desigualdades y penalizaciones QUBO para criptoanálisis
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Programación con restricciones
Funciones booleanas
Solucionadores
Programación lineal mixta entera
Transformación
Variables binarias
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 28
Citaciones: Sin citaciones
Existe una amplia gama de problemas de programación de restricciones (CP) definidos en funciones booleanas dependiendo de variables binarias. Uno de los enfoques para resolver problemas de CP es utilizando solucionadores específicos apropiados, por ejemplo, solucionadores SAT. Una alternativa es utilizar solucionadores genéricos para problemas de programación lineal entera mixta (MILP), pero requieren transformar expresiones con funciones booleanas a ecuaciones o desigualdades lineales. Aquí, presentamos dos métodos de tal transformación que se aplica a cualquier función booleana definida por reglas explícitas que dan valores de la función booleana para todas las combinaciones de sus variables booleanas. El primer método representa la función booleana como una ecuación lineal en las variables binarias originales y, posiblemente, binarias auxiliares, que se convierten en variables adicionales del problema MILP que se está componiendo. El segundo método representa la función booleana como un conjunto de desigualdades lineales en las variables binarias originales y una variable continua adicional (que representa el valor de la función). La elección entre el primer o segundo método es un compromiso entre el número de variables binarias y el número de restricciones lineales en el problema de MP emergente. La ventaja del enfoque propuesto es que ambos métodos reducen problemas importantes de criptoanálisis, como la preimagen de funciones hash o la ruptura de cifrados simétricos como los problemas MILP, que son resueltos por los solucionadores genéricos de MILP. Además, el primer método permite reducir las ecuaciones lineales binarias a optimización binaria no restringida cuadrática (QUBO), mediante el anulador cuántico, por ejemplo, D-Wave.
Descripción
Existe una amplia gama de problemas de programación de restricciones (CP) definidos en funciones booleanas dependiendo de variables binarias. Uno de los enfoques para resolver problemas de CP es utilizando solucionadores específicos apropiados, por ejemplo, solucionadores SAT. Una alternativa es utilizar solucionadores genéricos para problemas de programación lineal entera mixta (MILP), pero requieren transformar expresiones con funciones booleanas a ecuaciones o desigualdades lineales. Aquí, presentamos dos métodos de tal transformación que se aplica a cualquier función booleana definida por reglas explícitas que dan valores de la función booleana para todas las combinaciones de sus variables booleanas. El primer método representa la función booleana como una ecuación lineal en las variables binarias originales y, posiblemente, binarias auxiliares, que se convierten en variables adicionales del problema MILP que se está componiendo. El segundo método representa la función booleana como un conjunto de desigualdades lineales en las variables binarias originales y una variable continua adicional (que representa el valor de la función). La elección entre el primer o segundo método es un compromiso entre el número de variables binarias y el número de restricciones lineales en el problema de MP emergente. La ventaja del enfoque propuesto es que ambos métodos reducen problemas importantes de criptoanálisis, como la preimagen de funciones hash o la ruptura de cifrados simétricos como los problemas MILP, que son resueltos por los solucionadores genéricos de MILP. Además, el primer método permite reducir las ecuaciones lineales binarias a optimización binaria no restringida cuadrática (QUBO), mediante el anulador cuántico, por ejemplo, D-Wave.