Geoffroy Couteau
email: couteau@irif.fr

Dominik Hartmann
email: dominik.hartmann@rub.de

Shorter Non-Interactive Zero-Knowledge Arguments and ZAPs for Algebraic Languages

Keywords: zero-knowledge arguments, non-interactive zero-knowledge arguments, satistical witness-indistinguishability, pairing-based cryptography, tight security, structure-preserving signatures

We put forth a new framework for building pairing-based non-interactive zeroknowledge (NIZK) arguments for a wide class of algebraic languages, which are an extension of linear languages, containing disjunctions of linear languages and more. Our approach differs from the Groth-Sahai methodology, in that we rely on pairings to compile a Σ-protocol into a NIZK. Our framework enjoys a number of interesting features:

conceptual simplicity, parameters derive from the Σ-protocol; proofs as short as resulting from the Fiat-Shamir heuristic applied to the underlying Σprotocol; fully adaptive soundness and perfect zero-knowledge in the common random string model with a single random group element as CRS; yields simple and efficient two-round, public coin, publicly-verifiable perfect witness-indistinguishable (WI) arguments(ZAPs) in the plain model. To our knowledge, this is the first construction of two-rounds statistical witness-indistinguishable arguments from pairing assumptions. Our proof system relies on a new (static, falsifiable) assumption over pairing groups which generalizes the standard kernel Diffie-Hellman assumption in a natural way and holds in the generic group model (GGM) and in the algebraic group model (AGM). Replacing Groth-Sahai NIZKs with our new proof system allows to improve several important cryptographic primitives. In particular, we obtain the shortest tightly-secure structurepreserving signature scheme (which are a core component in anonymous credentials), the shortest tightly-secure quasi-adaptive NIZK with unbounded simulation soundness (which in turns implies the shortest tightly-mCCA-secure cryptosystem), and shorter ring signatures.

Introduction

Zero-knowledge proof systems, introduced in the seminal paper of Goldwasser, Micali, and Rackoff [START_REF] Goldwasser | The knowledge complexity of interactive proof systems[END_REF], allow a prover to convince a verifier of the truth of a statement, without revealing anything beyond this. Zero-knowledge proofs are among the most fundamental cryptographic primitives, and enjoy a tremendous number of applications. A particularly useful kind of zero-knowledge proof systems are non-interactive zero-knowledge proofs (NIZKs) [START_REF] Blum | Non-interactive zero-knowledge and its applications (extended abstract)[END_REF], which consist of a single flow from the prover to the verifier. NIZKs have found a wide variety of applications in cryptography, ranging from low-interactions secure computation protocols to the design of advanced cryptographic primitives and protocols such as verifiable encryption, group signatures, structure-preserving signatures, anonymous credentials, KDM-CCA2 and identity-based CCA2 encryption, among many others.

Early feasibility results for NIZKs were established in the 90's, under standard assumptions such as factorization, or the existence of (doubly-enhanced) trapdoor permutations [START_REF] Feige | Multiple non-interactive zero knowledge proofs based on a single random string[END_REF]. While these results demonstrated the possibility of building NIZKs under standard assumption for all NP languages (in the common reference string model), they were typically built upon a reduction to an NP-complete language such as graph hamiltonicity, and were concretely inefficient.

The Fiat-Shamir (FS) transform [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF], which relies on a hash function to compile an interactive ZK proof into a NIZK, provides a practical alternative to the above, leading to efficient NIZK arguments; however, it only offers heuristic security guarantees and any security proof for the FS transform must overcome several barriers [7, 38] 1 . Hence, for two decades after their introduction, essentially two types of NIZKs coexisted: inefficient NIZKs provably secure in the standard (common reference string) model, and heuristically secure practical NIZKs.

Pairing-Based NIZKs

With the advent of pairing-based cryptography, this somewhat unsatisfying situation changed. Starting with the celebrated work of Groth and Sahai [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF], a variety of pairing-based NIZK proof systems have been introduced. These proof systems have in common that they handle directly a large class of languages over abelian groups, avoiding the need for expensive reductions to NP-complete problems. Due to its practical significance, the Groth-Sahai proof system (and its follow-ups) initiated a wide variety of cryptographic applications. As of today, all known practically efficient (publicly verifiable) NIZKs in the standard model rely on pairing-based cryptography. Existing pairing-based NIZK proof systems can be divided in two categories:

NIZKs based on the Groth-Sahai (GS) methodology. These NIZKs directly rely on the techniques developed in [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF], and enhance the seminal construction in various ways [START_REF] Blazy | Batch Groth-Sahai[END_REF][START_REF] Daza | Shorter quadratic QA-NIZK proofs[END_REF][START_REF] Escala | Fine-tuning Groth-Sahai proofs[END_REF][START_REF] Ghadafi | Groth-sahai proofs revisited[END_REF][START_REF] Ràfols | Stretching groth-sahai: NIZK proofs of partial satisfiability[END_REF]. Unfortunately, in spite of these optimizations, Groth-Sahai proofs remain often unsatisfyingly inefficient, and are in particular notably less efficient than (heuristic) NIZKs obtained with the Fiat-Shamir transform. Furthermore, the design and analysis of a suitable NIZK, taking into account all existing optimizations, is often a tedious and error-prone task.

Quasi-Adaptive NIZKs for Linear Languages. In light of the above, an alternative line of research, starting with the work of [START_REF] Jutla | Shorter quasi-adaptive NIZK proofs for linear subspaces[END_REF] and culminating with [START_REF] Kiltz | Quasi-adaptive NIZK for linear subspaces revisited[END_REF], has investigated a different strategy for building pairing-based NIZKs. Roughly, the approach relies on a hash proof system [START_REF] Cramer | Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption[END_REF] (HPS) for the target language over some abelian group G 1 , which can be seen as a kind of designated-verifier NIZK proof, and makes it publicly verifiable by embedding the secret hashing key in the group G 2 . Verifying the proof is done with the help of a pairing operation between G 1 and G 2 . The HPS-based approach leads to conceptually simple and very efficient proofs (e.g. a membership proof for the DDH language can be made as short as a single group element in [START_REF] Kiltz | Quasi-adaptive NIZK for linear subspaces revisited[END_REF]). However, this efficiency comes with strong limitations: this approach can only handle linear languages, and only provides a quasi-adaptive type of soundness, where the common reference string is allowed to depend on the language.

Our Contribution

In this work, we introduce a new approach for building efficient, pairing-based non-interactive zeroknowledge arguments for a large class of languages, where soundness relies on a new (but plausible, static, and falsifiable) assumption, which extends the kernel Diffie-Hellman assumption [START_REF] Morillo | The kernel matrix Diffie-Hellman assumption[END_REF] in a natural way. Our approach is very simple and natural; yet it has to our knowledge never been investigated. It leads to proofs which are shorter and conceptually much simpler than proofs obtained with the GS methodology. At the same time and unlike the HPS-based methodology, our proof system is not limited to linear languages, but handles a more general class of witness samplable languages where, roughly, the language parameters can be sampled together with a trapdoor which can be used to decide membership in the language (in particular, this captures the important case of disjunctions of linear languages, from which one can build linear-size NIZKs for circuit satisfiability using the GOS methodology [START_REF] Groth | Non-interactive zaps and new techniques for NIZK[END_REF]) and achieves fully adaptive soundness with very short common random strings.

Statistical ZAPs and NIWIs. An additional benefit of our NIZK proof system is that it works in the common random string model, where the CRS is just a random bit string. Furthermore, we show that if we let the verifier pick the CRS himself, our proof system still satisfies statistical witness-indistinguishability. Therefore, we obtain the shortest two-round publicly-verifiable witnessindistinguishable argument system in the plain model (i.e., a ZAP [START_REF] Dwork | Zaps and their applications[END_REF]) for witness-samplable algebraic languages. Our ZAPs can be turned into fully non-interactive witness-indistinguishable arguments in the plain model, using the derandomization method of [START_REF] Barak | Derandomization in cryptography[END_REF]. We emphasize that the ZAPs obtained with our method are statistically witness-indistinguishable; to our knowledge, our construction is the first pairing-based statistical ZAP (it is in addition publicly verifiable, and public coin). Existing constructions of statistical ZAPs rely on the quasipolynomial hardness of LWE [START_REF] Badrinarayanan | B.: How to go beyond the black-box simulation barrier[END_REF][START_REF] Jain | Statistical zap arguments from quasi-polynomial lwe[END_REF], or rely on subexponential variants of standard assumptions and are not public coin [START_REF] Kalai | Statistical witness indistinguishability (and more) in two messages[END_REF]. While our result comes at the cost of basing soundness on a new pairing-based assumption, we believe that it represents a significant contribution to the important and long standing open question of building statistical ZAPs.

Simple Dual-Mode NIZKs. Eventually, a variant of our compiler allows to compile Σ-protocols for algebraic languages into (dual-mode) NIZK proofs, based on the standard SXDH assumption, for arbitrary algebraic languages (and not only witness-sampleable languages). While the proofs obtained this way have the same size and features as (optimized) Groth-Sahai proofs, it provides a conceptually simple and elegant way of constructing them.

High Level Overview. At a high level, our approach consists in compiling a three-move public coin zero-knowledge protocol (so called Σ-protocol) with linear answers over an abelian group G 1 into a non-interactive zero-knowledge argument, by embedding the challenge e into a group G 2 such that there is an asymmetric pairing between G 1 × G 2 and a target group G T , and adding the embedded challenge to the common reference string. Intuitively, correctness is preserved because the pairing can be used to perform the verification procedure, zero-knowledge is perfect, and soundness follows from the fact that a cheating adversary must compute a value in G 1 which has a non-trivial relation to e, which is conjectured to be intractable. An important part of our work is devoted to the analysis of the soundness property of our proof system, and the underlying assumption.

In addition to the efficiency improvements it provides, an important conceptual advantage of our approach over the Groth-Sahai methodology is that it gives a very simple and natural way to construct NIZKs. The construction of optimized Groth-Sahai proofs is generally cumbersome, and a significant amount of expertise is often required for the design of the best-possible GS proof in a given context. In contrast, Σ-protocols are typically straightforward to construct, and require considerably less expertise to optimize. Building a NIZK with our approach requires only to design an algebraic Σprotocol for the target language distribution, and compiling it into a NIZK (which essentially amounts to adding a single group element to the CRS). Computation, communication and the underlying assumption can be obtained in a straightforward way from the parameters of the underlying Σprotocol. We believe that this conceptual simplicity is an important feature toward making the use of pairing-based NIZKs accessible to a wider spectrum of researchers and industrials.

Technical Overview

The starting point of our approach is a (somewhat folklore) Σ-protocol for algebraic languages [START_REF] Ben Hamouda | Efficient UC-secure authenticated key-exchange for algebraic languages[END_REF][START_REF] Chaidos | Efficient designated-verifier non-interactive zero-knowledge proofs of knowledge[END_REF]. A Σ-protocol is a three-move public-coin honest-verifier zero-knowledge proof system (i.e., the message of the verifier is a random string, and the zero-knowledge property holds against verifiers that do not deviate from the specifications of the protocol). In the following, we use the implicit notations introduced in [START_REF] Escala | An algebraic framework for Diffie-Hellman assumptions[END_REF]: given a group G in additive form, we fix a generator g and write [x] for x • g. Most, if not all, algebraic languages over abelian groups considered in the literature can be written as

L M,Θ := {x ∈ G l |∃w ∈ Z t p : M(x) • w = Θ(x)}
, where M : G l → G n×t and Θ : G l → G n are linear maps sampled according to a distribution D par . This captures all algebraic languages defined by systems of polynomial equations between secret exponents. Most Σ-protocols for algebraic languages can then be seen as particular instantiations of the generic Σ-protocol represented on Figure 1.

To compile this Σ-protocol into a NIZK, we assume that all computations take place in a group G 1 , such that there exists another group G 2 together with an asymmetric pairing

• : G 1 × G 2 → G T .
We use the standard brackets with subscripts

[•] 1 , [•] 2 , [•] T to
M(x)] 1 • [d] 2 ? = [Θ(x)] 1 • [e] 2 + [a] 1 • [1] 2 .
While this construction is relatively simple, the bulk of our technical contribution is the detailed analysis of the security guarantees it provides.

The Extended-Kernel Matrix Diffie-Hellman Assumption. To prove the soundness of our NIZK, we introduce a new family of assumptions, which we call the extended-kernel Matrix Diffie-Hellman assumption (extKerMDH). The regular KerMDH assumption with respect to a distribution Dist over an asymmetric pairing group states that, given a matrix [A] 2 sampled from Dist, it is infeasible to find a vector [v] 1 where v is in the kernel of A. It is a natural computational analogue of the decisional Matrix Diffie-Hellman assumption (which it implies), and was introduced in [START_REF] Morillo | The kernel matrix Diffie-Hellman assumption[END_REF]. Our new assumption further generalizes the KerMDH assumption as follows: it states that it should be infeasible, given [A] 2 , to find another matrix [A ] 2 and a matrix [B] 1 such that B spans the entire kernel of A||A . Intuitively, the adversary is allowed to extend the matrix [A] 2 , which facilitates finding G 1 -vectors in its kernel; but each time the adversary extends A by one column, he must provide an additional G 1 -vector (linearly independent of the previous vectors) in the kernel of the extended matrix.

(M, Θ) $ ← -Dpar P V [x], w [x] r $ ← -Z k p [a] := [M(x)]r e $ ← -Zp d := ew + r check [M(x)]d ? = [Θ(x)]e + [a] [a] e d
The extKerMDH assumption is a static, non-interactive assumption, which generalizes the KerMDH assumption in a natural way. To provide further evidence for the security of our assumption, we prove that it is unconditionally secure in the generic group model [START_REF] Shoup | Lower bounds for discrete logarithms and related problems[END_REF] (GGM), and that it reduces to the discrete logarithm assumption in the algebraic group model [START_REF] Fuchsbauer | The algebraic group model and its applications[END_REF] (AGM). On the downside, the extKerMDH assumption might not in general be a falsifiable assumption [START_REF] Gentry | Separating succinct non-interactive arguments from all falsifiable assumptions[END_REF][START_REF] Naor | On cryptographic assumptions and challenges (invited talk)[END_REF]: it states that it is infeasible to output [A ] 2 and a basis [B] 1 of the kernel of A||A , but verifying whether the G 1 -matrix [B] 1 is full rank is not efficiently feasible in general (indeed, the hardness of deciding whether a matrix given in a group G is full rank is exactly the decisional matrix Diffie-Hellman assumption). However, we show that for all witness-sampleable languages, there is a language trapdoor which does allow to efficiently check whether B is full rank (intuitively, the trapdoor allows to put [B] 1 in triangular form, from which the rank can be easily checked), turning our new assumption into a falsifiable assumption.

Witness Samplable Languages. We give an intuition of the class of algebraic languages which satisfy our requirements. Intuitively, an algebraic language L admits a NIZK (using our compiler) where soundness reduces to a falsifiable assumption if the parameters of L can be sampled together with a trapdoor which allows to efficiently check language membership. For example, this captures the DDH language L DDH : given language parameters ([1] 1 , [s] 1 ), the words in L DDH are of the form

([x] 1 , [x • s] 1 )
, and the trapdoor s allows to verify that a word (c 1 , c 2 ) belongs to L DDH by checking whether s • c 1 -c 2 = [0] 1 . Witness samplable languages need not be linear languages: for example, the language of ElGamal encryptions (in the exponent) of a plaintext m ∈ {0, 1} is not a linear language, yet the ElGamal secret key allows to efficiently check wether a pair of group elements indeed encrypts a bit, hence it is also captured by our methods. More generally, the conjunctions and disjunctions of witness samplable languages are still witness samplable. On the other hand, some natural algebraic languages are not witness-samplable; for example, the language of triples of the form

([1] 1 , [x] 1 , [x 2 ] 1 )
does not seem to be witness samplable (since it is not clear how one could generate a word-independent trapdoor allowing to check membership to this language).

Witness-sampleable languages were originally introduced in [START_REF] Jutla | Shorter quasi-adaptive NIZK proofs for linear subspaces[END_REF], but were restricted to linear languages. We extend this notion of witness-sampleability to arbitrary algebraic languages, and will show that many languages of interest are actually witness sampleable. For these languages, we therefore obtain shorter NIZKs under a natural, static, falsifiable assumption. We note that for the case of linear languages (such as the language of DDH tuple), our generalized notion of witness-samplability is the same as the notion of [START_REF] Jutla | Shorter quasi-adaptive NIZK proofs for linear subspaces[END_REF], and applying our compiler to witness-samplable linear languages leads to NIZKs which are actually secure under the standard KerMDH assumption (while still being shorter than GS proofs).

Applications

Our new NIZKs have several attractive features and can be used to improve the efficiency of many NIZK-based primitives. We provide a non-exhaustive list of some applications below. All applications we describe rely on witness-sampleable algebraic languages, making the underlying extKerMDH assumption falsifiable.

Adaptive NIZKs for Linear Languages. We achieve the shortest and most efficient adaptive NIZKs for (witness-sampleable) linear languages, with perfect zero-knowledge and computational soundness under the kernel Diffie-Hellman assumption: a Groth-Sahai proof for the language of DDH tuples consists of four group elements, while our NIZK requires only three group elements, and considerably less pairings. We note that in the quasi-adaptive setting, where the common reference string is allowed to depend on the language, the work of [START_REF] Kiltz | Quasi-adaptive NIZK for linear subspaces revisited[END_REF] gives NIZKs with two group elements (for non witnesssampleable languages), or even a single group element (for witness-sampleable languages). Therefore, our work can be seen as filling a remaining gap, providing a more complete picture of the size of NIZKs for linear languages, depending on whether we allow quasi-adaptive soundness, and rely on witness-sampleability. In addition to providing a stronger soundness guarantee, full adaptivity also leads to increased efficiency when many proofs are run in some high level application: it allows to rely on a single CRS (which, in our case, consists of a single group element), even when executing many linear subspace proofs for different languages. In contrast, QA-NIZKs have a language-dependent CRS; hence, a different CRS must be generated for each language. The comparison is summarised in Table 1. Adaptive NIZKs for Disjunctions. Since our NIZKs are built by compiling a Σ-protocol, they are compatible with the OR-trick of [START_REF] Cramer | Proofs of partial knowledge and simplified design of witness hiding protocols[END_REF]. The OR-trick provides a general method to construct Σprotocols of partial satisfiability, such as "k of those n words belong to the language L", from a Σ-protocol for proving membership to L. Building upon this observation, we obtain shorter NIZKs for disjunctions of statements. The state-of-the-art NIZK for partial satisfiability of equations is the one in [START_REF] Ràfols | Stretching groth-sahai: NIZK proofs of partial satisfiability[END_REF]. For the important case of the disjunction between two (resp. n) DDH languages, it gives proofs of size 10 group elements under the SXDH assumption (resp. 4n + 2 group elements for 1out-of-n proofs). For the same language, our approach leads to proofs of size 7 (resp. 3n + 1 group elements for 1-out-of-n proofs). This is detailed in Table 2. NIZKs for disjunctions of languages are a core component in several applications; we outline some applications below. Ring Signatures. Ring signatures [START_REF] Rivest | How to leak a secret[END_REF] allow a signer to anonymously sign on behalf of an ad-hoc group to which it belongs. They are a core component in some e-voting and e-cash schemes [START_REF] Tsang | Short linkable ring signatures for e-voting, e-cash and attestation[END_REF] and anonymous cryptocurrencies such as Monero [START_REF] Noether | Ring signature confidential transactions for monero[END_REF]. A O( √ N )-size proof of membership in a ring of size N was designed by Chandran, Groth and Sahai [START_REF] Chandran | Ring signatures of sub-linear size without random oracles[END_REF] and subsequently improved in [START_REF] Ràfols | Stretching groth-sahai: NIZK proofs of partial satisfiability[END_REF]; it relies at its core on a NIZK for ( -1)-out-of-disjunction of DDH languages. Using our improved NIZK for disjunction, we reduce the ring signature size by √ N -1 group elements, for rings of size N . We observe that a O(log N )-size ring signature scheme was recently introduced in [START_REF] Backes | Ring signatures: Logarithmic-size, no setup -from standard assumptions[END_REF]. The authors do not provide a concrete efficiency analysis and use generic tools which would likely render concrete instantiations inefficient for reasonable group sizes. We note, though, that our proof system can be used to instantiate the non-interactive witness indistinguishable proof system they rely upon, and would likely lead to efficiency improvements comparable to what we get over the ring signature of [START_REF] Ràfols | Stretching groth-sahai: NIZK proofs of partial satisfiability[END_REF], for concrete instantiations of their building blocks.

Scheme

Tightly-Secure QA-NIZKs with Unbounded Simulation Soundness. In several applications in cryptography, the constructions require a NIZK for linear languages which satisfies a stronger soundness guarantee: soundness should hold even if the adversary is allowed to see an arbitrary number of simulated proofs. This stronger notion is known as unbounded simulation-soundness. The recent work of [START_REF] Abe | Shorter QA-NIZK and SPS with tighter security[END_REF] introduced the first unbounded simulation-sound quasi-adaptive NIZK (USS-QA-NIZK) which achieves simultaneously compact CRS, compact proof size, and a tight security reduction. At the core of their construction is the disjunction NIZK of [START_REF] Ràfols | Stretching groth-sahai: NIZK proofs of partial satisfiability[END_REF], which has 10 group elements; this accounts for most of the size of their USS-QA-NIZK, which has 14 group elements. By replacing the disjunction proof by our new NIZK, we reduce the size of their USS-QA-NIZK to only 11 group elements, and also reduce the CRS size, at the cost of requiring our new assumption. We provide a comparison to existing USS-QA-NIZKs for linear languages on Table 3. In particular, our result allows to further reduce the size of the tightly-secure IND-mCCA-secure public-key encryption scheme of [START_REF] Abe | Improved (almost) tightly-secure simulation-sound QA-NIZK with applications[END_REF] (IND-mCCA refers to indistinguishability against chosen ciphertext attacks in the multi-user, multi-challenge setting), with a security reduction independent of the number of decryption-oracle requests of the CCA2 adversary, from 17 group elements to 14 group elements.

CRS Size

Proof Size Pairings Sec. Loss Assumption [START_REF] Libert | Non-malleability from malleability: Simulation-sound quasiadaptive NIZK proofs and CCA2-secure encryption from homomorphic signatures[END_REF] Tightly-Secure Structure-Preserving Signatures. The notion of structure-preserving cryptography gives a paradigm for building modular protocols designed to be naturally expressed as systems of pairing-product equations, which makes them compatible with the Groth-Sahai methodology. Structure-Preserving Signatures (SPS) are one of the most fundamental primitives in structurepreserving cryptography. They are the core component in a variety of important applications, such as anonymous credentials (see e.g. [START_REF] Belenkiy | P-signatures and noninteractive anonymous credentials[END_REF][START_REF] Camenisch | An accumulator based on bilinear maps and efficient revocation for anonymous credentials[END_REF][START_REF] Camenisch | Signature schemes and anonymous credentials from bilinear maps[END_REF][START_REF] Chase | Algebraic MACs and keyed-verification anonymous credentials[END_REF][START_REF] Damgård | Payment systems and credential mechanisms with provable security against abuse by individuals[END_REF][START_REF] Garman | Decentralized anonymous credentials[END_REF][START_REF] Hanser | Structure-preserving signatures on equivalence classes and their application to anonymous credentials[END_REF][START_REF] Lysyanskaya | Pseudonym systems[END_REF], to name just a few), mixnets and voting systems [START_REF] Groth | A non-interactive shuffle with pairing based verifiability[END_REF], or simulation-sound NIZKs [START_REF] Groth | Simulation-sound NIZK proofs for a practical language and constant size group signatures[END_REF][START_REF] Libert | Compactly hiding linear spans -tightly secure constant-size simulation-sound QA-NIZK proofs and applications[END_REF]. A cryptographic scheme is tightly secure if its security loss is independent of the number of users of the scheme. A tight security reduction gives guarantees that do not degrade with the size of the setting in which the system is used. Tight security is especially important in structure-preserving cryptography, where many components rely on the same cyclic group: if a non-tightly-secure scheme is used and the number of users increases, this might require increasing the group size to compensate for the security loss, degrading the performance of all other schemes relying on the same cyclic group. There has been a long sequence of works that seeked to obtain increasingly shorter structure preserving signatures with tight security reductions; we summarize them in Table 4.

The work of [START_REF] Gay | More efficient (almost) tightly secure structure-preserving signatures[END_REF] provides a tightly-secure SPS with 14 group elements, which combines an algebraic MAC scheme with the proof of [START_REF] Ràfols | Stretching groth-sahai: NIZK proofs of partial satisfiability[END_REF] for the disjunction of two DDH languages. The latter has proof size of 10 group elements. Replacing the OR-NIZK in their work by the shorter proof which we introduce leads to a tightly-secure SPS with 11 group elements, matching the size of the best known tightly-secure SPS [START_REF] Abe | Shorter QA-NIZK and SPS with tighter security[END_REF]. The work of [START_REF] Abe | Shorter QA-NIZK and SPS with tighter security[END_REF] improves over [START_REF] Gay | More efficient (almost) tightly secure structure-preserving signatures[END_REF] by replacing the underlying OR-NIZK by a designated-prover OR-NIZK, which suffices in this context. They show that in the designated-prover setting, the size of the OR-NIZK can be reduced to 7 group elements. We observe that their technique is actually compatible with our improved OR-NIZK, and leads to a quasi-adaptive designated-prover OR-NIZK with only 5 group elements (which can be of independent interest). Overall, this leads to a tightly-secure SPS with only 9 group elements under (a falsifiable flavor of) the extKerMDH assumption, significantly improving over the efficiency of the state-of-the-art. Considering a setting with security parameter λ = 80, a large possible number of signing queries Q = 2 30 , and choosing a group G of order p ≈ 2 2(λ+log L) to account for the security loss of L(Q) (assuming that the best attack on the group is the generic √ p-time attack), our scheme is actually computationally more efficient than the state-of-the-art non-tightly-secure SPS of [START_REF] Jutla | Improved structure preserving signatures under standard bilinear assumptions[END_REF], and produces signatures which are only slightly larger: 241 Bytes versus 201 Bytes.

Scheme Sig. Size PK Size Pairings Sec. Loss Assumption 4. Comparison of existing structure-preserving signatures for message space G n 1 , in their most efficient variant. For [START_REF] Abe | Improved (almost) tightly-secure simulation-sound QA-NIZK with applications[END_REF], n and t are defined as in Table 3. The notation (x1, x2) denotes x1 elements in G1 and x2 elements in G2. Q denotes the number of signing queries, λ is the security parameter. In the tree-based scheme of [START_REF] Hofheinz | Tightly secure signatures and public-key encryption[END_REF], denotes the depth of the tree (which limits the number of signing queries to 2 ).

[48] 10 + 6 13 81l + 1 O(1) DLIN [1] (7, 4) (5, n + 12) 16 Q SXDH, XDLIN [62] (10, 1) (16, 2n + 5
) 17 + 2n O(Q) SXDH, XDLINX [58] (6, 1) (0, n + 6) 3n + 4 2Q 2 SXDH [53] (5, 1) (0, n + 6) n + 3 Q log Q SXDH [2] ( 13

Related Work

We already mentioned related works on NIZKs and SPS. Our work was partly inspired by a line of work initiated in [START_REF] Chaidos | Efficient designated-verifier non-interactive zero-knowledge proofs of knowledge[END_REF][START_REF] Damgård | Non-interactive zero-knowledge from homomorphic encryption[END_REF], which compiles Σ-protocols into designated-verifier NIZKs, by encrypting the challenge with a malleable cryptosystem, and putting the ciphertext in the CRS. The idea of hiding the challenge of an interactive protocol in a CRS was also used in different contexts; for example, it bears similarity with methods used in [START_REF] Gennaro | Quadratic span programs and succinct NIZKs without PCPs[END_REF][START_REF] Kalai | On publicly verifiable delegation from standard assumptions[END_REF].

In a recent independent work [START_REF] Lombardi | Statistical ZAPR arguments from bilinear maps[END_REF], Lombardi et al. constructed statistical ZAP arguments under standard pairing assumptions. Their result and our ZAPs are incomparable: we achieve public coin ZAPs, while [START_REF] Lombardi | Statistical ZAPR arguments from bilinear maps[END_REF] only achieves a relaxed notion of reusable ZAPs with private verifier randomness, and we only rely on a polynomial hardness assumption, while [START_REF] Lombardi | Statistical ZAPR arguments from bilinear maps[END_REF] requires quasi-polynomial hardness. On the other hand, [START_REF] Lombardi | Statistical ZAPR arguments from bilinear maps[END_REF] relies on the quasi-polynomial hardness of the standard DLIN assumption, while we must rely on a new assumption.

Organization

In Section 2, we recall necessary preliminaries. Section 3 introduces our new NIZK argument system. Section 4 is devoted to the security analysis of the new proof system; to this end, it introduces the notion of algebraic witness sampleability and the extKerMDH assumption. Section 5 extends our construction to disjunctions of algebraic languages and Section 6 describes a variant of our compiler which yields (dual-mode) NIZK proofs based on the SXDH assumption for arbitrary algebraic languages (and not only witness-sampleable languages). While the proofs obtained this way have the same size and features as (optimized) Groth-Sahai proofs, it provides a conceptually simple and elegant way of constructing them. We outline several applications of our results in Section 7. Appendix A provides examples to illustrate some of the notions we introduce. In Appendix B, we prove the security of our new assumption in the generic group model and in the algebraic group model. Appendix C shows that disjunctions of languages are in fact directly captured by the framework of algebraic languages, without going through the OR-trick of [START_REF] Cramer | Proofs of partial knowledge and simplified design of witness hiding protocols[END_REF].

Preliminaries

Let P denote the set of all primes and λ ∈ N denote the security parameter. A probabilistic polynomial time algorithm (PPT, also denoted efficient algorithm) runs in time polynomial in the (implicit) security parameter λ. A function f is negligible if for any positive polynomial p there exists a bound B > 0 such that, for any integer

k ≥ B, |f (k)| ≤ 1/|p(k)|. We will write f (λ) ≈ 0 to indicate that f is a negligible function of λ; we also write f (λ) ≈ g(λ) for |f (λ) -g(λ)| ≈ 0.
For sampling an element according to a distribution or selecting it uniformly random from a (finite) set, we write p $ ← -S. We use the same notation for the output of a probabilistic algorithm. For output y of a deterministic algorithm A on input x, we will also use y := A(x). Matrices will always be bold, upper-case letters and vectors will be bold, lower-case letters. For a matrix A let span(A) := {x|∃r : x = Ar} and ker(A) := {x|x T A = 0} the left kernel of A. All interactive protocols will be performed between a prover P and a verifier V. If one party can deviate from the protocol, we will denote this by P and V respectively. Additionally, a simulator will be called S. For language parameters ρ sampled from a language distribution D, let L ρ denote the language defined by ρ and let R ρ denote its witness relation. Finally, for a distribution D, we write Supp(D) for the support of the distribution.

Groups and Pairings

Throughout this work, let p ∈ P denote a prime with bit length polynomial in the security parameter λ. Let G 1 , G 2 , G T be finite groups of prime order p with generators g 1 , g 2 respectively and e : G 1 ×G 2 → G T a bilinear map. We set g T := e(g 1 , g 2 ), which is a generator of

G T . PG = (p, G 1 , G 2 , G T , g 1 , g 2 , e
) is called a pairing group setting, if the following properties hold: e(g 1 , g 2 ) = 0 T (non-degenerate); e(ag 1 , bg 2 ) = ab • e(g 1 , g 2 ) (bilinearity); and e is efficiently computable. Furthermore, we require the existence of a probabilistic algorithm PGGen, which on input 1 λ generates pairing parameters as above with a group order close to 2 λ , i.e. PG $ ← -PGGen(1 λ ). Throughout this work, we will write all groups in implicit notation, i.e. for an additive pairing group setting PG = (p, G 1 , G 2 , G T , g 1 , g 2 , e), we write [START_REF] Abe | Constant-size structurepreserving signatures: Generic constructions and simple assumptions[END_REF] i := g i and [x] i := x • g i for all x ∈ Z p and i ∈ {1, 2, T }. If the group is clear from context, we will omit the index. We write

[x] 1 • [y] 2 := e([x] 1 , [y] 2 ) = [xy]
T for pairings. The implicit notation also extends to matrices and vectors. For

A ∈ Z n×t p , A = (a ij ), let [A] k = ([a ij ] k ) ∈ G n×t k for k ∈ {1, 2

, T } and we also extend the pairing notation from above to

[A] 1 • [B] 2 := e([A] 1 , [B] 2 ) = [AB] T for matrices A ∈ Z n×t p , B ∈ Z t×m p
. Furthermore, we extend the implicit notation to linear (multivariate) polynomials. Let

P l := {[a 0 ] + l i=0 a i X i |a i ∈ Z p for i ∈ {0, . . . , l}} ⊂ G[x = (X 1 , . . . , X l )]
be the set of linear multivariate polynomials over G in l variables. For f ∈ P l and y = (y 1 , . . . , y l ) ∈ Z l p , we define the evaluation of f in y as applying the group operation in the exponent, i.e.

f ([y]) := f (y) = [a 0 ] + l i=1 a i [y i ] = [a 0 ] + l i=0 [a i y i ]
This allows us (in a slight abuse of notation) to use polynomials from P l inside of matrices and equations in implicit notation without changing variable names, i.e. [a 0 ]X 0 = [a 0 X 0 ], since the evaluation of the polynomial is defined exactly that way. For a matrix A = (a i,j ) ∈ P n×t l , the evaluation of the matrix (or vector) over P l in a vector y ∈ G l denotes the evaluation of all entries in the given vector, i.e. A(y) := (a i,j (y)) ∈ G n×t .

Matrix Assumptions

The assumptions used in this work are parametrised over matrix distributions. These are defined as follows.

Definition 1 (Matrix Distribution). Let k, l ∈ N with k < l. We call D k,l a matrix distribution, if it outputs matrices over G l×k of full rank k in polynomial time. If l = k + 1, we write D k instead. Without loss of generality, we assume that the first k rows of a matrix A ∈ Supp(D k,l ) form an invertible matrix.

We base the soundness of our construction on an extension of the Kernel Diffie-Hellman assumption. We recall its definition from [START_REF] Morillo | Matrix computational assumptions in multilinear groups[END_REF] and the definition of the underlying Matrix Diffie-Hellman assumption from [START_REF] Escala | An algebraic framework for Diffie-Hellman assumptions[END_REF].

Informally, the D k,l -Matrix Diffie-Hellman assumption states that for a matrix distribution D k,l , it is hard to distinguish a random vector of length l from the image of a random vector of length k under a matrix from said distribution.

Definition 2 (D k,l -Matrix Diffie-Hellman assumption (D k,l -MDDH)). Let D k,l be a matrix distribution, PGGen a pairing group generator and s ∈ {1, 2, T }. We say the D k,l -Matrix Diffie-Hellman assumption holds relative to PGGen in group G s , if for all efficient adversaries A, the function

Adv mddh P GGen,A (1 λ ) = |P r[A(G s , [A] s , [Ax] s ) = 1] -P r[A(G s , [A] s , [u] s ) = 1]| is negligible in λ with the probabilities taken over PG $ ← -PGGen, A $ ← -D k,l , x $ ← -Z k p , u $ ← -Z l p .
The computational analogue to the MDDH assumption is the KerMDH assumption [START_REF] Morillo | Matrix computational assumptions in multilinear groups[END_REF]. Instead of checking membership in the span, the adversary has to compute a vector in the (left) kernel of a matrix. To make the assumption falsifiable, the adversary has to provide the kernel vector in the opposite group of the challenge, i.e. for a matrix given in G s , the adversary has to answer in group G 3-s . Definition 3 (D k,l -Kernel Diffie-Hellman assumption (D k,l -KerMDH)). Let D k,l be a matrix distribution, PGGen a pairing group generator and s ∈ {1, 2}. We say the D k,l -KerMDH assumption holds relative to PGGen in G s , if for all efficient adversaries A, the function

Adv ker-mdh P GGen,A (1 λ ) = P r[c T A = 0 ∧ c = 0|[c] 3-s $ ← -A(PG, [A] s )
is negligible in λ with probabilities taken over

PG $ ← -PGGen(1 λ ), A $ ← -D k,l .
An example for a matrix distribution for which the KerMDH and MDDH assumptions hold in the AGM is the following:

L k : M =           1 1 1 • • • 1 e 1 0 0 • • • 0 0 e 2 0 0 0 0 e 3 . . . 0 . . . . . . . . . . . . 0 • • • 0 e k          
For k = 1, this distribution generates Diffie-Hellman matrices and for k ≥ 2 these matrices correspond to the k-Lin assumption [START_REF] Hofheinz | Secure hybrid encryption from weakened key encapsulation[END_REF]. We will only consider the distribution L k in this work as it is sufficient for all of our applications. For more matrix distributions, see for example [START_REF] Kiltz | Quasi-adaptive NIZK for linear subspaces revisited[END_REF][START_REF] Morillo | Matrix computational assumptions in multilinear groups[END_REF].

Σ-Protocols

Next, we recall the definition of Σ-protocols from [START_REF] Lindell | An efficient transform from sigma protocols to NIZK with a CRS and non-programmable random oracle[END_REF]. A Σ-protocol is a public-coin, three-move interactive proof between a prover P and a verifier V for a relation R, where the prover sends an initial message a, the verifier responds with a random e $ ← -{0, 1} λ and the prover concludes with a message d. Lastly, the verifier outputs 1, if it accepts and 0 otherwise. This is depicted in Figure 2.

Three properties are required for a Σ-protocol: completeness, special soundness and special honestverifier zero-knowledge. Definition 4 (Completeness). A three-move protocol Π R for a relation R with prover P and verifier V is complete, if

P (x, w) V (x) a $ ← -P1(x, w) e $ ← -{0, 1} λ d $ ← -P2(x,
P r out(V (x, a, e, d)) = 1 (x, w) ∈ R, a $ ← -P 1 (x, w), e $ ← -{0, 1} λ , d $ ← -P 2 (x, w, a, e) = 1
Definition 5 (Special soundness

Non-interactive Zero-Knowledge Arguments

An adaptive NIZK Π for a family of language distribution {D par } par consists of four probabilistic algorithms:

-CRSGen(1 λ ). On input 1 λ generates public parameters par (such as group parameters), a CRS and a trapdoor T . For simplicity of notation, we assume that any group parameters are implicitly included in the CRS. -Prove(CRS, ρ, x, w). On input of a CRS, a language description ρ ∈ D par and a statement x with witness w, outputs a proof π for x ∈ L ρ . -Verify(CRS, ρ, x, π). On input of a CRS, a language description ρ ∈ D par , a statement and a proof, accepts or rejects the proof. -SimProve(CRS, T , ρ, x). Given a CRS, the trapdoor T , a language description ρ ∈ D par and a statement x, outputs a simulated proof for the statement x ∈ L ρ .

Note that the CRS does not depend on the language distribution or language parameters, i.e. we define fully adaptive NIZKs for language distributions. The following properties need to hold for a NIZK argument (see e.g. [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF]).

Definition 7 (Perfect Completeness:). A proof system Π for a family of language distributions {D par } par is perfectly complete, if

P r Verify(CRS, ρ, x, π) = 1 (par , CRS, T ) $ ← -CRSGen(1 λ ); ρ ∈ Supp(D par ); (x, w) ∈ R ρ ; π $ ← -Prove(CRS, ρ, x, w) = 1
A proof system is sound, if it is hard to find proofs of incorrect statements. This is captured in the following definition. Definition 8 (Computational Soundness). A NIZK proof system Π for a family of language distributions {D par } par is computationally sound, if for every efficient adversary A

Pr Verify(CRS, ρ, x, π) = 1 ∧x ∈ L ρ (par , CRS, T ) $ ← -CRSGen(1 λ ); ρ ∈ Supp(D par ); (π, x) $ ← -A(CRS, ρ) ≈ 0
with the probability taken over CRSGen.

A proof system is zero knowledge, if it is impossible to distinguish between the output of SimProve and Prove. This is formalised as follows.

Definition 9 (Perfect Zero Knowledge). A NIZK proof system Π for a family of language distributions {D par } par is called perfectly zero-knowledge, if for all λ, all (par , CRS, T ) ∈ Supp(CRSGen(1 λ )), all ρ ∈ Supp(D par ) and all (x, w) ∈ R ρ , the distributions Prove(CRS, ρ, x, w) and SimProve(CRS, T , ρ, x) are identical.

We can relax the security of a NIZK argument to a Non-Interactive Witness Indistinguishable (NIWI) argument by replacing the zero-knowledge property with the following witness indistinguishability property. Note that unlike NIZKs, which can only exist in the CRS model, NIWIs are possible in the plain model.

Definition 10 (Statistical Witness Indistinguishability). A proof system Π = (CRSGen, Prove, SimProve, Verify) for a family of language distributions {D par } par is statistically witness indistinguishable, if for every adversary A, every λ, every (par , CRS, T ) ∈ Supp(CRSGen(1 λ )), all ρ ∈ Supp(D par ) and all x ∈ L ρ with witnesses w 1 , w 2 , we have

| Pr[A(CRS, ρ, x, π) = 1|π $ ← -Prove(CRS, ρ, x, w 1 )] -Pr[A(CRS, ρ, x, π) = 1|π $ ← -Prove(CRS, ρ, x, w 2 )]| ≈ 0
The property adapts to interactive protocols in a natural way.

A Pairing-Based Compiler for NIZKs from Σ-Protocols

In this section, we will describe our new approach to pairing-based non-interactive zero-knowledge arguments. Our starting point is a natural Σ-protocol for algebraic languages over abelian groups, which was used (implicitly or explicitly) in previous works [START_REF] Benhamouda | Implicit zero-knowledge arguments and applications to the malicious setting[END_REF][START_REF] Chaidos | Efficient designated-verifier non-interactive zero-knowledge proofs of knowledge[END_REF][START_REF] Hamouda | Efficient UC-Secure authenticated key-exchange for algebraic languages[END_REF]. Before describing the protocol and our NIZK construction, we formally introduce algebraic languages.

Algebraic Languages

We focus on languages that can be described by a set of algebraic equations over an abelian group. More precisely, we will consider languages of the form {x ∈ G l |∃w ∈ Z t p : M(x) • w = Θ(x)}, where M : G l → G n×t and Θ : G l → G n are linear maps, which can be sampled efficiently according to a language distribution D par . These languages have been used previously in several works on zeroknowledge proofs and hash proof systems over abelian groups [START_REF] Benhamouda | Implicit zero-knowledge arguments and applications to the malicious setting[END_REF][START_REF] Chaidos | Efficient designated-verifier non-interactive zero-knowledge proofs of knowledge[END_REF][START_REF] Hamouda | Efficient UC-Secure authenticated key-exchange for algebraic languages[END_REF], and are quite expressive: they capture a wide variety of languages, including but not limited to, linear and polynomial relations between committed values and the plaintexts of ElGamal-style ciphertexts, or polynomial relations between exponents. We call these languages algebraic languages.

It will prove convenient in this work to view the linear maps M and Θ as matrices and vectors over P l , where P l is the set of linear multivariate polynomial in l variables, via the natural extension.

Definition 11 (Algebraic Languages). Let t, l, n ∈ N, n > t and

P l := {[a 0 ] + l i=1 a i X i } ⊂ G[X = (X 1 , . . . , X l )
] the set of linear multivariate polynomials of degree at most 1. Let D par be a distribution that outputs pairs (M, Θ) ∈ P n×t l × P n l . We define the algebraic language L M,Θ ⊂ G n :

L M,Θ := {x ∈ G l |∃w ∈ Z t p : M(x) • w = Θ(x)}
where M(x) (resp. Θ(x)) denotes the matrix(resp. vector) received by evaluating every entry of M(resp. Θ) in the points of x.

Example: Linear Languages. Linear languages, capturing e.g. DDH relations, are obtained as a special case of algebraic languages by restricting M(x) to be a constant matrix, independent of x and Θ to being the identity. NIZKs for linear languages have been widely studied, see e.g. [START_REF] Jutla | Shorter quasi-adaptive NIZK proofs for linear subspaces[END_REF][START_REF] Kiltz | Quasi-adaptive NIZK for linear subspaces revisited[END_REF].

Definition 12 (Linear subspace languages). Let D par be a parameter distribution that outputs matrices from G n×t . For A ∈ Supp(D par ), we define the language L A := {x|∃w : Aw = x}. Specifically, the relation R A is defined such that (x, w) ∈ R A ⇔ x = Aw. We call D par witness samplable, Effectively, witness-samplability states that the language parameters can be sampled together with a trapdoor matrix T which allows to check whether x ∈ L. For linear languages, this trapdoor matrix is simply the exponents of all matrix entries, so the original matrix can be computed from the trapdoor, hence we only sample the latter in the distribution D par .

if
Σ-Protocol for Algebraic Languages. We introduce a generic Σ-protocol Π Σ for algebraic languages on Figure 3.

(M, Θ) ∈ Supp(Dpar ) P V w, [x] [x] r $ ← -Z k p [a] := [M(x)]r e $ ← -Zp d := ew + r check [M(x)]d ? = [Θ(x)]e + [a]
[a] e d Fig. 3. Σ-protocol ΠΣ for the generic language L M,Θ Theorem 13. The Σ-protocol Π Σ is complete, special honest-verifier zero-knowledge and special sound.

For the proof of Theorem 13 refer to e.g. [START_REF] Maurer | Unifying zero-knowledge proofs of knowledge[END_REF]. We will however recall the special honest-verifier zeroknowledge simulation algorithm S Π , since we need it in our construction. The simulator receives as input ([x], e) and samples d

Compiling Π Σ into a NIZK

The main idea of our construction is to keep the Σ-protocol in group G 1 while moving the challenge e to a group G 2 , which admits a bilinear pairing e : G 1 × G 2 → G T . This keeps the challenge hidden while allowing verification due to the pairing. For protocol Π Σ , the compiled NIZK Π C Σ is described in Figure 4. We present a detailed security analysis in Section 4.

CRSGen (1 λ ): Prove (CRS, ([M] 1 , [Θ] 1 ), [x] 1 ∈ G l 1 , w ∈ Z t p ): par := PG $ ← -PGGen(1 λ ) r $ ← -Z t p e $ ← -Zp [a] 1 := [M(x)] 1 r CRS := (PG, [e] 2 ), T := e [d] 2 := [e] 2 w + [r] 2 return (par , CRS, T ) return σ := ([a] 1 , [d] 2 ) SimProve (CRS, e, ([M] 1 , [Θ] 1 ), [x] 1 ): Verify (CRS, ([M] 1 , [Θ] 1 ), [x] 1 , σ = ([a] 1 , [d] 2 )): ([a] 1 , d) := SΠ ([x] 1 , e) check return σ := ([a] 1 , [d] 2 ) [M(x)] 1 • [d] 2 ? = [Θ(x)] 1 • [e] 2 + [a] 1 • [1] 2

Compiled NIZK as a ZAP

The CRS in our compiled NIZK consists of just one (random) group element from G 2 ; therefore, our protocol actually works in the common random string model. Furthermore, we observe that by allowing the verifier to choose the CRS himself and send it as its first flow, we can transform the NIZK into a statistical ZAP in the plain model (i.e., a two-round publicly-verifiable statistical witnessindistinguishable argument system, where the first flow can be reused for an arbitrary (polynomial) number of proofs). We stress that this provides the first known construction of statistical ZAPs from pairing-based assumptions; to our knowledge, the only existing constructions rely on the quasipolynomial hardness of LWE [START_REF] Badrinarayanan | B.: How to go beyond the black-box simulation barrier[END_REF][START_REF] Jain | Statistical zap arguments from quasi-polynomial lwe[END_REF]. We can apply the derandomisation technique from [START_REF] Barak | Derandomization in cryptography[END_REF] to obtain a NIWI argument in the plain model. Since correctness and soundness carry over directly from the NIZK case, it remains to show that our 2-round proof system is witness-indistinguishable. This is shown in Lemma 14.

Lemma 14. The ZAP resulting from the protocol Π C Σ for a family of language distributions {D par } par as described above is perfectly witness indistinguishable.

Proof. Let ρ := (M, Θ) ∈ Supp(D par ) and x ∈ L ρ with two witnesses w 1 , w 2 and let V be a (potentially misbehaving) verifier. Let [e] 2 be the CRS (i.e., first flow) chosen by V. We have to show that the distributions Prove([e] 2 , ρ, x, w 1 ) and Prove([e] 2 , ρ, x, w 2 ) are indistinguishable. A proof consists of the two vectors

[a i ] 1 = [M(x)] 1 r i and [d i ] 2 = [e] 2 w i + [r i ] 2
for random vectors r i , witnesses w i and e chosen by the verifier. Let w := w 1 -w 2 . Note that M(x)w = 0, since

M(x)w = M(x)(w 1 -w 2 ) = Θ(x) -Θ(x) = 0. For i = 1, we have π 1 = ([a 1 ] 1 = [M(x)r 1 ] 1 , [d 1 ] 2 = [e] 2 w 1 + [r 1 ] 2 )
. For i = 2 and by replacing w 2 with w 1 -w, we get

π 2 = ([a 2 ] 1 = [M(x)] 1 r 2 , [d 2 ] 2 = [e] 2 w 1 + ([r 2 -ew] 2 )
). Let r := -ew + r 2 and consider a proof using witness w 1 and random vector r . We get

[a ] 1 = [M(x)] 1 r = [M(x)] 1 (-ew +r 2 ) = -e [M(x)] 1 w +[M(x)] 1 r 2 = [M(x)] 1 r 2 = [a 2 ] 1 and [d ] 2 = [e] 2 w 1 + [r ] 2 = [d 2 ]
2 . This is identical to the proof using w 2 and randomness r 2 . r 1 , r 2 , and r are distributed identically (i.e. uniformly random), hence the proof distributions for witness w 1 and w 2 are identical.

Security Analysis

After describing our compiler, we will now argue its security in this section. We will first introduce two properties of distributions of algebraic languages, which will come in handy in the security analysis. Afterwards, we will introduce the new assumption under which all of our constructions are computationally sound. Lastly, we will perform the security reductions themselves.

Generalised Witness Samplablility

The definition of witness samplability for linear languages does not carry over to the case of algebraic languages, since only linear languages can be in the span of the kernel of their language trapdoor. To handle this issue, we adapt the witness samplability by requiring the samplability of a language trapdoor T, sampled together with the parameters of the language, which allows to efficiently check the rank of (M||Θ)(x), which will be full for words not in the language, and lower otherwise. We formally define our new notion of algebraic witness samplability in Definition 15.

Definition 15 (Algebraic Witness Samplability). Let t, l, n ∈ N with n > t. An algebraic language distribution D par , outputting pairs ρ = (M, Θ) ∈ P n×t l × P n l is called witness samplable, if there exists a second distribution D par outputting pairs (ρ = (M , Θ ), T ρ ∈ Z n×n p ), with D par (1) denoting the distribution of D par restricted to the first component, such that the following properties hold.

1. The distributions (D par ) and (D par (1)) are identical.

rank(T

ρ • (M ||Θ )(x)) = t + 1 x ∈ L ρ l < t + 1 x ∈ L ρ 3. ∃R, S permutation matrices such that (R • T ρ • (M ||Θ ) • S) (x)

is an upper triangular matrix

A family of language distributions {D par } par is witness samplable, if D par is witness samplable for all possible par . Note that R, S are efficiently computable from T ρ • (M||Θ)(x) (even without knowledge of T ρ ), as they only rearrange the rows and columns of T ρ • (M ||Θ )(x) to a specific form.

The first property states that we can sample a distribution with or without a trapdoor without altering the distribution. The second property is the rank condition itself, which shows language membership. The last property guarantees that the second condition can always be verified in polynomial time. To provide a better intuition of this property, we illustrate it on the language of ElGamal encryptions of a bit (which is a special case of the OR-language for DDH tuples) in Appendix A of the supplementary material.

Definition 16 (Trapdoor Reducibility). Let t, l, m, n ∈ N with n > t and D par be an algebraic language distribution which outputs pairs ρ = (M, Θ) ∈ P n×t l × P n l . D par is m-trapdoor reducible, if it is witness samplable with trapdoor distribution D par and for every language (ρ , T ρ ) ∈ Supp(D par ), we can instead sample a reducibility trapdoor T ρ ∈ Z (n-m)×n p such that the following properties hold.

-T ρ ⊂ T ρ , i.e. the rows of T ρ are a subset of the rows of T ρ .

-

rank(T ρ • (M||Θ)(x)) = n -m x ∈ L ρ m < n -m x ∈ L ρ -m columns of T ρ • (M||Θ)
are zero-columns and the last column is a non-zero column.

A family of language distributions {D par } par is trapdoor reducible, if D par is trapdoor reducible for all possible par .

Trapdoor reducibility captures a stronger notion of witness samplability where in addition to checking the rank of the matrix, we can also reduce the size of the check. Although this is not a necessary property, it allows us to perform reductions to weaker-parametrised assumptions and therefore to strengthen the security guarantees of our constructions for specific language distributions. We illustrate it as well in Appendix A of the supplementary material.

Extended-Kernel Matrix Diffie-Hellman Assumption

For the linear case, the security of our compiled NIZKs can be reduced to the KerMDH assumption. However for OR-proofs or general algebraic languages, it seems to be insufficient. Hence we propose a generalisation of the KerMDH assumption, which we will call the extKerMDH assumption, and to which we can reduce the soundness of our compiler for all algebraic languages.

Inadequacy of the KerMDH. Before we introduce our new assumption, we want to argue why the existing KerMDH assumption is not sufficient for our application. To do so we give an (informal) example.

For a linear language (described by matrix A), we can reduce soundness to the L 1 -KerMDH assumption for matrix distribution L 1 as follows. Suppose that a verifier in the Σ-protocol for a linear language(Figure 3) sends e as its challenge. Then the verification equation is

[Ad] = [x]e + [a].
If A is from a witness samplable distribution, we can use the trapdoor to find a vector t in the kernel of A, i.e. t • A = 0. Multiplying the above equation with t then yields 0 = [tx]e + [ta] and if x and a are not in the span of A, we have a non-zero vector in the kernel of [ 1 e ] 2 , namely ( ta tx )

T and therefore a solution to the KerMDH problem for [ 1 e ] 2 ∈ Supp(L 1 ). However for the simple binary OR proof from [START_REF] Cramer | Proofs of partial knowledge and simplified design of witness hiding protocols[END_REF] (see Figure 5 for more details), this approach already fails. Instead of one such equation, we get two equations of the form 0 = [t i x i ]e i + [t i a i ] for i ∈ {0, 1} and with e = e 0 + e 1 . Since the two vectors consist of group elements, we can't combine them to a single solution for the matrix

[ 1 e ] 2 .
However, what we obtain are two linearly independent vectors in the kernel of [1, e, e 0 ] 2 , namely

v 1 = [t 0 a 0 , 0, t 0 x 0 ] and v 2 = [t 1 a 1 , t 1 x 1 , -t 1 x 1 ]
. We assume that such a relation is also hard to compute and we formalise it as the extKerMDH assumption.

The extKerMDH Assumption.

Definition 17 (D k -l-extended Kernel Diffie-Hellman Assumption (D k -l-extKerMDH)). Let

l, k ∈ N, PG = (p, G 1 , G 2 , G T , g 1 , g 2 , e) $ ← -PGGen(1 λ
) and D k be a matrix distribution. The D k -l-extKerMDH assumption holds in G s relative to PGGen, if for all efficient adversaries A, the following probability is negligible.

Pr    [C] 3-s ∈ G l+1×k+l+1 3-s ∧ [B] s ∈ G l×k s ∧[C] 3-s • [D ] s = 0 ∧ rank(C) ≥ l + 1 PG $ ← -PGGen(1 λ ), D $ ← -D k ([C] 3-s , [B] s ) $ ← -A(PG, [D] s ) [D ] s := [ D B ] s   
The probability is taken over then randomness of A, D k and PGGen.

If in addition to the rank condition, C is also required to be an upper triangular matrix (in which case the bound on the rank can be verified in polynomial time), the assumption is called falsifiable

D k -l-extKerMDH.
This assumption is to the best of our knowledge new and so we want to give an intuition on why we deem it reasonable. First, it is a natural extension of the KerMDH assumption. We give the adversary more freedom by allowing it to extend the given matrix but require it to output multiple, linearly independent vectors in the kernel. As long as the number of linearly independent vectors is strictly larger than the number of vectors the adversary gets to add, breaking the assumption requires finding vectors in G 1 which depend on [M] 2 in a non-trivial way. Second, it is a static family of assumptions (as opposed to Q-type assumptions; once [M] 2 is fixed, our proof system will rely on an extKerMDH assumption with fixed parameters). Third, we consider the issue of falsifiability. It turns out that the extKerMDH assumption is not always falsifiable: to check the given matrix C for being a basis, one must break a DDH-like problem. However in many concrete cases of interest (formally, each time we will consider witness samplable languages), the matrix C can be brought in an upper triangular form where the rank will be visible and we can instead reduce the security to the falsifiable variant. Eventually, the assumption is unconditionally secure in the Generic Group Model (GGM) and can be reduced to the discrete logarithm problem in the Algebraic Group Model (AGM). For the proofs, refer to Appendix B.

Security Proof

With the two definitions and the new extKerMDH assumption, we can now finally prove the security of our construction.

Theorem 18. 1. The protocol Π C Σ described in Figure 4 is a NIZK argument for any algebraic language distribution D par outputting pairs ρ = (M, Θ) ∈ P n×t l × P n l , if the L 1 -t-extKerMDH assumption holds in G 2 relative to PGGen. 2. If the language distribution is witness samplable with trapdoors T ρ ∈ Z n×n p , then it is a NIZK argument if the falsifiable L 1 -t-extKerMDH holds in G 2 relative to PGGen. 3. If the language distribution is m-trapdoor reducible, then it is a NIZK argument if the falsifiable L 1 -(t -m)-extKerMDH holds in G 2 relative to PGGen.

Proof. To prove theorem 18, we have to show completeness, perfect zero knowledge and computational soundness. The first two properties are identical for all parts of the theorem. For the second and third part, the witness samplability and the trapdoor reducibility directly imply the soundness statements, if soundness holds in the first part.

Perfect Completeness: Let ρ = (M, Θ) ∈ Supp(D par ). If Θ(x) = M(x) • w and a = M(x) • r, we get [M(x)] 1 • [d] 2 = [M(x) • d] T = [M(x) • (e • w + r)] T = [M(x) • w • e] T + [M(x)r • 1] T = [Θ(x) • e] T + [a • 1] T (since Θ(x) = M(x) • w) = [Θ(x)] 1 • [e] 2 + [a] 1 • [1] 2
Perfect Zero Knowledge: We have to show that the distributions Prove and SimProve are identical. This directly follows from the perfect honest-verifier zero-knowledge property of the Σ-protocol, since we use its simulator in SimProve.

Computational Soundness: We will show that Π C Σ is computationally sound, if the L 1 -t-extKerMDH holds in G 2 relative to PGGen. Assume an adversary A which forges a proof for Π C Σ with nonnegligible probability. We will construct an adversary B against the L 1 -t-extKerMDH assumption, that uses adversary A and has the same success probability. B receives a challenge [ 1 e ] 2 from its challenger. B then sets [e] 2 as the CRS and samples language parameters ρ $ ← -D par . Now B runs A(CRS, ρ) and receives a statement x and a proof π = ([a] 1 , [d] 2 ) which are accepting with nonnegligible probability, i.e.

[M(x)] 1 • [d] 2 = [Θ(x)] 1 • [e] 2 + [a] 1 • [1] 2 0 = [a] 1 • [1] 2 + [Θ(x)] 1 • [e] 2 -[M(x)] 1 • [d] 2 0 = [a||Θ(x)|| -M(x)] 1 • 1 e d 2 If C := (a||Θ(x)|| -M(x)) has at least rank(C) = t + 1, then ([C] 1 , [d] 2
) is a solution for the assumption, since d has length t. This can be seen with simple linear algebra.

We know that M(x) has full rank t. By adding the two columns a and Θ(x), the rank cannot decrease. Assume Θ(x) and a are not in the span of M, i.e. A did produce a forgery. Then a and Θ(x) are completely independent of M and therefore the rank of the matrix will be increased by at least 1 and B has a solution. For a regular proof however, a and Θ(x) are in the span of M(x) and therefore linearly dependant on the columns of M(x), therefore the rank can not increase. This shows that C is full rank if and only if A outputs a valid forgery and B wins in this exact case.

For the second part of the theorem, B samples (ρ, T ρ ) from the trapdoor distribution D par , which is by definition indistinguishable from sampling ρ regularly. The statement is seen exactly as the first one except for a multiplication with the trapdoor matrix, which yields a full rank matrix in upper triangular form if and only if the given word is not in the language and we get a falsifiable solution. For the third part, B samples (ρ, T ρ ) from the trapdoor reducibility distribution (which is again indistinguishable from regular sampling) and B takes the matrix received by the multiplication with the reducibility trapdoor. By removing the zero columns and removing the corresponding elements from d, B can reduce d's size by exactly m and therefore gets a solution to the L 1 -(t-m)-extKerMDH.

Extension to Disjunctions of Languages

In this section, we will show how to obtain efficient OR-proofs by applying our compiler to the generic Σ-protocols for k-out-of-n disjunctions of [START_REF] Cramer | Proofs of partial knowledge and simplified design of witness hiding protocols[END_REF]. As we show in appendix C, disjunctions of languages can directly be described as algebraic languages; however, applying our transform directly to the disjunction protocol of [START_REF] Cramer | Proofs of partial knowledge and simplified design of witness hiding protocols[END_REF] allows us to save two group elements, hence we focus on this optimized variant.

We briefly recall the method of [START_REF] Cramer | Proofs of partial knowledge and simplified design of witness hiding protocols[END_REF] (for concreteness, we focus on 1-out-of-2 proofs; the general case is similar). It starts from two Σ-protocols for memberships into languages L ρ0 , L ρ1 , and produces a Σ-protocol for the language L ρ0∨ρ1 . Consider a prover knowing a witness w for x i ∈ L ρi but not for x 1-i ∈ L ρ (1-i) . The prover chooses a random e 1-i $ ← -Z p and uses the special honest-verifier zeroknowledge simulation algorithm to generate [a 1-i ], d 1-i which form an accepting proof for x 1-i ∈ L ρ (1-i) . Additionally it computes an honest commitment [a i ] for the Σ-protocol for L ρi and sends [a 0 ], [a 1 ] to the verifier, which returns a challenge e. The prover now sets e i := e -e 1-i and continues the honest protocol for x i ∈ L ρi , calculating d i and concludes the protocol by sending d 0 , d 1 and e 0 . The verifier can then calculate e 1 := e -e 0 and check both proofs. This protocol can be seen in Figure 5. While this does not immediately fit into the framework of Section 3, our approach is still applicable: The prover again chooses a challenge e 1-i $ ← -Z p and simulates the first proof as in the interactive variant and gets the second challenge for the honest proof part only in G 2 as

[e i ] 2 = [e] 2 -([1] 2 e 1-i ).
In addition to the two regular proofs, we have to include [e 0 ] 2 in the proof. This is illustrated in Figure 6. We get the following new, efficient OR-proof.

Theorem 19. Let D (0) par , D (1)
par be two algebraic language distributions outputting matrices of dimension n 0 × t 0 and n 1 × t 1 respectively. Applying the construction from Figure 6 yields a fully adaptive NIZK argument for the OR-language of ρ 0 ∈ Supp(D

(0) par ), ρ 1 ∈ Supp(D (1) par ) of size n 0 + n 1 + t 0 + t 1 + 1, if the L 1 -(n 0 + n 1 + 1) -extKerMDH assumption holds in G 2 .
If both language distributions are witness samplable, the above holds for the falsifiable L 1 -

(n 0 + n 1 + 1) -extKerMDH assumption. If D (0) par resp. D (1)
par is m 0 -resp. m 1 -trapdoor reducible, the above holds for the L 1 -(n 0 -m 0 + n 1 -m 1 + 1) -extKerMDH assumption.

The proof for Theorem 19 is almost identical to one for Theorem 18. The only difference lies in the soundness proof, where we apply the witness samplability (trapdoor reducibility) trapdoors of each language to the respective proofs separately and then combine the results by expressing e 1 as e -e 0 .

M0 $ ← -D (0) par M1 $ ← -D (1) par P V ([x0], [x1], w) ([x0], [x1]) ri $ ← -Z t p [ai] := Miri e1-i $ ← -Zp ([a1-i], d1-i) $ ← -S M 1-i ([x1-i], e1-i) e $ ← -Zp ei = e -e1-i di := eiw + ri e1 = e -e0 check [Mi]di ? = [xi]ei + [ai] i ∈ {0, 1} [a0], [a1] e d0, d1, e0
par := PG $ ← -PGGen(1 λ ) // xi = Miw e $ ← -Zp ri $ ← -Z t i p , e1-i $ ← -Zp CRS := (PG, [e] 2 ), T := e [ei] 2 = [e] 2 -[e1-i] 2 return (par , CRS, T ) ([ai] 1 , [di] 2 ) := ([Mi] 1 ri, [ei] 2 w + [r i ] 2 ) ([a1-i] 1 , d1-i) $ ← -S M 1-i ([x1-i] 1 , e1-i) return π := ([a0] 1 , [a1] 1 , [d0] 2 , [d1] 2 , [e0] 2 ) SimProve (CRS, T = e, ([Mi] 1 ) i∈{0,1} , [x0] 1 , [x1] 1 ): Verify (CRS, ([Mi] 1 ) i∈{0,1} , [x0] 1 , [x1] 1 , π): e0 $ ← -Zp parse π = ([e0] 2 , ([ai] 1 , [di] 2 ) i∈{0,1} )) e1 = e -e0 [e1] 2 = [e] 2 -[e0] 2 ([aj] 1 , dj) $ ← -S M j ([xj] 1 , ej) for j ∈ {0, 1} for j ∈ {0, 1} check return π := ([a0] 1 , [a1] 1 , [d0] 2 , [d1] 2 , [e0] 2 ) [Mj] 1 • [dj] 2 ? = [xj] 1 • [ej] 2 + [aj] 1 • [1] 2 Fig. 6. Compiled protocol Π c M 0 ∨M 1 . S (•)
denotes the SHVZK-simulator for the respective language.

The construction naturally extends to the 1 out of n setting by letting the prover choose n -1 challenges itself and setting the last as the difference of e and the sum of all chosen challenges. With n matrices M i , we get the following size, as the prover has to send n -1 challenges to uniquely determine the last challenge:

n i=1 (n i + t i ) + n -1.
In the special case of the disjunction of two DDH languages (as needed in e.g [START_REF] Gay | More efficient (almost) tightly secure structure-preserving signatures[END_REF]), the compiled OR-trick yields a proof with 7 group elements. The construction can easily be adapted to the setting of k-out-of-n disjunctions, by using a threshold secret sharing (e.g. [START_REF] Shamir | How to share a secret[END_REF]) to force the adversary to choose at most n -k challenges by itself. Our compiler can be applied in the same way as for the 1 out of n setting and yields NIZK arguments of size n i=1 (n i + t i ) + n -k.

Obtaining Non-Interactive Zero-Knowledge Proofs

The previously shown constructions all yields zero knowledge arguments, i.e. proofs which are perfect zero knowledge but only computationally sound. However, with a slight change (and at the cost of proof size), our construction can also be used to achieve zero knowledge proofs from Σ-protocols with linear answer. These proofs do not improve on the efficiency of Groth-Sahai proofs, but offer more simplicity. Additionally, the proofs are not dependant on any language distributions, as we do not require witness samplability. Lastly, we use a slightly different formalisation of zero-knowledge, namely computational composable zero-knowledge [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF]. To this end, we split the CRS generation into two algorithms, CRSGen for generating a regular CRS and CRSSim to generate a simulation CRS with a trapdoor T . Composable zero-knowledge requires that a regular CRS is indistinguishable from a simulated CRS and that given a simulated CRS, real and simulated proofs are indistinguishable.

The idea for the proofs is to use the unconditional special soundness of the Σ-protocol and adapt it to the NIZK setting. We provide two challenges in the CRS and have a prover answer both with the same randomness. The special soundness property now guarantees the existence of a witness, which results in perfect soundness. The problem with this approach is that it breaks the zero knowledge property due to the special soundness extractor. To prevent this trivial leakage, we provide the challenges to different generators. This yields unconditional soundness and computational zero knowledge, if the DDH assumption holds in G 2 .

Let Π be a Σ-protocol as in Figure 2 with linear answer, i.e. a 3 move protocol with commitment a, challenge e and response d, which is complete, special honest-verifier zero-knowledge and has the special soundness property.

The compiled protocol Π := (CRSGen Π , Prove Π , Verify Π , CRSSim Π , SimProve Π ) works as follows. For simplicity, we present the protocol for linear languages, however the algebraic case works analogously. Theorem 20. The compiled protocol Π is NIZK proof, if Π is a Σ-protocol with linear answer and the DDH assumption holds in G 2 relative to PGGen.

CRSGen Π (1 λ ): CRSSim Π (1 λ ): PG $ ← -PGGen(1 λ ) PG $ ← -PGGen(1 λ ) s0, s1 $ ← -Zp s0, s1 $ ← -Zp [e0] 2 , [e1] 2 $ ← -G2 e $ ← -Zp CRS := (PG, ([si] 2 , [eisi] 2 ) 1 i=0 ) CRS = (PG, ([si] 2 , [sie] 2 ) 1 i=0 ) return CRS T := (s0, s1, e) return (CRS, T ) Prove Π (CRS, [A] 1 , [x] 1 , w): SimProve Π (CRS, T = (e, s0, s1), [A] 1 , [x] 1 ): r $ ← -Z k p ([a] 1 , d) $ ← -SΠ ([x] 1 , e) [a] 1 := [A] 1 r d0 := s0d [di] 2 := [siei] 2 w + [si] 2 r d1 := s1d return π := ([a] 1 , ([di] 2 ) 1 i=0 ) return π := ([a] 1 , ([di] 2 ) 1 i=0 ) Verify Π (CRS, [A] 1 , [x] 1 , π = (([a] 1 , [di] 2 ) 1 i=0 )): for i ∈ {0, 1} check [A] 1 • [di] 2 ? = [x] 1 • [eisi] 2 + [a] 1 • [si] 2
Proof. We have to show, that Π is correct, perfectly sound and computationally composable zeroknowledge. We will prove these properties in the given order.

Correctness: As in the proof for 18, correctness follows directly from the correctness of the underlying sigma protocol, the only difference being that the prover answers two challenges with two different generators. Therefore, the compiled protocol is {perfectly, statistically, computationally} correct if and only if the underlying protocol is {perfectly, statistically, computationally} correct.

Perfect Soundness: Assume there exists an adversary A which breaks the soundness of Π with non-negligible probability, i.e.

([x] 1 , ([a] 2 , [d 1 ] 2 , [d 2 ] 2 )) $ ← -A(CRS, [A] 1
) is an accepting proof, yet x ∈ span(A). This means that

[A] 1 • [d i ] 2 = [x] 1 • [e i s i ] 2 + [a] 1 • [s i ] 2
and there are the two tuples ([a] 1 , e 0 , s -1 0 d 0 ) and ([a] 1 , e 1 , s -1 1 d 1 ), which are both accepting transcripts in the underlying Σ-protocol Π. By the special soundness property, there is an extraction algorithm E, which on input of these tuples would output a witness w for x ∈ span(A), which contradicts the assumption. Note that we can't compute w, since we can't recover e 0 , e 1 and the vectors d 0 , d 1 in Z p .

Computational composable zero-knowledge: First we need to show that the outputs of CRSGen and CRSSim are computationally indistinguishable. Let A be a PPT-adversary which can distinguish the two distributions. We will build an adversary B on the DDH assumption in G 2 , which wins with the same probability as A and does take only a constant time in addition to A's runtime.

B receives a DDH-challenge PG,

[1] 2 , [a] 2 , [b] 2 , [c] 2
for a, b, c ∈ Z p and has to output 1 iff c = ab. B now generates a CRS by setting s 0 = 1, s 0 e 0 := a, s 1 := b, s 1 e 1 := c. If c = ab, then e 0 = e 1 and therefore A receives a simulated CRS. Otherwise, e 0 := c b and therefore the CRS is distributed like a regular CRS, since b is random. B outputs 1, if A outputs that the CRS is simulated and 0 otherwise and therefore wins with the same probability as A.

Next, we have to show that simulated and real proofs are identical when using a simulated CRS. This step is completely analogue to the proof in 18 as the indistinguishability follows from the special honest-verifier zero-knowledge property of the underlying Σ-protocol.

Applications

NIZK for linear languages

Let G be a finite group of prime order p and D k,n be a matrix distribution. We apply our compiler to the standard Σ-protocol for membership to the linear language generated by A, for A ∈ Supp(D k,n ). This protocol was formally analyzed in [START_REF] Maurer | Unifying zero-knowledge proofs of knowledge[END_REF]. Applying our compiler yields the protocol Π C A shown in Figure 8.

CRSGen (1 λ ): Prove(CRS, [A] 1 , [x] 1 , w): par := PG $ ← -PGGen(1 λ ) r $ ← -Z k p [e] 2 $ ← -Zp [a] 1 := [A] 1 r CRS := (PG, [e] 2 ), T := e [d] 2 := [e] 2 w + [r] 2 return (par , CRS, T ) return π := ([a] 1 , [d] 2 ) SimProve(CRS, T = e, [A] 1 , [x] 1 ): Verify(CRS, [A] 1 , [x] 1 , π = ([a] 1 , [d] 2 )): d $ ← -Z k p check [A] 1 • [d] 2 ? = [x] 1 • [e] 2 + [a] 1 • [1] 2 [a] 1 := [A] 1 d -[x] 1 e return π := ([a] 1 , [d] 2 ) Fig. 8. Compiled protocol Π c A .
Theorem 21. Protocol Π c A is a NIZK for the language L A , if D k,n is witness samplable and the L 1 -kerMDH (= L 1 -0-extKerMDH) assumption holds in G 2 relative to PG.

Proof. If we show that A is k-trapdoor reducible, then the proof follows from Theorem 18. It is easy to see that all witness samplable matrix distributions D k,n are k-trapdoor reducible. We sample A ∈ Z n×k p and compute an element in the kernel of A, which is exactly the reducibility trapdoor.

The construction above includes proofs for DDH tuples, the Schnorr protocol [START_REF] Schnorr | Efficient identification and signatures for smart cards[END_REF], and general linear subspace membership. We compare our construction instantiated for the DDH language (and asymptotic) with the Groth-Sahai framework [START_REF] Groth | Efficient non-interactive proof systems for bilinear groups[END_REF] and the Kiltz-Wee proofs [START_REF] Kiltz | Quasi-adaptive NIZK for linear subspaces revisited[END_REF] on Table 1 from Section 1. Our construction is more efficient than Groth-Sahai both in terms of proof size as well as CRS size. For the verification, we also need less pairings (6 versus 24 for Groth-Sahai). Of course this comes at the (mild) cost of assuming witness sampleability of the language (Note that the security is based on the standard kerMDH assumption). On the other hand, our proofs are longer than the proofs from [START_REF] Kiltz | Quasi-adaptive NIZK for linear subspaces revisited[END_REF] (linear versus constant size). However our construction yields fully adaptive zero-knowledge arguments, while theirs yields quasi-adaptive zero-knowledge arguments and our CRS size is constant while theirs is linear. Our construction closes a gap in characterizing the efficiency of NIZKs for linear languages (with or without witness sampleability, with or without full adaptivity).

Disjunction of DDH Languages and Tight USS-QA-NIZKs

Using the construction of Section 5, we obtain a NIZK for the disjunction of two DDH languages with only 7 group elements. This is three group elements less than the best previously known NIZK for this language [START_REF] Ràfols | Stretching groth-sahai: NIZK proofs of partial satisfiability[END_REF]. We provide a self-contained description of the resulting proof system in Figure 6. As discussed in the introduction, combining this proof with the result of [START_REF] Abe | Shorter QA-NIZK and SPS with tighter security[END_REF], we obtain shorter tightlysecure QA-NIZKs with unbounded simulation-soundness (11 versus 14 group elements) and shorter IND-mCCA-secure PKE with tight security reduction (14 versus 17 group elements).

Tightly-Secure Structure-Preserving Signatures

NIZKs arguments are an important building block in structure-preserving signatures (SPS). Since our constructions yield shorter NIZK arguments for OR-proofs and (in the fully adaptive case) for linear subspaces, substituting existing proofs with our constructions directly improves various SPS schemes. For example, Gay et.al [START_REF] Gay | More efficient (almost) tightly secure structure-preserving signatures[END_REF] use an Or-proof for two DDH languages in their construction; using our OR-proof reduces the size of their tightly-secure SPS from 14 group elements to 11.

The same size was achieved recently by Abe et.al. [START_REF] Abe | Shorter QA-NIZK and SPS with tighter security[END_REF]. They use a new approach in describing the used OR-language as a conjunction statement and build a designated-prover quasi-adaptive NIZK from this formalization, which is shorter than the (publicly-verifiable) OR-proof of [START_REF] Ràfols | Stretching groth-sahai: NIZK proofs of partial satisfiability[END_REF] (7 versus 10 group elements). We notice that their OR-proof is compatible with our compiler, which allows us to reduce its size down to 5 group elements. This in turn reduces the size of the SPS by 2, resulting in a size of 9 group elements per signature.

Designated-Prover QA-NIZK for Disjunction of DDH languages First, we recall the definition of designated-prover quasi-adaptive zero-knowledge. Designated-prover quasi-adaptive noninteractive zero-knowledge is defined exactly as regular non-interactive zero-knowledge(2.4) except that the CRSGen algorithm may now depend on the language for which the proof system is intended and outputs additional, secret information for the prover. We will call this additional output ξ. The main idea behind the designated prover variant is an alternate formulation of the disjunction language for matrices from Z 2n×n p . However for n > 1, their formalisation does not yield a size improvement; therefore we will only consider it for the case of n = 1, which already captures the case of two DDHmatrices, which suffices to build tight SPS. Let M i = mi,0 mi,1 ∈ Z 2×1 p be two matrices. We define the language

L M0∨M1 := [x] = [ x0 x1 ] ∈ G 2 ∃w 0 , w 1 ∈ Z p s.t. 1 - m 0,0 m 0,1 ( x0 x1 ) = w 0 ∧ ( x0 x1 ) w 0 = m1,0 m1,1 w 1 Lemma 22.
For any two matrices M 0 , M 1 as above, the languages L M0∨M1 and L M0∨M1 are identical.

Proof. First, we will show that L M0∨M1 contains all vectors from L M0∨M1 , i.e. all vectors x which are in the span of either M 0 or M 1 . Assume x ∈ span(M 0 ). Then there exists a z ∈ Z p s.t. x = M 0 z. From this, the first condition of L M0∨M1 shows

w 0 = 1 -m 0,0 m 0,1 x = 1 -m 0,0 m 0,1 M 0 z = (m 0,0 -m 0,1 m 0,0 m 0,1 )z = 0 • z = 0
and since both matrices have a trivial kernel, the second condition shows w 0 = w 1 = 0 and x ∈ L M0∨M1 . On the other hand, assume that x = M 1 z. Then the second condition states

( x0 x1 ) w 0 = m1,0 m1,1 w 1 ⇔ m1,0 m1,1 zw 0 = m1,0 m1,1 w 1 ⇔ zw 0 = w 1
and from the first condition we get

w 0 = 1 -m 0,0 m 0,1 x = 0 since x ∈ span(M 0 ). Therefore L M0∨M1 ⊆ L M0∨M1 follows.
Next, we will show that L M0∨M1 ⊆ L M0∨M1 . Let x ∈ L M0∨M1 with witnesses w 0 , w 1 . First, assume that w 0 = 0. Then the first condition states that x ∈ span(M 0 ) and therefore x ∈ L M0∨M1 . Now assume w 0 = 0. Since M 0 and M 1 have full rank, the second equation is non-trivial, i.e. both sides aren't zero, especially w 1 = 0. Then we get

xw 0 = M 1 w 1 ⇔ x = M 1 w 1 w 0
and see that x ∈ span(M 1 ). This proves L M0∨M1 ⊆ L M0∨M1 and therefore

L M0∨M1 = L M0∨M1
This different formalisation of the OR-language with a conjunction instead of a disjunction allows us to express the language with a single matrix as an algebraic language. As a preparation, we will rearrange the equations to give a better understanding of the resulting matrix. By rearranging the first condition and setting γ = m0,0 m0,1 , we get x 0 = w 0 + γx 1 and for the second x i w 0 -m 1,i w 1 = 0. These equations describe membership in the language, however to ensure soundness, we also need to include a commitment to γ. Then we get the following algebraic language for L M0∨M1 :

M =       1 0 0 X 1 X 0 -m 1,0 0 0 X 1 -m 1,1 0 0 0 0 1 0 0 0 s 1       , Θ =       X 0 0 0 c 0 c 1      
where (c 0 , c 1 ) is an ElGamal commitment to γ with randomness α. By applying our compiler to this language, we obtain a proof with 9 group elements. However, the commitment part of the proof is independent of the word x and only depends on the matrix M 0 . By relaxing the security of our NIZK from fully adaptive to quasi adaptive, we can move the whole commitment part of the NIZK to the CRS. This adds 6 group elements to the CRS (

[c 0 ] 1 , [c 1 ] 1 , their counterparts [ ĉ0 ] 1 , [ ĉ1 ] 1 in a and [d α ] 2 , [d γ ] 2
, the blinded values of α and γ in d) but removes 4 from the proof (two from d and two from a), yielding a proof of size 5. The resulting protocol is shown on Figure 9. By plugging our new designated-prover QA-NIZK argument into the transformation of [START_REF] Abe | Shorter QA-NIZK and SPS with tighter security[END_REF], we get Lemma 23.

Lemma 23. There exists a structure-preserving signature scheme which reduces to the SXDH assumption and the L 1 -1-extKerMDH assumption with security loss 6 log Q, where Q is the number of signing queries, with a signature size is 9 group elements and a public key size of n + 15 elements (for length-n messages).

A comparison of the resulting SPS to existing schemes can be found in Table 4. We note that our tight SPS can be converted into a bilateral tight SPS (where messages can be from both G 1 and G 2 ) using the generic transform of [START_REF] Kiltz | Structure-preserving signatures from standard assumptions, revisited[END_REF], leading to a bilateral tightly-secure SPS of size 12 group elements (versus 14 for the best known bilateral tight SPS [START_REF] Abe | Shorter QA-NIZK and SPS with tighter security[END_REF]).

CRSGen(1 λ , [M] 1 , M0, M1): Prove(CRS, ξ, [M] 1 , [x] 1 , w): e $ ← -Zp, s, α $ ← -Zp r $ ← -Z 3 p γ := m 0,0 m 0,1 a ĉ0 ĉ1 1 = [M(x)] 1 r α γ (c0, c1) = ([α] 1 , [sα + γ] 1 ) d dα dγ 2 = [e] 2 w + r α γ α, γ $ ← -Zp return π = ([a] 1 ∈ G 3 1 , [d] 2 ∈ G 2 2 ) ( ĉ0, ĉ1) = ([ α] 1 , [s α + γ] 1 ) dα = α • e + α dγ = γ • e + γ CRS = ([s] 1 , [e] 2 , [dα] 2 , [dγ] 2 , ([ci] 1 , [ ĉi] 1 ) 1 i=0 ) ξ = (α, γ, α, γ) T = (e, s, α, γ, α, γ) return (CRS, T , ξ) SimProve(CRS, [M] 1 , T , [x] 1 ): Verify(CRS, [x] 1 , π): d $ ← -Z 3 p parse π = ([a] 1 , [d] 2 ) a ĉ0 ĉ1 1 = [M(x)] 1 d dα dγ -e [x] 1 check return π = ([a] 1 ∈ G 3 1 , [d] 2 ∈ G 2 2 ) [M(x)] 1 • d dα dγ 2 ? = [Θ(x)] 1 • [e] 2 + a ĉ0 ĉ1 1 • [1] 2
Fig. 9. Designated-prover quasi-adaptive non-interactive zero-knowledge argument for the or-language of two DDH matrices.

Ring Signatures

An example of the use of k-out-of-n OR-proofs is the construction of sublinear ring signatures in the standard model [START_REF] Chandran | Ring signatures of sub-linear size without random oracles[END_REF][START_REF] Ràfols | Stretching groth-sahai: NIZK proofs of partial satisfiability[END_REF]. The two constructions produce signatures of size O( √ N ), where N is the size of the ring. The previous works reduce the size of the signature by rearranging the list of potential signers in the ring into a square matrix, and commit to two bit vectors of weight one, where one denotes the row and the other the column of the used key. Then, a NIZK is used to show that the signature was produce with the key at the corresponding (committed) coordinates in the matrix. This NIZK requires at its core a proof that the two vectors are actually bit vectors and sum to 1. This can be rephrased as an (n -1)-out-of-n proof of opening of the commitments to 0, together with a proof that their sum opens to one. The proof given in [START_REF] Ràfols | Stretching groth-sahai: NIZK proofs of partial satisfiability[END_REF] requires 4 • √ N group elements, while our proof from Section 5 only requires 3 • √ N + 1 group elements.

Supplementary Material

A Witness Samplability Examples

A.1 Example for Algebraic Witness Sampleability

To provide a better intuition of algebraic witness sampleability, we illustrate it below on the language of ElGamal encryptions of a bit (which is a special case of the OR-language for DDH tuples).

Example 24. Distribution of languages of ElGamal encryptions of a bit:

M ∈            1 0 0 s 1 0 0 X 1 1 0 X 2 -1 s     s $ ← -Z p        ∈ P 4×3 2 , Θ =     X 1 X 2 0 0     ∈ P 4 2 L M,Θ := {(x 1 , x 2 ) ∈ G 2 |r $ ← -Z p , b ∈ {0, 1}, x 1 = [r], x 2 = [sr + b]} For x = (x 1 , x 2 )
as above, the witness is w = (r, b, -rb). This can be easily checked:

M(x) • w =     1 0 0 s 1 0 0 r 1 0 sr + b -1 s     •   r b -rb   =     r rs + b rb -rb srb + b 2 -b -srb     =     r rs + b 0 (b + 1)(b -1)     =     r rs + b 0 0     = Θ(x)
The language distribution is witness samplable since for every s ∈ Z p , we have the trapdoor T.

T =     1 0 0 0 s (-1) s (-1) 0 0 1 0 0 0 s (-1)    
Looking at the matrix product:

T • (M||Θ) =     1 0 0 0 s (-1) s (-1) 0 0 1 0 0 0 s (-1)     •     1 0 0 X 1 s 1 0 X 2 0 X 1 1 0 0 X 2 -1 s 0     =     1 0 0 X 1 0 sX 1 -X 2 0 sX 1 -X 2 0 X 1 1 0 0 sX 1 -X 2 + 1 0 0    
With the right permutations (swapping column 2 and 4), the matrix can be brought into an upper triangular form. Furthermore, if x ∈ L M,Θ , then row 2 or 4 will consist only of zeros and the matrix won't have full rank. Otherwise both will be non-zero and therefore the matrix has full rank.

A.2 Example for Trapdoor Reducibility

We continue the previous example and show the trapdoor reducibility of the language of ElGamal ciphertexts of bits.

Generic (Bilinear) Group Model. The generic group model was first introduced by Shoup in [START_REF] Shoup | Lower bounds for discrete logarithms and related problems[END_REF] and extended to the setting of bilinear groups by Groth [START_REF] Groth | Sub-linear size pairing-based non-interactive zero-knowledge arguments[END_REF], however only for the case of symmetric pairing groups. We use a simple extension to capture asymmetric pairings. The intention of the generic group model is to limit an adversary to only using the regular group operation when trying to solve a hard problem. This is done by hiding the group structure from the adversary and only providing it with group operation oracles and handles to (hidden) group elements. This restricted model allows for information theoretic proofs of hardness, which gives strong guarantees for generic groups. Elliptic curves are an example for groups which are presumed to be generic.

In the generic group model, we define an injective encoding function • : G → {0, 1} n , which assigns a random bitstring to each group element. The encoding function is defined adaptively by the challenger, who chooses a fresh random encoding, whenever a new group element comes up. The adversary only receives encodings of group elements. Since the adversary now can't compute anything by itself, the challenger provides the adversary with a group operation oracle O(•, •), which takes two encodings of group elements and returns the encoding of their "sum". This way, provided an encoding of a group generator, the adversary can generate random group elements and invert group elements in polynomial time using the standard double and add algorithm. Checking the equality of two group elements is simply comparing their encodings.

In the asymmetric pairing group setting, we have three groups instead of one and the pairing e. However, the approach from before extends naturally to this setting. We define three encoding functions • i : G i → {0, 1} n for i ∈ {1, 2, T }, one for each group. For simplicity, we will slightly abuse this notation and combine it with the implicit notation, i.e. for x ∈ Z p , x i := [x] i i . The challenger now provides three group operation oracles as well, again one for each group. Note that the encoding functions are still chosen adaptively. Especially, if an element [x] 1 ∈ G 1 already has an encoding x 1 , the same encoding will not necessarily be defined for group G 2 . If an encoding is not defined for a group but given to the respective oracle, the oracle returns ⊥. Additionally, a fourth oracle O P air (•, •) has to be provided, which, given the encoding of two group elements x 1 , y 2 , returns the encoding of xy T . Algebraic (Bilinear) Group Model For the Algebraic Group Model (AGM), we will use and extend the definition of Fuchsbauer et.al. [START_REF] Fuchsbauer | The algebraic group model and its applications[END_REF] and Mizuide et.al [START_REF] Mizuide | Tight reductions for diffie-hellman variants in the algebraic group model[END_REF]. The AGM takes the middle ground between the standard model and the generic group model. Adversaries in the AGM are allowed to see and use the structure of the group, however they are required to also output a representation of every output group element as a linear combination of the inputs. Adversaries adhering to this requirement are called algebraic. The definition of [START_REF] Fuchsbauer | The algebraic group model and its applications[END_REF] only captures regular groups. Their definition is extend in [START_REF] Mizuide | Tight reductions for diffie-hellman variants in the algebraic group model[END_REF] for symmetric pairing groups with outputs only allowed to be from the target group G T . For our protocols however, we require asymmetric pairings and multiple outputs from different groups. We will therefore extend their definition of algebraic adversaries accordingly and define the Algebraic Asymmetric Bilinear Group Model(AABGM).

Informally, an algebraic adversary in our model has to output a representation of each output group element relative to all input elements of the respective group. For elements from the target group G T , representations relative to pairings of input elements are also allowed. This notion is formalized in the following Definition 29.

Definition 29 (Algebraic Adversaries

). Let PG = (p, G 1 , G 2 , G T , g 1 , g 2 , e) be a pairing group and [x] 1 = ([x 1 ] 1 , . . . , [x n ] 1 ) ∈ G n 1 , [y] 2 = ([y 1 ] 2 , . . . , [y m ] 2 ) ∈ G m 2 , [Z] T = ([z 1 ] T , . . . , z l ) ∈ G l T be vectors in G 1 , G 2 and G T respectively. Let [x] 1 , [y] 2 , [z] T be the input for an algorithm A. A is called algebraic, if in addition to its output S = S (1) 1 1
, . . . , S

, S

, . . . , S

, S

T ) 1 T . . . , S (T ) l T ∈ G n 1 × G m 2 × G l T , A provides a vector s = ((α ij ) 1≤i≤n 1≤j≤n , (β ij ) 1≤i≤m 1≤j≤m , (γ ijk ) 1≤i≤l 1≤j≤n 1≤k≤m , (γ ij ) 1≤i≤l 1≤j≤l ) ∈ Z ζ p with ζ = n • n + m • m + l • (l + n • m) such that S (1) i = n j=1 α ij x j for i ∈ {1, . . . , n } S (2) i = m j=1 β ij y j for i ∈ {1, . . . , m } S (T ) i = n j=1 m k=1 e(x j , y k ) γ ijk + l j=1 γ ij z i for i ∈ {1, . . . , l } (
The additional output will be denoted as (S; s)

$ ← -A([x] 1 , [y] 2 , [z] T ).

B.2 Analysis of extKerMDH in the GGM and AGM

We now prove the security of our assumption in the Generic Bilinear Group Model and the Algebraic Asymmetric Bilinear Group Model for the matrix distribution L k . We start with the algebraic group model and prove that the dlog problem implies the hardness of the L k -extKerMDH.

Theorem 30. dlog

(1,1+ O(k 3 ) t ) =======⇒ L k -l-extKerMDH, i.e. if the dlog problem is ( , t + O(l 3
))-hard in the algebraic bilinear group model, then the L k -l-extKerMDH problem is ( , t)-hard in the algebraic bilinear group model as well.

Proof. Let PG be a pairing group setting. Assume an algebraic adversary A on the L k -l-extKerMDH assumption. We will describe an adversary B on the dlog assumption which queries A exactly once and only computes a polynomial number of additional operations and is still algebraic.

Let [e] 2 be the dLog challenge for adversary B in group G 2 . B then generates a matrix

M =      1 • • • 1 e 1 0 . . . 0 e k      2 $ ← -L k
and replaces e 1 with e. Then B calls A with input (PG, [M] 2 ) and receives a solution

(C = ([c i,j ] 1 ) i,j , [ B] 2 )
with probability after time t with witness vector s. Since A receives no inputs in G 1 , s contains the discrete logarithms of all c i,j . Let M := ( M B ). If A did indeed output a valid solution, then C M = 0 and therefore for i ∈ {0, . . . , l}: c i,0 + c i,1 e + k+1+l j=k+2 c i,j mj,i = 0.

Each equation contains l + 1 variables and there are l + 1 equations. This equation system can be solved in time O(l 3 ) and contains e as a variable, so B can output it as its solution by using only algebraic operations.

In the generic bilinear group model, we can use the same technique, however the generic adversary A will not output a representation of its solution. Yet B can compute it, since it has to simulate the group operation oracles for A. A again gets only the generator for group G 1 and by counting all oracle queries of A to the group operation oracle for G 1 , B gets the discrete logarithms of the matrix C as in the proof above. It remains to describe how to simulate the bilinear groups for the adversary A. =======⇒ L k -l-extKerMDH, i.e. if the discrete logarithm (dLog) problem is ( , t+O(l 3 ))-hard in the generic bilinear group model, then the L k -l-extKerMDH problem is ( , t)-hard in the generic bilinear group model as well.

Proof. Let A be a generic adversary on the L k -l-extKerMDH assumption. with running time t and success probability . We will construct a generic adversary B on the dLog assumption which uses adversary A. Let e 2 be the dLog challenge of B and let O 2 (•, •) denote the group oracle for the challenge group of B. B generates k -1 random elements ( e 2 2 , . . . , e k 2 ) from its group using the oracle O 2 and sets e 1 := e and

M 2 =      1 2 • • • 1 2 e 1 2 0 2 . . . 0 2 e k 2     
M 2 is given to A as its challenge. Additionally, B has to provide encodings of generators to pairing groups to A, however B only knows an encoding for its own group. Therefore, B generates a pairing group PG $ ← -PGGen with G 2 = G and chooses random encodings for the generators g 1 , g T itself and gives them to A. Now B has to answer the oracle queries of A. For group G 1 and G T , B behaves just like a normal oracle, since B does know the underlying groups. For G 2 , the group provided to B by the challenger, B forwards all oracle queries to its own oracle O 2 and forwards its answers to A. The pairing oracle is the challenging part, since B does not know e. Therefore, B internally replaces e with a variable X and regards elements from G 2 as polynomials in X, i.e. it outputs a new encoding, if a polynomial is not equal to an already seen polynomial. This introduces an error probability, since two different polynomials might yield the same group element when evaluated at e. However by the Schwartz-Zippel-Lemma [START_REF] Schwartz | Probabilistic algorithms for verification of polynomial identities[END_REF][START_REF] Zippel | Probabilistic algorithms for sparse polynomials[END_REF], an upper bound for this probability is 1 p and therefore negligible and B's simulation of the oracles is perfect except with negligible probability. By recording all of A's oracle queries, B gets the discrete logarithms of A's solution from G 1 and can therefore solve its challenge as described in the proof for Theorem 30.

With the above, we can prove an even stronger statement: We can also show that the L k -l-extKerMDH is as hard as the L k -KerMDH for any k and any l. The proof is straightforward with the algorithm above: Instead of embedding the dlog challenge in a fresh matrix, one simply forwards the KerMDH challenge matrix to the adversary and uses the same method to compute all entries of the challenge matrix. One can then use linear algebra to find an element in the kernel of the matrix. and corollary 32 follows.

C Disjunctions of Algebraic Languages

C.1 Disjunction matrices

We show that the disjunction of algebraic languages can again be described as an algebraic language. This approach was described in [START_REF] Benhamouda | Implicit zero-knowledge arguments and applications to the malicious setting[END_REF] and we recall it in Definition 33.

Definition 33 (Disjunction matrices). For i ∈ {0, 1}, let M i ∈ P ni×ti li and Θ i ∈ P ni li define two algebraic languages L Mi,Θi .

The disjunction matrix M ∈ P (n0+n1+1)×(t0+t1+2) l0+l1

and target vector Θ ∈ P n0+n1+1 l0+l1 for the language L M, Θ = L (M0,Θ0)∨(M1,Θ1) is built as seen in Figure 10 The idea of this construction is simple: Due to the -1 in the first component of Θ, either the (t 0 + 1)-component or the (t 0 + t 1 + 2)-component (or both) of the witness has to be non-zero. Therefore, either Θ 0 or Θ 1 are added at least once to the result of the matrix-witness multiplication. Since all entries of Θ except for the first are 0, they have to be cancelled by their respective matrix M 0 or M 1 , since all other entries in the matrix are 0, too. Therefore, any accepting witness for the new algebraic language contains at least one witness for one of the two languages, which is exactly what is required.

Since the resulting matrix is again algebraic, we can apply our construction and get a NIZK argument the size of both proofs for the single languages plus two G 2 element. One can easily check that if both matrix/vector pairs are from witness samplable (trapdoor reducible) distributions with trapdoors T 0 , T 1 , then the disjunction matrix distribution is witness samplable (trapdoor reducible) too. The new trapdoor matrix is simply the combination of both trapdoors together with a row of at the top and a column in the front containing exactly one 1 as seen in Figure 11. One can expand this construction to obtain 1 out of n NIZK arguments by adding more matrices on the diagonal with their respective Θ and added 1s to the first row above the Θs. The resulting arguments consist of n i=1 (t i + n i ) + n + 1 group elements, where the matrix M i as dimensions n i × t i .

M :=              0 • • • 0 1 0 • • • 0 1 0 • • •
T :=              1 0 • • • • • • • • • 0 0 0 • • • 0 . . .

C.2 k-out-of-n Disjunction Matrix

Now we will adapt the disjunction matrix to the k out of n setting. First we will define a k out of n OR-language.

Definition 34 (k out of n OR Languages). Let (n i , t i , l i ) n i=1 ∈ N and S i = (M i ∈ P ni×ti li , Θ i ∈ P ni li ) n i=1 describe n algebraic languages. We denote the k out of n disjunction language for the set S := {S i } as

L k S := {(x ∈ G li ) n i=1 |∃I ⊂ {1, . . . , n}, |I| ≥ k : ∀i ∈ I∃w i ∈ Z ti p : M i (x i ) • w i = Θ i (x i )}
The next step is to adapt the disjunction matrix from Figure 10. The main problem lies in assuring that the prover knows enough witnesses. For the 1 out of n scenario, this is easy as we only need to ensure that at least one witness is given, which can be done by simply adding the values. However for k ≥ 2, this approach does not work any longer. Instead we use a slightly different approach. We still add all the values multiplied with the Θs, but now they have to sum to k and not -1. If all values are either 0 or 1, this is enough to show that the prover knows exactly k witnesses. Therefore we let the prover commit to the factors and prove, that all these commitments contain a bit. We can do this with the ElGamal commitments of bits that we introduced in Example 24.

Definition 35 (Generalised Disjunction Matrix).

Let M E and Θ E denote the polynomial matrix and vector from 24. Then the generalised k out of n disjunction matrix M k S and the vector Θ k S for a set of algebraic languages S as above looks as follows.

  extend the implicit notation to the three groups G 1 , G 2 , G T . The setup algorithm of our proof system picks a random e ∈ Z p and sets the common reference string to [e] 2 . The prover computes [a] 1 as in the Σ-protocol, and obtains the value d embedded in G 2 by computing [d] 2 := w•[e] 2 +r•[1] 2 . Checking the verification equation can still be done, with the help of the pairing: the verifier checks that [

Fig. 1 .

 1 Fig. 1. Generic Σ-protocol for algebraic languages L M,Θ from a distribution Dpar

Fig. 2 .

 2 Fig. 2. General Σ-protocol.

  there is a distribution D par which outputs matrices from Z n×t p s.t. the distributions of A $ ← -D par and [B] $ ← -D par are indistinguishable.

$

  ← -Z t p . Then it sets [a] := M(x)d -e[Θ(x)] and returns ([a], d).

Fig. 4 .

 4 Fig. 4. Compiled protocol Π C Σ , where SΠ denotes the special honest-verifier simulator of ΠΣ and ([M] 1 , [Θ] 1 ) ∈ P n×t l × P n l is sampled from Dpar .

Fig. 5 .

 5 Fig.5. Sigma protocol Π M 0 ∨M 1 for the or language L M 0 ∨M 1 from[START_REF] Cramer | Proofs of partial knowledge and simplified design of witness hiding protocols[END_REF]

Fig. 7 .

 7 Fig. 7. Compiled protocol Π from Π. SΠ denotes the special honest-verifier zero-knowledge simulation algorithm of the Σ-protocol Π.

  Theorem 31. dlog(1,1+ O(k 3 ) t )

Corollary 32 .

 32 If the L k -KerMDH problem is ( , t + k • O(l 3))-hard in the generic(algebraic) bilinear group model, then the L k -extKerMDH problem is ( , t)-hard in the generic(algebraic) bilinear group model as well.

Fig. 10 .

 10 Fig. 10. Disjunction matrix

Fig. 11 .

 11 Fig. 11. Disjunction trapdoor

Table 1 .

 1 Comparison of existing NIZKs for the DDH language (linear languages described by an n × t

		Assumption CRS Proof size	Pairings	WS Fully Adaptive
	GS [45]	SXDH	4	4(n + 2t) 24(n(4t + 8))
	KW [59] KerMDH	6	2(2)	3(n + 1)
	KW [59] KerMDH	4	1(1)	2(n)
	Ours	KerMDH	1	3(n + t)	6(n + nt + 2)
	matrix). CRS/Proof size denotes the number of group elements in the common reference string/a proof.
	Pairings denotes the number of pairing operations in proof verification. "WS" indicates whether the proof
	system is restricted to witness sampleable languages.

Table 2 .

 2 Comparison of existing NIZKs for the OR of two DDH languages (two linear languages described by ni × ti matrices for i ∈ {1, 2}). CRS denotes the number of group elements in the common reference string. "WS" indicates whether the proof system deals only with witness sampleable languages. Note that our scheme can in fact handle non-witness sampleable languages; however, this comes at the cost of making the underlying extKerMDH assumption non-falsifiable.

	Scheme Assumption CRS	Proof size	Pairings	WS
	[44, 73] SXDH	4	10( 2 i=1 ni + 2ti + 2) 24( 2 i=1 4ni + 2niti)
	Ours	extKerMDH	1	7( 2 i=1 ni + ti + 1)	12( 2 i=1 ni + niti + 4)

Table 3 .

 3 Comparison of existing unbounded simulation-sound NIZKs for linear languages.

			2n + 3(t + λ) + 10 20	2n + 30	O(Q)	DLIN
	[59] (2t + 6, n + 6)	(4, 0)	t(n + t + 2)	O(Q)	SXDH
	[61] 2n + 3t + 24λ + 55 42	2n + 10	3λ + 7	DLIN
	[33] (t + 6λ + 1, n + 2) (3, 0)	n + 4	4λ + 1	SXDH
	[4]	(3t + 14, n + 12)	(n + 16, 2t + 5) 7n + 5t + 3nt + 121 36 log(Q) SXDH
	[3]	(4t + 4, 2n + 8)	(8, 6)	n + 30	6 log(Q) SXDH
	Ours (4t + 8, 2n + 3)	(8, 3)	n + 18	6 log Q	SXDH, extKerMDH
						The notation
	(x1, x2) denotes x1 elements in G1 and x2 elements in G2. Q denotes the number of simulation queries, λ
	is the security parameter. (n, t) are the parameters of the underlying linear language, defined by a matrix
	M ∈ Z n×t p	, with n > t.

  ). A three-move protocol Π R for a relation R has the special soundness property, if a polynomial time algorithm E exists, which for a statement x and two accepting

transcripts (a, e, d), (a, e , d ) of Π R with e = e outputs a witness w, s.t. (x, w) ∈ R with overwhelming probability.

Definition 6 (Special honest-verifier zero-knowledge). A three-move protocol Π R for a relation R is special honest-verifier zero-knowledge, if there exists a polynomial-time simulator S such that the distributions of S(x, e) and the transcript of an honest protocol execution between P and V are identical for (x, w) ∈ R, e ∈ {0, 1} λ .

Alternatively, the Fiat-Shamir transform offers provable security in the random oracle model; we note that there have been recent developments regarding instantiating Fiat-Shamir in the standard model under strong assumptions[START_REF] Canetti | Fiat-Shamir and correlation intractability from strong KDM-secure encryption[END_REF][START_REF] Kalai | From obfuscation to the security of Fiat-Shamir for proofs[END_REF].

Acknowledgements. We would like to thank Dennis Hofheinz for discussions and contributions to early stages of this work, and Eike Kiltz for helpful comments.

The first author was supported by ERC Project PREP-CRYPTO (724307), and the second author was supported by the Deutsche Forschungsgemeinschaft (DFG) under Germany's Excellence Strategy (EXC 2092 CASA), and the German Federal Ministry of Education and Research (BMBF) iBlockchain project.

Example 25. Let M, Θ, T be defined as in Example 24. The witness reducibility trapdoor for L M,Θ is T := s (-1) s (-1) 0 0 s (-1)

One can easily see that T is a submatrix of T. Looking at the product T • (M||Θ)(x) shows the other two properties:

The resulting matrix contains exactly the two rows used to check the rank of the matrix and contains two zero columns without the last column being one of them. This shows that the language L M,Θ is 2-trapdoor reducible.

B Security of extKerMDH in the Generic and Algebraic Group Models

B.1 Generic and algebraic groups

In this section, we study the extKerMDH assumption. To argue the soundness of this new assumption, we will prove that it holds in generic and algebraic group models. We begin with some notation (adapted from [START_REF] Kiltz | The algebraic group model and its applications[END_REF]) and then introduce the Generic Group Model and the Algebraic Group Model.

Definition 26 (Time and Adv). Let G ρ be a security game with parameters ρ and A an adversary for said game. We denote the result of the game G ρ with adversary A as G A ρ and say that A wins, if

For the advantage of an adversary A in a security game G ρ , we write Adv G ρ,A := Pr[G A ρ = 1] and we denote the running time of the experiment as Time G ρ,A . In the generic group model, oracle queries count as one time unit.

Next, we define how to measure the hardness of a problem. Definition 27 (( , t)-hardness). We call a problem G ( , t)-hard in the generic(algebraic) group model, if for any generic(algebraic) algorithm A it holds that

Lastly, we define generic/algebraic reductions.

Definition 28 (Generic/algebraic reduction). Let G, H be two generic(algebraic) security games.

We write

= ==== ⇒ G if there is a generic(algebraic) algorithm R, called a (∆ , ∆ t )-reduction, such that for every generic(algebraic) algorithm A, an algorithm B is defined as R A (denoting the algorithm R with access to A) which satisfies

= ==== ⇒ G states that if H is hard in the GGM/AGM, then G is too. This is equivalent to saying that if H is ( , t)-hard, then G is ( • ∆ , t ∆t )-hard. As an example, the dlog problem is ( t p , t)-hard in generic groups [START_REF] Maurer | Abstract models of computation in cryptography (invited paper)[END_REF][START_REF] Shoup | Lower bounds for discrete logarithms and related problems[END_REF].