Information (Jul 2021)

New Commitment Schemes Based on Conjugacy Problems over Rubik’s Groups

  • Ping Pan,
  • Junzhi Ye,
  • Yun Pan,
  • Lize Gu,
  • Licheng Wang

DOI
https://doi.org/10.3390/info12080294
Journal volume & issue
Vol. 12, no. 8
p. 294

Abstract

Read online

Commitment schemes are important tools in cryptography and used as building blocks in many cryptographic protocols. We propose two commitment schemes by using Rubik’s groups. Our proposals do not lay the security on the taken-for-granted hardness of the word problem over Rubik’s groups. Instead, our first proposal is based on a symmetric encryption algorithm that is secure based on the hardness of the conjugacy search problem over Rubik’s groups, while our second proposal is based on the hardness of a newly derived problem—the functional towering conjugacy search problem over Rubik’s groups. The former is proved secure in the sense of both computational hiding and binding, while the latter is proved even secure in the sense of perfect hiding and computational binding. Furthermore, the proposed schemes have a remarkable performance advantage: a linear commitment/opening speed. We also evaluate the efficiency of the commitment schemes and show that they are considerably fast.

Keywords