# 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

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