1 of 18

Can we Speed Up Information Set Decoding by Using Extension Field Structure?

Freja Elbro, Violetta Weger

(And also: André Esser, Paolo Santini, Edoardo Persichetti)

1

DTU Compute

11 June 2019

McEliece Cryptosystem

2 of 18

Information Set Decoding (ISD)

  •  

2

Non-binary ISD

Peters 2010

Meurer 2012

Hirose 2016

Carrier, Hatey, Tillich 2024

No change

(GKH 2017)

DTU Compute

11 June 2019

McEliece Cryptosystem

3 of 18

Plan

  • Quick review of ISD

​

  • Four possible algorithms

​

  • Results

3

DTU Compute

11 June 2019

McEliece Cryptosystem

4 of 18

Information Set Decoding

  •  

4

 

DTU Compute

11 June 2019

McEliece Cryptosystem

5 of 18

 

5

 

 

 

 

 

 

 

 

 

 

 

 

DTU Compute

11 June 2019

McEliece Cryptosystem

6 of 18

Why end there?

6

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

DTU Compute

11 June 2019

McEliece Cryptosystem

7 of 18

Why end there?

7

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

DTU Compute

11 June 2019

McEliece Cryptosystem

8 of 18

 

  •  

8

Original

​

Expansion

​

​

​

​

​

 

Example:

DTU Compute

11 June 2019

McEliece Cryptosystem

9 of 18

 

  •  

9

 

Example:

Original

​

Expansion

​

​

​

​

​

DTU Compute

11 June 2019

McEliece Cryptosystem

10 of 18

Idea 2: Smaller baselists in BJMM

10

 

 

 

 

 

 

 

 

 

DTU Compute

11 June 2019

McEliece Cryptosystem

11 of 18

Idea 2: Smaller baselists in BJMM

11

 

 

 

 

 

 

 

 

 

 

 

DTU Compute

11 June 2019

McEliece Cryptosystem

12 of 18

Idea 2: Smaller baselists in BJMM

12

 

 

 

 

 

 

01|10|00|11

 

 

DTU Compute

11 June 2019

McEliece Cryptosystem

13 of 18

Idea 2: Smaller baselists in BJMM

13

01|10|00|11

 

 

 

 

 

 

00|10|00|01

01|00|00|10

 

 

DTU Compute

11 June 2019

McEliece Cryptosystem

14 of 18

Idea 2: Smaller baselists in BJMM

14

01|10|00|11

 

 

 

 

 

 

00|10|00|01

01|00|00|10

00|10|00|00

00|00|00|01

01|00|00|00

00|00|00|10

 

 

 

DTU Compute

11 June 2019

McEliece Cryptosystem

15 of 18

Idea 3: Solve in the Trace Code

  •  

15

Original

​

Expansion

​

Trace

​

​

​

DTU Compute

11 June 2019

McEliece Cryptosystem

16 of 18

 

16

 

 

 

 

Original

​

Expansion

​

Trace

​

​

​

 

 

 

 

DTU Compute

11 June 2019

McEliece Cryptosystem

17 of 18

Results

17

 

Trace code

Trace of n-k

Expanded code

Prange

Small Base BJMM

BJMM 2 level

BJMM 3 level

 

Code rate

Complexity Coefficient

Code rate

Complexity Coefficient

DTU Compute

11 June 2019

McEliece Cryptosystem

18 of 18

Conclusion

  •  

18

 

DTU Compute

11 June 2019

McEliece Cryptosystem