# How to Prove Correct Decryption in ElGamal Cryptosystem

I am working on a project that uses ElGamal cryptography using multiplicative notation. The project is an internet voting implementation that uses the cryptosystem to encrypt the received ballots, re-encrypt and shuffle them, and then finally decrypt them. I am basing the project on this paper (https://www.usenix.org/conference/evt-06/simple-verifiable-elections).

I know how to provide proof of correctness for the encryption and subsequent re-encryptions. But I am not sure how to do this for the decryption.

main function

async function testDecryptProof() {
// create instance
const instance = {
g: '578581162149404798490571324493050333821753231896276896347588934236801486075345228356031089034308080355169502516970783985992465797790164077579971312181422206518964809883668939849570386967992767051369301215310754209280449807411021102153029377771783635510279329651149063858558329423219030908013960533321414499048784570490530207084776596253913339841694321299265784157923029847261603752469185349628532689446592521898507856757944009320377006868172969323251633981722550110871375408446896988161342745052895534300357801608217690146321171241606375301572941706622980330319103629192157393821194824468143500823157190887876038021286294694041671207075207845465680928059613160518275520282872421869149103173333949258329687311303065379518852070463040315621848668909908323797263963006103095659510784649320024411908921807300979021343984882137053231099693459838679137130760178994756250748747915572916102102876710115689234104349836600282068293111526381083439422743411854769767922191654138690358405340374558063855405817898848980774741636240733553597229888674227126306560767485612428694999914792050501101312713302487481236334084764126207814284673857139915086576279907709746386734910200293561256639347096905974796093763848648123958776190861142984370193373964',
p: '677088805808970643479133732614124310412316623451218811091733045838654739392363246453577008799155078839179531842224968947275228243113309850038122844034206790202276653380214548364178679947759556696213093774565712592343240601574723204104637149412506691550790846672244951946792272265332057245338838114080139164225120755358666371656799563377820758711742540625164732489435107295380237174828977225345274146615784182060315544480619981291902484596100159217062987931193501343478984350495475702937235166238839021800138523942802532967536519581875286415594806347061067009294601218779715836970031767680879370919882661828875007748699870086971737821411346178288109455141870605199207659215196027250095379359566675689788259770429733392884433737152092042439686604640479912921568537010168396445693348455112670632809025917594376152255614259482541945870534263328423690524049145709753098095473739179196969320905245503058104512347909553056470869228505715399271424136417025630569603129329944058750767224129798692688740617502975582916178170805288244361290828581356312322935742661288429293532378052789528032585149311919895258686737427981082058024550795015310013119653546412823602194115506883191730229098656656148675288450465794412620701805411630849845729707087',
y: '382541894983964690600293162993526991869438173208527886500815850372727490490048311900486843636684693220001234051265912000458425655926678741851522719141293453368701940787634131131196427632614127446128495491905145044221633881520859645274995287215391978093575963895028167371694057070023147521911999684763356037257097673911792867527883096328386171907773038204485470204595657681201490660401688164906946299164190680760257500808669498582862986527118065188947831650737443443357097875097317920241765784522696708021513408487224769269973358382952580868567815159167359342442935603924778373322260032811171703657045034945915068180793534715218521799021830059817105632423337977835717430573381512994650158949119647731472744313095838197029087455544614839618193123218393274500113565190237969194540716381907787190591680894096348619987465944314839217090897633240118907708728353977025942702693106124970322110442607454542840275031105740666888044262170783637186395453664958521125875844465859389112205599987204310138768154921310117836693453278604471256064092734451809018012352357011096070124567848586327900704665937932950816991331801099649890210617795966726051925732113487988689469786194024598695027099070158275365734245304820270230893796520258396313809218890',
x: '616914029784684855584714763340231492426100908655598976178651791609234807056421053678974092428484049715977123677899097157098622080979041003927320362108200586714799090933761996208900770559381734321267815567110342197287576060025703739925849141675379598311434697933729313626192885380020685335329593523683609103215285169226770018382824725553812040702257335748147376326047305998867888770159365634562244725476650780424134398942488222401859993782573792903020198868770888683341512671917249668225729306370351732926629458171105560538191103043275872688888584466859088043099329411213275826825557043830486585129455864229382917640721073590402279057985247862312161789404732832442295228432080975219571242951411904049824485202437265338712435017168333411682666572416980738892698829498421760253857943632271593969328472288492330564021179434722617280763223039329943080029254943467229417289060396673943590493918852192675127990512256579717957084720198671301881651767516973189185729965027130349998299701037240197132700980314839484971221210667187937244266087926343180431454910347212397518641142169016005016264904729137249817095250718240286083681743398488217525519989102901338103699237904737924109523062555162939255331967791259668687674201147438796261750843089',
};

// generate random encryption key
const s =
'207967822958110442178778278109830447433503852402785414821328709330349706312359283387206955571124544392109210639606384509083067520738417890305269373324678620850457624398942613053579091229263806574714035427029619796357685651219711112936206300136236554121413686413214781615737095413615972501136982626464802727651907543106754703441441867970819395278183757983355179097731548906256832974088244956504713377024931955849691572802532244064111313910004860917884899557614954275881853133846262202050937167007131258789440000321676167668782902794234299192316157418176379233048725674797860563914779298033729896033445543648327892278530279961688960419952711651675214205857184412263089450401851071510115939315543359563890816581201118807559534493006019524452621986959292183026635598059041969421186679562738320841257692505660048481680152158187087105039570206133866131147519932162950362812031235948074911811982616011007001800625736370940681178846920490275589689820196930672465994980780481940620705475248697225767799033066552773631904422782173583218760970539001080545554938763429864207029045564378485380363928567848534012360219680344285059829947885084536196661274257662548943187519599088821053868299335512862744163973139401071913251452241673699504961828835';

// encrypt the message using the encryption key
const message = 'hello world';

const encryptedMessage = await encryptMessage(
instance.g,
instance.p,
instance.y,
s,
message
);

// decrypt the message using the private key
const decryptedMessage = await decryptMessage(
instance.g,
instance.p,
instance.y,
instance.x,
encryptedMessage.encryptedMessage
);

// print the decrypted message
console.log(decryptedMessage.decryptedMessage.toString());

// generate k (random value used for proof)
const k = '432205588646359998072224940064050935541369966394428484286606496274949773265492520159561676254097175019399709157761827095358022557958118413270468363999537167910755408187731997035127421700651768420439270321539448061683930331314698667799883223300188515362283888605617138025465786893693127823694045331580720227445485016920391306083193825633049758877989424584806625002701306010980195936677251435453631912177533802372502229011410348247984698429037652109117115017510165679937247526350721944318387659334771288992577782481631999650684825467430896338090307144064969030989050561636545005807648750202696561764939329124837105153531769100765427789554512954001081570213946427116617138629761442441009571626270063662767295832445315119859315970224916761383918383449721705662562881539201176051986369670294625303588746629219579160556167662688170268007426222479052568698031137000163790568401670991050564172462876076169476615726119917986801572616644842291881886106617171867062928319054287450035022520087446449208860329043240893517321165335791019471565786995296353746166068105298686142956437669545600524122590537823201925276349186461350793613350249464595214594694635689236568081217849150982922989123384819183607112825771749599283303037622596134255625592473';

// create proof
const proof = await createDecryptionProof(
k,
instance.g,
instance.p,
s,
encryptedMessage.encryptedMessage
);

// verify proof
const verification = await verifyDecryptionProof(
instance.g,
instance.p,
instance.y,
proof.proof.c,
proof.proof.r,
encryptedMessage.encryptedMessage,
decryptedMessage.decryptedMessage.toString()
);
}



create proof

async function createDecryptionProof(k, g, p, s, _encryptedMessage) {
try {
const parsedK = Utils.parseBigInt(k);
const parsedG = Utils.parseBigInt(g);
const parsedP = Utils.parseBigInt(p);
const parsedS = Utils.parseBigInt(s);

const parsedA = Utils.parseBigInt(_encryptedMessage.a);
const parsedB = Utils.parseBigInt(_encryptedMessage.b);

// calculate c
const c1 = parsedG.modPow(parsedK, parsedP);
const c2 = parsedB.modPow(parsedK, parsedP);

// concatnate c1 and c2
const c = c1.toString() + c2.toString();

// hash c
const hashedC = await createHash(c);

// convert c to number

// calculate r

return {
success: true,
proof: {
r: r.toString(),
},
};
} catch (error) {
console.log(error);
return { success: false };
}
}


verify proof

async function verifyDecryptionProof(
g,
p,
y,
c,
r,
_encryptedMessage,
_decryptedMessage
) {
try {
const parsedG = Utils.parseBigInt(g);
const parsedP = Utils.parseBigInt(p);
const parsedY = Utils.parseBigInt(y);
const parsedC = Utils.parseBigInt(c);
const parsedR = Utils.parseBigInt(r);

const parsedA = Utils.parseBigInt(_encryptedMessage.a);
const parsedB = Utils.parseBigInt(_encryptedMessage.b);
const parsedMessage = Utils.parseBigInt(_decryptedMessage);

// derive P
const P = parsedA
.multiply(parsedMessage.modInverse(parsedP))
.mod(parsedP);
console.log(P: ${P}); // creating hash const mod1 = parsedG.modPow(parsedR, parsedP); const mod2 = parsedY.modPow(parsedC, parsedP); const mod3 = parsedB.modPow(parsedR, parsedP); const mod4 = P.modPow(parsedC, parsedP); // multiply the mods const hash1 = mod1.multiply(mod2).mod(parsedP); const hash2 = mod3.multiply(mod4).mod(parsedP); // concatnate the mods const hash = hash1.toString() + hash2.toString(); // hash the concatenated mods const hashedProof = await createHash(hash); // convert the hashed proof to a number const proof = Utils.parseBigInt(hashedProof.hashedPassword); const proofReady = proof.mod(parsedP); // log the values console.log(proof:${proofReady});
console.log(c: {parsedC}); } catch (error) { console.log(error); return { success: false }; } }  • Commit the message before encryption then test the commitment (hash-commit is enough) after decryption? Dec 31 '21 at 16:53 • Thanks for the response @kelalaka, I don't think that this will work for my implementation, as the application doesn't have access to the decrypted ballots cast by the voter. The application is designed for proportional representation elections (can vote for multiple candidates). When inputting their candidate selection, the voter does not directly input the candidates but their encrypted ciphertexts (encrypted earlier by the app). As a result, the app never has the plaintext candidate selection of a voter to create a commitment from. Would there be another way to prove the decryption? Dec 31 '21 at 19:04 ## 1 Answer The shuffled re-encrypted ballots, according to the El Gamal encryption scheme referenced in the appendix of the paper, will be in the form $$(X', Y')$$. We need to prove that the declared ballot message $$M$$ is genuinely calculated as $$M = X'-sY'$$, where $$s$$ is the same private key linked to the public key $$Z = sG$$ that the voter originally used to encrypt the ballot. The verifier first calculates $$P=(X'-M)$$. We need to prove to the verifier that $$P \overset{?}{=} sY'$$. To do this, we need to provide a Discrete Logarithm EQuivalence (DLEQ) proof, demonstrating that the private key for the public key $$Z$$ on the base point $$G$$ is the same private key for the public key $$P$$ on the base point $$Y'$$. The DLEQ proof $$(c,r)$$ is calculated as follows: The prover • selects a uniform random scalar $$k$$ • calculates $$c=H_s(kG\mathbin\|kY')$$ Here $$H_s$$ means a cryptographically secure hash that produces a scalar value), and • $$r = k - cs$$. All scalar operations are mod the order of the base point. The verifier(c,r,G,P,Z,Y') • The DLEQ proof is verified by checking $$c\overset{?}{=}H_s(rG+cZ \mathbin\| rY'+cP)$$. \begin{align} H_s(kG - csG + cZ \mathbin\| kY' - csY' + cP)\ & =H_s(kG \color{red}{- cZ + cZ} \mathbin\| kY' \color{red}{ - cP' + cP})\\ & = H_s(kG \mathbin\| kY')\\ & = c\\ \end{align} To convert this from additive notation to multiplicative notation, just replace point addition/subtraction with multiplication/division, and replace point multiplication with exponentiation with the scalar as the exponent. Therefore in multiplicative notation: If your prime is $$p$$ and your cyclic group size is $$\ell$$, then you calculate $$P=X' \cdot (M^{-1}\ mod\ p)\ mod\ p$$ (where $$M^{-1}\ mod\ p$$ means multiplicative modular inverse), $$c=H_s(G^k\ mod\ p \mathbin\| Y'^k\ mod\ p)$$, $$r=k-cs\ mod\ \ell$$, then verify $$c\overset{?}{=}H_s((G^r\ mod\ p) \cdot (Z^c\ mod\ p) \ mod\ p \mathbin\| (Y'^r \ mod\ p) \cdot (P^c\ mod\ p)\ mod\ p)$$. • As you can see, I've heavily edited the answer to make it more clear. You may use\overset{?}{=}$(\overset{?}{=})instead of$==$Jan 1 at 16:55 • @kelalaka thanks Jan 1 at 17:04 • Ah I think I know what's wrong. Two things: firstly, ensure that "division" uses modinverse, and not regular division. Secondly, although the exponentiations need to be$mod p$, the scalar operations also need to be modded, but not with$p$. They have to be modded with the group size of$g$. This group size will depend on the prime you have chosen. Sometimes it's just$p-1$, but there could be many large cyclic groups, so it could take the form$(p-1)/n$, where n is a cofactor that you'd need to know for the prime. I rarely do such implementations outsize of EC, so I'm a bit rusty. Jan 3 at 8:13 • I've added it in. Make sure you have a proper modular multiplicate inverse library available to do the$M^{-1}\ mod\ p$. Btw to make this less error-prone, I recommend you have scalar and group element classes, with methods that will automatically apply the$mod\ p$or$mod\ \ell$for you, so you don't have code littered with$mod\$ everywhere and so that you're always properly classifying what is a group element and what is a scalar. Jan 9 at 12:07
• Thank you so much! I looked over it and made some changes and it checks out. You're a savior! 😁 Jan 9 at 19:33