Enhanced Threshold Schemes and their Applications

Thalia Laing

Research output: ThesisDoctoral Thesis

377 Downloads (Pure)


Techniques that distribute data across multiple players in such a way that a threshold number of players can reconstruct the data, whilst any fewer than the threshold cannot learn information about the data, are well established. These techniques are called threshold schemes and are important as they allow for increased availability, add redundancy and offer security without the reliance on cryptographic keys. With constrained devices restricted by low computational capabilities becoming more prevalent, it is important to discuss the use of threshold schemes in this setting. We study efficient threshold schemes and their applications in constrained devices and illustrate the compromise between efficiency and security.

We begin by using combinatorial techniques to propose an ideal, efficient, perfectly secure threshold scheme, which we analyse and compare to existing efficient threshold schemes. We show our scheme is efficient, with respect to the number of bitwise operations, compared to other schemes.

Next, we revisit a computationally secure threshold scheme, called AONT-RS, originally proposed in 2010. We generalise the scheme to allow for greater cryptographic flexibility and prove the scheme to be secure in the random oracle model. When compared to Krawczyk’s scheme, the generalised scheme is more efficient, but requires greater assumptions in order to be proven secure. We then discuss extending AONT-RS to be robust, which prevents the unauthorised alteration of data.

Following this, we consider repairable threshold schemes, which enable recovery of a corrupted share without the help of a dealer. We consider and refine existing methods, analysing the storage costs and bandwidth required for each repair. We introduce a new metric to measure the repairability of the scheme, then consider secure regenerating codes and applying these techniques to repairable threshold schemes. We finish by comparing a range of techniques and highlight how they find a compromise between bandwidth and storage.

Finally, we propose localised multi-secret sharing schemes, which are multi-secret sharing schemes for an ordered set of players in which a sufficient number of sufficiently close players are able to recover secrets. We define threshold versions of localised multi-secret sharing schemes, provide lower bounds on the share size and give explicit constructions of schemes to show these bounds are tight. We then analyse a range of approaches to relaxing the model that provides a trade-off between the share size and the security provided by the scheme. Finally, we explore applying localised threshold multi-secret sharing schemes to RFID enabled supply chains.
Original languageEnglish
Awarding Institution
  • Royal Holloway, University of London
  • Martin, Keith M., Supervisor
Thesis sponsors
Award date1 Feb 2018
Publication statusUnpublished - 2018


  • threshold schemes, secret sharing, security, perfect security, computational security, repairable threshold schemes, localised multi-secret sharing schemes, combinatorics, applications, lightweight devices

Cite this