Paper 2025/2100

Tag Functions and Their Applications to Lattice-based Signatures and IBEs — Compact Designs and Tighter Security

Abstract

The existing lattice-based signature and IBE schemes suffer from the non-compactness of public keys or larger reduction loss in the security analysis. Thus we solve and improve those deficiencies as follows: – First, we construct a lattice-based short signature scheme with a compact verification key in the standard model based on the ring short integer solution (RSIS) assumption. Under the same com- pactness, the ring modulus of our signature scheme is significantly smaller than the compact sig- nature scheme of Alperin-Sheriff (PKC 2015). More importantly, our signature scheme achieves better reduction loss than all the previous confined guessing-based signatures. In other words, our signature scheme achieves better security and efficiency simultaneously. – Secondly, we further design a short signature scheme with a nearly compact public key size and an even smaller reduction loss. Our second signature scheme achieves even better reduction loss than our first signature scheme yet at the cost of increasing the public key to a super-constant number of ring vectors. – Last but not least, we construct an adaptively secure compact IBE scheme from the lattice as- sumptions and the truncation collision-resistant hash functions (TCRHF) introduced by Jager and Kurek (ASIACRYPT 2018). Note that the previous TCRHF-based IBE schemes are not even close to compactness. The above improvements mainly benefited from our compact design of the tag functions and their more compact homomorphic evaluations. We also believe that our newly designed tag function may find new applications in designing other cryptographic schemes, like ABE and others.

Note: 2025-11-15