Partially blind signature schemes are the most important ingredient for anonymity in off-line e-cash system. In this paper, a new approach to setup formal security arguments in random oracle model for factorization based partially blind signature schemes is presented. Then a provably secure and efficient scheme based on quadratic residue is proposed. The approach also allows one to give formal proofs in the random oracle model for all the factorization based fully blind signature schemes. Our scheme takes an outstanding performance in computational costs compared to the existing schemes.