Does anyone know an easily creatable asymmetric cryptosystem for usage in VDF?

Question

I've read multiple papers about VDFs (1, 2, etc.). I look for a lighter alternative to El-Gamal regarding cryptosystem creation. It can be anything exotic too, but it would be nice to have at least some security.

(Let's assume I know what I'm doing; This is my small research)

I would like to know if anyone knows a cryptosystem that could fulfill these criteria:

1. Creation of public key with 100% guarantee that private key will exist (Or open key validation would work) (I want to pick a valid public key and compute private key by brute force later)

2. Light creation of cryptosystem. There shouldn't be a need to factor large integers or derive difficult parameters. It could have a small amount of calculations, but I want to avoid brute-force.

ElGamal has some good parts, but won't work for my case:

• El-Gamal allows creation of public keys without private ones. So if the generator operates on the whole cyclical group then we can have shorter keys too.

• Integer factorization is one of the ways to create an efficient generator. I want to avoid factorization.

ECC is even harder to set up:

• To derive a new ECC cryptosystem I have to choose several parameters and a big prime number. I want to create cryptosystems on the fly so it's not very convenient. Let's say it may be solvable somehow (for the sake of this example) -- prebuilt cryptosystems.

• Public key generation, though, won't work for 100%. As elliptic curve public key points can't be validated such as ElGamal's because we never operate in the whole group.

• Also this means that order of the base point has to be brute-force-adjusted to have the maximum number of points in a group. Because elliptic curve (under a field) contains point count related to it's base point. So this creates a brute-force need when creating a cryptosystem. I would like to avoid it.

RSA

• Won't work because there is no way to validate the public key.

NTRUencrypt

• Private key has to be of a certain form so that polynomial multiplication would work during decryption (wiki). I would like to know if it's possible to use it as the basis for this kind of VDF.

I would like to get any guidance or even samples of cryptosystems that would work under such scenario.

Thanks.

Answer 1

The issue of having to factor a large number in ElGamal appears only if you set the group order to be an arbitrary prime $p$. In this case, to find all subgroups of $\mathbb{G}$, you need the factorization of $p-1$.

However, this issue entirely disappears if you take $p$ to be a safe prime, i.e., a prime number of the form $p = 2q+1$, where $q$ is also a prime. Finding such primes is not so hard, and testing primality does not require to compute any expensive factorization.

Once you have $p$, sets $\mathbb{G}$ to be the sugroup of quadratic residues (i.e., squares modulo $p$) of order $q$ in the field of order $p$. Note that every quadratic residue (except $1$, of course) generates the full group of quadratic residues, and testing whether a number is a quadratic residue can be done efficiently. Therefore, there is no possibility that some ElGamal key in this group is invalid: any quadratic residue $h$ not equal to 1 is uniquely associated to a secret ElGamal key $s$, which is the unique $s$ such that $g^s = h$ ($g$ is some fixed generator of the group). Even though brute force to find the key is not efficient (that's the whole point of it, in fact), it is guaranteed to succeed (in exponential time) in finding the unique ElGamal key.

Therefore, it seems to me that a properly instantiated ElGamal scheme should suit all your needs.