Advance in Keyless Cryptography

Abstract

The term “keyless cryptography” as it is commonly adopted, applies to secure message transmission either directly without any key distribution in advance or as key sharing protocol between communicating users, based on physical layer security, before ordinary encryption/decryption procedures. In the current chapter the results are presented concerning to keyless cryptography that have been obtained by authors recently. Firstly Shamir’s protocol of secure communication is considered where commutative encryption procedure is executed. It has been found out which of the public key algorithms can be used with such protocol. Next item of consideration concerns Dean’s and Goldsmith’s cryptosystem based on multiple-input, multiple-output (MIMO) technology. It has been established under which conditions this cryptosystem is in fact secure. The third example under consideration is EVSkey scheme proposed recently by D. Qin and Z. Ding. It has been proven that such key distribution method is in fact insecure, in spite of the authors’ claims. Our main result is a description of a key sharing protocol executing over public noiseless channels (like internet) that provides a key sharing reliability and security without any cryptographic assumptions.

1. Introduction

The term keyless cryptography dates back many years ago. See for example the paper [1]. One author of this chapter used also before this term many times, for example in the papers [2, 3, 4]. This term is commonly used in two senses: either in the scenarios where information transmission security is provided by special channel properties without execution of key sharing protocol in advance, or in the second scenarios where specific channel properties are used on the stage of secret key sharing between users, whereas later are executed ordinary key-based cryptography. An approach to a providing of security at the cost of channel properties was termed as physical layer security [5]. As a rule, it means that communication channel plays the role of some randomizer due to their specific stochastic properties. However, sometimes such randomization is provided by the use of artificial noises by the communicating users.

A natural question arises—why it is not sufficiently to execute algorithms of the so-called public key cryptosystems (PKC), invented by W. Diffie and M. Hellman and developed later by many cryptographers: A. Shamir, Rabin, El Gamal, McEliece, J. Massey, and others (see [6, 7])? The point is that PKC have some drawbacks that limit their practical use. The main of these are:

1. PKC are based on some cryptographic assumptions (integer factoring, discrete log computation, error correction by random liner codes [6]). Unfortunately, the most of such hard computational problems can be solved in polynomial time by quantum computers (QC) [8]. Although a practical implementation of such QC’s is still highly conjectural [9], it would be a hazardous to ignore such attacks in the future.

2. The use of PKC is needed in an assistance of certificated center that would be guaranty an authenticity of public keys in order to prevent impersonation attack where an attacker camouflages itself by authorized user and could share with legitimate user falsified keys.

3. The third shortcoming is in a complexity of encryption/decryption algorithms because it requires performing operations with large integer values. It is especially important for mobile hardware devices.

One more way out to provide secure key sharing is an implementation of quantum cryptography [10]. But unfortunately such approach requires the use of very specific quantum devices.

The objections mentioned above give the reason to turn to keyless cryptography which is what we do in this chapter. In Section 2 we investigate Shamir’s protocol for secure communication over public channels but without any key sharing in advance. This protocol corresponds to the first scenario. Section 3 presents Dean and Goldsmith cryptosystem that performs channel transmission like a randomizer in the first scenario. We turn out under which restrictions on the channel such protocol is in fact secure. In Section 4 the second scenario (with key sharing) is considered and it is shown that on the contrary to author’s claims [11], such key sharing protocol (KSP) is in fact insecure. Section 5 corresponds also to the second scenarios. We present a new KSP and prove that such protocol for appropriated chosen parameters provides reliable shared keys which are secure in terms of Shannon information without any cryptographic assumptions. Section 6 summarized all previous results and presents our opinion regarding to possible future investigations.

2. Investigation of Shamir’s protocol based on commutative cryptography

Shamir’s protocol was described in the book [6]. This protocol can be executed for any cryptosystem (both symmetric and asymmetric) if they satisfy the following condition:

$$f_{K_A}\left(f_{K_B}\left(M\right)\right)=f_{K_B}\left(f_{K_A}\left(M\right)\right),$$E1

where $f_{K_A\left(K_B\right)}\left(M\right)$ is encryption algorithm using the keys $K_A$ and $K_B$, respectively and $M$ is any message. If relation (1) is true for some encryption algorithm $f_{K_A\left(K_B\right)}\left(M\right)$ then can be performed protocol presented in Figure 1.

Figure 1.

Protocol based on relation (1) where $f_{K_A}^{-1}\left(·\right)$ is decryption algorithm given the key $K_A$.

If the relation (1) is valid, then we get:

$$C_A^{\prime }=f_{K_A}^{-1}\left(C_B\right)=f_{K_A}^{-1}\left(f_{K_B}\left(f_{K_A}\left(M\right)\right)\right)=f_{K_A}^{-1}\left(f_{K_A}\left(f_{K_B}\left(M\right)\right)\right)=f_{K_B}\left(M\right)$$E2

On the next step user B decrypts $f_{K_B}\left(M\right)$ by the algorithm $f_{K_B}^{-1}\left(·\right)$ and gets the message $M$. But the following question arises—for which cryptosystems the relation (1) is valid? Let us call such encryption algorithms, for which (1) is true, commutative encryption (CE). It is easy to verify that for such cryptographic standard as AES, 3DES, GOST [7] the relation (1) is not fulfilled for all messages. Let us consider public key cryptosystems and, first of all, Rivest-Shamir-Adleman system (RSA). It is well known that such cryptosystem is determined by the following parameters: $p,q$—different primes, $n=\mathit{pq}\left(\mathit{\text{modulo}}\right)$, $\phi =\left(p-1\right)\left(q-1\right)$, $e$—encryption key, $1\le e\le \phi$, $d$—decryption key, $d=e^{-1}\mathit{mod}\phi$, $gcd\left(e,\phi \right)=1$, $1\le M\le n-1$—integers. Encryption algorithm for RSA is $E=M^e\mathit{mod}n$; decryption algorithm is $M=E^d\mathit{mod}n$. Then for RSA condition (1) takes the form:

$${\left(M^{e_A}\mathit{mod}n\right)}^{e_B}\mathit{mod}n={\left(M^{e_B}\mathit{mod}n\right)}^{e_A}\mathit{mod}n$$E3

Since exponentiation by modulo $n$ is a commutative operation, the relation (3) becomes trivially true. In fact

$${\left(M^{e_A}\mathit{mod}n\right)}^{e_B}\mathit{mod}n=M^{e_A{e}_B}\mathit{mod}n={\left(M^{e_B}\mathit{mod}n\right)}^{e_A}\mathit{mod}n=M^{e_B{e}_A}\mathit{mod}n.$$

On the one hand RSA system is self-sufficient one but on the other hand there may be situations where its public key $e_B$ is unknown for the user $A$ or should be secure. Then protocol shown in Figure 1 could have a reason.

Example. Let $p=3$, $q=5$, $M=2$, $e_A=3$, $e_B=5$. Then it is easy to verify that both parts of (3) are equal to 8.

Let us consider as next public key cryptosystem, Rabin’s one, that is determined by the following parameters [7]: $p,q$ are distinct primes (secret key), $n_{A\left(B\right)}=\mathit{pq}\left(\mathit{\text{modulo}}\right)$ is public key. $0\le M\le n-1$, $E=M^2\mathit{mod}n$. Then relation (1) takes the form:

$${\left(M^2\mathit{mod}{n}_A\right)}^2\mathit{mod}{n}_B={\left(M^2\mathit{mod}{n}_B\right)}^2\mathit{mod}{n}_A$$E4

It is easy to make sure that (4) is not satisfied, generally speaking. In fact, let us consider an example: $p_A=3$, $q_A=5$, $n_A=15$, $p_B=11$, $q_B=7$, $n_B=77$, $M=5$. Then it is easy to check that the left side of (4) is equal to 23, while the right side is equal to 10.

In order to find out the reason of that fact, let us present both sides of (4) as the following values, respectively:

$$\begin{array}{c}{\left(M^2\mathit{mod}{n}_A\right)}^2\mathit{mod}{n}_B={\left(M^2-n_{A}l\right)}^2\mathit{mod}{n}_B=\\ =\left(M^4-2M^2{n}_{A}l+n_A^2{l}^2\right)\mathit{mod}{n}_B,\end{array}$$E5

where $l$ is some integer.

$$\begin{array}{c}{\left(M^2\mathit{mod}{n}_B\right)}^2\mathit{mod}{n}_A={\left(M^2-n_{B}m\right)}^2\mathit{mod}{n}_A=\\ =\left(M^4-2M^2{n}_{B}m+n_B^2{m}^2\right)\mathit{mod}{n}_A,\end{array}$$E6

where $m$ is some integer too. We can see that in general case $n_A\ne n_B$ the right sides of (5) and (6) are different values. It was mentioned in Section 1 that some PKC is vulnerable against QC’s. Such of them that are resistant against QC’s attacks were called post quantum cryptosystems. The most known among them is McEliece PKC [7]. The matrices that determine it are: $k\times n$ matrix ${\stackrel{\sim }{G}}_{A\left(B\right)}=S_{A\left(B\right)}{G}_{A\left(B\right)}{P}_{A\left(B\right)}$—public key where $S_{A\left(B\right)}$ is nonsingular random $k\times k$ matrix, $P_{A\left(B\right)}$ is permutation random $n\times n$ matrix, $G_{A\left(B\right)}$ is random Goppa code generating matrix. Matrices $S_{A\left(B\right)}$, $G_{A\left(B\right)}$, $P_{A\left(B\right)}$ are believed as secret key jointly with a binary random vector $Z_{A\left(B\right)}$ of the known length $n$, and with given weight $t_{A\left(B\right)}$. Encryption procedure is performed as follows:

$$E_{A\left(B\right)}=M{\stackrel{\sim }{G}}_{A\left(B\right)}\oplus Z_{A\left(B\right)},$$E7

where “$\oplus$” is bitwise modulo two addition. It follows from (7) that commutative property (1) for McEliece CS was looking as:

$$f_{K_A}\left(f_{K_B}\left(M\right)\right)=\left(M{\stackrel{\sim }{G}}_B\oplus Z_B\right){\stackrel{\sim }{G}}_A\oplus Z_A=M{\stackrel{\sim }{G}}_B{\stackrel{\sim }{G}}_A\oplus Z_B{\stackrel{\sim }{G}}_A\oplus Z_A$$E8

$$f_{K_B}\left(f_{K_A}\left(M\right)\right)=\left(M{\stackrel{\sim }{G}}_A\oplus Z_A\right){\stackrel{\sim }{G}}_B\oplus Z_B=M{\stackrel{\sim }{G}}_A{\stackrel{\sim }{G}}_B\oplus Z_A{\stackrel{\sim }{G}}_B\oplus Z_B$$E9

It is easy to see that the values in the right sides of (8) and (9) are, generally speaking, unequal one to another owing at least different vectors $Z_A$ and $Z_B$. Hence McEliece CS does not correspond to CE algorithm. At a single glance stream cipher is looking as CE algorithm. In fact, the encryption procedure for this cipher is:

$$E\left(M,K\right)=M\oplus \gamma \left(K\right),$$E10

where $E\left(M,K\right)$ is a cipher text given secret key $K$, $\gamma \left(K\right)$ is an encrypting binary sequence (gamma) given the key $K$, “$\oplus$” is bitwise modulo 2 addition, $M$ is the binary message to be encrypted. It follows from (10) that the condition (1) takes the following form for $\gamma$-based stream ciphers:

$$M\oplus \gamma \left(K_A\right)\oplus \gamma \left(K_B\right)=M\oplus \gamma \left(K_B\right)\oplus \gamma \left(K_A\right)$$E11

that is valid trivially. The use of stream ciphers as CE in protocol shown in Figure 1 was looking as it is presented in Figure 2.

Figure 2.

Protocol of secret message transmission based on stream ciphers.

However we can see from Figure 2 that eavesdropper receiving $C_B$ and $C_A^{\prime }$ be able to bitwise add them by modulo 2 that gives the following binary sequence: $M\oplus \gamma \left(K_B\right)\oplus \gamma \left(K_B\right)\oplus M\oplus \gamma \left(K\mathrm{A}\right)=\gamma \left(K_A\right)$. Next, attacker add bitwise modulo 2 the last sequence $\gamma \left(K_A\right)$ with the sequence $C_A$ intercepted during the first transmission session that gives $M\oplus \gamma \left(K_A\right)\oplus \gamma \left(K_A\right)=M$ that is exactly the desired open sequence $M$. (It is worth to note that similar conclusion was mentioned in [6].)

3. Protocol of keyless Dean and Goldsmith system elaborated for secure message transmission through fading channels with executing MIMO technology

Cryptosystem proposed by Dean and Goldsmith in [12] belongs also to the class of keyless cryptography because it may provide a security of message transmission without a secret key sharing in advance. The main difference in the knowledge of legitimate users and eavesdroppers is only their different locations in space. But such cryptosystems can be used not in all possible scenarios but only in those ones where messages are transmitted over fading channels and with the use of a massive multiple-input, multiple-output (MIMO) technology.

For brevity, we denote such cryptosystem by abbreviation DGC. First, we consider the model with the main steps of its implementation for the particular case where the number of legal user receiving antennas $n_r$ and eavesdropper antennas $n_r^{\prime }$ are equal to each other. (Later we consider more general case $n_r\ne n_r^{\prime }$).

Legitimate channel between Alice (A) and Bob (B) is described by equation:

$$z=\mathit{Ay}+e,$$E12

where $z\in {\mathbb{R}}^n$ is vector received by B, $y\in {\mathbb{R}}^n$ is vector transmitted by A, $e\in {\mathbb{R}}^n$ is additive noise vector at the receiver B, $A\in {\mathbb{R}}^{n\times n}$ is legitimate channel matrix. It is assumed that $e$ are i.i.d. Gaussian vectors: $N\left(0,{\sigma }_e^2\right)$. $A=\left(a_{\mathit{ij}}\right),\left(i=1\dots n,j=1\dots n\right)$ are also matrices with i.i.d. Gaussian matrix elements: $N\left(0,{\sigma }^2\right)$. For Eavesdropper channel from A to E (Eve) holds the equation:

$$z^{\prime }=\mathit{By}+e^{\prime },$$E13

where $z^{\prime }\in {\mathbb{R}}^n$ is vector received by E, $e^{\prime }\in {\mathbb{R}}^n$ is additive noise vector at the receiver E, $B\in {\mathbb{R}}^{n\times n}$ eavesdropper channel matrix. It is assumed that $e^{\prime }$ are also i.i.d. vectors based on Gaussian distribution $N\left(0,{\stackrel{\sim }{\sigma }}_e^2\right)$, $B=\left(b_{\mathit{ij}}\right)$, $i=1,\dots ,n,j=1,\dots ,n$ with $b_{\mathit{ij}}$ which are i.i.d. Gaussian values $N\left(0,{\sigma }_w^2\right)$. All entries of matrices $A$ and $B$ are assumed to be mutually independent. Next three conditions are very important for further discussion:

• channel matrices $A$ and $B$ are constant for some time until user A applies encoder,

• matrix $A$ is known exactly by legitimate users,

• matrices $A$ and $B$ are known exactly by eavesdropper E.

It is worth to note that the model described above is more or less valid in practice for fading channels based on MIMO technology if space distance between legitimate users and eavesdropper is at least several wavelengths of communication. Encoding procedure in line with [12] is the following:

$$y=\mathit{Vx},$$E14

where $V\in {\mathbb{R}}^{n\times n}$ is orthogonal matrix taken from singular value decomposition (SVD) of matrix $A=\mathit{US}{V}^T$, $x\in {\mathbb{R}}^n$ with binary entries $x_i$, $i=1,\dots ,n$. Predecoding procedure in line with [12] is the following:

$$z^{\prime }=U^{T}z=U^T\mathit{Ay}+e^{\prime }=U^T\mathit{US}{V}^T\mathit{Vx}+U^{T}e=\mathit{Sx}+e\prime ,$$E15

where $U\in {\mathbb{R}}^{n\times n}$ is orthogonal matrix taken from SVD of matrix $A$, $e^{\prime }=U^{T}e$. Since $S$ is diagonal matrix, we get from (15) the following optimal decoding rule:

$$x^{\prime }=arg\underset{{\mathrm{x}}_{\mathrm{i}}}{min}\left|z_i^{\prime }-x_i{s}_i\right|,i=1,\dots ,n,$$E16

where $s_i$ is $i$-th element of diagonal matrix $S$, $x_i$ are binary entries of vector $x$. We can see from (16) that decoding procedure has linear complexity on the number of antennas $n$. Eavesdropper E following to strategy of legitimate users performs the optimal decoding procedure:

$$z^{\prime }={U^{\prime }}^T{z}^{\prime },$$E17

where

$$z^{\prime }=\mathit{BVx}+e^{\prime }=U^{\prime }{S}^{\prime }{V^{\prime }}^T\mathit{Vx}+e^{\prime },$$E18

where $U^{\prime }$, $V^{\prime }$, $S^{\prime }$ are SVD of matrix $B$. Substituting (18) into (17), we get:

$$z^{\prime \prime }=\mathit{Cx}+\stackrel{\sim }{e},$$E19

where $C=S^{\prime }{V^{\prime }}^{T}V$, $\stackrel{\sim }{e}={U^{\prime }}^T{e}^{\prime }$. Since matrix C is not a diagonal one in this case, their optimal decoding be the following:

$$\stackrel{\sim }{x}=argmin‖z^{\prime \prime }-\mathit{Cx}‖,$$E20

where$‖·‖$ is Euclidian norm in ${\mathbb{R}}^n$. Solution of problem (20) is known as hard CVP problem and it was proved in [12] that it has exponential complexity with respect to the number of antennas $n$ if the following condition holds:

$${\sigma }_w^2{\stackrel{\sim }{\sigma }}_e^2>n^{1/2}$$

But let us consider suboptimal decoding method after some transform, assuming that matrix $C$ is non-singular:

$$C^{-1}{z}^{\prime \prime }=x+C^{-1}\stackrel{\sim }{e}$$

Thus suboptimal decoding method can be implemented as follows:

$${\stackrel{\sim }{x}}_i=argmin\mid {\stackrel{\sim }{z}}_i-x_i\mid ,i=1,\dots ,n,$$E21

where ${\stackrel{\sim }{z}}_i$ is the $i$-th entry of vector $C^{-1}{z}^{\prime \prime }$.

We can see from (21) that complexity of suboptimal decoding procedure is linear on the number $n$ of antennas. The efficiency of DGC can be estimated by comparing the bit error rate (BER) for optimal decoding (16) and suboptimal decoding (21). In fact if for some chosen DGC parameters the first BER is satisfactory while the second one is close to ½, then DGC can be termed as secure. In Table 1 are presented the results of simulation for BER’s by (16) and (21) denoted as $p$ and $p^{\prime }$, respectively.

No	System parameters	n	Symbol error probability for legitimate users (p)	Symbol error probabilities for Eavesdropper ($p\prime$)
1	${\sigma }^2={\sigma }_w^2=2,{\sigma }_e^2={\stackrel{\sim }{\sigma }}_e^2=1$	100	0.02	0.2
2	${\sigma }^2={\sigma }_w^2=4,{\sigma }_e^2={\stackrel{\sim }{\sigma }}_e^2=8$	100	0.037	0.3
3	${\sigma }^2={\sigma }_w^2=1,{\sigma }_e^2={\stackrel{\sim }{\sigma }}_e^2=30$	100	0.02	0.42
4	${\sigma }^2=2,{\sigma }_w^2=1,{\sigma }_e^2={\stackrel{\sim }{\sigma }}_e^2=4$	1000	$5.6\times {10}^{-3}$	0.3
5	${\sigma }^2=4,{\sigma }_w^2=8,{\sigma }_e^2={\stackrel{\sim }{\sigma }}_e^2=12$	1000	0.01	0.33

Table 1.

The results of simulation for BER $p$ and $p^{\prime }$ with different chosen parameters of DGC.

We can see from Table 1 that for all five set of system parameters, DGC is looking as acceptable one because the case $p^{\prime }\ge 0.3$ does not allow to recover a meaningful text. In fact, let us consider 32-ary symmetric noisy channel (in line with 32-ary alphabet of Russian language). Then it is easy to see that Shannon capacity of such channel, if every letter is encoded by five bits with BER equal to $p^{\prime }$, is:

$$C=\begin{array}{l}5+{\left(1-p^{\prime }\right)}^5{log}_2{\left(1-p^{\prime }\right)}^5+5p^{\prime }{\left(1-p^{\prime }\right)}^4{log}_2\left(p^{\prime }{\left(1-p^{\prime }\right)}^4\right)+\\ +10{p^{\prime }}^2{\left(1-p^{\prime }\right)}^3{log}_2\left({p^{\prime }}^2{\left(1-p^{\prime }\right)}^3\right)+10{p^{\prime }}^3{\left(1-p^{\prime }\right)}^2{log}_2\left({p^{\prime }}^3{\left(1-p^{\prime }\right)}^2\right)+\\ +5{p^{\prime }}^4\left(1-p^{\prime }\right){log}_2\left({p^{\prime }}^4\left(1-p^{\prime }\right)\right)+{p^{\prime }}^5{log}_2{p^{\prime }}^5\end{array}$$E22

In Table 2 are presented the values of channel capacity calculated by (22) for different values $p^{\prime }$.

p’	0.1	0.11	0.15	0.18	0.19
C	2.65	2.5	1.95	1.6	1.5
p’	0.2	0.25	0.3	0.35	0.4
C	1.39	0.94	0.59	0.33	0.15
p’	0.41	0.42	0.43	0.44	0.45
C	0.12	0.093	0.071	0.052	0.036
p’	0.46	0.47	0.48	0.49	0.5
C	0.023	0.013	0.0058	0.0014	0

Table 2.

The values of channel capacity $C$ for different $p^{\prime }$.

It is well known that entropy $H$ of Russian language lies within interval $1.5÷2.5$ bit/letter. This means that according to Shannon’s theorem, if $H>C$, then a reading of meaningful text be impossible. In our case we get that if $p^{\prime }>0.19$ such text decoding cannot be done, that is exactly the thing for every set of parameters in Table 1. Moreover, we simulated transmission of Russian meaningful text over the channel with BER equal to $0.19$ and have got that only very short words could be readable. Thus we may conclude so far, that DGC is secure against eavesdropping at least for the condition $n_r^{\prime }=n_r$ and the more $n_r^{\prime }<n_r$. But the following question arises—if such conclusion is true for the case $n_r^{\prime }>n_r$? In Table 3 are presented the results of simulation BER’s $p^{\prime }$ for eavesdropper by suboptimal decoding rule (21) in the case of typical parameters ${\sigma }^2={\sigma }_w^2=4$, ${\sigma }_e^2={\stackrel{\sim }{\sigma }}_e^2=7$, $n_r=100$ and different $n_r^{\prime }$, where inverse matrix $C^{-1}$ for rectangular $n_r\times n_r^{\prime }$ matrix $C$ was calculated as Moore-Penrose pseudo-inverse matrix to $C\left[14\right]$.

$n_r^{\prime }$	100	101	102	103	105	107
$p^{\prime }$	0.31	0.22	0.16	0.12	0.07	0.048
$n_r^{\prime }$	108	109	110	120	150
$p^{\prime }$	0.039	0.03	0.024	0.003	$7\times {10}^{-4}$

Table 3.

Results of BER $p^{\prime }$ simulation for decision rule (21), $n_r=100$ and different $n_r^{\prime }\ge n_r$.

We can see from Table 3 that even small increasing of $n_r^{\prime }$ (on 9 antennas) compared to $n_r$, results in a drastic degradation of DGC because the symbol error probability $p^{\prime }$ becomes for eavesdropper very close to the probability $p$ for legitimate users. In order to find out that such “paradox” that contradicts to our intuition appears not due to “ill-posed” inverse matrices [13], let us consider a theoretical proof of the bounds for the symbol correct probabilities both for legitimate users and eavesdropper. It is easy to see that decision rule (16) for legitimate users when $x_i\in \left(0,1\right)$ is equivalent to the following relation:

$$x_i^{\prime }=\left\{\begin{array}{c}0\text{if}{z}_i^{\prime \prime }\le S_i/2,\\ 1\text{if}{z}_i^{\prime \prime }>S_i/2.\end{array}\right.$$

Thus for the symbol correct probability we get the following lower bound:

$$P\left\{x_i^{\prime }=x_i\right\}\ge P\left\{\left|e_i\right|<S_i/2\right\},$$E23

where $e_i$ is the $i$-th entry of additive noise vector $e$ in (12). Because we assumed before that $e_i\sim N\left(0,{\sigma }_e^2\right)$ we get from (23):

$$P\left\{x_i^{\prime }=x_i\right\}\ge 2\mathrm{\Phi }\left(\frac{S_i}{2{\sigma }_e}\right)$$E24

where $\mathrm{\Phi }\left(a\right)=\frac{1}{\sqrt{2\pi }}{\int }_0^{a}exp\left(-\frac{t^2}{2}\right)\mathit{dt}$. The decision rule (21) for eavesdropper will be equivalent to the following one:

$${\stackrel{\sim }{x}}_i=\left\{\begin{array}{c}0\text{if}{\stackrel{\sim }{z}}_i\le 1/2,\\ 1\text{if}{\stackrel{\sim }{z}}_i>1/2.\end{array}\right.$$E25

From relation (25) we get the lower bound for correct symbol probability:

$$P\left\{{\stackrel{\sim }{x}}_i=x_i\right\}\ge P\left\{\left|e_i^{\prime \prime }\right|\le \frac{1}{2}\right\}=2\mathrm{\Phi }\left(\frac{1}{2\sqrt{\mathit{Var}\left\{e_i^{\prime \prime }\right\}}}\right),$$E26

where $e_i^{\prime \prime }$ is the $i$-th entry of additive noise vector $e^{\prime \prime }=C^{-1}\stackrel{\sim }{e}$. In order to find $\mathit{Var}\left\{e_i^{\prime \prime }\right\}$ let us accomplish some matrix transforms:

$$C=\mathit{BV}=U^{\prime }{S}^{\prime }{V}^{\prime }V,$$

$$C^{-1}=V^T{V}^{\prime }{\left(S^{\prime }\right)}^{-1}{U^{\prime }}^T,$$

$$e^{\prime \prime }=C^{-1}\stackrel{\sim }{e}=V^T{V}^{\prime }{\left(S^{\prime }\right)}^{-1}{U^{\prime }}^T.$$E27

Taking into account that $U^{\prime }$ is orthogonal matrix and $S^{\prime }$ is diagonal one, we get from (27):

$$\mathit{Var}\left\{e_i^{\prime \prime }\right\}={\stackrel{\sim }{\sigma }}_e^2\sum _{k=1}^{n_r}\frac{V_{\mathit{ik}}^2}{{S_k^{\prime }}^2}$$E28

where $V_{\mathit{ik}}$ are elements of matrix $V^T{V}^{\prime }$ and $S_k^{\prime }$ elements of matrix $S^{\prime }$. Substituting (28) into (27) we obtain

$$P\left\{{\stackrel{\sim }{x}}_i=x_i\right\}\ge 2\mathrm{\Phi }\left(\frac{1}{2{\stackrel{\sim }{\sigma }}_e\sqrt{{\sum }_{k=1}^{n_r}\frac{V_{\mathit{ik}}^2}{{S_k^{\prime }}^2}}}\right)$$E29

In order to compute theoretically the average value of symbol correct probabilities, it would be necessary to average relations (24) and (29) on the probability distribution of singular values $S_k$, and also on elements of channel matrices $V^T{V}^{\prime }$. Solution to this problem requires a very crude approximations. Therefore we used simulations by (24) and (29). In Table 4 are presented such results for both legitimate users ($q$) and for eavesdropper ($q^{\prime }$) with channel parameters: ${\sigma }^2={\sigma }_w^2=7$, ${\sigma }_e^2={\stackrel{\sim }{\sigma }}_e^2=4$, $n_t=n_r=100$ against different numbers $n_r^{\prime }$ for eavesdropper antennas.

$n_r^{\prime }$	100	101	102	103	104	105
$q$	0.95	0.95	0.95	0.95	0.95	0.95
$q^{\prime }$	0.71	0.75	0.8	0.87	0.9	0.95
$n_r^{\prime }$	106	107	108	109	110
$q$	0.95	0.95	0.95	0.95	0.95
$q^{\prime }$	0.96	0.97	0.98	0.985	0.99

Table 4.

The symbol correct probabilities obtained by simulation of averaged bounds for $q$ (24) and for $q^{\prime }$ (29).

We can see from this Table that an increasing of the eavesdropper’s antennas even till $n_r^{\prime }=105$ results in equality of values $q$ and $q^{\prime }$ that is in line with our previous claiming. Thus we can conclude that a compromising of DGC after a small increment of the eavesdropper antenna numbers against legitimate user antenna numbers is the proved fact but not a consequence of an ill-conditioned matrix property. On the other hand, legitimate users executing DGC do not take for granted that the condition $n_r^{\prime }\le n_r$ holds. In the paper [14] it was proposed to change matrix $V$ in “precoding” procedure to another matrix. In particular, authors of the current paper have proved that a choice of matrix $A^{-1}$ as precoding one has some advantages, namely a growth of some parameter “advantage” (introduced in [14]) for legitimate users proportional to $n^2$ if $n=n_t=n_r=n_r^{\prime }$. Such approach means that a precoding procedure is simply “canceling of channel fading”.

However in the case of such precoding we face with a growing of the transmitter power. In Table 5 are presented the results of the average transmitter power calculated for the case of precoding with matrix $A^{-1}$, and obtained by simulation for $n=n_t=n_r=n_r^{\prime }=100$ on different sessions with 10,000 realizations for each session.

Session numbers	1	2	3	4	5
$P_0$	$4.5\times {10}^5$	$1.8\times {10}^7$	$9.1\times {10}^5$	$2.1\times {10}^6$	$8.8\times {10}^4$
Session numbers	6	7	8	9	10
$P_0$	$5.9\times {10}^5$	$3.4\times {10}^4$	$5.2\times {10}^4$	$2.5\times {10}^5$	$1.08\times {10}^5$

Table 5.

Average transmitter power $P_0$ with precoding matrix $A^{-1}$ for different sessions.

We can see from Table 5 that the use of inverse precoding results in a drastic growing of the required transmission power and to a large fluctuations on each of sessions that makes such approach impracticable (we note that such power was equal to be $n^2={10}^4$ only for ordinary encoding by matrix $V$). It seems to be acceptable to use for a precoding $V=A^{-1}$ only in the case with the required transmitter power $P_0\le P_{\mathit{tr}}$ where $P_{\mathit{tr}}$ is some reasonable threshold and ordinary matrix $V$ otherwise. But such approach requires further investigations.

There is one more problem with practical implementation of DGC. It is a correct estimation of the channel matrix $A$ by legitimate users. Of course, they may do it by a sending of special test signal from user A to user B and back from B to A during a coherent time of legitimate channel, when matrix $A$ holds practically constant. But any way it will result in some matrix $A$ corruption. In Table 6 are given our simulation results for symbol error probabilities that obtain legitimate users if they estimate elements of the channel matrix $A$ with Gaussian noise error having variance ${\sigma }_{\epsilon }^2$. We can see from Table 6 that a correctness of matrix element estimation affects very strong on the symbol error probabilities. It is possible to neglect such incorrectness only if signal-to-noise ratio for legitimate users is about 30-40 dB that is sufficiently high requirement.

${\sigma }^2$	${\sigma }_e^2$	${\sigma }_{\epsilon }^2$
		1	0.1	0.01	0.001	0
2	3	0.1677	0.0587	0.0271	0.0208	0.02
3	8	0.1332	0.053	0.0383	0.0378	0.037
50	4	0.0364	0.0126	0.0093	0.0088	0.0084

Table 6.

Results of symbol error probabilities for legitimate users under the incorrect estimation of channel elements with variance ${\sigma }_{\epsilon }^2$.

Concluding the Section 3 we may say that theoretically would be interesting to develop further DGC in the direction of improving precoding algorithm. But according to our opinion, practical implementation of such approach is very sensitive to channel and system parameters (SNR for eavesdropper and their antenna numbers). It is worth to note also that it is not so dangerous to face with unfavorable parameters for DGC implementation as the fact that these parameters cannot be controlled by legitimate users and hence they are unable to match with parameters of DGC. In the Section 5 we consider protocol that is completely invariant to channel parameters.

4. EVSkey scheme proposed by Qin and Ding

In this Section we consider the second scenarios of keyless cryptography the purpose of which is to share secret keys between legitimate users communicating with each other over channels and next to execute the shared key for ordinary key-based cryptography. In the current section we consider key sharing protocol proposed by G. Qin and Z. Ding in the paper [11], called EVSkey Scheme and declared secure by their authors. This KSP is presented in Figure 3. Before a performance of KSP A and B generate their own random unitary matrices $X_A,X_B\in {ℂ}^{n\times n}$ as well as random Ginibre matrices $G_A,G_B\in {ℂ}^{n\times n}$, where $n$ is the number of antennas employed by each of the users, and length of pilot signals too. Matrices $H_{\mathit{AB}},H_{\mathit{BA}}$ are $n\times n$ channel matrices with independent Gaussian matrix elements distributed according to $\left(h_{\mathit{AB}}\right),\left(h_{\mathit{BA}}\right)\sim \mathit{CN}\left(0,1\right)$. $N_{A_1},N_{B_1}$ are additive white Gaussian noise (AWGN) matrices ${\left(n_{A_1}\right)}_{\mathit{ij}},{\left(n_{B_1}\right)}_{\mathit{ij}}\in \mathit{CN}\left(0,{\sigma }^2\right)$ of proper noises for legitimate users A and B, respectively.

Figure 3.

The KSP corresponding to EVSkey scheme.

Let us introduce the following matrices: $P=H_{\mathit{BA}}{G}_B,Q=H_{\mathit{AB}}{G}_A$. Then $\mathit{PQ}$ and $\mathit{QP}$ can be estimated by users via least square method as

$$\mathit{PQ}\approx Y_{A_2}{\left(X_A\right)}^{-1},\mathit{QP}\approx Y_{B_2}{\left(X_B\right)}^{-1}$$

It is well known [13] that square matrices of the same size $\mathit{PQ}$ and $\mathit{QP}$ have the same characteristic polynomials (CP):

$$\mathit{CP}\left[\mathit{PQ}\right]=\mathit{CP}\left[\mathit{QP}\right]$$E30

Thus from (30) we conclude that the legitimate users A and B are able to extract the same CP after a completion of four-steps KSP through noiseless channels although matrices $\mathit{PQ}$ and $\mathit{QP}$ can be different.

It was claimed in [11] that EVSkey Scheme is secure against interception of key bits by eavesdropper E. Let us show that, in fact, such KSP is insecure because eavesdropper E is able to intercept the key bits if she intercepts simultaneously the following signals:

$$\begin{array}{c}{\stackrel{\sim }{Y}}_{A_1}=H_{\mathit{BE}}{G}_B{X}_B,{\stackrel{\sim }{Y}}_{A_2}=H_{\mathit{BE}}{G}_B{H}_{\mathit{AB}}{G}_A{X}_A,\\ {\stackrel{\sim }{Y}}_{B_1}=H_{\mathit{AE}}{G}_A{X}_A,{\stackrel{\sim }{Y}}_{B_2}=H_{\mathit{AE}}{G}_A{H}_{\mathit{BA}}{G}_B{X}_B,\end{array}$$E31

where $H_{\mathit{AE}},H_{\mathit{BE}}$ denote E’s channel matrices and under the condition that all E’s noises are equal to zero.

Statement 1. For random matrices described above, say $Y$, the inverse matrix ${\left(Y\right)}^{-1}$ and, in the general case of rectangular matrices, the Moore-Penrose pseudoinverse ${\left(Y\right)}_P^{-1}$ matrix [13] does exist with probability one.

Proof. Indeed let $H$ be $n\times n$ complex random matrix with i.i.d. elements which are $\mathit{CN}\left(0,1\right)$. Then its joint element density is [15]:

$$f\left(H\right)={\left(2\pi \right)}^{-n^2}exp\left(-\frac{1}{2}\mathit{Tr}\left(H{H}^T\right)\right),$$

where $\mathit{Tr}\left(·\right)$ is matrix trace. Degenerate matrices ($detH=0$) form $2n^2-2$ dimension manifold. $f\left(H\right)$, being non-singular, entails zero probability for $H$ to hit any manifold of lower than $2n^2$ dimension. Thus, probability of $detH\ne 0$ equals one. Such matrices stay invertible being multiplied by unitary matrices $G,X$. □

Statement 2. Let $\mathit{EV}\left(Y\right)$ denote the set of matrix $Y$ eigenvalues. Then

$$\mathit{EV}\left(Y\right)=\mathit{EV}\left(\mathit{PQ}\right)=\mathit{EV}\left(\mathit{QP}\right),$$

where

$$Y={\stackrel{\sim }{Y}}_{A_2}{\left({\stackrel{\sim }{Y}}_{B_1}\right)}^{-1}{\stackrel{\sim }{Y}}_{B_2}{\left({\stackrel{\sim }{Y}}_{A_1}\right)}^{-1}.$$E32

Proof. Substituting (31) into (32), we get:

$$Y=H_{\mathit{BE}}{G}_B{H}_{\mathit{AB}}{G}_A{H}_{\mathit{BA}}{G}_B{\left(H_{\mathit{BE}}{G}_B\right)}^{-1}=\left(H_{\mathit{BE}}{G}_B\right)\mathit{QP}{\left(H_{\mathit{BE}}{G}_B\right)}^{-1}$$

The last relation means that matrix Y is similar to matrix $\mathit{QP}$ and thus $\mathit{EV}\left(Y\right)=\mathit{EV}\left(\mathit{QP}\right)$ for any matrices $H_{\mathit{AE}},H_{\mathit{BE}}$.□

The statement 2 has been proved for the case of noiseless E’s channels. But our simulation shows that even for noisy channels, if Eva be following to algorithm (32), she extracts the key bits with BER very close to those that have legitimate users. This fact proves finally that EVSkey Scheme is in fact insecure and hence cannot be recommended for practical application. However the general idea to use KSP with matrix exchange over the channels and extraction of key bits after a quantization of eigenvalues is possible if protocol be elaborated in the desired directions. Such KSP is presented in the next Section.

5. Novel key sharing protocol for public constant noiseless channels and without any cryptographic assumptions

Let us introduce novel KSP designed for its use in constant, public and noiseless communication channels. This protocol has the following distinctions in comparison with other KSP’s:

• it executes over public, constant parameter, noiseless channels (like internet),

• no cryptographic assumptions are needed in order to provide its security and quantum computers cannot break it,

• this KSP provides tradeoff between key reliability and security for given size of key strings,

• security of protocol is estimated in terms of Shannon information leaking to eavesdropper,

• a good key bits statistics can be provided due to their generation by hardware devices,

• the size of traffic for execution of protocol is acceptable for ordinary users,

• the number of protocol steps is minimized and equal to 2.

In Figure 4 it is presented KSP protocol for execution in public constant noiseless channels that we call KSP-PCN. Here $G$ and $P$ are $n\times n$ random matrices generating A and B in advance as well as $n\times n$ matrices of artificial noises $N_{A_1},N_{B_1}$. We believe that all matrix elements are independent of each and Gaussian distributed.

Figure 4.

Two-step KSP-PCN protocol.

At first step, these matrices are transmitted over constant public noiseless channel to opposite party. Next, each of users A and B calculates ${\stackrel{\sim }{K}}_A$ and ${\stackrel{\sim }{K}}_B$ that are noisy version of matrices GP, $\mathit{PG}$, respectively, and extract eigenvalues from these matrices. After a quantization procedure of eigenvalues A and B obtain “raw bits” of the shared key ${\stackrel{\sim }{\stackrel{\sim }{K}}}_A$ and ${\stackrel{\sim }{\stackrel{\sim }{K}}}_B$, respectively. Eavesdropper E intercepts signals $G+N_A$, $G+N_B$. It extracts eigenvalues from the matrix product $\left(G+N_A\right)\left(G+N_B\right)$ and subsequently quantizes them to get eavesdropper’s “raw key” $K_E$. Simulation of KSP shows that the of key bit error probabilities for legitimate users $P_l$ occur very close to that ones $P_e$ of eavesdropper. Hence we need such additional protocol that be able to “diverse” these probabilities. Such protocol that was called Preference Improvement of the Main Channel (PIMC) works as follows: user A (or B) repeats $S$ times each “raw bit”, while opposite user accepts such $S$-blocks if, and only if, they consist of the same $S$ bits (zeros or ones),otherwise opposite user inform initiator of protocol about inadequate receiving blocks. Supposing that bit errors are independent, one from another, PIMC protocol provides the following BER between A and B:

$${\stackrel{\sim }{P}}_l=\frac{P_l^S}{{\left(1-P_l\right)}^S+P_l^S}$$E33

At the same time eavesdropper E also intercepts $S$-blocks with BER $P_e$ and controls public channel over that was transmitting information regarding acceptance or rejection of $S$-blocks between legitimate users. E takes decisions about each $S$-block using majority rule. If E’s channel is believed statistically independent on the legitimate channel, then the BER after such decision will be (for odd number $S$):

$${\stackrel{\sim }{P}}_e=\sum _{i=\frac{S+1}{2}}\left(\begin{array}{c}S\\ i\end{array}\right)P_e^i{\left(1-P_e\right)}^{S-i}$$E34

In order to provide a repetition of bit’s blocks and to improve key bit statistics, it was proposed to use the scheme of key bit generation shown in Figure 5.

Figure 5.

Additional key-transformed protocol.

We can see from Figure 5 that user B generates truly random binary string$\gamma$ that is XOR-ed with B’s raw bit string ${\stackrel{\sim }{\stackrel{\sim }{K}}}_B$ and the sum is transmitted over public noiseless channel to user A who adds this string with raw bits string ${\stackrel{\sim }{\stackrel{\sim }{K}}}_A$ in order to get:

$$K_A={\stackrel{\sim }{\stackrel{\sim }{K}}}_B\oplus \gamma \oplus {\stackrel{\sim }{\stackrel{\sim }{K}}}_A={\stackrel{\sim }{\stackrel{\sim }{K}}}_A\oplus {\epsilon }_{\mathit{AB}}\oplus {\stackrel{\sim }{\stackrel{\sim }{K}}}_A\oplus \gamma =\gamma \oplus {\epsilon }_{\mathit{AB}},$$E35

where ${\epsilon }_{\mathit{AB}}$ is noise string between raw strings ${\stackrel{\sim }{\stackrel{\sim }{K}}}_A$ and ${\stackrel{\sim }{\stackrel{\sim }{K}}}_B$, “$\oplus$” is operation of bitwise modulo two addition. In such version only one user has to repeat $S$ times each bit of $\gamma$ in order to perform PIMC protocol. From now on a string $\gamma$ will be considered as a final key bit string between A and B. At the same time E receives ${\stackrel{\sim }{\stackrel{\sim }{K}}}_B\oplus \gamma$ over public noiseless channel and possessing her string ${\stackrel{\sim }{\stackrel{\sim }{K}}}_E$ be able to add her intercepted bit string $K_E$ as follows:

$$K_E={\stackrel{\sim }{\stackrel{\sim }{K}}}_E\oplus \gamma \oplus {\stackrel{\sim }{\stackrel{\sim }{K}}}_B={\stackrel{\sim }{\stackrel{\sim }{K}}}_B\oplus {\epsilon }_{\mathit{BE}}\oplus \gamma \oplus {\stackrel{\sim }{\stackrel{\sim }{K}}}_B=\gamma \oplus {\epsilon }_{\mathit{BE}},$$E36

where ${\epsilon }_{\mathit{BE}}$ is noise string between raw string ${\stackrel{\sim }{\stackrel{\sim }{K}}}_E$ and ${\stackrel{\sim }{\stackrel{\sim }{K}}}_B$. In order to optimize KSP with point of reliability, security and key string size, it is necessary to select the following parameters:

• sizes of matrices $n$,

• number of bit repetitions $S$,

• variances of additive artificial noises ${\sigma }^2$.

It is worth to note that in the proposed KSP (see Figure 4), unlike the earlier presented protocols (see [5]), all parameters are under the control of legitimate users. This means that we can take for granted reliability and security of the shared key string as well as its size regardless of properties of eavesdropper’s channel.

Although the formulas (33) and (34) of BER for both legitimate users and eavesdropper have been already proved they have to be specified by simulation because our assumption regarding statistical independence of errors is valid only partly. In Tables 7–9 are presented the results of simulation for BER’s ${\stackrel{\sim }{P}}_l$ and ${\stackrel{\sim }{P}}_e$ for given parameters ${\sigma }^2$, the matrix sizes $n$ and parameter $S$. (They were chosen, of course, from a huge simulation results which have been removed simply as unsuitable.)

s	${\sigma }^2$
	0.1	0.2	0.3	0.4
1	0.296	0.343	0.37	0.387	${\stackrel{\sim }{P}}_l$
	0.222	0.269	0.299	0.316	${\stackrel{\sim }{P}}_e$
3	0.0523	0.0703	0.0974	0.113	${\stackrel{\sim }{P}}_l$
	0.0407	0.0643	0.0863	0.103	${\stackrel{\sim }{P}}_e$
5	0.00727	0.0122	0.0174	0.0224	${\stackrel{\sim }{P}}_l$
	0.00638	0.0125	0.0189	0.0268	${\stackrel{\sim }{P}}_e$
7	0.00124	0.00209	0.0039	0.00673	${\stackrel{\sim }{P}}_l$
	0.00133	0.00332	0.00571	0.0119	${\stackrel{\sim }{P}}_e$

Table 7.

The results of simulation for BER ${\stackrel{\sim }{P}}_l$ and ${\stackrel{\sim }{P}}_e$ for matrix size $n=1$ (integers instead of matrices), given different noise variances ${\sigma }^2$ and the number of repetitions $S$.

s	${\sigma }^2$
	0.1	0.2	0.3	0.4
1	0.26	0.294	0.309	0.317	${\stackrel{\sim }{P}}_l$
	0.212	0.252	0.271	0.279	${\stackrel{\sim }{P}}_e$
3	0.031	0.0428	0.0477	0.051	${\stackrel{\sim }{P}}_l$
	0.0333	0.0427	0.0562	0.0604	${\stackrel{\sim }{P}}_e$
5	0.00293	0.00443	0.0048	0.00535	${\stackrel{\sim }{P}}_l$
	0.00528	0.00822	0.0106	0.0118	${\stackrel{\sim }{P}}_e$
7	0.000182	0.000464	0.00061	0.000644	${\stackrel{\sim }{P}}_l$
	0.00108	0.000195	0.000308	0.00358	${\stackrel{\sim }{P}}_e$

Table 8.

The results of simulation for BER ${\stackrel{\sim }{P}}_l$ and ${\stackrel{\sim }{P}}_e$ for matrix size $n=4$ given different noise variances ${\sigma }^2$ and the number of repetitions $S$.

s	${\mathrm{\sigma }}^2$
	0.1	0.2	0.3	0.4
1	0.0816	0.0851	0.0859	0.0963	${\stackrel{\sim }{P}}_l$
	0.0922	0.117	0.140	0.154	${\stackrel{\sim }{P}}_e$
3	0.00362	0.00402	0.00407	0.00396	${\stackrel{\sim }{P}}_l$
	0.0185	0.0439	0.0673	0.0822	${\stackrel{\sim }{P}}_e$
5	0.000193	0.000294	0.000258	0.000226	${\stackrel{\sim }{P}}_l$
	0.00875	0.0314	0.053	0.0699	${\stackrel{\sim }{P}}_e$
7	1.44∙10^−5	3∙10^−5	1.79∙10^−5	1.68∙10^−5	${\stackrel{\sim }{P}}_l$
	0.00529	0.0256	0.0455	0.059	${\stackrel{\sim }{P}}_e$

Table 9.

The results of simulation for BER ${\stackrel{\sim }{P}}_l$ and ${\stackrel{\sim }{P}}_e$ for matrix size $n=64$ given different noise variances ${\sigma }^2$ and the number of repetitions $S$.

We can see from these Tables that a choice of matrix size $n=1$ (i.e. replacing matrices with integer numbers) is inadmissible because the probabilities ${\stackrel{\sim }{P}}_l$ and ${\stackrel{\sim }{P}}_e$ occur close to one another for all parameters $S$ and ${\sigma }^2$. The choice of matrix size $n=4$ also cannot be recommended because it is inferior to the case with $n=64$. In the last case we can see the most large difference of the BER’s ${\stackrel{\sim }{P}}_l$ and ${\stackrel{\sim }{P}}_e$ for some parameters $S$ and ${\sigma }^2$. But unfortunately the BER ${\stackrel{\sim }{P}}_l$ and ${\stackrel{\sim }{P}}_e$ cannot be chosen as final results.

In fact, the probability ${\stackrel{\sim }{P}}_l$ has to be decreased in order to provide an acceptable reliability of the shared key with the key length at least 256 bits. The probability ${\stackrel{\sim }{P}}_e$ is quite unacceptable because it results in a large leakage of the key information to the eavesdropper E.

Therefore, it is necessary first of all to correct errors in legitimate channel, suppose, using error correcting codes and next to amplify security of the shared bit string against eavesdropping. Let us apply so called enhance of privacy amplification procedure described in [16]. We recall that privacy amplification procedure can be performed in two stages: firstly with the use of hashing by hash function taken randomly from universal₂ class, and secondly, by special “puncturing” of the hashed string [16]. Then the upper bound for Shannon’s information $I$ leaking to eavesdropper be given by the following [16]:

$$I\le \frac{2^{-\left(k-t_c-l_0-r\right)}}{\alpha ln2},$$E37

where $k$ is the string, generated by A and B after a completion of PIMC protocol, $t_c$ is the Renyi (or collision) information obtained by E via eavesdropper BSC channel with BER ${\stackrel{\sim }{P}}_e$, $r$ is the number of check bits sent by one of legitimate users to another one in order to reconcile their key strings finally, $l_0$ is the length of the final key string, $\alpha$ is a coefficient that approaches to 0.42 for any fixed $r$ as $k$ and $k-r$ are increasing. It has been proved in [17] that in order to satisfy Shannon’s theorem about reliable communication over noisy channel and provide an exponential decreasing of information leaking to eavesdropper E, minimum sum $k_0+r_0$ is provided with:

$$r_0=H_L\frac{\lambda +l_0}{C{H}_C-H_L},k_0=C\frac{\lambda +l_0}{C{H}_C-H_L},$$E38

where

$$H_L=1-C=-{\stackrel{\sim }{P}}_l{log}_2{\stackrel{\sim }{P}}_l-\left(1-{\stackrel{\sim }{P}}_l\right){log}_2\left(1-{\stackrel{\sim }{P}}_l\right),$$

$$H_C=-{log}_2\left({\stackrel{\sim }{P}}_e^2+{\left(1-{\stackrel{\sim }{P}}_e\right)}^2\right),$$

$$C=1+{\stackrel{\sim }{P}}_l{log}_2{\stackrel{\sim }{P}}_l+\left(1-{\stackrel{\sim }{P}}_l\right){log}_2\left(1-{\stackrel{\sim }{P}}_l\right),$$

$$\lambda =k-t_c-l_0-r,$$

$$t_c=k-k{H}_C.$$

Let us adopt the following parameters from Table 9: $n=64,S=5,{\sigma }^2=0.4,{\stackrel{\sim }{P}}_l=0.00022,{\stackrel{\sim }{P}}_e=0.0699.$ After a simulation of LDPC decoding procedure in line with [18] we select LDPC code with parameters $k=24039,r=961,$ that provides for the final key length $l_0=3659$ the block error probability after decoding $P_{\mathit{ed}}\approx 2.5·{10}^{-3}$ and information leakage $I_0\approx 9·{10}^{-4}$ bits. If we select LDPC code with parameters $k=50001,r=1999,$ we get for final key length $l_0=7624$ the error probability after error correction $P_{\mathit{ed}}=8·{10}^{-4}$ and information leakage $I=1.4·{10}^{-3}$ bits. In the paper [17] has been proved the formula for amount of the traffic bytes that is needed in order to perform KSP described above:

$$\mathit{\text{Traffic}}=\mathit{Tr}=2.66·{10}^{-6}\frac{\mathit{Skn}}{{\left({\left(1-P_l\right)}^S+P_l^S\right)}^2}\text{MB}$$E39

Substituting the corresponding parameters chosen for KSP, we get that $\mathit{Tr}\approx 32$ MB that is acceptable for practical implementation.

As it can be seen from a description of proposed KSP, the generators of random numbers are needed for its implementation. Moreover it is impossible to use standard program-oriented generator (like MT19937) because it can be vulnerable to sequence prediction attack. Thus it is necessary to use hardware generator of random numbers. We propose to take such generator as Crypton USB-DRN that is manufactured by company “Ankad” [19]. Photo of this device is shown in Figure 6. We tested this device on standard NIST tests and concluded that it passes all of them except two last ones from the list of 15-ary NIST tests. Experiment showed that it is required at most about 20 minutes in order to generate key string according to this KSP.

Figure 6.

View of random number generator Crypton USB-DRN.

For our KSP is required (as for any such protocol) to perform authentication procedure—otherwise the adversary could impersonate legitimate users and eventually share with them a common key. It is possible to use different authentication methods: short key, the Needham-Schroder protocol [20] or pairing procedure during the face to face device meeting [21].

6. Conclusion

In the current chapter we have presented four different systems related with keyless cryptography. The first two of them consider such systems that do not require any key distribution in advance. The first one is based on protocol with feedback that uses public key cryptosystems but it does not require any key distribution in advance, even public one. It executes commutative cryptography but, unfortunately, it is a poor choice. It would be very interesting to find at least one of symmetric strong block cipher or post-quantum public cryptosystems that belong to commutative ones (or may be to prove that such cryptosystem does not exist at all). The second example in our “gallery” of keyless cryptography was Dean-Goldsmith one. It is based on physical layer properties and has unquestionable theoretical interest. But unfortunately it is impractical because requires from eavesdroppers unrealistic conditions. The third example is related with key sharing without some short subkeys sharing in advance. Unfortunately authors’ claiming that such system is secure, occurs wrong. But their scheme can be significantly modified (see version four) to be in fact secure. According to our opinion, the fourth key sharing protocol is the first attempt to distribute keys by secret manner executing over such very popular channel as internet (or over any other public and noiseless channel). It provides easy way for a confidential communication between ordinary internet users. In the future it will be interesting to investigate exchange by integers (but not matrices) that results in, for sure, to a decreasing of channel traffic. Elaboration of reliable authentication system is also interesting both for theory and practice.