Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Implementation of the fastest ISD algorithms

NotificationsYou must be signed in to change notification settings

FloydZ/decoding

Repository files navigation

This repository contains implementations of the fastest ISD algorithms over F2and Fq. Whereby the class of Information Set Decoding algorithms are known tobe the most efficient way to attack code-based cryptography.

Currently the following algorithms are implemented on CPU:

  • Prange (F2/Fq)
  • Stern (F2/Fq)
  • Stern Indyk-Motwani (F2)
  • Stern May-Ozerov (F2)
  • MMT/BJMM (F2/Fq)
  • May-Ozerov (F2)

For the Nearest-Neighbor subroutine see thecryptanalysislib.

Requirements:

Note:google-benchmark is not really needed.

Arch Linux:

sudo pacman -S cmake make clang gtest benchmark

Ubuntu 22.04:

sudo apt install make cmake libomp-dev clang libgtest-dev googlebenchmark

Note: only Ubuntu 22.04 is supported, all older version specially Ubuntu 20.04is not supported.

MacOS:

brew install cmake make googletest libomp llvm google-benchmark

You need to have llvm first in your PATH, run:

echo 'export PATH="/usr/local/opt/llvm/bin:$PATH"' >> ~/.zshrc

For compilers to find llvm you may need to set:

export LDFLAGS="-L/usr/local/opt/llvm/lib"export CPPFLAGS="-I/usr/local/opt/llvm/include"

NixOS

The installation onnixos is super easy:

nix-shell

Windows:

You probably want to reevaluate some life decisions.

Python:

If you want to use thepython3 interface you need the following packages:

pip install prettytableas

or just run:

pip install -r requirements.txt

Build:

git clone --recurse-submodules https://github.com/FloydZ/decodingmkdir buildcd buildcmake ../ make -j8

Usage:

#C++ API:

You will find a lot of examples in thetest folder. Here a littleexample how to useSterns algorithm

#include"tests/mceliece/challenges/mce431.h"#include"stern.h"static constexprConfigISDisdConfig{.n=n,.k=k,.q=2,.w=w,.p=2,.l=13,.c=0,.threads=1};static constexprConfigSternconfig{isdConfig, .HM_bucketsize=16};Stern<isdConfig,config>stern{};stern.from_string(h,s);stern.run();assert(stern.correct());

All Implemented algorithms inherit from a base class calledISD. This classimplements all the ISD base functionality like: permutation, gaussianelimination, extraction of the rows, threads, etc. Thus we first need toinitialize the configuration for this class with:

static constexprConfigISDisdConfig{.n=n,.k=k,.q=2,.w=w,.p=2,.l=13,.c=0,.threads=1};

Next the configuration of Sterns algorithms is initialized. Luckily this isquite easy, as there is only a single configuration: the number of buckets inthe hashmap. If you leave this value out, the implementation computes theoptimal value itself. NOTE: this can lead to alignment issues.

Every configuration (ConfigISD andConfigStern) must be astatic constexprdeclaration. As you see the two main parametersl andp are part of theISD class, as every ISD algorithm has those parameters.

After this the main class for Stern is initialized via:

Stern<isdConfig,config>stern{};

Now you can either pass the needed parity check matrix via

stern.from_string(h,s);

seehere for an example of how thestrings should look like. Or you can generate a random instance via:

stern.random();

And finally the algorithm is started via:

stern.run();

Reproduction of Results EC'22 and EC'23:

This is a renewed implementation of our paperMcEliece needs a Breakand our second paperNew Time-Memory Trade-Offs for Subset-Sum.Hence, to reproduce the original results you need to checkout to thefollowingcommit

Optimization Note:

Performance Graphs:

A little helper to find performance holes. Note that you should compile wile-fno_inline to get better results.

flamegraph -o mceliece_1284_l19_noinline.svg ./test/mceliece/mceliece_test_bjmm1284 --gtest_filter='BJMM.t1284_small:BJMM/*.t1284_small:*/BJMM.t1284_small/*:*/BJMM/*.t1284_small --gtest_color=no'

Bolt

That was an idea of me. Did not work.

python gen.py -n431 -l13 -l1 2 -p 1 --bjmm_hm1_bucketsize 1024 --bjmm_hm2_bucketsize 16 --bjmm_hm1_nrbuckets 2 --bjmm_hm2_nrbuckets 11 --threads 1 --bjmm_outer_threads 1 --bench --loops 10 Bolt Optimisation------```bashperf record -e cycles:u -j any,u -o perf.data --  ./mceliece_test_bjmm1284"--gtest_filter=BJMM.t1284_small_normal:BJMM/*.t1284_small_normal:*/BJMM.t1284_small_normal/*:*/BJMM/*.t1284_small_normal --gtest_color=no"perf2bolt -p perf.data mceliece_test_bjmm1284  -o perf.fdatallvm-bolt mceliece_test_bjmm1284 -o mceliece_test_bjmm1284.bolt data=perf.fdata -reorder-blocks=cache+ -reorder-functions=hfsort -split-functions=2 -split-all-cold -split-eh -dyno-stats

Implemented Algorithms:

The following algorithms are currenlty implemented:

MMT andBJMM depth 2

                           n-k-l                                        n          0┌─────────────────────────────┬─────────────────────────────────────────┐ ┌──────┐│             I_n-k-l         │                  H                      │ │  0   │├─────────────────────────────┼─────────────────────────────────────────┤ ├──────┤ n-k-l│              0              │                                         │ │      │└─────────────────────────────┴─────────────────────────────────────────┘ └──────┘  n-k             w-p                                  p┌─────────────────────────────┬─────────────────────────────────────────┐│              e1             │                    e2                   │└─────────────────────────────┴────────────────────┬────────────────────┘                                                   │                                             ┌─────┴────┐                                           ┌───┴───┐   ┌──┴────┐                                         │  iL   │   │       │                                         └──┬────┘   └───┬───┘                                     ┌───────┴─┐         ┌┴────────┐                                ┌───┼───┐ ┌───┴───┐ ┌───┴───┐ ┌───┴───┐                                │ L1│   │ │  L2   │ │  L3   │ │   L4  │                                │   │   │ │       │ │       │ │       │                                └───┴───┘ └───────┘ └───────┘ └───────┘
  • L3 and L4 do not exist, L1 and L2 are simply reused.
  • The right intermediate List do not exist. So actually we implemented a streamjoin approach.
  • The output list do not exist. Every element is directly checked.
  • List L1 is hashed. So the Join between L1 and L2 is done with hashmaps.
  • iL is actually a hashmap.
  • source insrc/bjmm.h in classBJMM.

MMT andBJMM depth 3:

Level                        ┌───┐                            │                        │                        └─▲─┘                          │            ┌─────────────┴────────────┐0            │                          │          ┌─┴─┐                      ┌─┴─┐          │   │ HM2                      │          │   │                      │          └─▲─┘                      └─▲─┘            │                          │     ┌──────┴─────┐              ┌─────┴──────┐1     │            │              │            │   ┌─┴─┐        ┌─┴─┐          ┌─┴─┐        ┌─┼─┐   │   │ HM1        │              │ HM1        │   │   │        │              │            │   └─▲─┘        └─▲─┘          └─▲─┘        └─▲─┘     │            │              │            │  ┌──┴──┐      ┌──┴──┐        ┌──┴──┐      ┌──┴──┐2  │     │      │     │        │     │      │     │┌─┴─┐ ┌─┴─┐  ┌─┴─┐ ┌─┴─┐    ┌─┴─┐ ┌─┴─┐  ┌─┴─┐ ┌─┴─┐base lists│HM0│ │   │      │     │        │     │      │     ││   │ │   │  │     │        │     │      │     │└───┘ └───┘  └───┘ └───┘    └───┘ └───┘  └───┘ └───┘  L1L2  L1L2  L1L2   L1  L2
  • OnlyL1,L2 exist, every other List is justL1 orL2 with a differentintermediate target.
  • in the intermediate levels only hashmaps are used.
  • the output list do not exists. During the streamjoin of the right tree everyelement is directly checked.
  • source insrc/mitm.h in classCollisionHashMapD

May-OzerovIndyk-Motwani based:

TODO image
  • ListsL1 andL2 (L3,L4) are not computed. InsteadL1 is a hashmap onl1coordinates.
  • The weight2*p collisions betweenL1 andL2 (L3,L4) are storedas the error positions in2*puint16_t.
  • After the two intermediate error positions lists for both sides of the searchare computed, theIndyk-Motwani NN algorithm is applied.
  • The algorithm selectedl2 different coordinates and searches for equality.This isv times repeated.

May-OzerovEsser-Kübler-Z. based:

TODO image
  • L1 and `L2

Dumer andStern:

TODO image
  • Technically onlyDumers algorithm is implemented.
  • no list is directly computed. The listL1 is directly hashed into a hashmap.
  • The output list can be cached, s.t. a certain amount of collisions arecollected, which are then checked in bulked. This caching size can beconfigured.

SternMay-Ozerov usingIndyk-Motwani- NN:

Apply the nearest neighbour strategy by Indyk-Motwani in the last level

TODO image
  • Technically onlyDumers algorithm is implemented.

SternMay-Ozerov usingEsser-Kübler-Z.- NN:

Apply the nearest neighbour algorithm byEsser-Kübler-Z. to findclose elements in the last level.

TODO image
  • Technically onlyDumers algorithm is implemented.

Pollard:

  • memory less LeeBrickell inpollard.h

Core Binding

Either via-sudo taskset -c 1 ./mainor-OMP_PLACES=cores OMP_PROC_BIND=close ./main,OMP_PLACES=cores OMP_PROC_BIND=spread ./mainor-for j in {0..127}; do sudo taskset -c ${j} ./main & done

About

Implementation of the fastest ISD algorithms

Topics

Resources

Stars

Watchers

Forks

Languages

[8]ページ先頭
©2009-2025 Movatter.jp