We show how to construct length-preserving 1-1 one-way
functions based on popular intractability assumptions (e.g., RSA, DLP).
Such 1-1 functions should not
be confused with (infinite) families of (finite) one-way permutations.
What we want and obtain is a single (infinite) 1-1 one-way function.
In this paper we compare hardness of two well known problems: the Diffie-Hellman problem and the root finding problem. We prove that in any cyclic group computing Diffie-Hellman is not weaker than root finding if certain circumstances are met. As will be discussed in the paper this theorem can affect ... more >>>
Given a prime $p$, an integer $0\le n\le p-1$, and a divisor $q\mid(1+p+p^2)$, we compute $n!\bmod p$ in expected bit complexity $\widetilde{O}\left(q^c+\frac{\sqrt{p}}{q^{1/4}}\right)$ for some absolute constant $c\ge1$. More generally, the construction applies when $q\mid\Phi_r(p)$, where $\Phi_r$ is the $r$-th cyclotomic polynomial and $r$ is any fixed odd prime power. Combining ... more >>>
