  Group signatures allow users of a group to sign messages anonymously in the
name of the group, while incorporating a tracing mechanism to revoke anonymity
and identify the signer of any message. Since its introduction by Chaum and van
Heyst (EUROCRYPT 1991), numerous proposals have been put forward, yielding
various improvements on security, efficiency and functionality. However, a
drawback of traditional group signatures is that the opening authority is given
too much power, i.e., he can indiscriminately revoke anonymity and there is no
mechanism to keep him accountable. To overcome this problem, Kohlweiss and
Miers (PoPET 2015) introduced the notion of accountable tracing signatures
(ATS) - an enhanced group signature variant in which the opening authority is
kept accountable for his actions. Kohlweiss and Miers demonstrated a generic
construction of ATS and put forward a concrete instantiation based on
number-theoretic assumptions. To the best of our knowledge, no other ATS scheme
has been known, and the problem of instantiating ATS under post-quantum
assumptions, e.g., lattices, remains open to date.
  In this work, we provide the first lattice-based accountable tracing
signature scheme. The scheme satisfies the security requirements suggested by
Kohlweiss and Miers, assuming the hardness of the Ring Short Integer Solution
(RSIS) and the Ring Learning With Errors (RLWE) problems. At the heart of our
construction are a lattice-based key-oblivious encryption scheme and a
zero-knowledge argument system allowing to prove that a given ciphertext is a
valid RLWE encryption under some hidden yet certified key. These technical
building blocks may be of independent interest, e.g., they can be useful for
the design of other lattice-based privacy-preserving protocols.
