165 reputation
5
bio website
location
age
visits member for 9 months
seen Jul 26 at 17:10

CS and Maths are awesome!


Sep
24
awarded  Autobiographer
Feb
21
comment Proving that a function is not a OWF (One-way-function)
so what definition would you suggest?
Feb
18
comment Proving that a function is not a OWF (One-way-function)
But it has to be for a random x, right? Also, what if the construction of the candidate OWF say g depends on another OWF say f (I don't want to give example because I want to solve the ones I have for myself), does that mean g is a OWFT if there is not OWF f that break g being a OWF? Because the one I have is a OWF for some stuff, but I can construct a specfic one that breaks g remaining being a OWF.
Feb
17
asked Proving that a function is not a OWF (One-way-function)
Jan
24
awarded  Editor
Jan
24
accepted What does “Inverting the RSA function is as hard as factoring” mean (a rigorous explanation or intuitive will do)?
Jan
24
comment What does “Inverting the RSA function is as hard as factoring” mean (a rigorous explanation or intuitive will do)?
@DrLecter I apologize for the semi-regirously, I changed it to avoid confusion. I just wanted any explanation, either rigorous or intuitive would have been ok. I see, so we don't know if factoring reduces to RSA. Thanks so much for the feedback! :D
Jan
24
revised What does “Inverting the RSA function is as hard as factoring” mean (a rigorous explanation or intuitive will do)?
edited title
Jan
24
comment What does “Inverting the RSA function is as hard as factoring” mean (a rigorous explanation or intuitive will do)?
Phrased another way, if $RSA^{-1}(x) \xrightarrow[poly-time]{reduces} factoring$ and factoring is easy, then RSA is Equally as easy as factoring (since they would be in the same complexity class)?
Jan
24
comment What does “Inverting the RSA function is as hard as factoring” mean (a rigorous explanation or intuitive will do)?
I guess I am a little confused about how this relates to reductions. I agree that if factoring is efficiently solvable then inverting RSA is easy. Does that mean that RSA reduces to factoring?
Jan
24
comment What does “Inverting the RSA function is as hard as factoring” mean (a rigorous explanation or intuitive will do)?
So we know that $factoring \leq_M RSA^{-1}(x)$ but we don't know whether $factoring \geq_M RSA^{-1}(x)$ is true?
Jan
23
asked What does “Inverting the RSA function is as hard as factoring” mean (a rigorous explanation or intuitive will do)?
Jan
21
awarded  Scholar
Jan
21
accepted What does it mean that $BW_N$ is a permutation over the squares mod N?
Jan
21
awarded  Supporter
Jan
21
awarded  Student
Jan
21
comment What does it mean that $BW_N$ is a permutation over the squares mod N?
The word permutation is what is confusing me the most. I know what a quadratic residue is, but I was unsure what it meant by "permutation over the squares". If it just meant that the function $BW_N$ was just a trapdoor function if we focused our attention to the domain and codomain of quadratic residues. Is that what it means? I think I might be confused about the terms they used (and specifically what a trapdoor permutation mean, isn't it just a trapdoor function? or how is it different?). Thanks for your help btw! :)
Jan
21
asked What does it mean that $BW_N$ is a permutation over the squares mod N?