logo móvil
Contáctanos

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

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro