Toward Efficient Certificateless Signcryption from (and without) Bilinear Pairings

  • Paulo S. L. M. Barreto USP
  • Alexandre Machado Deusajute USP
  • Eduardo de Souza Cruz USP
  • Geovandro C. F. Pereira USP
  • Rodrigo Rodrigues da Silva USP


In this paper we describe how to construct an efficient certificateless signcryption scheme. Contrary to the usual paradigm of converting identitybased encryption and signature schemes into a combined certificateless protocol, we adopt the approach of extending a conventional signcryption method with a certificateless key validation mechanism, resorting to the underlying identity-based techniques, and as a consequence to pairings, exclusively to validate the associated public keys. The result is as efficient as the underlying signcryption method as long as the amortized cost of this validation is low, as is the case of our concrete proposal.


Al-Riyami, S. S. and Paterson, K. G. (2003). Certificateless public key cryptography. In Advanced in Cryptology – Asiacrypt’2003, volume 2894 of Lecture Notes in Computer Science, pages 452–473. Springer.

Baek, J., Safavi-Naini, R., and Susilo, W. (2005). Certificateless public key encryption without pairing. In Information Security Conference – ISC’2005, volume 3650 of Lecture Notes in Computer Science, pages 134–148. Springer.

Baek, J., Steinfeld, R., and Zheng, Y. (2002). Formal proofs for the security of signcryption. In Public Key Cryptography – PKC’2002, volume 2274 of Lecture Notes in Computer Science, pages 80–98. Springer.

Barbosa, M. and Farshim, P. (2008). Certificateless signcryption. In ACM Symposium on Information, Computer and Communications Security – ASIACCS’2008, Lecture Notes in Computer Science, Tokyo, Japan. Springer. To appear.

Barreto, P. S. L. M., Libert, B., McCullagh, N., and Quisquater, J.-J. (2005). Efficient and provably-secure identity-based signatures and signcryption from bilinear maps. In Advanced in Cryptology – Asiacrypt’2005, volume 3788 of Lecture Notes in Computer Science, pages 515–532. Springer.

Barreto, P. S. L. M. and Naehrig, M. (2006). Pairing-friendly curves of prime order. In Selected Areas in Cryptography – SAC’2005, volume 3897 of Lecture Notes in Computer Science, pages 319–331. Springer.

Bellare, M. and Rogaway, P. (1993). Random oracles are practical: A paradigm for designing efficient protocols. In 1st ACM Conference on Computer and Communications Security, pages 62–73, Fairfax, USA. ACM Press.

Boneh, D. and Franklin, M. (2001). Identity-based encryption from the Weil pairing. In Advanced in Cryptology – Crypto’2001, volume 2139 of Lecture Notes in Computer Science, pages 213–229. Springer.

Freeman, D., Scott, M., and Teske, E. (2006). A taxonomy of pairing-friendly elliptic curves. IACR ePrint Archive, report 2006/372.

Fujisaki, E. and Okamoto, T. (1999). Secure integration of asymmetric and symmetric encryption schemes. In Advanced in Cryptology – Crypto’1999, volume 1666 of Lecture Notes in Computer Science, pages 537–554. Springer.

Galbraith, S. D., Lin, X., and Scott, M. (2008). Endomorphisms for faster elliptic curve cryptography on general curves. IACR ePrint Archive, report 2008/194.

Hess, F., Smart, N. P., and Vercauteren, F. (2006). The eta pairing revisited. IEEE Transactions on Information Theory, 52(10):4595–4602.

Li, F., Xin, X., and Hu, Y. (2007). A pairing-based signcryption scheme using self-certified public keys. International Journal of Computers and Applications, 29(3):278–282.

Libert, B. (2006). New Secure Applications of Bilinear Maps in Cryptography. PhD thesis, Université Catholique de Louvain, Louvain-La-Neuve, Belgium.

Libert, B. and Quisquater, J. J. (2006). On constructing certificateless cryptosystems from identity based encryption. In Public Key Cryptography Workshop – PKC’2006, volume 3958 of Lecture Notes in Computer Science, pages 474–490. Springer.

Miyaji, A., Nakabayashi, M., and Takano, S. (2001). New explicit conditions of elliptic curve traces for FR-reduction. IEICE Transactions on Fundamentals, E84-A(5):1234– 1243.

Pointcheval, D. and Stern, J. (1996). Security proofs for signature schemes. In Advanced in Cryptology – Eurocrypt’1996, volume 1070 of Lecture Notes in Computer Science, pages 387–398. Springer.

Sakai, R. and Kasahara, M. (2003). ID based cryptosystems with pairing on elliptic curve. In SCIS’2003, Hamamatsu, Japan.

Sakai, R., Ohgishi, K., and Kasahara, M. (2000). Cryptosystems based on pairing. In Symposium on Cryptography and Information Security – SCIS’2000, Okinawa, Japan.

Schnorr, C. P. (1991a). Efficient signature generation by smart cards. Journal of Cryptology, 4(3):161–174.

Schnorr, C. P. (1991b). Method for identifying subscribers and for generating and verifying electronic signatures in a data exchange system. US Patent 4995082. Expired in February 2008.

Shamir, A. (1984). Identity based cryptosystems and signature schemes. In Advances in Cryptology – Crypto’84, volume 0196 of Lecture Notes in Computer Science, pages 47–53. Springer.

Vercauteren, F. (2008). Optimal pairings. IACR ePrint Archive, report 2008/096.

Zheng, Y. (1997). Digital signcryption or how to achieve cost(signature & encryption) ¡¡ cost(signature) + cost(encryption). In Advanced in Cryptology – Crypto’97, volume 1294 of Lecture Notes in Computer Science, pages 165–179. Springer.
Como Citar

Selecione um Formato
BARRETO, Paulo S. L. M.; DEUSAJUTE, Alexandre Machado; CRUZ, Eduardo de Souza; PEREIRA, Geovandro C. F.; SILVA, Rodrigo Rodrigues da. Toward Efficient Certificateless Signcryption from (and without) Bilinear Pairings. In: SIMPÓSIO BRASILEIRO DE SEGURANÇA DA INFORMAÇÃO E DE SISTEMAS COMPUTACIONAIS (SBSEG), 8. , 2008, Gramado. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2008 . p. 115-125. DOI: