Computing discrete logarithms in cryptographically-interesting characteristic-three finite fields
Gora Adj Isaac Canales-Martínez Nareli Cruz-Cortés Alfred Menezes Thomaz Oliveira Luis Rivera-Zamarripa Francisco Rodríguez-Henríquez
Advances in Mathematics of Communications 2018, 12(4): 741-759 doi: 10.3934/amc.2018044

Since 2013 there have been several developments in algorithms for computing discrete logarithms in small-characteristic finite fields, culminating in a quasi-polynomial algorithm. In this paper, we report on our successful computation of discrete logarithms in the cryptographically-interesting characteristic-three finite field $\mathbb{F}_{3^{6.509}}$    using these new algorithms; prior to 2013, it was believed that this field enjoyed a security level of 128 bits. We also show that a recent idea of Guillevic can be used to compute discrete logarithms in the cryptographically-interesting finite field $\mathbb{F}_{3^{6.709}}$    using essentially the same resources as we expended on the $\mathbb{F}_{3^{6.509}}$    computation. Finally, we argue that discrete logarithms in the finite field $\mathbb{F}_{3^{6.1429}}$    can feasibly be computed today; this is significant because this cryptographically-interesting field was previously believed to enjoy a security level of 192 bits.

keywords: Discrete logarithm problem finite fields pairing-based cryptography
Another look at security definitions
Neal Koblitz Alfred Menezes
Advances in Mathematics of Communications 2013, 7(1): 1-38 doi: 10.3934/amc.2013.7.1
We take a critical look at security models that are often used to give "provable security" guarantees. We pay particular attention to digital signatures, symmetric-key encryption, and leakage resilience. We find that there has been a surprising amount of uncertainty about what the "right" definitions might be. Even when definitions have an appealing logical elegance and nicely reflect certain notions of security, they fail to take into account many types of attacks and do not provide a comprehensive model of adversarial behavior.
keywords: provable security Cryptography definitions.
Another look at generic groups
Neal Koblitz Alfred Menezes
Advances in Mathematics of Communications 2007, 1(1): 13-28 doi: 10.3934/amc.2007.1.13
Starting with Shoup's seminal paper [24], the generic group model has been an important tool in reductionist security arguments. After an informal explanation of this model and Shoup's theorem, we discuss the danger of flaws in proofs. We next describe an ontological difference between the generic group assumption and the random oracle model for hash unctions. We then examine some criticisms that have been leveled at the generic group model and raise some questions of our own.
keywords: Cryptography generic group. public key
Generalizations of Verheul's theorem to asymmetric pairings
Koray Karabina Edward Knapp Alfred Menezes
Advances in Mathematics of Communications 2013, 7(1): 103-111 doi: 10.3934/amc.2013.7.103
For symmetric pairings $e : \mathbb{G} \times \mathbb{G} \rightarrow \mathbb{G}_T$, Verheul proved that the existence of an efficiently-computable isomorphism $\phi : \mathbb{G}_T \rightarrow \mathbb{G}$ implies that the Diffie-Hellman problems in $\mathbb{G}$ and $\mathbb{G}_T$ can be efficiently solved. In this paper, we explore the implications of the existence of efficiently-computable isomorphisms $\phi_1 : \mathbb{G}_T \rightarrow \mathbb{G}_1$ and $\phi_2 : \mathbb{G}_T \rightarrow \mathbb{G}_2$ for asymmetric pairings $e : \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T$. We also give a simplified proof of Verheul's theorem.
keywords: cryptography discrete logarithm problem. asymmetric pairings Verheul's theorem

Year of publication

Related Authors

Related Keywords

[Back to Top]