We answer the open question of the possibility of building a digital signature scheme with proven security based on the one-wayness of a trapdoor permutation and with signatures as short as possible. Our scheme is provably secure against existential forgery under chosen-message attacks (with tight reduction) in the ideal cipher model. It is a variant of the construction used in QUARTZ, that makes multiple calls to the trapdoor permutation to avoid birthday paradox attacks. We name our scheme the generic chained construction (GCC) and we show that the k-rounds GCC based on a k-bit one-way permutation with k-bit security generates k-bit signatures with almost k-bit security.
展开▼
