International Association
for Cryptologic Research

Non-interactive batch arguments (BARGs) for NP allow a prover to prove \ell NP statements with a proof whose size scales sublinearly with \ell. In this work, we construct a pairing-based BARG where the size of the common reference string (CRS) scales linearly with the number of instances and the prover's overhead is quasi-linear in the number of instances. Our construction is fully black box in the use of the group. Security relies on a q-type assumption in composite-order pairing groups. The best black-box pairing-based BARG prior to this work has a nearly-linear size CRS (i.e., a CRS of size \ell^{1 + o(1)}) and the prover overhead is quadratic in the number of instances. All pairing-based BARGs with a sublinear-size CRS relies on some type of recursive composition and correspondingly, non-black-box use of the group. The main technical insight underlying our construction is to substitute the vector commitment in previous pairing-based BARGs with a polynomial commitment. This yields a scheme that does not rely on cross terms in the common reference string. In previous black-box pairing-based schemes, the super-linear-size CRS and quadratic prover complexity was due to the need for cross terms.

Most adaptively secure identity-based encryption (IBE) constructions from lattices in the standard model follow the framework proposed by Agrawal et al. (EUROCRYPT 2010). However, this framework has an inherent restriction: the modulus is quadratic in the trapdoor norm. This leads to an unnecessarily large modulus, reducing the efficiency of the IBE scheme. In this paper, we propose a novel framework for adaptively secure lattice-based IBE in the standard model, that removes this quadratic restriction of modulus while keeping the dimensions of the master public key, secret keys, and ciphertexts unchanged. More specifically, our key observation is that the original framework has a \textit{natural} cross-multiplication structure of trapdoor. Building on this observation, we design two novel algorithms with non-spherical Gaussian outputs that efficiently exploit this structure and thus remove the restriction. Furthermore, we apply our framework to various IBE schemes with different partitioning functions in both integer and ring settings, demonstrating its significant improvements and broad applicability. Besides, compared to a concurrent and independent work by Ji et al. (PKC 2025), our framework is significantly simpler in design, and enjoys a smaller modulus, a more compact master public key and shorter ciphertexts.