• PDF
• Cite
• Share
Article Contents Article Contents

# Some cryptanalytic and coding-theoretic applications of a soft stern algorithm

• * Corresponding author

This work was supported in part by the Swedish Research Council (Grant No. 2015-04528). The first author was also supported in part by the Norwegian Research Council (Grants No. 247742/070)

• Using the class of information set decoding algorithms is the best known way of decoding general codes, i.e. codes that admit no special structure, in the Hamming metric. The Stern algorithm is the origin of the most efficient algorithms in this class. We consider the same decoding problem but for a channel with soft information. We give a version of the Stern algorithm for a channel with soft information that includes some novel steps of ordering vectors in lists, based on reliability values. We demonstrate how the algorithm constitutes an improvement in some cryptographic and coding theoretic applications. We also indicate how to extend the algorithm to include multiple iterations and soft output values.

Mathematics Subject Classification: Primary: 94A60; Secondary: 68P30.

 Citation: • • Figure 1.  An ilustration of what the binary tree in the algorithm for finding the most probable bit patterns looks like in the first six steps

Figure 2.  The logarithm of the success probability for the different algorithms as a function of $\sigma$

Figure 3.  The failure probability for the different algorithms as a function of $\sigma$

• ## Article Metrics DownLoad:  Full-Size Img  PowerPoint
{"ft_lang_label":"__label__en","ft_lang_prob":0.6454944,"math_prob":0.877915,"size":7678,"snap":"2023-14-2023-23","text_gpt3_token_len":2381,"char_repetition_ratio":0.15519938,"word_repetition_ratio":0.062440872,"special_character_ratio":0.35504037,"punctuation_ratio":0.25841346,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.95783496,"pos_list":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14],"im_url_duplicate_count":[null,null,null,null,null,null,null,null,null,null,null,1,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-06-04T17:35:40Z\",\"WARC-Record-ID\":\"<urn:uuid:7877b6c7-fe28-4568-b65b-ad091b6ad0fb>\",\"Content-Length\":\"121248\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:5203e854-0299-429a-ba04-6c2229c0a87d>\",\"WARC-Concurrent-To\":\"<urn:uuid:b59cfd57-b0bd-477c-92f6-ccf8720692a9>\",\"WARC-IP-Address\":\"107.161.80.18\",\"WARC-Target-URI\":\"https://ftp.aimsciences.org/article/doi/10.3934/amc.2019035\",\"WARC-Payload-Digest\":\"sha1:KSNJQUN7SNY7GUCIZSSQ3J5NJOHJMQK4\",\"WARC-Block-Digest\":\"sha1:CURLBL2KITT4Z462CP3DKL72UOR2AHVZ\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-23/CC-MAIN-2023-23_segments_1685224650201.19_warc_CC-MAIN-20230604161111-20230604191111-00593.warc.gz\"}"}