Wyniki wyszukiwania - BazTech

1

A Polynomial-Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3

Šíma Jiří, Žák Stanislav

Fundamenta Informaticae

|

2021

|

Vol. 184, nr 4

307--354

EN

Recently, an interest in constructing pseudorandom or hitting set generators for restricted branching programs has increased, which is motivated by the fundamental issue of derandomizing space-bounded computations. Such constructions have been known only in the case of width 2 and in very restricted cases of bounded width. In this paper, we characterize the hitting sets for read-once branching programs of width 3 by a so-called richness condition. Namely, we show that such sets hit the class of read-once conjunctions of DNF and CNF (i.e. the weak richness). Moreover, we prove that any rich set extended with all strings within Hamming distance of 3 is a hitting set for read-once branching programs of width 3. Then, we show that any almost O(log n)-wise independent set satisfies the richness condition. By using such a set due to Alon et al. (1992) our result provides an explicit polynomial-time construction of a hitting set for read-once branching programs of width 3 with acceptance probability ɛ > 5/6. We announced this result at conferences more than ten years ago, including only proof sketches, which motivated a number of subsequent results on pseudorandom generators for restricted read-once branching programs. This paper contains our original detailed proof that has not been published yet.

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

Nowe wyzwania dla polskiej kryptologii drugiej dekady XXI wieku

Bondaryk K., Pomykała J.

Studia Bezpieczeństwa Narodowego

|

2014

|

R. 4, Nr 6

19--31

PL

W artykule analizujemy wyzwania dla polskiej kryptologii XXI wieku ze szczególnym uwzględnieniem potrzeb narodowej kryptologii i roli, jaką spełniają w niej wybrane dziedziny matematyki, takie jak teoria liczb i geometria algebraiczna. W szczególności pokreślono rolę i bezpieczeństwo kryptosystemów bazujących na iloczynach dwuliniowych, a także problemy złożoności obliczeniowej ważnych dla kryptologii algorytmów deterministycznych. Wskazano na znaczenie funkcji typu L we współczesnej kryptograﬁi i kryptoanalizie.

EN

In this paper we analyze the challenges for the twenty-ﬁrst century Polish cryptology with special emphasis on the needs of the national cryptology and the role they perform in the selected areas of mathematics such as number theory and algebraic geometry. In particular, westress the role and security of bilinear based cryptosystems, as well as the problems of computational complexity of deterministic algorithms important for cryptology. We pointed out the importance of L-functions in modern cryptography and cryptoanalysis.