On the security of the hashing scheme based on SL2

Kanat S. Abdukhalikov; Chul Kim

doi:10.1007/3-540-69710-1_7

On the security of the hashing scheme based on SL₂

Kanat S. Abdukhalikov, Chul Kim

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

11 Citations (Scopus)

Abstract

Tillich and Zémor proposed a hashing scheme based on the group of unimodular matrices SL₂(F_q) over a finite field F_q of q = 2ⁿ elements. Charnes and Pieprzyk studied the security of this scheme. They showed that for n = 131 and for some irreducible polynomial P₁₃₁(x) this scheme is weak. We show that with suffciently high probability the polynomials P_n(x) can be chosen in such a way that this type of attack can be avoided. Futhermore, we generalize the Tillich-Zémor hashing scheme for any finite field F_q and show that the new generalized scheme has similar properties.

Original language	English
Title of host publication	Fast Software Encryption - 5th International Workshop, FSE 1998, Proceedings
Editors	Serge Vaudenay
Publisher	Springer Verlag
Pages	93-102
Number of pages	10
ISBN (Print)	354064265X, 9783540642657
DOIs	https://doi.org/10.1007/3-540-69710-1_7
Publication status	Published - 1998
Externally published	Yes
Event	5th International Workshop on Fast Software Encryption, FSE 1998 - Paris, France Duration: Mar 23 1998 → Mar 25 1998

Publication series

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

Other

Other	5th International Workshop on Fast Software Encryption, FSE 1998
Country/Territory	France
City	Paris
Period	3/23/98 → 3/25/98

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/3-540-69710-1_7

Cite this

Abdukhalikov, K. S., & Kim, C. (1998). On the security of the hashing scheme based on SL₂. In S. Vaudenay (Ed.), Fast Software Encryption - 5th International Workshop, FSE 1998, Proceedings (pp. 93-102). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1372). Springer Verlag. https://doi.org/10.1007/3-540-69710-1_7

On the security of the hashing scheme based on SL₂. / Abdukhalikov, Kanat S.; Kim, Chul.
Fast Software Encryption - 5th International Workshop, FSE 1998, Proceedings. ed. / Serge Vaudenay. Springer Verlag, 1998. p. 93-102 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1372).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abdukhalikov, KS & Kim, C 1998, On the security of the hashing scheme based on SL₂. in S Vaudenay (ed.), Fast Software Encryption - 5th International Workshop, FSE 1998, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1372, Springer Verlag, pp. 93-102, 5th International Workshop on Fast Software Encryption, FSE 1998, Paris, France, 3/23/98. https://doi.org/10.1007/3-540-69710-1_7

Abdukhalikov KS, Kim C. On the security of the hashing scheme based on SL₂. In Vaudenay S, editor, Fast Software Encryption - 5th International Workshop, FSE 1998, Proceedings. Springer Verlag. 1998. p. 93-102. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-69710-1_7

@inproceedings{43668b4c7a4c4ea3ad5a718bebe7449b,

title = "On the security of the hashing scheme based on SL2",

abstract = "Tillich and Z{\'e}mor proposed a hashing scheme based on the group of unimodular matrices SL2(Fq) over a finite field Fq of q = 2n elements. Charnes and Pieprzyk studied the security of this scheme. They showed that for n = 131 and for some irreducible polynomial P131(x) this scheme is weak. We show that with suffciently high probability the polynomials Pn(x) can be chosen in such a way that this type of attack can be avoided. Futhermore, we generalize the Tillich-Z{\'e}mor hashing scheme for any finite field Fq and show that the new generalized scheme has similar properties.",

author = "Abdukhalikov, {Kanat S.} and Chul Kim",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1998.; 5th International Workshop on Fast Software Encryption, FSE 1998 ; Conference date: 23-03-1998 Through 25-03-1998",

year = "1998",

doi = "10.1007/3-540-69710-1_7",

language = "English",

isbn = "354064265X",

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

publisher = "Springer Verlag",

pages = "93--102",

editor = "Serge Vaudenay",

booktitle = "Fast Software Encryption - 5th International Workshop, FSE 1998, Proceedings",

}

TY - GEN

T1 - On the security of the hashing scheme based on SL2

AU - Abdukhalikov, Kanat S.

AU - Kim, Chul

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1998.

PY - 1998

Y1 - 1998

N2 - Tillich and Zémor proposed a hashing scheme based on the group of unimodular matrices SL2(Fq) over a finite field Fq of q = 2n elements. Charnes and Pieprzyk studied the security of this scheme. They showed that for n = 131 and for some irreducible polynomial P131(x) this scheme is weak. We show that with suffciently high probability the polynomials Pn(x) can be chosen in such a way that this type of attack can be avoided. Futhermore, we generalize the Tillich-Zémor hashing scheme for any finite field Fq and show that the new generalized scheme has similar properties.

AB - Tillich and Zémor proposed a hashing scheme based on the group of unimodular matrices SL2(Fq) over a finite field Fq of q = 2n elements. Charnes and Pieprzyk studied the security of this scheme. They showed that for n = 131 and for some irreducible polynomial P131(x) this scheme is weak. We show that with suffciently high probability the polynomials Pn(x) can be chosen in such a way that this type of attack can be avoided. Futhermore, we generalize the Tillich-Zémor hashing scheme for any finite field Fq and show that the new generalized scheme has similar properties.

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

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

U2 - 10.1007/3-540-69710-1_7

DO - 10.1007/3-540-69710-1_7

M3 - Conference contribution

AN - SCOPUS:34547467291

SN - 354064265X

SN - 9783540642657

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

SP - 93

EP - 102

BT - Fast Software Encryption - 5th International Workshop, FSE 1998, Proceedings

A2 - Vaudenay, Serge

PB - Springer Verlag

T2 - 5th International Workshop on Fast Software Encryption, FSE 1998

Y2 - 23 March 1998 through 25 March 1998

ER -