Wyniki wyszukiwania - BazTech

1

On Computing Discrete Logarithms in Bulk and Randomness Extractors

Durnoga K., Źrałek B.

Fundamenta Informaticae

|

2015

|

Vol. 141, nr 4

345--366

EN

We prove several results of independent interest related to the problem of computing deterministically discrete logarithms in a finite field. The motivation was to give a number-theoretic construction of a non-malleable extractor improving the solution from the recent paper Privacy Amplification and Non-Malleable Extractors via Character Sums by Dodis et al. There, the authors provide the first explicit example of a non-malleable extractor – a cryptographic primitive that significantly strengthens the notion of a classical randomness extractor. In order to make the extractor robust, so that it runs in polynomial time and outputs a linear number of bits, they rely on a certain conjecture on the least prime in a residue class. In this work we present a modification of their construction that allows to remove that dependency and address an issue we identified in the original development. Namely, it required an additional assumption about feasibility of finding a primitive element of a finite field. As an auxiliary result, we show an efficiently computable bijection between any order M subgroup of the multiplicative group of a finite field and a set of integers modulo M with the provision that M is a smooth number. Also, we provide a version of the baby-step giantstep method for solving multiple instances of the discrete logarithm problem in the multiplicative group of a prime field. It performs better than the generic algorithm when run on a machine without constant-time access to each memory cell, e.g., on a classical Turing machine.

2

Rozszerzony algorytm Pohliga-Hellmana i jego zastosowanie do faktoryzacji

Źrałek B.

Studia Bezpieczeństwa Narodowego

|

2014

|

R. 4, Nr 6

177--183

PL

Wskażemy ścisły związek między problemami logarytmu dyskretnego i faktoryzacji. Opiszemy mianowicie uogólnienie algorytmu Pohliga-Hellmana dla grup niecyklicznych Z*n, które można zastosować do derandomizacji algorytmu p−1 Pollarda. Algorytm ten bowiem w w wersji potrzebuje źródła losowości. Okazuje się, że obliczenia można przeprowadzić deterministycznie bez znaczącego pogorszenia złożoności.

EN

We will show that the discrete logarithm problem and the problem of factoring are closely related. Namely, we will describe a generalization of the Pohlig-Hellman algorithm to noncyclic Z*n, groups which can be used to derandomize Pollard’s p − 1 algorithm. The original version of this factoring algorithm needs indeed a source of randomness. It turns out however that the computations can be done deterministically with only slightly worse complexity.

3

Dynamic group threshold signature based on derandomized Weil pairing computation

Pomykała J., Źrałek B.

Metody Informatyki Stosowanej

|

2008

|

nr 4 (Tom 17)

183--193

EN

We propose the Weil Pairing based threshold flexible signature scheme for dynamic group. The protocol applies the simple additive secret sharing device. Its security is based on the computational Diffie-Hellman problem in the gap Diffie-Hellman groups. The computation of the Weil pairing is the crucial point of our proposition. We have managed to avoid the random numbers generation in the corresponding Miller’s algorithm without an essential increase in the computational cost. The system is particularly interesting when the threshold size is small in relation to the group cardinality.