# How to prove hardness of approximate-GCD problem?

I am trying to prove the security of my system using the hardness assumption of the approximate-GCD problem using contradiction, i.e. If the attacker is able to break in our scheme, then attacker would be able to solve the approximate-GCD problem. I am stuck at the point where I proved that the complexity is O(2^rho) using brute-force approach. How shall I proceed? Is there any concrete complexity measure which can be used as to prove the contradiction?

• Assume there is a crack for your scheme, and now show that by inputting careful values to this crack program, you obtain a solution to AGCD, or at least get something easily converted into a solution. This is the formula for a reductionist security proof. You just show that you can actually use any crack to compute the hard problem easily. Even if the crack works in an unexpected way. – MickLH Jan 25 '17 at 20:57

## 1 Answer

I am stuck at the point where I proved that the complexity is $O(2^\rho)$ using brute-force approach. How shall I proceed?

Well, a proof that assumed a specific attack strategy is of limited use, as that proof would be inapplicable if the attacker used some other strategy.

Instead, what we typically do in a proof is assume that the adversary had some Oracle that could break your system, and then show that, using that Oracle, he could break the hard problem (in this case, approximate-GCD). This has the advantage that it doesn't matter how the adversary breaks your system; if he can break it by any means, then he can solve the hard problem; hence, if he is unable to solve the hard problem (which is our assumption), then he can't break your system.

• Thanks! So, is there any literature that I can cite as to show the hardness of approximate-GCD problem? i.e. Any paper that shows that approximate-GCD is a hard problem. – Ainish Dave Apr 17 '16 at 3:15
• There are some instances of AGCD that are proven to be hard. For example see: perso.ens-lyon.fr/damien.stehle/AGCD.html – Luckyluck63 Apr 17 '16 at 22:35