## CryptoDB

### Bao Li

#### Publications

**Year**

**Venue**

**Title**

2020

EUROCRYPT

Double-Base Chains for Scalar Multiplications on Elliptic Curves
📺
Abstract

Double-base chains (DBCs) are widely used to speed up scalar multiplications on elliptic curves. We present three results of DBCs. First, we display a structure of the set containing all DBCs and propose an iterative algorithm to compute the number of DBCs for a positive integer. This is the first polynomial time algorithm to compute the number of DBCs for positive integers. Secondly, we present an asymptotic lower bound on average Hamming weights of DBCs $\frac{\log n}{8.25}$ for a positive integer $n$. This result answers an open question about the Hamming weights of DBCs. Thirdly, we propose a new algorithm to generate an optimal DBC for any positive integer. The time complexity of this algorithm is $\mathcal{O}\left(\left(\log n\right)^2 \log\log n\right)$ bit operations and the space complexity is $\mathcal{O}\left(\left(\log n\right)^{2}\right)$ bits of memory. This algorithm accelerates the recoding procedure by more than $6$ times compared to the state-of-the-art Bernstein, Chuengsatiansup, and Lange's work. The Hamming weights of optimal DBCs are over $60$\% smaller than those of NAFs. Experimental results show that scalar multiplication using our optimal DBC is about $13$\% faster than that using non-adjacent form on elliptic curves over large prime fields.

2018

ASIACRYPT

Understanding and Constructing AKE via Double-Key Key Encapsulation Mechanism
Abstract

Motivated by abstracting the common idea behind several implicitly authenticated key exchange (AKE) protocols, we introduce a primitive that we call double-key key encapsulation mechanism (2-key KEM). It is a special type of KEM involving two pairs of secret-public keys and satisfying some function and security property. Such 2-key KEM serves as the core building block and provides alternative approaches to simplify the constructions of AKE. To see the usefulness of 2-key KEM, we show how several existing constructions of AKE can be captured as 2-key KEM and understood in a unified framework, including widely used HMQV, NAXOS, Okamoto-AKE, and FSXY12-13 schemes. Then, we show (1) how to construct 2-key KEM from concrete assumptions, (2) how to adapt the classical Fujisaki-Okamoto transformation and KEM combiner to achieve the security requirement of 2-key KEM, (3) an elegant Kyber-AKE over lattice using the improved Fujisaki-Okamoto technique.

2010

EPRINT

Chosen Ciphertext Secure Encryption over Semi-smooth Subgroup
Abstract

In this paper we propose two public key encryption schemes over the
semi-smooth subgroup introduced by Groth05. Both the schemes are
proved secure against chosen ciphertext attacks under the factoring
assumption. Since the domain of exponents is much smaller, both our
schemes are significantly more efficient than Hofheiz-Kiltz 2009
encryption.

2005

EPRINT

Efficient reduction of 1 out of $n$ oblivious transfers in random oracle model
Abstract

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.

2005

EPRINT

Computation of Tate Pairing for Supersingular Curves over characteristic 5 and 7
Abstract

We compute Tate pairing over supersingular elliptic curves via the generic BGhES\cite{BGES} method for $p=5,7$. In those cases, the point multiplication by $p$ is efficiently computed by the Frobenius endomorphism. The function in a cycle can be efficiently computed by the method of continued fraction.

#### Coauthors

- Ronglin Hao (3)
- Jingnan He (1)
- Dingding Jia (4)
- Xiaoqian Li (3)
- Hongda Li (1)
- Bei Liang (1)
- Xianhui Lu (5)
- Bingke Ma (3)
- Qixiang Mei (3)
- Saud Al Musa (1)
- Kunpeng Wang (1)
- Guangwu Xu (1)
- Haixia Xu (1)
- Haiyang Xue (1)
- Wei Yu (1)