SpringerLink
Log in

Efficient Forward-Secure Threshold Public Key Encryption

  • Conference paper
  • First Online:
Information Security and Privacy (ACISP 2020)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 12248))

Included in the following conference series:

  • 1161 Accesses

Abstract

The purpose of forward-secure threshold public key encryption schemes is to mitigate the damage of secret key exposure. We construct the first CCA forward-secure threshold public key encryption scheme based on bilinear pairings with groups of prime order that is secure against adaptive and malicious adversaries in the standard model. Our scheme is very efficient since it has a non-interactive key update and decryption procedure. Additionally, our scheme does not require a trusted dealer and has optimal resilience as well as small ciphertexts of constant size. It is the first scheme which achieves all of these and that can also be implemented on standardized elliptic curves.

R. Kurek—Supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, grant agreement 802823, and by the German Research Foundation (DFG) within the Collaborative Research Center “On-The-Fly Computing” (SFB 901/3).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Adaptive adversaries can corrupt parties at any time. Static adversaries need to corrupt the parties before the protocol execution begins. For a proper overview see [1].

  2. 2.

    In the static security model the adversary has to submit its choice of k parties it wants to corrupt before receiving the public key. In the adaptive model it can corrupt the parties at any time. For a proper overview see [1].

  3. 3.

    Note that this case can only occur for time periods \(t > 0\), i.e. after \(\mathbf{FST}.KeyGen \) had finished. Otherwise the adversary would have no possibility to win the security game.

  4. 4.

    Note that in [10] the secret value is set as x instead of \(h^x\). This modification happens only internally and has no impact on the adversary’s view or security.

  5. 5.

    Note that the secret share \(x_i\) is computed commonly by all parties and the randomness \(r_i\) is computed locally by party \(P_i\) and is not a share of another random value. This approach is more efficient than computing random values commonly, especially to different bases.

  6. 6.

    Example: Let \(T=2^3\). Then \(t_0= 000\), \(t_1=100\), \(t_2=010\),... . Given a substring xy, we can compute xy0 and xy1. Hence, for time period \(t_2\) the set \(C_{t_2}\) consists of the node keys for 01 and 1. From 01 it can compute the secret key for \(t_2=010\) and \(t_3=011\). From 1 it can compute the secret key for all time periods greater \(t_3\): 100, 101, 110, 111. The keys for time periods \(t_0=000\) and \(t_1=001\) cannot be computed from this set. If we update to time period \(t_3\), we need to compute 011 and erase the node key for 01. Thus \(C_{t_3}\) consists of the key for 011 and the node key 1. Then, also the key for 010 cannot be computed anymore.

  7. 7.

    Note that decryption happens with respect to a time period. Since time periods are encoded in full bit length (even if they start with zero) they are low in the binary tree. Hence, they only have left \(e_{i,\ell +1}\) as going down one level in depth erases one value \(e_{i,x}, x \in [\ell ].\)

  8. 8.

    For comparison of concrete sizes see the common recommendations: https://www.keylength.com/.

References

  1. Abdalla, M., Miner, S., Namprempre, C.: Forward-Secure threshold signature schemes. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 441–456. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45353-9_32

    Chapter  Google Scholar 

  2. Boneh, D., Boyen, X., Goh, E.-J.: Hierarchical identity based encryption with constant size ciphertext. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 440–456. Springer, Heidelberg (2005). https://doi.org/10.1007/11426639_26

    Chapter  Google Scholar 

  3. Boneh, D., Boyen, X., Halevi, S.: Chosen ciphertext secure public key threshold encryption without random oracles. In: Pointcheval, D. (ed.) CT-RSA 2006. LNCS, vol. 3860, pp. 226–243. Springer, Heidelberg (2006). https://doi.org/10.1007/11605805_15

    Chapter  Google Scholar 

  4. Boneh, D., Canetti, R., Halevi, S., Katz, J.: Chosen-ciphertext security from identity-based encryption. SIAM J. Comput. 36(5), 1301–1328 (2007)

    Article  MathSciNet  Google Scholar 

  5. 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_30

    Chapter  Google Scholar 

  6. Canetti, R., Halevi, S., Katz, J.: A forward-secure public-key encryption scheme. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 255–271. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-39200-9_16

    Chapter  Google Scholar 

  7. Chatterjee, S., Hankerson, D., Menezes, A.: On the efficiency and security of pairing-based protocols in the type 1 and type 4 settings. In: Hasan, M.A., Helleseth, T. (eds.) WAIFI 2010. LNCS, vol. 6087, pp. 114–134. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13797-6_9

    Chapter  MATH  Google Scholar 

  8. Chow, S.S.M., Go, H.W., Hui, L.C.K., Yiu, S.-M.: Multiplicative forward-secure threshold signature scheme. Int. J. Netw. Secur. 7, 397–403 (2008)

    Google Scholar 

  9. Freeman, D.M.: Converting pairing-based cryptosystems from composite-order groups to prime-order groups. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 44–61. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_3

    Chapter  Google Scholar 

  10. Gennaro, R., Jarecki, S., Krawczyk, H., Rabin, T.: Secure distributed key generation for discrete-log based cryptosystems. J. Cryptology 20(1), 51–83 (2006). https://doi.org/10.1007/s00145-006-0347-3

    Article  MathSciNet  MATH  Google Scholar 

  11. Herzberg, A., Jakobsson, M., Jarecki, S., Krawczyk, H., Yung, M.: Proactive public key and signature systems. In: Proceedings of the ACM Conference on Computer and Communications Security, January 1997

    Google Scholar 

  12. Herzberg, A., Jarecki, S., Krawczyk, H., Yung, M.: Proactive secret sharing or: how to cope with perpetual leakage. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 339–352. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-44750-4_27

    Chapter  Google Scholar 

  13. Lewko, A., Okamoto, T., Sahai, A., Takashima, K., Waters, B.: Fully secure functional encryption: attribute-based encryption and (Hierarchical) inner product encryption. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 62–91. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_4

    Chapter  Google Scholar 

  14. Lewko, A., Waters, B.: New techniques for dual system encryption and fully secure HIBE with short ciphertexts. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 455–479. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-11799-2_27

    Chapter  Google Scholar 

  15. Libert, B., Yung, M.: Adaptively secure non-interactive threshold cryptosystems. Theoret. Comput. Sci. 478, 76–100 (2013)

    Article  MathSciNet  Google Scholar 

  16. Liu, L.-S., Chu, C.-K., Tzeng, W.-G.: A threshold GQ signature scheme. In: Zhou, J., Yung, M., Han, Y. (eds.) ACNS 2003. LNCS, vol. 2846, pp. 137–150. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45203-4_11

    Chapter  Google Scholar 

  17. Ostrovsky, R., Yung, M.: How to withstand mobile virus attacks (extended abstract). In: Proceedings of the Tenth Annual ACM Symposium on Principles of Distributed Computing, PODC 1991, pp. 51–59. ACM, New York (1991)

    Google Scholar 

  18. Tzeng, W.-G., Tzeng, Z.-J.: Robust forward-secure signature schemes with proactive security. In: Kim, K. (ed.) PKC 2001. LNCS, vol. 1992, pp. 264–276. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44586-2_19

    Chapter  MATH  Google Scholar 

  19. Waters, B.: Dual system encryption: realizing fully secure IBE and HIBE under simple assumptions. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 619–636. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03356-8_36

    Chapter  Google Scholar 

  20. Yu, J., Kong, F.: Forward secure threshold signature scheme from bilinear pairings. In: Wang, Y., Cheung, Y., Liu, H. (eds.) CIS 2006. LNCS (LNAI), vol. 4456, pp. 587–597. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74377-4_61

    Chapter  Google Scholar 

  21. Zhang, X., Xu, C., Zhang, W.: Efficient chosen ciphertext secure threshold public-key encryption with forward security. In: Proceedings of the 2013 Fourth International Conference on Emerging Intelligent Data and Web Technologies, EIDWT 2013, USA, pp. 407–413. IEEE Computer Society (2013)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Group of IT Security and Cryptography, University of Wuppertal, Wuppertal, Germany

    Rafael Kurek

Authors
  1. Rafael Kurek
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Rafael Kurek .

Editor information

Editors and Affiliations

  1. Faculty of Information Technology, Monash University, Clayton, VIC, Australia

    Joseph K. Liu

  2. Murdoch University, Perth, WA, Australia

    Hui Cui

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Kurek, R. (2020). Efficient Forward-Secure Threshold Public Key Encryption. In: Liu, J., Cui, H. (eds) Information Security and Privacy. ACISP 2020. Lecture Notes in Computer Science(), vol 12248. Springer, Cham. https://doi.org/10.1007/978-3-030-55304-3_17

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-55304-3_17

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-55303-6

  • Online ISBN: 978-3-030-55304-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation