nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Secure and Efficient Delegation of Elliptic-Curve Pairing

verfasst von : Giovanni Di Crescenzo, Matluba Khodjaeva, Delaram Kahrobaei, Vladimir Shpilrain

Erschienen in: Applied Cryptography and Network Security

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Many public-key cryptosystems and, more generally, cryptographic protocols, use pairings as important primitive operations. To expand the applicability of these solutions to computationally weaker devices, it has been advocated that a computationally weaker client delegates such primitive operations to a computationally stronger server. Important requirements for such delegation protocols include privacy of the client’s pairing inputs and security of the client’s output, in the sense of detecting, except for very small probability, any malicious server’s attempt to convince the client of an incorrect pairing result.

In this paper we show that the computation of bilinear pairings in essentially all known pairing-based cryptographic protocols can be efficiently, privately and securely delegated to a single, possibly malicious, server. Our techniques provides efficiency improvements over past work in all input scenarios, regardless on whether inputs are available to the parties in an offline phase or only in the online phase, and on whether they are public or have privacy requirements. The client’s online runtime improvement is, for some of our protocols, almost 1 order of magnitude, no matter which practical elliptic curve, among recently recommended ones, is used for the pairing realization.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Random Walks and Concurrent Zero-Knowledge

Nächstes Kapitel Tweaking Key-Alternating Feistel Block Ciphers

Al-Riyami, S.S., Paterson, K.G.: Certificateless public key cryptography. In: Laih, C.-S. (ed.) ASIACRYPT 2003. LNCS, vol. 2894, pp. 452–473. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-40061-5_29CrossRef

Asokan, N., Tsudik, G., Waidner, M.: Server-supported signatures. J. Comput. Secur. 5(1), 91–108 (1997)CrossRef

Atallah, M., Pantazopoulos, K., Rice, J., Spafford, E.: Secure outsourcing of scientific computations. Adv. Comput. 54, 215–272 (2002)CrossRef

Atallah, M., Frikken, K.: Securely outsourcing linear algebra computations. In: Proceedings of 5th ACM ASIACCS, pp. 48–59 (2010)

Barreto, P.S.L.M., Costello, C., Misoczki, R., Naehrig, M., Pereira, G.C.C.F., Zanon, G.: Subgroup security in pairing-based cryptography. In: Lauter, K., Rodríguez-Henríquez, F. (eds.) LATINCRYPT 2015. LNCS, vol. 9230, pp. 245–265. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-22174-8_14CrossRefMATH

Benjamin, D., Atallah, M.: Private and cheating-free outsourcing of algebraic computations. In: 6th Sixth Annual Conference on Privacy, Security and Trust, pp. 240–245 (2008)

Boneh, D., Franklin, M.: Identity-based encryption from the Weil pairing. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213–229. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44647-8_13CrossRef

Boneh, D., Di Crescenzo, G., Ostrovsky, R., Persiano, G.: Public key encryption with keyword search. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 506–522. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24676-3_30CrossRef

Boneh, D., Lynn, B., Shacham, H.: Short signatures from the Weil pairing. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 514–532. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45682-1_30CrossRef

10.

Bos, J.W., Costello, C., Naehrig, M.: Exponentiating in pairing groups. In: Lange, T., Lauter, K., Lisoněk, P. (eds.) SAC 2013. LNCS, vol. 8282, pp. 438–455. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-43414-7_22CrossRefMATH

11.

Canard, S., Devigne, J., Sanders, O.: Delegating a pairing can be both secure and efficient. In: Boureanu, I., Owesarski, P., Vaudenay, S. (eds.) ACNS 2014. LNCS, vol. 8479, pp. 549–565. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-07536-5_32CrossRefMATH

12.

Cavallo, B., Di Crescenzo, G., Kahrobaei, D., Shpilrain, V.: Efficient and secure delegation of group exponentiation to a single server. In: Mangard, S., Schaumont, P. (eds.) RFIDSec 2015. LNCS, vol. 9440, pp. 156–173. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-24837-0_10CrossRef

13.

Chen, X., Li, J., Ma, J., Tang, Q., Lou, W.: New algorithms for secure outsourcing of modular exponentiations. IEEE Trans. Parallel Distrib. Syst. 25(9), 2386–2396 (2014)CrossRef

14.

Chevallier-Mames, B., Coron, J.S., McCullagh, N., Naccache, D., Scott, M.: Secure delegation of elliptic-curve pairing. Cryptology ePrint Archive. In report 2005/150 (2005). http://eprint.iacr.org/2005/150

15.

Chevallier-Mames, B., Coron, J.-S., McCullagh, N., Naccache, D., Scott, M.: Secure delegation of elliptic-curve pairing. In: Gollmann, D., Lanet, J.-L., Iguchi-Cartigny, J. (eds.) CARDIS 2010. LNCS, vol. 6035, pp. 24–35. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-12510-2_3CrossRef

16.

Chevalier, C., Laguillaumie, F., Vergnaud, D.: Privately outsourcing exponentiation to a single server: cryptanalysis and optimal constructions. In: Askoxylakis, I., Ioannidis, S., Katsikas, S., Meadows, C. (eds.) ESORICS 2016. LNCS, vol. 9878, pp. 261–278. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-45744-4_13CrossRef

17.

Chung, K.-M., Kalai, Y., Vadhan, S.: Improved delegation of computation using fully homomorphic encryption. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 483–501. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_26CrossRef

18.

Di Crescenzo, G., Khodjaeva, M., Kahrobaei, D., Shpilrain, V.: Practical and secure outsourcing of discrete log group exponentiation to a single malicious server. In: Proceedings of 9th ACM CCSW, pp. 17–28 (2017)

19.

Di Crescenzo, G., Kahrobaei, D., Khodjaeva, M., Shpilrain, V.: Efficient and secure delegation to a single malicious server: exponentiation over non-abelian groups. In: Davenport, J.H., Kauers, M., Labahn, G., Urban, J. (eds.) ICMS 2018. LNCS, vol. 10931, pp. 137–146. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96418-8_17CrossRef

20.

Di Crescenzo, G., Khodjaeva, M., Kahrobaei, D., Shpilrain, V.: Secure delegation to a single malicious server: exponentiation in RSA-type groups. In: Proceedings of IEEE CNS, pp. 1–9 (2019)

21.

Dijk, M., Clarke, D., Gassend, B., Suh, G., Devadas, S.: Speeding up exponentiation using an untrusted computational resource. Des. Codes Crypt. 39(2), 253–273 (2006)MathSciNetCrossRef

22.

Fiore, D., Gennaro, R.: Publicly verifiable delegation of large polynomials and matrix computations, with applications. In: Proceedings of ACM CCS Conference, pp. 501–512 (2012)

23.

Gennaro, R., Gentry, C., Parno, B.: Non-interactive verifiable computing: outsourcing computation to untrusted workers. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 465–482. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_25CrossRef

24.

Girault, M., Lefranc, D.: Server-aided verification: theory and practice. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 605–623. Springer, Heidelberg (2005). https://doi.org/10.1007/11593447_33CrossRef

25.

Goldwasser, S., Tauman Kalai, Y., Rothblum, G.N.: Delegating computation: interactive proofs for muggles. J. ACM (JACM) 62(4), 1–64 (2015)MathSciNetCrossRef

26.

Guillevic, A., Vergnaud, D.: Algorithms for outsourcing pairing computation. In: Joye, M., Moradi, A. (eds.) CARDIS 2014. LNCS, vol. 8968, pp. 193–211. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-16763-3_12CrossRef

27.

Hess, F.: Efficient identity based signature schemes based on pairings. In: Nyberg, K., Heys, H. (eds.) SAC 2002. LNCS, vol. 2595, pp. 310–324. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36492-7_20CrossRef

28.

Hohenberger, S., Lysyanskaya, A.: How to securely outsource cryptographic computations. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 264–282. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-30576-7_15CrossRef

29.

Joux, A.: A one round protocol for tripartite Diffie–Hellman. In: Bosma, W. (ed.) ANTS 2000. LNCS, vol. 1838, pp. 385–393. Springer, Heidelberg (2000). https://doi.org/10.1007/10722028_23CrossRef

30.

Kachisa, E.J., Schaefer, E.F., Scott, M.: Constructing Brezing-Weng pairing-friendly elliptic curves using elements in the cyclotomic field. In: Galbraith, S.D., Paterson, K.G. (eds.) Pairing 2008. LNCS, vol. 5209, pp. 126–135. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85538-5_9CrossRefMATH

31.

Kang, B.G., Lee, M.S., Park, J.H.: Efficient delegation of pairing computation. In: IACR Cryptology ePrint Archive, no. 259 (2005)

32.

Liu, J.K., Au, M.H., Susilo, W.: Self-generated-certificate public key cryptography and certificateless signature/encryption scheme in the standard model. In: Proceedings of the ACM Symposium on Information, Computer and Communications Security. ACM Press (2007)

33.

Ma, X., Li, J., Zhang, F.: Outsourcing computation of modular exponentiations in cloud computing. Cluster Comput. 16, 787–796 (2013). (also INCoS 2012)

34.

Matsumoto, T., Kato, K., Imai, H.: An improved algorithm for secure outsourcing of modular exponentiations. In: Proceedings of CRYPTO 1988, pp. 497–506. LNCS, Springer, Cham (1988)

35.

Scott, M.: Unbalancing pairing-based key exchange protocols. In: IACR Cryptology ePrint Archive, no. 688 (2013)

36.

Shi, Y., Li, J.: Provable efficient certificateless public key encryption. In: IACR Cryptology ePrint Archive, no. 284 (2005)

37.

Vercauteren, F.: Optimal pairings. IEEE Trans. Inf. Theory 56(1), 455–461 (2010)MathSciNetCrossRef

38.

Yao, A.: Protocols for secure computations. In: Proceedings of 23rd IEEE FOCS, pp. 160–168 (1982)

Titel: Secure and Efficient Delegation of Elliptic-Curve Pairing
verfasst von: Giovanni Di Crescenzo
Matluba Khodjaeva
Delaram Kahrobaei
Vladimir Shpilrain
Verlag: Springer International Publishing
Buch: Applied Cryptography and Network Security
Print ISBN: 978-3-030-57807-7

Electronic ISBN: 978-3-030-57808-4

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-57808-4_3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner