Open access peer-reviewed chapter - ONLINE FIRST

Advance in Keyless Cryptography

Written By

Valery Korzhik, Vladimir Starostin, Victor Yakovlev, Muaed Kabardov, Andrej Krasov and Sergey Adadurov

Submitted: February 11th, 2022Reviewed: March 9th, 2022Published: April 24th, 2022

DOI: 10.5772/intechopen.104429

IntechOpen
Cryptography - Modern Theory and PracticesEdited by Srinivasan Ramakrishnan

From the Edited Volume

Cryptography - Modern Theory and Practices [Working Title]

Dr. Srinivasan Ramakrishnan

Chapter metrics overview

5 Chapter Downloads

View Full Metrics

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.

Keywords

  • keyless cryptography
  • protocols
  • public cryptosystems
  • MIMO technology
  • 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.

Advertisement

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:

fKAfKBM=fKBfKAM,E1

where fKAKBMis encryption algorithm using the keys KAand KB, respectively and Mis any message. If relation (1) is true for some encryption algorithm fKAKBMthen can be performed protocol presented in Figure 1.

Figure 1.

Protocol based on relation(1)wherefKA1·is decryption algorithm given the keyKA.

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

CA=fKA1CB=fKA1fKBfKAM=fKA1fKAfKBM=fKBME2

On the next step user B decrypts fKBMby the algorithm fKB1·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=pqmodulo, φ=p1q1, e—encryption key, 1eφ, d—decryption key, d=e1modφ, gcdeφ=1, 1Mn1—integers. Encryption algorithm for RSA is E=Memodn; decryption algorithm is M=Edmodn. Then for RSA condition (1) takes the form:

MeAmodneBmodn=MeBmodneAmodnE3

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

MeAmodneBmodn=MeAeBmodn=MeBmodneAmodn=MeBeAmodn.

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

Example. Let p=3, q=5, M=2, eA=3, eB=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,qare distinct primes (secret key), nAB=pqmodulois public key. 0Mn1, E=M2modn. Then relation (1) takes the form:

M2modnA2modnB=M2modnB2modnAE4

It is easy to make sure that (4) is not satisfied, generally speaking. In fact, let us consider an example: pA=3, qA=5, nA=15, pB=11, qB=7, nB=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:

M2modnA2modnB=M2nAl2modnB==M42M2nAl+nA2l2modnB,E5

where lis some integer.

M2modnB2modnA=M2nBm2modnA==M42M2nBm+nB2m2modnA,E6

where mis some integer too. We can see that in general case nAnBthe 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×nmatrix GAB=SABGABPAB—public key where SABis nonsingular random k×kmatrix, PABis permutation random n×nmatrix, GABis random Goppa code generating matrix. Matrices SAB, GAB, PABare believed as secret key jointly with a binary random vector ZABof the known length n, and with given weight tAB. Encryption procedure is performed as follows:

EAB=MGABZAB,E7

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

fKAfKBM=MGBZBGAZA=MGBGAZBGAZAE8
fKBfKAM=MGAZAGBZB=MGAGBZAGBZBE9

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 ZAand ZB. 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:

EMK=MγK,E10

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

MγKAγKB=MγKBγKAE11

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 CBand CAbe able to bitwise add them by modulo 2 that gives the following binary sequence: MγKBγKBMγKA=γKA. Next, attacker add bitwise modulo 2 the last sequence γKAwith the sequence CAintercepted during the first transmission session that gives MγKAγKA=Mthat is exactly the desired open sequence M. (It is worth to note that similar conclusion was mentioned in [6].)

Advertisement

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 nrand eavesdropper antennas nrare equal to each other. (Later we consider more general case nrnr).

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

z=Ay+e,E12

where zRnis vector received by B, yRnis vector transmitted by A, eRnis additive noise vector at the receiver B, ARn×nis legitimate channel matrix. It is assumed that eare i.i.d. Gaussianvectors: N0σe2. A=aij,i=1nj=1nare also matrices with i.i.d. Gaussian matrix elements: N0σ2. For Eavesdropper channel from A to E (Eve) holds the equation:

z=By+e,E13

where zRnis vector received by E, eRnis additive noise vector at the receiver E, BRn×neavesdropper channel matrix. It is assumed that eare also i.i.d. vectors based on Gaussian distribution N0σe2, B=bij, i=1,,n,j=1,,nwith bijwhich are i.i.d. Gaussian values N0σw2. All entries of matrices Aand Bare assumed to be mutually independent. Next three conditions are very important for further discussion:

  • channel matrices Aand Bare constant for some time until user A applies encoder,

  • matrix Ais known exactly by legitimate users,

  • matrices Aand Bare 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 technologyif space distance between legitimate users and eavesdropper is at least several wavelengths of communication. Encoding procedure in line with [12] is the following:

y=Vx,E14

where VRn×nis orthogonal matrix taken from singular value decomposition(SVD) of matrix A=USVT, xRnwith binary entries xi, i=1,,n. Predecoding procedure in line with [12] is the following:

z=UTz=UTAy+e=UTUSVTVx+UTe=Sx+e,E15

where URn×nis orthogonal matrix taken from SVD of matrix A, e=UTe. Since Sis diagonal matrix, we get from (15) the following optimal decoding rule:

x=argminxizixisi,i=1,,n,E16

where siis i-th element of diagonal matrix S, xiare 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=UTz,E17

where

z=BVx+e=USVTVx+e,E18

where U, V, Sare SVD of matrix B. Substituting (18) into (17), we get:

z=Cx+e,E19

where C=SVTV, e=UTe. Since matrix C is not a diagonal one in this case, their optimal decoding be the following:

x=argminzCx,E20

where·is Euclidian norm in Rn. Solution of problem (20) is known as hard CVP problemand it was proved in [12] that it has exponential complexity with respect to the number of antennas nif the following condition holds:

σw2σe2>n1/2

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

C1z=x+C1e

Thus suboptimal decoding method can be implemented as follows:

xi=argminzixi,i=1,,n,E21

where ziis the i-th entry of vector C1z.

We can see from (21) that complexity of suboptimal decoding procedure is linear on the number nof 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 pand p, respectively.

NoSystem parametersnSymbol error probability for legitimate users (p)Symbol error probabilities for Eavesdropper (p)
1σ2=σw2=2,σe2=σe2=11000.020.2
2σ2=σw2=4,σe2=σe2=81000.0370.3
3σ2=σw2=1,σe2=σe2=301000.020.42
4σ2=2,σw2=1,σe2=σe2=410005.6×1030.3
5σ2=4,σw2=8,σe2=σe2=1210000.010.33

Table 1.

The results of simulation for BER pand pwith 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 p0.3does 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 capacityof such channel, if every letter is encoded by five bits with BER equal to p, is:

C=5+1p5log21p5+5p1p4log2p1p4++10p21p3log2p21p3+10p31p2log2p31p2++5p41plog2p41p+p5log2p5E22

In Table 2 are presented the values of channel capacity calculated by (22) for different values p.

p’0.10.110.150.180.19
C2.652.51.951.61.5
p’0.20.250.30.350.4
C1.390.940.590.330.15
p’0.410.420.430.440.45
C0.120.0930.0710.0520.036
p’0.460.470.480.490.5
C0.0230.0130.00580.00140

Table 2.

The values of channel capacity Cfor different p.

It is well known that entropy Hof Russian language lies within interval 1.5÷2.5bit/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>0.19such 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.19and 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 nr=nrand the more nr<nr. But the following question arises—if such conclusion is true for the case nr>nr? In Table 3 are presented the results of simulation BER’s pfor eavesdropper by suboptimal decoding rule (21) in the case of typical parameters σ2=σw2=4, σe2=σe2=7, nr=100and different nr, where inverse matrix C1for rectangular nr×nrmatrix Cwas calculated as Moore-Penrose pseudo-inverse matrixto C14.

nr100101102103105107
p0.310.220.160.120.070.048
nr108109110120150
p0.0390.030.0240.0037×104

Table 3.

Results of BER psimulation for decision rule (21), nr=100and different nrnr.

We can see from Table 3 that even small increasing of nr(on 9 antennas) compared to nr, results in a drastic degradation of DGC because the symbol error probability pbecomes for eavesdropper very close to the probability pfor 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 xi01is equivalent to the following relation:

xi=0ifziSi/2,1ifzi>Si/2.

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

Pxi=xiPei<Si/2,E23

where eiis the i-th entry of additive noise vector ein (12). Because we assumed before that eiN0σe2we get from (23):

Pxi=xi2ΦSi2σeE24

where Φa=12π0aexpt22dt. The decision rule (21) for eavesdropper will be equivalent to the following one:

xi=0ifzi1/2,1ifzi>1/2.E25

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

Pxi=xiPei12=2Φ12Varei,E26

where eiis the i-th entry of additive noise vector e=C1e. In order to find Vareilet us accomplish some matrix transforms:

C=BV=USVV,
C1=VTVS1UT,
e=C1e=VTVS1UT.E27

Taking into account that Uis orthogonal matrix and Sis diagonal one, we get from (27):

Varei=σe2k=1nrVik2Sk2E28

where Vikare elements of matrix VTVand Skelements of matrix S. Substituting (28) into (27) we obtain

Pxi=xi2Φ12σek=1nrVik2Sk2E29

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 Sk, and also on elements of channel matrices VTV. 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) with channel parameters: σ2=σw2=7, σe2=σe2=4, nt=nr=100against different numbers nrfor eavesdropper antennas.

nr100101102103104105
q0.950.950.950.950.950.95
q0.710.750.80.870.90.95
nr106107108109110
q0.950.950.950.950.95
q0.960.970.980.9850.99

Table 4.

The symbol correct probabilities obtained by simulation of averaged bounds for q(24) and for q(29).

We can see from this Table that an increasing of the eavesdropper’s antennas even till nr=105results in equality of values qand qthat 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 nrnrholds. In the paper [14] it was proposed to change matrix Vin “precoding” procedure to another matrix. In particular, authors of the current paper have proved that a choice of matrix A1as precoding one has some advantages, namely a growth of some parameter “advantage” (introduced in [14]) for legitimate users proportional to n2if n=nt=nr=nr. 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 A1, and obtained by simulation for n=nt=nr=nr=100on different sessions with 10,000 realizations for each session.

Session numbers12345
P04.5×1051.8×1079.1×1052.1×1068.8×104
Session numbers678910
P05.9×1053.4×1045.2×1042.5×1051.08×105

Table 5.

Average transmitter power P0with precoding matrix A1for different sessions.

We can see from Table 5 that the use of inverse precodingresults 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 n2=104only for ordinary encoding by matrix V). It seems to be acceptable to use for a precoding V=A1only in the case with the required transmitter power P0Ptrwhere Ptris some reasonable threshold and ordinary matrix Votherwise. 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 Aby 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 Aholds practically constant. But any way it will result in some matrix Acorruption. In Table 6 are given our simulation results for symbol error probabilities that obtain legitimate users if they estimate elements of the channel matrix Awith Gaussian noise error having variance σε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.

σ2σe2σε2
10.10.010.0010
230.16770.05870.02710.02080.02
380.13320.0530.03830.03780.037
5040.03640.01260.00930.00880.0084

Table 6.

Results of symbol error probabilities for legitimate users under the incorrect estimation of channel elements with variance σε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.

Advertisement

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 Schemeand 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 XA,XBn×nas well as random Ginibre matrices GA,GBn×n, where nis the number of antennas employed by each of the users, and length of pilot signals too. Matrices HAB,HBAare n×nchannel matrices with independent Gaussian matrix elements distributed according to hAB,hBACN01. NA1,NB1are additive white Gaussian noise (AWGN) matrices nA1ij,nB1ijCN0σ2of proper noises for legitimate users A and B, respectively.

Figure 3.

The KSP corresponding to EVSkey scheme.

Let us introduce the following matrices: P=HBAGB,Q=HABGA. Then PQand QPcan be estimated by users via least square method as

PQYA2XA1,QPYB2XB1

It is well known [13] that square matrices of the same size PQand QPhave the same characteristic polynomials (CP):

CPPQ=CPQPE30

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 PQand QPcan 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:

YA1=HBEGBXB,YA2=HBEGBHABGAXA,YB1=HAEGAXA,YB2=HAEGAHBAGBXB,E31

where HAE,HBEdenote 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 Y1and, in the general case of rectangular matrices, the Moore-Penrose pseudoinverse YP1matrix [13] does exist with probability one.

Proof.Indeed let Hbe n×ncomplex random matrix with i.i.d. elements which are CN01. Then its joint element density is [15]:

fH=2πn2exp12TrHHT,

where Tr·is matrix trace. Degenerate matrices (detH=0) form 2n22dimension manifold. fH, being non-singular, entails zero probability for Hto hit any manifold of lower than 2n2dimension. Thus, probability of detH0equals one. Such matrices stay invertible being multiplied by unitary matrices G,X. □

Statement 2. Let EVYdenote the set of matrix Yeigenvalues. Then

EVY=EVPQ=EVQP,

where

Y=YA2YB11YB2YA11.E32

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

Y=HBEGBHABGAHBAGBHBEGB1=HBEGBQPHBEGB1

The last relation means that matrix Y is similarto matrix QPand thus EVY=EVQPfor any matrices HAE,HBE.□

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.

Advertisement

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 Gand Pare n×nrandom matrices generating A and B in advance as well as n×nmatrices of artificial noises NA1,NB1. 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 KAand KBthat are noisy version of matrices GP, PG, respectively, and extract eigenvalues from these matrices. After a quantization procedure of eigenvalues A and B obtain “raw bits” of the shared key KAand KB, respectively. Eavesdropper E intercepts signals G+NA, G+NB. It extracts eigenvalues from the matrix product G+NAG+NBand subsequently quantizes them to get eavesdropper’s “raw key” KE. Simulation of KSP shows that the of key bit error probabilities for legitimate users Ploccur very close to that ones Peof 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 Stimes each “raw bit”, while opposite user accepts such S-blocks if, and only if, they consist of the same Sbits (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:

Pl=PlS1PlS+PlSE33

At the same time eavesdropper E also intercepts S-blocks with BER Peand 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):

Pe=i=S+12SiPei1PeSiE34

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γthat is XOR-ed with B’s raw bit string KBand the sum is transmitted over public noiseless channel to user A who adds this string with raw bits string KAin order to get:

KA=KBγKA=KAεABKAγ=γεAB,E35

where εABis noise string between raw strings KAand KB, “” is operation of bitwise modulo two addition. In such version only one user has to repeat Stimes each bit of γin order to perform PIMC protocol. From now on a string γwill be considered as a final key bit string between A and B. At the same time E receives KBγover public noiseless channel and possessing her string KEbe able to add her intercepted bit string KEas follows:

KE=KEγKB=KBεBEγKB=γεBE,E36

where εBEis noise string between raw string KEand KB. 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 σ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 79 are presented the results of simulation for BER’s Pland Pefor given parameters σ2, the matrix sizes nand parameter S. (They were chosen, of course, from a huge simulation results which have been removed simply as unsuitable.)

sσ2
0.10.20.30.4
10.2960.3430.370.387Pl
0.2220.2690.2990.316Pe
30.05230.07030.09740.113Pl
0.04070.06430.08630.103Pe
50.007270.01220.01740.0224Pl
0.006380.01250.01890.0268Pe
70.001240.002090.00390.00673Pl
0.001330.003320.005710.0119Pe

Table 7.

The results of simulation for BER Pland Pefor matrix size n=1(integers instead of matrices), given different noise variances σ2and the number of repetitions S.

sσ2
0.10.20.30.4
10.260.2940.3090.317Pl
0.2120.2520.2710.279Pe
30.0310.04280.04770.051Pl
0.03330.04270.05620.0604Pe
50.002930.004430.00480.00535Pl
0.005280.008220.01060.0118Pe
70.0001820.0004640.000610.000644Pl
0.001080.0001950.0003080.00358Pe

Table 8.

The results of simulation for BER Pland Pefor matrix size n=4given different noise variances σ2and the number of repetitions S.

sσ2
0.10.20.30.4
10.08160.08510.08590.0963Pl
0.09220.1170.1400.154Pe
30.003620.004020.004070.00396Pl
0.01850.04390.06730.0822Pe
50.0001930.0002940.0002580.000226Pl
0.008750.03140.0530.0699Pe
71.44∙10−53∙10−51.79∙10−51.68∙10−5Pl
0.005290.02560.04550.059Pe

Table 9.

The results of simulation for BER Pland Pefor matrix size n=64given different noise variances σ2and 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 Pland Peoccur close to one another for all parameters Sand σ2. The choice of matrix size n=4also 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 Pland Pefor some parameters Sand σ2. But unfortunately the BER Pland Pecannot be chosen as final results.

In fact, the probability Plhas to be decreased in order to provide an acceptable reliability of the shared key with the key length at least 256 bits. The probability Peis 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 amplificationprocedure can be performed in two stages: firstly with the use of hashing by hash function taken randomly from universal2 class, and secondly, by special “puncturing” of the hashed string [16]. Then the upper bound for Shannon’s information Ileaking to eavesdropper be given by the following [16]:

I2ktcl0rαln2,E37

where kis the string, generated by A and B after a completion of PIMC protocol, tcis the Renyi (or collision) information obtained by E via eavesdropper BSC channel with BER Pe, ris the number of check bits sent by one of legitimate users to another one in order to reconcile their key strings finally, l0is the length of the final key string, αis a coefficient that approaches to 0.42 for any fixed ras kand krare 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 k0+r0is provided with:

r0=HLλ+l0CHCHL,k0=Cλ+l0CHCHL,E38

where

HL=1C=Pllog2Pl1Pllog21Pl,
HC=log2Pe2+1Pe2,
C=1+Pllog2Pl+1Pllog21Pl,
λ=ktcl0r,
tc=kkHC.

Let us adopt the following parameters from Table 9: n=64,S=5,σ2=0.4,Pl=0.00022,Pe=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 l0=3659the block error probability after decoding Ped2.5·103and information leakage I09·104bits. If we select LDPC code with parameters k=50001,r=1999,we get for final key length l0=7624the error probability after error correction Ped=8·104and information leakage I=1.4·103bits. 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:

Traffic=Tr=2.66·106Skn1PlS+PlS2MBE39

Substituting the corresponding parameters chosen for KSP, we get that Tr32MB 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].

Advertisement

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.

References

  1. 1.Alpern B, Schneider FB. Key exchange using ‘keyless cryptography. Information Processing Letters. 1983;16(2):79-81. DOI: 10.1016/0020-0190(83)90029-7
  2. 2.Korzhik V. Keyless cryptography. In: The 9-th International Conference on System Administration, Networking and Security; Orlando, USA. 2000
  3. 3.Korzhik V, Bakin M. Information-theoretically secure keyless authentication. In: Proceedings of the 2000 IEEE International Symposium on Information Theory; 2000 June 25-30; Sorrento, Italy. Piscataway, NJ (USA): IEEE Press; 2000. Available from: IEEE Xplore. DOI: 10.1109/ISIT.2000.2
  4. 4.Korzhik V. Keyless Cryptography. Invited Talk at Security Seminar at CERIAS Purdue University. 2001. Available from:http://www.cerias.purdue.edu/secsem/abstracts.html#Fall
  5. 5.Mukherjee A, Fakoorian SAA, Huang J, Swindlehurst AL. Principles of physical layer security in multiuser wireless networks: A survey. IEEE Communications Surveys & Tutorials. 2014;16(3):1550-1573. DOI: 10.1109/SURV.2014.012314.00178
  6. 6.Schneier B. Applied Cryptography. Montreal: JW Publ. Inc.; 1994
  7. 7.Menezes AJ, van Oorschot PC, Vanstone SA. Handbook of Applied Cryptography. Boca Raton: CRC Press; 1997. DOI: 10.1201/9780429466335
  8. 8.Shor PW. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science; 1994 November 20–22; Santa Fe, USA. Los Alamitos: IEEE Press; 1994. pp. 124-134. DOI: 10.1109/SFCS.1994
  9. 9.Dyakonov MI. Is fault-tolerant quantum computation really possible? In: Luryi S, Xu J, Zaslavsky A, editors. Future Trends in Microelectronics. Hoboken, NJ, USA: John Wiley & Sons; 2007. pp. 4-18
  10. 10.Bennett CH, Bessette F, Brassard G, Salvail L, Smolin J. Experimental quantum cryptography. Journal of Cryptology. 1992;5:3-28
  11. 11.Qin D, Ding Z. Exploiting multi-antenna non-reciprocal channels for share secret key generation. IEEE Transactions on Information Forensics and Security. 2016;11(10):2691-2705
  12. 12.Dean T, Goldsmith AJ. Physical-layer cryptography through massive MIMO. In: Proceedings of the 2013 IEEE Information Theory Workshop; 2013 September 9-13; Seville, Spain. Piscataway, NJ, USA: IEEE; 2013. pp. 1-5
  13. 13.Ben-Israel A et al. Generalized Inverses: Theory and Applications. NY: Springer; 2003
  14. 14.Steinfeld R, Sakzad A. On massive MIMO physical layer cryptosystem. In: Proceedings of the 2015 IEEE Information Theory Workshop; 2015 October 11-15; Lotte City Hotel Jeju, Jeju Island, Korea. Piscataway, NJ, USA: IEEE; 2015. pp. 292-296. Available from:http://ieeexplore.ieee.org/servlet/opac?punumber=7355548.
  15. 15.Edelman A. Eigenvalues and condition numbers of random matrices PhD thesis: Cambridge, Massachusetts, USA: Massachusetts Institute of Technology; 1989
  16. 16.Korzhik V, Morales-Luna G, Balakirsky V. Privacy amplification theorem for noisy main channel. Lecture Notes in Computer Science. 2001;2200:18-26
  17. 17.Korzhik V, Starostin V, Kabardov M, Gerasimovich A, Yakovlev V, Zhuvikin A. Protocol of key distribution over public noiseless channels executing without cryptographic assumption. International Journal of Computer Science and Application. 2020;17(01):1-14
  18. 18.Fossorier MPC, Mihaljevic M, Imai H. Reduced complexity iterative decoding of low density parity check codes based on belief propagation. IEEE Transactions on Communications. 1999;47(5):673-680
  19. 19.Podorozhnyi IV. КBDZ.469435.052 RE. Obzor apparatnykh generatorov sluchainykh chisel//Molodoy uchenyi (in Russian). Available from:http://moluch.ru/archive/105/24688/[Accessed: June 24, 2020]
  20. 20.Needham RM, Schroeder MD. Using encryption for authentication in large network of computers. Communications of the ACM. 1978;21:993-999
  21. 21.Jin R et al. MagPairing: Pairing smartphones in close proximity using magnetometer. IEEE Transactions on Information Forensics and Security. 2016;6:1304-1319

Written By

Valery Korzhik, Vladimir Starostin, Victor Yakovlev, Muaed Kabardov, Andrej Krasov and Sergey Adadurov

Submitted: February 11th, 2022Reviewed: March 9th, 2022Published: April 24th, 2022