Key predistribution schemes and one-time broadcast encryption schemes from algebraic geometry codes

Hao Chen*, San Ling, Carles Padró, Huaxiong Wang, Chaoping Xing

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

6 Citations (Scopus)


Key predistribution schemes (KPSs) and one-time broadcast encryption schemes (OTBESs) are unconditionally secure protocols for key distribution in networks. The efficiency of these schemes has been measured in previous works in terms of their information rate, that is, the ratio between the length of the secret keys and the length of the secret information that must be stored by every user. Several constructions with optimal information rate have been proposed, but in them the secret keys are taken from a finite field with at least as many elements as the number of users in the network. This can be an important drawback in very large networks in which the nodes have limited computational resources as, for instance, wireless sensor networks. Actually, key predistribution schemes have been applied recently in the design of key distribution protocols for such networks. In this paper we present a method to construct key predistribution schemes from linear codes that provide new families of KPSs and OTBESs for an arbitrarily large number of users and with secret keys of constant size. As a consequence of the Gilbert-Varshamov bound, we can prove that our KPSs are asymptotically more efficient than previous constructions, specially if we consider KPSs that are secure against coalitions formed by a constant fraction of the users. We analyze as well the KPSs that are obtained from families of algebraic geometry linear codes that are above the Gilbert-Varshamov bound, as the ones constructed from the curves of Garcia and Stichtenoth. Finally, we discuss how the use of KPSs based on algebraic geometry codes can provide more efficient OTBESs.

Original languageEnglish
Title of host publicationCryptography and coding
Subtitle of host publication12th IMA International Conference, Cryptography and Coding 2009, Cirencester, UK, December 2009, proceedings
EditorsMatthew G. Parker
Place of PublicationBerlin
PublisherSpringer, Springer Nature
Number of pages15
ISBN (Print)3642108679, 9783642108679
Publication statusPublished - 2009
Event12th IMA International Conference on Cryptography and Coding - Cirencester, United Kingdom
Duration: 15 Dec 200917 Dec 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5921 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349


Other12th IMA International Conference on Cryptography and Coding
Country/TerritoryUnited Kingdom


Dive into the research topics of 'Key predistribution schemes and one-time broadcast encryption schemes from algebraic geometry codes'. Together they form a unique fingerprint.

Cite this