Eli Biham, Dan Boneh, Omer Reingold

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 >>>

Jean-Pierre Seifert

While quantum computers might speed up in principle

certain computations dramatically, in pratice, though

quantum computing technology is still in its infancy.

Even we cannot clearly envison at present what the

hardware of that machine will be like.

Nevertheless, we can be quite confident that it will be

more >>>

Kooshiar Azimian, Mahmoud Salmasizadeh, Javad Mohajeri

In1985, Shmuley proposed a theorem about intractability of Composite Diffie-Hellman [Sh85]. The Theorem of Shmuley may be paraphrased as saying that if there exist a probabilistic poly-time oracle machine which solves the Diffie-Hellman modulo an

RSA-number with odd-order base then there exist a probabilistic algorithm which factors the modulo. ...
more >>>

Gábor Ivanyos, Marek Karpinski, Nitin Saxena

In this work we relate the deterministic

complexity of factoring polynomials (over

finite

fields) to certain combinatorial objects we

call

m-schemes. We extend the known conditional

deterministic subexponential time polynomial

factoring algorithm for finite fields to get an

underlying m-scheme. We demonstrate ...
more >>>

Neeraj Kayal, Timur Nezhmetdinov

We give a polynomial time algorithm that computes a

decomposition of a finite group G given in the form of its

multiplication table. That is, given G, the algorithm outputs two

subgroups A and B of G such that G is the direct product

of A ...
more >>>

Gábor Ivanyos, Marek Karpinski, Lajos Rónyai, Nitin Saxena

In this paper we develop techniques that eliminate the need of the Generalized

Riemann Hypothesis (GRH) from various (almost all) known results about deterministic

polynomial factoring over finite fields. Our main result shows that given a

polynomial f(x) of degree n over a finite field k, we ...
more >>>

Zeev Dvir, Rafael Mendes de Oliveira

We show that if $f(x_1,\ldots,x_n)$ is a polynomial with $s$ monomials and $g(x_1,\ldots,x_n)$ divides $f$ then $g$

has at most $\max(s^{O(\log s \log\log s)},d^{O(\log d)})$ monomials, where $d$ is a bound on the individual degrees

of $f$. This answers a question of von zur Gathen and Kaltofen (JCSS ...
more >>>