International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

A Framework for Efficient Signatures, Ring Signatures and Identity Based Encryption in the Standard Model

Authors:
Zvika Brakerski
Yael Tauman Kalai
Download:
URL: http://eprint.iacr.org/2010/086
Search ePrint
Search Google
Abstract: In this work, we present a generic framework for constructing efficient signature scheme, ring signature schemes, and identity based encryption schemes, all in the standard model (without relying on random oracles). We start by abstracting the recent work of Hohenberger and Waters (Crypto 2009), and specifically their ``prefix method''. We show a transformation taking a signature scheme with a very weak security guarantee (a notion that we call a-priori-message unforgeability under static chosen message attack) and producing a fully secure signature scheme (i.e., existentially unforgeable under adaptive chosen message attack). Our transformation uses the notion of chameleon hash functions, defined by Krawczyk and Rabin (NDSS 2000) and the ``prefix method''. Constructing such weakly secure schemes seems to be significantly easier than constructing fully secure ones, and we present {\em simple} constructions based on the RSA assumption, the {\em short integer solution} (SIS) assumption, and the {\em computational Diffie-Hellman} (CDH) assumption over bilinear groups. Next, we observe that this general transformation also applies to the regime of ring signatures. Using this observation, we construct new (provably secure) ring signature schemes: one is based on the {\em short integer solution} (SIS) assumption, and the other is based on the CDH assumption over bilinear groups. As a building block for these constructions, we define a primitive that we call {\em ring trapdoor functions}. We show that ring trapdoor functions imply ring signatures under a weak definition, which enables us to apply our transformation to achieve full security. Finally, we show a connection between ring signatures and identity based encryption (IBE) schemes. Using this connection, and using our new constructions of ring signature schemes, we obtain two IBE schemes: The first is based on the {\em learning with error} (LWE) assumption, and is similar to the recently introduced IBE schemes of Peikert, Agrawal-Boyen and Cash-Hofheinz-Kiltz (2009); The second is based on the $d$-linear assumption over bilinear groups.
BibTeX
@misc{eprint-2010-22987,
  title={A Framework for Efficient Signatures, Ring Signatures and Identity Based Encryption in the Standard Model},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / digital signatures, ring signatures, identity based encryption},
  url={http://eprint.iacr.org/2010/086},
  note={ zvika.brakerski@weizmann.ac.il 14657 received 17 Feb 2010},
  author={Zvika Brakerski and Yael Tauman Kalai},
  year=2010
}