International Association for Cryptologic Research

International Association
for Cryptologic Research


Guangwu Xu


Pre-Computation Scheme of Window $\tau$NAF for Koblitz Curves Revisited
Wei Yu Guangwu Xu
Let $E_a/ \mathbb{F}_{2}: y^2+xy=x^3+ax^2+1$ be a Koblitz curve. The window $\tau$-adic non-adjacent form (window $\tau$NAF) is currently the standard representation system to perform scalar multiplications on $E_a/ \mathbb{F}_{2^m}$ utilizing the Frobenius map $\tau$. This work focuses on the pre-computation part of scalar multiplication. We first introduce $\mu\bar{\tau}$-operations where $\mu=(-1)^{1-a}$ and $\bar{\tau}$ is the complex conjugate of $\tau$. Efficient formulas of $\mu\bar{\tau}$-operations are then derived and used in a novel pre-computation scheme. Our pre-computation scheme requires $6${\bf M}$+6${\bf S}, $18${\bf M}$+17${\bf S}, $44${\bf M}$+32${\bf S}, and $88${\bf M}$+62${\bf S} ($a=0$) and $6${\bf M}$+6${\bf S}, $19${\bf M}$+17${\bf S}, $46${\bf M}$+32${\bf S}, and $90${\bf M}$+62${\bf S} ($a=1$) for window $\tau$NAF with widths from $4$ to $7$ respectively. It is about two times faster, compared to the state-of-the-art technique of pre-computation in the literature. The impact of our new efficient pre-computation is also reflected by the significant improvement of scalar multiplication. Traditionally, window $\tau$NAF with width at most $6$ is used to achieve the best scalar multiplication. Because of the dramatic cost reduction of the proposed pre-computation, we are able to increase the width for window $\tau$NAF to $7$ for a better scalar multiplication. This indicates that the pre-computation part becomes more important in performing scalar multiplication. With our efficient pre-computation and the new window width, our scalar multiplication runs in at least 85.2\% the time of Kohel's work (Eurocrypt'2017) combining the best previous pre-computation. Our results push the scalar multiplication of Koblitz curves, a very well-studied and long-standing research area, to a significant new stage.
Impossible Differential Cryptanalysis of Pelican, MT-MAC-AES and PC-MAC-AES
Wei Wang Xiaoyun Wang Guangwu Xu
In this paper, the impossible differential cryptanalysis is extended to MAC algorithms \textsc{Pelican}, MT-MAC and PC-MAC based on AES and 4-round AES. First, we collect message pairs that produce the inner near-collision with some specific differences by the birthday attack. Then the impossible differential attack on 4-round AES is implemented using a 3-round impossible differential property. For \textsc{Pelican}, our attack can recover the internal state, which is an equivalent subkey. For MT-MAC-AES, the attack turns out to be a subkey recovery attack directly. The data complexity of the two attacks is $2^{85.5}$ chosen messages, and the time complexity is about $2^{85.5}$ queries. For PC-MAC-AES, we can recover the 256-bit key with $2^{85.5}$ chosen messages and $2^{128}$ queries.
Distinguishing Attack and Second-Preimage Attack on the CBC-like MACs
In this paper, we first present a new distinguisher on the CBC-MAC based on a block cipher in Cipher Block Chaining (CBC) mode. It can also be used to distinguish other CBC-like MACs from random functions. The main results of this paper are on the second-preimage attack on CBC-MAC and CBC-like MACs include TMAC, OMAC, CMAC, PC-MAC and MACs based on three-key encipher CBC mode. Instead of exhaustive search, this attack can be performed with the birthday attack complexity.
Efficient reduction of 1 out of $n$ oblivious transfers in random oracle model
We first present a protocol which reduces 1-out-of-$n$ oblivious transfer OT$_l^m$ to 1-out-of-$n$ oblivious transfer OT$_m^k$ for $n>2$ in random oracle model, and show that the protocol is secure against malicious sender and semi-honest receiver. Then, by employing a cut-and-choose technique, we obtain a variant of the basic protocol which is secure against a malicious receiver.
Refinements of Miller's Algorithm for Computing Weil/Tate Pairing
Ian Blake Kumar Murty Guangwu Xu
In this paper we propose three refinements to Miller's algorithm for computing Weil/Tate Pairing.The first one is an overall improvement and achieves its optimal behavior if the binary expansion of the involved integer has more zeros. If more ones are presented in the binary expansion, second improvement is suggested. The third one is especially efficient in the case base three. We also have some performance analysis.