# American Institute of Mathematical Sciences

February 2019, 13(1): 11-39. doi: 10.3934/amc.2019002

## The secrecy capacity of the arbitrarily varying wiretap channel under list decoding

 1 Lehrstuhl für Theoretische Informationstechnik, Technische Universität München, 80290 München, Germany 2 Information Theory and Applications Chair, Technische Universität Berlin, 10587 Berlin, Germany

This work was presented in part at IEEE-CNS, Philadelphia, USA, October 2016 [19] and at IEEE-SPAWC, Sapporo, Japan, July 2017 [20]

Received  April 2017 Published  December 2018

We consider a communication scenario in which the channel undergoes two different classes of attacks at the same time: a passive eavesdropper and an active jammer. This scenario is modelled by the concept of arbitrarily varying wiretap channels (AVWCs). In this paper, we derive a full characterization of the list secrecy capacity of the AVWC, showing that the list secrecy capacity is equivalent to the correlated random secrecy capacity if the list size L is greater than the order of symmetrizability of the AVC between the transmitter and the legitimate receiver. Otherwise, it is zero. Our result indicates that for a sufficiently large list size L, list codes can overcome the drawbacks of correlated and uncorrelated codes and provide a stable secrecy capacity for AVWCs. Furthermore, we investigate the effect of relaxing the reliability and secrecy constraints by allowing a non-vanishing error probability and information leakage on the list size L. We found that we can construct a list code whose rate is close to the correlated secrecy capacity using a finite list size L that only depends on the average error probability requested. Finally, we point out that our capacity characterization is an important step in investigating the analytical properties of the capacity function such as: the continuity behavior, Turing computability and super-activation of parallel AVWCs.

Citation: Ahmed S. Mansour, Holger Boche, Rafael F. Schaefer. The secrecy capacity of the arbitrarily varying wiretap channel under list decoding. Advances in Mathematics of Communications, 2019, 13 (1) : 11-39. doi: 10.3934/amc.2019002
##### References:
 [1] R. Ahlswede, Elimination of correlation in random codes for arbitrarily varying channels, Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, 44 (1978), 159-175. doi: 10.1007/BF00533053. [2] I. Bjelaković, H. Boche and J. Sommerfeld, Capacity results for arbitrarily varying wiretap channels, Information Theory, Combinatorics, and Search Theory, Springer-Verlag, New York, NY, USA, 7777 (2013), 123-144 doi: 10.1007/978-3-642-36899-8_5. [3] D. Blackwell, L. Breiman and A. J. Thomasian, The capacities of certain channel classes under random coding, The Annals of Mathematical Statistics, 31 (1960), 558-567. doi: 10.1214/aoms/1177705783. [4] V. M. Blinovskii, P. Narajan and M. S. Pinsker, Capacity of the arbitrarily varying channel under list decoding, Problems Inform. Transmission, 2 (1995), 99-113. [5] M. Bloch and J. Barros, Physical-Layer Security: From Information Theory to Security Engineering, Cambridge University Press, 2011. doi: 10.1017/CBO9780511977985. [6] H. Boche and R. F. Schaefer, Arbitrarily varying multiple access channels with conferencing encoders: List decoding and finite coordination resources, Adv. in Math. of Comm., 10 (2016), 333-354. doi: 10.3934/amc.2016009. [7] H. Boche, R. F. Schaefer and H. V. Poor, On the continuity of the secrecy capacity of compound and arbitrarily varying wiretap channels, IEEE Trans. Inf. Forensics and Security, 10 (2015), 2531-2546. [8] H. Boche, R. F. Schaefer and H. V. Poor, Identification over Channels with Feedback: Discontinuity Behavior and Super-Activation IEEE International Symposium on Information Theory Proceedings (ISIT), Colorado, USA, (2018), 256-260. [9] H. Boche, R. F. Schaefer and H. V. Poor, Identification Capacity of Channels with Feedback: Discontinuity Behavior, Super-Activation, and Turing Computability, Under submission, 2018. [10] H. Boche and R. F. Schaefer, Arbitrarily varying wiretap channels with finite coordination resources, 2014 IEEE International Conference on Communications Workshops (ICC), Sydney, Australia, (2014), 746-751. [11] I. Csiszar and P. Narayan, The capacity of the arbitrarily varying channel revisited: Positivity, constraints, IEEE Trans. Inf. Theory, 34 (1988), 181-193. doi: 10.1109/18.2627. [12] I. Csiszár and J. Körner, Information Theory: Coding Theorems for Discrete Memoryless Systems, Cambridge University Press, 2011. doi: 10.1017/CBO9780511921889. [13] G. Fettweis, H. Boche, T. Wiegand and E. Zielinski et al., The tactile Internet, ITU-T Technology Watch, August, 2014, Available at: http://www.itu.int/oth/T2301000023/en. [14] Deutsche Telekom AG Laboratories, Next Generation Mobile Networks - (R)evolution in Mobile Communications, Technology Radar Edition Ⅲ, 2010. [15] U. Helmbrecht and R. Plaga, New challenges for IT-security research in ICT, 40th World Federation of Scientists, International Seminars on Planetary Emergencies, Erice, Italy, August, (2008), 1-6. [16] B. L. Hughes, The smallest list for the arbitrarily varying channel, IEEE Trans. Inf. Theory, 43 (1997), 803-815. doi: 10.1109/18.568692. [17] A. Lapidoth and P. Narayan, Reliable communication under channel uncertainty, IEEE Trans. Inf. Theory, 44 (1998), 2148-2177. doi: 10.1109/18.720535. [18] Y. Liang, H. V. Poor and S. Shamai, Information theoretic security, Found. Trends Commun. Inf. Theory, 5 (2009), 355-580. [19] A. S. Mansour, H. Boche and R. F. Schaefer, List decoding for arbitrarily varying wiretap channels, IEEE Conference on Communications and Network Security (CNS), Philadelphia, PA, USA, (2016), 611-615. [20] A. S. Mansour and H. Boche and R. F. Schaefer, Stabilizing the secrecy capacity of the arbitrarily varying wiretap channel and transceiver synchronization using list decoding, IEEE International Workshop on Signal Processing Advances in Wireless Communications (SPAWC), Sapporo, Japan, (2017), 1-5. [21] E. MolavianJazi, M. Bloch and J. N. Laneman, Arbitrary jamming can preclude secure communication, Proceedings of the 47th Annual Allerton Conference on Communication, Control, and Computing, Monticello, Illinois, USA, (2009), 1069-1075. [22] S. Nitinawarat, On the deterministic code capacity region of an arbitrarily varying multipleaccess channel under list decoding, IEEE Trans. Inf. Theory, 59 (2013), 2683-2693. doi: 10.1109/TIT.2013.2242514. [23] J. Nötzel, M. Wiese and H. Boche, The arbitrarily varying wiretap channel - secret randomness, stability, and super-activation, IEEE Trans. Inf. Theory, 62 (2016), 3504-3531. doi: 10.1109/TIT.2016.2550587. [24] R. F. Schaefer and H. Boche, Physical layer service integration in wireless networks: Signal processing challenges, IEEE Signal Processing Magazine, 31 (2014), 147-156. [25] R. F. Schaefer, H. Boche and H. V. Poor, Super-Activation as a Unique Feature of Secure Communication in Malicious Environments, Information, 7 (2016), 24. [26] M. Wiese, J. Nötzel and H. Boche, A channel under simultaneous jamming and eavesdropping attack - correlated random coding capacities under strong secrecy criteria, IEEE Trans. Inf. Theory, 62 (2016), 3844-3862. doi: 10.1109/TIT.2016.2565482. [27] A. D. Wyner, The wire-tap channel, Bell Syst. Tech. J., 54 (1975), 1355-1387. doi: 10.1002/j.1538-7305.1975.tb02040.x.

show all references

##### References:
 [1] R. Ahlswede, Elimination of correlation in random codes for arbitrarily varying channels, Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, 44 (1978), 159-175. doi: 10.1007/BF00533053. [2] I. Bjelaković, H. Boche and J. Sommerfeld, Capacity results for arbitrarily varying wiretap channels, Information Theory, Combinatorics, and Search Theory, Springer-Verlag, New York, NY, USA, 7777 (2013), 123-144 doi: 10.1007/978-3-642-36899-8_5. [3] D. Blackwell, L. Breiman and A. J. Thomasian, The capacities of certain channel classes under random coding, The Annals of Mathematical Statistics, 31 (1960), 558-567. doi: 10.1214/aoms/1177705783. [4] V. M. Blinovskii, P. Narajan and M. S. Pinsker, Capacity of the arbitrarily varying channel under list decoding, Problems Inform. Transmission, 2 (1995), 99-113. [5] M. Bloch and J. Barros, Physical-Layer Security: From Information Theory to Security Engineering, Cambridge University Press, 2011. doi: 10.1017/CBO9780511977985. [6] H. Boche and R. F. Schaefer, Arbitrarily varying multiple access channels with conferencing encoders: List decoding and finite coordination resources, Adv. in Math. of Comm., 10 (2016), 333-354. doi: 10.3934/amc.2016009. [7] H. Boche, R. F. Schaefer and H. V. Poor, On the continuity of the secrecy capacity of compound and arbitrarily varying wiretap channels, IEEE Trans. Inf. Forensics and Security, 10 (2015), 2531-2546. [8] H. Boche, R. F. Schaefer and H. V. Poor, Identification over Channels with Feedback: Discontinuity Behavior and Super-Activation IEEE International Symposium on Information Theory Proceedings (ISIT), Colorado, USA, (2018), 256-260. [9] H. Boche, R. F. Schaefer and H. V. Poor, Identification Capacity of Channels with Feedback: Discontinuity Behavior, Super-Activation, and Turing Computability, Under submission, 2018. [10] H. Boche and R. F. Schaefer, Arbitrarily varying wiretap channels with finite coordination resources, 2014 IEEE International Conference on Communications Workshops (ICC), Sydney, Australia, (2014), 746-751. [11] I. Csiszar and P. Narayan, The capacity of the arbitrarily varying channel revisited: Positivity, constraints, IEEE Trans. Inf. Theory, 34 (1988), 181-193. doi: 10.1109/18.2627. [12] I. Csiszár and J. Körner, Information Theory: Coding Theorems for Discrete Memoryless Systems, Cambridge University Press, 2011. doi: 10.1017/CBO9780511921889. [13] G. Fettweis, H. Boche, T. Wiegand and E. Zielinski et al., The tactile Internet, ITU-T Technology Watch, August, 2014, Available at: http://www.itu.int/oth/T2301000023/en. [14] Deutsche Telekom AG Laboratories, Next Generation Mobile Networks - (R)evolution in Mobile Communications, Technology Radar Edition Ⅲ, 2010. [15] U. Helmbrecht and R. Plaga, New challenges for IT-security research in ICT, 40th World Federation of Scientists, International Seminars on Planetary Emergencies, Erice, Italy, August, (2008), 1-6. [16] B. L. Hughes, The smallest list for the arbitrarily varying channel, IEEE Trans. Inf. Theory, 43 (1997), 803-815. doi: 10.1109/18.568692. [17] A. Lapidoth and P. Narayan, Reliable communication under channel uncertainty, IEEE Trans. Inf. Theory, 44 (1998), 2148-2177. doi: 10.1109/18.720535. [18] Y. Liang, H. V. Poor and S. Shamai, Information theoretic security, Found. Trends Commun. Inf. Theory, 5 (2009), 355-580. [19] A. S. Mansour, H. Boche and R. F. Schaefer, List decoding for arbitrarily varying wiretap channels, IEEE Conference on Communications and Network Security (CNS), Philadelphia, PA, USA, (2016), 611-615. [20] A. S. Mansour and H. Boche and R. F. Schaefer, Stabilizing the secrecy capacity of the arbitrarily varying wiretap channel and transceiver synchronization using list decoding, IEEE International Workshop on Signal Processing Advances in Wireless Communications (SPAWC), Sapporo, Japan, (2017), 1-5. [21] E. MolavianJazi, M. Bloch and J. N. Laneman, Arbitrary jamming can preclude secure communication, Proceedings of the 47th Annual Allerton Conference on Communication, Control, and Computing, Monticello, Illinois, USA, (2009), 1069-1075. [22] S. Nitinawarat, On the deterministic code capacity region of an arbitrarily varying multipleaccess channel under list decoding, IEEE Trans. Inf. Theory, 59 (2013), 2683-2693. doi: 10.1109/TIT.2013.2242514. [23] J. Nötzel, M. Wiese and H. Boche, The arbitrarily varying wiretap channel - secret randomness, stability, and super-activation, IEEE Trans. Inf. Theory, 62 (2016), 3504-3531. doi: 10.1109/TIT.2016.2550587. [24] R. F. Schaefer and H. Boche, Physical layer service integration in wireless networks: Signal processing challenges, IEEE Signal Processing Magazine, 31 (2014), 147-156. [25] R. F. Schaefer, H. Boche and H. V. Poor, Super-Activation as a Unique Feature of Secure Communication in Malicious Environments, Information, 7 (2016), 24. [26] M. Wiese, J. Nötzel and H. Boche, A channel under simultaneous jamming and eavesdropping attack - correlated random coding capacities under strong secrecy criteria, IEEE Trans. Inf. Theory, 62 (2016), 3844-3862. doi: 10.1109/TIT.2016.2565482. [27] A. D. Wyner, The wire-tap channel, Bell Syst. Tech. J., 54 (1975), 1355-1387. doi: 10.1002/j.1538-7305.1975.tb02040.x.
Discrete memoryless arbitrarily varying wiretap channel $(\mathfrak{W},\mathfrak{V})$
 [1] Holger Boche, Rafael F. Schaefer. Arbitrarily varying multiple access channels with conferencing encoders: List decoding and finite coordination resources. Advances in Mathematics of Communications, 2016, 10 (2) : 333-354. doi: 10.3934/amc.2016009 [2] Peter Beelen, Kristian Brander. Efficient list decoding of a class of algebraic-geometry codes. Advances in Mathematics of Communications, 2010, 4 (4) : 485-518. doi: 10.3934/amc.2010.4.485 [3] Henry Cohn, Nadia Heninger. Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding. Advances in Mathematics of Communications, 2015, 9 (3) : 311-339. doi: 10.3934/amc.2015.9.311 [4] Jonas Eriksson. A weight-based characterization of the set of correctable error patterns under list-of-2 decoding. Advances in Mathematics of Communications, 2007, 1 (3) : 331-356. doi: 10.3934/amc.2007.1.331 [5] Fernando Hernando, Tom Høholdt, Diego Ruano. List decoding of matrix-product codes from nested codes: An application to quasi-cyclic codes. Advances in Mathematics of Communications, 2012, 6 (3) : 259-272. doi: 10.3934/amc.2012.6.259 [6] Alain Bensoussan, Sonny Skaaning. Base stock list price policy in continuous time. Discrete & Continuous Dynamical Systems - B, 2017, 22 (1) : 1-28. doi: 10.3934/dcdsb.2017001 [7] Tobias Sutter, David Sutter, John Lygeros. Capacity of random channels with large alphabets. Advances in Mathematics of Communications, 2017, 11 (4) : 813-835. doi: 10.3934/amc.2017060 [8] David Karpuk, Anne-Maria Ernvall-Hytönen, Camilla Hollanti, Emanuele Viterbo. Probability estimates for fading and wiretap channels from ideal class zeta functions. Advances in Mathematics of Communications, 2015, 9 (4) : 391-413. doi: 10.3934/amc.2015.9.391 [9] Ellina Grigorieva, Evgenii Khailov, Andrei Korobeinikov. Optimal control for an epidemic in populations of varying size. Conference Publications, 2015, 2015 (special) : 549-561. doi: 10.3934/proc.2015.0549 [10] Yanan Zhao, Daqing Jiang, Xuerong Mao, Alison Gray. The threshold of a stochastic SIRS epidemic model in a population with varying size. Discrete & Continuous Dynamical Systems - B, 2015, 20 (4) : 1277-1295. doi: 10.3934/dcdsb.2015.20.1277 [11] Tone Arnold, Myrna Wooders. Dynamic club formation with coordination. Journal of Dynamics & Games, 2015, 2 (3&4) : 341-361. doi: 10.3934/jdg.2015010 [12] Kwankyu Lee. Decoding of differential AG codes. Advances in Mathematics of Communications, 2016, 10 (2) : 307-319. doi: 10.3934/amc.2016007 [13] M. Núñez-López, J. X. Velasco-Hernández, P. A. Marquet. The dynamics of technological change under constraints: Adopters and resources. Discrete & Continuous Dynamical Systems - B, 2014, 19 (10) : 3299-3317. doi: 10.3934/dcdsb.2014.19.3299 [14] Kai Zehmisch. The codisc radius capacity. Electronic Research Announcements, 2013, 20: 77-96. doi: 10.3934/era.2013.20.77 [15] Benny Avelin, Tuomo Kuusi, Mikko Parviainen. Variational parabolic capacity. Discrete & Continuous Dynamical Systems - A, 2015, 35 (12) : 5665-5688. doi: 10.3934/dcds.2015.35.5665 [16] Lasse Kiviluoto, Patric R. J. Östergård, Vesa P. Vaskelainen. Sperner capacity of small digraphs. Advances in Mathematics of Communications, 2009, 3 (2) : 125-133. doi: 10.3934/amc.2009.3.125 [17] Chungen Liu, Qi Wang. Symmetrical symplectic capacity with applications. Discrete & Continuous Dynamical Systems - A, 2012, 32 (6) : 2253-2270. doi: 10.3934/dcds.2012.32.2253 [18] Elisa Gorla, Felice Manganiello, Joachim Rosenthal. An algebraic approach for decoding spread codes. Advances in Mathematics of Communications, 2012, 6 (4) : 443-466. doi: 10.3934/amc.2012.6.443 [19] Washiela Fish, Jennifer D. Key, Eric Mwambene. Partial permutation decoding for simplex codes. Advances in Mathematics of Communications, 2012, 6 (4) : 505-516. doi: 10.3934/amc.2012.6.505 [20] Alexander Barg, Arya Mazumdar, Gilles Zémor. Weight distribution and decoding of codes on hypergraphs. Advances in Mathematics of Communications, 2008, 2 (4) : 433-450. doi: 10.3934/amc.2008.2.433

2017 Impact Factor: 0.564