Cryptography is of fundamental importance to guarantee the security of communications, from the point-to-point transmission of messages and documents to the storage of big sets of data on cloud providers. As an example, we can use encryption, message authentication codes, and digital signatures to help us guarantee the privacy, integrity, and authenticity of data that is stored and/or transmitted. Many cryptographical solutions have a Boolean outcome, for example, the message is either authentic and accepted as it is, or it is not and so it needs to be rejected/re-transmitted. This outcome may be acceptable in scenarios where we can easily re-transmit the message, but it can pose a challenge when we deal with a large amount of data or a more sensitive content in which changes need to be further explored. In this context, this thesis proposes solutions to provide fault tolerance to certain cryptographic problems that traditionally have an all-or-nothing outcome.
Fault tolerance is application dependent. In the case of a digital signature of a doc- ument that has been later modified, a fault-tolerant scheme can ensure authenticity and further identify which parts of the document were modified. This approach can be used in data forensics to investigate cybercrime, or to create redactable signatures for the purpose of privacy. In the case of aggregation of signatures, we consider an aggregation of a set of signatures containing a few invalid signatures (in the traditional sense). A fault-tolerant scheme is able to identify which signatures are valid and which ones are invalid, instead of rejecting the whole set. Digital signatures and aggregation of digital signatures require fault tolerance to be ensured at the origin (signer algorithm and aggregation algorithm, respectively), rather than just at the destination (verification algorithm). For this rea- son, we focus on techniques from combinatorial group testing that are nonadaptive rather than adaptive. This is in contrast with other applications of group testing, such as batch verification of signatures, employed at the verifier’s end which allow both adaptive and nonadaptive solutions.
In this work, we explore solutions for fault tolerance using techniques of identification of defective elements used in nonadaptive combinatorial group testing. More specifically, we use the well studied cover-free families (CFFs). A d-cover-free family d-CFF(t, n) is a set system with n subsets of a t-set, where the union of any d subsets does not contain any other. A d-CFF(t, n) allows for the identification of up to d defective elements in a set of n elements by performing only t tests (typically t ≪ n). In the literature, CFFs are used to solve many problems in cryptography. In this work, we explore different aspects of cover-free families in order to better approach fault tolerance problems.
The problems we investigate can be divided into two categories: static problems (fixed size) and dynamic problems (increasing size). In the context of static problems, we consider modification-tolerant digital signature schemes, which allow the identification of modifica- tions in signed data using a d-CFF, and in some cases the correction of such modifications in order to retrieve the originally signed data. We also propose a generalization of the classical definition of a d-CFF to support variable cover-free property, followed by some constructions and potential applications in cryptography. For dynamic problems, we con- sider the application of fault-tolerant aggregation of signatures. This problem requires an
ii
infinite sequence of CFFs with increasing n, consequently increasing t, and potentially in- creasing d. In this context, we investigate monotone, nested, and embedding sequences of CFFs, and propose constructions using techniques from combinatorial design theory and finite fields. In constructing these families, we are concerned with their compression ratio. The compression ratio of a sequence of CFFs measures how slowly the number of tests grow with respect to the number of elements to be tested, which affects the overall efficiency of the method. We provide constructions of CFF sequences with different compression ratios, which depend on relations among the CFF parameters in the sequence and the type of sequence. Some of these sequences achieve the best possible compression ratio, which meets the best known upper bound. Monotone, nested and embedding sequences of CFFs can be used in any group testing problem that is dynamic in nature. We discuss various cryptographical applications that can benefit from these infinite sequences of CFFs.
| Identifer | oai:union.ndltd.org:uottawa.ca/oai:ruor.uottawa.ca:10393/39672 |
| Date | 27 September 2019 |
| Creators | Bardini Idalino, Thais |
| Contributors | Moura, Lucia |
| Publisher | Université d'Ottawa / University of Ottawa |
| Source Sets | Université d’Ottawa |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | application/pdf |
Page generated in 0.002 seconds