| Title |
Vienos vienkryptės funkcijos saugumo ir efektyvumo analizė / |
| Translation of Title |
The security and efficiency investigation of certain on-way function. |
| Authors |
Vitkus, Paulius |
| Full Text |
|
| Pages |
74 |
| Keywords [eng] |
cryptography ; one-way function ; Burau representation ; braid groups ; Groebner bases |
| Abstract [eng] |
For creating cryptographic protocols secure and efficient one-way function is needed. In this decade we saw several one-way functions based on braid groups being proposed. However recently those functions were shown to have security flaws and the use of braid groups in cryptography was set under suspicion. In this work we take a new look at braid group cryptography and propose a certain one-way function based in Burau representation level of braid groups. Function parameters are set with the respect to efficient computer memory usage and it can be compared with the security of AES encryption system with 128 bit cryptographic keys. The security of proposed one-way function is based on the complexity of solving underdefined systems of multivariate quadratic polynomial equations over finite fields. This problem is NP-complete even if all the equations are quadratic and the field is GF(2). The classical algorithm for solving such systems is Buchberger’s algorithm for constructing Groebner bases. It is shown that in our case Buchberger’s algorithms running time is at least exponential. |
| Type |
Master thesis |
| Language |
Lithuanian |
| Publication date |
2009 |
