Введение в современную криптографию
Выбор однородного группового элемента
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| Выбор однородного группового элемента
Для криптографических приложений часто бывает необходимо выбрать од- нородный элемент группы G. Сначала рассмотрим проблему в абстрактной об- становке, а затем сосредоточимся именно на случаях ZN and ZN* . Заметим, что если G является циклической группой порядка q, и генератор g∈ G из- вестен, то выбор однородного элемента h∈ G сводится к выбору однородного целого x ∈ Zq и заданию h := gx. В дальнейшем мы не делаем никаких допущений относительно G. Элементы группы G должны быть указаны с использованием некоторого представле- ния этих элементов в качестве строк битов, где мы предполагаем, без какой-либо потери общности, что все представленные элементы используют строки одной и той же длины. (Важно также, что существует единственная строка, представляющая каждый группо- вой элемент). Например, если ||N|| = n, то все элементы ZN могут быть представлены в виде строк n, где целое число a ∈ZN заполняется налево нулями, если ||a|| < n. Мы не уделяем много внимания вопросу о представлении, поскольку для всех групп, рассматриваемых в этом тексте, представление может быть принято как «естественное» представление (как в случае ZN , приведенном выше). Однако заметим, что различные представления одной и той же группы, могут влиять на сложность выполнения различных вычислений, и поэтому выбор «правильно- го» представления для данной группы, зачастую важен на практике. Посколь- ку наша задача заключается в том, чтобы показать полиномиально-временные алгоритмы для каждой из операций (и не показывать наиболее эффективные известные алгоритмы), то используемое точное представление менее важно для нас. Более того, большинство алгоритмов «более высокого уровня», которые мы представляем, используют групповую операцию в стиле «черного ящика», таким образом, что до тех пор, пока групповая операция может быть выполнена в течение полиномиального времени (по какому-то параметру), результирую- щий алгоритм также будет действовать в течение полиномиального времени. Учитывая группу G, где элементы представлены строками длиной A, однородный элемент группы можно отобрать, выбирая равномерные A-битные строки до тех пор, пока не найдена первая строка, соответствующая элементу группы. (При этом пред- полагается, что тестирование члена группы может быть выполнено эффективно). Чтобы получить алгоритм с ограниченным временем действия, введем параметр t, ограничивающий максимальное количество повторений этого процесса; если после 330 всех t итераций не удалось найти элемент G, то алгоритм выводит fail (ошибка). (Аль- тернативой будет вывод произвольного элемента G). Другими словами: жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|