In the article "Short factoring proofs" under "Security parameters:" you list among others "$m$, and $K$". However, $K$ is never used in the rest of the article. Instead, $m$ takes the role of $K$ (from the original paper [PS00]), denoting the number of $z_i$'s. I suggest to rename $m$ to $K$, or vice versa, so that there are no more redundant security parameters.
Also, it would be nice to give more details on the choice of $K$/$m$ in the respective section "Choice of security parameters". For example, you write "$B$ and $\ell$ should satisfy $\ell \cdot \log B = \theta(k)$", so you could add something like "$K$/$m$ should be approximately equal to $k$" (or, heuristically, even smaller, cf. [PS00]).

In the short factoring proof, there is the line $y = r + (N - \varphi(N))e$. In the vanilla protocol, the verifier checks $x \overset{?}{\equiv} z^{y - eN} \mod N$. Because $\varphi(N)$ is the order of the multiplicative group of integers modulo $N$, taking the exponent of a multiple of $\varphi(N)$ gives you the identity 1 for all group elements, so $z^{\varphi(N)e} \equiv 1 \mod N$. This is my understanding how the protocol works.

I was wondering, can we define $y = r + (N + \varphi(N))e$ instead? The minus sign seems redundant to me and the above argument should still work, shouldn't it?

In practice, p should be reasonably large. Breaking S into multiple parts introduces complexity and opportunities for malicious actors. Also, in some verifiable secret sharing schemes, a large p is needed to prevent discrete log attacks.

This advice seems to go against a very common field choice of GF(2^8). As such, I’m personally curious to better understand the argument against (if that is the argument), and generally I think a deeper explanation (or link or reference to one) would be a good idea!

I don't know to which extent you plan to document less well known algorithms, but here is one that is crucial for designing cryptographic formats that do not reveal that they are encrypted text but can still have public key encryption.

While there is some documentation on the Elligator 2 itself, namely a research paper, and while the use of the algorithm is somewhat general knowledge among cryptographic circles, almost no-one knows how to actually implement it securely.

The background is that most formats need to store an ephemeral public key in plain text, and if this is a Curve25519 point, what is stored is a 32-byte value, where the highest bit is always zero, only half of the remaining 255 bit values encode valid points, only 1/8 of those are in the prime group. All these combined, 32 bytes of random data have only 1/32 chance of being a normal public key. An adversary can quickly test for all these things and thus keys can be easily distinguished from random bytes.

Fixing it is a whole lot more complicated than just using Elligator 2 and inserting a few random bits to fill in the blanks. One also has to randomise the subgroups, to avoid only using the prime group, which fortunately stays compatible with standard ECDH (no need to project back to prime group first).

The existing documentation is within Monocypher source code, Covert Encryption source code, and in some Github discussions and old Reddit comments. It would be quite valuable if someone created proper documentation for it, so that not everybody else needs to do the same trial and error that we had to. Let me know if you are interested and I'll collect you the relevant links to get started.

Such documentation could work as a good primer to Ed25519/Curve25519 in general, as all the points can be visualised as a simple rectangle with 8 columns and q rows (~2**252), the low order points on the top row and the prime group on the left column. The neutral element (zero point) is at the top left corner. To hide points, we want to make use of all the columns but still correspond to the standard point on the left column on that same row. It turns out that point add/scalarmult are just adding or multiplying vectors in these rectangle coordinates (columns mod 8, rows mod q), so it can be visualised neatly. The base point is (row 1, column 0) so multiplying it by any number goes to row by that number but stays in the left column.

On the Paillier-Blum Modulus page (content/docs/zkdocs/zero-knowledge-protocols/product-primes/paillier_blum_modulus.md), it mentions choosing a modulus size of 2048 to get 80 bits of security. By any chance, could someone include a reference for why this modulus size yields this security and ideally which size is needed to target different security levels?

Thanks

Adding terms to the search bar does not filter sections.

Hey hey,

This project is amazing! Have you thought about releasing this as something that can be used individually by projects to spec their protocols? I would probably use it in a heartbeat :)

Thanks for the nice project! There are some overlaps in goals with the hacspec project.
Cryptographic primitives have been specified there, and some work on ZK proofs is underway.

There may be some opportunities for collaboration in the future, so I wanted to give you a heads-up.