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

Question

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?

Answer 1

As Natanael pointed out, if you are willing to make very strong assumptions, SNARGs can be used to give proofs of constant size, independent of the size of the statement to be proven. However, these proof systems are in general not UC-compatible (see e.g. this paper). You have two natural alternatives:

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.

2) Alternatively, you can use the right approach: look at the concrete statement you want to prove, write a NIZK for this statement, and look at its size.