Encrypted Numeric Vector Computations Based on Non-Systematic QC-MDPC Code Over Prime Field

This paper presents three types of post-quantum encrypted vector computations over the prime field. Based on the linearity and quasi-cyclicity of non-binary QC-MDPC code, the method can perform vector addition (VA), scalar multiplication (SM), and cyclic shift (CS) without decrypting ciphertexts, where the scalar value and shift width are public plaintext data. Com-binations of these computations enable some important practical computations, e.g., the batch of weighted sums and convolution of vector elements. The parity-check matrix of QC-MDPC code used in the key encapsulation is modified to remove the systematic information part of the ciphertext. The decoding failure rate is evaluated by simulation for QC-MDPC code over <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbb{F}_{q}$</tex> with the non-binary sum-product algorithm and the parallel symbol flipping decoding. Also the work factors of the information set decoding for key recovery and decoding attacks are calculated. The numerical results show that, using a (9602, 4801) code over <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbb{F}_{251}$</tex>, the method can perform up to three VAs and arbitrary numbers of SMs and CSs.