Improved Broadcast Encryption Scheme with Constant-Size Ciphertext

Renaud Dubois; Aurore Guillevic; Marine Sengelin Le Breton

Paper 2012/370 Original: eprint.iacr.org/2012/370 ↗

Improved Broadcast Encryption Scheme with Constant-Size Ciphertext

Renaud Dubois

Aurore Guillevic

Marine Sengelin Le Breton

Abstract

The Boneh-Gentry-Waters (BGW) scheme is one of the most efficient broadcast encryption scheme regarding the overhead size. This performance relies on the use of a pairing. Hence this protocol can benefit from public key improvements. The ciphertext is of constant size, whatever the proportion of revoked users is. The main lasting constraint is the computation time at receiver end as it depends on the number of revoked users. In this paper we describe two modifications to improve the BGW bandwidth and time complexity. First we rewrite the protocol and its security proof with an asymmetric pairing over the Barreto-Naehrig (BN) curves instead of a symmetric one over supersingular curves. This modification leads to a practical gain of 60 % in speed and 84 % in bandwidth. The second tweaks allows to reduce the computation time from $O(n-r)$ to $\min(O(r),O(n-r))$ for the worst case (and better for the average case). We give performance measures of our implementation for a 128-bit security level of the modified protocol on a smartphone.

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Preprint.
History: 2012-07-05: last updated; 2012-07-05: published
Short URL: https://ia.cr/2012/370
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2012/370,
      author = {Renaud Dubois and Aurore Guillevic and Marine Sengelin Le Breton},
      title = {Improved Broadcast Encryption Scheme with Constant-Size Ciphertext},
      howpublished = {Cryptology {ePrint} Archive, Paper 2012/370},
      year = {2012},
      url = {https://eprint.iacr.org/2012/370}
}