Can Wyner Wiretap Channel Equivocation Region Be Extended to Continuous Alphabets

Abstract

In the Wyner wiretap channel a sender is connected to a receiver and an eavesdropper through two noisy channels. It has been shown that if the noise in the eavesdropper channel is higher than the receiver's channel, information theoretically secure communication from Alice to Bob, without requiring a shared key, is possible. The approach is particularly attractive noting the rise of quantum computers and possibility of the complete collapse of todays' cryptographic infrastructure. If the eavesdropper's channel is noise free however, no secrecy can be obtained. The iJam protocol, proposed by Gollakota and Katabi, is an interactive protocol over noise free channels that uses friendly jamming by the receiver to establish an information theoretically secure shared key between the sender and the receiver. The protocol relies on the Basic iJam Transmission protocol (BiT protocol) that uses properties of OFDM (Orthogonal Frequency-Division Multiplexing) to create uncertainty for Eve (hence noisy view) in receiving the sent information, and use this uncertainty to construct a secure key agreement protocol. The protocol has been implemented and evaluated using extensive experiments that examines the best eavesdropper's reception strategy. In this paper we develop an abstract model for BiT protocol as a wiretap channel and refer to it as a virtual wiretap channel. We estimate parameters of this virtual wiretap channel, derive the secrecy capacity of this channel, and design a secure message transmission protocol with provable semantic security using the channel. Our analysis and protocol gives a physical layer security protocol, with provable security, that is implementable in practice (BiT protocol has already been implemented).

References

1. 802.1x & WPA settings. https://www.ietf.org/mail-archive/web/ietf/current/msg32026.html

2. The secure sockets layer (SSL) protocol version 3.0. https://tools.ietf.org/html/rfc6101

3. SSH protocol architecture. https://www.ietf.org/proceedings/52/I-D/draft-ietf-secsh-architecture-11.txt

4. Bellare, M., Tessaro, S.: Polynomial-time, semantically-secure encryption achieving the secrecy capacity. arXiv preprint arXiv:1201.3160 (2012)

5. Bellare, M., Tessaro, S., Vardy, A.: A cryptographic treatment of the wiretap channel. arXiv preprint arXiv: 1201.2205 (2012)

6. Bellare, M., Tessaro, S., Vardy, A.: Semantic security for the wiretap channel. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 294–311. Springer, Heidelberg (2012). doi:10.1007/978-3-642-32009-5_18

   CrossRef  Google Scholar

7. Bergmans, P.: Random coding theorem for broadcast channels with degraded components. IEEE Trans. Inf. Theory 19(2), 197–207 (1973)

   CrossRef  MathSciNet  Google Scholar

8. Csiszár, I., Körner, J.: Broadcast channels with confidential messages. IEEE Trans. Inf. Theory 24(3), 339–348 (1978)

   CrossRef  MathSciNet  MATH  Google Scholar

9. Dickerson, K.: Microsoft lab predicts we'll have a working 'hybrid' quantum computer in 10 years, October 2015. http://www.techinsider.io/microsoft-hybrid-quantum-computer-2015-10

10. Dodis, Y., Reyzin, L., Smith, A.: Fuzzy extractors: how to generate strong keys from biometrics and other noisy data. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 523–540. Springer, Heidelberg (2004). doi:10.1007/978-3-540-24676-3_31

    CrossRef  Google Scholar

11. Dong, L., Han, Z., Petropulu, A.P., Poor, H.V.: Cooperative jamming for wireless physical layer security. In: 2009 IEEE/SP 15th Workshop on Statistical Signal Processing, pp. 417–420. IEEE (2009)

    Google Scholar

12. Goldsmith, A.: Wireless Communications. Cambridge University Press, Cambridge (2005)

    CrossRef  Google Scholar

13. Gollakota, S., Katabi, D.: Physical layer wireless security made fast and channel independent. In: 2011 Proceedings IEEE INFOCOM, pp. 1125–1133. IEEE (2011)

    Google Scholar

14. Guruswami, V.: Bridging Shannon and Hamming: list error-correction with optimal rate (2010)

    Google Scholar

15. Han, Z., Marina, N., Debbah, M., Hjørungnes, A.: Physical layer security game: interaction between source, eavesdropper, and friendly jammer. EURASIP J. Wirel. Commun. Netw. 2009(1), 1 (2010)

    Google Scholar

16. Karagiannidis, G.K., Lioumpas, A.S.: An improved approximation for the Gaussian Q-function. IEEE Commun. Lett. 11(8) (2007)

    Google Scholar

17. Lai, L., El Gamal, H.: The relay-eavesdropper channel: cooperation for secrecy. IEEE Trans. Inf. Theory 54(9), 4005–4019 (2008)

    CrossRef  MathSciNet  MATH  Google Scholar

18. Leung-Yan-Cheong, S.: On a special class of wiretap channels (Corresp.). IEEE Trans. Inf. Theory 23(5), 625–627 (1977)

    CrossRef  MathSciNet  MATH  Google Scholar

19. Leung-Yan-Cheong, S., Hellman, M.: The Gaussian wire-tap channel. IEEE Trans. Inf. Theory 24(4), 451–456 (1978)

    CrossRef  MathSciNet  MATH  Google Scholar

20. Mahdavifar, H., Vardy, A.: Achieving the secrecy capacity of wiretap channels using polar codes. IEEE Trans. Inf. Theory 57(10), 6428–6443 (2011)

    CrossRef  MathSciNet  MATH  Google Scholar

21. Muramatsu, J., Miyake, S.: Construction of wiretap channel codes by using sparse matrices. In: 2009 IEEE Information Theory Workshop (2009)

    Google Scholar

22. Schulze, H., Lüders, C.: Theory and Applications of OFDM and CDMA: Wideband Wireless Communications. Wiley, Hoboken (2005)

    CrossRef  Google Scholar

23. Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev. 41(2), 303–332 (1999)

    CrossRef  MathSciNet  MATH  Google Scholar

24. Strasser, M., Danev, B., Čapkun, S.: Detection of reactive jamming in sensor networks. ACM Trans. Sens. Netw. (TOSN) 7(2), 16 (2010)

    Google Scholar

25. Tal, I., Vardy, A.: Channel upgrading for semantically-secure encryption on wiretap channels. In: 2013 IEEE International Symposium on Information Theory Proceedings (ISIT), pp. 1561–1565. IEEE (2013)

    Google Scholar

26. Tang, X., Liu, R., Spasojevic, P., Poor, H.V.: The Gaussian wiretap channel with a helping interferer. In: 2008 IEEE International Symposium on Information Theory, pp. 389–393. IEEE (2008)

    Google Scholar

27. Tang, X., Liu, R., Spasojevic, P., Poor, H.V.: Interference assisted secret communication. IEEE Trans. Inf. Theory 57(5), 3153–3167 (2011)

    CrossRef  MathSciNet  Google Scholar

28. Tekin, E., Yener, A.: Achievable rates for the general Gaussian multiple access wire-tap channel with collective secrecy. arXiv preprint cs/0612084 (2006)

29. Tekin, E., Yener, A.: The Gaussian multiple access wire-tap channel: wireless secrecy and cooperative jamming. In: 2007 Information Theory and Applications Workshop, pp. 404–413. IEEE (2007)

    Google Scholar

30. Tekin, E., Yener, A.: The general Gaussian multiple-access and two-way wiretap channels: achievable rates and cooperative jamming. IEEE Trans. Inf. Theory 54(6), 2735–2751 (2008)

    CrossRef  MathSciNet  MATH  Google Scholar

31. Thangaraj, A., Dihidar, S., Calderbank, A.R., McLaughlin, S.W., Merolla, J.-M.: Applications of LDPC codes to the wiretap channel. IEEE Trans. Inf. Theory 53(8), 2933–2945 (2007)

    CrossRef  MathSciNet  MATH  Google Scholar

32. Tse, D., Viswanath, P.: Fundamentals of Wireless Communication. Cambridge University Press, Cambridge (2005)

    CrossRef  MATH  Google Scholar

33. Wyner, A.D.: The wire-tap channel. Bell Syst. Tech. J. 54(8), 1355–1387 (1975)

    CrossRef  MathSciNet  MATH  Google Scholar

Download references

Author information

Authors and Affiliations

1. Department of Computer Science, University of Calgary, Calgary, Canada

   Setareh Sharifian, Reihaneh Safavi-Naini & Fuchun Lin

Corresponding author

Correspondence to Setareh Sharifian .

Editor information

Editors and Affiliations

1. Multimedia University, MMU, Cyberjaya, Malaysia

   Raphaël C.-W. Phan

2. Snapchat and Columbia University, New York, New York, USA

   Moti Yung

Appendices

Appendix A: Achievable Transmission Rate Using BiT\(^N_{q,\eta }\)

For a noise free main channel, the secrecy capacity of BiT\(^N_{q,\eta }\) is given by:

$$ C_s(\text {BiT}_{\eta ,q}^N)=-\{\eta \log \eta +(1-\eta )\log \frac{1-\eta }{(2^{Nq}-1)}\}. $$

Figure 4 shows the rate of communication when, the information block length is Nq bits, \(q=2,3\) and 4, and \(N=64\). The graphs show the achievable rates for \(\sigma =128\) semantic security, and \(\eta =0.2\) (upper graph) and \(\eta =0.4\) (lower graph). The figures show that the achievable secrecy rate and secrecy capacity decreases as \(\eta \) grows. This is expected because higher \(\eta \) means that the adversary has a better chance of correctly decoding the jammed signal.

Fig. 4.

The secrecy rate and capacity (bits per channel use) for \(N=64\) and different values of q for \(\eta =0.2\) (upper graph) and \(\eta =0.4\) (lower graph).

Full size image

Appendix B: BiT over Noisy Receiver Channel—An Example

In this section we derive a sufficient relation between \(P_b\) and \(\eta \) so that the virtual wiretap channel is a stochastically degraded broadcast channel. Following Sect. 3, the transition matrix of the virtual wiretapper channel W for \(q=2\) is given by:

$$\mathbf {P}_{\mathsf {W}}= \begin{bmatrix} \eta&\frac{1-\eta }{3}&\frac{1-\eta }{3}&\frac{1-\eta }{3} \\ \frac{1-\eta }{3}&\eta&\frac{1-\eta }{3}&\frac{1-\eta }{3} \\ \frac{1-\eta }{3}&\frac{1-\eta }{3}&\eta&\frac{1-\eta }{3} \\ \frac{1-\eta }{3}&\frac{1-\eta }{3}&\frac{1-\eta }{3}&\eta \end{bmatrix}, $$

where \(u=\frac{1-\eta }{3}\), and \(v=\eta -\frac{1-\eta }{3}=\frac{4\eta -1}{3}\). Note that the sum of each row is \(4u+v=1\). On the other hand, we can compute:

$$ \begin{array}{ll} \mathbf {P}_{\mathsf {M}}^{-1} &{}= \frac{1}{(1-2P_b)^2}\cdot \\ &{}\ \ \begin{pmatrix} (1-P_b)(1-P_b) &{} -P_b(1-P_b) &{} -P_b(1-P_b) &{} P_b^2 \\ -P_b(1-P_b) &{} (1-P_b)(1-P_b) &{} P_b^2 &{} -P_b(1-P_b) \\ -P_b(1-P_b) &{} P_b^2 &{} (1-P_b)(1-P_b) &{} -P_b(1-P_b) \\ P_b^2 &{} -P_b(1-P_b) &{}-P_b(1-P_b)&{} (1-P_b)(1-P_b) \end{pmatrix}. \end{array} $$

Let \(a=1-P_b\) and \(b=P_b\). The above matrix can be written as:

$$\mathbf {P}_{\mathsf {M}}^{-1} = \frac{1}{(a-b)^2}\cdot \begin{pmatrix} a^2 &{} -ab &{} -ab &{} b^2 \\ -ab &{} a^2 &{} b^2 &{} -ab \\ -ab &{} b^2 &{} a^2 &{} -ab \\ b^2 &{} -ab &{}-ab&{} a^2 \end{pmatrix}. $$

The sum of entries of each row is given by, \(\frac{1}{(a-b)^2}(a^2-2ab+b^2)=1\). The following is used to prove the required relation.

Lemma 1

Let there be two matrices

$$ A= \begin{bmatrix} a_{11}&a_{12}&\dots&a_{1n} \\ a_{21}&a_{22}&\dots&a_{2n} \\ \vdots&\vdots&\vdots \\ a_{n1}&a_{n2}&\dots&a_{nn} \end{bmatrix}, B= \begin{bmatrix} b_{11}&b_{12}&\dots&b_{1n} \\ b_{21}&b_{22}&\dots&b_{2n} \\ \vdots&\vdots&\vdots \\ b_{n1}&b_{n2}&\dots&b_{nn} \end{bmatrix}. $$

If \(\sum _{j=1}^n a_{ij}=1\) and \(\sum _{j=1}^n b_{ij}=1\) for any \(i\in [n]\), then \(\sum _{j=1}^n (AB)_{ij}=1\), for any \(i\in [n]\).

Proof

For any \(i\in [n]\),

$$ \begin{array}{ll} \sum _{j=1}^n (AB)_{ij}&{}=\sum _{j=1}^n \left( \sum _{k=1}^n a_{ik}b_{kj} \right) \\ &{}=\sum _{k=1}^n a_{ik}\cdot \left( \sum _{j=1}^n b_{kj} \right) \\ &{}=\sum _{k=1}^n a_{ik}\\ &{}=1. \end{array} $$

\(\square \)

Lemma 2

The virtual wiretap channel is a stochastically degraded broadcast channel if \(P_b\le \frac{1-\sqrt{\frac{4\eta -1}{3}}}{2}\) and \(\eta >\frac{1}{4}\).

Proof

The virtual wiretap channel is a stochastically degraded broadcast channel if there exists a matrix \(\mathbf {R}\) such that \(\mathbf {P}_{\mathsf {W}}=\mathbf {P}_{\mathsf {M}}\times \mathbf {R}\), and \(\mathbf {R}\) is a channel transition matrix; that is, has non-negative entries and each row sums to 1. Using the matrices \(\mathbf {P}_{\mathsf {M}}\) and \(\mathbf {P}_{\mathsf {W}}\) above, we have:

$$ \begin{array}{ll} \mathbf {R}&{}=\mathbf {P}_{\mathsf {W}}\times \mathbf {P}_{\mathsf {M}}^{-1}\\ &{}=\frac{1}{(a-b)^2}\begin{bmatrix} u(a-b)^2+va^2\ &{} u(a-b)^2-vab\ &{} u(a-b)^2-vab\ &{} u(a-b)^2+vb^2 \\ u(a-b)^2-vab &{} u(a-b)^2+va^2 &{} u(a-b)^2+vb^2 &{} u(a-b)^2-vab \\ u(a-b)^2-vab &{} u(a-b)^2+vb^2 &{} u(a-b)^2+va^2 &{} u(a-b)^2-vab \\ u(a-b)^2+vb^2 &{} u(a-b)^2-vab &{} u(a-b)^2-vab &{} u(a-b)^2+va^2 \\ \end{bmatrix}. \end{array} $$

Using Lemma 1, entries in each row of \(\mathbf {R}\) sum to 1.

To ensure entries of \(\mathbf {R}\) are all non-negative, we first note that \(u(a-b)^2+va^2> 0\) and \(u(a-b)^2+vb^2>0\). So the virtual wiretap channel is a stochastically degraded broadcast channel if \(u(a-b)^2-vab\ge 0\) and so:

$$ \begin{array}{ll} u(a-b)^2-vab\ge 0 &{}\Leftrightarrow ua^2+ub^2-(2u+v)ab\ge 0\\ &{}\Leftrightarrow ua^2+ub^2-(2u+1-4u)ab\ge 0\\ &{}\Leftrightarrow ua^2+ub^2-(1-2u)ab\ge 0\\ &{}\Leftrightarrow u(a+b)^2-ab\ge 0\\ &{}\Leftrightarrow u-ab\ge 0\\ &{}\Leftrightarrow P_b^2-P_b+u\ge 0,\\ \end{array} $$

where \(4u+v=1\) and \(a+b=1\) are repeatedly invoked to simplify the expressions. The solution to the above inequality depends on the determinant \(1-4u\). When \(1-4u>0\), we have

$$ \begin{array}{ll} P_b^2-P_b+u\ge 0&{}\Leftrightarrow \left( P_b-\frac{1-\sqrt{1-4u}}{2}\right) \left( P_b-\frac{1+\sqrt{1-4u}}{2}\right) \ge 0\\ &{}\Leftrightarrow \left( P_b-\frac{1-\sqrt{v}}{2}\right) \left( P_b-\frac{1+\sqrt{v}}{2}\right) \ge 0\\ &{}\Leftrightarrow \left( P_b-\frac{1-\sqrt{\frac{4\eta -1}{3}}}{2}\right) \left( P_b-\frac{1+\sqrt{\frac{4\eta -1}{3}}}{2}\right) \ge 0\\ &{}\Leftrightarrow P_b\le \frac{1-\sqrt{\frac{4\eta -1}{3}}}{2} \text {or}\; P_b\ge \frac{1+\sqrt{\frac{4\eta -1}{3}}}{2}. \end{array} $$

By assumption, \(P_b\in [0,\frac{1}{2}]\) and so \(P_b\le \frac{1-\sqrt{\frac{4\eta -1}{3}}}{2} = \frac{1}{2} - \sqrt{\frac{4\eta -1}{12}}\).\(\square \)

Example 2

Let \(P_b=0.1\) and Let \(\eta =0.55\). Therefore,

$$ \mathbf {P}_{\mathsf {M}}= \begin{bmatrix} 0.81&0.09&0.09&0.01 \\ 0.09&0.81&0.01&0.09 \\ 0.09&0.01&0.81&0.09 \\ 0.01&0.09&0.09&0.81 \end{bmatrix} $$

and

$$ \mathbf {P}_{\mathsf {W}}= \begin{bmatrix} 0.55&0.15&0.15&0.15 \\ 0.15&0.55&0.15&0.15 \\ 0.15&0.15&0.55&0.15 \\ 0.15&0.15&0.15&0.55 \end{bmatrix}. $$

Therefore

$$ \mathbf {R}= \mathbf {P}_{\mathsf {W}}\times \mathbf {P}_{\mathsf {M}}^{-1}= \begin{bmatrix} 0.66&0.094&0.094&0.156 \\ 0.094&0.66&0.156&0.094 \\ 0.094&0.156&0.66&0.094 \\ 0.156&0.094&0.094&0.66 \end{bmatrix}. $$

\(\mathbf {R}\) is the transition probability matrix of a virtual channel that confirms \(\mathbf {P}_{\mathsf {W}}\) is degraded with respect to \(\mathbf {P}_{\mathsf {M}}\). The secrecy capacity in this example is

$$\begin{aligned} C_s =C_{\mathsf {M}}-C_{\mathsf {W}}=(2-0.7624)-(2-1.1515)=0.3891. \end{aligned}$$

Rights and permissions

Copyright information

© 2017 Springer International Publishing AG

About this paper

Cite this paper

Sharifian, S., Safavi-Naini, R., Lin, F. (2017). A Virtual Wiretap Channel for Secure Message Transmission. In: Phan, RW., Yung, M. (eds) Paradigms in Cryptology – Mycrypt 2016. Malicious and Exploratory Cryptology. Mycrypt 2016. Lecture Notes in Computer Science(), vol 10311. Springer, Cham. https://doi.org/10.1007/978-3-319-61273-7_9

Download citation

• .RIS
• .ENW
• .BIB

• DOI : https://doi.org/10.1007/978-3-319-61273-7_9

• Published: 14 July 2017

• Publisher Name: Springer, Cham

• Print ISBN: 978-3-319-61272-0

• Online ISBN: 978-3-319-61273-7

• eBook Packages: Computer Science Computer Science (R0)

dotsonheary1990.blogspot.com

Source: https://link.springer.com/chapter/10.1007/978-3-319-61273-7_9

Share this post