Implementaciones eficientes de algoritmos de cribado y enumeración para criptografía basada en retículos
Autores: Satlm, Hami; Akleylek, Sedat; Lee, Cheng-Chi
Idioma: Inglés
Editor: MDPI
Año: 2021
Acceso abierto
Artículo científico
2021
Implementaciones eficientes de algoritmos de cribado y enumeración para criptografía basada en retículos
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Sistemas criptográficos basados en retículas
Problema del vector más corto
Problema del vector más cercano
GaussSieve
HashSieve
BKZ
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 28
Citaciones: Sin citaciones
La seguridad de los criptosistemas basados en retículas se basa en la resolución de problemas difíciles de retículas como el problema del vector más corto (SVP) y el problema del vector más cercano (CVP). Se han propuesto varios algoritmos de criptoanálisis como (Pro)GaussSieve, HashSieve, ENUM y BKZ para resolver estos problemas difíciles. Se han desarrollado varias implementaciones de estos algoritmos. Por otro lado, se espera que las implementaciones de estos algoritmos sean eficientes en cuanto al tiempo de ejecución y al espacio de memoria. En este documento, se desarrolla un paquete/biblioteca de software modular que contiene implementaciones eficientes de los algoritmos GaussSieve, ProGaussSieve, HashSieve y BKZ. Estas implementaciones se consideran eficientes en cuanto al tiempo de ejecución. Al construir esta biblioteca de software, se realizan algunas modificaciones a los algoritmos para aumentar el rendimiento. Luego, se comparan los tiempos de ejecución de estas implementaciones con los demás. Según los resultados experimentales, las implementaciones propuestas de GaussSieve, ProGaussSieve y HashSieve son al menos un 70%, un 75% y un 49% más eficientes que las anteriores, respectivamente.
Descripción
La seguridad de los criptosistemas basados en retículas se basa en la resolución de problemas difíciles de retículas como el problema del vector más corto (SVP) y el problema del vector más cercano (CVP). Se han propuesto varios algoritmos de criptoanálisis como (Pro)GaussSieve, HashSieve, ENUM y BKZ para resolver estos problemas difíciles. Se han desarrollado varias implementaciones de estos algoritmos. Por otro lado, se espera que las implementaciones de estos algoritmos sean eficientes en cuanto al tiempo de ejecución y al espacio de memoria. En este documento, se desarrolla un paquete/biblioteca de software modular que contiene implementaciones eficientes de los algoritmos GaussSieve, ProGaussSieve, HashSieve y BKZ. Estas implementaciones se consideran eficientes en cuanto al tiempo de ejecución. Al construir esta biblioteca de software, se realizan algunas modificaciones a los algoritmos para aumentar el rendimiento. Luego, se comparan los tiempos de ejecución de estas implementaciones con los demás. Según los resultados experimentales, las implementaciones propuestas de GaussSieve, ProGaussSieve y HashSieve son al menos un 70%, un 75% y un 49% más eficientes que las anteriores, respectivamente.