Pinocchio
Reputation
Top tag
Next privilege 250 Rep.
 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?