This paper analyzes and improves the recently proposed bins and balls signature (BiBa [23]), a new approach for designing signatures from one-way functions without trapdoors. We first construct a general framework for signature schemes based on the balls and bins paradigm and propose several new related signature algorithms. The framework also allows us to obtain upper bounds on the security of such signatures. Several of our signature algorithms approach the upper bound. We then show that by changing the framework in a novel manner we can boost the efficiency and security of our signature schemes. We call the resulting mechanism Powerball signatures. Powerball signatures offer greater security and efficiency than previous signature schemes based on one-way functions without trapdoors.
