# 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. Jan 25, 2017 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?