{"id":39,"date":"2020-11-11T13:46:52","date_gmt":"2020-11-11T13:46:52","guid":{"rendered":"http:\/\/codebasedcrypto.uav.ro\/wordpress\/?p=39"},"modified":"2022-08-30T08:52:26","modified_gmt":"2022-08-30T08:52:26","slug":"code-based-post-quantum-project","status":"publish","type":"post","link":"http:\/\/codebasedcrypto.uav.ro\/wordpress\/2020\/11\/11\/code-based-post-quantum-project\/","title":{"rendered":"Modified syndrome decoding problem"},"content":{"rendered":"\n

The problem of finding an error vector with fixed Hamming weight given a parity check matrix of a linear code and a syndrome vector is one of the oldest and most representative problems in code-based cryptography. From public-key encryption schemes to digital signatures, the Syndrome Decoding Problem (SDP) has become a common denominator. <\/p>\n\n\n\n

Recently, a slight modification of this well-studied problem, combined with a new technique in laser fault injections, enabled efficient message recovery attacks against the classic McEliece cryptosystem(Message Recovery Attack<\/a>) <\/p>\n\n\n

The integer syndrome decoding problem is one of the topics we focus our interest. More exactly, we are looking for two types of algorithms for this problem: exact (with presumably exponential time complexity) and probabilistic (with polynomial time complexity).<\/p>\n\n\n

Algorithms for Integer Syndrome Decoding Problem<\/h2>\n\n\n\n

We have proposed three different algorithms for solving this problem: 1. combinatorial (exponential time complexity in the worst case), 2. based on Integer Linear Programming (no theoretical evidence of the complexity so far), 3. ISD-Scode Decoder (polynomial time complexity). <\/p>\n\n\n\n

For the best solution (ISD-Score Decoder) we have provided theoretical evidence of its complexity and practical simulations, using implementations for small to large set of parameters. The algorithm not only that retrieves a solution to the Integer Syndrome Decoding Problem but it manages to find it even in a noisy scenario. This is the case when hybrid attacks are performed and a noisy estimation of the integer syndrome is computed. The results (in a short 5 page article) were accepted for presentation and publication at IEEE ITW 2022. <\/p>\n","protected":false},"excerpt":{"rendered":"

The problem of finding an error vector with fixed Hamming weight given a parity check matrix of a linear code […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-39","post","type-post","status-publish","format-standard","hentry","category-updates"],"_links":{"self":[{"href":"http:\/\/codebasedcrypto.uav.ro\/wordpress\/wp-json\/wp\/v2\/posts\/39","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/codebasedcrypto.uav.ro\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/codebasedcrypto.uav.ro\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/codebasedcrypto.uav.ro\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/codebasedcrypto.uav.ro\/wordpress\/wp-json\/wp\/v2\/comments?post=39"}],"version-history":[{"count":4,"href":"http:\/\/codebasedcrypto.uav.ro\/wordpress\/wp-json\/wp\/v2\/posts\/39\/revisions"}],"predecessor-version":[{"id":148,"href":"http:\/\/codebasedcrypto.uav.ro\/wordpress\/wp-json\/wp\/v2\/posts\/39\/revisions\/148"}],"wp:attachment":[{"href":"http:\/\/codebasedcrypto.uav.ro\/wordpress\/wp-json\/wp\/v2\/media?parent=39"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/codebasedcrypto.uav.ro\/wordpress\/wp-json\/wp\/v2\/categories?post=39"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/codebasedcrypto.uav.ro\/wordpress\/wp-json\/wp\/v2\/tags?post=39"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}