# Upper bound for the length of non-interactive zero-knowledge proofs of knowledge

In a hybrid protocol $$\pi$$ for which I want to proof uc-security in the absence of corrupted parties, there is an ideal functionality $$\mathcal{F}_{SMT}$$ for secure message transfer that leaks the message length to the attacker.

Also, there are non-interactive zero-knowledge proofs of knowledge that are built using $$\Sigma$$-protocols and the Fiat-Shamir heuristic.

In this protocol there is an exchange of messages via $$\mathcal{F}_{SMT}$$ that include an instance and a corresponding NIZK proof of knowledge.

The instance includes some constant-size values, a commitment to a value (which is also assumed to be of constant size) and a list of party identifiers of variable size $$l$$, with $$0 < l \leq MAX$$.

I still can make some changes to the protocol, e.g. to add padding of messages. Ideally, I want this kind of message to be of constant size. Therefore, I want to find an upper bound for the length of the possible proofs in this protocol and use this to pad all messages to the same, constant size.

So my question is: How do I find this upper bound for NIZK proofs constructed as mentioned above?

• There exist Zero-knowledge proof techniques with fixed length proofs (and with a corresponding fixed length statement to be proven, the whole bundle is fixed length). See zk-snark, zk-stark – Natanael Apr 4 at 0:19

1) use NIZKs with "almost optimal size", i.e., of size $$w + \mathsf{poly}(k)$$, where $$w$$ is the witness size, and $$\mathsf{poly}(k)$$ is a fixed polynomial in the security parameter. Such NIZKs exist from the LWE assumption (by combining this recent breakthrough and this paper), or from more exotic assumption. This is the generic, "heavy hammer" approach, if you really want to avoid thinking about how to concretely implement your NIZK.