
PreviousNext
The Diffie-Hellman key-exchange protocol may naturally be
extended to k>2 parties. This gives rise to the generalized
Diffie-Hellman assumption (GDH-Assumption).
Naor and Reingold have recently shown an efficient construction
of pseudo-random functions and reduced the security of their
construction to the GDH-Assumption.
In this note, we ...
more >>>
We show that the satisfiability problem for
bounded error probabilistic ordered branching programs is NP-complete.
If the error is very small however
(more precisely,
if the error is bounded by the reciprocal of the width of the branching program),
then we have a polynomial-time algorithm for the satisfiability problem.
more >>>
Recently Ajtai showed that
to approximate the shortest lattice vector in the $l_2$-norm within a
factor $(1+2^{-\mbox{\tiny dim}^k})$, for a sufficiently large
constant $k$, is NP-hard under randomized reductions.
We improve this result to show that
to approximate a shortest lattice vector within a
factor $(1+ \mbox{dim}^{-\epsilon})$, for any
$\epsilon>0$, ...
more >>>
PreviousNext