Semantic Security and the Second-Largest Eigenvalue of Biregular Graphs

Moritz Wiese, Holger Boche

Biregular irreducible functions are introduced and applied as security components (instead of, e.g., universal hash functions) in modular wiretap coding schemes, whose second component is an error-correcting code. These schemes are called modular BRI schemes. An upper bound on the semantic security information leakage of modular BRI schemes in a one-shot setting is derived which separates the effects of the biregular irreducible function on the one hand and the error-correcting code plus the channel on the other hand. A characterization of biregular irreducible functions is given in terms of connected edge-disjoint biregular graphs. It allows for the construction of new biregular irreducible functions from families of edge-disjoint Ramanujan graphs, which are shown to exist. A concrete and frequently used arithmetic universal hash function can be converted into a biregular irreducible function for certain parameters. Sequences of Ramanujan biregular irreducible functions are constructed which exhibit an optimal trade-off between the size of the regularity set and the rate of decrease of the second-largest eigenvalues of associated stochastic matrices. Together with the one-shot bound on the information leakage, the existence of these sequences implies an asymptotic coding result for modular BRI schemes applied to discrete and Gaussian wiretap channels. It shows that the separation of error correction and security as done in a modular BRI scheme is optimal. In particular, the secrecy capacity of any discrete and Gaussian wiretap channel is achievable with semantic security by modular BRI schemes. The same holds for a derived construction where the seed is generated locally by the sender and reused several times. It is shown that the optimal sequences of biregular irreducible functions used in the above constructions must be nearly Ramanujan.

Knowledge Graph



Sign up or login to leave a comment