Cryptology ePrint Archive: Report 2016/202

An Encryption Scheme based on Random Split of St-Gen Codes

Simona Samardjiska and Danilo Gligoroski

Abstract: Staircase-Generator codes (St-Gen codes) have recently been introduced in the design of code-based public key schemes and for the design of steganographic matrix embedding schemes. In this paper we propose a method for random splitting of St-Gen Codes and use it to design a new coding based public key encryption scheme. The scheme uses the known list decoding method for St-Gen codes, but introduces a novelty in the creation of the public and private key. We modify the classical approach for hiding the structure of the generator matrix by introducing a technique for splitting it into random parts. This approach counters the weaknesses found in the previous constructions of public key schemes using St-Gen codes. Our initial software implementation shows that encryption using Random Split of St-Gen Codes compared to original St-Gen Codes is slower by a linear factor in the number of random splits of the St-Gen code, while the decryption complexity remains the same.

Category / Keywords: public-key cryptography / Public Key Cryptography, Code Based Cryptosystems, St-Gen Codes, List Decoding

Date: received 25 Feb 2016, last revised 4 Mar 2016

Contact author: simona samardjiska at finki ukim mk

Available format(s): PDF | BibTeX Citation

Note: technical corrections

Version: 20160304:213746 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]