Score:1

How to Prove Correct Decryption in ElGamal Cryptosystem

br flag

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
        const cNum = Utils.parseBigInt(hashedC.hashedPassword);
        const cReady = cNum.mod(parsedP);

        // calculate r
        const r = parsedK.subtract(cReady.multiply(parsedS));

        return {
            success: true,
            proof: {
                c: cReady.toString(),
                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 };
    }
}

GitHub Repo: https://github.com/Andrei-Florian/cryptosystem-public

kelalaka avatar
in flag
Commit the message before encryption then test the commitment (hash-commit is enough) after decryption?
Andrei Florian avatar
br flag
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?
Score:2
es flag

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)$.

kelalaka avatar
in flag
As you can see, I've heavily edited the answer to make it more clear. You may use $\overset{?}{=}$ (`\overset{?}{=}`)instead of $==$
knaccc avatar
es flag
@kelalaka thanks
Andrei Florian avatar
br flag
Hi, thank you for the answer. I have a few questions. Firstly, I'm not used to reading this notation and I'm not sure what || denotes, how would this symbol be translated to code? Can I use SHA256 as the hash function? And finally, just making sure that G represents the group generator.
knaccc avatar
es flag
@AndreiFlorian || means concatenation. E.g. if you were using curve25519, then EC points are 32 bytes, and if you concatenate them prior to hashing you have 64 bytes being hashed. Yes, G is the group generator. SHA256 is fine in this particular example, but then mod it with the order of the base point to ensure that the result is a valid scalar. Btw I would always err on the side of caution and use a hash that is not vulnerable to length extension attacks, such as SHA512 truncated to 256 bits.
Andrei Florian avatar
br flag
Thanks for that, I seem to be struggling with the conversion to multiplicative notation, I'm not 100% sure which signs to change and which to keep the same. Am I right in saying that: c=H((G^k)modp || (Y'^k)modp)modp, r=(k-cs)modp (same), P=(X'-M)modp (same), c=(([G^r]modp) * ([Z^c]modp)modp || ([Y'^r]modp) * ([P^c]modp)modp)modp? Thank you again for the time and sorry for the poor notation.
knaccc avatar
es flag
@AndreiFlorian it's X'/M instead of X'-M when converting to multiplicative notation.
Andrei Florian avatar
br flag
@knaccc, I'm quite sure I'm doing something wrong. Would you have the time to write the proof in multiplicative notation? I've been trying switching signs around for a few hours and still can't get the proof to check out. Many thanks.
knaccc avatar
es flag
@AndreiFlorian When doing EC implementations, scalar operations are mod the order of the base point. But if you're using normal exponentiation and not using EC scalars, then you don't do $mod$ on the $k-cs$ part when calculating $r$ (not in the subtraction, and not in the multiplication). This should fix it. In summary, don't use $mod$ or change any operators when calculating $r = k-cs$, but everywhere else use $mod p$ and convert addition to multiplication, subtraction to division, and multiplication to exponentiation. Let me know if that fixes it.
Andrei Florian avatar
br flag
@knaccc, I tried that change but it still does not work. I'm wondering if it would be easier if I'd share the code with you. I've attached it to the post. I'm working in JavaScript, the code I attached to the question has 3 methods (with some methods handling certain operations). I added a link to the GitHub repo where I have all helper methods included. Thank you again for the time, I really appreciate it :).
knaccc avatar
es flag
@AndreiFlorian there is a lot to work through and debug there. I would recommend you start with checking that you can come up with two random numbers $b$ and $c$, calculate $a = b + c$, and then check that you can successfully calculate that $g^a mod p == (g^b mod p * g^c mod p) mod p$. If you can get that far, then start checking that the subcomponents of the algebra above work out correctly, e.g. that $G^k mod p == (G^r mod p * Z^c mod p) mod p$. You probably have a simple coding error somewhere.
knaccc avatar
es flag
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.
Andrei Florian avatar
br flag
Hi, I'm quite sure I'm doing the divisions right (multiply by mod inverse). Regarding the mods, I can confirm that the group size is p-1, however I'm not sure where to use this and where to use p. Could you possibly include where these are used in the formulae in the answer. I think this would solve the problem. Thank you again.
knaccc avatar
es flag
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.
Andrei Florian avatar
br flag
Thank you so much! I looked over it and made some changes and it checks out. You're a savior!
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.