Broadcast Encryption using Sum-Product decomposition of Boolean functions

Aurélien Dupin; Simon Abelard

doi:10.62056/av4fe0iuc

Broadcast Encryption using Sum-Product decomposition of Boolean functions

Authors

Aurélien Dupin, Simon Abelard

Aurélien Dupin

Thales SIX France, Gennevilliers, France
aurelien dot dupin at thalesgroup dot com

Simon Abelard

Thales SIX France, Gennevilliers, France
sabelard at protonmail dot com

Keywords: Broadcast Encryption Boolean Functions

Abstract

The problem of Broadcast Encryption (BE) consists in broadcasting an encrypted message to a large number of users or receiving devices in such a way that the emitter of the message can control which of the users can or cannot decrypt it.

Since the early 1990s, the design of BE schemes has received significant interest and many different concepts were proposed. A major breakthrough was achieved by Naor, Naor and Lotspiech (CRYPTO 2001) by partitioning cleverly the set of authorized users and associating a symmetric key to each subset. Since then, while there have been many advances in public-key based BE schemes, mostly based on bilinear maps, little was made on symmetric cryptography.

In this paper, we design a new symmetric-based BE scheme, named $\Sigma\Pi$BE, that relies on logic optimization and consensual security assumptions. It is competitive with the work of Naor et al. and provides a different tradeoff: the bandwidth requirement is significantly lowered at the cost of an increase in the key storage.

References

[AWY20]

Shweta Agrawal, Daniel Wichs, and Shota Yamada. Optimal broadcast encryption from LWE and pairings in the standard model. In Rafael Pass and Krzysztof Pietrzak, editors, Theory of Cryptography - 18th International Conference, TCC 2020, Durham, NC, USA, November 16-19, 2020, Proceedings, Part I, volume 12550 of Lecture Notes in Computer Science, 149–178. Springer, 2020. https://doi.org/10.1007/978-3-030-64375-1_6.

Google Scholar ePrint

[BGW05]

Dan Boneh, Craig Gentry, and Brent Waters. Collusion resistant broadcast encryption with short ciphertexts and private keys. In Victor Shoup, editor, Advances in Cryptology - CRYPTO 2005: 25th Annual International Cryptology Conference, Santa Barbara, California, USA, August 14-18, 2005, Proceedings, volume 3621 of Lecture Notes in Computer Science, 258–275. Springer, 2005. https://doi.org/10.1007/11535218_16.

Google Scholar ePrint

[BHMS84]

Robert K. Brayton, Gary D. Hachtel, Curtis T. McMullen, and Alberto L. Sangiovanni-Vincentelli. Logic Minimization Algorithms for VLSI Synthesis. Volume 2 of The Kluwer International Series in Engineering and Computer Science. Springer, 1984. ISBN 978-1-4612-9784-0. https://doi.org/10.1007/978-1-4613-2821-6.

Google Scholar ePrint

[BS13]

Sanjay Bhattacherjee and Palash Sarkar. Complete tree subset difference broadcast encryption scheme and its analysis. Des. Codes Cryptogr., 66(1-3):335–362, 2013. https://doi.org/10.1007/s10623-012-9702-6.

Google Scholar ePrint

[BS16]

S. Bhattacherjee and P. Sarkar. Reducing communication overhead of the subset difference scheme. IEEE Transactions on Computers, 65(08):2575–2587, aug 2016. https://doi.org/10.1109/TC.2015.2485231.

Google Scholar ePrint

[CFN61]

A. Cobham, R. Fridshal, and J. H. North. An application of linear programming to the minimization of boolean functions. In 2nd Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 1961), volume, 3–9. 1961. https://doi.org/10.1109/FOCS.1961.5.

Google Scholar ePrint

[CM78]

Ashok K. Chandra and George Markowsky. On the number of prime implicants. Discret. Math., 24(1):7–11, 1978. https://doi.org/10.1016/0012-365X(78)90168-1.

Google Scholar ePrint

[DF03]

Yevgeniy Dodis and Nelly Fazio. Public key trace and revoke scheme secure against adaptive chosen ciphertext attack. In Yvo Desmedt, editor, Public Key Cryptography - PKC 2003, 6th International Workshop on Theory and Practice in Public Key Cryptography, Miami, FL, USA, January 6-8, 2003, Proceedings, volume 2567 of Lecture Notes in Computer Science, 100–115. Springer, 2003. https://doi.org/10.1007/3-540-36288-6_8.

Google Scholar ePrint

[DGB12]

Renaud Dubois, Aurore Guillevic, and Marine Sengelin Le Breton. Improved broadcast encryption scheme with constant-size ciphertext. In Michel Abdalla and Tanja Lange, editors, Pairing-Based Cryptography - Pairing 2012 - 5th International Conference, Cologne, Germany, May 16-18, 2012, Revised Selected Papers, volume 7708 of Lecture Notes in Computer Science, 196–202. Springer, 2012. https://doi.org/10.1007/978-3-642-36334-4_12.

Google Scholar ePrint

[FN93]

Amos Fiat and Moni Naor. Broadcast encryption. In Douglas R. Stinson, editor, Advances in Cryptology - CRYPTO '93, 13th Annual International Cryptology Conference, Santa Barbara, California, USA, August 22-26, 1993, Proceedings, volume 773 of Lecture Notes in Computer Science, 480–491. Springer, 1993. https://doi.org/10.1007/3-540-48329-2_40.

Google Scholar ePrint

[HS02]

Dani Halevy and Adi Shamir. The LSD broadcast encryption scheme. In Moti Yung, editor, Advances in Cryptology - CRYPTO 2002, 22nd Annual International Cryptology Conference, Santa Barbara, California, USA, August 18-22, 2002, Proceedings, volume 2442 of Lecture Notes in Computer Science, 47–60. Springer, 2002. https://doi.org/10.1007/3-540-45708-9_4.

Google Scholar ePrint

[KL14]

Jonathan Katz and Yehuda Lindell. Introduction to Modern Cryptography, Second Edition. CRC Press, 2014. ISBN 9781466570269.

Google Scholar ePrint

[KRS99]

Ravi Kumar, Sridhar Rajagopalan, and Amit Sahai. Coding constructions for blacklisting problems without computational assumptions. In Michael J. Wiener, editor, Advances in Cryptology - CRYPTO '99, 19th Annual International Cryptology Conference, Santa Barbara, California, USA, August 15-19, 1999, Proceedings, volume 1666 of Lecture Notes in Computer Science, 609–623. Springer, 1999. https://doi.org/10.1007/3-540-48405-1_38.

Google Scholar ePrint

[NNL01]

Dalit Naor, Moni Naor, and Jeffery Lotspiech. Revocation and tracing schemes for stateless receivers. In Joe Kilian, editor, Advances in Cryptology - CRYPTO 2001, 21st Annual International Cryptology Conference, Santa Barbara, California, USA, August 19-23, 2001, Proceedings, volume 2139 of Lecture Notes in Computer Science, 41–62. Springer, 2001. https://doi.org/10.1007/3-540-44647-8_3.

Google Scholar ePrint

[Pet56]

Stanley R Petrick. A direct determination of the irredundant forms of a boolean function from the set of prime implicants. Air Force Cambridge Res. Center Tech. Report, pages 56–110, 1956.

Google Scholar ePrint

[PPSS13]

Duong Hieu Phan, David Pointcheval, Siamak Fayyaz Shahandashti, and Mario Strefler. Adaptive CCA broadcast encryption with constant-size secret keys and ciphertexts. Int. J. Inf. Sec., 12(4):251–265, 2013. https://doi.org/10.1007/s10207-013-0190-0.

Google Scholar ePrint

[SDSP23]

Vikas Srivastava, Sumit Kumar Debnath, Pantelimon Stanica, and Saibal Kumar Pal. A multivariate identity-based broadcast encryption with applications to the internet of things. Adv. Math. Commun., 17(6):1302–1313, 2023. https://doi.org/10.3934/amc.2021050.

Google Scholar ePrint

[TT01]

Wen-Guey Tzeng and Zhi-Jia Tzeng. A public-key traitor tracing scheme with revocation using dynamic shares. In Kwangjo Kim, editor, Public Key Cryptography, 4th International Workshop on Practice and Theory in Public Key Cryptography, PKC 2001, Cheju Island, Korea, February 13-15, 2001, Proceedings, volume 1992 of Lecture Notes in Computer Science, 207–224. Springer, 2001. https://doi.org/10.1007/3-540-44586-2_16.

Google Scholar ePrint

[Wee22]

Hoeteck Wee. Optimal broadcast encryption and CP-ABE from evasive lattice assumptions. In Orr Dunkelman and Stefan Dziembowski, editors, Advances in Cryptology - EUROCRYPT 2022 - 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, May 30 - June 3, 2022, Proceedings, Part II, volume 13276 of Lecture Notes in Computer Science, 217–241. Springer, 2022. https://doi.org/10.1007/978-3-031-07085-3_8.

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/av4fe0iuc

History

Submitted: 2024-01-08
Accepted: 2024-03-05
Published: 2024-04-09

How to cite

Aurélien Dupin and Simon Abelard, "Broadcast Encryption using Sum-Product decomposition of Boolean functions," IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/av4fe0iuc.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{CiC-1-1-18,
    author = "Dupin, Aurélien and Abelard, Simon",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "Broadcast Encryption using Sum-Product decomposition of Boolean functions",
    volume = "1",
    number = "1",
    date = "2024-04-09",
    year = "2024",
    issn = "3006-5496",
    doi = "10.62056/av4fe0iuc"
}

TY - JOUR
AU - Dupin, Aurélien
AU - Abelard, Simon
PY  - 2024
TI  - Broadcast Encryption using Sum-Product decomposition of Boolean functions
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 1
IS  - 1
DO  - 10.62056/av4fe0iuc
UR  - https://doi.org/10.62056/av4fe0iuc
AB  - <p>    The problem of Broadcast Encryption (BE) consists in broadcasting an encrypted message to a large number of users or receiving devices in such a way that the emitter of the message can control which of the users can or cannot decrypt it.</p><p>    Since the early 1990s, the design of BE schemes has received significant interest and many different concepts were proposed. A major breakthrough was achieved by Naor, Naor and Lotspiech (CRYPTO 2001) by partitioning cleverly the set of authorized users and associating a symmetric key to each subset. Since then, while there have been many advances in public-key based BE schemes, mostly based on bilinear maps, little was made on symmetric cryptography.</p><p>    In this paper, we design a new symmetric-based BE scheme, named $\Sigma\Pi$BE, that relies on logic optimization and consensual security assumptions. It is competitive with the work of Naor et al. and provides a different tradeoff: the bandwidth requirement is significantly lowered at the cost of an increase in the key storage. </p>
ER  -

Aurélien Dupin and Simon Abelard, "Broadcast Encryption using Sum-Product decomposition of Boolean functions," IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/av4fe0iuc.