On the trace based public key cryptosystems over finite fields

---

Tezin Türü: Doktora

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Uygulamalı Matematik Enstitüsü, Türkiye

Tezin Onay Tarihi: 2013

Öğrenci: MUHAMMAD ASHRAF

Danışman: ERSAN AKYILDIZ

Özet:

In this thesis, the trace based Public Key Cryptosystems (PKC) are explored from theoretical and implementation point of view. We will introduce cryptographic protocols for the ones they are not discussed yet. We introduce improved trace based exponentiation algorithm for fifth degree recursive relation. The Discrete Log Problem (DLP), that is computing $x$, given $y=\alpha^x$ and $<\alpha>=G\subset \F_q^*$, based Public Key Cryptosystems (PKC) are being studied since late 1970's. Such development of PKC was possible because of the trapdoor function $f:\Z_\ell\rightarrow G=<\alpha>\subset \F_q^*$, $f(m)=\alpha^m$, is a group homomorphism. Due to this fact, we have Diffie Hellman (DH) type key exchange, ElGamal type message encryption, and Nyberg Rueppel type digital signature protocols. The cryptosystems based on the trapdoor $f(m)=\alpha^m$ are well understood and complete. However, there is another trapdoor function $f:\Z_\ell\rightarrow G$, $f(m)\rightarrow Tr(\alpha^m)$, where $G=<\alpha>\subset \F_{q^k}^*,\; k\ge 2$, which needs more attention from cryptographic protocols point of view. There are some works for a more efficient algorithm to compute $f(m)=Tr(\alpha^m)$ and not wondering about the protocols. There are also some works dealing with an efficient algorithm to compute $Tr(\alpha^m)$ as well as discussing the cryptographic protocols. In this thesis these works are studied along with introduction of some protocols which are not discussed earlier and trace based exponentiation for fifth degree recursive relation is improved.