  Policy-based signatures (PBS) were proposed by Bellare and Fuchsbauer (PKC
2014) to allow an {\em authorized} member of an organization to sign a message
on behalf of the organization. The user's authorization is determined by a
policy managed by the organization's trusted authority, while the signature
preserves the privacy of the organization's policy. Signing keys in PBS do not
include user identity information and thus can be passed to others, violating
the intention of employing PBS to restrict users' signing capability.
  In this paper, we introduce the notion of {\em traceability} for PBS by
including user identity in the signing key such that the trusted authority will
be able to open a suspicious signature and recover the signer's identity should
the needs arise. We provide rigorous definitions and stringent security notions
of traceable PBS (TPBS), capturing the properties of PBS suggested by
Bellare-Fuchsbauer and resembling the "full traceability" requirement for group
signatures put forward by Bellare-Micciancio-Warinschi (Eurocrypt 2003). As a
proof of concept, we provide a modular construction of TPBS, based on a
signature scheme, an encryption scheme and a zero-knowledge proof system.
Furthermore, to demonstrate the feasibility of achieving TPBS from concrete,
quantum-resistant assumptions, we give an instantiation based on lattices.
