Depending on the application, malleability in cryptography can be viewed as either a flaw or --- especially if sufficiently understood and restricted --- a feature. In this work, we examine notions of malleability for three cryptographic primitives: encryption, signatures, and non-interactive zero-knowledge (NIZK) proofs. For each primitive, we both define general notions of malleability and consider ways to meaningfully control malleability, as in many settings we would like to guarantee that only certain types of transformations can be performed.

To construct malleable proofs, we first observe that Groth-Sahai proofs are inherently malleable. We thus use Groth-Sahai proofs within a generic construction to efficiently instantiate controlled-malleable NIZK proofs (cm-NIZKs) using only the Decision Linear assumption. We additionally show that cm-NIZKs can be generically constructed using succinct non-interactive zero-knowledge arguments of knowledge (SNARGs); this second construction results in cm-NIZKs that --- while less efficient than those based on Groth-Sahai proofs --- provide more flexibility. Our controlled-malleable signature and encryption schemes are then constructed generically from cm-NIZKs.

Finally, we consider a number of applications of cm-NIZKs, such as shorter proofs for verifiable shuffles (in which one proof suffices to show the correctness of an entire multi-step shuffle) and threshold decryption, and --- as an application of controlled-malleable signatures --- delegatable anonymous credentials that scale linearly with the number of delegations and satisfy stronger notions of unforgeability than could previously be achieved. Here again, all our constructions are fully generic, and the concrete instantiations can be based on Decision Linear.