Lattice-Based Proof-Friendly Signatures from Vanishing Short Integer Solutions

Efficient anonymous credentials are typically constructed by combining proof-friendly signature schemes with compatible zero-knowledge proof systems. Inspired by pairing-based proof-friendly sig-natures such as Boneh-Boyen (BB) and Boneh-Boyen-Shacham (BBS), we propose a wide family of lattice-based proof-friendly signatures based on variants of the vanishing short integer solution (vSIS) assumption [Cini-Lai-Malavolta, Crypto’23]. In particular, we obtain natural lattice-based adaptions of BB and BBS which, similar to their pairing-based counterparts, admit nice algebraic properties. [Bootle-Lyubashevsky-Nguyen-Sorniotti, Crypto’23] (BLNS) recently proposed a framework for constructing lattice-based proof-friendly signa-tures and anonymous credentials, based on another new lattice assumption called ISIS _f parametrised by a fixed function f, with focus on f being the binary decomposition. We introduce a generalised ISIS _f framework, called GenISIS _f, with a keyed and probabilistic function f. For example, picking f _b(μ) = 1/(b−μ) with key b for short ring element μ leads to alge-braic and thus proof-friendly signatures. To better gauge the robustness and proof-friendliness of (Gen)ISIS _f, we consider what happens when the inputs to ff are chosen selectively (or even adaptively) by the adversary, and the behaviour under relaxed norm checks. While bit decomposition quickly becomes insecure, our proposed function families seem robust.