Partial Bits Exposure Attacks on a New Commitment Scheme Based on the Zagier Polynomial

摘要

In Asiacrypt'14, Boneh et al. built a new statistically hiding and computationally binding commitment scheme based on the collision-resistant property of the Zagier polynomial f_(zag)(x,y) = x~7 + 3y~7. In this paper, we describe severed types of partial bits exposure attacks on this new commitment, that is, the most significant bits exposure attack, the least significant bits exposure attack and the middle parts exposure attack. Besides, we study the partial bits exposure attack on the situation that a message is committed twice. We mainly use the famous Coppersmith's method in our analyses.