Tightly-Secure Encryption in the Multi-user, Multi-challenge Setting with Improved Efficiency

We construct a compact public-key encryption with tight CCA security in the multi-user, multi-challenge setting, where the reduction loss is a constant. Our scheme follows the Hofheinz-Jager framework but is compressed in the sense that only one of the underlying two-tier signatures needs to be committed. Considering the virtually unbounded simulations, e.g., \(2^{80}\), the ciphertext size of our scheme decreases to about 256 group elements, whereas the best known solution provided by Blazy et al. required about 625 group elements under the same standard assumptions. In particular, we formalize a new notion called simulatable two-tier signature, which plays a central role in the construction of our tree-based signature and public-key encryption. Combining simulatable two-tier signatures with additional “ephemeral” signatures, we provide a method of constructing commitments to a tree-based signature, where most parts of the tree-based signature can be simulated and sent in the clear. Our method can reduce the length of the commitments and the related proofs of knowledge in previous works by 60%.