Improving the exact security of fiat-shamir signature schemes

摘要

We provide two contributions to exact security analysis of digital signatures: 1. We put forward a new methhod of constructing Fiat-Shamir-like signature schemes that yields better "exact security" than the original Fiat-Shamir method; and 2. We extend exact security analysis to exact cost-security analysis by showing that digital signature schemes with "loose security" may be preferable for reasonable measures of cost.