On the Security of the Hashing Scheme Based on SL_2

Kanat Abdukhalikov; Chul Kim

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

On the Security of the Hashing Scheme Based on SL_2

Kanat Abdukhalikov, Chul Kim

Department of Mathematical Sciences

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

Abstract

Tillich and Zémor proposed a hashing scheme based on the group of unimodular matrices SL_2(F_q) over a finite field F_q of q = 2^n elements. Charnes and Pieprzyk studied the security of this scheme. They showed that for n = 131 and for some irreducible polynomial P_{131}(x) this scheme is weak. We show that with sufficiently 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	Proceedings of 5th International Workshop, FSE’ 98 Paris, France, March 23–25, 1998
Publisher	Springer Berlin Heidelberg
ISBN (Print)	978-3-540-64265-7
DOIs	https://doi.org/10.1007/3-540-69710-1_7
Publication status	Published - 1998
Event	Fast Software Encryption, Springer Lecture Notes in Computer Science, Vol. 1372, pp. 93--102 - Paris, France Duration: Mar 1 1998 → …

Conference

Conference	Fast Software Encryption, Springer Lecture Notes in Computer Science, Vol. 1372, pp. 93--102
Period	3/1/98 → …

Access to Document

10.1007/3-540-69710-1_7

http://link.springer.com/chapter/10.1007/3-540-69710-1_7

Cite this

@inproceedings{fef44c204989436db368b7e0c9fe9bcb,

title = "On the Security of the Hashing Scheme Based on SL_2",

abstract = "Tillich and Z{\'e}mor proposed a hashing scheme based on the group of unimodular matrices SL_2(F_q) over a finite field F_q of q = 2^n elements. Charnes and Pieprzyk studied the security of this scheme. They showed that for n = 131 and for some irreducible polynomial P_{131}(x) this scheme is weak. We show that with sufficiently 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{\'e}mor hashing scheme for any finite field F_q and show that the new generalized scheme has similar properties.",

author = "Kanat Abdukhalikov and Chul Kim",

year = "1998",

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

language = "English",

isbn = "978-3-540-64265-7",

booktitle = "Proceedings of 5th International Workshop, FSE{\textquoteright} 98 Paris, France, March 23–25, 1998",

publisher = "Springer Berlin Heidelberg",

note = "Fast Software Encryption, Springer Lecture Notes in Computer Science, Vol. 1372, pp. 93--102 ; Conference date: 01-03-1998",

}

TY - GEN

T1 - On the Security of the Hashing Scheme Based on SL_2

AU - Abdukhalikov, Kanat

AU - Kim, Chul

PY - 1998

Y1 - 1998

N2 - Tillich and Zémor proposed a hashing scheme based on the group of unimodular matrices SL_2(F_q) over a finite field F_q of q = 2^n elements. Charnes and Pieprzyk studied the security of this scheme. They showed that for n = 131 and for some irreducible polynomial P_{131}(x) this scheme is weak. We show that with sufficiently 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.

AB - Tillich and Zémor proposed a hashing scheme based on the group of unimodular matrices SL_2(F_q) over a finite field F_q of q = 2^n elements. Charnes and Pieprzyk studied the security of this scheme. They showed that for n = 131 and for some irreducible polynomial P_{131}(x) this scheme is weak. We show that with sufficiently 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.

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

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

M3 - Conference contribution

SN - 978-3-540-64265-7

BT - Proceedings of 5th International Workshop, FSE’ 98 Paris, France, March 23–25, 1998

PB - Springer Berlin Heidelberg

T2 - Fast Software Encryption, Springer Lecture Notes in Computer Science, Vol. 1372, pp. 93--102

Y2 - 1 March 1998

ER -

On the Security of the Hashing Scheme Based on SL_2

Abstract

Conference

Access to Document

Fingerprint

Cite this