<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Öznur Mut Sağdıçoğlu on Medium]]></title>
        <description><![CDATA[Stories by Öznur Mut Sağdıçoğlu on Medium]]></description>
        <link>https://medium.com/@oznurmut?source=rss-c6c2e75355b8------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*DFk91WalO3WWk0Je</url>
            <title>Stories by Öznur Mut Sağdıçoğlu on Medium</title>
            <link>https://medium.com/@oznurmut?source=rss-c6c2e75355b8------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sat, 21 Nov 2026 01:42:53 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@oznurmut/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Secure Nonce Usage in Threshold EdDSA]]></title>
            <link>https://medium.com/@oznurmut/secure-nonce-usage-in-threshold-eddsa-317e9fd47852?source=rss-c6c2e75355b8------2</link>
            <guid isPermaLink="false">https://medium.com/p/317e9fd47852</guid>
            <dc:creator><![CDATA[Öznur Mut Sağdıçoğlu]]></dc:creator>
            <pubDate>Wed, 25 Mar 2026 07:57:22 GMT</pubDate>
            <atom:updated>2026-03-25T07:57:22.142Z</atom:updated>
            <content:encoded><![CDATA[<p>Edwards-curve Digital Signature Algorithm (EdDSA) is a signature algorithm based on twisted Edwards curves that uses a variant of the Schnorr signature [<a href="https://eprint.iacr.org/2011/368.pdf">3</a>]. In general, EdDSA can be viewed as a deterministic adaptation of the Schnorr signature scheme [<a href="https://d-nb.info/1156214580/34">4</a>]. This means that the freshness, called a nonce (a number used once), used in the signature is produced deterministically. In other words, the nonce is derived from the message and the secret signing key, and thus it does not require random number generators. For the nonce generation, EdDSA can use a cryptographic hash function.<br>A threshold EdDSA signature can be used as a drop-in replacement for traditional (non-threshold) EdDSA signatures, meaning they work seamlessly with existing verification systems. Instead of relying on a single party to hold the entire private signing key, threshold schemes divide the key among multiple participants. A valid signature can be generated only when a predefined threshold number of participants cooperate, whereas any group with fewer members obtains no information about the secret key. This removes the single point of failure and significantly lowers the risk of key compromise.</p><p>In a single-party setting for EdDSA, deterministic nonce generation is secure because it protects against catastrophic private key leakage caused by poor randomness or biased random number generators. However, in a threshold or multi-party setting, the security breaks down, leading to what is known as the <strong>Key-Recovery Pitfall</strong>.</p><p>Before that, we give some definitions:</p><h3>The Edwards-curve Digital Signature Algorithm (EdDSA)</h3><p>EdDSA is a high-performance variant of Schnorr signatures that relies on a<br>twisted Edwards curve with a subgroup<em> G </em>of prime order <em>n</em>, a base point (generator) <em>G</em>, and a cryptographic hash function H (e.g., using SHA-512).<br>A secret/public key pair is derived from a <em>b</em>-bit private key <em>d</em>, whose first half is used to derive the secret signing key <em>s</em> and the second half acts as a secret nonce-derivation key <em>ν</em>; then the public verification key is the point <em>Q = s · G</em>.<br>To sign a message <em>M</em>, the signer derives a secret nonce <em>r</em> (typically deterministically as <em>r = H(ν, M )</em>, computes a nonce <em>R = r · G</em>, the<br>challenge <em>χ = H(R, Q, M )</em>, and the response <em>S = r + χ · s (mod n)</em>.<br>The signature is the pair <em>(R, S)</em>. A verifier checks the signature’s validity by<br>recalculating the challenge <em>χ</em> and verifying the group equation:</p><blockquote>S · G = R + χ · Q</blockquote><p>In the standardized version, this is often performed as a cofactored verification to account for the curve’s cofactor<em> c</em>:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/318/1*iZ_pEM6TyIBSCRXsvosAQg.png" /></figure><p>where <em>2^c</em> is the cofactor of the curve (e.g., 8 for Ed25519).</p><p>The parameters are used as follows, [7]:<br>• <em>G</em>: Represents the cyclic subgroup of prime order n.<br>• <em>Q = s.G</em>: The public verification key derived from the signing key s.<br>• <em>r = H(ν, M )</em>: The deterministic derivation of the secret nonce using the<br>nonce-derivation key ν and the message <em>M</em>.<br>• <em>χ = H(R, Q, M)</em>: The signature ”challenge” that binds the nonce commitment, public key, and message.<br>• <em>2^c </em>: The cofactor of the curve, used in the cofactored verification equation.</p><h3>Nonce Generation in a Threshold EdDSA Protocol</h3><p>The naive way to design a multi-signature or threshold scheme fully compatible with EdDSA would be as follows. Suppose a group of <em>n co</em>signers wants to sign a message <em>M</em>, and let</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/298/1*wxAqCrE0LhAozk09KoaFYA.png" /></figure><p>be a set of all their public keys. In a group of <em>n co</em>signers, each participant generates a secret nonce share <em>r_i, </em>like in the definition of EdDSA, as <em>r_i = H(ν_i, M)</em>. Signing parties then exchange their nonce commitments</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/89/1*GoLu5_dGUdoM8dEPD_Oyrw.png" /></figure><p>to compute the aggregate group nonce</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/129/1*3ciWLBbsRpxeTcd2rSRlpg.png" /></figure><p>The group’s aggregate public key is defined as the product of all individual keys,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/136/1*fFTxgvh22RHEfA5JjFFAtw.png" /></figure><p>and the common challenge is derived as <em>c = H( ˜X, R, m)</em>. Each<br>signer produces a partial signature share:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/544/1*ATFTfQ6HHwk0zGOUUV0uww.png" /></figure><p>where<em> λ_i</em> is the Lagrange coefficient.<br>These shares are aggregated into a single signature<em> (R, s)</em>, where</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/118/1*rOqhjB3ShDI6nKsz5DENOg.png" /></figure><p>The validity of the signature is verified against the group public key <em>˜X</em> using the standard Schnorr equation</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/102/1*hB1cPvhoCZg48ZpzwWq4PQ.png" /></figure><p>matching the verification of an ordinary Schnorr/EdDSA signature scheme [<a href="https://d-nb.info/1156214580/34">4</a>].</p><p>We assume that the aggregated public key is generated securely, and consider the generation of a nonce in the threshold signing. Since deterministic and probabilistic Schnorr-type signatures are indistinguishable from the signature itself, the National Institute of Standards and Technology (NIST) recommends that different nonce generation modes in the threshold setting be designed to remain interchangeable and fully compatible with the standard EdDSA verification algorithm [<a href="https://nvlpubs.nist.gov/nistpubs/ir/2022/NIST.IR.8214B.ipd.pdf">7</a>]. Thus, according to NIST IR 8214B, nonce generation for threshold EdDSA can be implemented through three distinct strategies: deterministic, random, and hybrid.</p><p>Regardless of whether nonce generation is deterministic, random, or hybrid (randomness and pseudorandomness), each signer must first commit to their nonce share. This requirement comes from the attack of Drijvers et al. [<a href="https://bford.info/pub/sec/two-round-multisig.pdf">1</a>], which targets two-round Schnorr multi-signature schemes without a preliminary nonce commitment phase. In this attack, a malicious party initiates many parallel signing sessions, collects honest nonce shares, and then applies Wagner’s k-sum algorithm [<a href="https://www.enseignement.polytechnique.fr/informatique/profs/Francois.Morain/Master1/Crypto/projects/Wagner02.pdf">2</a>] to manipulate the challenges. You may also check the attack explanation <a href="https://medium.com/@oznurmut/the-security-of-the-threshold-eddsa-protocol-66dc3fc14530">here</a>. By solving the resulting generalized birthday problem, the adversary can combine valid partial signatures from different sessions to forge a signature on a message of their choice without the honest parties ever knowing or approving it.<br>A threshold EdDSA implementation is classified as deterministic if the secret nonce is derived deterministically from the secret signing key and the message to be signed [<a href="https://nvlpubs.nist.gov/nistpubs/ir/2022/NIST.IR.8214B.ipd.pdf">7</a>]. Thus, a malicious participant could attempt to induce an honest party to generate two distinct signatures using the same secret nonce, which would lead to the recovery of the honest party’s secret key share. This attack is called a Key Recovery Pitfall.</p><h4>Key Recovery Pitfall</h4><p>The attack is described in several works in the literature, including the<br>MuSig-DN paper [<a href="https://eprint.iacr.org/2020/1057.pdf">14</a>]. In this paper, it is shown that there is a severe<br>security failure when applying standard deterministic nonce generation (like in RFC 6979) to the multi-signature protocol Musig1, [<a href="https://eprint.iacr.org/2018/068.pdf">13</a>].</p><p>In this attack, a malicious participant (Bob) initiates a signing session for<br>a message <em>m </em>and receives from an honest participant (Alice) her deterministic nonce share <em>R_1 = r_1.G</em> and corresponding partial signature <em>s_1 = r_1 + c.μ_1.x_1</em>, where <em>G </em>is the base point of the elliptic curve, <em>x_1 </em>is Alice’s secret key, and <em>c = H(R, X, m)</em> is the challenge. Bob receives <em>s_1</em> and chooses not to (or maybe cannot) produce his partial signature, then aborts the protocol. He then restarts the signing session for the same message <em>m</em>, but this time provides a different nonce share <em>R′_2</em>, even though he does not need to know the discrete log value of <em>R′_2</em>.<br>Since Alice follows a deterministic nonce derivation procedure, she reuses her secret nonce<em> r_1</em> for the same message <em>m</em>. However, the aggregate nonce <em>R′ =R_1R′_2</em> changes due to Bob’s modified contribution, which results in a different challenge value</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/217/1*Y5T15KLvcY5Zrcdzrd5NxA.png" /></figure><p>Alice computes <em>s′_1 = r_1 + c′.μ_1.x_1 mod p</em> and sends it to Bob.<br>As a consequence, Bob obtains two partial signatures <em>s_1 </em>and <em>s′_1</em> corresponding to the same secret nonce <em>r_1</em> but different challenges <em>c </em>and <em>c′</em>. This enables him to solve a simple system of linear equations and recover Alice’s private key <em>x_1</em> as follows:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/208/1*amjQW-lwnbMbFX5VWyKTIQ.png" /></figure><p>Importantly, note that this attack remains possible even if a commitment round is employed in a deterministic nonce generation. While nonce commitments prevent their manipulation in Drijvers’ attack, they do not help to stop the key recovery attack above. The fundamental issue arises from the lack of fresh randomness in the honest party’s nonce derivation.</p><h4>Probabilistic, Random, or Hybrid</h4><p>While standard EdDSA (<a href="https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf">FIPS 186–5</a>) is defined as a deterministic scheme;<br>deterministic or probabilistic cases are not verifiable from the signature itself [<a href="https://nvlpubs.nist.gov/nistpubs/ir/2022/NIST.IR.8214B.ipd.pdf">7</a>]. Consequently, probabilistic signatures generated with correct parameters are accepted by standard EdDSA verification algorithms and are considered <strong>interchangeable</strong>.</p><p>In threshold schemes, performing the deterministic nonce computation required by standard EdDSA is significantly complex and inefficient in a distributed manner, as it requires expensive multi-party computation (MPC) of a hash over secret-shared inputs. In contrast, the probabilistic approach enables much simpler and more efficient protocols by leveraging the homomorphic properties innate to the signature scheme</p><p>It can be seen that random nonces are generally less vulnerable to the<br>attacks mentioned above in the deterministic case. Furthermore, in a threshold setting, the good randomness from even a single honest participant is sufficient to ensure the production of a global, unbiased nonce, protecting parties with poor local entropy.</p><p>However, the risk of secret nonce reuse persists in probabilistic schemes due to implementation or hardware failures, such as unreliable entropy sources or state-rewinding attacks [<a href="https://nvlpubs.nist.gov/nistpubs/ir/2022/NIST.IR.8214B.ipd.pdf">7</a>]. In this case, a zero-knowledge proof of knowledge for a nonce is meaningless because it cannot verify or ensure the quality of the random number generator [<a href="https://nvlpubs.nist.gov/nistpubs/ir/2022/NIST.IR.8214B.ipd.pdf">7</a>].</p><p>Instead of relying on unverifiable local proofs, NIST suggests that the threshold setting provides a more robust mitigation: ”well-behaved but with bad local randomness” (WBBR) parties are protected by the distributed entropy of the group, where high-quality randomness from even a single honest participant is sufficient to ensure a global, unbiased nonce and prevent private key exposure.</p><p>The hybrid (with randomness and pseudorandomness) mode is also highlighted as a particularly robust approach in the NIST document, as it combines secret-key-based pseudorandomness with fresh randomness, [<a href="https://nvlpubs.nist.gov/nistpubs/ir/2022/NIST.IR.8214B.ipd.pdf">7</a>, Table 6]. This way, nonce reuse with the same secret signing key and message does not result in a key recovery attack as explained above. However, note that unless the hybrid mode is supported by additional mechanisms, a hybrid approach may still inherit the weaknesses of both deterministic and probabilistic schemes.</p><h3>Literature Examples of Threshold Schnorr and EdDSA Schemes</h3><p>This section reviews various threshold signature protocols in the literature, focusing on the critical design choice between deterministic and random nonce generation.<br>MuSig is a Schnorr-based multi-signature scheme designed to enable a group of signers to produce a short signature that is efficiently verifiable as a standard Schnorr signature [<a href="https://eprint.iacr.org/2018/068.pdf">13</a>].<br>Two-round version of Musig 1, called InsecureMuSig in [<a href="https://eprint.iacr.org/2020/1261.pdf">15</a>], omits the nonce commitments before the signing phase, and so is vulnerable to the Drijvers’ attack [<a href="https://bford.info/pub/sec/two-round-multisig.pdf">1</a>]. To fix this, a commitment round is added. However, the problem still remains in the three-round version, since in deterministic nonce generation, there is no clear mechanism to prevent key recovery pitfalls when using randomness as in RFC6979. A malicious attacker can trick an honest party and make them create two partial signatures with the same nonce.</p><p>The primary goal of MuSig-DN, following MuSig1, is to enable secure deterministic signing in a <strong>two-round protocol</strong>, to reduce the three rounds<br>required by MuSig1, making the scheme robust against randomness generation failures and state-related attacks by using non-interactive zero-knowledge proofs, which verify that nonces are correctly derived and their ownership is ensured [<a href="https://eprint.iacr.org/2020/1057.pdf">14</a>]. Thus, if a malicious party tries to force a different nonce or challenge in another session, the honest party will detect the discrepancy via the proof and abort before revealing the signature share that would expose their key.</p><p>While Musig-DN is a deterministic scheme, FROST, MuSig2, SPRINT, and<br>ROAST are probabilistic schemes, generating random nonces by combining with binding factors to ensure security during concurrent signing sessions, [<a href="https://www.rfc-editor.org/rfc/rfc9591.pdf">11</a>], [<a href="https://eprint.iacr.org/2020/1261.pdf">15</a>], and [<a href="https://eprint.iacr.org/2022/550.pdf">16</a>]. In FROST and MuSig2, the binding factors are nonce sets, the set of all cosigners, and the message or a linear combination of multiple nonces and commitment sets to ensure that each signature session is independent and that the effective nonce changes unpredictably if the adversary manipulates any part of the input, [<a href="https://www.rfc-editor.org/rfc/rfc9591.pdf">11</a>] and [<a href="https://eprint.iacr.org/2020/1261.pdf">15</a>].</p><p>ROAST inherits <strong>binding </strong>techniques from FROST, ensuring every signature is dependent on the message to be signed, all provided commitments, and the group of cosigners [<a href="https://eprint.iacr.org/2022/550.pdf">16</a>]. Moreover, ROAST employs a pipelining strategy managed by a coordinator to prevent the system from freezing due to slow or malicious behavior. In other words, participants turn in one signature share; they also hand over presignatures for the next potential session. This keeps the process moving without interruption, even when individual participants cause delays.</p><p>The Garillot et al. proposed a protocol that provides a solution for stateless<br>and deterministic threshold signing by ensuring secure nonce derivation even if participants’ devices crash or lose state, [<a href="https://eprint.iacr.org/2021/1055.pdf">12</a>].<br>In this scheme, each signer locally derives their nonce share using a precommitted pseudo-random function key and then generates a zero-knowledge proof from Garbled Circuits to prove the correctness of that derivation to other cosigners. This protocol is designed to be compatible with standard and well-analyzed primitives such as AES and SHA512. This approach is designed for the dishonest majority setting, remaining secure as long as at least one party is honest.</p><p>In the Bonte et al. protocol, titled ”Thresholdizing HashEdDSA,” uses deter-<br>ministic nonce generation by employing Secure Multi-Party Computation, [<a href="https://eprint.iacr.org/2020/214.pdf">20</a>]. Instead of giving a zero-knowledge proof for the nonce share, all participants jointly and securely evaluate the hash function within an MPC framework to derive the secret nonce.</p><p>To prevent a key recovery attack in deterministic nonce generation, NIST recommends using MPC tools or zero-knowledge proofs to verify that each party’s nonce contribution adheres to deterministic rules [<a href="https://nvlpubs.nist.gov/nistpubs/ir/2022/NIST.IR.8214B.ipd.pdf">7</a>]. For the random case, NIST also emphasizes the two-round protocol FROST for the nonce binding property, namely, the signing session is bound to the nonce commitments, to the message, the specific set of cosigners, and the contributions of all participants, thereby protecting the scheme against concurrent session attacks like the Wagner k-sum attack [<a href="https://nvlpubs.nist.gov/nistpubs/ir/2022/NIST.IR.8214B.ipd.pdf">7</a>].</p><p>Therefore, for the deterministic nonce case, two approaches are needed for secure nonce distribution: secure multi-party computation and zero-knowledge proofs. For the MPC, the parties jointly compute the nonce. For the ZK proofs, each party computes its nonce share and proves that it is correctly produced from its secret key and the message. For a random nonce case, binding techniques are useful for security.</p><h3>Conclusion</h3><p>The probabilistic threshold EdDSA scheme does not require ZK proofs for deterministic derivation; instead, for example, it relies on nonce binding and commitment phases to prevent manipulation like FROST. Against the key recovery attack, ZK proofs or MPC solutions remain the vital tool for deterministic signing, like Musig-DN and Bonte et al. protocol.<br>In other words, for a threshold EdDSA scheme, simply committing to a nonce fixes its value, and against the Drijvers’ attack, but does not guarantee that it was derived according to the correct nonce value and the protocol rule, and it could still be vulnerable to the key recovery attack in both deterministic and random nonce generations.</p><h4>A Python Code for the Key Recovery Pitfall</h4><p>In this section, we give a Python code for the key recovery pitfall in deterministic signing. There are two parties, Alice and Bob. Alice produces her nonce value depending on the message and her secret signing key. After two concrete sessions, Bob can recover Alice’s private key due to the reuse of Alice’s nonce value.</p><pre>import random<br>import hashlib<br><br># An example curve<br>p = 101 <br>A = 0   <br>B = 3    # y^2=x^3+ax+b mod p<br><br># Point Addition<br>def point_add(P, Q, p, A):<br>    if P is None: return Q<br>    if Q is None: return P<br>    x1, y1 = P<br>    x2, y2 = Q<br>    if x1 == x2 and y1 != y2: return None<br>    # P+(-P)=0<br>    if x1 == x2 and (y1 + y2) % p == 0:<br>        return None<br>    if x1 == x2:<br>        num = (3 * x1**2 + A)<br>        den = (2 * y1)<br>    else:<br>        num = (y2 - y1)<br>        den = (x2 - x1)<br>    lam = (num * pow(den, -1, p)) % p<br>    x3 = (lam**2 - x1 - x2) % p<br>    y3 = (lam * (x1 - x3) - y1) % p<br>    return (x3, y3)<br><br># Scalar Multiplication - r * G<br>def scalar_mul(k, G, p, A):<br>    res = None<br>    temp = G<br>    while k:<br>        if k &amp; 1: <br>            res = point_add(res, temp, p, A)<br>        temp = point_add(temp, temp, p, A)<br>        k &gt;&gt;= 1<br>    return res<br><br># Generator<br>G = (1,2) <br>q = 17<br><br># Key Recovery Attack<br><br>x1 = random.randint(1, q-1) <br>A1 = scalar_mul(x1, G, p, A) <br><br>def get_x_or_zero(pt):<br>    # None case<br>    return pt[0] if pt is not None else 0  <br><br>def compute_challenge(R_pt, A_pt, msg, q):<br>    r_x = get_x_or_zero(R_pt)<br>    a_x = get_x_or_zero(A_pt)<br>    # Hash the x-coordinate of the points and the message<br>    data = f&quot;{r_x}{a_x}{msg}&quot;.encode()<br>    return int.from_bytes(hashlib.sha256(data).digest(), &#39;big&#39;) % q<br>def compute_challenge_for_nonce(x1, msg, q):<br>    # Hash the x-coordinate of the points and the message<br>    data = f&quot;{x1}{msg}&quot;.encode()<br>    return int.from_bytes(hashlib.sha256(data).digest(), &#39;big&#39;) % q<br>    <br><br># Alice chooses a nonce share<br>r1 = compute_challenge_for_nonce(x1, &quot;merhaba&quot;, q)<br>print(f&quot;Alice nonce share (r1): {r1}&quot;)<br>R1 = scalar_mul(r1, G, p, A) # R1 = r1 * G<br><br># Bob&#39;s public key and the nonce share<br>A2=(91,35)<br>R2=(68,27)<br><br># --- 1. session ---<br>#Aggregated nonce<br>R=point_add(R1,R2,p,A)<br>#Aggregated Public key<br>X=point_add(A1,A2,p,A)<br>print(f&quot;Public key (X): Point {X}&quot;)<br><br><br>c1 = compute_challenge(R, X, &quot;merhaba&quot;, q)<br>s1 = (r1 + c1 * x1) % q<br><br><br># --- 2. session ---(Attacker manipulates R but Alice uses the SAME r1) <br><br># Attacker chooses a different R2&#39; <br>R2_prime = point_add(R1, G, p, A)<br>R_prime = point_add(R1, R2_prime, p, A) <br><br><br>c2 = compute_challenge(R_prime, X, &quot;merhaba&quot;, q)<br>s2 = (r1 + c2 * x1) % q<br>if c1==c2: <br>    print(&#39;Hash collision detected (c1 == c2). Key recovery failed. Exiting...&#39;)<br>    exit()<br>print(f&quot;\n1. session - Alice nonce share: {R1}, c1: {c1}, s1: {s1},X: {X}&quot;)<br>print(f&quot;\n1. session - Bob nonce share: {R2}&quot;)<br>print(f&quot;\nAgg nonce (R): Point {R}&quot;)<br><br>print(f&quot;\n2. session - Alice nonce share: {R1}, c2: {c2}, s2: {s2},X: {X}&quot;)<br>print(f&quot;\n2. session - Bob nonce share: {R2_prime}&quot;)<br>print(f&quot;\nAgg nonce (R): Point {R_prime}&quot;)<br><br><br><br># --- Alice&#39;s Key Recovery ---<br># x1 = (s1 - s2) / (c1 - c2) mod q<br>num = (s1 - s2) % q<br>den = (c1 - c2) % q<br>x1_recovered = (num * pow(den, -1, q)) % q<br><br>print(&quot;-&quot; * 30)<br>print(f&quot;Alice key x_1: {x1_recovered}&quot;)<br>print(f&quot;Is attack successful: {x1 == x1_recovered}&quot;)</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=317e9fd47852" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[“Understanding the Bybit Hack: Analyzing the Attack and Its Impact”]]></title>
            <link>https://medium.com/@oznurmut/bybit-hack-critical-security-flaws-exposed-in-recent-attack-67056ff630b3?source=rss-c6c2e75355b8------2</link>
            <guid isPermaLink="false">https://medium.com/p/67056ff630b3</guid>
            <dc:creator><![CDATA[Öznur Mut Sağdıçoğlu]]></dc:creator>
            <pubDate>Wed, 05 Mar 2025 10:53:37 GMT</pubDate>
            <atom:updated>2025-03-05T10:58:24.466Z</atom:updated>
            <content:encoded><![CDATA[<p><em>Öznur MUT SAĞDIÇOĞLU, PhD, Cryptography Researcher/Consultant at TÜBİTAK BİLGEM Blockchain Research Laboratory.</em></p><p>On February 21, 2025, Bybit, one of the fastest-growing cryptocurrency ex-<br>changes, with over 2 million registered users, was hit by a massive cyberattack, leading to the theft of over $1.4 billion in cryptocurrencies, including 401,347 Ether. This incident marks the biggest exchange hack in history, highlighting the growing sophistication of cyber threats.</p><p>The attack is revealed when a critical attack is detected on the Ethereum<br>blockchain network. The system’s AI engine identified an anomaly in a transaction and flagged it as a critical threat in real time.<br>Ben Zhou, the CEO of Bybit, recently shared the preliminary details of the<br>hack, shedding light on how attackers managed to breach the exchange’s security systems. According to cybersecurity firms Sygnia Labs and Verichains, the source of the attack appears to be a vulnerability in the infrastructure of Safe{Wallet}, rather than a direct breach of Bybit’s platform itself, [<a href="https://docsend.com/view/rmdi832mpt8u9">Syg</a>] and [<a href="https://docsend.com/view/rmdi832mpt8u93s7/d/rwecw3rumhqtgs6a">Veric</a>]; (Safe Wallet is a company that provides security solutions for cryptocurrency wallets, and it has been associated with Bybit for offering wallet infrastructure services).</p><p>The attack targeted the multisig cold wallet on Safe{Wallet} but was executed through a compromise on the hot wallet side, with social engineering tactics impacting the cold wallet.<br>Instead of directly exploiting protocol vulnerabilities, attackers manipulated the Safe wallet code, which is used by multisig cosigners for transactions through an infrastructure breach, deceiving signers into approving fraudulent transactions. Namely, the attackers exploited the Safe Protocol’s ‘<em>execTransaction</em>‘ function to alter legitimate transactions.<br>By leveraging the <em>‘execTransaction‘ </em>function, the attackers replaced Bybit’s<br>multisig contract with a malicious one, enabling them to redirect funds to their own addresses.<br>How is it possible? Etherium is based on smart contracts. We can write<br>a multi-signature code with the public key of authenticated users. Then, for example, in a 3 out of 5 case, it is written 5 public key of authenticated users. 3 of the users can sign, and then a transaction is made. A smart contract, like a multisig smart contract, is immutable and not updateable. When it is written, you cannot change it; even if it contains some bugs, it stays forever.</p><p>Sometimes, a new version, patch, or improvement is needed for a smart contract. To address this, the proxy smart contract pattern is often used. A proxy contract forwards user calls to the designated contract using <em>delegatecall</em>. In a multisig wallet setup, once the authorization process is completed, the <em>execTransaction</em> function is used to call the <em>upgradeTo(newLogicAdress)</em> function within the proxy. When the required signatures are provided, the contract address stored in the proxy is updated to <em>newLogicAdress</em>. After the update, the proxy redirects <em>delegatecall</em> to the new contract, effectively replacing the old logic while keeping the proxy itself unchanged. Throughout this process, the proxy contract remains the same, only modifying the address it points to.</p><p>A simple use case of the proxy pattern could be in the management of a<br>token contract. If the logic of the token needs to change (e.g., adding new<br>features or fixing a bug), the proxy contract can be updated to point to a<br>new implementation contract while the users still interact with the same proxy address.<br>Thus, when the <em>execTransaction</em> function, with its hacked parameters, is<br>triggered, the malicious smart contract is executed through the proxy contract. In the end, the hacker transfers all the funds to their own address.</p><p>Based on the audits and analyses released so far, how the attack was executed can be written as follows:</p><ol><li>Initiating the Transaction:</li></ol><ul><li>Any user can start a transaction using the Safe Protocol’s <em>execTrans-<br>action</em> function. If this initiating user is compromised, the transaction<br>parameters are hacked.</li></ul><p>2. Understanding the Transaction Parameters</p><ul><li><em>execTrans(address to,unit256 value,bytes data,unit8 operation,unit256<br>safeTxGas,unit256 basGas,unit256 gasPrice, address gasToken, address<br>refundReceiver, bytes Signatures)</em></li><li><strong>uint8 operation</strong> — a crucial parameter that determines how the<br>transaction is executed.</li><li>If <strong>uint8 operation </strong>= 0, the transaction is a standard call, meaning<br>the funds are directly transferred from the cold wallet to the intended<br>recipient (e.g., Bybit’s multisig smart contract).</li><li>If <strong>uint8 operation</strong> = 1, the transaction executes a <em>delegatecall</em>, which<br>allows execution within the context of another contract. Since this was likely not validated or visible on the UI, the attack was able to occur.</li></ul><p>3. Exploiting the <em>delegatecall</em> Mechanism</p><ul><li>The attacker compromised a cold wallet, possibly through a cyber<br>attack, and altered <strong>uint8 operation</strong> to 1. This change caused the<br>Safe multisig wallet to execute a <em>delegatecall </em>instead of a normal<br>call.</li></ul><p>4. Redirecting Execution to a Malicious Contract</p><ul><li>Since <em>delegatecall </em>runs the code of another contract while maintaining the original storage context, the attacker set the proxy contract to point to their malicious smart contract instead of a legitimate one.</li></ul><p>5. The Malicious Contract’s Functionality</p><ul><li>Once the malicious contract is uploaded, the hacker gains full control, including the ability to transfer all funds to their own address.</li></ul><p>6. Final Exploitation: Sweeping the Funds</p><ul><li>The attacker’s malicious contract contained a function (e.g., sweepFunds() ) that redirected all assets to the attacker’s address.</li></ul><p>7. Theft of Assets</p><ul><li>As a result, over $1 billion in assets, including 400,000 ETH, were stolen<br>from the compromised Safe wallet.</li></ul><p>Why Was This Attack So Effective?<br>• <em>UI Deception</em>: The attack tricked signers into approving a transaction<br>they thought was legitimate.<br>• <em>Delegatecall Exploitation</em>: Since delegatecall runs the code of another contract within the same storage context, the attacker could seize control of the transaction and manipulate it.<br>• <em>Malicious Contract Control</em>: By selecting their contract through the<br>proxy, the attacker could freely dictate what the transaction did — such as<br>transferring all funds to their own address.<br>• This attack highlights the risks of <em>delegatecall</em> in smart contract design<br>and the importance of verifying contract execution paths before signing<br>transactions.</p><h3>Mitigating Risks</h3><p>The first and naive method is that signing a transaction must be done completely offline. There are many methods to sign transactions in the custody world. Air-gapped cold storage can be a solution. But, in the end, the device is connected to the internet. A robust solution is that the signing be done on a completely offline device. How can we do this in real life? One can use a QR code, for example. However, Wi-Fi or Bluetooth connection could reveal the proposal side parameters into the internet like the creation of transaction values.</p><p>The Bybit attack redirected the transaction target to a malicious smart<br>contract created by the attacker. This was achieved by an attacker who has control of a cold wallet (after a cyber attack) and modified a parameter in the <em>execTransaction </em>function within SafeWallet’s software. Thus, strict validation of transaction parameters and restricting <em>delegatecall </em>usage can mitigate exploits.</p><p>Moreover, more secure alternatives, like MPC (Multi Party Computation), could be implemented. MPC enhances privacy by eliminating the need for multiple on-chain signatures, ensuring no single point of failure. With key management and approval processes handled off-chain, MPC can operate without the blockchain even knowing it’s being used, providing an extra layer of security and discretion.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=67056ff630b3" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Understanding Feldman’s Verifiable Secret Sharing: Definition, Example, and Rust Implementation]]></title>
            <link>https://medium.com/@oznurmut/verifiable-secret-sharing-providing-integrity-and-consistency-in-secret-sharing-97e598491bd1?source=rss-c6c2e75355b8------2</link>
            <guid isPermaLink="false">https://medium.com/p/97e598491bd1</guid>
            <dc:creator><![CDATA[Öznur Mut Sağdıçoğlu]]></dc:creator>
            <pubDate>Tue, 14 Jan 2025 09:28:03 GMT</pubDate>
            <atom:updated>2025-01-14T09:40:49.457Z</atom:updated>
            <content:encoded><![CDATA[<p>In cryptography, a secret sharing scheme is verifiable if it includes<br>additional information that allows parties to validate the correctness and consistency of their shares. Unlike traditional secret sharing, which assumes an honest dealer, Verifiable Secret Sharing (VSS) protocols ensure the secure distribution of secrets, guaranteeing that all participants receive valid and consistent shares, even in the presence of malicious actions by the dealer or some parties.<br>Verifiable secret sharing schemes are crucial for secure multi-party computation. In a multi party computation, each party acts like a dealer in a VSS. This ensures that all parties receive valid shares and that a well-defined secret can always be reconstructed even if some parties act dishonestly.<br>In general, for a multi party computation using a verifiable secret sharing<br>scheme, parties are provided with auxiliary information, such as cryptographic commitments, to verify the correctness of their shares. These commitments guarantee that the distributed shares are consistent with the secret and that any tampering or inconsistency can be detected.</p><p>The concept of VSS was introduced in 1985 by Benny Chor, Shafi Gold-<br>wasser, Silvio Micali, and Baruch Awerbuch , [<a href="https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&amp;arnumber=4568164">CGMA</a>]. Feldman’s Verifiable Secret Sharing (VSS) is a widely known and used protocol built on Shamir’s secret sharing scheme, and its security relies on the hardness of the discrete logarithm problem, [<a href="https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&amp;arnumber=4568297">Feldman</a>].<br> The Discrete Logarithm Problem (DLP) is hard in a group <em>G </em>means that given</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/97/1*Qwr6h49ky007snNApg1xaQ.png" /></figure><p>it is computationally infeasible to find <em>x</em>.<br>This note explains Feldman’s VSS protocol, accompanied by a straightforward example, and includes a Rust implementation for a single<br>dealer scenario.</p><h4>Feldman’s Verifiable Secret Sharing Scheme</h4><p>Feldman’s VSS allows the parties to verify the shares they receive from the<br>dealer, [<a href="https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&amp;arnumber=4568297">Feldman</a>]. The main idea of Feldman’s VSS is that the dealer does not only distribute the secret but also needs to send a commitment to the parties in order for them to verify their secret shares. The dealer chooses a polynomial whose coefficients are random over a finite field.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/396/1*rIAcl8TspXiEPMnab34AFw.png" /></figure><p>The commitment is the public values of the coefficients</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/387/1*AaCwoOVE6SqZwPC5bV1OdQ.png" /></figure><p>where <em>p </em>and <em>q </em>are primes (<em>q </em>is the greatest divisor of <em>p − 1</em>) and <em>g </em>is the<br>generator of the subgroup</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/195/1*7DToPvOxilrGxHynnjlt4A.png" /></figure><p>Since the discrete logarithm problem is hard for today’s computers, no one can learn the coefficients and, as a result, the polynomial. The dealer sends to each party <em>Pi </em>the secret shares <em>f (i)</em>, and the commitment values:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/387/1*qu5P1dcucxkIOZfO0-BWYg.png" /></figure><p>In the reconstruction of the secret, each party <em>Pi </em>verifies the secret share<br>sent by the dealer. To verify the share sent by the dealer, <em>Pi </em>computes both</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/420/1*UksSoQDfyMhh8XJ8lWs6iA.png" /></figure><p>Since</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/521/1*XAUFK7wBjnSaj3kKSvQvQw.png" /></figure><p>the equality holds if the secret share is valid. If the equality does not hold then <em>Pi </em>publishes a complaint against the dealer. If there are more than <em>t </em>complaints against the dealer, then the dealer is not considered honest and is disqualified, and clearly, the secret will not be reconstructed.</p><p>Otherwise, if at least<em> t + 1</em> secret shares are verified by the parties, the secret <em>f (0)</em> can be constructed by using the polynomial interpolation, [<a href="https://en.wikipedia.org/wiki/Polynomial_interpolation">Int</a>].</p><p><strong>Lagrange interpolation</strong>: Let <em>x1, …, xn</em> be distinct field elements where no<br>two <em>xj </em>are the same. We denote the Lagrange basis polynomials with respect to a set <em>|I| &lt; n</em> by <em>Lj </em>where</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/238/1*nu5PwZSJmL8CKiv0VbgHiA.png" /></figure><p>The standard Lagrange interpolation works by the fact that for any set of <em>t+1</em> distinct points <em>{(xi, f (xi))}, i∈I</em> , it holds that</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/241/1*IMGdx5OXCnr1KYLy1aUWTA.png" /></figure><p>is the unique degree <em>t </em>polynomial for every <em>i ∈ I</em>.</p><p><strong>An Example of Feldman’s VSS</strong></p><p>Let <em>G </em>be a cyclic group of order <em>23 </em>generated by <em>g= 2</em>. Assume that<br>there are 6 parties, and the threshold is<em> t = 3</em>.</p><p>A dealer uses a random polynomial <em>f (x)</em> of degree 2 defined over the finite<br>field <em>Fq </em>. Let <em>q = 11</em> because <em>q </em>is the<em> </em>largest prime dividing <em>p − 1</em>.<br>Let the polynomial be</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/312/1*XjYJvOOJ0QhVRTxTKt_7vQ.png" /></figure><p>where 9 is the secret to be shared.</p><p>Each party <em>Pi </em>receives a share <em>f (i) </em>computed mod 11. You can choose the number of parties and the threshold in the code given below.</p><p><em>P1 </em>gets <em>(1, f (1) = 0 mod q ),</em></p><p><em>P2 </em>gets<em> (2, f(2)=5 mod q)</em> ….</p><p>The shares and the corresponding parties are</p><p>(P1; 1, 0), (P2; 2, 5), (P3; 3, 2), (P4; 4, 2), (P5; 5, 5), (P6; 6, 0)</p><p>The polynomial operates over the finite field <em>Fq </em>, while commitments are<br>made in the group <em>G </em>of order <em>p</em>. These commitments bind the polynomial<br>coefficients to group elements. To commit to the secret shares and its polynomial coefficients, the dealer computes and sends</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/527/1*b3bXuSMG6nDiuzxsUbuKDQ.png" /></figure><p>This ensures that <em>f (i)</em> corresponds to the committed polynomial <em>f (x)</em>, guaranteeing that the dealer distributed consistent shares.<br>According to the example, <em>P2 </em>can check his share by looking at the equality:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/603/1*jsMgMXFFJZZEUUnRCXhJoQ.png" /></figure><p>This confirms to <em>P2 </em>that the share provided by the dealer is indeed valid.</p><p>After <em>P2, P5 </em>and <em>P6 </em>verify their shares, the secret 9 is reconstructed by using the Lagrange interpolation. Note that the secret is never revealed and no party can learn it.</p><h4>The Rust code</h4><p>The following Rust code is for Feldman’s VSS with a single dealer. This code<br>can be updated in a multi-party setting.</p><pre>use rand::Rng;<br>use std::collections::HashSet;<br><br>// Function to calculate modular exponentiation<br>fn mod_exp(base: u64, exp: u64, p: u64) -&gt; u64 {<br>    let mut result = 1;<br>    let mut base = base % p;<br>    let mut exp = exp;<br><br>    while exp &gt; 0 {<br>        if exp % 2 == 1 {<br>            result = (result * base) % p;<br>        }<br>        base = (base * base) % p;<br>        exp /= 2;<br>    }<br>    result<br>}<br><br>// Function to evaluate a polynomial at a given x value<br>fn evaluate_polynomial(coefficients: &amp;[u64], x: u64, q: u64) -&gt; u64 {<br>    coefficients.iter().rev().fold(0, |acc, &amp;coeff| (acc * x + coeff) % q)<br>}<br><br>// Generate commitments for the polynomial coefficients<br>fn generate_commitments(coefficients: &amp;[u64], g: u64, p: u64) -&gt; Vec&lt;u64&gt; {<br>    coefficients.iter().map(|&amp;coeff| mod_exp(g, coeff, p)).collect()<br>}<br><br>// Verify a share using commitments<br>fn verify_share(x: u64, y: u64, commitments: &amp;[u64], g: u64, p: u64) -&gt; bool {<br>    let lhs = mod_exp(g, y, p);<br>    let rhs = commitments<br>        .iter()<br>        .enumerate()<br>        .fold(1, |acc, (i, &amp;commitment)| {<br>            let exp = x.pow((i as u64).try_into().unwrap());<br>            (acc * mod_exp(commitment, exp, p)) % p<br>        });<br>    lhs == rhs<br>}<br><br>// Reconstruct the secret using Lagrange interpolation<br>fn reconstruct_secret(shares: &amp;[(u64, u64)], q: u64) -&gt; u64 {<br>    let mut secret = 0;<br><br>    for (i, &amp;(x_i, y_i)) in shares.iter().enumerate() {<br>        let mut product = 1;<br>        for (j, &amp;(x_j, _)) in shares.iter().enumerate() {<br>            if i != j {<br>                let numerator = q + x_j;<br>                let denominator = q + x_j - x_i;<br><br>                let inv_denominator = mod_inverse(denominator % q, q);<br>                product = product * numerator % q * inv_denominator % q;<br>            }<br>        }<br>        secret = (secret + y_i * product % q) % q;<br>    }<br><br>    secret<br>}<br><br>// Calculate the modular inverse using the extended Euclidean algorithm<br>fn mod_inverse(a: u64, q: u64) -&gt; u64 {<br>    let mut mn = (q, a);<br>    let mut xy = (0, 1);<br><br>    while mn.1 != 0 {<br>        let quotient = mn.0 / mn.1;<br>        mn = (mn.1, mn.0 % mn.1);<br>        xy = (xy.1, xy.0 - quotient as i64 * xy.1);<br>    }<br><br>    ((xy.0 + q as i64) % q as i64) as u64<br>}<br><br>fn main() {<br>    // Generator for a cyclic group and the order of the group<br>    let p = 23;<br>    let g = 2;<br>    let q=11;  //the order of a finite field F_q<br>    // Secret to share<br>    let secret = 2;<br>    println!(&quot;Secret: {}&quot;, secret);<br><br>    // Total shares and threshold<br>    let total_shares = 7;<br>    let threshold = 3;<br>    println!(&quot;{}-out-{}&quot;,threshold,total_shares);<br><br>    // Generate random polynomial coefficients<br>    let mut rng = rand::thread_rng();<br>    let mut coefficients: Vec&lt;u64&gt; = (0..threshold - 1).map(|_| rng.gen_range(1..q)).collect();<br>    coefficients.insert(0, secret); // Constant term is the secret<br>    println!(&quot;Dealer&#39;s Polynomial: {:?}+{:?}x+{:?}x^2 &quot;, coefficients[0],coefficients[1],coefficients[2]);<br><br>    // Generate commitments<br>    let commitments = generate_commitments(&amp;coefficients, g, p);<br>    println!(&quot;Commitments: {:?}&quot;, commitments);<br><br>    // Generate shares<br>    let shares: Vec&lt;_&gt; = (1..=total_shares)<br>        .map(|x| (x as u64, evaluate_polynomial(&amp;coefficients, x as u64, q)))<br>        .collect();<br>    println!(&quot;Shares: {:?}&quot;, shares);<br><br>    // Randomly select shares for reconstruction<br>    let mut selected_indices = HashSet::new();<br>    while selected_indices.len() &lt; threshold {<br>        selected_indices.insert(rng.gen_range(0..total_shares));<br>    }<br>    let selected_shares: Vec&lt;_&gt; = selected_indices.iter().map(|&amp;i| shares[i]).collect();<br>    println!(&quot;Selected shares: {:?}&quot;, selected_shares);<br><br>    // Verify selected shares<br>    for &amp;(x, y) in &amp;selected_shares {<br>        if verify_share(x, y, &amp;commitments, g, p) {<br>            println!(&quot;Share ({}, {}) is valid.&quot;, x, y);<br>        } else {<br>            println!(&quot;Share ({}, {}) is invalid!&quot;, x, y);<br>        }<br>    }<br><br>    // Reconstruct the secret<br>    let reconstructed_secret = reconstruct_secret(&amp;selected_shares, q);<br>    println!(&quot;Reconstructed Secret: {}&quot;, reconstructed_secret);<br><br>    assert_eq!(secret, reconstructed_secret);<br>}</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=97e598491bd1" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[The Security of the Threshold EdDSA Protocol]]></title>
            <link>https://medium.com/@oznurmut/the-security-of-the-threshold-eddsa-protocol-66dc3fc14530?source=rss-c6c2e75355b8------2</link>
            <guid isPermaLink="false">https://medium.com/p/66dc3fc14530</guid>
            <dc:creator><![CDATA[Öznur Mut Sağdıçoğlu]]></dc:creator>
            <pubDate>Sun, 05 Jan 2025 17:31:49 GMT</pubDate>
            <atom:updated>2025-01-07T07:05:37.739Z</atom:updated>
            <content:encoded><![CDATA[<p><em>Öznur MUT SAĞDIÇOĞLU, PhD, Cryptography Researcher/Consultant at TÜBİTAK BİLGEM Blockchain Research Laboratory.</em></p><p>Edwards-curve Digital Signature Algorithm (EdDSA) is a signature algorithm scheme using a variant of the Schnorr signature based on twisted Edwards curves. It aims to have a design to deliver higher performance than existing digital signature schemes while maintaining robust security. This scheme was created by a team including Bernstein et al. in 2011, [<a href="https://eprint.iacr.org/2011/368">Ber+12</a>]. EdDSA is a deterministic signature meaning that we always get the same signature for the same private key and message, whereas ECDSA is non-deterministic which was proposed around 2001 by Johnson et al. <a href="https://www.cs.miami.edu/home/burt/learning/Csc609.142/ecdsa-cert.pdf">[Jhon+01]</a>.</p><p>A threshold EdDSA is a signature scheme where a group of parties collectively compute a signature without learning the private key. In a <em>(t, n)</em>-threshold signature scheme, <em>n </em>parties hold key shares, and any subset of <em>t </em>parties can generate a signature, but no group smaller than t parties can perform this task. The parties all want to sign the same message <em>m</em>, naturally, they agree on an elliptic curve over a finite field, the same base point <em>G </em>on the curve, and a cryptographic hash function Hash.</p><p>Threshold key generation for EdDSA consists of the secret sharing of both the private signing key and a random secret nonce across multiple parties, enhancing security and eliminating single points of failure. Thus, a threshold EdDSA signing can be based on a DKG-based (Distributed key generation) approach. A verifiable DKG allows each party to see the commitments of all shares and confirm their validity.</p><p>As a result, the commitment to publicly shared nonces and their verification by all parties is particularly crucial. Because there is an attack that exploits the absence of nonce commitment within EdDSA threshold protocol. The vulnerability was first demonstrated through an attack on the CoSig algorithm by Drijvers et al. in 2018 <a href="https://eprint.iacr.org/2018/417">[Dri+19]</a>. As a result, it is observed that this attack can also be applied to Schnorr, EdDSA, and Musig signature schemes. This writing provides a detailed analysis of the application of this attack to the threshold EdDSA signature scheme.</p><p>In a general view of the attack, due to the absence of commitment and verification of nonces, an attacker can wait for nonces from other parties and then he find an evil/malicious nonce. As a result, using this evil nonce, he can sign any message he wants, and according to the attack, this message need not be known by the other parties. In other words, the attacker can perform signature forgery without other parties’ knowledge. To find such an evil nonce relies on Wagner’s Generalized Birthday Attack, as described in <a href="https://www.iacr.org/archive/crypto2002/24420288/24420288.pdf">[Wag02</a>].</p><h3>The Attack</h3><p>If the commitment of shared nonces and their verification is missing, then an adversary has the potential to lead other parties into signing something they didn’t intend.<br>Let’s assume there are three parties in the protocol to facilitate the explanation of the attack. The naming of these parties shall be as follows: Alice, Bob, and Carol. Let’s also assume that Carol is the attacker. Let <em>(d, D = dG)</em> represent the aggregated private and public key pairs.</p><p>The attack works as follows.</p><ol><li>Carol opens <em>k </em>concurrent signing sessions with Alice and Bob. She pro-<br>poses <em>k </em>messages <em>{m1, m2, …, mk} </em>which Alice and Bob would be perfectly agreeable to sign. The number<em> k </em>will be discussed in <strong>Wagner Generalized Birthday Algorithm section.</strong></li><li>Carol waits for Alice and Bob to share their public nonces</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/514/1*S7hYO9zxYFkhNZBmNr1WPw.png" /></figure><p>with Carol in every one of the signing sessions.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/605/1*cqbMptbEQBck5Cyo6M9ZTA.png" /></figure><p>where <em>rai </em>and <em>rbi </em>denote Alice and Bob’s secret nonces for signing session <em>i</em>.</p><p>3. Carol chooses randomly a nonce <em>rc ∈ Zn</em> and generates its point on the<br>curve <em>Rc = rcG</em>.</p><p>4. Carol uses<strong> Wagner’s algorithm</strong> (see Wagner Generalized Birthday Algorithm section) to find <em>k </em>different curve points <em>{X1, X2, …, Xk}</em> such that for the evil challenge <em>e′</em> for its evil message <em>m′</em> can be written as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*CureYhifgdbMGKbhFWtyIw.png" /></figure><p>and <em>D </em>is the aggregated public key. The evil nonce <em>R′ </em>is the sum of Alice<br>and Bob’s public nonces and Carol’s nonce <em>Rc</em>.</p><p>5. Each <em>Xi</em> is hashed with the message <em>mi </em>and produces a challenge</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/320/1*zFKA5PD_g5Vv5gVM-rCHgQ.png" /></figure><p>for each signing session <em>i</em>.</p><p>6. Due to Wagner’s algorithm, the sum of all <em>ei</em> hashes equals another hash<br>which Carol has chosen based on the evil message <em>m′</em> which Alice and Bob<br>never see.</p><p>7. Since there is no validation of public nonces in the protocol, Carol can see Alice and Bob nonces and can produce evil nonces <em>Rci</em>. Carol calculates<br>a set of nonces <em>{Rc1, …, Rck} </em>one for each signing session</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/466/1*HZqGvKekJcFXovWf7XHAUQ.png" /></figure><p>8. Alice and Bob upon receiving <em>Rci</em>, will compute the aggregate nonce</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/417/1*zyUNM6ZRd51vWeOuRR6oLA.png" /></figure><p>9. Carol can convince Alice and Bob to sign <em>{m1, m2, …, mk} </em>with the aggregated nonces <em>{X1, X2, …, Xk} </em>chosen by Carol. I know it is not an easy<br>job, but it is not impossible!</p><p>10. After that, Carol awaits <em>k </em>pairs of partial signatures</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/757/1*9XtsZ24LUvU2QuL1vCTViQ.png" /></figure><p>where <em>wa = λa.da</em> and <em>wb = λb.db</em>, and <em>da </em>and <em>db </em>are secret shares of Alice<br>and Bob, respectively <a href="https://en.wikipedia.org/wiki/Polynomial_interpolation">[Int]</a>. <em>D </em>is the aggregated public key.</p><p>12. Carol sums Alice and Bob’s signature shares from <em>k </em>signing sessions to<br>create a forged signature <em>s′ </em>which is valid for the evil message <em>m′, D</em> and<br>the evil nonce <em>R′.</em></p><h4>Forged Signature:</h4><p>13. Carol adds her signature share</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/846/1*kM2Ycz_44CMd3rVayC5RFw.png" /></figure><p>14. Since</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/620/1*BZAGHmLSAEt1uYFCdxAwHg.png" /></figure><p>15. Thus<em> s′ </em>can be written as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/587/1*tDnt-4xJJNE680rEC2yYsw.png" /></figure><p>16. Recall that the evil nonce is defined as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/379/1*6nsftuQHMkHF5fJwd_3sUg.png" /></figure><p>Although Carol does not know</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/284/1*px6oGvIUa3uLFtZ7P4B3ig.png" /></figure><p>she assumes that it is a discrete logarithm of <em>R′</em>. Now the secret nonce<br>is</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/691/1*B_4FVVkChxuHIOl0DiYCbA.png" /></figure><p>17. Now substitute <em>r′ </em>into the signature equation to show the aggregated<br>signature is</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/608/1*vsY_R5Pt3LsxkdQ0kn4IaQ.png" /></figure><p>and call <em>wa + wb + wc</em> as <em>d, </em><a href="https://en.wikipedia.org/wiki/Polynomial_interpolation">[Int]</a>.<br>Thus,<em> (R′, s′)</em> is a forged signature of the evil message<em> m′ </em>with the public<br>key <em>D</em> and</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/237/1*MrEffuf-P44LT3h7_zr_HQ.png" /></figure><p><strong>Verification</strong>:</p><p>The signature for the evil message <em>m′</em> and the public key <em>D</em> is <em>(R′, s′)</em>.<br>18. Calculate <em>H(R′||D||m′)</em> which is exactly <em>e′</em>.<br>19. Calculate <em>s′G</em> and <em>R′ + e′D</em>. If they are equal then the signature is valid.</p><h3>Wagner Generalized Birthday Algorithm</h3><p>It is time to explain how we use Wagner’s Generalized Birthday Algorithm in the attack above.<br>An adversary can adaptively choose its shared <em>R</em>-value to determine the<br>aggregated<em> R</em>-value after seeing shared nonce values from all other signing parties. Exploiting the attack involves solving the Generalized Birthday Problem, which can be done with subexponential complexity using Wagner’s algorithm, <a href="https://www.iacr.org/archive/crypto2002/24420288/24420288.pdf">[Wag02]</a>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*VCcib-L8-njCdNRK2idZzQ.png" /></figure><p>Carol finds <em>k</em> distinct points (some set of nonces) <em>X1, X2, .., Xk </em>on the curve<br>such that for each signing session they combined with <em>D</em> and <em>{m1, m2, .., mk</em>} hash into the challenges <em>e1, e2, .., ek</em>. Their sum will be the evil challenge <em>e′ = e1 + e2 + .. + ek</em>, see the Attack section in Step 4.</p><p>For Wagner’s algorithm, some lists are defined to create the evil challenge as wanted:<br>1. Carol generates<em> k − 1</em> lists<em> {L1, L2, .., Lk−1}</em>.</p><p>2. Each list <em>Li,</em> for <em>i = 1, 2, .., k − 1</em>, contains say λ hashes as follows</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/285/1*KfspRqgWEPGG0xsiO_Au1Q.png" /></figure><p>Namely, <em>Li = {ei1, ei2, …, eiλ} </em>(see Table 1) We will consider λ later.</p><p>3. Carol generates the last list <em>Lk = {ek1, ek2, , …, ekλ</em>} in the same way, but<br>this time she subtracts<em> e′</em> from each hash <em>ekj </em>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/400/1*hOqp9sTJEvOqxQBhEk6ynw.png" /></figure><p>4. Carol stores <em>Xij </em>values in each list because she needs to define <em>Rci</em>, for<br><em>i = 1, 2, .., k</em> (see the Attack section in Step 8).</p><p>As a result, Carol can find a hash value in each list and</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/511/1*Bc0P1xYyHVEHJcPGoNMl6w.png" /></figure><p>However, how many hash values does Carol need to obtain this sum? In<br>summary, what should the value of λ be?</p><h4>The complexity</h4><p>How many hashes do we need to find the following equation holds</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/538/1*HPhfjj0LL31xvU3RwJwPIQ.png" /></figure><p>where <em>ej,i_j ∈ Lj</em>?<br>This problem is also called the k-sum problem: Given <em>k </em>lists <em>L1, L2, …, Lk</em><br>of elements drawn uniformly and independently at random from {0, 1}^n, find<em> x1 ∈ L1, x2 ∈ L2, .., xk ∈ Lk</em> such that<em> x1 ⊕ x2 ⊕ … ⊕ xk = 0.</em><br>For <em>k = 2</em> case, it is simply the Birthday problem. Let’s have two lists <em>L1</em><br>and <em>L2</em>, each of length λ. Carol wants to find a hash chosen from each list<br><em>e1 ∈ L1 and e2 ∈ L2 </em>so that</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/211/1*_vbQai9RBA08-Y2FgW-F_g.png" /></figure><p>This equality holds with the probability</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/33/1*XzK-IpZzkvp2lLW9-niINw.png" /></figure><p>It is because the expected number of solutions in <em>L1 </em>and <em>L2 </em>will be the number of possible pairs<em> (e1i, e2j ) t</em>imes the probability that each pair could be a solution (namely, 1/n).<br>As a result, if λ^2 ≥ n, our expected number of solutions is at least 1, namely there is about a 50% chance that the sum of two values in the two lists will be zero. In other words, the length of each list must be at least</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/34/1*GeQFbCDIPtqaw_GCKMv2Qw.png" /></figure><p>i.e.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/80/1*niP_q9MUsNvNKqFHeQRn0g.png" /></figure><p>For the<em> k &gt; 2</em> case, it is easy to see that a solution to the k-sum problem<br>exists with good probability so long as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/209/1*_0RFrO9MbQXhBQE8rG_Y0w.png" /></figure><p>Since there is no good algorithm with complexity</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/76/1*VP6eQqIsh8LZG-VqfPxRHg.png" /></figure><p>the challenge is to find a solution <em>x1, …, xk</em> explicitly and efficiently, <a href="https://www.iacr.org/archive/crypto2002/24420288/24420288.pdf">[Wag02]</a>. However, Wagner proposes an idea in <a href="https://www.iacr.org/archive/crypto2002/24420288/24420288.pdf">[Wag02]</a> to find a solution explicitly and efficiently. He considers the 4-list birthday problem, see Figure 1.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/405/1*f7WNlz-fFyvDJR1VO8Qcgw.png" /></figure><p>Given <em>L1, .., L4 </em>we find values <em>x1, .., x4 </em>that XOR is zero.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/164/1*bs7ECsf8OqDgFuCLVD0ovA.png" /></figure><p>contains all pairs from L1 × L2 that agree in their least<em> l</em> significant bits. Each list contains about</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/22/1*wq2_VIaz8zvgEE-N1rBLQg.png" /></figure><p>elements.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/365/1*eHCo8aeHoj6LbBWuiSwVrw.png" /></figure><p>We search matches between <em>L12 </em>and <em>L34 </em>so that <em>x1 ⊕ x2 ⊕ x3 ⊕ x4 = 0</em> where lowl(x) represents the least significant bit of x. This leads to a solution to the 4-sum problem.<br>By <a href="https://brilliant.org/wiki/linearity-of-expectation/">the linearity of expectation</a></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/365/1*xMtXAZm6-qM06fhefFeA8w.png" /></figure><p>Similarly,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/124/1*Fm9gfN2rYjGKMfB19yTdVw.png" /></figure><p>Any pair of elements from <em>L12 ×L34</em> yields a match with probability</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/48/1*ZXh0-tl90Cv_XKRP4oHUoA.png" /></figure><p>The expected number of elements in common between <em>L12 </em>and<br><em>L34 </em>is about</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/99/1*lQm8tu5eyqbuKa0Mgeu4GA.png" /></figure><p>To have one solution, we need</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/99/1*QTYWP-5-s5O9PSjcHz4gZA.png" /></figure><p>Thus, if we set<em> l = n/3</em>, we expect to have one solution to the 4-sum problem<br>with non-trivial probability. Since the size of all lists is around</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/44/1*3yEwXg-kO30VbaEaYETK7w.png" /></figure><p>the resulting algorithm can be implemented with</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/78/1*oBhIe7cfxrNVaDv1ck8nsg.png" /></figure><p>time and space. Wagner generalizes this idea to a k-list tree algorithm, <a href="https://www.iacr.org/archive/crypto2002/24420288/24420288.pdf">[Wag02]</a>. First, assume that <em>k </em>is a power of two. Now to solve the k-sum problem even faster than cube-root time for larger values of <em>k</em>, it can be extended the idea of the 4-list tree algorithm.<br>This will be a complete binary tree of depth <em>lgk</em>. At internal nodes of height<br><em>h</em>, we use the join operator</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/311/1*uAG2gSLDUsLb1vR7gbaa7w.png" /></figure><p>except that at the root we use the full join operator. Each element x of an internal list<em> Li…j </em>contains back-pointers to elements <em>x</em>′ and <em>x′′</em> of the two child lists used to form <em>Li…j </em>, such that <em>x = x′ ⊕ x′′</em>.</p><p>In this way, we will obtain an algorithm for the k-sum problem that requires</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/147/1*JFMT0kpkM1ighSjlKWJs5w.png" /></figure><p>time and space and uses lists of size</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/156/1*GrHShjMfCflA2kunpweNOA.png" /></figure><p>If <em>k </em>is not a power of two, we work with<em> </em>⌊k⌋<em>,</em> the largest power of two less<br>than <em>k</em>, and we use the list-elimination trick above. However, the algorithm<br>obtained in this way runs essentially no faster for<em> k = 2^i + j </em>than for <em>k = 2^i</em>.</p><h4>Attack implementation</h4><p>For the implementation, we choose an elliptic curve defined by</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/116/1*1T7ZbP7TaZazE-RBCJQrbA.png" /></figure><p>over finite field of size 101, F_101 is used. <em>G = (1, 2) </em>is the base point of order 17. We use SHA 256 as a cryptographic hash function.<br>The code is written for <em>k = 2</em>. According to Wagner’s Generalized Birthday algorithm, it will be enough to have λ ≥ 10. The code is written in Python.</p><pre>import math<br>from random import randint<br>from ecpy.curves     import Curve,Point<br>from ecpy.keys       import ECPublicKey, ECPrivateKey<br>from ecpy.ecdsa      import ECDSA<br>import random<br>import hashlib<br>import array as arr <br>import math<br><br>#k-sum attack on EdDSA for k=2<br><br>#y^2=x^3+3 over Z_101; G=(1,2) base point<br><br>def double(x, y, a, p):<br>    lambd = (((3 * x**2) % p ) *  pow(2 * y, -1, p)) % p<br>    newx = (lambd**2 - 2 * x) % p<br>    newy = (-lambd * newx + lambd * x - y) % p<br>    return (newx, newy)<br><br>def add_points(P, Q, p):<br>    xp, yp = P<br>    xq, yq = Q<br>    a=0<br>    if xq == yq == None:<br>        return xp, yp<br>    if xp == yp == None:<br>        return xq, yq<br>    <br>    assert (xq**3 + 3) % p == (yq ** 2) % p, &quot;q not on curve&quot;<br>    assert (xp**3 + 3) % p == (yp ** 2) % p, &quot;p not on curve&quot;<br>    <br>    if xq == xp and yq == yp:<br>        return double(xq, yq, a, p)<br>    elif xq == xp:<br>        return None, None<br>    <br>    lambd = ((yq - yp) * pow((xq - xp), -1, p) ) % p<br>    xr = (lambd**2 - xp - xq) % p<br>    yr = (lambd*(xp - xr) - yp) % p<br>    return xr, yr<br><br><br>def apply_double_and_add_method(G, k, p):<br>    target_point = G   <br>    k_binary = bin(k)[2:] <br>    for i in range(1, len(k_binary)):<br>        current_bit = k_binary[i: i+1]<br>        target_point = add_points(target_point, target_point, p)<br>        if current_bit == &quot;1&quot;:<br>            target_point = add_points(target_point, G, p)<br>    return target_point<br><br>def find_hash(n):<br>    m = str.encode(str(n))<br>    hash_value = hashlib.sha256(m).digest()<br>    # Convert the hash value to an integer<br>    c=int.from_bytes(hash_value, &#39;big&#39;)<br>    return c<br><br>G=(1,2)                                                 #base point of order 17<br><br>def key_gen(d):<br>    D=apply_double_and_add_method(G,d,101)<br>    return D<br>#keys <br>da=1                                                   #secret key of Alice<br>D_a=key_gen(da)<br>db=5                                                   #secret key of Bob<br>D_b=key_gen(db)<br>dc=2                                                   #secret key of Carol<br>D_c=key_gen(dc)                <br><br><br><br>D=apply_double_and_add_method(G,(da+db+dc)%17,101)<br>print(&#39;Aggregated public key&#39;,D)<br><br><br><br><br><br>m = [] <br>for _ in range(2):<br>   random_integer = random.randint(1, 101)  <br>   m.append(random_integer)<br>print(&#39;Messages m1,m2 &#39;,m)                                           #k=2 case, we have two messages<br><br><br>sampleRa=[]<br>sampleRb=[]<br>ra=[]<br>rb=[]<br>for i in range(2):                                                   #k=2, each party send two nonces for each message<br>    ra.append(random.randint(1, 101))                                #secret nonce share of Alice<br>    sampleRa.append(apply_double_and_add_method(G,ra[i],101) )<br>    rb.append(random.randint(1, 101) )                               #secret nonce share of Bob<br>    sampleRb.append(apply_double_and_add_method(G,rb[i],101) )<br><br>print(&#39;Ra,ra&#39;,sampleRa,ra)<br>print(&#39;Rb,rb&#39;,sampleRb,rb)<br><br>#Attack<br><br>Rc=(1,2)                                                             #random evil nonce value of Carol<br>rc=1<br>print(&#39;Rc&#39;,Rc)<br><br>m_prime=1                                                         # evil message<br><br>add=add_points(sampleRa[0],sampleRb[0],101)<br>R_agg=add_points(add_points(add_points(add ,sampleRa[1],101),sampleRb[1],101),Rc,101)                 <br>print(&#39;R_prime&#39;,R_agg)<br><br><br>e_prime=find_hash(int(bin(R_agg[0])[2:]+bin(D[0])[2:]+bin(m_prime)[2:],2))  %17                                #evil challenge<br>print(&#39;e_prime&#39;,e_prime)<br><br><br>t=20  #\lambda<br><br>#Wagner&#39;s algorithm to find x1,x2 for k=2 case<br>X=[]<br>for i in range(t):  <br>    X.append(apply_double_and_add_method(G,random.randint(0,16),101) )<br>Y=[]<br>for i in range(t):  <br>   Y.append(apply_double_and_add_method(G,random.randint(0,16),101) )<br>#Lists<br>hashX=[]<br>for i in range(t):<br><br>    hashX.append(find_hash(int(bin(X[i][0])[2:]+bin(D[0])[2:]+bin(m[0])[2:],2)))<br><br>hashY=[]<br>for i in range(t):<br>    hashY.append(find_hash(int(bin(Y[i][0])[2:]+bin(D[0])[2:]+bin(m[1])[2:],2)))<br><br><br> #Wagner k-sum algorithm<br>for i in range(t):<br>    for j in range(t):<br>        if (hashX[i]+hashY[j]-e_prime)% 17 == 0:                     <br>            e1=hashX[i]<br>            e2=hashY[j]    <br><br>#print(&#39;L_1&#39;,X)<br>print(&#39;e1, point&#39;,e1%17, apply_double_and_add_method(G,e1%101,101))<br>#print(&#39;L_2&#39;,Y) <br>print(&#39;e2, point&#39;,e2%17,apply_double_and_add_method(G,e2%101,101))<br><br><br><br><br>sa1=ra[0]+(e1)*da                               #Alice computes her signature share for each signing session<br>sa2=ra[1]+(e2)*da<br><br>sb1=rb[0]+(e1)*db                               #Bob computes her signature share for each signing session<br>sb2=rb[1]+(e2)*db<br><br>s_prime=(sa1+sa2+sb1+sb2+rc+(e_prime*dc)) %17   #Carol computes s_prime<br><br>print(&#39;s_prime&#39;, s_prime)<br><br>#check that s_prime is correctly evaluated<br>if ( (e1+e2-e_prime)%17 == 0 ) and (e_prime%17 !=0) and (e1%17 !=0)  and (e2%17 !=0): <br>  ss_prime=((ra[0]+ra[1]+rb[0]+rb[1]+rc) + (((e1+e2)%17)*(da+db)+(e_prime%17)*dc)) %17                       #s&#39;=r&#39;+e&#39;d<br>assert(ss_prime==s_prime)<br><br><br>#Aggregated forged signature and its verification    <br>r_prime=(ra[0]+ra[1]+rb[0]+rb[1]+rc)%17                                                      #r&#39; is aggregatedly calculated <br>E=apply_double_and_add_method(D,e_prime%101,101)<br>Sum=add_points(R_agg,E,101)<br>S_prime=apply_double_and_add_method(G,(s_prime%101),101) <br>print(&#39;Signature (R_prime, S_prime)=&#39;,R_agg, S_prime)                                         <br>      <br>if Sum == S_prime:                                                 #S_prime=?R_agg+e_prime*D  , evil signature is verified                                 <br>    print(&#39;Forged signature is valid&#39;)<br><br><br><br></pre><h4>References:</h4><p><strong>[Wag02]</strong> David A. Wagner. “A Generalized Birthday Problem”. In: Advances<br>in Cryptology — CRYPTO 2002, 22nd Annual International Cryptology Conference, Santa Barbara, California, USA, August 18–22, 2002, Proceedings. Ed. by Moti Yung. Vol. 2442. Lecture Notes in Computer Science. Springer, 2002, pp. 288–303. doi: 10.1007/3-540–45708–9 \ _19. url: https : / / doi . org / 10 . 1007 / 3–540 — 45708–9%5C_19.</p><p><strong>[Ber+12]</strong> Daniel J. Bernstein et al. “High-speed high-security signatures”. In: J. Cryptogr. Eng. 2.2 (2012), pp. 77–89. doi: 10.1007/S13389–012-0027–1. url: <a href="https://doi.org/10.1007/s13389-012-0027-1">https://doi.org/10.1007/s13389-012-0027-1</a>.</p><p><strong>[Dri+19]</strong> Manu Drijvers et al. “On the Security of Two-Round Multi-Signatures”. In: 2019 IEEE Symposium on Security and Privacy, SP 2019, San Francisco, CA, USA, May 19–23, 2019. IEEE, 2019, pp. 1084–1101. doi: 10.1109/SP.2019.00050. url: <a href="https://doi.org/10.1109/">https://doi.org/10.1109/</a>SP.2019.00050.</p><p><strong>[Int]</strong> Polynomial Interpolation. In: (). url: <a href="https://en.wikipedia.org/">https://en.wikipedia.org/</a><br>wiki/Polynomial_interpolation.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=66dc3fc14530" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[A Comparative Examination of Some Threshold ECDSA Protocols in Custody]]></title>
            <link>https://medium.com/@oznurmut/a-comparative-examination-of-some-threshold-ecdsa-protocols-e7af8cad1992?source=rss-c6c2e75355b8------2</link>
            <guid isPermaLink="false">https://medium.com/p/e7af8cad1992</guid>
            <dc:creator><![CDATA[Öznur Mut Sağdıçoğlu]]></dc:creator>
            <pubDate>Thu, 28 Nov 2024 08:27:11 GMT</pubDate>
            <atom:updated>2025-02-17T17:59:21.449Z</atom:updated>
            <content:encoded><![CDATA[<h3>A Comparative Examination of Some Threshold ECDSA Protocols Used in Custody</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/520/1*Uw2rOLBK22nuQZhycQQKlA.png" /></figure><p><em>Öznur MUT SAĞDIÇOĞLU, PhD, Cryptography Researcher/Consultant at TÜBİTAK BİLGEM Blockchain Research Laboratory.</em></p><p>Digital asset custody involves methods for safeguarding digital assets on behalf of their owners. It can be in many forms, such as hot wallets, cold wallets, hardware wallets, and custodial services for which third-party services manage digital assets on behalf of users.</p><p>Custody primarily focuses on securely storing and managing the cryptographic keys needed to access and transfer the assets: a public key and a private key. The private key allows the asset owner to authorize transactions, serving as a verifiable proof of ownership. Given their crucial role, custody solutions must securely store these keys to ensure that only the asset owner can access them. Otherwise, if the private key is compromised or the asset owner loses it accidentally, the digital asset risks being lost or stolen.<br>As a result, to securely store private keys, and avoid a single point of failure, the concept of sharing custody responsibilities has drawn great attention in recent years with threshold signature algorithms based on multiparty computation (MPC).<br>Threshold signatures require a subset of parties, namely signatories, authorized to produce signatures on behalf of the group. The message is only considered signed if a number <em>t</em>, the threshold, of signers signs the message. The process is based on MPC, no single entity has full control of the key, enhancing security and resilience. In other words, these solutions ensure that the private key is never exposed at any instance of the process.</p><p>Although numerous ECDSA threshold signature protocols have been pro-<br>posed in the literature, this writing focuses on GG18, GG20, MPC CMP, CG-<br>GMP, and a Class Group-based ECDSA scheme CCLST ([<a href="https://eprint.iacr.org/2019/114.pdf">GG18</a>], [<a href="https://eprint.iacr.org/2020/540.pdf">GG20</a>], [<a href="https://eprint.iacr.org/2020/492.pdf">CMP20</a>], [<a href="https://eprint.iacr.org/2021/060.pdf">CGGMP</a>], and [<a href="https://eprint.iacr.org/2021/291.pdf">CCLST</a>], respectively). We talk about each protocol’s performance, resilience against potential attacks, and inherent complexity, evaluating their practical application for secure and efficient custody solutions in the digital asset space.</p><p>Today, various organizations and institutions are working on digital asset custody solutions using threshold signature schemes based on MPC, such as BitGo, Fireblocks, and Coinbase Custody. Selecting an optimal threshold signature scheme is important for ensuring the security and efficiency of digital asset custody. To this end, a thorough understanding of the differences between various threshold signature schemes is essential, especially for custody services looking to implement Multi-Party Computation (MPC) solutions in their custody frameworks.</p><p>This comparison helps to assist developers and researchers in evaluating these protocols to choose the most effective solution based on the specific requirements of their MPC-based custody projects.</p><h3>Threshold ECDSA Protocol</h3><p>A threshold signature scheme (TSS) is a signature scheme where a group of parties collectively compute a signature without learning the private key. In a <em>(t,n)</em> -threshold signature scheme, <em>n </em>parties hold key shares, and any subset of<em> t </em>parties can generate a signature, but no group smaller than <em>t</em> parties can perform this task. TSS key generation depends on distributed key generation (DKG) protocol, in this way, no party can learn the private key when they generate key shares.</p><p><strong>ECDSA (Elliptic Curve Digital Signature algorithm)</strong></p><p>ECDSA is an Elliptic Curve Digital signature algorithm. While DSA is based on arithmetic operations modulo over a prime number, ECDSA uses elliptic curve operations over finite fields. Requiring shorter key lengths and being more efficient than its predecessors, ECDSA has become the signature scheme of choice, powering major systems like Bitcoin and Ethereum.</p><p>Let <em>F_q</em> be a finite field of order <em>q</em>, and <em>H </em>be a hash function for embedding messages into the field of <em>q </em>elements. Let <em>(G,g,q)</em> denote the group-order-generator tuple associated with the ECDSA curve. We use the multiplicative notation for the group operation.</p><p>The ECDSA signature for a secret key <em>x ∈ F_q</em> and the message <em>m </em>is</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/390/1*XmqjEP7xLFnNJtZrPcTNDg.png" /></figure><p><em>r </em>is the x-projection (mod <em>q</em>) of the point</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/269/1*yUfZAYHWpTnXBtJHpIsmmg.png" /></figure><p>and <em>k </em>is uniformly random nonce in <em>F_q.</em></p><p>The verification algorithm accepts signature <em>(r, s)</em> with the message <em>m </em>and<br>the public key <em>Q = x × G.</em></p><p>The verifier calculates</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/448/1*wCb8iuEJABM2pxBT93QfwQ.png" /></figure><p>If <em>r = x_1</em>, then the signature is valid otherwise it is invalid.</p><h4>Difficulties in threshold computing</h4><p>ECDSA signature depends on a random nonce <em>k</em>, which must be kept secret and used only once per signature. Threshold ECDSA protocols require the participants collaboratively to compute</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/82/1*NZQzEkmbYC62Plfkv9OK5w.png" /></figure><p>without revealing <em>k </em>and <em>kx </em>without compromising the signature private key <em>x.</em></p><p>Directly sharing information about <em>k </em>exposes it, which can lead to the compromise of the private key <em>x</em>. Indeed, if the nonce <em>k </em>is reused or leaked for two different messages <em>m </em>not equal to <em>m’,</em> one can have the private key as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/250/1*ewoB0ndgQPBYVhC0uA1bVQ.png" /></figure><p>Moreover, it was shown that even less than 1 bit of bias in <em>k </em>is enough to recover the whole private key, [<a href="https://doi.org/10.1145/3372297.3417268">LadderLeak20</a>]. This situation can happen in real life, for example, a random number generator can generate a number whose most significant bit(s) may be the same for different messages. Knowing such a vulnerability in a random generator, for example, an attacker can collect many signatures to recover the signature’s private key.</p><p>Thus, modular inversion in a threshold setting is inherently challenging. Since no single party should know the full nonce <em>k </em>in a threshold setting, the nonce must be generated collaboratively in a distributed manner.</p><p>Let us see how this can be done. Assume that each party <em>P_i </em>has a secret nonce share <em>k_i</em> and a mask <em>γ_i of k_i</em>. Let</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/438/1*Hx7MGhQa4ef75c2grDu8Dg.png" /></figure><p>where <em>S</em> represented signatories whose number is at least <em>t </em>and</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/363/1*qs5ZdB9NPPVE1vCbkYBHpQ.png" /></figure><p>and <em>δ_i </em>are Lagrangian coefficients.</p><p>Parties first jointly compute</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/331/1*YmwGRw04BX5I5nBGaoIlSA.png" /></figure><p>In the signing protocol, each part commits its public value <em>γ_i × G</em>, and so at<br>the end, they jointly calculate the inverse of <em>k </em>by multiplying the following values</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/313/1*T1B56i3kWSdWblK9sMLK1g.png" /></figure><p>At this point, how can every pair of signatories calculate <em>k_iγ_j and k_jγ_i </em>without disclosing their secrets <em>k </em>and <em>γ</em> ? This is solved by a protocol that helps to convert multiplicative shares into additive ones, the Multiplicative-to-additive share conversion protocol (MtA), [<a href="https://link.springer.com/content/pdf/10.1007/3-540-48405-1_8.pdf">Gil99</a>].</p><p>Given the multiplicative secrets<em> k_iγ_j </em>by MtA one can write additively</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/254/1*gf6ngd74cmR0VQqJhmYQ6Q.png" /></figure><p>where <em>α_ij</em> is the share of <em>P_i</em> and <em>β_ij</em> is the share of <em>P_j</em>. The same idea is applied to <em>kx</em>.</p><p>MtA protocol’s security depends on the use of the homomorphic encryption scheme. Since it is based on homomorphic encryption, it can be used with Pailler-based or class group-based encryption.<br>If Paillier encryption is used, like RSA, each party holds its own Paillier key. This key should be generated appropriately and verified for validity by other parties, which can be done using zero-knowledge range proof. Otherwise, if the Paillier key is not properly generated or verified, there’s a risk of exposing the private signing key, which could compromise the security of the entire threshold signature protocol, [<a href="https://eprint.iacr.org/2023/1234">MY23</a>]. Thus, a threshold ECDSA based on Paillier encryption needs many zero-knowledge proofs to show that each party’s Paillier key is correctly generated, that the encrypted values must be a given range, and that the encrypted value corresponds to a discrete logarithm of some known public value, like in [<a href="https://eprint.iacr.org/2020/492.pdf">CMP20</a>] and [<a href="https://eprint.iacr.org/2021/060.pdf">CGGMP</a>].</p><p>There are protocols like GG18, GG20, CMP, and CGGMP using a combination of Paillier encryption and threshold ECDSA. These protocols are typically designed to ensure security and correctness even if a small number of participants act maliciously, called a dishonest majority.<br>Paillier encryption efficiently hides the message <em>m ∈ Z_N</em>, where <em>N </em>is Pallier modulus, assuming that computing the <em>N </em>th residuosity classes of ciphertexts,<em> c mod N^2</em>, is hard, [<a href="https://www.researchgate.net/profile/Pascal-Paillier/publication/221348062_Public-Key_Cryptosystems_Based_on_Composite_Degree_Residuosity_Classes/links/56b35be808ae156bc5fb1f1f/Public-Key-Cryptosystems-Based-on-Composite-Degree-Residuosity-Classes.pdf">Pai99</a>]. The homomorphic property of Pailler encryption for any two messages <em>m</em>, <em>m′ ∈ Z_N </em>means that</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/689/1*KgTUkdiUGf1ogZV6vf5HYw.png" /></figure><p>Second, MtA can be used with class groups of imaginary quadratic fields, [<a href="https://eprint.iacr.org/2021/291.pdf">CCLST</a>]. In other words, encryption is done in a class group, which is a group of unknown order. Since class groups have an unknown order, threshold ECDSA protocols based on class group encryption eliminate the need for a trusted third party directly. Furthermore, as this signing protocol does not use the Paillier modulus, we avoid the necessity for the zero-knowledge proofs. Another advantage of this approach is that the message space is the same as the order of the elliptic curve, which further reduces the need for additional zero-knowledge proofs that should be used in a Paillier-based scheme, [<a href="https://info.fireblocks.com/hubfs/A_Note_on_the_Security_of_GG.pdf">MP21</a>].<br>Therefore, these aspects contribute to significantly lower communication<br>costs. Moreover, as noted in [<a href="https://eprint.iacr.org/2021/291.pdf">CCLST</a>], a class group-based scheme with the same security level significantly reduces bandwidth consumption compared to other approaches. However, since the signing protocol is based on a group of unknown orders, it is needed zero-knowledge proof for the correction of the encryption in this scheme.</p><h4>MtA (Multiplication to Addition)</h4><p>Threshold ECDSA protocols are based on a core protocol, Multiplication to Addition (MtA). MtA protocol as noted above, converts multiplicative shares into additive ones without revealing the shares and is based on homomorphic encryption. Thus, in this section, a Paillier or a class group-based encryption can be used for the encryption operation.</p><p>Let <em>S ⊆ [1..n]</em> be the set of players participating in the signature protocol<br><em>(|S| &gt; t). </em>Before the MtA, each party has a secret share of the private key (signing key). They randomly choose their secret share <em>x_i </em>from <em>F_q </em>.</p><p>Let each party <em>P_i </em>select a nonce share <em>k_i </em>and a mask <em>γ_i </em>in the finite field of order <em>q</em>. Define</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/295/1*RuUcvkpAKD_KG6_03CohmA.png" /></figure><p>Note that</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/189/1*lVlV1yAok3jodrMLcs2afw.png" /></figure><p>Each party commits the public value of <em>γi × G</em> at the beginning of MtA. This commitment is a non-malleable equivocable commitment, [<a href="https://eprint.iacr.org/2021/060.pdf">CGGMP</a>].<br>Every pair of signatories <em>P_i</em> and <em>P_j </em>engages in a multiplicative-to-additive<br>share conversion protocol for the shares <em>k_i </em>of the party <em>P_i </em>and <em>γ_j </em>of the party <em>P_j </em>and for the shares <em>k_j </em>of the party <em>P_j </em>and <em>γ_i </em>of the party <em>P_i.</em> Then, MtA protocol can create an additive form without revealing the multiplicative shares.</p><p>MtA protocol to calculate <em>k_iγ_j</em> securely as follows:</p><ul><li>Party <em>P_i </em>encrypts <em>k_i</em> with its Paillier public key: <em>Enc_i(k_i)</em>, and sends it to <em>P_j</em>.</li><li>Since <em>P_j </em>does not know the private key, it can not learn <em>k_i</em>. However, due to the homomorphic encryption, <em>P_j </em>can calculate the following with the public key of <em>P_i</em></li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/479/1*ZhiYKrZT3d-jSbeJUtOegw.png" /></figure><p>with a randomly chosen element <em>β_ij </em>in <em>F_q </em>. <em>P_j </em>sends the encrypted value to <em>P_i</em>.</p><ul><li><em>P_i </em>decrypts it modulo <em>q </em>and calls it</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/320/1*_l71xrmxu53AePTv2PQJVw.png" /></figure><p>where <em>α_ij </em>and <em>β_ji </em>are the shares output by the MtA protocol for player <em>P_i, </em>and <em>β_ij </em>is the share of<em> P_j. </em>Since <em>P_i </em>can not know <em>β_ij,</em> it can not learn<em> γ_j </em>also<em>.</em></p><ul><li>As can be seen, the sum of additive shares can be written as follows:</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/282/1*D-MS5krkc4CsaOosjT4AYg.png" /></figure><p>The protocol runs MtA between <em>P_i </em>and <em>P_j </em>so that the following additive shares are calculated:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/268/1*6Rb_Ow2r0VtfrfkNxPOd2g.png" /></figure><p>where <em>α_ij </em>and <em>β_ji </em>are shares of <em>P_i and α_ji </em>and <em>β_ij </em>are shares of <em>P_j.</em></p><p>Then <em>P_i</em> calculates</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/365/1*DpgttOojVtfQ4ccdPJWaOg.png" /></figure><p>so that <em>α_ij </em>and <em>β_ji </em>are shares of <em>P_i. </em>However<em>, P_i </em>does not know <em>β_ij, </em>thus the product of secrets<em> k_i γ_j (α_ij+</em> <em>β_ij mod q) </em>can be written as a sum of additive secret shares both from <em>P_i </em>and <em>P_j</em>.</p><ul><li>At the end of MtA, each <em>P_i </em>sends <em>δ_i </em>to all parties so that <em>kγ </em>can be calculated by the parties:</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/435/1*7oeFriRo9Dtso8fGFn-bUA.png" /></figure><p>The signing protocol for threshold ECDSA protocol also uses MtA to compute the additive shares of <em>kx</em>.<br>When MtA protocol runs, each party <em>P_i </em>has the following additive shares:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/604/1*Ve0AIc8MkBpsCKtedLO4qQ.png" /></figure><p>Using the public values, parties jointly compute</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/344/1*hIe0iBPK8l_GXmUIJlAs_g.png" /></figure><p>and</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/273/1*kgvPQSsZ9n_zd-RAxCc2-g.png" /></figure><p>Thus, when the message is known, each party <em>P_i </em>has signature shares</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/224/1*yIUKQ7gFCZmhxvkxntv-4A.png" /></figure><p>The signature will be</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/213/1*8dPKSOwZHmBZkRh1KupczQ.png" /></figure><h4>GG18 and GG20</h4><p>GG18 and GG20 are threshold ECDSA protocols created by Rosario Gennaro<br>and Steven Goldfeder, [<a href="https://eprint.iacr.org/2019/114.pdf">GG18</a>], and [<a href="https://eprint.iacr.org/2020/540.pdf">GG20</a>]. Both GG18 and GG20 are Paillier-<br>based threshold ECDSA protocols, [<a href="https://www.researchgate.net/profile/Pascal-Paillier/publication/221348062_Public-Key_Cryptosystems_Based_on_Composite_Degree_Residuosity_Classes/links/56b35be808ae156bc5fb1f1f/Public-Key-Cryptosystems-Based-on-Composite-Degree-Residuosity-Classes.pdf">Pai99</a>].</p><p>GG18 was the first protocol that supports <em>t ≤ n</em> threshold signatures with<br>no trusted third party, where t is the threshold and <em>n </em>is the number of parties. However, the communication cost of GG18 is high, namely 9 rounds for signing. <br>Thus, the authors design a fast protocol, GG20 with adding some crucial properties: noninteractive online signing and identifiable abort. If something goes wrong in an identifiable abort due to malicious intent or an unintentional mistake, who did it can be easily recognized and held accountable. GG20 is faster because most of the computations are done during the offline stage, when the message is known, parties only calculate one scalar multiplication in one round.</p><p>GG18 and GG20 schemes require each participant to prove that their<br>publicly disclosed <em>N </em>satisfies the square-free property. However, verifying square-freeness alone does not ensure that <em>N </em>is a valid Paillier modulus. If the Paillier modulus contains small prime factors, then the signature private key will be exploited. The attack done by the Fireblocks team which exploits the full private key by using only 16 signatures and the Chinese Remainder theorem, is called the 6ix1een attack, [<a href="https://eprint.iacr.org/2023/1234">MY23</a>]. Moreover, in the same paper, the Death by 1M cuts attack targets the old version of GG18 and GG20 where the beta parameter in MtA is chosen from <em>{1, …, N }</em> and again, Paillier modulus has small factors, [<a href="https://eprint.iacr.org/2023/1234">MY23</a>]. This attack also retrieves the private key again using relatively more signatures, depending on the number of signatories.</p><p>GG18 and GG20 use the MtA protocol and MtAwc (MtA with check). In<br>MtA, a party’s inputs are not verified, and in MtAwc a public value adds a<br>verification step with an abort. However, even if these protocols use some zero-knowledge proofs, MtA and MtAwc, in GG18 and GG20 are still vulnerable to an attack where the encrypted values of Paillier encryption are not in some range with proof, [<a href="https://info.fireblocks.com/hubfs/A_Note_on_the_Security_of_GG.pdf">MP21</a>]. Although this attack does not lead to the exposure of the full private key, it must still be regarded as a serious security concern. As a result, in [<a href="https://info.fireblocks.com/hubfs/A_Note_on_the_Security_of_GG.pdf">MP21</a>] the authors of CGGMP add zero-knowledge range proof for the parameters used in MtA.</p><p>In the latest attack article about the threshold ECDSA protocol based on Paillier encryption, it is stressed that MPC-CMP and CGGMP protocols with zero-knowledge range proofs for checking those values have no vulnerabilities, [<a href="https://eprint.iacr.org/2023/1234">MY23</a>].</p><h4>MPC-CMP and CGGMP</h4><p>Fireblock uses MPC CMP as a threshold signature algorithm. It has an open-source code, so everyone can check that the protocol is mathematically safe and sound. CGGMP protocol’s key generation is a 3-round protocol. Instead of Feldmann VSS like in GG18 and GG20, each party proves by Schnorr’s zero-knowledge proof that it knows the secret signing private key share.<br>Key-Refresh and auxiliary information is a 3-round protocol. Auxiliary in-<br>formation means each party has a correct Paillier modulus and Ring Pedersen parameters. In this stage, due to the mentioned attacks, parties must prove that the Paillier modulus is a Paillier Blum modulus, and can be factored into exactly two prime factors which are not small, [<a href="https://eprint.iacr.org/2023/1234">MY23</a>].</p><p>Another zero-knowledge proof is for a generation of valid ring Pedersen<br>parameters. As in the key generation process, the refreshed key is needed a<br>Shnorr’s proof of knowledge. Also, it is checked that the modulus for Paillier and ring Pedersen is bigger than a bound given in [<a href="https://eprint.iacr.org/2021/060.pdf">CGGMP</a>]. In this protocol, they use ephemeral values for the validity of the secret signing key share for each signing operation. Finally, in the key refresh, parties check the sum of public key shares is zero. For these, they can abort a corrupted party easily. <br>However, to reach this feature they must use quite a few zero-knowledge proofs. MPC-CMP provides a non-interactive signing capability even in the presence of an adversary that adaptively corrupts up to <em>t = n − 1</em> signatories.</p><p>MPC CMP is analyzed within the Universally Composable (UC) Security<br>framework, [CMP20]. The protocol achieves an ideal threshold signature functionality within the UC framework, operating in the global random oracle model. Its security is based on the Strong RSA assumption, the semantic security of Paillier encryption, and a slightly enhanced version of existential unforgeability for ECDSA, [<a href="https://eprint.iacr.org/2020/492">CMP20</a>].<br>The authors of two independent works, GG20 and CMP, collaborated on<br>a paper CGGMP that has enhanced the CMP protocol lately. CGGMP features a key refresh mechanism. For the key refresh phase, the authors use DH-style encryption because it is more efficient than Paillier and its security proof is much more easier under DDH assumption, [<a href="https://eprint.iacr.org/2021/060.pdf">CGGMP</a>]. In addition, due to the Paillier commitment and a noninteractive zero-knowledge proof, parties are confident that their output is well formed at the end of the pre-signing phase.</p><h4>CCLST 2023</h4><p>The ideal class group (or class group) of an algebraic number field K is the<br>quotient group<em> C = JK/PK </em>where <em>JK </em>is the group of fractional ideals of the<br>ring of integers of <em>K</em>, and <em>PK</em> is its subgroup of principal ideals, [<a href="https://www.sciencedirect.com/science/article/abs/pii/S0304397522006004?via%3Dihub">CCLST</a>]. In<br>CCLST, it is formalized that a group exists in which the decisional Diffie-Hellman problem is hard, whereas it contains a subgroup in which the discrete logarithm problem is easy. And it is denoted by a DDH Group <em>G = ⟨g⟩</em> with an easy DL Subgroup <em>F = ⟨f ⟩, </em>[<a href="https://www.sciencedirect.com/science/article/abs/pii/S0304397522006004?via%3Dihub">CCLST</a>]. Also, they proposed a linearly homomorphic encryption scheme, called CL framework, that relies upon such a group and the authors prove its security. The encryption for a message <em>m </em>is given by</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/286/1*EXQ4Sk62_CVdmsuNd6VfHg.png" /></figure><p>for a random <em>r</em>, the public key <em>pk </em>is <em>h</em>.</p><p>CL framework is semantically secure under chosen plaintext attacks (ind-cpa). The ind-cpa security relies on the HSM (Hard Subgroup membeship assumption), [<a href="https://doi.org/10.1016/j.tcs.2022.10.016">CCLST</a>]. Another assumption for the security of this protocol is the low-order element assumption which improves the efficiency of the zero-knowledge proofs needed in the protocol. The third assumption is the strong root assumption similar to the Strong RSA assumption. For strong RSA, this involves factoring the modulus. The strong root problem in class groups requires computing the class number, for which the best-known algorithms have worse complexity compared to integer factorization algorithms.</p><p>To put it more briefly and clearly, a DDH group with an easy DL subgroup exists in the class group of imaginary quadratic fields, and it allows us to create a linearly homomorphic encryption scheme, that is why this encryption can be used in MtA.</p><p>In more detail,in the key generation phase of the threshold ECDSA scheme, parties generate jointly <em>g_q</em> whose order is unknown to all parties. Then they generate the group generator</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/105/1*PIq5iuj3phIKvPH2sTY6YA.png" /></figure><p>for a DDH group <em>G </em>where <em>f </em>is the generator of <em>F, </em>a DL subgroup of G<em>, </em>[CCLST]. After the group is generated, the parties independently create their encryption key pairs</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/211/1*ASWhhwpSVnNpNuG2JBRqnQ.png" /></figure><p>Then they collaboratively generate the signing key pairs using Feldman VSS and Shamir Secret sharing, [<a href="https://medium.com/@oznurmut/distributed-key-generation-protocols-on-private-communication-model-279743dd6b32">DKG</a>].</p><p>The signing protocol proposed by Castagnos et al. closely follows the structure of GG20 substituting Paillier encryption with the class group encryption.</p><p>As mentioned, since the message space is the same as the order of the elliptic curve <em>q, </em>the MtA<em> </em>protocol does not need zero-knowledge proof<em> </em>which exists for MPC CMP and CGGMP. This yields a significant bandwidth improvement. However, as it is used a class group of unknown order, the protocol must include zero-knowledge proofs to ensure the correctness of the encryptions.</p><p>To identify a corrupted party, or for identifiable abort, the protocol employs the same approach as outlined in the GG20 protocol. However, due to the class-group-based encryption, they need to design new zero-knowledge proofs that enable the simulator to complete the proof successfully without compromising the overall efficiency of the protocol.</p><p>In the latest update of class group-based threshold ECDSA, many features<br>are added by the authors, [<a href="https://doi.org/10.1016/j.tcs.2022.10.016">CCLST</a>]. The protocol is a noninteractive, maliciously secure, full-threshold ECDSA protocol. It has identifiable aborts, adaptive security for <em>t = n−1</em>, and proactive security.</p><p>Last but not least, the authors achieve their goal that the protocol improves upon existing Paillier-based implementations, achieving similar objectives while reducing bandwidth consumption by a factor of up to 10, [<a href="https://doi.org/10.1016/j.tcs.2022.10.016">CCLST</a>].</p><h3>To Sum Up</h3><p>All threshold signature schemes -GG18, GG20, CMP, CGGMP, and CCLST-<br>operate under the assumption of a dishonest majority. All schemes mentioned so far can be adapted to a protocol without a trusted third party. Thus, each party generates its own secret share, functioning both as a dealer and as a recipient in the key generation process for the ECDSA signature algorithm.</p><p>GG18, GG20, and CCLST use distributed key generation methods: Feldman<br>Verifiable Secret Sharing (VSS) and Shamir Secret Sharing, to generate the<br>signature private key. In the CMP and CGGMP, each party generates its secret shares and uses Schnorr’s proof to verify knowledge of the secret share associated with their public share.<br>As mentioned above there are two kinds of encryption in threshold signature protocol: one is based on Paillier encryption and the other is based on class groups of imaginary quadratic fields.</p><p>For the Paillier encryption, the Paillier modulus must be chosen properly.<br>An attack proposed by the Fireblocks team demonstrates practical exploitation of the private key, [MY23]. There is no mechanism in GG18 and GG20, like a range-proof check, for detecting small factors of <em>N </em>(factors of size <em>2⁸⁰ </em>or smaller are considered critical vulnerabilities) and it is the product of exactly two primes. <br>Therefore, when generating a new Paillier (RSA) modulus <em>N</em>, the following zero-knowledge range proofs must be provided to verify</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/719/1*Ed3UuwKEvO4HncC9ASU74w.png" /></figure><p>While threshold ECDSA signature schemes provide enhanced security, they<br>may still be vulnerable to evolving attacks. Consequently, either the signature keys or encryption keys could be at risk of compromise over time. To achieve proactive security parties periodically engage in a key-refresh protocol. This approach helps maintain security over time by refreshing keys without changing the public key, thus preventing gradual leakage and ensuring the protocol remains secure against long-term threats.<br>CMP and CGGMP include a periodic key refresh mechanism, resulting in<br>full proactive security, [<a href="https://eprint.iacr.org/2020/492.pdf">CMP20</a>] and [<a href="https://eprint.iacr.org/2021/060.pdf">CGGMP</a>]. CCLST also adds a key refresh mechanism for the full threshold, <em>t = n − 1</em> in the latest version of the paper, [<a href="https://doi.org/10.1016/j.tcs.2022.10.016">CCLST</a>].</p><p>In the CCLST scheme, the key setup/refresh explicitly requires parties to<br>generate new encryption key pairs, namely each party <em>P_i </em>generates the public key share</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/63/1*wPnUE7gsyKTIZ6vfFx9KjQ.png" /></figure><p>where <em>g </em>is public, [<a href="https://eprint.iacr.org/2021/291.pdf">CCLST</a>].<br>Thus, since there is no need to generate a new key or refresh key, the CCLST key setup/refresh protocol works much faster. It is given that for <em>n = 5</em> and a <em>112</em>-bit level of security, the total data sent and received between players in the key refresh protocol is 15 times less than one in CGGMP, [<a href="https://eprint.iacr.org/2021/291.pdf">CCLST</a>].<br>To minimize computational costs, protocols with the latest updates implement a presigning or offline signing stage after the key setup/refresh stage. After these steps, when the message is available, parties non-interactively compute the signature shares and broadcast this share to all signatories. This stage takes only one round to complete the signing.<br>Another important thing in threshold cryptography is accountability. A<br>threshold signature protocol achieves accountability by identifying corrupted signatories in case of failure to generate a valid signature. It is called identifiable abort in [<a href="https://eprint.iacr.org/2021/060.pdf">CGGMP</a>], [<a href="https://eprint.iacr.org/2020/540.pdf">GG20</a>] and [<a href="https://eprint.iacr.org/2021/291.pdf">CCLST</a>].</p><p>Now we are ready to list the properties of each threshold ECDSA scheme.</p><blockquote>GG18<br>• Multiparty signatures for any t ≤ n.<br>• Dishonest majority<br>• Paillier-based encryption<br>• Security assumptions: DDH and Strong RSA assumptions, [<a href="https://eprint.iacr.org/2019/114.pdf">GG18</a>]<br>• Static adversaries ( the adversary must choose which players to corrupt at the beginning of the protocol. )<br>• Key generation: Feldman VVS and Shamir SS<br>• MtA share conversion protocol.<br>• Non-malleable equivocable commitments, [<a href="https://eprint.iacr.org/2019/114.pdf">GG18</a>].<br> 1. Key generation: 3 rounds<br> 2. Signing: 9 rounds</blockquote><blockquote>GG20<br>• The successor to GG18.<br>• A non-interactive threshold ECDSA protocol: when the message is known, only one noninteractive round for signing.<br>• Multiparty signatures for any t ≤ n.<br>• Dishonest majority.<br>• Paillier-based encryption.<br>• Security assumptions: Enhanced ECDSA, DDH, strong RSA.</blockquote><blockquote>• Static adversaries and rushing adversaries (the adversary gets to speak last<br>in a given round and, in particular, can choose his message after seeing<br>the honest parties’ messages. )<br>• Key generation: Feldman VSS and Shamir’s SS.<br>• MtA conversion protocol.<br>• Non-malleable equivocable commitments.<br>• Identifiable abort, both in key generation and signing.<br>• Rounds:<br>1. Key generation: 3 rounds,<br>2. Signing: 7 rounds (including 1 online)</blockquote><blockquote>MPC CMP<br>• A non-interactive threshold ECDSA protocol.<br>• Multiparty signatures for any t ≤ n.<br>• Dishonest majority.<br>• Paillier-based encryption.<br>• Security analysis in the UC framework.<br>• Security assumptions: Strong RSA, semantic security of the Paillier encryption, and enhanced ECDSA.<br>• Static adversaries for t &lt; n and adaptive adversaries for t = n − 1.<br>• A key refresh mechanism.<br>• Full proactive security.<br>• The MtA share conversion protocol.<br>• Paillier as non-malleable equivocable commitment<br>• Ring Pedersen commitments<br>• Rounds:<br>1. Key generation : 3 rounds<br>2. Auxiliary Info. &amp; Key Ref: 2 rounds<br>3. Signing: 3 rounds presigning + 1 round online signing.</blockquote><blockquote>CGGMP<br>• Joint work of the authors of GG20 and CMP.<br>• A non-interactive threshold ECDSA protocol.<br>• Multiparty signatures for any t ≤ n.<br>• Dishonest majority.<br>• Paillier-based encryption.<br>• Security analysis in the UC framework.<br>• Adaptive adversaries for t = n − 1.<br>• Identifiable abort.<br>• Online/Noninteractive signing.<br>• Key refresh mechanism.<br>• Proactive security.<br>• Security assumptions: Strong RSA, DDH, enhanced ECDSA.<br>• Static adversaries for t &lt; n and adaptive adversaries for t = n − 1 as long as at least one party remains uncorrupted between any two consecutive key .<br>• Full proactive security.<br>• MtA share conversion protocol based on Paillier and zero-knowledge range proofs.<br>• Paillier as non-malleable equivocable commitment<br>• Ring Pedersen commitments.<br>• Rounds:<br> 1. Key generation: 3 rounds.<br> 2. Auxiliary Info. &amp; Key Ref: 3 rounds<br> 3. Signing: 3 rounds presigning + 1 round online signing</blockquote><blockquote>CCLST<br>• A noninteractive threshold ECDSA protocol.<br>• Multiparty signatures for any t ≤ n.<br>• Dishonest majority.<br>• Class group-based encryption.<br>• Provable security. Simulation-based and game-based proofs.<br>• Adaptive security for t = n − 1 and proactive security.<br>• Identifiable abort .<br>• Key generation: Feldman VSS and Shamir’s SS<br>• Non-interactive signing.<br>• Key refresh mechanism.<br>• Security assumptions: Hard subgroup membership assumption, the low-order assumption, and a strong root assumption for class groups.<br>• MtA share conversion protocol.<br>• Non-malleable equivocable commitments<br>• Rounds:<br>1. Setup (threshold computation of the group generator ): 5<br>rounds,<br>2. Key generation: 4 rounds,<br>3. Key refresh: 3 rounds,<br>4. Signing : 6 +1 (online round)</blockquote><p>An approximate communication cost of these schemes is given as a Figure in [<a href="https://eprint.iacr.org/2021/060.pdf">CGGMP</a>]. In parentheses below, it is provided concrete estimates given in [<a href="https://eprint.iacr.org/2021/060.pdf">CGGMP</a>] for the curve secp256k1 (i.e., the Bitcoin curve and<em> q = 256</em>) and <em>log(N ) = 2048 </em>for 112-bit security for Paillier.<br>GG18: 43520 bits ( 7 KiB)<br>Class group-based threshold ECDSA: 25600 bits (3.5 KiB)<br>CGGMP: 119040 bits (15 KiB)</p><h3>Conclusion</h3><p>GG18 and GG20 are implemented by various vendors and open-source projects, such as Binance bnb-chain, ING Bank (open source project), ZenGo (open source project), and Safeheron, [<a href="https://eprint.iacr.org/2023/1234">MY23</a>]. The protocols are vulnerable to some attacks mentioned above. The issue arises from the absence of correct generation and validity checks for the Paillier modulus and the parameters used in the MtA share conversion protocol. As a result, when custody uses them, they need proof to verify the Paillier modulus and the parameters used in MtA like in [<a href="https://eprint.iacr.org/2021/060.pdf">CGGMP</a>].</p><p>In CMP and CGGMP protocols, such vulnerabilities have been addressed using zero-knowledge range proofs. However, employing a large number of range proofs significantly increases communication costs.</p><p>To minimize bandwidth consumption and reduce the overhead introduced by zero-knowledge range proofs, an alternative method based on class group encryption has been proposed.</p><p>Although reducing bandwidth consumption is advantageous, class group-based homomorphic encryption relies on highly complex mathematics. On the other hand, threshold signature schemes using Paillier encryption are more straightforward to implement, as they primarily involve relatively simple modular arithmetic.</p><p>References:</p><p>[Gil99] Niv Gilboa. “Two Party RSA Key Generation”. In: Advances in<br>Cryptology — CRYPTO ’99.</p><p>[Pai99] Pascal Paillier. “Public-Key Cryptosystems Based on Composite<br>Degree Residuosity Classes”. In: Advances in Cryptology — EURO-<br>CRYPT ’99.</p><p>[CL15] Guilhem Castagnos and Fabien Laguillaumie. “Linearly Homomor-<br>phic Encryption from DDH”. In: IACR Cryptol. ePrint Arch. (2015).</p><p>[GG18] Rosario Gennaro and Steven Goldfeder. “Fast Multiparty Thresh-<br>old ECDSA with Fast Trustless Setup”. In: Proceedings of the 2018<br>ACM SIGSAC Conference on Computer and Communications Secu-<br>rity, CCS 2018.</p><p>[Ara+20] Diego F. Aranha et al. “LadderLeak: Breaking ECDSA with Less<br>than One Bit of Nonce Leakage”. In: CCS ’20: 2020 ACM SIGSAC<br>Conference on Computer and Communications Security, Virtual Event,<br>USA.</p><p>[CMP20] Ran Canetti, Nikolaos Makriyannis, and Udi Peled. “UC Non-Interactive,<br>Proactive, Threshold ECDSA”. In: IACR Cryptol. ePrint Arch. (2020).</p><p>[GG20] Rosario Gennaro and Steven Goldfeder. “One Round Threshold ECDSA with Identifiable Abort”. In: IACR Cryptol. ePrint Arch. (2020).</p><p>[CGGMP] Ran Canetti Rosario Gennaro Steven Goldfeder Nikolaos Makriyannis Udi Peled. “UC Non-Interactive, Proactive, Threshold ECDSA<br>with Identifiable Aborts”. In: CCS ’20: 2020 ACM SIGSAC Conference on Computer and Communications Security, Virtual Event, USA.</p><p>[MP21] Nikolaos Makriyannis and Udi Peled. A Note on the Security of<br>GG18. 2021.</p><p>[MY23] Nikolaos Makriyannis and Oren Yomtov. “Practical Key-Extraction<br>Attacks in Leading MPC Wallets”. In: IACR Cryptol. ePrint Arch. (2023).</p><p>[CCLST] Guilhem Castagnos Dario Catalano Fabien Laguillaumie Federico<br>Savasta Ida Tucker. “Bandwidth-efficient threshold EC-DSA revisited: Online/offline extensions, identifiable aborts proactive and adaptive security”. In: Theor. Comput. Sci. 939 (2023).</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e7af8cad1992" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Distributed Key Generation Protocols]]></title>
            <link>https://medium.com/@oznurmut/distributed-key-generation-protocols-on-private-communication-model-279743dd6b32?source=rss-c6c2e75355b8------2</link>
            <guid isPermaLink="false">https://medium.com/p/279743dd6b32</guid>
            <dc:creator><![CDATA[Öznur Mut Sağdıçoğlu]]></dc:creator>
            <pubDate>Thu, 25 Jan 2024 17:22:56 GMT</pubDate>
            <atom:updated>2024-01-29T16:31:10.657Z</atom:updated>
            <content:encoded><![CDATA[<p>A set of <em>n</em> parties uses distributed key generation (DKG) protocols<br>to generate a secret key without needing a third party. The important feature is that the secret key is not computed, reconstructed, or stored in a single location.</p><p>DKG protocols are the main component of threshold cryptosystems. For<br>the threshold cryptosystems, unless an adversary compromises parties whose number is more than a certain threshold, the secret key remains secure and is reconstructed jointly by the parties for creating a signature or decryption purposes.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*vgbQp0Yq9RNK3dhziiIouQ.png" /></figure><p>We assume that the parties are connected with a private point-to-point channel. In addition, the parties have access to a dedicated broadcast channel. A malicious adversary can corrupt parties to divert from the specified protocol in any way. Moreover, we assume that an adversary can corrupt at most<em> t </em>of the <em>n </em>parties in a network such that <em>t &lt; n/2.</em></p><p>For a DKG protocol <em>n </em>parties<em> P1, …, Pn</em> generate a key pair, public and<br>secret key, denoted by <em>(pk, sk)</em>, such that <em>t + 1</em> honest party can reconstruct the secret key but never get the secret key with less. Thus, they create <em>n </em>secret key shares <em>sk1, sk2, …, skn</em> so that the party <em>Pi </em>owns the secret share <em>ski </em>and other parties do not know this value. With a DKG protocol without sharing <em>ski </em>values,<em> t + 1 </em>parties reconstruct the secret key <em>sk</em>.</p><p>The security of a DKG is defined in <a href="https://doi.org/10.1007/s00145-006-0347-3">[Gen+07]</a>. A secure DKG with threshold <em>t</em> satisfies correctness and secrecy. For correctness, any subset of <em>t + 1</em> shares provided by honest parties defines the same unique secret key. Secondly, all honest parties have the same value of public key. For secrecy, no information about the secret key can be learned by the adversary except the related public key. In addition to these, when we talk about the security of a DKG we also note that the secret key must be uniformly distributed.</p><p>During DKG protocols, parties may face some problems, we talk about two of them. First, if one secret key share or more is lost or stolen, or in other words, parties lose their secret shares, is it still possible to reconstruct the secret key?</p><p>During a DKG protocol, parties send some values (public or committed values), and these public values are used to reconstruct the secret key at the end of the protocol. If these values are not correct, the secret key is never reconstructed. Thus, the second question is how parties can be sure that the values sent by other parties are valid.</p><p>For the first question, Shamir’s secret sharing (<a href="https://doi.org/10.1145/359168.359176">SSS</a>) scheme is proposed<br>by Adi Shamir. Using SSS, we may define a DKG where each party becomes a dealer. Lost or stolen secret shares can be replaceable in a DKG based on SSS. However, when it comes to a DKG based on SSS, parties can not be sure whether the values sent by the other party during the protocol are valid or not. Thus, for the second question or verifiability of public shares or committed values sent during a DKG protocol, many verifiable secret sharing schemes are proposed, [<a href="https://link.springer.com/content/pdf/10.1007/3-540-46766-1_9.pdf">Ped91]</a>, <a href="https://doi.org/10.1007/s00145-006-0347-3">[Gen+07]</a>, and <a href="https://doi.org/10.1002/sec.1651">[NSR16]</a>.</p><h3>Shamir’s Secret Sharing (SSS) Scheme</h3><p>Shamir’s secret sharing is a threshold scheme based on polynomial interpolation over finite fields. Among <em>n </em>parties the secret key <em>sk </em>is shared, so that <em>t + 1</em> of shares can reconstruct <em>sk</em>, but knowledge of <em>t</em> or fewer shares is not enough to reconstruct <em>sk</em>. The dealer chooses random field elements <em>a1, a2, …, at</em> and construct the polynomial</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/610/1*V-tZ9U5VNbMhFmKMDz89Vg.png" /></figure><p>Since it is a secret-sharing scheme, a dealer prepares secret shares for parties. The dealer prepares the values <em>(i, f (i))</em> and sends them to each party <em>Pi</em> through a private channel for <em>i = 1, 2, …, n</em>. Each party <em>Pi </em>has only one point <em>(i, f (i))</em>, and does not learn anything about the other party’s share <em>(j, f (j)) </em>for i is different from j. Given any subset of <em>t + 1</em> shares the secret can be constructed using <a href="https://en.wikipedia.org/wiki/Polynomial_interpolation">polynomial interpolation</a>. This is the fact that it takes <em>t+1</em> points to define a polynomial of degree <em>t</em> uniquely. For example, only one line can be drawn between two points, but an infinite number of lines can be through a point.</p><p>Now, if secret shares are lost or stolen, the dealer sends a new share (i.e., a<br>new point for the polynomial) without changing the secret and without hurting the secrecy of other parties’ shares in SSS. Moreover, a malicious party with less than<em> t + 1 </em>shares can not obtain the secret even if it has unlimited computational power. Therefore, SSS is called information-theoretically secure.</p><p>However, Shamir’s Secret Sharing resists passive attacks only. Namely, the dealer can share non-valid shares with the parties or the parties may contribute incorrect shares during the secret key reconstruction. As a result of this, the secret key is never reconstructed. Therefore, the public shares need to be verified by the parties.</p><p>Although a DKG based on SSS is an answer for stolen or lost shares and is<br>a good choice for information-theoretic security, the validity of public values can not be checked during the protocol. For this, many verifiable secret-sharing schemes are defined for DKG protocols, <a href="https://ieeexplore.ieee.org/document/4568164">[Cho+85]</a>, <a href="https://doi.org/10.1109/SFCS.1987.4">[Fel87]</a>, and [<a href="https://link.springer.com/content/pdf/10.1007/3-540-46766-1_9.pdf">Ped91]</a>.</p><h3>DKG protocols based on verifiable secret sharing</h3><p>Let the computation model be composed of a set of <em>n</em> parties <em>P1, …, Pn</em>. They are connected by private channels. In addition, the parties have access to a dedicated broadcast channel. Let <em>p </em>and <em>q </em>be primes such that <em>q </em>is a large prime dividing <em>p − 1</em> and <em>g </em>is the generator of the subgroup</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/214/1*2gLuVWPWLVQFQHjZHASzDg.png" /></figure><p>of order<em> q</em>.<br>The first DKG based on a verifiable secret-sharing scheme JF-DKG was introduced by Pedersen in 1991, [<a href="https://link.springer.com/content/pdf/10.1007/3-540-46766-1_9.pdf">Ped91]</a>.</p><p><strong>The Joint Feldman Distributed Key Generations (JF-DKG)</strong></p><p>Pedersen proposed a DKG protocol for discrete log-based cryptosystems based on Feldman’s verifiable secret sharing, <a href="https://doi.org/10.1109/SFCS.1987.4">[Fel87]</a> and [<a href="https://link.springer.com/content/pdf/10.1007/3-540-46766-1_9.pdf">Ped91]</a>.<br>The JF-DKG works as follows:</p><ol><li>Each party <em>Pi</em> prepares a polynomial</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/830/1*w_JO-7_Psqmamlr7bOe1iQ.png" /></figure><p>where the constant term is the secret share <em>ski </em>of <em>Pi</em></p><p>2. <em>Pi </em>sends share <em>fi(j)</em> on a private channel to each party <em>Pj</em> .<br>3. <em>Pi </em>prepares a public commitment that contains the coefficients of the<br>polynomial <em>fi</em>. That is, <em>Pi </em>broadcasts</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Wa_oEHLhxOsap3_iytr9kg.png" /></figure><p>4. <em>Pj </em>verifies the share <em>fi(j)</em> sent by <em>Pi </em>by checking the following equation:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/415/1*Y9NHiDMX5OGXIA3q0U1M1A.png" /></figure><p>Since</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/400/1*iN9NTG5P8TnTzs8oXrFg_Q.png" /></figure><p>the equality holds for an honest party.</p><p>5. If (*) does not hold, <em>Pj </em>broadcasts a complaint against <em>Pi</em>.<br> (a) If more than <em>t</em> parties complain against a party <em>Pi</em>, that party is<br>disqualified.<br> (b) Otherwise, <em>Pi </em>broadcasts its share<em> fi(j)</em>.<br> • If <em>fi(j)</em> is not verified again, <em>Pi </em>will be disqualified.<br>6. Let the set <em>QUAL </em>be the set of non-disqualified parties.<br>7. After this elimination, assume that there remain <em>m </em>non-disqualified parties <em>P1, …, Pm, |QU AL| = m</em>. Since among <em>n </em>parties, it is allowed to have at most <em>t &lt; n/2</em> corrupt parties, we may assume that <em>m ≥ t + 1</em>.<br>8. The public key is computed from non-disqualified parties</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/276/1*BHDFUeUvbxeSDULr_Qu0nQ.png" /></figure><p>9. Each party <em>Pi </em>sets his share</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/326/1*6n5iP_Cs4zpmo_3XKpYCQw.png" /></figure><p>10. Each party <em>Pi </em>prepares the public verification values</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/320/1*ZpPnzpdfyeLVJegK-YxjFQ.png" /></figure><p>Note that</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/103/1*oZ2Awf0844tzVPW4OC2F6g.png" /></figure><p>11. Each party <em>Pi </em>sends his share <em>si </em>along with his public verification values<br>so that each non-disqualified party can check <em>Pi’s </em>share</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/331/1*I-SRx0xvG3iOrrNPWlSmNA.png" /></figure><p>(a) If this check fails, <em>Pi </em>is eliminated. But since there are at least <em>t + 1</em><br>honest parties, the secret key can be reconstructed.<br>12. Among the set of non-disqualified parties, any<em> t + 1</em> parties reconstruct<br>the private key <em>sk </em>using the interpolation of degree <em>t </em>polynomial</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/372/1*c1jiJMZYEddq3aBRIPLSKg.png" /></figure><p>where <em>m </em>is the number of parties after Step 11.<br>13. The secret shared key <em>sk </em>is not computed by any party, but it is equal to</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/669/1*JYiXHb-TPiXNkIeYF-vzGg.png" /></figure><h3>Security of JF-DKG</h3><p>JF-DKG does not guarantee a uniformly random distribution of generated keys. This attack was found by Gennaro et al,<a href="https://doi.org/10.1007/s00145-006-0347-3"> [Gen+07]</a>. In the attack, an adversary corrupts only two parties, say <em>P1 </em>and <em>P2</em>. Using two parties he can control the last bit of the public key <em>pk</em>.<br>This can be done as follows. Let<em> α = y1y2…yn</em> and <em>β = y2y3…yn</em> where</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/556/1*1UTizhpK7bBBWngC-CZN7w.png" /></figure><p>public key shares of the parties.<br>The adversary checks the last bit of <em>α.</em> If the last bit of <em>α</em> is zero, then the party <em>P1 </em>follows the protocol and it is not disqualified. Otherwise, the adversary makes <em>P2 </em>have a complaint about the party <em>P1</em>, and <em>P1 </em>broadcasts an inconsistent share.<br>Therefore, <em>P1 </em>will be disqualified. This makes the public key value <em>y </em>to <em>β </em>which ends with zero with probability <em>1/2</em>. Thus an adversary makes the last bit of the public key <em>pk </em>zero with probability <em>3/4 </em>rather than <em>1/2</em>.<br>Since</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/107/1*v5dk_3h26-lK2Q27Xp8syg.png" /></figure><p>the adversary also makes the private key’s distribution nonuniform.<br>This attack can be done because an adversary can see all public key shares<br>during the non-disqualified party selection. Thus, we can avoid this situation in two ways. One way is to hide the public key share during the preparation of <em>QUAL </em>set, as a result of this, an adversary can not affect the distribution of keys. Another way is that after the set <em>QUAL </em>is selected, we can use a different group element to construct the public key. Thus, an adversary can not affect the distribution of the newly generated public key and so the secret key. These two ideas are applied in the following two protocols, <a href="https://doi.org/10.1007/s00145-006-0347-3">[Gen+07] </a>and <a href="https://doi.org/10.1002/sec.1651">[NSR16]</a>.</p><h3>Gennaro et al.’s DKG</h3><p>Gennaro et al prepare a DKG that securely distributes commitment values<br>so that the public key can not be captured by the adversary, <a href="https://doi.org/10.1007/s00145-006-0347-3">[Gen+07]</a>. This<br>protocol is based on Pedersen’s verifiable secret sharing and Feldman’s verifiable secret sharing protocols, <a href="https://doi.org/10.1109/SFCS.1987.4">[Fel87]</a> and [<a href="https://link.springer.com/content/pdf/10.1007/3-540-46766-1_9.pdf">Ped91]</a>.<br>Pedersen’s VSS protocol is unconditionally secure. It means that an adversary can not learn anything about the public share value by looking at the shared values even if he has unbounded computational power. Thus, in the first phase of the protocol, Pedersen’s VSS is used to hide public key shares, and the set of non-disqualified parties is selected in a perfectly secure way. In other words, since an adversary can not see public key shares, he can not make Gennaro et al’s attack in this case, <a href="https://doi.org/10.1007/s00145-006-0347-3">[Gen+07]</a>.<br>Gennaro et al. DKG works as follows:<br>1. Each party <em>Pi </em>chooses two random degree t polynomial</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/635/1*PJA-uuhS8rOy6b9oM7hCIQ.png" /></figure><p>where the constant term of <em>fi </em>is the secret share of <em>Pi.</em></p><p>2. Each party <em>Pi </em>computes shares</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/433/1*jcASgwb6FV-SxZszzQ25Sw.png" /></figure><p>and sends secretly to each party <em>Pj </em>.<br>3. Each party <em>Pi </em>broadcasts the commitment</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/765/1*SGBSOG3UZCf4mMk3xyU1kw.png" /></figure><p>4.Each party <em>Pj </em>validates its shares <em>sij</em> and <em>s′ij</em> from a party <em>Pi </em>by checking<br>the following equality</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/404/1*sC9CfWPS098uIiTslfyPQw.png" /></figure><p>5. If (***) does not hold, <em>Pj </em>publishes a complaint about <em>Pi</em>.<br> (a) If more than <em>t </em>parties complain against <em>Pi</em>, that party is disqualified.<br> (b) Otherwise, Then <em>Pi </em>broadcasts its shares <em>sij </em>and <em>s′ij</em> .<br>• If revealed shares in (***) are not verified again, <em>Pi </em>will be disqualified.<br>6. Each party now has a set <em>QUAL </em>of non-disqualified parties.<br>7. Each party <em>Pi</em> sets his share of the secret as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/559/1*_eKcK8Snbc9bgdoLsQP2yA.png" /></figure><p>8. The secret key is</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/276/1*rNSy2A4sBkTXSM8i_jhGKw.png" /></figure><p>9. Now each party <em>Pi </em>in <em>QUAL </em>exposes <em>yi </em>to construct the public key. Also<br><em>Pi </em>broadcasts <em>Aik </em>where</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/580/1*SHPGtYma9aI-oNqqI-LHOQ.png" /></figure><p>10. Each party <em>Pj </em>verifies the public key shares</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/356/1*j9LXKBPywuWy2SVkbRPmcw.png" /></figure><p>a) If the check fails, <em>Pj </em>complains against <em>Pi </em>by broadcasting the values<br><em>sij </em>and <em>s′ij</em> , that satisfy (***) but do not satisfy (****).<br>11. For players <em>Pi </em>who receive at least one valid complaint in Step 10, the<br>other players run the reconstruction phase and get the secret share of <em>Pi</em>,<br><em>fi </em>and <em>Ai0, Ai1, …, Ait</em>. This can be done by the parties in <em>QUAL </em>since<br>we assume that there are at least <em>t + 1 </em>honest parties.<br>12. For all players <em>Pi </em>in <em>QUAL</em>, set</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/239/1*hIzNxyWW3vyRy6U-jaParw.png" /></figure><p>Compute</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/262/1*_58TgAG607blD3l-lB4Jjg.png" /></figure><p>13. sk can be computed from the polynomial</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/171/1*vl-Pu1fX_Xwgr81D-6-jBQ.png" /></figure><p>by using <a href="https://en.wikipedia.org/wiki/Polynomial_interpolation">polynomial interpolation</a>.<br>JF-DKG involves only one round of communication and one round of complaint management phase.<br>Although Gennaro et al.’s DKG ensures that keys are distributed uniformly,<br>it has two rounds of communication and two rounds of complaint management phase. Moreover, Gennaro et al.’s DKG uses two polynomials for commitments. Thus, this scheme comes with a computational load.</p><p>There is another solution for the Gennaro et al. attack by Neji et al., called the Extended version of JF-DKG <a href="https://doi.org/10.1002/sec.1651">[NSR16]</a>.</p><h3>The Extended Version of JF-DKG</h3><p>The extended version of JF-DKG is similar to JF-DKG. In this case, to prevent the Gennaro et al. attack, the public key is constructed with a group element that is different from the one used in the first commitment phase of the DKG protocol.<br>The extended version of JF-DKG works as follows:<br>1. Each party chooses a random secret <em>ski </em>and sets their polynomial</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/530/1*ASqGQN_8bxzW0YUuXulsIA.png" /></figure><p>2. Each party <em>Pi </em>sends its share <em>sij = fi(j)</em> to <em>Pj </em>on a private channel.<br>3. Each party <em>Pi </em>broadcasts the commitment values</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/633/1*OnTHyUx6641_UcJYExjX3w.png" /></figure><p>4. Now each party <em>Pj </em>verifies the shares:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/287/1*X1YW-ZYUpsMZw8GyC-5jIA.png" /></figure><p>5. If this verification does not hold, <em>Pj </em>publishes a complaint for <em>Pi</em>.<br>• If more than t parties complain against <em>Pi</em>, that party is disqualified.<br>• Otherwise, Then <em>Pi </em>broadcasts its shares <em>sij </em>.<br>– If revealed shares <em>sij</em> are not verified again, then <em>Pi </em>will be disqualified.<br>6. The set <em>QUAL </em>of non-disqualified parties is determined. Let <em>P1, P2, .., Pm </em>be the set of non-disqualified parties.<br>7. Each party <em>Pi </em>sets his share <em>si</em> as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/372/1*arwcIXeiN44P_ZmwkWkwcg.png" /></figure><p>8. For computing the public key, Neji et al use a different group element<br><em>h</em>.<br>9. Each <em>Pi ∈ QU AL</em> publishes</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/44/1*JesOQdbZ_zW_cOITOKi5lg.png" /></figure><p>Moreover, <em>Pi </em>proves that</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/144/1*aO0z-j8uxgK8_rLWA6WxnQ.png" /></figure><p>have the same discrete logarithm value by using <a href="https://link.springer.com/content/pdf/10.1007/3-540-48071-4_7.pdf">Chaum Pedersen zero<br>knowledge proof</a>.<br>10. If the proof fails for <em>Pi</em>, the other parties reconstruct <em>ski </em>since there is at<br>least <em>t + 1 </em>honest party. Also, <em>Pi </em>is disqualified.<br>11. The public key is constructed by using honest parties, whose number is at least <em>t + 1</em> by our assumption</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/438/1*mGXzZGrB1D-1wX_LBSsxUg.png" /></figure><p>where the disqualified parties’ shares are computed by parties in <em>QUAL.</em></p><p>12. Finally, each party <em>Pi </em>submits its share <em>si</em>. Other parties verify this share</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/762/1*GuAl5BVSG3s9SGs-sQ6AkQ.png" /></figure><p>13. Assume that there are at least <em>t + 1 </em>qualified party submitting their secret shares. Then <em>sk </em>is reconstructed from the submitted shares using<br><a href="https://en.wikipedia.org/wiki/Polynomial_interpolation">polynomial interpolation</a>.<br> In the extended version of Joint-Feldman DKG, Gennaro et al’s attack does<br>not work because the public value <em>pk </em>is not computed from the public values published in the first commitment or key share distribution phase. Thus, the adversary can not change the distribution of the generated keys.<br>Compared to Gennaro et al. DKG, the extended JF-DKG has also two<br>rounds of communications. However, since it uses only one polynomial and a zero-knowledge proof instead of a complaint management phase, the extended JF-DKG can be seen as a simpler version of Gennaro et al. DKG.</p><h3>Conclusion</h3><p>We have seen Pedersen DKG namely JF-DKG (1991), Gennaro et al’s DKG<br>(2007), and the extended version of JF-DKG (2016).</p><p>Although Gennaro et al’s DKG and Extended version of JF-DKG are two solutions that we stated above, they need private channels to send secret shares to each other. This makes the protocol complex and not easy to use in practical situations like threshold cryptography.<br>Thus, the shares can be verified publicly. This mechanism is called the<br>Publicly Verifiable Secret Sharing mechanism (PVSS) introduced by Stadler,<br><a href="https://crypto.ethz.ch/publications/files/Stadle96.pdf">[Sta96]</a>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=279743dd6b32" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Man-in-the-middle Attacks on zk-SNARKs]]></title>
            <link>https://medium.com/@oznurmut/man-in-the-middle-attack-on-zk-snarks-679d95a374f3?source=rss-c6c2e75355b8------2</link>
            <guid isPermaLink="false">https://medium.com/p/679d95a374f3</guid>
            <category><![CDATA[zero-knowledge-proofs]]></category>
            <category><![CDATA[man-in-the-middle-attack]]></category>
            <category><![CDATA[cryptography]]></category>
            <category><![CDATA[zksnark]]></category>
            <dc:creator><![CDATA[Öznur Mut Sağdıçoğlu]]></dc:creator>
            <pubDate>Fri, 31 Mar 2023 08:03:55 GMT</pubDate>
            <atom:updated>2023-03-31T08:04:45.229Z</atom:updated>
            <content:encoded><![CDATA[<p><em>We explore man-in-the-middle attacks on Groth16 and Plonk. In the attack, an attacker can change a valid proof into a new proof without the witness, and the new proof is deemed valid by the verifier. We give two attack constructions one for Groth16 and one for Plonk.</em></p><h3>Introduction</h3><p>Blockchain technology which can be used to facilitate information sharing and value exchange between parties has use cases for several products and services across various industries including financial applications, supply chains, healthcare, trading, and many more.</p><p>The main challenge developers face when creating a blockchain is to provide a decentralized, scalable, and secure blockchain. These three criteria are termed blockchain trilemma (by Vitalik Buterin of Ethereum) where it is difficult to construct a blockchain without compromising any one of these attributes.</p><p>zk-SNARK (Zero-Knowledge Succinct Non-interactive Arguments of Knowledge) is an important cryptographic primitive which tries to find solutions for blockchain scalability, privacy, and decentralization. SNARK is a succinct proof of certain information where the verifier validates the proof without interaction with the prover. The proof is short and it is fast to verify. For zero-knowledge SNARK, the proof reveals nothing but the message. There are many zk-SNARKs such as <a href="https://eprint.iacr.org/2016/260.pdf">Groth16</a>, <a href="https://eprint.iacr.org/2019/953">Plonk</a>, <a href="https://eprint.iacr.org/2017/1066.pdf">Bulletproof</a>, <a href="https://eprint.iacr.org/2019/1021">Halo2</a>, and more which are characterized by the tools they are built on, and by differences in performance, proof sizes, verification times, etc.</p><p>In general, the problem with the zk-SNARKs is that they are susceptible to man-in-the-middle attacks. In this attack, an adversary can modify a proof so that the proof seems valid to the verifier without a witness.</p><p>To apply a man-in-the-middle attack on zk-SNARK for proof forgery, the attacker may use two ways. First, the attacker can change a valid proof by adding some values to the proof elements., which does not hurt the validity of the proof. Second, the attacker makes use of faulty implementation of challenges which are used to make an interactive proof to a non-interactive one using the Fiat Shamir method¹.</p><h4>Man-in-the-middle Attack on Groth16</h4><p><a href="https://medium.com/ppio/how-to-generate-a-groth16-proof-for-forgery-9f857b0dcafd">The proof forgery</a> for which the proof elements are changed by the attacker so that the new proof seems to be valid proof for the verifier is Groth16. <a href="https://eprint.iacr.org/2016/260.pdf">Groth16 </a>is a zk-SNARK. Since it has a small proof size and fast verification, it has been used in many projects such as Zcash and Filecoin. Zcash now uses another zkSNARK, Halo2.</p><p>Groth16 is the pairing-based non-interactive zero-knowledge proof, yielding constant-size proofs which are based on constructing a set of polynomial equations and using pairings to verify these equations efficiently. <a href="https://medium.com/ppio/how-to-generate-a-groth16-proof-for-forgery-9f857b0dcafd">An attacker can change proof elements by using</a></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/24/0*_dgppo4PzxD3fvxL" /></figure><p>defined in <a href="http://eprint.iacr.org/2016/260">the designer’s paper</a>. This is not a surprising result because knowledge-sound proofs are not secure against man-in-the-middle attacks². Knowledge-soundness means that a prover can create valid proof only by knowing the witness. However, an adversary can see a simulated proof for a false instance and might use some malleability property to modify this proof into another new proof for a different false instance. Groth16 is originally proven to achieve knowledge-soundness, which does not guarantee the non-malleability of proofs².</p><p><a href="https://medium.com/ppio/how-to-generate-a-groth16-proof-for-forgery-9f857b0dcafd">The attack</a> works as follows. The attacker uses a valid proof</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/120/0*3V5CsxJl6-Xp7-NW" /></figure><p>and comes out with a new proof</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/323/0*M8jro-5owSVSt5hk" /></figure><p>where [.] is an elliptic curve point on</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/86/0*0qvPEE5CuwHqt8_k" /></figure><p>This new proof can be computed by the attacker since the attacker can see public values and thus he can compute</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/162/0*81NzFbozdefLZHGB" /></figure><p>and</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/170/0*kmnV2diZRJ0KU1wz" /></figure><p>The attacker then sends updated proof to the verifier. The verifier checks the pairing equation for <a href="https://medium.com/ppio/how-to-generate-a-groth16-proof-for-forgery-9f857b0dcafd">the new proof </a>elements:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ADzGWn1OKqcFuaWQkTA42A.png" /></figure><p>And it is verified. The values above are defined in <a href="http://eprint.iacr.org/2016/260">the designer’s paper.</a></p><h4>Man-in-the-middle Attack on Plonk</h4><p>The example in which the Fiat Shamir method is implemented inappropriately so that an attacker can create a new and valid proof is Plonk. <a href="https://eprint.iacr.org/2019/953">Plonk </a>is a zk-SNARK protocol and stands for Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge.</p><p>Plonk has short proofs, fast proving time, fully succinct verification,<br>and a non-circuit-specific trusted setup. Because of these properties, The Electric Coin Company, Mina Protocol, Matter Labs, Dusk Network, the Ethereum Foundation (EF), and some others are using Plonk in their projects. For example, Zcash which is the first project to implement zk-SNARKs also uses Plonk.</p><p>Plonk uses Kate polynomial commitments based on elliptic curve pairing. To make the proof non-interactive, it makes use of the Fiat Shamir method.</p><p>To use Fiat-Shamir in the right way, the prover generates a challenge by hashing all data, including the proof. In practice, however, the developers could misunderstand this statement and they do not include all the data needed in the hash function and make a wrong implementation of the system.</p><p>As a result, an attacker could change a valid proof without needing the witness and the new proof seems valid to the verifier. This leads to the <a href="https://blog.trailofbits.com/2022/04/13/part-1-coordinated-disclosure-of-vulnerabilities-affecting-girault-bulletproofs-and-plonk/">forgery of Plonk</a> by malicious users.</p><p>In practice, the following are affected by faulty implementations of Plonk:</p><blockquote><em>ZenGo’s zk-paillier</em><br><em>ING Bank’s zkrp (deleted)<br>SECBIT Labs’ ckb-zkp<br>Adjoint, Inc.’s bulletproofs<br> Dusk Network’s plonk<br> Iden3’s SnarkJS<br> ConsenSys’ gnark</em></blockquote><p>In this post, we construct a proof forgery of Plonk caused by faulty implementation, i.e. misuse of the Fiat Shamir method.</p><p>First, assume that some proof values are not included in the calculation of the challenge value</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/8/0*7OP5028nXMcpU44N" /></figure><p>which is called an evaluation challenge in the <a href="https://eprint.iacr.org/2019/953">designer’s paper</a>. In other words, when calculating this challenge, developers do not put some or all proof elements in the hash function.</p><p>Then the attacker can modify the values of the quotient polynomial and the opening proof polynomial</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/113/0*0DW4Q36ZQHsZXZYi" /></figure><p>respectively, in a way that the new values are</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/396/0*fNrX7QEHjsiIxQYj" /></figure><p>The notation [.] represents a point on the given elliptic curve.</p><p>The attacker then sends the new proof to the verifier. The final equation in the verification phase of Plonk uses the elliptic curve pairing. Since the attacker changes the quotient polynomial <em>t</em>, the value <em>F</em> changes and the new <em>F</em> value appears as</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/123/0*AWXqZ85320Evg8xV" /></figure><p>in the pairing equation. The verifier is going to check that the pairing equation holds for new values, the values are defined in <a href="https://eprint.iacr.org/2019/953">the designer’s paper</a>:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/558/0*YL1EspgDqQHkJ2yC" /></figure><p>The left-hand side of the pairing equation is</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/264/0*vDGGKQOVjBG8xYLe" /></figure><p>And the right-hand side of the pairing equation is</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/504/0*Xd5C46N60ejLu_8T" /></figure><p>Up to now, the question is whether these two values</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/81/0*aRrKihpkHIwHCtAw" /></figure><p>and</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/288/0*3d2BQro6g0Zryabp" /></figure><p>are equal or not. We know the following equalities</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/336/0*IouYg2oMmb91Mn0x" /></figure><p>and</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/336/0*dH7NEZKSdytCVwWk" /></figure><p>are equal, where <em>G’</em>s are points on elliptic curves defined in the designer’s paper. As a result, the left-hand side and the right-hand side of the pairing equation are equal and the final pairing equation holds for new values which the attacker has updated without knowing the witness. As a result, if the Fiat-Shamir method is not used appropriately, then Plonk may become vulnerable to a man-in-the-middle attack resulting in proof forgery.</p><h4>Recap</h4><p>zk-SNARK may in general be vulnerable to a man-in-the-attack. This is mainly because of two reasons.</p><p>The first reason is that knowledge soundness does not guarantee the non-malleability of proof.</p><p>The second reason is faulty implementations of the proving system. In a proof system, developers should be careful in achieving the correct implementation. Indeed this is true for almost all implementations. Interestingly, not every faulty software/hardware implementation leads to a security vulnerability in the target system. However, in the case of Plonk, faulty implementation leads to an attack.</p><p>[1]: Amos Fiat, Adi Shamir: <strong>How to Prove Yourself: Practical Solutions to Identification and Signature Problems.</strong> CRYPTO 1986: 186–194.</p><p>[2]: Karim Baghery, Zaira Pindado, Carla Ràfols: <strong>Simulation Extractable Versions of Groth’s zk-SNARK Revisited.</strong> CANS 2020: 453–461.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=679d95a374f3" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>