New differential-algebraic attacks and reparametrization of rainbow

Jintai Ding; Bo Yin Yang; Chia Hsin Owen Chen; Ming Shing Chen; Chen Mou Cheng

doi:10.1007/978-3-540-68914-0_15

New differential-algebraic attacks and reparametrization of rainbow

Jintai Ding^*, Bo Yin Yang, Chia Hsin Owen Chen, Ming Shing Chen, Chen Mou Cheng

^*Corresponding author for this work

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

87 Citations (Scopus)

Abstract

A recently proposed class of multivariate Public-Key Cryptosystems, the Rainbow-Like Digital Signature Schemes, in which successive sets of central variables are obtained from previous ones by solving linear equations, seem to lead to efficient schemes (TTS, TRMS, and Rainbow) that perform well on systems of low computational resources. Recently SFLASH (C^{* -}) was broken by Dubois, Fouque, Shamir, and Stern via a differential attack. In this paper, we exhibit similar algebraic and diffential attacks, that will reduce published Rainbow-like schemes below their security levels. We will also discuss how parameters for Rainbow and TTS schemes should be chosen for practical applications.

Original language	English
Title of host publication	Applied Cryptography and Network Security - 6th International Conference, ACNS 2008, Proceedings
Pages	242-257
Number of pages	16
DOIs	https://doi.org/10.1007/978-3-540-68914-0_15
Publication status	Published - 2008
Externally published	Yes
Event	6th International Conference on Applied Cryptography and Network Security, ACNS 2008 - New York, NY, United States Duration: 3 Jun 2008 → 6 Jun 2008

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5037 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	6th International Conference on Applied Cryptography and Network Security, ACNS 2008
Country/Territory	United States
City	New York, NY
Period	3/06/08 → 6/06/08

Keywords

Algebraic attack
Differential attack
Oil-and-vinegar
Rank

Access to Document

10.1007/978-3-540-68914-0_15

Cite this

Ding, J., Yang, B. Y., Chen, C. H. O., Chen, M. S., & Cheng, C. M. (2008). New differential-algebraic attacks and reparametrization of rainbow. In Applied Cryptography and Network Security - 6th International Conference, ACNS 2008, Proceedings (pp. 242-257). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5037 LNCS). https://doi.org/10.1007/978-3-540-68914-0_15

Ding, Jintai ; Yang, Bo Yin ; Chen, Chia Hsin Owen et al. / New differential-algebraic attacks and reparametrization of rainbow. Applied Cryptography and Network Security - 6th International Conference, ACNS 2008, Proceedings. 2008. pp. 242-257 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{13d01e793d524a559b1be5575076cd55,

title = "New differential-algebraic attacks and reparametrization of rainbow",

abstract = "A recently proposed class of multivariate Public-Key Cryptosystems, the Rainbow-Like Digital Signature Schemes, in which successive sets of central variables are obtained from previous ones by solving linear equations, seem to lead to efficient schemes (TTS, TRMS, and Rainbow) that perform well on systems of low computational resources. Recently SFLASH (C* -) was broken by Dubois, Fouque, Shamir, and Stern via a differential attack. In this paper, we exhibit similar algebraic and diffential attacks, that will reduce published Rainbow-like schemes below their security levels. We will also discuss how parameters for Rainbow and TTS schemes should be chosen for practical applications.",

keywords = "Algebraic attack, Differential attack, Oil-and-vinegar, Rank",

author = "Jintai Ding and Yang, {Bo Yin} and Chen, {Chia Hsin Owen} and Chen, {Ming Shing} and Cheng, {Chen Mou}",

year = "2008",

doi = "10.1007/978-3-540-68914-0_15",

language = "English",

isbn = "3540689133",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "242--257",

booktitle = "Applied Cryptography and Network Security - 6th International Conference, ACNS 2008, Proceedings",

note = "6th International Conference on Applied Cryptography and Network Security, ACNS 2008 ; Conference date: 03-06-2008 Through 06-06-2008",

}

Ding, J, Yang, BY, Chen, CHO, Chen, MS & Cheng, CM 2008, New differential-algebraic attacks and reparametrization of rainbow. in Applied Cryptography and Network Security - 6th International Conference, ACNS 2008, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5037 LNCS, pp. 242-257, 6th International Conference on Applied Cryptography and Network Security, ACNS 2008, New York, NY, United States, 3/06/08. https://doi.org/10.1007/978-3-540-68914-0_15

New differential-algebraic attacks and reparametrization of rainbow. / Ding, Jintai; Yang, Bo Yin; Chen, Chia Hsin Owen et al.
Applied Cryptography and Network Security - 6th International Conference, ACNS 2008, Proceedings. 2008. p. 242-257 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5037 LNCS).

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

TY - GEN

T1 - New differential-algebraic attacks and reparametrization of rainbow

AU - Ding, Jintai

AU - Yang, Bo Yin

AU - Chen, Chia Hsin Owen

AU - Chen, Ming Shing

AU - Cheng, Chen Mou

PY - 2008

Y1 - 2008

N2 - A recently proposed class of multivariate Public-Key Cryptosystems, the Rainbow-Like Digital Signature Schemes, in which successive sets of central variables are obtained from previous ones by solving linear equations, seem to lead to efficient schemes (TTS, TRMS, and Rainbow) that perform well on systems of low computational resources. Recently SFLASH (C* -) was broken by Dubois, Fouque, Shamir, and Stern via a differential attack. In this paper, we exhibit similar algebraic and diffential attacks, that will reduce published Rainbow-like schemes below their security levels. We will also discuss how parameters for Rainbow and TTS schemes should be chosen for practical applications.

AB - A recently proposed class of multivariate Public-Key Cryptosystems, the Rainbow-Like Digital Signature Schemes, in which successive sets of central variables are obtained from previous ones by solving linear equations, seem to lead to efficient schemes (TTS, TRMS, and Rainbow) that perform well on systems of low computational resources. Recently SFLASH (C* -) was broken by Dubois, Fouque, Shamir, and Stern via a differential attack. In this paper, we exhibit similar algebraic and diffential attacks, that will reduce published Rainbow-like schemes below their security levels. We will also discuss how parameters for Rainbow and TTS schemes should be chosen for practical applications.

KW - Algebraic attack

KW - Differential attack

KW - Oil-and-vinegar

KW - Rank

UR - http://www.scopus.com/inward/record.url?scp=45749150774&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-68914-0_15

DO - 10.1007/978-3-540-68914-0_15

M3 - Conference Proceeding

AN - SCOPUS:45749150774

SN - 3540689133

SN - 9783540689133

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 242

EP - 257

BT - Applied Cryptography and Network Security - 6th International Conference, ACNS 2008, Proceedings

T2 - 6th International Conference on Applied Cryptography and Network Security, ACNS 2008

Y2 - 3 June 2008 through 6 June 2008

ER -

Ding J, Yang BY, Chen CHO, Chen MS, Cheng CM. New differential-algebraic attacks and reparametrization of rainbow. In Applied Cryptography and Network Security - 6th International Conference, ACNS 2008, Proceedings. 2008. p. 242-257. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-68914-0_15

New differential-algebraic attacks and reparametrization of rainbow

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this