-
Locating modifications in signed data for partial data integrity
Authors:
Thaís Bardini Idalino,
Lucia Moura,
Ricardo Felipe Custódio,
Daniel Panario
Abstract:
We consider the problem of detecting and locating modifications in signed data to ensure partial data integrity. We assume that the data is divided into $n$ blocks (not necessarily of the same size) and that a threshold $d$ is given for the maximum amount of modified blocks that the scheme can support. We propose efficient algorithms for signature and verification steps which provide a reasonably…
▽ More
We consider the problem of detecting and locating modifications in signed data to ensure partial data integrity. We assume that the data is divided into $n$ blocks (not necessarily of the same size) and that a threshold $d$ is given for the maximum amount of modified blocks that the scheme can support. We propose efficient algorithms for signature and verification steps which provide a reasonably compact signature size, for controlled sizes of $d$ with respect to $n$. For instance, for fixed $d$ the standard signature size gets multiplied by a factor of $O(\log n)$, while allowing the identification of up to $d$ modified blocks. Our scheme is based on nonadaptive combinatorial group testing and cover-free families.
△ Less
Submitted 31 July, 2022;
originally announced August 2022.
-
Modification tolerant signature schemes: location and correction
Authors:
Thais Bardini Idalino,
Lucia Moura,
Carlisle Adams
Abstract:
This paper considers malleable digital signatures, for situations where data is modified after it is signed. They can be used in applications where either the data can be modified (collaborative work), or the data must be modified (redactable and content extraction signatures) or we need to know which parts of the data have been modified (data forensics). A \new{classical} digital signature is val…
▽ More
This paper considers malleable digital signatures, for situations where data is modified after it is signed. They can be used in applications where either the data can be modified (collaborative work), or the data must be modified (redactable and content extraction signatures) or we need to know which parts of the data have been modified (data forensics). A \new{classical} digital signature is valid for a message only if the signature is authentic and not even one bit of the message has been modified. We propose a general framework of modification tolerant signature schemes (MTSS), which can provide either location only or both location and correction, for modifications in a signed message divided into $n$ blocks. This general scheme uses a set of allowed modifications that must be specified. We present an instantiation of MTSS with a tolerance level of $d$, indicating modifications can appear in any set of up to $d$ message blocks. This tolerance level $d$ is needed in practice for parametrizing and controlling the growth of the signature size with respect to the number $n$ of blocks; using combinatorial group testing (CGT) the signature has size $O(d^2 \log n)$ which is close to the \new{best known} lower bound \new{of $Ω(\frac{d^2}{\log d} (\log n))$}. There has been work in this very same direction using CGT by Goodrich et al. (ACNS 2005) and Idalino et al. (IPL 2015). Our work differs from theirs in that in one scheme we extend these ideas to include corrections of modification with provable security, and in another variation of the scheme we go in the opposite direction and guarantee privacy for redactable signatures, in this case preventing any leakage of redacted information.
△ Less
Submitted 31 July, 2022;
originally announced August 2022.
-
Nested Cover-Free Families for Unbounded Fault-Tolerant Aggregate Signatures
Authors:
Thais Bardini Idalino,
Lucia Moura
Abstract:
Aggregate signatures are used to create one short proof of authenticity and integrity from a set of digital signatures. However, one invalid signature in the set invalidates the entire aggregate, giving no information on which signatures are valid. Hartung et al. (2016) propose a fault-tolerant aggregate signature scheme based on combinatorial group testing. Given a bound $d$ on the number of inva…
▽ More
Aggregate signatures are used to create one short proof of authenticity and integrity from a set of digital signatures. However, one invalid signature in the set invalidates the entire aggregate, giving no information on which signatures are valid. Hartung et al. (2016) propose a fault-tolerant aggregate signature scheme based on combinatorial group testing. Given a bound $d$ on the number of invalid signatures among $n$ signatures to be aggregated, this scheme uses $d$-cover-free families to determine which signatures are invalid. These combinatorial structures guarantee a moderate increase on the size of the aggregate signature that can reach the best possible compression ratio of $O(\frac{n}{\log n})$, for fixed $d$, coming from an information theoretical bound. The case where the total number of signatures grows dynamically (unbounded scheme) was not satisfactorily solved in their original paper, since explicit constructions had constant compression ratios. In the present paper, we propose efficient solutions for the unbounded scheme, relying on sequences of $d$-cover-free families that we call {\em nested families}. Some of our constructions yield high compression ratio close to \rmv{the information theoretical bound}\todo{the best known upper bound}. We also propose the use of $(d,λ)$-cover-free families to support the loss of up to $λ-1$ parts of the aggregate.
△ Less
Submitted 31 July, 2022;
originally announced August 2022.
-
Structure-aware combinatorial group testing: a new method for pandemic screening
Authors:
Thais Bardini Idalino,
Lucia Moura
Abstract:
Combinatorial group testing (CGT) is used to identify defective items from a set of items by grouping them together and performing a small number of tests on the groups. Recently, group testing has been used to design efficient COVID-19 testing, so that resources are saved while still identifying all infected individuals. Due to test waiting times, a focus is given to non-adaptive CGT, where group…
▽ More
Combinatorial group testing (CGT) is used to identify defective items from a set of items by grouping them together and performing a small number of tests on the groups. Recently, group testing has been used to design efficient COVID-19 testing, so that resources are saved while still identifying all infected individuals. Due to test waiting times, a focus is given to non-adaptive CGT, where groups are designed a priori and all tests can be done in parallel. The design of the groups can be done using Cover-Free Families (CFFs). The main assumption behind CFFs is that a small number $d$ of positives are randomly spread across a population of $n$ individuals. However, for infectious diseases, it is reasonable to assume that infections show up in clusters of individuals with high contact (children in the same classroom within a school, households within a neighbourhood, students taking the same courses within a university, people seating close to each other in a stadium). The general structure of these communities can be modeled using hypergraphs, where vertices are items to be tested and edges represent clusters containing high contacts. We consider hypergraphs with non-overlapping edges and overlapping edges (first two examples and last two examples, respectively). We give constructions of what we call structure-aware CFF, which uses the structure of the underlying hypergraph. We revisit old CFF constructions, boosting the number of defectives they can identify by taking the hypergraph structure into account. We also provide new constructions based on hypergraph parameters.
△ Less
Submitted 16 February, 2022;
originally announced February 2022.
