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.


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


  • 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.


  • 1
    $\begingroup$ "Integer factorization is mandatory to create such generator. I want to avoid it." I do not understand this. Integer factorization is never used in ElGamal. Also, do you want something where the secret key always exist (this is the case with ElGamal), or do you want additionally that it is not possible to create a public key without knowing the secret key? (this is what you seem to want from your list of downsides of ElGamal - but then, any adversary can always create the key pair and erase the secret key afterward, so I do not really see the point). $\endgroup$ Jul 1, 2019 at 12:29
  • $\begingroup$ If I want to find all full groups I have to do something like this: crypto.stackexchange.com/a/54255/70152 Also I updated the question part about picking the public key in advance. $\endgroup$
    – vvwccgz4lh
    Jul 1, 2019 at 15:10

1 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.

  • $\begingroup$ Thanks for a detailed explanation. It may suit needs defined in my question, but it's not over, I'll have to ask another question. $\endgroup$
    – vvwccgz4lh
    Jul 1, 2019 at 16:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.