Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2102.00983 · Designs Codes and Cryptography

Mosaics of combinatorial designs for information-theoretic security

Moritz Wiese, Holger Boche

Published Jan 5, 2022• 13 citations
arXivHTMLPDF

Abstract

Abstract We study security functions which can serve to establish semantic security for the two central problems of information-theoretic security: the wiretap channel, and privacy amplification for secret key generation. The security functions are functional forms of mosaics of combinatorial designs, more precisely, of group divisible designs and balanced incomplete block designs. Every member of a mosaic is associated with a unique color, and each color corresponds to a unique message or key value. Every block index of the mosaic corresponds to a public seed shared between the two trusted communicating parties. The seed set should be as small as possible. We give explicit examples which have an optimal or nearly optimal trade-off of seed length versus color (i.e., message or key) rate. We also derive bounds for the security performance of security functions given by functional forms of mosaics of designs.

DOI
10.1007/s10623-021-00994-1

Related papers

Mosaics of combinatorial designs for privacy amplification

Moritz Wiese, Holger Boche

We study security functions which can serve to establish semantic security for privacy amplification in secret key generation. The security functions are functional forms of mosaics of combinatorial designs, more precisely, of group divisible designs and balanced incomplete block designs. Every member of a mosaic corresponds to a unique key value. We give explicit examples which have an optimal or nearly optimal tradeoff of seed size, given by the size of the block index set of the mosaics, versus key rate. We also derive bounds for the security performance in privacy amplification of security functions given by functional forms of mosaics of designs.

IEEE International Symposium on Information Theory (ISIT)•Jul 12, 2021•1 citation

Mosaics of Combinatorial Designs for Semantic Security on Quantum Wiretap Channels

Holger Boche, Minglai Cai, Moritz Wiese

We study semantic security for classical-quantum channels. Our security functions are functional forms of mosaics of combinatorial designs. We extend methods in [25] from classical channels to classical-quantum channels to demonstrate that mosaics of designs ensure semantic security for classical-quantum channels, and are also capacity achieving coding schemes. An advantage of these modular wiretap codes is that we provide explicit code constructions that can be implemented in practice for every channel, given an arbitrary public code.

arXiv:2202.05314•IEEE International Symposium on Information Theory (ISIT)•Jun 26, 2022•4 citations

Contributions to Information Theoretically Secure Communication

Setareh Sharifian

Secure communication ensures the integrity and confidentiality of communication between connected devices. An information-theoretic approach to secure communication gives the strongest confidentiality guarantee by assuming that the attacker has unlimited computing power. The earliest formal model and definition of information-theoretic secure communication is by Shannon, who employed a secret key shared between communicating parties to provide confidentiality. An alternative elegant information-theoretic approach to secure communication views the natural characteristics of the environment (i.e., channel’s noise) as a resource to build security functionalities. This approach was first proposed by Wyner, and the corresponding secure communication model is called the wiretap channel model. These two approaches introduce two primary resources for providing information-theoretic secure communication: the shared secret key and physical properties of the communication medium. In this thesis, we study how to employ the above two resources for secure message transmission. We study this by using channel’s noise in the wiretap channel model. In this model, a sender is connected to the receiver and the adversary through two noisy channels. We propose a new wiretap encoding scheme with strong secrecy that provides perfect secrecy and reliability, asymptotically. The construction treats the noise in the adversary’s channel as a source of randomness that is extracted and used to hide the message from the adversary. We realize the wiretap channel model using cooperative jamming to evaluate the performance of wiretap codes in practice. We consider a model called keyed wiretap channel that unifies Wyner’s model with Shannon’s model of perfect secrecy for information systems, and propose a keyed encoding schemes with strong secrecy and other properties that are attractive in practice. We also study two-party information-theoretic secret key agreement when the two parties have access to samples of a common source of randomness and use a single message transmission to arrive at a shared random key. We propose a secret key agreement protocol in this setting, prove its security, and show its superior performance compared to other known protocols with the same properties. Finally, we propose an information-theoretic secret key agreement over a virtual wiretap channel created by cooperative jamming.

•May 15, 2020•0 citations

Semantic-Security Capacity for the Physical Layer via Information Theory

Ziv Goldfeld, Paul Cuff, Haim Henri Permuter

Physical layer security can ensure secure communication over noisy channels in the presence of an eavesdropper with unlimited computational power. We adopt an information theoretic variant of semantic-security (SS) (a cryptographic gold standard), as our secrecy metric and study the open problem of the type II wiretap channel (WTC II) with a noisy main channel is, whose secrecy-capacity is unknown even under looser metrics than SS. Herein the secrecy-capacity is derived and shown to be equal to its SS capacity. In this setting, the legitimate users communicate via a discrete-memory less (DM) channel in the presence of an eavesdropper that has perfect access to a subset of its choosing of the transmitted symbols, constrained to a fixed fraction of the block length. The secrecy criterion is achieved simultaneously for all possible eavesdropper subset choices. On top of that, SS requires negligible mutual information between the message and the eavesdropper's observations even when maximized over all message distributions. A key tool for the achievability proof is a novel and stronger version of Wyner's soft covering lemma. Specifically, the lemma shows that a random codebook achieves the soft-covering phenomenon with high probability. The probability of failure is doubly-exponentially small in the block length. Since the combined number of messages and subsets grows only exponentially with the block length, SS for the WTC II is established by using the union bound and invoking the stronger soft-covering lemma. The direct proof shows that rates up to the weak-secrecy capacity of the classic WTC with a DM erasure channel (EC) to the eavesdropper are achievable. The converse follows by establishing the capacity of this DM wiretap EC as an upper bound for the WTC II. From a broader perspective, the stronger soft-covering lemma constitutes a tool for showing the existence of codebooks that satisfy exponentially many constraints, a beneficial ability for many other applications in information theoretic security.

Software - Science, Technology and Engineering•Jun 1, 2016•6 citations

Coding for secrecy

Matthieu R. Bloch, João Barros

In this chapter, we discuss the construction of practical codes for secrecy. The design of codes for the wiretap channel turns out to be surprisingly difficult, and this area of information-theoretic security is still largely in its infancy. To some extent, the major obstacles in the road to secrecy capacity are similar to those that lay in the path to channel capacity: the random-coding arguments used to establish the secrecy capacity do not provide explicit code constructions. However, the design of wiretap codes is further impaired by the absence of a simple metric, such as a bit error rate, which could be evaluated numerically. Unlike codes designed for reliable communication, whose performance is eventually assessed by plotting a bit-error-rate curve, we cannot simulate an eavesdropper with unlimited computational power; hence, wiretap codes must possess enough structure to be provably secure. For certain channels, such as binary erasure wiretap channels, the information-theoretic secrecy constraint can be recast in terms of an algebraic property for a code-generator matrix. Most of the chapter focuses on such cases since this algebraic view of secrecy simplifies the analysis considerably. As seen in Chapter 4, the design of secret-key distillation strategies is a somewhat easier problem insofar as reliability and security can be handled separately by means of information reconciliation and privacy amplification. Essentially, the construction of coding schemes for key agreement reduces to the design of Slepian–Wolf-like codes for information reconciliation, which can be done efficiently with low-density parity-check (LDPC) codes or turbo-codes.

Cambridge University Press eBooks•Sep 22, 2011•3 citations

Information Theoretic Security over Physical-Layer Channels

Hadi Ahmadi

Wyner [96] proved that unconditionally secure communication over noisy channels is possible if the wiretapping channel is noisier than the main channel. The work has developed the following belief: Physical-channel characteristics are great resources to build security functionalities in the information-theoretic framework. We follow this belief and investigate the three problems of secret key establishment, manipulation detection, and distance bounding verification over physical-layer channels. We investigate secret key establishment (SKE) between Alice and Bob when they are connected through a pair of noisy wiretap channels with leakage to Eve. Our results show the possibility of SKE even in cases where the main channels are noisier than Eve's channels. We then notice two implicit assumptions of this work: (i) local randomness is freely available, and (ii) the wiretap channels are independent. We remove Assumption (i) by considering no local randomness for the parties. The results appreciate the role of noise as a single resource for randomness derivation and key generation in this setting. Regarding the second assumption, we consider the general two-way wiretap channel, where simultaneous data transmission can help achieve higher key rates. We show under what condition our security requirements can be strengthened without sacrificing the SK capacity. We consider manipulation detection against physical-layer adversaries noticing their limitations. We define leakage-resilient algebraic manipulation detection (LR-AMD) codes and prove optimal LR-AMD code constructions in general and special leakage scenarios. We show two applications of these codes: (i) robust nonperfect secret sharing and (ii) manipulation detection over wiretap channels. We then discuss how these codes can be composed with other primitives to guarantee bitwise manipulation detection and SKE against active adversaries over binary wiretap channels. Distance bounding verification (DBV) allows a verifier to check an upper bound on a claimed distance from a prover. We study DBV over physical channels with security against distance fraud (DFA), ma a fraud (MFA) and terrorist fraud (TFA) attacks. We show efficient DFA- and MFA-secure protocols only using physical channel properties. We further prove that TFA-security becomes feasible if the parties' communication is limited by the bounded retrieval model (BRM).

•Jan 1, 2012•0 citations
Abstract We study security functions which can serve to establish semantic security for the two central problems of information-theoretic security: the wiretap channel, and privacy amplification for secret key generation. The security functions are functional forms of mosaics of combinatorial designs, more precisely, of group divisible designs and balanced incomplete block designs. Every member of a mosaic is associated with a unique color, and each color corresponds to a unique message or key value. Every block index of the mosaic corresponds to a public seed shared between the two trusted communicating parties. The seed set should be as small as possible. We give explicit examples which have an optimal or nearly optimal trade-off of seed length versus color (i.e., message or key) rate. We also derive bounds for the security performance of security functions given by functional forms of mosaics of designs.
We study security functions which can serve to establish semantic security for privacy amplification in secret key generation. The security functions are functional forms of mosaics of combinatorial designs, more precisely, of group divisible designs and balanced incomplete block designs. Every member of a mosaic corresponds to a unique key value. We give explicit examples which have an optimal or nearly optimal tradeoff of seed size, given by the size of the block index set of the mosaics, versus key rate. We also derive bounds for the security performance in privacy amplification of security functions given by functional forms of mosaics of designs.
We study semantic security for classical-quantum channels. Our security functions are functional forms of mosaics of combinatorial designs. We extend methods in [25] from classical channels to classical-quantum channels to demonstrate that mosaics of designs ensure semantic security for classical-quantum channels, and are also capacity achieving coding schemes. An advantage of these modular wiretap codes is that we provide explicit code constructions that can be implemented in practice for every channel, given an arbitrary public code.
Secure communication ensures the integrity and confidentiality of communication between connected devices. An information-theoretic approach to secure communication gives the strongest confidentiality guarantee by assuming that the attacker has unlimited computing power. The earliest formal model and definition of information-theoretic secure communication is by Shannon, who employed a secret key shared between communicating parties to provide confidentiality. An alternative elegant information-theoretic approach to secure communication views the natural characteristics of the environment (i.e., channel’s noise) as a resource to build security functionalities. This approach was first proposed by Wyner, and the corresponding secure communication model is called the wiretap channel model. These two approaches introduce two primary resources for providing information-theoretic secure communication: the shared secret key and physical properties of the communication medium. In this thesis, we study how to employ the above two resources for secure message transmission. We study this by using channel’s noise in the wiretap channel model. In this model, a sender is connected to the receiver and the adversary through two noisy channels. We propose a new wiretap encoding scheme with strong secrecy that provides perfect secrecy and reliability, asymptotically. The construction treats the noise in the adversary’s channel as a source of randomness that is extracted and used to hide the message from the adversary. We realize the wiretap channel model using cooperative jamming to evaluate the performance of wiretap codes in practice. We consider a model called keyed wiretap channel that unifies Wyner’s model with Shannon’s model of perfect secrecy for information systems, and propose a keyed encoding schemes with strong secrecy and other properties that are attractive in practice. We also study two-party information-theoretic secret key agreement when the two parties have access to samples of a common source of randomness and use a single message transmission to arrive at a shared random key. We propose a secret key agreement protocol in this setting, prove its security, and show its superior performance compared to other known protocols with the same properties. Finally, we propose an information-theoretic secret key agreement over a virtual wiretap channel created by cooperative jamming.
Physical layer security can ensure secure communication over noisy channels in the presence of an eavesdropper with unlimited computational power. We adopt an information theoretic variant of semantic-security (SS) (a cryptographic gold standard), as our secrecy metric and study the open problem of the type II wiretap channel (WTC II) with a noisy main channel is, whose secrecy-capacity is unknown even under looser metrics than SS. Herein the secrecy-capacity is derived and shown to be equal to its SS capacity. In this setting, the legitimate users communicate via a discrete-memory less (DM) channel in the presence of an eavesdropper that has perfect access to a subset of its choosing of the transmitted symbols, constrained to a fixed fraction of the block length. The secrecy criterion is achieved simultaneously for all possible eavesdropper subset choices. On top of that, SS requires negligible mutual information between the message and the eavesdropper's observations even when maximized over all message distributions. A key tool for the achievability proof is a novel and stronger version of Wyner's soft covering lemma. Specifically, the lemma shows that a random codebook achieves the soft-covering phenomenon with high probability. The probability of failure is doubly-exponentially small in the block length. Since the combined number of messages and subsets grows only exponentially with the block length, SS for the WTC II is established by using the union bound and invoking the stronger soft-covering lemma. The direct proof shows that rates up to the weak-secrecy capacity of the classic WTC with a DM erasure channel (EC) to the eavesdropper are achievable. The converse follows by establishing the capacity of this DM wiretap EC as an upper bound for the WTC II. From a broader perspective, the stronger soft-covering lemma constitutes a tool for showing the existence of codebooks that satisfy exponentially many constraints, a beneficial ability for many other applications in information theoretic security.
In this chapter, we discuss the construction of practical codes for secrecy. The design of codes for the wiretap channel turns out to be surprisingly difficult, and this area of information-theoretic security is still largely in its infancy. To some extent, the major obstacles in the road to secrecy capacity are similar to those that lay in the path to channel capacity: the random-coding arguments used to establish the secrecy capacity do not provide explicit code constructions. However, the design of wiretap codes is further impaired by the absence of a simple metric, such as a bit error rate, which could be evaluated numerically. Unlike codes designed for reliable communication, whose performance is eventually assessed by plotting a bit-error-rate curve, we cannot simulate an eavesdropper with unlimited computational power; hence, wiretap codes must possess enough structure to be provably secure. For certain channels, such as binary erasure wiretap channels, the information-theoretic secrecy constraint can be recast in terms of an algebraic property for a code-generator matrix. Most of the chapter focuses on such cases since this algebraic view of secrecy simplifies the analysis considerably. As seen in Chapter 4, the design of secret-key distillation strategies is a somewhat easier problem insofar as reliability and security can be handled separately by means of information reconciliation and privacy amplification. Essentially, the construction of coding schemes for key agreement reduces to the design of Slepian–Wolf-like codes for information reconciliation, which can be done efficiently with low-density parity-check (LDPC) codes or turbo-codes.
Wyner [96] proved that unconditionally secure communication over noisy channels is possible if the wiretapping channel is noisier than the main channel. The work has developed the following belief: Physical-channel characteristics are great resources to build security functionalities in the information-theoretic framework. We follow this belief and investigate the three problems of secret key establishment, manipulation detection, and distance bounding verification over physical-layer channels. We investigate secret key establishment (SKE) between Alice and Bob when they are connected through a pair of noisy wiretap channels with leakage to Eve. Our results show the possibility of SKE even in cases where the main channels are noisier than Eve's channels. We then notice two implicit assumptions of this work: (i) local randomness is freely available, and (ii) the wiretap channels are independent. We remove Assumption (i) by considering no local randomness for the parties. The results appreciate the role of noise as a single resource for randomness derivation and key generation in this setting. Regarding the second assumption, we consider the general two-way wiretap channel, where simultaneous data transmission can help achieve higher key rates. We show under what condition our security requirements can be strengthened without sacrificing the SK capacity. We consider manipulation detection against physical-layer adversaries noticing their limitations. We define leakage-resilient algebraic manipulation detection (LR-AMD) codes and prove optimal LR-AMD code constructions in general and special leakage scenarios. We show two applications of these codes: (i) robust nonperfect secret sharing and (ii) manipulation detection over wiretap channels. We then discuss how these codes can be composed with other primitives to guarantee bitwise manipulation detection and SKE against active adversaries over binary wiretap channels. Distance bounding verification (DBV) allows a verifier to check an upper bound on a claimed distance from a prover. We study DBV over physical channels with security against distance fraud (DFA), ma a fraud (MFA) and terrorist fraud (TFA) attacks. We show efficient DFA- and MFA-secure protocols only using physical channel properties. We further prove that TFA-security becomes feasible if the parties' communication is limited by the bounded retrieval model (BRM).