The problem ElGamal encryption for Miden VM solves

We're targeting Bounty 1 to improve Miden VM stdlib. Our original motivation was driven by a need for the ElGamal encryption scheme to enable hidden information gameplay mechanics in Miden VM ala the Geometry blog-post "Mental Poker in the Age of SNARKs" which uses a threshold variant of the scheme. Since this didn't exist in Miden VMs stdlib, we just decided to implement it as a mini challenge.

The module includes three functions: genkey, encrypt, and remask. These can be used to prove one has knowledge of a private key for said public key. It can also be used to prove the use of some private key for an encrypted or remasked piece of information. These are necessary properties for trustlessly setting up and playing mental poker.

We consider this another small step toward filling out the cornerstone toolset of any ZKVM, the crypto module.

You can run the tests to verify the module with

cargo test elgamal

(images from dreamstime.com and feature film Mission Impossible)

Challenges we ran into

The big challenge was acquainting ourselves with the semantics of Miden Assembly and then idiomatically introducing an assembly module into stdlib of miden-vm. We ended up forking the repo, so we could do a proper PR with integration tests and everything.