Mosaics of combinatorial designs for information-theoretic security

A channel \(W:{\mathcal {X}}\rightarrow {\mathcal {Z}}\) is a stochastic matrix W with rows indexed by the finite input alphabet \({\mathcal {X}}\) and columns indexed by the finite output alphabet \({\mathcal {Z}}\). The (x, z) entry is nonnegative and denoted by \(w(z\vert x)\). The sum of the entries of every row sums to 1, hence it defines a probability distribution on \({\mathcal {Z}}\). For the purpose of this paper, a wiretap channel is determined by a single channel W. The interpretation is that a sender, Alice, wants to transmit a confidential message to a receiver, Bob, through a channel which accepts inputs from \({\mathcal {X}}\) and whose output is identical to the input, or whose error probability is as small as desired. An eavesdropper, Eve, obtains a noisy version of the input symbol \(x\in {\mathcal {X}}\) through the channel W, in other words, she observes a random variable distributed according to \(w(\,\cdot \,\vert x)\). The task now is to devise a security code for the transmission of confidential messages which does not decrease the reliability of the channel to Bob, and which at the same time ensures that Eve learns nothing about the transmitted messages. In fact, we aim for semantic security, by which we loosely mean that the security code should guarantee security no matter how the message is distributed on the message set. Two possible rigorous definitions of this concept will be given below. They guarantee unconditional security, which means that no assumptions are made on Eve’s computing power.

Another problem from information-theoretic security is privacy amplification. Here, Alice and Bob share a random variable X living on a finite set \({\mathcal {X}}\). Eve, the adversary, has access to a discrete random variable Z correlated with X. The task is to apply a privacy amplification function to X such that the resulting random variable A (the secret key shared by Alice and Bob) is distributed approximately uniformly and such that Eve has no information about A. Again, the goal is to achieve semantic security. Although all distributions are fixed in this setting, it makes sense to require semantic security. For instance, it guarantees that even if Eve has the a priori knowledge that the key generated in the privacy amplification process has one of only two possible values, she is unable to tell which of these two is the one actually chosen. This property is sometimes called distinguishing security, but it is well-known that it is equivalent to unconditional semantic security [4].

Practical scenarios will not in general translate directly into one of the two problems described above. In the wiretap scenario, the physical channel from Alice to Bob will generally be noisy as well, and an error-correcting code needs to be applied first to make the error probability on this channel as small as possible. In this case, the input alphabet \({\mathcal {X}}\) actually is the message set of the error-correcting code. Similarly, in secret key generation, two remote parties will not in general share a random variable X from the outset. In order to establish such a random variable, an information reconciliation protocol has to be performed using communication over a public channel. Eve obtains at least part of her correlated information Z about X as she observes the public messages exchanged during information reconciliation.

It follows that a security code or a privacy amplification function will generally be just one component of a modular scheme which as a whole ensures both “reliability” (viz. error-correction or information reconciliation) and semantic security as well as, in the privacy amplification setting, approximately uniform key distribution.

The two problems above are key techniques for the generation of information-theoretic security in communication and data storage systems. They can be building blocks for embedded security and security-by-design of such systems. An important feature of information-theoretic security is that it provides provable security even against attacks performed by a quantum computer. For this reason, the techniques developed here are of great importance for the development of future 6G mobile communication systems [16]. A first practical implementation is presented in [31].

Both for the wiretap and the privacy amplification scenario, we will assume that Alice and Bob can share an additional resource, a publicly known seed s chosen uniformly at random from the finite seed set \({\mathcal {S}}\). Then the basis both for security codes and privacy amplification functions are onto functions \(f:{\mathcal {X}}\times {\mathcal {S}}\rightarrow {\mathcal {A}}\), where \({\mathcal {A}}\) is a finite set. We will call such a function a security function. In the wiretap scenario, \({\mathcal {A}}\) will be the set of confidential messages; in privacy amplification, it represents the range of possible key values. In fact, in privacy amplification, f is nothing else than the privacy amplification function, i.e., given a seed \(s\in {\mathcal {S}}\) and a realization \(x\in {\mathcal {X}}\) of the random variable X shared by Alice and Bob, the secret key is chosen to be f(x, s) (see Fig. 1). For the wiretap channel, if Alice wants to send a confidential message \(\alpha \in {\mathcal {A}}\) and shares the seed s with Bob, she selects an element x from the preimage \(f_s^{-1}(\alpha )=\{x:f(x,s)=\alpha \}\) uniformly at random and transmits x. We call this process of selecting x the randomized inverse of f. By assumption, with high probability, or even with certainty, Bob receives the x that was sent and decodes it into the original confidential message \(\alpha =f(x,s)\), so the reliability of message transmission is preserved (see Fig. 2).

The color rate of a security function \(f:{\mathcal {X}}\times {\mathcal {S}}\rightarrow {\mathcal {A}}\), both in the wiretap and in the privacy amplification context, is given by¹(the name will be justified in the context of mosaics, see below). As f is onto, this is a number between 0 and 1 which indicates the cost of establishing security as well as, in the privacy amplification scenario, approximately uniform key distribution. This is not a parameter to be optimized. Instead, given a required security level, the channel W in the former and the joint probability \(P_{XZ}\) in the latter situation determine a maximal possible color rate. The question is which f achieve or come close to this rate.

In the wiretap case, a common assumption is that Alice generates the seed, but then she has to use the unsecured channel to transmit it to Bob. This diminishes the overall communication rate significantly. The block rateindicates how often the unsecured channel needs to be used for the transmission of the seed. It has been shown that in some scenarios the seed can be reused in order to make the loss of overall communication rate negligibly small asymptotically. Nevertheless, it is important to make the seed set \({\mathcal {S}}\) as small as possible.

The use of a seed is not as problematic in the privacy amplification setting, since it is commonly assumed that there exists a public channel between Alice and Bob. For the purpose of seed sharing, it is sufficient that the public channel goes in one direction only. Usually, one still wants to keep the communication overhead on this public channel small, and this overhead can again be measured by the block rate.

Finally, we would like security codes and privacy amplification functions to be efficiently computable. For an underlying security function, this translates to the efficiency of computing f(x, s) and the randomized inverse \(f_s^{-1}(\alpha )\). A precise definition of what we mean by efficiency will be given below.

Semantic security can be seen as a per-message type of security. It means that the probability distribution of Eve’s observations conditional on any message or key value should be indistinguishable from an arbitrary fixed distribution on Eve’s observation space which is independent of the message or key distribution. This suggests to construct security functions \(f:{\mathcal {X}}\times {\mathcal {S}}\rightarrow {\mathcal {A}}\) whose preimages \(f^{-1}(\alpha )\) for every \(\alpha \in {\mathcal {A}}\) have a structure suitable for establishing this indistinguishability.

Our goal in this paper is to systematically study security functions where every preimage \(f^{-1}(\alpha )\) is the incidence relation of a balanced incomplete block design (BIBD) or a group divisible design (GDD) with point set \({\mathcal {X}}\) and block index set \({\mathcal {S}}\). Such a function defines a mosaic of designs \((D_\alpha )_{\alpha \in {\mathcal {A}}}\), which is a family of designs on a common point set and a common block index set satisfying that every pair \((x,s)\in {\mathcal {X}}\times {\mathcal {S}}\) is incident in a unique \(D_\alpha \). The security function corresponding to such a mosaic will be its functional form. The precise definitions will be given in Sect. 2.

Two aspects guide us in the construction of mosaics of designs: the trade-off of the color rate and the block rate, and the computational complexity of the functional form and its randomized inverse. We investigate the optimal trade-off of the color rate \(\varrho \) vs. the block rate for functional forms of mosaics of BIBDs and GDDs. For mosaics of BIBDs with small color rate, the block rate can at best be equal to 1. In all other cases, the minimal block rate is approximately equal to \(2\varrho \). In particular, if \(\varrho <1/2\) and the mosaic consists of GDDs, then a block rate smaller than 1 is possible.

We construct families of examples which are close to optimal, or even optimal, in terms of this trade-off. Their color rates are distributed over the complete interval between 0 and 1, densely in all cases except for BIBDs of small color rate. Both for mosaics of BIBDs and GDDs, we need two different families in order to obtain sufficiently variable color rates \(\varrho \). In both cases, at \(\varrho \approx 1/2\), the type of designs which is (close to) optimal in terms of this trade-off changes.

To the best of our knowledge, we are the first to explicitly study semantic security for privacy amplification. In both scenarios, we measure the amount of semantic security offered by the functional form of a mosaic of BIBDs or GDDs using two alternative security metrics, one of them based on total variation distance, the other on Kullback-Leibler divergence. The upper bounds on these metrics rely on the local properties of the functional form, i.e., on the properties of BIBDs and GDDs. The wiretap channel and the distribution of the random variables X and Z only appear in these bounds through at most two Rényi entropies or divergences, which gives the bounds some robustness with respect to the knowledge about the channel or the random variables.

We evaluate the security bounds in the most frequently studied scenarios of memoryless discrete or Gaussian wiretap channels and of privacy amplification for secret-key generation from discrete memoryless correlated sources. Unfortunately, block rate optimal mosaics of GDDs in the range where \(\varrho \) is small only achieve a suboptimal security level in general. This is not due to our construction, but holds in general. Hence a block rate of at least 1 is necessary to achieve asymptotically perfect semantic security at the maximal message or key rate with mosaics of BIBDs or GDDs. For the other block rate optimal constructions, the bounds are asymptotically optimal in the benchmark scenarios. Additionally, in the case of privacy amplification, the regularity of BIBDs and GDDs immediately implies the perfect uniform distribution of the key generated by the functional form of a mosaic of designs.

All the mosaics we construct are explicit, by which we mean the efficient computability of the functional form and its inverse in the usual setting of asymptotic complexity. The examples are derived from well-known designs based on finite fields, so in some cases the explicitness is obvious. There is one case where some work is required to show explicitness.

Mosaics of combinatorial designs were introduced by Gnilke, Greferath and Pavčević [17]. Our method of constructing mosaics from resolvable designs or duals thereof is essentially due to them. The application of mosaics to construct functions with special desired properties is new, in particular, the analysis of color and block rates and of efficient computability of such functions. Mosaics generalize more specialized concepts like the tiling of a group with difference sets due to Ćustić, Krčadinac and Zhou [14]. A predecessor of what now is called mosaics was presented in [18] by Greferath and Therkelsen. General background on combinatorial designs can be found in the reference work of Beth, Jungnickel and Lenz [8].

The idea of separating privacy amplification from information reconciliation goes back to Bennett, Brassard and Robert [6] and Bennett, Brassard, Crépeau and Maurer [7]. Hayashi [21] extended the idea to the construction of security codes for the wiretap channel, where error correction is separated from the establishment of security. Like in [6, 7] and [21], the weaker strong secrecy criterion has been widely applied in information-theoretic security, where Eve’s a priori knowledge is restricted to the true message or key distribution.

Semantic security ensures security no matter what the key or message distribution might be. Originating in complexity-based cryptography, it was adapted for (unconditional) information-theoretic security by Bellare, Tessaro and Vardy [4] (the shorter, published version of which is [3]). To the authors’ knowledge, semantic security has only been considered for wiretap channels so far. In [20], Hayashi implicitly describes a technique for achieving semantic security for the quantum BB84 key distribution protocol.

[6, 7] and [21] used universal hash functions as security functions. Alternative choices in the privacy amplification scenario with strong secrecy are \(\varepsilon \)-almost dual universal hash functions (Hayashi [22]) and strong randomness extractors (Maurer and Wolf [25]). None of these choices guarantees perfect uniform distribution of the key. However, the seed required by randomness extractors can be very short. Seedless extractors have been used by Cheraghchi, Didier and Shokrollahi [11] to ensure strong secrecy for the “wiretap channel II”, where the eavesdropper may observe a fraction of his choosing of the transmitted codeword.

When applied as security functions in the wiretap scenario, it seems that the global property defining universal hash functions in general is not enough to ensure semantic security. Even with additional regularity properties (cf. [5, 32]), semantic security can only be shown for sufficiently symmetric channels. Usually, only strong secrecy is achievable.

Upper bounds on the semantic security metric for the wiretap channel which are comparable to ours were given by Hayashi and Matsumoto [23, Lemma 21] and the authors [34], using security functions of a different type. The security functions of the former paper are defined in terms of group homomorphisms together with a regularity condition. The single efficiently computable example given in [23, Remark 16] exhibits a block rate \(\approx 2\), which is worse than for mosaics of designs with an optimal trade-off of block rate vs. color rate. The security functions of [34] are induced by decompositions of complete biregular bipartite graphs into nearly Ramanujan graphs. A nonconstructive example of such a decomposition into Ramanujan graphs is given with a block rate of 1 independent of the color rate.

In Sect. 2, we define and analyze mosaics of BIBDs and GDDs. In Sect. 3, we define how we measure semantic security and give the bounds on the security metrics obtained from functional forms of mosaics of designs. These bounds are proved in Sect. 4. In Sect. 5, we prove the explicitness of one of the examples of Sect. 2 for which this is not immediately obvious.

Let \({\mathcal {X}}\) and \({\mathcal {S}}\) be finite sets. An incidence structure \(D=({\mathcal {X}},{\mathcal {S}},I)\) on \(({\mathcal {X}},{\mathcal {S}})\) is determined by the incidence relation I on \({\mathcal {X}}\times {\mathcal {S}}\). An incidence structure \(({\mathcal {X}},{\mathcal {S}},I)\) is called empty if \(I=\emptyset \). If \(x\,I\,s\), then x and s are called incident. The incidence matrix of an incidence structure \(D=({\mathcal {X}},{\mathcal {S}},I)\) is the 01-matrix N with rows indexed by \({\mathcal {X}}\) and columns indexed by \({\mathcal {S}}\) such that \(N(x,s)=1\) if and only if x and s are incident in D.

A mosaic of incidence structures on \(({\mathcal {X}},{\mathcal {S}})\) is a family \(M=(D_\alpha )_{\alpha \in {\mathcal {A}}}\) of nonempty incidence structures on \(({\mathcal {X}},{\mathcal {S}})\) such that for every pair (x, s) there exists a unique incidence structure \(D_\alpha \) in which x and s are incident. We call \({\mathcal {A}}\) the color set of M. Every \(D_\alpha \) is called a member of M. If \(N_\alpha \) is the incidence matrix of \(D_\alpha \), then \(\sum _{\alpha \in {\mathcal {A}}}N_\alpha =J\), the all-ones matrix of appropriate size.

Any function \(f:{\mathcal {X}}\times {\mathcal {S}}\rightarrow {\mathcal {A}}\) induces a mosaic \((D_\alpha )_{\alpha \in {\mathcal {A}}}\) of incidence structures, where x and s are incident in \(D_\alpha \) if and only if \(f(x,s)=\alpha \). We say that f is the functional form of this mosaic. Clearly, every mosaic \((D_\alpha )_{\alpha \in {\mathcal {A}}}\) on \(({\mathcal {X}},{\mathcal {S}})\) has a functional form \(f:{\mathcal {X}}\times {\mathcal {S}}\rightarrow {\mathcal {A}}\).

We consider the case where every \(D_\alpha \) is a combinatorial design. In the context of designs, we will call \({\mathcal {X}}\) the point set and \({\mathcal {S}}\) the block index set. We set \(v=|{\mathcal {X}}|\) and \(b=|{\mathcal {S}}|\). A (v, k, r) tactical configuration on \(({\mathcal {X}},{\mathcal {S}})\) is an incidence structure where every point x is incident with precisely r block indices and every block index s is incident with precisely k points. It holds thatA \((v,k,\lambda )\) balanced incomplete block design (BIBD) on \(({\mathcal {X}},{\mathcal {S}})\) is an incidence structure on \(({\mathcal {X}},{\mathcal {S}})\) such that every s is incident with precisely k points from \({\mathcal {X}}\) and such that any two distinct points from \({\mathcal {X}}\) are incident with precisely \(\lambda \ge 1\) common block indices. Every \((v,k,\lambda )\) BIBD is a (v, k, r) tactical configuration, whereThe key equality when we want to establish security using a security function which is the functional form of a mosaic of BIBDs is that the incidence matrix N of a \((v,k,\lambda )\) BIBD satisfies(here I is the identity matrix of appropriate dimensions).

The second type of designs we consider are group divisible designs (GDDs). A \((u,m,k,\lambda _1,\lambda _2)\) GDD is based on a partition of \({\mathcal {X}}\) into m point classes of size u each, so \(v=um\). Every block index is incident with precisely k points, and two points are incident with \(\lambda _1\ge 0\) common block indices if they are contained in the same point class and with \(\lambda _2\ge 1\) block indices otherwise. A \((u,m,k,\lambda _1,\lambda _2)\) GDD is a (v, k, r) tactical configuration for r satisfyingAn equality similar to (2.3) holds for the incidence matrix N of a GDD. Let C be the 01-matrix with rows and columns indexed by \({\mathcal {X}}\) which has a 1 in the \((x,x')\) entry if and only if x and \(x'\) are contained in the same point class. With a suitable ordering of the elements of \({\mathcal {X}}\), this is a block diagonal matrix with m all-ones matrices of size u each on the diagonal. ThenFor a BIBD or GDD \(({\mathcal {X}},{\mathcal {S}},I)\), the sets of the form \(\{x:x\,I\,s\}\), where \(s\in {\mathcal {S}}\), are usually called blocks and the set \({\mathcal {S}}\) is identified with the multiset of blocks of the design. Occasionally, we will also speak of blocks and call the parameter k the block size. However, we will not identify \({\mathcal {S}}\) with a block multiset since we operate with multiple designs simultaneously. Hence the more cumbersome term “block index set”.

All mosaics in this paper will consist of tactical configurations with the same parameters (v, k, r). Given a mosaic \((D_\alpha )_{\alpha \in {\mathcal {A}}}\), we will use the letter a to indicate the cardinality of its color set \({\mathcal {A}}\). If \((D_\alpha )_{\alpha \in {\mathcal {A}}}\) is a mosaic of (v, k, r) tactical configurations, thenIn fact, the examples of mosaics constructed in the present paper will exclusively consist of BIBDs only or of GDDs only. BIBDs and GDDs together allow us to construct security functions with a wide range of color rates between 0 and 1. For a mosaic of BIBDs with constant block size k, note that \(\lambda \) also has to be constant due to (2.1) and (2.2).

If \(D=({\mathcal {X}},{\mathcal {S}},I)\) is an incidence structure, then its dual is the incidence structure \(D^T=({\mathcal {S}},{\mathcal {X}},I^T)\) where \(s\,I^T\,x\) if and only if \(x\,I\,s\). Obviously, the incidence matrix of \(D^T\) is the transpose of the incidence matrix of D. If \((D_\alpha )_{\alpha \in {\mathcal {A}}}\) is a mosaic of designs, then so is \((D_\alpha ^T)_{\alpha \in {\mathcal {A}}}\).

A (v, k, r) tactical decomposition \(({\mathcal {X}},{\mathcal {S}},I)\) is called resolvable if the block index set \({\mathcal {S}}\) can be partitioned into subsets \({\mathcal {S}}_1,\ldots ,{\mathcal {S}}_r\) such that for every \(j\in \{1,\ldots ,r\}\), every \(x\in {\mathcal {X}}\) is incident with a unique \(s\in {\mathcal {S}}_j\). (It is clear that such a partition necessarily has to have precisely r elements.) Every \({\mathcal {S}}_j\) is called a parallel class and contains v/k block indices, in particular, k divides v.

The sum of a mosaic is the incidence structure on \(({\mathcal {X}},a{\mathcal {S}})\), where \(a{\mathcal {S}}\) is the disjoint union of a copies of \({\mathcal {S}}\), and where a point x is incident with the \(\alpha \)-th copy of \(s\in {\mathcal {S}}\) if x and s are incident in \(D_\alpha \). Note that the sum of a mosaic of tactical configurations is resolvable.

Two incidence structures \(({\mathcal {X}},{\mathcal {S}},I)\) and \(({\mathcal {X}}',{\mathcal {S}}',I')\) are called isomorphic if there exist bijective mappings \(\varPhi _{{\mathcal {X}}}:{\mathcal {X}}\rightarrow {\mathcal {X}}'\) and \(\varPhi _{{\mathcal {S}}}:{\mathcal {S}}\rightarrow {\mathcal {S}}'\) such that \(x\,I\,s\) if and only if \(\varPhi _{{\mathcal {X}}}(x)\,I'\,\varPhi _{{\mathcal {S}}}(s)\). We also define that two mosaics \((D_\alpha )_{\alpha \in {\mathcal {A}}}\) on \(({\mathcal {X}},{\mathcal {S}})\) and \((D'_{\alpha '})_{\alpha '\in {\mathcal {A}}'}\) on \(({\mathcal {X}}',{\mathcal {S}}')\) are isomorphic if there exist bijective mappings \(\varPhi _{{\mathcal {X}}}:{\mathcal {X}}\rightarrow {\mathcal {X}}'\) and \(\varPhi _{{\mathcal {S}}}:{\mathcal {S}}\rightarrow {\mathcal {S}}'\) and \(\varPhi _{{\mathcal {A}}}:{\mathcal {A}}\rightarrow {\mathcal {A}}'\) such that \(x\in {\mathcal {X}}\) and \(s\in {\mathcal {S}}\) are incident in \(D_\alpha \) for \(\alpha \in {\mathcal {A}}\) if and only if \(\varPhi _{{\mathcal {X}}}(x)\) and \(\varPhi _{{\mathcal {S}}}(s)\) are incident in \(D_{\varPhi _{{\mathcal {A}}}(\alpha )}\).

A BIBD is called affine or affine resolvable if it is resolvable and if there exists a number \(\mu >0\) such that any two distinct non-parallel blocks have precisely \(\mu \) points in common. An affine plane is an affine BIBD with \(\mu =1\) and block size at least 2. Affine BIBDs have the property that their number of blocks is minimal among all resolvable BIBDs with the same number of points and parallel classes. This is a consequence of Bose’s inequality, which states thatfor resolvable BIBDs [8, Corollary 8.6], and that equality holds if and only if the BIBD is affine.

Here we give the classical examples of affine designs, on which our constructions below will be based. This is no restriction, since all known affine BIBDs have the same parameters as the affine-geometric ones below or are Hadamard designs [8, p. 128]. We ignore the latter since they are limited to \(v/k=a=2\), which only allows a very small color rate which vanishes asymptotically as v increases.

Let q be a prime power and \(t\ge 2\). The \((q^t,q^{t-1},q^{t-2})\) BIBD \(AG_{t-1}(t,q)\) has as block set the vector space \({\mathbb {F}}_q^t\), the blocks are given by the hyperplanes of this vector space, i.e., all cosets of all \((t-1)\)-dimensional subspaces, and the incidence relation is \(\in \). These designs are affine resolvable, the parallel classes are given by the sets of nonintersecting hyperplanes. In the case \(t=2\), one obtains the affine plane AG(2, q), where the hyperplanes are called lines.

We characterize block rate optimality for mosaics of BIBDs and GDDs.

We note that \(\varrho _0(v,k)\) quickly approaches 1/2 from below as v increases.

We also consider the block rate for GDDs. This is connected to some subclasses of GDDs. First, we recall the classification of GDDs due to Bose and Connor [10]. A GDD is called Every GDD falls under exactly one of these categories.

An important subclass of the semi-regular GDDs are the transversal designs, which satisfy that every block intersects every point class in precisely one point. In this case \(m=k\) and \(\lambda _1=0\). We call a transversal design with these parameters a \((u,k,\lambda )\) TD, where \(\lambda =\lambda _2\). Hanani [19] has shown that a \((u,k,\lambda )\) TD necessarily satisfies

Unfortunately, the block rate of any mosaic one of whose members is a semi-regular GDD cannot be much smaller than 1. This implies that the minimal possible color rate of a block rate optimal GDD quickly approaches 1/2 from below as the number of colors increases.

We have seen that we cannot come close to block rate optimality for rates well below 1/2 using mosaics which contain at least one semi-regular GDD. The same holds for mosaics which have at least one regular GDD as a member, since regular GDDs satisfy \(b\ge v\) by [10], soFor color rates smaller than those in Corollary 2.4, the solution is to use singular GDDs. (However, we will see that singular block rate optimal GDDs give suboptimal bounds for semantic security for sufficiently large point set.) Bose and Connor show in [10] that every singular GDD is obtained by the multiplication of the points of a BIBD. We apply the same construction in order to obtain a mosaic \(M=(D_\alpha )_{\alpha \in {\mathcal {A}}}\) of singular GDDs from a mosaic \(M^*=(D_\alpha ^*)_{\alpha \in {\mathcal {A}}}\) of \((v^*,k^*,\lambda ^*)\) BIBDs on \(({\mathcal {X}}^*,{\mathcal {S}}^*)\). For an arbitrary positive integer u, replace each point \(x^*\in {\mathcal {X}}^*\) by a class of u copies of \(x^*\). This gives the point set \({\mathcal {X}}\) of M. The block index set does not change, we set \({\mathcal {S}}={\mathcal {S}}^*\). A point x and a block index s are defined to be incident in \(D_\alpha \) if x is a copy of an \(x^*\) which is incident with s in \(D_\alpha ^*\). Every \(D_\alpha \) has parametersNote that all members of M have the same point class partition. We call M the u-fold point multiple of \(M^*\).

Conversely, one shows in the same way as in [10] that every mosaic of singular GDDs with the same parameters and the same point class partition is the u-fold point multiple of a mosaic of BIBDs.

We see that if \(M^*\) is close to block rate optimality and \(\varrho ^*\ge \varrho _0(v^*,k^*)\), then M is close to block rate optimality as well. The color rates can be chosen arbitrarily small by choosing u accordingly. A block rate optimal mosaic \(M^*\) of BIBDs with color rate larger than 1/2 will be constructed in Sect. 2.6.

With a view towards applications, we would like to be able to find examples of mosaics of designs whose functional form and randomized inverse are efficiently computable (in the Turing model of computation). By efficiency, we mean that it must be possible to do the computations in time polylogarithmic in v and b. This is compatible with the usual requirements in coding theory, where encoding and decoding must be done in time polynomial in the blocklength. For this asymptotic definition to make sense, we will implicitly assume that the mosaic is part of an infinite family of mosaics where each color rate can be attained infinitely often and where v is unbounded. This will be satisfied by all examples we give below.

Since \({\mathcal {X}}\) and \({\mathcal {S}}\) do not necessarily have a natural representation as a set of consecutive bit sequences, we define efficiency in terms of the functional form of an isomorphic mosaic defined on sets of integers. The choice of integers instead of bit strings allows us to ignore questions arising when the cardinality of a set is not a power of 2.

For any positive integer n, we write \([n]=\{1,\ldots ,n\}\). We call the mosaic \(M=(D_\alpha )_{\alpha \in {\mathcal {A}}}\) explicit if there exists a mosaic \({\tilde{M}}=({\tilde{D}}_j)_{j\in [a]}\) with point set [v] and block index set [b] which is isomorphic to M and whose functional form \({\tilde{f}}:[v]\times [b]\rightarrow [a]\) satisfies

If, in the wiretap channel case, Alice chooses the seed, which is the most likely scenario, then the order of the choice of seed s and channel input x can be reversed. So far, we have assumed that s is chosen first and x is chosen from \(f_s^{-1}(\alpha )\). Due to (2.1), it is equivalent to first choose x uniformly at random from \({\mathcal {X}}\) and then to choose s from \(f_x^{-1}(\alpha )=\{s\in {\mathcal {S}}:f(x,s)=\alpha \}\). We will see in one of the mosaics which we are going to construct that this can reduce the cost of computation.

However, reversing the order of choosing s and x has a drawback. We already mentioned above that if the channel from Alice to Bob is used to first transmit the seed and then the confidential message, this incurs a loss of total communication rate, and that it is possible to make up for this by reusing the seed. Since s depends on x if the latter is chosen first, seed reuse is impossible in this case.

All functions constructed in this paper will be based on finite-field arithmetic. For real implementations, not all finite fields are equally suitable. However, in principle, the complexities are comparable. If \(q=p^t\) for a prime p, then \({\mathbb {F}}_q\) can be regarded as a vector space over \({\mathbb {F}}_p\). If \({\mathbb {F}}_q\) is represented in a polynomial basis, i.e., a basis of the form \(\{1,\vartheta ,\vartheta ^2,\ldots ,\vartheta ^{t-1}\}\), then addition and subtraction in the field \({\mathbb {F}}_q\) can be done in time \(O(\log q)\). For multiplication and division, \(O((\log q)^2)\) time is sufficient [26]. A polynomial basis exists for all prime powers q [24].

We next present a method from which all examples of mosaics below will be constructed. A key ingredient for its construction are quasigroups. A quasigroup on the finite set \({\mathcal {A}}\) is an array L with entries from \({\mathcal {A}}\) and rows and columns indexed by \({\mathcal {A}}\) and which satisfies Every finite group is a quasigroup. If one labels the rows and columns of a quasigroup by a set which is not necessarily the same as \({\mathcal {A}}\), one obtains a Latin square. Using quasigroups instead of Latin squares is more convenient in our setting.

A quasigroup L on \({\mathcal {A}}\) and a quasigroup \({\tilde{L}}\) on \(\tilde{{\mathcal {A}}}\) are called isomorphic if there exists a bijective mapping \(\varPhi :{\mathcal {A}}\rightarrow \tilde{{\mathcal {A}}}\) such that \({\tilde{L}}(\varPhi (\alpha ),\varPhi (\beta ))=\varPhi (\gamma )\) for all \(\alpha ,\beta ,\gamma \in {\mathcal {A}}\).

The following theorem was already shown in [17] for the case of resolvable BIBDs, using Latin squares instead of quasigroups (which combinatorially amounts to the same thing). It is based on the idea that it should be possible to obtain a mosaic if one starts with a resolvable incidence structure, since the sum of a mosaic is resolvable.

The explicitness of a mosaic constructed as in Theorem 2.7 follows from the explicitness of the involved design D and the quasigroup L. This is important in those cases where explicitness is not immediately clear from the functional form of the mosaic, like for the mosaics \({\mathcal {M}}^{(2)}\) of the next section.

We say that a quasigroup L on \({\mathcal {A}}\) is explicit if there exists an isomorphic quasigroup \({\tilde{L}}\) over [a] such that Let \(D=({\mathcal {X}},{\mathcal {S}},I)\) be a resolvable (v, k, r) tactical configuration with \({\mathcal {S}}={\mathcal {R}}\times {\mathcal {A}}\), where \({\mathcal {R}}\) is an index set for the parallel classes and \({\mathcal {A}}\) for the elements of each parallel class. We call D explicit if there exists an isomorphic resolvable tactical configuration \({\tilde{D}}=([v],[r]\times [a],{\tilde{I}})\) satisfying We call the dual \(D^T\) of D explicit if there exists a resolvable tactical configuration \({\tilde{D}}=([v],[r]\times [a],{\tilde{I}})\) isomorphic to D which satisfies (D1) and

We present four families of mosaics. Not all of these are block rate optimal, but those which are not are arbitrarily close to optimality for sufficiently large point sets. There is a family for each combination of the cases The sets of color rates will be dense except for the case of BIBDs with small color rates.

In all cases we will use Theorem 2.7. Thus in every case the key is to find a single resolvable design with the desired parameters.

BIBD and \(\varrho \le 1/2\): For this case we build our construction on the affine designs. Fix an integer \(t\ge 2\) and a prime power q and let \(v,k,\lambda \) etc. be the parameters of the BIBD \(AG_{t-1}(t,q)\). ThenHence the color rate of the mosaic \(M^{(1)}_{t,q}\) we obtain from \(AG_{t-1}(t,q)\) with the construction of Theorem 2.7 isWe have \(1/t>\varrho _0(v,k)\) only if \(t=2\). In this case, \(M^{(1)}_{t,q}\) is block rate optimal since \(\lambda =1\).

If \(t\ge 3\), then \(M^{(1)}_{t,q}\) could only be block rate optimal if it were square, which is not the case. However, since \(AG_{t-1}(t,q)\) is affine, it is a consequence of Bose’s inequality (2.6) that the block rate of \(M^{(1)}_{t,q}\) is minimal among those mosaics constructed from any of the known resolvable BIBDs with \(v=q^t\) and color rate 1/t. The block rate satisfiesThus for fixed color rate 1/t, one gets closer to block rate optimality by increasing q.

Every hyperplane of \(AG_{t-1}(t,q)\) can be represented by a unique pair \((h,\alpha )\), where \(\alpha \in {\mathbb {F}}_q\) and h is a nonzero element of \({\mathbb {F}}_q^t\) whose first nonzero component is normalized to 1. We denote the set of these h by \({\mathcal {R}}\). The hyperplane corresponding to \((h,\alpha )\) is the set of points x satisfying \(h\cdot x=\alpha \), where \(h\cdot x=\sum _ih_ix_i\). Different h give different parallel classes and different \(\alpha \) with a fixed h indicate different parallel hyperplanes in the parallel class corresponding to h.

The natural quasigroup to construct a mosaic from \(AG_{t-1}(t,q)\) is the additive group of \({\mathbb {F}}_q\). Then a point \(x\in {\mathbb {F}}_q^t\) and an element \((h,\beta )\) of the block index set are incident in \(D_\alpha \) if and only if x is incident with \((h,\alpha -\beta )\) in \(AG_{t-1}(t,q)\). The functional form \(f:{\mathbb {F}}_q^t\times ({\mathcal {R}}\times {\mathbb {F}}_q)\rightarrow {\mathbb {F}}_q\) of \(M^{(1)}_{t,q}\) is given byThis immediately shows that the familyis explicit.

BIBD and \(\varrho \ge 1/2\): Fix a positive integer \(t\ge 2\) and an integer \(\ell \) between 1 and t. For \(q=2^t\), let \(Q:{\mathbb {F}}_q^2\rightarrow {\mathbb {F}}_q\) be an irreducible quadratic form, i.e., a polynomial of the formwhich cannot be factored into linear forms. Such a quadratic form exists for all q. Choose an arbitrary subgroup H of order \(2^\ell \) of the additive group of \({\mathbb {F}}_q\) and consider the setIt was proved by Denniston [15] that \({\mathcal {X}}\) haselements and that every line of AG(2, q) has either \(2^\ell \) or no points in common with \({\mathcal {X}}\).

We will regard \({\mathcal {X}}\) as a subset of AG(2, q). It is not hard to see [8, Corollary VIII.5.21] that if we denote by \({\mathcal {S}}\) the set of nontrivial intersections of lines of AG(2, q) with \({\mathcal {X}}\), then \(D=({\mathcal {X}},{\mathcal {S}},\in )\) is a resolvable (v, k, 1) BIBD with \(k=2^\ell \). Since \(r=2^t+1\) by (2.2), the set of parallel classes of D is in one-to-one relation with the set of parallel classes of lines in AG(2, q). In fact, if \(\ell =t\), then \(D=AG(2,q)\).

Applying Theorem 2.7, one constructs a mosaic \(M^{(2)}_{t,\ell ,H}\) with the parametersSince \(\lambda =1\), the mosaic \(M^{(2)}_{t,\ell ,H}\) is block rate optimal and satisfiesFor every t and \(\ell \), it is possible to choose a subgroup \(H_{t,\ell }\) such that the resulting familyis explicit. Some work has to be done in order to show this, which we postpone to Sect. 5. Moreover, every number between 1/2 and 1 can be approximated arbitrarily closely by the color rates of elements of \({\mathcal {M}}^{(2)}\) for sufficiently large t and \(\ell \).

GDD and \(\varrho <1/2\): Fix a positive integer t and a nonnegative \(\ell \) between 0 and t. Denote the elements of the explicit family \({\mathcal {M}}^{(2)}\) constructed above by \(M^{(2)}_{t,\ell }\) (we omit the subgroups here in order to simplify notation). Choose an integer u and let \(M^{(3)}_{t,\ell ,u}\) be the u-fold point multiple of \(M^{(2)}_{t,\ell }\). Its parameters areBy Lemma 2.5, its color rate isand the ratio of the block rate and the color rate is given by (2.15). The color rate is smaller than 1/2 for sufficiently large u.

Denote the point set of \(M^{(2)}_{t,\ell }\) by \({\mathcal {X}}^*\) and its block index set by \({\mathcal {S}}^*\). Let \(f^*:{\mathcal {X}}^*\times {\mathcal {S}}^*\rightarrow {\mathcal {A}}^*\) be the functional form of \(M^{(2)}_{t,\ell }\). The point set of \(M^{(3)}_{t,\ell ,u}\) can be taken to be \({\mathcal {X}}={\mathcal {X}}^*\times [u]\), the block index set and the color set remain the same as for \(D^*\), so \({\mathcal {S}}={\mathcal {S}}^*\) and \({\mathcal {A}}={\mathcal {A}}^*\). The functional form \(f:{\mathcal {X}}\times {\mathcal {S}}\rightarrow {\mathcal {A}}\) of \(M^{(3)}_{t,\ell ,u}\) satisfiesfor \(x^*\in {\mathcal {X}}^*,i\in [u],s\in {\mathcal {S}}\) and \(\alpha \in {\mathcal {A}}\). The explicitness of the familyfollows from that of \({\mathcal {M}}^{(2)}\).

By the discussion in Sect. 2.3, mosaics of singular GDDs give the best approximation to block rate optimality among mosaics of GDDs with a small color rate if the point set is sufficiently large. The ratio of the block and the color rates is given by (2.15). All numbers between 0 and 1 can be approximated arbitrarily well by the color rates of suitable members of \({\mathcal {M}}^{(3)}\).

GDD and \(\varrho \ge 1/2\): If one deletes some of the parallel classes from the block set of AG(2, q), where q is a prime power, then one obtains the dual of a transversal design. Assume we keep \(k\ge 2\) of the parallel classes of AG(2, q). Call the resulting design \(D^T\) and set \(D=(D^T)^T\). The point set \({\mathcal {X}}\) of D consists of lines of AG(2, q) and the block index set \({\mathcal {S}}\) of D consists of all the points of AG(2, q). Two points \(x,x'\in {\mathcal {X}}\) are incident with a common block index s if and only if they intersect as lines in AG(2, q), and so parallel classes of \(D^T\) translate into point classes of D. If \(x,x'\) are not in the same point class of D, then in \(D^T\), their corresponding lines intersect in a unique point. In D, this means that two points from different point classes are incident with a unique block index, and so D is a (q, k, 1) TD.

Letting \({\mathcal {R}}\) denote the set of remaining parallel classes of lines, we construct from this transversal design a mosaic \(M^{(4)}_{k,q,{\mathcal {R}}}\) as in Theorem 2.7, using the natural additive group structure of \({\mathbb {F}}_q\) on every parallel class of AG(2, q). We obtain a mosaic withThus \(M^{(4)}_{k,q,{\mathcal {R}}}\) has color rateSince k ranges between 2 and \(q+1\), \(\varrho \) is a number betweenThe block rate is optimal by Lemma 2.2.

The point set \({\mathcal {X}}\) of \(M^{(4)}_{k,q,{\mathcal {R}}}\) has the structure of a Cartesian product, \({\mathcal {X}}={\mathcal {R}}\times {\mathbb {F}}_q\). For the discussion of the functional form of the mosaic, we assume that \(k\le q\) and that \({\mathcal {R}}\) is given by a subset of \({\mathbb {F}}_q\). Then \(x=(c,d)\in {\mathcal {X}}\) corresponds to the line \(\{(u,cu+d):u\in {\mathbb {F}}_q\}\) in AG(2, q). The case \(k=q+1\) can be treated analogously and corresponds to a mosaic whose members all are isomorphic to the dual of AG(2, q).

A point \(x=(c,d)\in {\mathcal {X}}\) and a block \(s=(s_1,s_2)\in {\mathcal {S}}={\mathbb {F}}_q^2\) are incident in D if \(cs_1+d=s_2\). They are incident in \(D_\alpha \) if \(cs_1+d-\alpha =s_2\), where \(\alpha \in {\mathbb {F}}_q\). ThusGiven \(\alpha \in {\mathbb {F}}_q\) and \(s=(s_1,s_2)\in {\mathbb {F}}_q^2\), one can find those \(x\in {\mathcal {X}}\) which are incident with s by taking any \(c\in {\mathcal {R}}\) and solving for \(d=\alpha -s_2+cs_1\). In this way, one obtains the randomized inverse of f. This can be done efficiently if \({\mathcal {R}}\) can be enumerated efficiently. Clearly, such an \({\mathcal {R}}={\mathcal {R}}_{k,q}\) exists for every k. This gives us an explicit familyAll numbers between 1/2 and 1 can be approximated arbitrarily well by the color rates of members of this family.

Discussion. All our examples are constructed using Theorem 2.7, hence all members of these designs are either themselves resolvable or duals of resolvable designs. We do not know whether mosaics of BIBDs or GDDs with constant block size exist which are not resolvable or dually resolvable. Such a construction would be particularly relevant for cases where mosaics of resolvable designs cannot be block rate optimal. For instance, a block rate optimal mosaic of BIBDs with color rate smaller than 1/2 must be square, and consequently cannot be resolvable.

It would also be desirable to construct a family of mosaics of BIBDs which is close to block rate optimality and whose color rates are dense in the interval between 0 and 1/2.

The degree of semantic security offered by a security function when applied to a wiretap channel or in privacy amplification can be measured using various distances, divergences and entropies of probability measures.

Let P, Q be probability distributions on a finite set \({\mathcal {Z}}\). The total variation distance of P and Q isThis is a metric on the space of probability measures on \({\mathcal {Z}}\). The \(\chi ^2\) divergencesatisfieswhich is an immediate consequence of Cauchy-Schwarz. The Kullback-Leibler divergence of P and Q is given byand the Rényi 2-divergence byThey are nonnegative and related by [33]It is a straightforward calculation to show that if \(D_2(P\Vert Q)<\infty \), thenWe also introduce averaged versions of these divergences. If \(W:{\mathcal {X}}\rightarrow {\mathcal {Z}}\) is a channel, and additionally P is a probability distribution on \({\mathcal {X}}\) and Q on \({\mathcal {Z}}\), then we setandLet X, Y be discrete random variables with joint distribution \(P_{XY}\). Denote the marginal distributions by \(P_X\) and \(P_Y\) and the conditional distribution of Y given the event \(X=x\) by \(P_{Y\vert X=x}\). Then the mutual information of X and Y is defined byThe bounds obtained in the privacy amplification scenario involve Rényi 2-entropy, which for a random variable X on \({\mathcal {X}}\) is defined as

Let \(f:{\mathcal {X}}\times {\mathcal {S}}\rightarrow {\mathcal {A}}\) be the functional form of a mosaic \((D_\alpha )_{\alpha \in {\mathcal {A}}}\) of (v, k, r) tactical configurations and let \(W:{\mathcal {X}}\rightarrow {\mathcal {Z}}\) be a wiretap channel. Assume that the confidential messages to be transmitted are represented by the random variable A on \({\mathcal {A}}\). The random seed is represented by S, uniformly distributed on \({\mathcal {S}}\) and independent of A. Application of the randomized inverse of f determines the random input X to W, and the random output of W seen by Eve is denoted by Z. The joint probability distribution of these four random variables iswhere \(N_\alpha \) is the incidence matrix of \(D_\alpha \).

The two security metrics by which we measure the degree of security offered by f for W are defined in terms of the joint distribution of Z, S and A with a worst-case choice of A. The first security metric is defined as the mutual information between the message A and the eavesdropper’s information Z, S, maximized over all possible message distributions,The best case would be that Eve’s observations are independent of the message, no matter what the message distribution is, in which case the mutual information would vanish. This is not achievable in general, even for a fixed message distribution. Instead, we try to make the maximum in (3.5) as small as possible. Like the other security criteria defined below, the requirement that (3.5) be small does not make any assumptions on Eve’s computing power. Thus we aim for unconditional security.

In order to formulate the upper bound for (3.5), we need to introduce additional notation. If \({\mathcal {U}}\) is a finite set and \(R:{\mathcal {U}}\rightarrow {\mathcal {X}}\) a channel, then the usual matrix product RW of the stochastic matrices R and W gives the channel with input alphabet \({\mathcal {U}}\) and output alphabet \({\mathcal {Z}}\) resulting from concatenating R and W. If P is a probability measure on \({\mathcal {X}}\), then this also defines the probability measure PW on \({\mathcal {Z}}\) by regarding P as a channel with a single row.

The uniform distribution on any set \({\mathcal {X}}\) is denoted by \(P_{{\mathcal {X}}}\). Also, recall Rényi 2-divergence defined in Sect. 3.1.

This theorem is proved in Sect. 4. The main observation is Proposition 4.2, which both for the BIBD and the GDD case states equality between \(\exp (D_2(P_{Z\vert S,A=\alpha }\Vert P_{Z\vert S}\vert P_{{\mathcal {S}}}))\) and the respective upper bounds in the statement. Since this equality for every \(\alpha \) only depends on \(D_\alpha \), it really is a statement about BIBDs and GDDs.

Clearly, a GDD with \(\lambda _1=\lambda _2\) is a BIBD, so the first part of the theorem is implied by the second one. The same holds for Theorems 3.3, 3.6 and 3.7 below.

An alternative measure of semantic security is formulated in terms of total variation distance. Denote the product of probability distributions P and Q by PQ. Then, with the random variables Z, S, A as defined in (3.4), we would liketo be small. If it equals zero, then the eavesdropper’s observations are independent of the message, for all possible message distributions.

This theorem is also proved in Sect. 4. It essentially follows from Theorem 3.2 and the relations (3.1) and (3.3).

Interpretation. The importance of the bounds of Theorems 3.2 and 3.3 is that they show how much randomness k is sufficient in the randomized inverse in order to obtain a desired level of semantic security. Since v non-confidential messages can be reliably transmitted to Bob, this transforms into a lower bound on the number a of confidential messages.

The bounds of Theorems 3.2 and 3.3 can be improved by “smoothing” W. This means that the outputs of W are restricted to being “typical”, i.e., outputs of low probability are cut off. This idea goes back to Renner and Wolf [28]. By smoothing, the conditional divergences can be reduced substantially at the cost of a small additive term in each bound. After smoothing, the channel will in general not be stochastic any more, but only substochastic. The proofs of the theorems remain valid for substochastic channels since they only use the nonnegativity of the entries of W. All that needs to be done is to generalize the Rényi divergences to substochastic channels like in [34].

The bounds can be evaluated by comparing them with the benchmark cases of memoryless discrete and Gaussian wiretap channels (see [9] or [34] for a definition). These wiretap channels actually are families \(\{W_n:n\ge 1\}\) of channels; the parameter n indicates the blocklength. For these channels, a sequence of security codes achieves asymptotic optimality as the blocklength goes to infinity if the largest possible asymptotic communication rate for confidential message transmission, the secrecy capacity, is achieved subject to the condition that either (3.5) or (3.6) goes to zero.

Theorems 3.2 and 3.3 show that security functions given by suitable mosaics of BIBDs or of semi-regular GDDs achieve asymptotic optimality when applied to memoryless discrete or Gaussian wiretap channels after smoothing each \(W_n\). This holds even if the channel between Alice and Bob is not perfect, in which case the \(W_n\) are concatenations of an encoder and a memoryless channel. For the proof, one proceeds like in [34]. Functional forms of block rate optimal mosaics of singular GDDs turn out to be suboptimal security functions, as discussed below.

Note that both in Theorems 3.2 and 3.3, the wiretap channel enters into the upper bounds only through the conditional Rényi 2-divergences. This gives some robustness against channel variations or limited channel knowledge.

The bounds in the GDD case. Assume that N is the incidence matrix of a \((u,m,k,\lambda _1,\lambda _2)\) GDD and \(w\in {\mathbb {R}}^{{\mathcal {X}}}\) a nonnegative vector. Set \(\lambda _\mathrm {max}=\max \{\lambda _1,\lambda _2\}\). ThenIn the proofs of the GDD cases of Theorems 3.2 and 3.3 , the relation (2.5) is used with equality. By using (3.7) instead of (2.5), one obtains an upper bound of the same form as that obtained in the BIBD case of the theorems, with \(\lambda \) replaced by \(\lambda _\mathrm {max}\). Since the point class decomposition of \({\mathcal {X}}\) associated with the applied mosaic of GDDs will not in general have any special relation to the channel, using this looser upper bound might save the work of estimating the additional Rényi divergence or entropy and give a bound which, for the benchmark cases and for mosaics of BIBDs or of semi-regular GDDs, is asymptotically equivalent to the one appearing in the theorems.

The GDD bounds of Theorems 3.2 and 3.3 can also be simplified without using the upper bound (3.7) by taking the type of the members of the mosaic \(M=(D_\alpha )_{\alpha \in {\mathcal {A}}}\) into consideration.

In the case where the members of M are singular GDDs, every \(D_\alpha \) is induced by a BIBD \(D_\alpha ^*\). Since the point class partitions of all \(D_\alpha \) are the same, all \(D_\alpha ^*\) have the same parameters \(v^*,k^*,\lambda ^*\) and form a mosaic of BIBDs. The coefficients of \(D_2(W\Vert P_{{\mathcal {X}}}W\vert P_{{\mathcal {X}}})\) vanish, hence only the divergence involving the point class partition is relevant. In Theorem 3.2, the two nonzero coefficients have the formIn Theorem 3.3, both remaining coefficients equal \((r^*-\lambda ^*)/k^*r^*\).

Semi-regular GDDs satisfy \(rk=\lambda _2v\). Hence if M consists of semi-regular GDDs, then the three coefficients in Theorem 3.2, in the order of their appearance, equalFor the case where \(\lambda _1=0\), in particular, in the case of transversal designs, the same coefficients becomeThe coefficients obtain a similarly simple form in Theorem 3.3.

Suboptimality of singular GDDs. When applied in Theorems 3.2 and 3.3, approximately block rate optimal mosaics of singular GDDs with a small color rate and a sufficiently large point set achieve strictly lower color rates than mosaics of BIBDs or of semi-regular GDDs at the same security level. In particular, they turn out to be asymptotically suboptimal in the case of memoryless discrete or Gaussian wiretap channels, where the size of the point set goes to infinity with increasing blocklength. This means that asymptotically optimal sequences of security functions given by mosaics of BIBDs or GDDs for these channels have block rates at least 1.

We only discuss Theorem 3.2 here, the situation is analogous in Theorem 3.3. We begin with the following simple lemma which is the basis of our discussion.

If one applies Theorem 3.2 with a mosaic of semi-regular GDDs, then one sees from (3.9) that a security level \(\max _{P_A}I(A\wedge Z,S)\) smaller than \(\delta >0\) is achieved by choosing \(\log k\) equal to \(D_2(W\Vert P_{{\mathcal {X}}}W\vert P_{{\mathcal {X}}})+\log (1/\delta )\). This results in the color rateThe same holds in the simpler situation of mosaics of BIBDs.

Now assume that \({\tilde{\varrho }}<1/2\). By Sect. 2.3, the only possibility to achieve a security level smaller than \(\delta \) for the same channel W with an approximately block rate optimal mosaic could be a mosaic M of singular GDDs which is the u-fold multiple of a mosaic \(M^*\) of block rate optimal BIBDs and of color rate \(\varrho ^*\). When Theorem 3.2 is applied with the security function determined by M, the \(D_2(W\Vert P_{{\mathcal {X}}}W\vert P_{{\mathcal {X}}})\) term vanishes in the upper bound of Theorem 3.2. By (3.8), a security level smaller than \(\delta \) is achieved by choosing \(\log k^*\) equal to \(D_2(R_\varPi W\Vert P_{{\mathcal {X}}}W\vert P_\varPi )+\log (1/\delta )\), and without any further information about the channel, this latter expression can be as large as \(D_2( W\Vert P_{{\mathcal {X}}}W\vert P_{{\mathcal {X}}})+\log (1/\delta )\) by Lemma 3.4.

For the color rate \(\varrho \) of M, this means thatThis is at most \({\tilde{\varrho }}\). In fact, for fixed \({\tilde{\varrho }}\), it is easy to see that \(\log u/\log v\) is bounded from below for large v. This is because the approximate block rate optimality of M requires \(\varrho ^*\) to be at least \(\varrho _0(v^*,k^*)\), which tends to 1/2 as \(v^*\) grows. And if \(v^*\) is kept small, then u necessarily has to be large.

The loss of color rate as in (3.10) can be avoided if one knows that equality is satisfied in the left-hand inequality of Lemma 3.4 for a certain partition \(\varPi \). However, an application of this in the security bounds would require knowledge of \(D_2(R_\varPi W\Vert P_{{\mathcal {X}}}W\vert P_\varPi )\) and the adaptation of the point class partition of the GDDs to that of the wiretap channel, which is not necessary in the case of mosaics of BIBDs or of semi-regular GDDs.

Now we turn to privacy amplification. Assume that the random variable X is shared by Alice and Bob and that Eve observes a random variable Z correlated with X. Without loss of generality, we assume that \(P_Z(z)>0\) for all \(z\in {\mathcal {Z}}\). Moreover, Alice and Bob both are given the functional form \(f:{\mathcal {X}}\times {\mathcal {S}}\rightarrow {\mathcal {A}}\) of a mosaic \((D_\alpha )_{\alpha \in {\mathcal {A}}}\) of (v, k, r) tactical configurations. In order to generate a secret key, Alice and Bob observe a realization x of X, choose a seed \(s\in {\mathcal {S}}\) uniformly at random, and take \(\alpha =f(x,s)\) as the secret key. Denote the random variable generated by applying f as described above by A. The joint distribution of X, Z, S and A iswhere \(N_\alpha \) is the incidence matrix of \(D_\alpha \). The key A should be nearly uniformly distributed on \({\mathcal {A}}\) and semantically secure with respect to Eve’s observation. The first condition is satisfied perfectly.

For semantic security, we can again use total variation distance or mutual information as the security measure. One equivalent formulation of semantic security is the indistinguishability of two possible realizations of the secret. In terms of total variation distance, this means that for any two distinct \(\alpha ,\alpha '\in {\mathcal {A}}\), one wantsto be uniformly small. By the triangle inequality, this is true ifis small, uniformly in \(\alpha \in {\mathcal {A}}\).

For any point class partition \(\varPi =\{{\mathcal {X}}_1,\ldots ,{\mathcal {X}}_m\}\) of \({\mathcal {X}}\), we define the random variable \(X_\varPi \) whose conditional distribution given Z isThen we have the following result.

This is proved in Sect. 4 as a consequence of the next theorem.

If we prefer to measure the indistinguishability of key values with respect to Kullback-Leibler divergence, we should ensure that there exists a probability measure Q on \({\mathcal {Z}}\times {\mathcal {S}}\) such that \(P_{ZS\vert A=\alpha }\) is close to Q in terms of Kullback-Leibler divergence, uniformly in \(\alpha \in {\mathcal {A}}\). This is analogous to (3.12). If we choose \(Q=P_ZP_{{\mathcal {S}}}\), then we have the following bound.

The theorem is proved in Sect. 4. As in the wiretap case, its core is Proposition 4.4, proving the equality of \(\exp (D_2(P_{S\vert Z=z,A=\alpha }\Vert P_{{\mathcal {S}}}))\) with the z-term in the upper bound.

Interpretation. The interpretation of Theorems 3.6 and 3.7 is analogous to that of Theorems 3.2 and 3.3 . The number of interest is a, the size of the key space. Theorems 3.6 and 3.7 give a lower bound on the maximal possible a given a required degree of security, and show that this lower bound is achievable using the functional form of a mosaic of BIBDs or GDDs.

It is proved in [7, Corollary 4] thatif the security function is a universal hash function. The upper bound is very similar to the one proved in the first part of Theorem 3.7 for mosaics of BIBDs or of semi-regular GDDs, but only gives strong secrecy. (The conditioning on the event \(Z=z\) is also possible in our setting, see (4.7).) It follows that these mosaics yield the same key size as universal hash functions, but resulting in a stronger notion of security and generating a perfectly uniformly distributed key. Mosaics of singular GDDs only involve the \(\min _zH_2(X_\varPi \vert Z=z)\) term and are discussed in more detail below.

If Alice and Bob are connected by a public two-way channel without rate constraint, the secret-key capacity in the benchmark case of a memoryless discrete source model can be achieved by a sequential key distillation protocol guaranteeing semantic security, using functional forms of mosaics of BIBDs or suitable GDDs in the privacy amplification step (cf. [9, Theorem 4.5]).

The bounds in the GDD case. By applying (3.7), the bounds for the GDD cases of Theorems 3.6 and 3.7 can be given the same form as the ones for the BIBD case, with \(\lambda \) replaced by \(\lambda _\mathrm {max}\).

If the mosaic consists of singular GDDs, then the coefficient of the \(H_2(X\vert Z=z)\) term vanishes. The second and third terms in Theorem 3.7 arewhere, like in the wiretap scenario, \(k^*,r^*,\lambda ^*\) are parameters of the underlying BIBDs.

In the case of semi-regular GDDs, one has, in the order of their appearance, the three termsIn particular, for transversal designs, one obtainsSimilar simplifications are possible for the bounds of Theorem 3.6.

Suboptimality of singular GDDs. As in the wiretap scenario, mosaics of singular GDDs are suboptimal compared with mosaics of BIBDs or of semi-regular GDDs since they require a larger k in order to achieve a comparable security level.

The reasons are analogous to those for the wiretap case, based on the inequalitiesfor any partition \(\varPi =\{{\mathcal {X}}_1,\ldots ,{\mathcal {X}}_m\}\) of \({\mathcal {X}}\) into sets of size u, and any \(z\in {\mathcal {Z}}\). The condition for equality in the right-hand inequality is that there exist at most one x per \({\mathcal {X}}_i\) with \(P_{X\vert Z}(x\vert z)>0\). On the left-hand side, equality holds if and only if \(P_{X\vert Z}(\cdot \vert z)\) is constant on each \({\mathcal {X}}_i\) for every z.

With a mosaic of BIBDs or of semi-regular GDDs, a key size \(\log a\) approximately equal to \(\min _zH_2(X\vert Z=z)+\log (1/\delta )\) gives a security level \(\delta \).

Now assume that the security function is given by a mosaic of singular GDDs. If one only knows \(\min _zH_2(X\vert Z=z)\), then the largest possible key size \(\log a\) by which to guarantee a security level of \(\delta \) is \(H_2(X\vert Z=z)-\log u+\log (1/\delta )\). The key can be chosen larger if one also knows \(\min _zH_2(X_\varPi \vert Z=z)\). However, the same key size as in the case of BIBDs or semi-regular GDDs is achievable only if there exists a partition \(\varPi \) such that equality is satisfied on the right-hand side of (3.14). If one knows that the joint distribution \(P_{XZ}\) has this property for a partition \(\varPi \), then a mosaic of singular GDDs incurs no rate loss, but the security function has to be adapted to \(\varPi \).

We first prove Theorem 3.2. It is sufficient to do the proof for mosaics of GDDs. We start with an upper bound on \(\max _{P_A}I(A\wedge Z,S)\) in terms of Kullback-Leibler divergence. The all-ones vector of suitable dimension will be denoted by j, and for each \(z\in {\mathcal {Z}}\), we let \(w_z\) be the z-th column of W

Note that, since the eavesdropper also knows S, the validity of (4.1) is not enough to guarantee security.

If we want to use (2.3) or (2.5), we need to pass from Kullback-Leibler to Rényi 2-divergence. By Lemmas 4.1 and (3.2), it is sufficient to show that the upper bound of Theorem 3.2 is an upper bound for\(P_{Z\vert S,A=\alpha }\) is fully determined by \(N_\alpha \) and W. Hence for each of the divergence terms in (4.2) it is no longer important that \(N_\alpha \) is the incidence matrix of a member of a mosaic. It follows that Theorem 3.2 is a consequence of the following equality.

Turning to the proof of Theorem 3.3, we first state the following simple analog of Lemma 4.1.

By (4.1), \(P_Z(z)=0\) only if z is not reachable with positive probability from any input of W. ThusHence one can apply (3.1) and (3.3) to upper-bound the right-hand side of (4.5) byTheorem 3.3 now follows from Proposition 4.2.

We start by proving Theorem 3.7. Define the \({\mathbb {R}}^{{\mathcal {X}}}\)-vector \(p_z\) byFrom (3.11), Lemmas 3.5 and (2.1), it follows thatIn particular, Z is independent of A. (Of course, since the eavesdropper also knows S, this is not yet enough to guarantee security.) A straightforward computation givesAs in the wiretap case, one passes to Rényi 2-divergence, and so it remains to bounduniformly in z and \(\alpha \).

We compute \(P_{S\vert Z=z,A=\alpha }\) as follows. Recall the assumption that \(P_Z(z)>0\) for all \(z\in {\mathcal {Z}}\). Let \(\alpha \in {\mathcal {A}}\) and \(s\in {\mathcal {S}}\). The uniform distribution of A and (4.6) imply that \(P_{ZA}(z,\alpha )=a^{-1}p_z^Tj\). Hence, again applying (2.1),This only depends on the incidence matrix \(N_\alpha \), and so as in the wiretap case, we can reduce the proof of Theorem 3.7 to a proposition which holds for GDDs without any reference to mosaics.

This completes the proof of Theorem 3.7.

In order to prove Theorem 3.6, we can appeal to the case where security is measured using divergence, just like in the wiretap case. It is a straightforward computation to show thatfor all \(\alpha \in {\mathcal {A}}\). Using (3.1) and (3.3), we see that Theorem 3.6 follows from Proposition 4.4.

Denote by \(L_{c,d}=\{(x,cx+d):x\in {\mathbb {F}}_q\}\) the line in AG(2, q) with slope \(c\in {\mathbb {F}}_q\) and intercept \(d\in {\mathbb {F}}_q\). This are all lines of AG(2, q) except the “vertical” ones with infinite slope, given by \(L_{\infty ,d}=\{(d,y):y\in {\mathbb {F}}_q\}\), for any \(d\in {\mathbb {F}}_q\). For these lines, we call d the intercept.

For the characterization of \({\mathcal {X}}\) and \({\mathcal {S}}\), we choose H arbitrary. Note that \(0\in {\mathcal {X}}\). Thus every line \(L_{c,0}\) (\(c\in {\mathbb {F}}_q\cup \{\infty \}\)) has nontrivial intersection \({\mathcal {X}}_c\) with \({\mathcal {X}}\). Since any two of these lines only meet in 0, the union of all these \({\mathcal {X}}_c\) has preciselyelements, and so \({\mathcal {X}}\) must equal the union of all \({\mathcal {X}}_c\) by (2.14). Now assume \(c\in {\mathbb {F}}_q\). An element (x, cx) of \(L_{c,0}\) is contained in \({\mathcal {X}}_c\) if and only ifor equivalently, \(x^2\in (\eta _1+\eta _2c+\eta _3c^2)^{-1}H\) (the irreducibility of Q ensures that \(\eta _1+\eta _2c+\eta _3c^2\) is nonzero). In an analogous way one sees that \((0,y)\in {\mathcal {X}}_\infty \) if and only if \(y^2\in \eta _3^{-1}H\).

Next we turn to \({\mathcal {S}}\). We already noted in Sect. 2 that the parallel classes of D are in one-to-one correspondence with those of AG(2, q), i.e., with the slopes from \({\mathbb {F}}_q\cup \{\infty \}\).

For the description of the elements of a parallel class, we need the (absolute) trace of an element x of \({\mathbb {F}}_q\) defined byThe trace is an \({\mathbb {F}}_2\)-linear form from \({\mathbb {F}}_q\) onto \({\mathbb {F}}_2\). Every linear form \(\xi \) from \({\mathbb {F}}_q\) to \({\mathbb {F}}_2\) corresponds to a unique element \(\beta \in {\mathbb {F}}_q\) such that \(\xi (x)={{\,\mathrm{Tr}\,}}(\beta x)\) for all \(x\in {\mathbb {F}}_q\) (see [24, Theorem 2.23]). We denote by \(H^\perp \) the \((t-\ell )\)-dimensional subspace of \({\mathbb {F}}_q\) consisting of those elements whose corresponding linear form vanishes on H.

We will also use the following facts on polynomials. The first one is [24, Theorem 2.25], the second one is elementary.

We have the following lemma.

D is explicit if it satisfies properties (D1) and (D2) formulated in Sect. 2.5. Here we show that it satisfies (D1) for suitable H. Let \(\varTheta =\{1,\vartheta ,\vartheta ^2,\ldots ,\vartheta ^{t-1}\}\) be a polynomial basis of \({\mathbb {F}}_q\). We take H as the span of \(1,\ldots ,\vartheta ^{\ell -1}\). Let \(\varPhi _H:[k]\rightarrow {\mathbb {F}}_2^\ell \) be a bijection which in time \({{\,\mathrm{poly}\,}}(\log k)\) associates to every number from [k] a unique element of H, represented in terms of \(\varTheta \), such that \(\varPhi _H(0)=0\).

Denote by \(\varPhi _{{\mathcal {R}}}:[q+1]\rightarrow {\mathbb {F}}_2^t\cup \{\infty \}\) a \({{\,\mathrm{poly}\,}}(\log q)\) time bijection between \([q+1]\) and the set of slopes \({\mathcal {R}}={\mathbb {F}}_q\cup \{\infty \}\), where \(\varPhi ({\tilde{\imath }})\) for any \({\tilde{\imath }}\in [q]\) is the representation in the basis \(\varTheta \) of a unique element of \({\mathbb {F}}_q\).

Arithmetic operations in \({\mathbb {F}}_q\) can be performed efficiently in \(\varTheta \), as well as the computation of the square root [2, Corollary 7.1.2]. Hence using \(\varPhi _{{\mathcal {R}}}\) and \(\varPhi _H\), one obtains a mapping \(\varPhi _{{\mathcal {X}}}:[v]\rightarrow {\mathbb {F}}_2^t\) which to every element of [v] associates the \(\varTheta \)-representation of a unique element of \({\mathcal {X}}\) (see Lemma 5.2). This mapping is computable in time \({{\,\mathrm{poly}\,}}(\log v)\).

To the basis \(\varTheta \) there exists a dual basis \(Z=\{\zeta _1,\ldots ,\zeta _t\}\) satisfying\(H^\perp \) is the span of \(\{\zeta _{\ell },\ldots ,\zeta _{t-1}\}\). Denote by T the change-of-basis matrix representing every \(\zeta _i\) in terms of \(\varTheta \). Then for any c, there exists a bijective mapping \(\varPhi _{{\mathcal {U}}_c}:[a]\rightarrow {\mathbb {F}}_2^t\) which to any element of [a] first associates the Z-representation of an element of \(({\mathbb {F}}_q\setminus H^\perp )\cup \{0\}\), then changes the basis to \(\varTheta \) using T, and finally does the necessary arithmetic to obtain an element of \({\mathcal {U}}_c\). The values of this mapping can be computed in time \({{\,\mathrm{poly}\,}}(t)={{\,\mathrm{poly}\,}}(\log a)\).

Now assume we are given numbers \({\tilde{x}}\in [v]\) and \({\tilde{\imath }}\in [q+1]\), corresponding to the point \((x,{\tilde{c}}x)\in {\mathcal {X}}\) and the parallel class \(c\in {\mathbb {F}}_q\cup \{\infty \}\) via \(\varPhi _{{\mathcal {X}}}\) and \(\varPhi _{{\mathcal {R}}}\). We want to find the intercept d such that \((x,{\tilde{c}}x)\in L_{c,d}\). If \(c\in {\mathbb {F}}_q\), then \(d=(c+{\tilde{c}})x\). If \(c=\infty \), then \(d=x\). It is straightforward to do these computations in \(\varTheta \). The result is transformed to a number from [a] via \(\varPhi _{{\mathcal {U}}_c}^{-1}\). The representation of d in [a] can be found from inputs \({\tilde{x}}\) and \({\tilde{\imath }}\) in \({{\,\mathrm{poly}\,}}(\log v)\) time.

Let \((c,d)\in {\mathcal {S}}\) be given. We want to find the set \(B_{c,d}\) of those elements of \({\mathcal {X}}\) which are incident with (c, d) in D. For \(d=0\), we have \(L_{c,d}={\mathcal {X}}_c\cup \{0\}\). Now we consider the case \(d\ne 0\). LetOnce we know the set \({\mathcal {R}}_{c,d}\), we can for every \({\tilde{c}}\in {\mathcal {R}}_{c,d}\) find the unique point at the intersection of \(L_{c,d}\) and \({\mathcal {X}}_{{\tilde{c}}}\). If \({\tilde{c}}\in {\mathbb {F}}_q\), this point has the form \((x,{\tilde{c}}x)\) for(clearly, \(c\ne {\tilde{c}}\)). If \({\tilde{c}}=\infty \), the point at the intersection of \(L_{c,d}\) and \({\mathcal {X}}_\infty \) is given by (0, d).

For \(c\in {\mathbb {F}}_q\), define the setand, for every \(z\in H_{c,d}\), the polynomialFor \(c=\infty \), we setand define, for all \(z\in H_{c,d}\), the polynomialAll \(H_{c,d}\) are nonempty due to the proof of Lemma 5.4.

It remains to check that (D2) is satisfied. Let \({\tilde{\imath }}\in [q+1]\) correspond to a parallel class and \({\tilde{\kappa }}\in [a]\) to an element of this parallel class. Through the mapping \(\varPhi _{{\mathcal {R}}}\), one associates to \({\tilde{\imath }}\) a slope \(c\in {\mathbb {F}}_q\cup \{\infty \}\). Then \(\varPhi _{{\mathcal {U}}_c}({\tilde{\kappa }})\) gives an intercept d such that \((c,d)\in {\mathcal {S}}\), where both c and d are represented in the basis \(\varTheta \). It remains to show that the set \({\mathcal {R}}_{c,d}\) can be enumerated in polylogarithmic time. The first task is to find \(H_{c,d}\). We shall use that if \(\beta =\sum _{i=0}^{t-1}\beta _i\zeta _i\) and \(z=\sum _{i=0}^{t-1}z_i\vartheta ^i\), then \({{\,\mathrm{Tr}\,}}(\beta z)=\sum _{i=0}^{t-1}\beta _iz_i\).

Assume that \(c\in {\mathbb {F}}_q\) and \(\eta _3d^2\notin H\) (which can be checked by representing \(\eta _3d^2\) in the basis Z). The other cases are similar. Using the \(\varTheta \)-representations of c and d, computeTransform the result to Z. Now assume that \(\beta =\sum _{i=0}^{t-1}\beta _i\zeta _i\). Since \(H_{c,d}\) is nonempty, the linear form \(z\mapsto {{\,\mathrm{Tr}\,}}(\beta z)\) does not vanish on H. Hence \(\beta _i=1\) for some \(0\le i\le \ell -1\), say \(\beta _{\ell -1}=1\). One can now enumerate the \(\varTheta \)-representations of all elements of \(H_{c,d}\) by enumerating all sequences \(z_0,\ldots ,z_{\ell -2}\) and choosing \(z_{\ell -1}\) such that \(\sum _{i=0}^{\ell -1}\beta _iz_i=1\).

Given \(z\in H_{c,d}\), it remains to find both roots of \(G_{c,d,z}\). This means that one has to solve the inhomogeneous linear equationIf \({\tilde{c}}\) satisfies this equation, then \({\tilde{c}}+1\) is the other solution. This equation can be solved in polylogarithmic time in q, and so it is possible to find the points of \({\mathcal {X}}\) incident with (c, d) in polylogarithmic time.