Cryptology ePrint Archive: Report 2019/557

Identity-Based Encryption from $e$-th Power Residue Symbols

Xiaopeng Zhao and Jinwen Zheng and Zhenfu Cao and Xiaolei Dong and Nanyuan Cao

Abstract: Boneh, LaVigne and Sabin (BLS)'s scheme naturally generalizes Cocks' scheme to higher power residue symbols, but it is less efficient, bandwidth-wise as computing the $e$-th power residue symbols is really time-consuming and ciphertexts are expressed in the form of polynomials. This paper, we improve the efficiency of BLS's scheme through taking off the part of computing $e$-th power residue symbols in its encryption phase. This modification makes the encryption much more efficient than that in Cocks' scheme. Our construction also widens BLS's scheme to the case $e$ is square-free. Furthermore, we generalize the notable Galbraith's test by introducing the general reciprocity law on function fields. With the help of the extended Galbraith's test, we show BLS's scheme is not anonymous in general. We also provide some methods for computing the $e$-th power residue symbols.

Category / Keywords: public-key cryptography / identity-based encryption; $e$-th power residue symbol; the general reciprocity law on function fields; anonymity.

Date: received 24 May 2019, last revised 9 Jun 2019

Contact author: 52164500025 at stu ecnu edu cn

Available format(s): PDF | BibTeX Citation

Version: 20190610:012920 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]