Покадровый анализ решеточных алгоритмов с использованием динамических систем

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 11:49, 5 декабря 2015.
Analyzing Blockwise Lattice Algorithms using Dynamical Systems
Two-Output Secure Computation with Malicious Adversaries.png
Авторы Abhi Shelat[@: 1] and
Chih-Hao Shen[@: 2]
Опубликован 2010 г.
Сайт Department of Computer Science
Перевели Egor Zorin
Год перевода 2011 г.
Скачать оригинал

__NUMBEREDHEADINGS__

Аннотация. Сильное уменьшение решетки – ключевой элемент в большинстве атак против криптосистем на основе решеток. Между сильнейшим, но непрактичным HKZ-уменьшением, и слабым но сильным LLL-уменьшением было несколько попыток найти эффективный компромисс. Среди них, BKZ-алгоритм, представленный Шнорром и Ихнером в 1991, на практике достигает лучшего соотношения время/качество. Однако, для BKZ не существует разумной верхней границы сложности, так что Гама и Нгуен на конференции Eurocrypt 2008 экспериментально показали, что на практике его время работы, видимо, растёт по экспоненте с размерностью решётки. В этой работе мы покажем, что BKZ может быть прерван задолго до завершения, в тоже время предоставляя высококачественные базисы. Если быть точным, мы покажем, что подавая на вход базис

для решетки L размером блока β, и если алгоритм прерван после

вызовов к β-мерному HKZ-уменьшению подпрограммы, алгоритм BKZ вернёт базис, норма первого вектора которого

,

Где - максимальная из констант Эрмита для измерений ≤β Для получения результата мы разработали полностью новую элементарную технику, основанную на дискретных аффинных динамических системах, которые могут привести к проектированию улучшенных алгоритмов уменьшения решетки. Ключевые слова: Евклидовы решетки, BKZ, решеточный криптоанализ

Контакты авторов материала

  1. University of Virginia, Charlottesville, VA 22904, E-mail: shelat@virginia.edu
  2. University of Virginia, Charlottesville, VA 22904, E-mail: shench@virginia.edu

Примечание

Литература