Mejora del muestreo de Bernoulli para distribuciones gaussianas discretas sobre los enteros
Autores: Xie, Shaohao; Zhuang, Shaohua; Du, Yusong
Idioma: Inglés
Editor: MDPI
Año: 2021
Acceso abierto
Artículo científico
2021
Mejora del muestreo de Bernoulli para distribuciones gaussianas discretas sobre los enteros
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Muestreo gaussiano discreto
Muestreo de Bernoulli
Criptografía basada en retículos
Algoritmo
Enteros
Eficiencia
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 23
Citaciones: Sin citaciones
El muestreo gaussiano discreto es una de las herramientas matemáticas fundamentales para la criptografía basada en retículos. En este artículo, revisitamos el muestreo Bernoulli(-tipo) para distribuciones gaussianas discretas centradas sobre los enteros, propuesto por Ducas et al. en 2013. Combinando la idea del algoritmo de Karney para muestrear de la distribución de Bernoulli, presentamos un algoritmo de muestreo de Bernoulli mejorado. No requiere el uso de aritmética de punto flotante para generar una tabla precalculada, como lo hacía el algoritmo de muestreo de Bernoulli original. Solo necesita una tabla de búsqueda fija de tamaño muy pequeño (por ejemplo, 128 bits) que almacena la expansión binaria de . También proponemos una versión no centrada del algoritmo de muestreo de Bernoulli para distribuciones gaussianas discretas con centros variables sobre los enteros. No requiere aritmética de punto flotante y puede admitir centros de precisión de hasta 52 bits. Los resultados experimentales muestran que nuestros algoritmos propuestos tienen una mejora significativa en la eficiencia de muestreo en comparación con otros algoritmos de rechazo.
Descripción
El muestreo gaussiano discreto es una de las herramientas matemáticas fundamentales para la criptografía basada en retículos. En este artículo, revisitamos el muestreo Bernoulli(-tipo) para distribuciones gaussianas discretas centradas sobre los enteros, propuesto por Ducas et al. en 2013. Combinando la idea del algoritmo de Karney para muestrear de la distribución de Bernoulli, presentamos un algoritmo de muestreo de Bernoulli mejorado. No requiere el uso de aritmética de punto flotante para generar una tabla precalculada, como lo hacía el algoritmo de muestreo de Bernoulli original. Solo necesita una tabla de búsqueda fija de tamaño muy pequeño (por ejemplo, 128 bits) que almacena la expansión binaria de . También proponemos una versión no centrada del algoritmo de muestreo de Bernoulli para distribuciones gaussianas discretas con centros variables sobre los enteros. No requiere aritmética de punto flotante y puede admitir centros de precisión de hasta 52 bits. Los resultados experimentales muestran que nuestros algoritmos propuestos tienen una mejora significativa en la eficiencia de muestreo en comparación con otros algoritmos de rechazo.