Paper 2019/557

Extended Galbraith's Test on the Anonymity of IBEs from Higher Residuosity

Xiaopeng Zhao, Zhenfu Cao, Xiaolei Dong, and Jun Shao


At PKC 2019, Clear and McGoldrick presented the first identity-based encryption (IBE) scheme that supports homomorphic addition modulo a poly-sized prime $e$. Assuming that deciding solvability of a special system of multivariate polynomial equations is hard, they proved that their scheme for $e>2$ is anonymous. In this paper, we review the classical Galbraith's test on the anonymity of the first pairing-free IBE scheme due to Cocks. With the eye of the reciprocity law over $\mathbb{F}_\mathtt{q}[x]$, we can have a profound understanding of the test and naturally extend it to give a practical attack on the anonymity of the Clear-McGoldrick IBE scheme. Furthermore, we believe that our technique plays a crucial role in anonymizing IBE schemes from higher residuosity.

Available format(s)
Public-key cryptography
Publication info
Preprint. Major revision.
identity-based encryptionGalbraith's testanonymity
Contact author(s)
1306062147 @ qq com
2020-09-20: last of 4 revisions
2019-05-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Xiaopeng Zhao and Zhenfu Cao and Xiaolei Dong and Jun Shao},
      title = {Extended Galbraith's Test on the Anonymity of IBEs from Higher Residuosity},
      howpublished = {Cryptology ePrint Archive, Paper 2019/557},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.