Tag Info

1

Sure. Use the strong RSA assumption. The accumulator of $x_1,\dots,x_k$ is $A = g^{x_1 x_2 \cdots x_k} \bmod n$, where $n$ is a RSA modulus and $g$ is a fixed base. To prove that the accumulator $A$ contains $x$, exhibit a value $h$ such that $h^x=A \pmod n$. This is secure under the strong RSA assumption, and has a discrete log "feel" to it.

0

If $G$ is the distinguished point on your curve, you can perform pre-computations to speed up multiplication of $G$ by a scalar. For instance, if you need a transient key pair $\{K_{PRI},K_{PUB}\}$, you can use these pre-computed points to compute $K_{PUB} = [K_{PRI}]G$ quickly. But if you need to compute a shared secret using another public key $K'_{PUB}$, ...

3

Yes, you are correct. There are various methods for scalar multiplication on elliptic curves. Some of them are optimised for fixed base-point scalar multiplication, i.e., where you a-priori know that you will mostly/exclusively perform scalar multiplications with respect to a fixed base point on the curve. Thus, one can make (extensive) pre-computations ...

3

Actually, that problem is exactly equivalent to the standard DLOG problem (assuming that you know the group order, and that it is prime). Here's the reduction: suppose that we have an Oracle that can solve your problem with nontrivial probability. Then, given a value $g$ and $h$, we can find $x$ with $g^x = h$ with nontrivial probability by: Create ...

0

Just knowing any such triple would not help at all. Reason: Choose $g$ and $x$ arbitrarily, calculate $h$. Now you got such a triple, but it shouldn't help you factorize $N$, unless you have another interesting property. If on the other hand you can somehow calculate roots (given $x$ and $h$, and then find $g$), then you can break RSA: Choose $x=e$, and ...

1

As a hint, suppose we pick a random $h$, and compute $g = h^3 \bmod N$. We then find the minimal value $x$ where $g^x \equiv h \pmod{N}$ (and, yes, such an $x$ will exist, assuming $p, q > 7$). What can we deduce from such a value of $x$?

Top 50 recent answers are included