| 1. |
|
|
| 2. |
- Goldmann, Mikael, et al.
(författare)
-
Complexity bounds on general hard-core predicates
- 2001
-
Ingår i: Journal of Cryptology. - : Springer Science and Business Media LLC. - 0933-2790 .- 1432-1378. ; 14:3, s. 177-195
-
Tidskriftsartikel (refereegranskat)abstract
- A Boolean function b is a hard-core predicate for a one-way function S if b is polynomial-time computable but b(x) is difficult to predict from lf(x). A general one-way function. A seminal result of Goldreich and Levin asserts that the family of parity functions is a general family of hard-core predicates. We show that no general family of hard-core predicates can consist of functions with O(n(1-epsilon)) average sensitivity for any epsilon > 0. As a result, such families cannot consist of functions in AC(0), monotone functions, functions computed by generalized threshold gates, or symmetric d-threshold functions, for d = O(n(1/2-epsilon)) and epsilon > 0.
|
|
| 3. |
- Goldmann, Mikael, et al.
(författare)
-
The complexity of solving equations over finite groups
- 2002
-
Ingår i: Information and Computation. - : Elsevier BV. - 0890-5401 .- 1090-2651. ; 178:1, s. 253-262
-
Tidskriftsartikel (refereegranskat)abstract
- We study the computational complexity of solving systems of equations over a finite group. An equation over a group G is an expression of the form w(1)(.)w(2)(.)...(.)w(k) = 1(G), where each wi is either a variable, an inverted variable, or a group constant and 1G is the identity element of G. A solution to such an equation is an assignment of the variables (to values in G) which realizes the equality. A system of equations is a collection of such equations; a solution is then an assignment which simultaneously realizes each equation. We show that the problem of determining if a (single) equation has a solution is NP-complete for all nonsolvable groups G. For nilpotent groups, this same problem is shown to be in P. The analogous problem for systems of such equations is shown to be NP-complete if G is non-Abelian, and in P otherwise. Finally, we observe some connections between these problems and the theory of nonuniform automata.
|
|
