Network Coding-Based Post-Quantum Cryptography

被引:17
作者
Cohen, Alejandro [1 ]
D'Oliveira, Rafael G. L. [1 ]
Salamatian, Salman [2 ,3 ]
Medard, Muriel [1 ]
机构
[1] MIT, Elect Res Lab, Cambridge, MA 02139 USA
[2] MIT, 77 Massachusetts Ave, Cambridge, MA 02139 USA
[3] DE Shaw Grp, New York, NY 10036 USA
来源
IEEE JOURNAL ON SELECTED AREAS IN INFORMATION THEORY | 2021年 / 2卷 / 01期
关键词
Post quantum cryptography; cryptography; information-theoretic security; secure network coding; public key; encryption; communication system security; secure distributed storage; DISTRIBUTED STORAGE; MCELIECE; SECURITY; CAPACITY; CODES;
D O I
10.1109/JSAIT.2021.3054598
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
We propose a novel hybrid universal network-coding cryptosystem (HUNCC) to obtain secure post-quantum cryptography at high communication rates. The secure network-coding scheme we offer is hybrid in the sense that it combines information-theoretic security with public-key cryptography. In addition, the scheme is general and can be applied to any communication network, and to any public-key cryptosystem. Our hybrid scheme is based on the information theoretic notion of individual secrecy, which traditionally relies on the assumption that an eavesdropper can only observe a subset of the communication links between the trusted parties - an assumption that is often challenging to enforce. For this setting, several code constructions have been developed, where the messages are linearly mixed before transmission over each of the paths in a way that guarantees that an adversary which observes only a subset has sufficient uncertainty about each individual message. Instead, in this article, we take a computational viewpoint, and construct a coding scheme in which an arbitrary secure cryptosystem is utilized on a subset of the links, while a pre-processing similar to the one in individual security is utilized. Under this scheme, we demonstrate 1) a computational security guarantee for an adversary which observes the entirety of the links 2) an information theoretic security guarantee for an adversary which observes a subset of the links, and 3) information rates which approach the capacity of the network and greatly improve upon the current solutions. A perhaps surprising consequence of our scheme is that, to guarantee a computational security level b, it is sufficient to encrypt a single link using a computational post-quantum scheme. That is, using HUNCC, we can ensure post-quantum security in networks where it is not possible to use public-key encryption over all the links in the network. In addition, the information rate approaches 1 as the number of communication links increases. As a concrete example, in a multipath network with three links, using a 128-bit computationally secure McEliece cryptosystem only over one link, we obtain a 128-bit individually computationally secure level over all paths with a total information rate of 0.91 in the network.
引用
收藏
页码:49 / 64
页数:16
相关论文
共 95 条
[11]   INHERENT INTRACTABILITY OF CERTAIN CODING PROBLEMS [J].
BERLEKAMP, ER ;
MCELIECE, RJ ;
VANTILBORG, HCA .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1978, 24 (03) :384-386
[12]   GOPPA CODES [J].
BERLEKAMP, ER .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1973, 19 (05) :590-592
[13]  
Bernstein D. J., 2009, POSTQUANTUM CRYPTOGR, DOI DOI 10.1007/978-3-540-88702-7
[14]  
Bernstein DJ, 2008, LECT NOTES COMPUT SC, V5299, P31, DOI 10.1007/978-3-540-88403-3_3
[15]  
Bhattad K., 2005, P NETCOD, V104, P1
[16]  
Biryukov A, 1998, LECT NOTES COMPUT SC, V1462, P72, DOI 10.1007/BFb0055721
[17]  
Bloch M., 2011, Physical-Layer Security: From Information Theory to Security Engineering
[18]  
Borthakur D., 2011, SIGMOD, DOI DOI 10.1145/1989323.1989438
[19]  
Calder B, 2011, SOSP 11: PROCEEDINGS OF THE TWENTY-THIRD ACM SYMPOSIUM ON OPERATING SYSTEMS PRINCIPLES, P143
[20]  
Chabanne H, 2012, IEEE INT SYMP INFO