Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/2590296.2590329acmconferencesArticle/Chapter ViewAbstractPublication Pagesasia-ccsConference Proceedingsconference-collections
research-article

Multi-recipient encryption, revisited

Published: 04 June 2014 Publication History

Abstract

A variant of public key encryption that promises efficiency gains due to batch processing is multi-recipient public key encryption (MR-PKE). Precisely, in MR-PKE, a dedicated encryption routine takes a vector of messages and a vector of public keys and outputs a vector of ciphertexts, where the latter can be decrypted individually, as in regular PKE. In this paper we revisit the established security notions of MR-PKE and the related primitive MR-KEM. We identify a subtle flaw in a security model by Bellare, Boldyreva, and Staddon, that also appears in later publications by different authors. We further observe that these security models rely on the knowledge-of-secret-key (KOSK) assumption---a requirement that is rarely met in practice. We resolve this situation by proposing strengthened security notions for MR-PKE and MR-KEMs, together with correspondingly secure yet highly efficient schemes. Importantly, our models abstain from restricting the set of considered adversaries in the way prior models did, and in particular do not require the KOSK setting. We prove our constructions secure assuming hardness of the static Diffie-Hellman problem, in the random oracle model.

References

[1]
M. Abdalla, M. Bellare, and P. Rogaway. The oracle Diffie-Hellman assumptions and an analysis of DHIES. In D. Naccache, editor, CT-RSA 2001, volume 2020 of LNCS, pages 143--158, San Francisco, CA, USA, Apr. 8--12, 2001. Springer, Berlin, Germany.
[2]
J. Baek, R. Safavi-Naini, and W. Susilo. Efficient multi-receiver identity-based encryption and its application to broadcast encryption. In S. Vaudenay, editor, PKC 2005, volume 3386 of LNCS, pages 380--397, Les Diablerets, Switzerland, Jan. 23--26, 2005. Springer, Berlin, Germany.
[3]
M. Barbosa and P. Farshim. Efficient identity-based key encapsulation to multiple parties. In N. P. Smart, editor, 10th IMA International Conference on Cryptography and Coding, volume 3796 of LNCS, pages 428--441, Cirencester, UK, Dec. 19--21, 2005. Springer, Berlin, Germany.
[4]
M. Bellare, A. Boldyreva, K. Kurosawa, and J. Staddon. Multirecipient encryption schemes: How to save on bandwidth and computation without sacrificing security. IEEE Transactions on Information Theory, 53(11):3927--3943, 2007.
[5]
M. Bellare, A. Boldyreva, and J. Staddon. Randomness re-use in multi-recipient encryption schemes. In Y. Desmedt, editor, PKC 2003, volume 2567 of LNCS, pages 85--99, Miami, USA, Jan. 6--8, 2003. Springer, Berlin, Germany.
[6]
D. Boneh, C. Gentry, and B. Waters. Collusion resistant broadcast encryption with short ciphertexts and private keys. In V. Shoup, editor, CRYPTO 2005, volume 3621 of LNCS, pages 258--275, Santa Barbara, CA, USA, Aug. 14--18, 2005. Springer, Berlin, Germany.
[7]
S. Chatterjee and P. Sarkar. Multi-receiver identity-based key encapsulation with shortened ciphertext. In R. Barua and T. Lange, editors, INDOCRYPT 2006, volume 4329 of LNCS, pages 394--408, Kolkata, India, Dec. 11--13, 2006. Springer, Berlin, Germany.
[8]
R. Cramer and V. Shoup. A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. In H. Krawczyk, editor, CRYPTO'98, volume 1462 of LNCS, pages 13--25, Santa Barbara, CA, USA, Aug. 23--27, 1998. Springer, Berlin, Germany.
[9]
R. Cramer and V. Shoup. Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack. SIAM J. Computing, 33(1):167--226, 2003.
[10]
C. Delerablée. Identity-based broadcast encryption with constant size ciphertexts and private keys. In K. Kurosawa, editor, ASIACRYPT 2007, volume 4833 of LNCS, pages 200--215, Kuching, Malaysia, Dec. 2--6, 2007. Springer, Berlin, Germany.
[11]
T. ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. In G. R. Blakley and D. Chaum, editors, CRYPTO'84, volume 196 of LNCS, pages 10--18, Santa Barbara, CA, USA, Aug. 19--23, 1984. Springer, Berlin, Germany.
[12]
A. Fiat and M. Naor. Broadcast encryption. In D. R. Stinson, editor, CRYPTO'93, volume 773 of LNCS, pages 480--491, Santa Barbara, CA, USA, Aug. 22--26, 1993. Springer, Berlin, Germany.
[13]
K. Kurosawa. Multi-recipient public-key encryption with shortened ciphertext. In D. Naccache and P. Paillier, editors, PKC 2002, volume 2274 of LNCS, pages 48--63, Paris, France, Feb. 12--14, 2002. Springer, Berlin, Germany.
[14]
D. Naor, M. Naor, and J. Lotspiech. Revocation and tracing schemes for stateless receivers. In J. Kilian, editor, CRYPTO 2001, volume 2139 of LNCS, pages 41--62, Santa Barbara, CA, USA, Aug. 19--23, 2001. Springer, Berlin, Germany.
[15]
N. P. Smart. Efficient key encapsulation to multiple parties. In C. Blundo and S. Cimato, editors, SCN 04, volume 3352 of LNCS, pages 208--219, Amalfi, Italy, Sept. 8--10, 2004. Springer, Berlin, Germany.

Cited By

View all
  • (2024)Group Oblivious Message Retrieval2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00115(4367-4385)Online publication date: 19-May-2024
  • (2023)A Study of KEM GeneralizationsSecurity Standardisation Research10.1007/978-3-031-30731-7_3(53-77)Online publication date: 7-Apr-2023
  • (2019)Proxy Re-Encryption That Supports Homomorphic Operations for Re-Encrypted CiphertextsIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1587/transfun.E102.A.81E102.A:1(81-98)Online publication date: 1-Jan-2019
  • Show More Cited By

Index Terms

  1. Multi-recipient encryption, revisited

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    ASIA CCS '14: Proceedings of the 9th ACM symposium on Information, computer and communications security
    June 2014
    556 pages
    ISBN:9781450328005
    DOI:10.1145/2590296
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 04 June 2014

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. efficiency
    2. multi-user setting
    3. public key encryption

    Qualifiers

    • Research-article

    Conference

    ASIA CCS '14
    Sponsor:

    Acceptance Rates

    ASIA CCS '14 Paper Acceptance Rate 50 of 255 submissions, 20%;
    Overall Acceptance Rate 418 of 2,322 submissions, 18%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)33
    • Downloads (Last 6 weeks)3
    Reflects downloads up to 19 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Group Oblivious Message Retrieval2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00115(4367-4385)Online publication date: 19-May-2024
    • (2023)A Study of KEM GeneralizationsSecurity Standardisation Research10.1007/978-3-031-30731-7_3(53-77)Online publication date: 7-Apr-2023
    • (2019)Proxy Re-Encryption That Supports Homomorphic Operations for Re-Encrypted CiphertextsIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1587/transfun.E102.A.81E102.A:1(81-98)Online publication date: 1-Jan-2019
    • (2019)Identity-based Multi-Recipient Public Key Encryption Scheme and Its Application in IoTMobile Networks and Applications10.1007/s11036-019-01490-6Online publication date: 19-Dec-2019
    • (2017)On the Robustness of RSA-OAEP Encryption and RSA-PSS Signatures Against (Malicious) Randomness FailuresProceedings of the 2017 ACM on Asia Conference on Computer and Communications Security10.1145/3052973.3053040(241-252)Online publication date: 2-Apr-2017
    • (2017)Certificateless Cryptographic Protocols for Efficient Drone-Based Smart City ApplicationsIEEE Access10.1109/ACCESS.2017.26841285(3721-3749)Online publication date: 2017

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media