Embedding cover-free families and cryptographical applications

DOI10.3934/AMC.2019039MaRDI QIDQ2274240zbMATH OpenOpenAlexWikidataFDO

Authors Lucia Moura, Thais Bardini Idalino

Publication date 19 September 2019

Published in Advances in Mathematics of Communications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1811.00126

zbMATH Keywords

combinatorial cryptographycombinatorial group testingcover-free familyembedding cover-free familypolynomial over finite fieldseparating hash family

Mathematics Subject Classification ID

Enumerative combinatorics (05A99) Combinatorial aspects of packing and covering (05B40) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Fault detection; testing in circuits and networks (94C12)

Abstract: Cover-free families are set systems used as solutions for a large variety of problems, and in particular, problems where we deal with $n$ elements and want to identify $d$ invalid ones among them by performing only $t$ tests ($tleqn$). We are specially interested in cryptographic problems, and we note that some of these problems need cover-free families with an increasing size $n$. Solutions that propose the increase of $n$, such as emph{monotone families} and emph{nested families}, have been recently considered in the literature. In this paper, we propose a generalization that we call emph{embedding families}, which allows us to increase both $n$ and $d$. We propose constructions of emph{embedding families} using polynomials over finite fields, and show specific cases where this construction allows us to prioritize increase of $d$ or $n$ with good compression ratios. We also provide new constructions for monotone families with improved compression ratio. Finally, we show how to use embedded sequences of orthogonal arrays and packing arrays to build embedding families.

Recommendations

• Pseudo-free families and cryptographic primitives
• scientific article; zbMATH DE number 6341749
• Covering sequences of Boolean functions and their cryptographic significance
• Cover-preserving embedding of modular lattices
• Cryptography and Coding
• scientific article; zbMATH DE number 691466
• Partial covering sequences: a method for designing classes of cryptographic functions
• Hidden cosets and applications to unclonable cryptography
• Almost optimal cover-free families
• On a bound of cover-free families

Cited in

(8)

• Generalized cover-free families.
• Union-intersection-bounded families and their applications
• Structure-aware combinatorial group testing: a new method for pandemic screening
• Nested cover-free families for unbounded fault-tolerant aggregate signatures
• Union distinct families of sets, with an application to cryptography.
• Partial covering sequences: a method for designing classes of cryptographic functions
• A survey of cover-free families: constructions, applications, and generalizations
• Cover-free families on hypergraphs and combinatorial group testing

This page was built for publication: Embedding cover-free families and cryptographical applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2274240)