History

Please fill in your query. A complete syntax description you will find on the General Help page.
Short signatures from weaker assumptions. (English)
Lee, Dong Hoon (ed.) et al., Advances in cryptology ‒ ASIACRYPT 2011. 17th international conference on the theory and application of cryptology and information security, Seoul, South Korea, December 4‒8, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-25384-3/pbk). Lecture Notes in Computer Science 7073, 647-666 (2011).
Summary: We provide constructions of $(m,1)$-programmable hash functions (PHFs) for $m \geq 2$. Mimicking certain programmability properties of random oracles, PHFs can, e.g., be plugged into the generic constructions by {\it D. Hofheinz} and {\it E. Kiltz} [“Programmable hash functions and their applications”, J. Cryptology (2011; doi:10.1007/s00145-011-9102-5)] to yield digital signature schemes from the strong RSA and strong $q$-Diffie-Hellman assumptions. As another application of PHFs, we propose new and efficient constructions of digital signature schemes from weaker assumptions, i.e., from the (standard, non-strong) RSA and the (standard, non-strong) $q$-Diffie-Hellman assumptions. The resulting signature schemes offer interesting tradeoffs between efficiency/signature length and the size of the public-keys. For example, our $q$-Diffie-Hellman signatures can be as short as 200 bits; the signing algorithm of our Strong RSA signature scheme can be as efficient as the one in RSA full domain hash; compared to previous constructions, our RSA signatures are shorter (by a factor of roughly 2) and we obtain a considerable efficiency improvement (by an even larger factor). All our constructions are in the standard model, i.e., without random oracles.