1,384 reputation
1820
bio website
location
age
visits member for 3 years, 4 months
seen 1 hour ago

10h
comment Is computing roots moduli a composite $N$ a hard problem without knowing the factorization of $N$?
@Thomas you mean that you can find the inverse moduli $N$ but you do not which one is the correct one.
14h
accepted Is computing roots moduli a composite $N$ a hard problem without knowing the factorization of $N$?
14h
comment Is computing roots moduli a composite $N$ a hard problem without knowing the factorization of $N$?
But $v \equiv u^{-1} \mod N$ also which is easy computable
16h
comment Is computing roots moduli a composite $N$ a hard problem without knowing the factorization of $N$?
@Aleph Then why finding $x \mod N$ from $x^u \mod N$ is difficult? You compute $v=u^{-1}$ and then $x= (x^{u})^v=x^{uu^{-1}} \mod N$
17h
comment Is computing roots moduli a composite $N$ a hard problem without knowing the factorization of $N$?
Does this imply that finding inverses mod $N=pq$ is also hard as long you don't know the factorization of $N$
1d
revised Is computing roots moduli a composite $N$ a hard problem without knowing the factorization of $N$?
deleted 9 characters in body
1d
comment Is computing roots moduli a composite $N$ a hard problem without knowing the factorization of $N$?
The adversary knows $N^2$, so i guess it is not hard to learn the inverse of $u$ with the extended Euclidean.
1d
comment Is computing roots moduli a composite $N$ a hard problem without knowing the factorization of $N$?
Yes but my concern is that i want the inverse not moduli $\phi(N^2)$ but $(N^2)$
1d
comment Is computing roots moduli a composite $N$ a hard problem without knowing the factorization of $N$?
The solution to the RSA problem as you said is the inverse of $e$ moduli $\phi(N)=(p-1)(q-1)$. And it is believed that if the factorization $(p,q)$ is not known you cannot find the inverse.
1d
comment Is computing roots moduli a composite $N$ a hard problem without knowing the factorization of $N$?
RSA problem states that it is difficult to compute multiplicative inverses moduli $\phi(N)$
1d
revised Is computing roots moduli a composite $N$ a hard problem without knowing the factorization of $N$?
deleted 47 characters in body
1d
revised Is computing roots moduli a composite $N$ a hard problem without knowing the factorization of $N$?
deleted 15 characters in body
1d
revised Is computing roots moduli a composite $N$ a hard problem without knowing the factorization of $N$?
edited body
1d
asked Is computing roots moduli a composite $N$ a hard problem without knowing the factorization of $N$?
Mar
3
awarded  Famous Question
Feb
26
revised Are there any asymmetric composite order group bilinear pairings?
added 37 characters in body
Feb
26
asked Are there any asymmetric composite order group bilinear pairings?
Jan
26
awarded  Tumbleweed
Jan
19
asked Differential Privacy and appropriate noise distribution
Dec
28
comment Why is proof-by-reduction needed (for Elgamal proof of security, for example)?
@Maeher i can't get how you start building your distinguisher since you state:compute x. In order to compute x you break DL, which is impossible for computationally bounded adversary.