Article Preview
TopBackground
With the same PRNGs, Alice and Bob create the same parity check (H) matrices using a process specified in the next section. It is assumed that Alice and Bob use a systematic code which uses codewords that include the original message. Alice punctures (removes) the message from the codeword before sending it to the transmitter. Bob uses his H matrix at the receiver to depuncture (recreate) the message portion of the codeword. For the next message block, this procedure is repeated and a new H matrix (a new LDPC code) is created and used. For each message block, Bob needs the correct H matrix to properly depuncture the codeword and recover the message.
In a traditional system, Alice encrypts the message (by XORing it with a stream from the PRNG for example) and then uses standard static LDPC encoding so that Bob can remove errors in the encrypted message due to the channel. Eve is able to get her own copy of codewords. She does not know what LDPC code is being used. However, we assume that she is sophisticated and is able to figure out H over time by analyzing her received series of codewords. She uses her H matrix to perform error correction and then has a clean copy of Alice's encrypted message blocks. With a clean copy of the encrypted message, she may eventually break the encryption and recover Alice's message. However, using the system described here, Eve will have more difficulty recovering the message. She does not have access to the PRNGs, H matrices, or G matrices being used. Looking for patterns in her series of codewords is not fruitful because H changes for each codeword. Thus, she may be stuck at this stage. Because encryption and error correction are combined, Eve has to try to perform error correction and cryptanalysis together, or perform cryptanalysis on noisy codewords. For large entropy PRNGs, Eve may desire a long string of error free (or near error free) transmitted bits to use for identifying these PRNGs and decrypting Alice's message. However, to make use of the error correcting capabilities of the transmission, she will need the H matrix which is determined by the PRNGs. This combination of privacy and error correction creates a “chicken and egg” issue for Eve.
Alice punctures the message portion of the codeword before sending it across the channel so that Eve does not directly receive the message. Thus, the rate of the LDPC code (the message block length divided by the codeword length) before puncturing must be less than 1/2. Note that a half rate code before puncturing would lead to a rate 1 code after puncturing and would not have any error correcting capability if a random or fully compressed message is assumed.
Using LDPC codes for privacy is not new. Demijan Klinc et al. use LDPC codes for private communications in (Klinc et al., 2009). They created a special class of LDPC codes that has a small security gap and privacy for their system relies on the channel between Eve and Alice being noisier than the channel between Bob and Alice, which is not always valid. Their LDPC code is static and known to all. Another system developed by R.J. McEliece makes use of the fact that it is difficult to decode an arbitrary (n,k) linear code without knowing G (or H). See (McEliece, 1978). This problem has been proven to be NP-complete in (Berlekamp et al., 1978). The McEliece cryptosystem is a public key system. The code is used multiple times and this system is useful for a multi-user scenario. McEliece uses Goppa codes in his cryptosystem. However, his system is modified by replacing the Goppa codes with QC-LDPC codes in (Baldi et al., 2008). Unlike the systems by Klinc, McEliece and Baldi, the system presented in this paper uses new codes (new H matrices) for each message block.