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?
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.