Partial Key Exposure Attacks on BIKE, Rainbow, and NTRU
P
a
r
t
i
a
l
K
e
y
E
x
p
o
s
u
r
e
A
t
t
a
c
k
s
o
n
B
I
K
E
,
R
a
i
n
b
o
w
a
n
d
N
T
R
U
A
n
d
r
e
E
s
s
e
r
A
l
e
x
a
n
d
e
r
M
a
y
J
a
v
i
e
r
V
e
r
b
e
l
W
e
i
q
i
a
n
g
W
e
n
@
C
R
Y
P
T
O
2
0
2
2
,
S
a
n
t
a
B
a
r
b
a
r
a
M
o
t
i
v
a
t
i
o
n
2
N
e
w
a
t
t
a
c
k
s
a
n
d
b
o
u
n
d
s
o
n
r
e
q
u
i
r
e
d
l
e
a
k
a
g
e
3
M
e
t
h
o
d
o
l
o
g
y
How to model leakage?
Errors / Erasures
Asymptotic leakage bounds (poly-time)
Practical leakage bounds
R
a
i
n
b
o
w
,
B
I
K
E
a
n
d
N
T
R
U
4
5
S
e
c
r
e
t
K
e
y
s
R
a
i
n
b
o
w
B
I
K
E
N
T
R
U
quadratic
redundancy
linear
redundancy
least
redundancy
no intrinsic shortcut
but stores some extra
information
for efficiency
6
I
n
f
o
r
m
a
t
i
o
n
S
e
t
D
e
c
o
d
i
n
g
[
P
r
a
n
g
e
‘
6
2
]
B
I
K
E
0
e
s
6
I
n
f
o
r
m
a
t
i
o
n
S
e
t
D
e
c
o
d
i
n
g
[
P
r
a
n
g
e
‘
6
2
]
B
I
K
E
0
0 0 0 0 0 0 0 0 0 0 0 0
6
I
n
f
o
r
m
a
t
i
o
n
S
e
t
D
e
c
o
d
i
n
g
[
P
r
a
n
g
e
‘
6
2
]
B
I
K
E
0
Solve linear
system
0 0 0 0 0 0 0 0 0 0 0 0
Guess other
set of zeros
e
s
0 0 0 0 0 0 0 0 0 0 0 0 0
T
h
e
E
r
a
s
u
r
e
M
o
d
e
l
7
T
h
e
E
r
r
o
r
M
o
d
e
l
1 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 1 0 0 1 0 0 1 1 1 01 1 0 1 1 1 0
Erased key
1 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 1 0 0 1 0 0 1 1 1 01 1 0 1 1 1 0
? ? ?
? ?
?
?
?
?
? ?
? ?
?
?
? ? ?
E
rasure-probability:
8
9
A
s
y
m
p
t
o
t
i
c
B
o
u
n
d
s
0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1
0, 11, 14
0 1 -1 -1 0
0 1 0 0 1 0 0
packed:
unpacked:
linear / quadratic
systems due to
key relations
10
A
s
y
m
p
t
o
t
i
c
-
B
I
K
E
1 0
?
0 0 0
?
0 0 0 0
?
1 0 … … … … … 0 0 0
?
0 0 0
?
0 1
?
?
0 0 0 0
BIKE secret key satisfies n/2 known linear equations: As = e
standard
compact
1 0 1
?
1 0
0
?
0
?
1 0
0
?
1
1 0 1
0 1 0 1
?
1
solve linear system
solve linear system
?
?
?
?
?
? ?
?
?
?
?
?
?
?
42, 46, 2, 6, 18, 22 …
11
P
r
a
c
t
i
c
a
l
B
o
u
n
d
s
lattice reduction
Enumeration usually
less than 0.01
ISD (accelerated)
linear / quadratic system
E
r
a
s
u
r
e
s
-
B
I
K
E
1 0
?
0 0 0
?
0 0 0 0
?
1 0 … … … … … 0 0 0
?
0 0 0
?
0 1
?
?
0 0 0 0
standard
solve via ISD
?
?
?
?
?
? ?
reduce weight + remove zeros
0
1
0 0 0 0 0 0 0 0 0
1
0
0
0
0 0 0 0 0 0 0 0 0
1
0 0
0
0 0 0 0 0 0 0 0 0
0
0 0
? ? ? ? ? ? ? ? ? ? ? ? ?
15
E
r
a
s
u
r
e
s
-
B
I
K
E
1 0
?
0 0 0
?
0 0 0 0
?
1 0 … … … … … 0 0 0
?
0 0 0
?
0 1
?
?
0 0 0 0
standard
compact
1 0 1
?
1 0
1
?
0
?
1 0
0
?
1
1 0 1
0 1 0 1
?
1
solve via ISD
?
?
?
?
?
? ?
?
?
?
?
?
?
reduce weight + remove zeros :
solve via ISD
T
h
e
E
r
r
o
r
M
o
d
e
l
12
L
e
a
k
a
g
e
m
o
d
e
l
s
1 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 1 0 0 1 0 0 1 1 1 01 1 0 1 1 1 0
Secret key
Erroneous Key
1
0
1
0
1
0
0
0
1
0
0
1
0
0
0
0
0
1
1
1
1
0
1
1
0
1
1
0
0
0
0
0
1
0
0
0
1
1
1
1
1
0
0
Error
-probability:
(symmetric)
(asymmetric)
13
14
A
s
y
m
p
t
o
t
i
c
B
o
u
n
d
s
Information
Set Decoding
15
A
s
y
m
p
t
o
t
i
c
-
B
I
K
E
standard
compact
0
1
0
0
0
0
1
0
1
0
1
1
1
0
0
0
1
…
…
…
…
…
0
0
0
1
0
0
0
1
0
1
0
0
0
0
solve via ISD
1
0
1
0
1
0
1
1
0
1
1
0
0
0
1
1
0
1
0
1
0
1
1
1
1.
Enumerate small-weight errors
list of candidates
2.
but sample zeros only from non-candidates
solve via ISD
16
P
r
a
c
t
i
c
a
l
B
o
u
n
d
s
lattice reduction /
meet-in-the-middle
Enumeration usually
less than 0.001 / 0.01
ISD
(accelerated)
ISD + quadratic system
21
P
r
a
c
t
i
c
a
l
-
B
I
K
E
standard
compact
0
1
0
0
0
0
1
0
1
0
1
1
1
0
0
0
1
…
…
…
…
…
0
0
0
1
0
0
0
1
0
1
0
0
0
0
b
u
t
s
a
m
p
l
e
m
o
s
t
z
e
r
o
s
f
r
o
m
(
a
n
d
)
0
solve via ISD
0
1
0
1
0
1
0
1
1
0
1
1
0
0
0
1
1
0
1
0
1
0
1
1
1
1.
E
n
u
m
e
r
a
t
e
c
a
n
d
i
d
a
t
e
s
w
i
t
h
h
i
g
h
p
r
o
b
a
b
i
l
i
t
y
2.
b
u
t
s
a
m
p
l
e
m
o
s
t
z
e
r
o
s
f
r
o
m
n
o
n
-
c
a
n
d
i
d
a
t
e
s
solve via ISD
17
C
o
n
c
l
u
s
i
o
n
Non-trivial polynomial time recovery
Even higher practical bounds
Comparable to non-post-quantum systems
P
Q
C
d
o
e
s
n
o
t
p
e
r
s
e
e
n
j
o
y
l
e
a
k
a
g
e
r
e
s
i
s
t
a
n
c
e
Explore the vulnerability of PQC candidates to partial key exposure attacks in schemes like BIKE, Rainbow, and NTRU. Learn about leakage resistance, modeling leakage, practical bounds, and secret key decoding methods. Dive into the erasure and error models, analyzing the security of secret keys in varying scenarios.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Partial Key Exposure Attacks on BIKE, Rainbow and NTRU Andre Esser Alexander May Javier Verbel Weiqiang Wen @ CRYPTO 2022, Santa Barbara
Motivation Are PQC candidates leakage resistant? ?-bit key, -bit leaked security of (? ) -bit key? Best known: Enumeration attacks No use of key-redundancy / structure New attacks and bounds on required leakage 2
Methodology How to model leakage? Errors / Erasures Asymptotic leakage bounds (poly-time) Practical leakage bounds 3
Secret Keys Rainbow BIKE NTRU ? ?/2 Vector ? ?3 Vector ?,? ?2 ?2 with few 1 s Matrices over ??: ?/2 ? 0 0 ?1 ? 0 ?2 ?3 ? ? 1=? ? ? , ? 1= 0 Satisfies: ?? = ? Satisfies: ?? = ? ? or ? suffice no intrinsic shortcut Row of ? and constant columns of ?1 suffice for full recovery but stores some extra information for efficiency 5
Information Set Decoding [Prange 62] BIKE Secret key ?,? ?2 Satisfies: ?? = ? and has ? entries equal to 1 (??/2 ?) (?,?) = 0?/2 ?/2 ?2 ?/2 ??/2 ? 0 = e s 6
Information Set Decoding [Prange 62] BIKE Secret key ?,? ?2 Satisfies: ?? = ? and has ? entries equal to 1 ?/2 ?2 ?/2 ??/2 ? 0 = 0 0 0 0 0 0 0 0 0 0 0 0 ? 2 6
Information Set Decoding [Prange 62] BIKE Secret key ?,? ?2 Satisfies: ?? = ? and has ? entries equal to 1 ?/2 ?2 ?/2 0 = ? 0 0 0 0 0 0 0 0 0 0 0 0 e 0 0 0 0 0 0 0 0 0 0 0 0 0 s ? 2 weight ? 6
The Error Model Secret key (?-bits) 1 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 1 0 0 1 0 0 1 1 1 01 1 0 1 1 1 0 Erased key 1 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 1 0 0 1 0 0 1 1 1 01 1 0 1 1 1 0 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? Erasure-probability: Pr[ ] = Pr[ ] = p 0 ? 1 ? 8
Asymptotic Bounds Number of Erasures Setting first layer ? ?(?) ? 0 0 ?1 ? 0 ?2 ?3 ? ? 1=? ? ? , ? 1= linear / quadratic Rainbow 0 full key ? ? 2 ? 11 standard 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 systems due to key relations BIKE compact 0, 11, 14 NTRU (un) packed unpacked: 0 1 -1 -1 0 0 1 0 0 1 0 0 3? packed: 9
Asymptotic - BIKE BIKE secret key satisfies n/2 known linear equations: As = e standard ? ? ? ? 1 0 ? 0 0 0 ? 0 0 0 0 ? 1 0 0 0 0 ? 0 0 0 ? 0 1 ? ? 0 0 0 0 ? ? ? ? 2 Less than n/2 : solve linear system ? ? 11 compact 1 0 1 ? 1 0 0 ? 0 ? 1 0 ? 0 ? 1 1 0 1 ? 0 1 0 1 ? 1 ? ? ? ? log ? ? 42, 46, 2, 6, 18, 22 1. Enumerate all ? 2. If less than ?/2 candidates ?/2 zeros known : solve linear system 10
Practical Bounds Category I Parameters Setting 60-bit complexity linear / quadratic system Rainbow full key 0.81 standard 0.65 ISD (accelerated) BIKE compact 0.43 unpacked 0.30 lattice reduction NTRU packed 0.09 11
Leakage models Secret key 1 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 1 0 0 1 0 0 1 1 1 01 1 0 1 1 1 0 Erroneous Key 1 0 1 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 1 1 1 0 1 1 0 1 1 0 0 0 0 0 1 0 0 01 1 1 1 1 0 0 Error-probability: Pr[ ] = Pr[ ] = p 0 1 (symmetric) (asymmetric) 1 0 Pr[ ] =0.001, Pr[ ] = p 0 1 1 0 13
Asymptotic Bounds Number of Errors Setting first layer log2? Rainbow full key log ? Information Set Decoding standard ? log ? ? log2? BIKE compact NTRU (un) packed log ? 14
Asymptotic - BIKE standard 0 1 0 0 0 0 1 0 1 0 1 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 0 solve via ISD but sample zeros only from (and ) 0 0 compact 1 0 1 0 1 0 1 1 0 1 1 0 0 0 1 1 0 1 0 1 0 1 1 1 log ? ? 1. Enumerate small-weight errors list of candidates 2. but sample zeros only from non-candidates solve via ISD 15
Practical Bounds 60-bit complexity sym Category I Parameters Setting asym ISD + quadratic system Rainbow full key 0.19 0.38 standard 0.12 0.15 ISD (accelerated) BIKE compact 0.06 0.24 unpacked lattice reduction / meet-in-the-middle 0.01 0.10 NTRU packed 0.01 0.02 16
Conclusion Non-trivial polynomial time recovery Even higher practical bounds Comparable to non-post-quantum systems PQC does not per se enjoy leakage resistance 17
