1A silent competition for ultrafast public key cryptography

Presented by
Danilo Gligoroski
Department of Telematics,
Faculty of Information Technology, Mathematics and Electrical Engineering
Norwegian University of Science and TechnologyTechnology - NTNU, NORWAY

Rump Session, CRYPTO 2011, A silent competition for ultra-fast public key cryptography

2Raising the awareness:
There is an ongoing silent
competition for ultra-fastpublic key primitives

Rump Session, CRYPTO 2011, A silent competition for ultra-fast public key cryptography

3

What is a loudcryptographic competition?

Rump Session, CRYPTO 2011, A silent competition for ultra-fast public key cryptography

4

SHA-3 competition before the NIST
announcement for the finalists

Round 1

Rump Session, CRYPTO 2011, A silent competition for ultra-fast public key cryptography

5

SHA-3 competition before the NIST
announcement for the finalists

Round 2

Rump Session, CRYPTO 2011, A silent competition for ultra-fast public key cryptography

6

What does it mean: Ultrafast public key primitives?

Rump Session, CRYPTO 2011, A silent competition for ultra-fast public key cryptography

7Search Google images for:ultra fast

Rump Session, CRYPTO 2011, A silent competition for ultra-fast public key cryptography

8Search Google images for:ultra fast

Rump Session, CRYPTO 2011, A silent competition for ultra-fast public key cryptography

9Search Google images for:ultra fast

Rump Session, CRYPTO 2011, A silent competition for ultra-fast public key cryptography

10Look at SUPERCOP for
Measurements of public-key
signature systems

Rump Session, CRYPTO 2011, A silent competition for ultra-fast public key cryptography

11

Beside well established andtrusted RSA, DSA and ECDSA
Primitive

donald512donald1024
donald2048

ecdonaldb163...

Description
DSA signatures using a 512-bit prime
DSA signatures using a 1024-bit prime
DSA signatures using a 2048-bit prime
ECDSA signatures using the standard NIST B163 elliptic curve, a curve over a field of size
2^163
...

ronald512

ECDSA signatures using the standard NIST P521 elliptic curve, a curve modulo the prime2^521-1
512-bit RSA signatures with message recovery

...

...

ronald4096

4096-bit RSA signatures with message
recoveryecdonaldp521

Rump Session, CRYPTO 2011, A silent competition for ultra-fast public key cryptography

12A lot of other designs
Primitive

DescriptionDesigners

1. 3icp

3-invertible cycle with minus and prefix

Jintai Ding
Christopher Wolf
Bo-Yin Yang

2. blsBoneh–Lynn–Shacham: Pairing-based
short signatures

Michael Scott

EdDSA signatures using Curve25519

Daniel J. Bernstein
Niels DuifTanja Lange
Peter Schwabe
Bo-Yin Yang

3. ed25519

Hyperelliptic Curve with Two-Rank One:
Signatures using a genus-2 hyperelliptic Peter Birkner
4. hector
curve of 2-rank 1 over a field of sizePeter Schwabe
2^113
Danilo Gligoroski
Rune Steinsmo ØdegardRune Erlend Jensen
160 - 256 bit signatures based on
5. mqqsig160 – mqqsig256
Ludovic Perret
Multivariate-Quadratic-Quasigroups
Jean-Charles Fauge`reSvein Johan Knapskog
Smile Markovski
Rump Session, CRYPTO 2011, A silent competition for ultra-fast public key cryptography

13

A lot of other designs
Primitive
6.

pflash1

7.

rainbow

8.

rainbow5640 & rainbow6440

9.

rainbowbinary16242020 &256181212

10. rwb0fuz1024

Description
Designers
C*- with a prefix over GF16 designed to match Jintai Ding
SFLASH
Bo-Yin Yang
Jintai Ding
Rainbow multivariate-quadratic signatures
Dieter Schmidt
Jintai Ding
Rainbow over GF31
Bo-Yin Yang
Rainbow over GF16

Bo-Yin Yang

1024-bit Rabin-Williams signatures withcompression

Adam Langley (Google)

11. sflashv2

SFLASHv2 multivariate-quadratic signatures

12. tts6440

Rainbow over GF16

Louis Goubin
Nicolas Courtois
Thomas Icart
Bo-Yin Yang

Rump Session, CRYPTO 2011, A silent competition for ultra-fast public key cryptography

14So, what does it mean: Ultrafast public key primitives?
They are also verysafe, as this two.

Rump Session, CRYPTO 2011, A silent competition for ultra-fast public key cryptography

15

amd64; Sandy Bridge (206a7); 2011
Intel Core i7-2600K; 4 x 3400MHz;
threads; sandy0, supercop-20110708
Cycles to sign 59 bytes
quartile
medianquartile
systemmqqsig224
5028
5032
5040
mqqsig256
5044
5052
5060
mqqsig160
5564
5616
5652
mqqsig192
7424
7476
7520
rainbowbinary256181212
21348
21404
21488
tts6440
44772
44860
44944
rainbowbinary16242020
48176
48560
49004
ed25519
71984
72068
72280
rainbow5640
75628
75796
78076
sflashv2
100872
101088101264
rainbow6440
128356
128516132340donald512
233836237392240488ronald512
513472525092537420donald1024
555784562480570192
rainbow
580932582392584072
ecdonaldp160
726780734420739864ronald768
958388968972
9846683icp
328804995116 1704396
ecdonaldp224
1149144 1156900 1165640
pflash1708052 1208212 2203320

quartile
1283164
13242881360532
162504416571121752932
2379704
25243722783164
3904204
513642056059805858976767795611096908
122961282158780023877492
26748216
47030164

Cycles to sign 59 bytes
medianquartile
1297996 1306580
1337120 1343664
1371852 1380548
1637744 1655040
1665588 1679752
1761496 1775448
2388496 2395188
2533704 2543676
2796580 2817992
3922324 3953112
5157552 5174616
5629004 5642988
5888580 5918352
7725364 7787476
11127692 11162296
12321440 12349988
21683476 21818548
23920456 23994632
26795812 26865356
47083916 47179400

systemecdonaldp192
ecdonaldp256
donald2048
ronald1024
ecdonaldk163

ecdonaldb163
New designs vs RSA orECC
ecdonaldk233
ecdonaldb233
10, 100, 1000, 5000 times
fasterecdonaldp384

ronald1536
ecdonaldk283
ecdonaldb283
ecdonaldp521
ronald2048
ecdonaldk409
ecdonaldb409
ronald3072
ecdonaldk571
ecdonaldb571
ronald4096

Rump Session, CRYPTO 2011, A silent competition for ultra-fast public key cryptography

16

Why we should be interested
about ultra-fast public key crypto?

Rump Session, CRYPTO 2011, A silent competition for ultra-fast public key cryptography

17

Why we should be interestedabout ultra-fast public key crypto?

Because they fit nice with thescalability of the future Internetof Things, where billions ofpetabytes will have to beprocessed, authenticated,digitally signed, …
Rump Session, CRYPTO 2011, A silent competition for ultra-fast public key cryptography

18

Advertisement!
Beside MQQ-SIG, soon expect to see:••••

MQQ-SIG with smaller public keys,
MQQ-ENC (encryption),
MQQ-ID (Identification schemes),
MQQ-IBE (first Multivariate Quadratic Identity
Based Encryption scheme).

• Cryptographers: Please look at them and try to
break them!

Rump Session, CRYPTO 2011, A silent competition for ultra-fast public key cryptography

19

Rump Session, CRYPTO 2011, A silent competition for ultra-fast public key cryptography