The classic Gibbard-Satterthwaite Theorem establishes that only dictatorial voting rules are strategy-proof; under any other voting rule, players have an incentive to lie about their true preferences. We consider a new approach for circumventing this result: we consider randomized voting rules that only approximate a deterministic voting rule and only are approximately strategy-proof. Leveraging the notion of differential privacy, we show that any deterministic voting rule can be approximated by an approximately strategy-proof randomized voting rule. We also extend the Gibbard-Satterthwaite Theorem to provide asymptotically tight lower bounds on the parameters required by such voting rules.