Policy-based signature scheme from lattices

Policy-based signature, introduced by Bellare and Fuchsbauer at PKC 2014, is a new type of digital signature in which a signer is only allowed to sign messages satisfying certain policy specified by the authority, but the signatures should not reveal the underlying policy. Having these features, policy-based signatures are attractive from both theoretical and practical aspects. In their pioneering paper, Bellare and Fuchsbauer have provided generic constructions of policy-based signatures, and a concrete instantiation based on pairings. In this work, we develop the recent techniques in lattice-based cryptography to construct a (delegatable) policy-based signature scheme from lattice assumptions. Specifically, we adapt Langlois et al.’s zero-knowledge argument system (PKC 2014) for the Bonsai tree signature scheme (Eurocrypt 2010) to enable the prover to convince the verifier that its secret witness satisfies an additional condition. Making the protocol non-interactive via the Fiat-Shamir transformation, we obtain a policy-based signature scheme supporting polynomially many policies, which satisfies the two security requirements (simulatability and extractability) in the random oracle model. Furthermore, our construction can be efficiently extended to a delegatable policy-based signature, thanks to the hierarchical structure of the Bonsai tree. Our contribution is twofold. On the one hand, we enrich the scope of policy-based signatures by providing the first quantum-resistant instantiation. On the other hand, our technical approach can potentially be applied to design a wide variety of privacy-enhanced lattice-based cryptographic constructions.