Sovereign Modal Signatures

Abstract

Signing anonymously under both hidden and public policies with per-signature accountability has only been studied piecemeal, as prior schemes address at most one dimension or restrict function classes. Here, we introduce sovereign modal signatures, the first scheme unifying both dimensions with support for hidden-circuit evaluation over bounded-size arithmetic circuits without universal circuits. Each signer holds a private attribute and a hidden policy F, certified by an authority and concealed from signatures. Resting on a public combiner P, the signing process maps the joint outputs of F and an ad hoc function G to a derived message and an opening tag governing per-signature traceability. Modifying the effective policy at signing time requires no key reissuance, since G is chosen freshly against the fixed F. Achieving zero-knowledge evaluation of F without exposing its structure is our core challenge, resolved by treating F’s PLONK description as witness rather than statement. No universal circuits are required: our reduction yields a fixed verification circuit of size linear in F’s gate count; the resulting scheme is provably secure in the random oracle model. Concretely, our generic construction needs only signatures, public-key encryption, and non-interactive zero-knowledge arguments of knowledge for arithmetic circuits. Hidden arithmetic circuits over any finite field are fully supported, subsuming the restricted Boolean and linear function classes of prior hidden-function schemes. Our post-quantum instantiation combines ZKBoo (Usenix Security ’16) under the MPC-in-the-Head (MPCitH, STOC ’07) paradigm with lattice-based primitives over , achieving plausibly post-quantum security without pairings or the algebraic group model. With proof sizes quasilinear in F’s gate count and linear in G and P’s multiplications, the scheme also readily admits richer MPCitH instantiations.