I am trying to implement a distributed encryption system by having as a main source of information this book (Introduction to Cryptography by Delfs and Knebl) and this Internet article (More Mix than Net by Wood).

I generate the following variables:

  • $p$: prime,
  • $g$: generator,
  • $x$: random within $[1, p-1]$,
  • $h$: $g^x \bmod p$

I can then use these variables to successfully encrypt, re-encrypt, and decrypt a message.

I am now trying to make the system use multiple authorities by following subsection 4.5.5 on Delfs's book that states:

enter image description here

According to this subsection $x$ is computed as a random number between $1$ and $q-1$, yet I am using the range $1$ and $p-1$ as shown in the article. Another difference is that in the book there is no mention of modulo $p$ when computing $h$.

Note that I have also implemented the ElGamal system as described in the book, but I would like to go with the implementation from the article since it makes more sense to me and I would like to not use external libraries).

My question is, what is the commitment I should generate and how can I later verify it?

  • 2
    $\begingroup$ طاهر الجمل himself spells it Elgamal according to Wikipedia, but I - and it seems most others - prefer ElGamal so that it becomes two connected words. "el gamal" however not really acceptable for names, some capitalization is in order. $\endgroup$
    – Maarten Bodewes
    Commented May 11, 2018 at 12:56

2 Answers 2


You can use a hash based commitment scheme, which is very simple to implement. The downside is that it is not easy to do zero-knowledge proof with the commitments. But from what you have given in the question, this does not seem to be a problem.

Let $\lambda$ be the security parameter (e.g. 128), let $H$ be a cryptographic hash function:

1 To commit, generate a $\lambda$-bit uniformly random string $r$. Then compute the commitment $C(h_i)=H(h_i||r)$.

2 To open a commitment $c=C(h_i)$, reveal $(h_i,r)$ and others can verify and accept if $c=H(h_i||r)$.


I can't access the book, so not sure exactly what it says, but the article you referenced also seems to be generating values in a group with order q: my intuition is that they are just using separate variables and group is of the same size in both texts just using $q$ and $p$ as variables respectively. As long as you are sampling $x_i$ uniformly from the full modular group you should be okay.

A for using modulo p, the security of El Gamal relies on the hardness of discrete log within the group $G$ with order $p$, so all operations are bounded via $\bmod p$.

Hope this is helpful, did I understand your question correctly?

  • $\begingroup$ The part of the book I am referencing is about creating a mixnet where we use the Shamir secret sharing technique to distribute the public keys. Since I created a simple system that can encrypt and de-crypt data using the ElGamal encryption scheme I would like to advance it a little bit and create a number of authorities that implement the distributed ElGamal scheme. I am confused about the generation of the commitments though. $\endgroup$
    – dearn44
    Commented May 11, 2018 at 18:25

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.