arnaucube
arnaucube/arnaucube.comPublic Self-hosted repository
arnaucube.com/blog/blind-signatures-ec.html
blog/blind-signatures-ec.htmlRaw
  1<!DOCTYPE html>
  2<html lang="en">
  3
  4  <head>
  5    <meta name="description" content="In this notes, we will cover the scheme proposed at 'New Blind Signature Schemes Based on the (Elliptic Curve) Discrete Logarithm Problem' paper by Hamid Mala & Nafiseh Nezhadansari." />
  6    <meta charset="utf-8">
  7    <title> Notes on blind signatures over elliptic curves - arnaucube - blog</title>
  8    <meta name="title" content=" Notes on blind signatures over elliptic curves - arnaucube - blog">
  9    <meta name="description" content="In this notes, we will cover the scheme proposed at 'New Blind Signature Schemes Based on the (Elliptic Curve) Discrete Logarithm Problem' paper by Hamid Mala & Nafiseh Nezhadansari.">
 10
 11    <meta property="og:title" content=" Notes on blind signatures over elliptic curves - arnaucube - blog" />
 12    <meta property="og:description" content="In this notes, we will cover the scheme proposed at 'New Blind Signature Schemes Based on the (Elliptic Curve) Discrete Logarithm Problem' paper by Hamid Mala & Nafiseh Nezhadansari." />
 13    <meta property="og:url" content="https://arnaucube.com/blog/blind-signatures-ec.html" />
 14    <meta property="og:type" content="article" />
 15    <meta property="og:image" content="https://arnaucube.com/blog/img/posts/blind-signatures-ec/flow1.png" />
 16    <meta name="twitter:title" content=" Notes on blind signatures over elliptic curves - arnaucube - blog">
 17    <meta name="twitter:description" content="In this notes, we will cover the scheme proposed at 'New Blind Signature Schemes Based on the (Elliptic Curve) Discrete Logarithm Problem' paper by Hamid Mala & Nafiseh Nezhadansari.">
 18    <meta name="twitter:image" content="https://arnaucube.com/blog/img/posts/blind-signatures-ec/flow1.png">
 19    <meta name="twitter:card" content="summary_large_image">
 20    <meta name="author" content="arnaucube">
 21
 22    <link rel="icon" type="image/png" href="img/logoArnauCubeFavicon.png">
 23
 24    <meta name="viewport" content="width=device-width, initial-scale=1">
 25
 26    <link href="css/bootstrap.min.css" rel="stylesheet">
 27    <link rel="stylesheet" href="css/style.css">
 28
 29    <!-- highlightjs -->
 30    <!-- <link rel="stylesheet" href="js/highlightjs/atom-one-dark.css"> -->
 31    <link rel="stylesheet" href="js/highlightjs/atom-one-light.css">
 32    <!-- <link rel="stylesheet" href="js/highlightjs/gruvbox-dark.css"> -->
 33    <script src="js/highlightjs/highlight.pack.js"></script>
 34
 35    <!-- katex -->
 36    <link rel="stylesheet" href="js/katex/katex.min.css">
 37  <link rel="alternate" type="application/rss+xml" title="arnaucube - blog RSS" href="https://arnaucube.com/blog/rss.xml">
 38</head>
 39
 40  <body>
 41
 42    <!-- o_gradient_background" -->
 43    <nav id="mainNav" class="navbar navbar-default navbar-fixed-top"
 44                      style="height:50px;font-size:100%;">
 45      <div class="container">
 46        <div style="float:left;">
 47        <a href="/blog" style="color:#000;display:inline-block;">blog</a>
 48        <span style="margin-right:20px; margin-left:20px;">|</span>
 49        <a href="/blog/notes.html" style="font-size:90%;color:#000;display:inline-block;">notes</a>
 50        </div>
 51        <div style="float:right;">
 52          <a href="/" style="color:#000;display:inline-block;margin-right:10px;">arnaucube.com</a>
 53          <a href="/blog/rss.xml" target="_blank"
 54            type="application/rss+xml" title="subscribe via RSS" aria-label="subscribe via RSS">
 55              <img width="12px;" src="img/rss.png" />
 56          </a>
 57          <div class="onoffswitch" style="margin-left:0px;display:inline-block;" title="change theme">
 58            <input onclick="switchTheme()" type="checkbox" name="onoffswitch" class="onoffswitch-checkbox"
 59              id="themeSwitcher">
 60            <label class="onoffswitch-label" for="themeSwitcher"></label>
 61          </div>
 62        </div>
 63      </div>
 64      <!-- <img style="height:5px; width:100%; margin-top:8px;" src="img/gradient-line.jpg" /> -->
 65    </nav>
 66
 67
 68    <div class="container" style="max-width:800px;">
 69        <br>
 70        <div style="background:#cccccc; border:2px gray solid; padding:5px; width:80%;margin-left:auto; margin-right:auto; margin-bottom:5px;">
 71          <i>Note: this blog is human-written, no AI generated content.</i>
 72        </div>
 73
 74      <h1>Notes on blind signatures over elliptic curves</h1>
 75
 76<p><em>2021-07-30</em></p>
 77
 78<blockquote>
 79<p><strong>Warning</strong>: I want to state clearly that I&rsquo;m not a mathematician, I&rsquo;m just an amateur on math studying in my free time, and this article is just an attempt to try to sort the notes that I took while reading about the blind signatures over elliptic curves.</p>
 80</blockquote>
 81
 82<h4>Blind signatures</h4>
 83
 84<p>Few years ago I read about the RSA blind signatures scheme (thanks to <a href="https://futur.upc.edu/JuanHernandezSerrano">Juan Hernández</a> who discovered it to me) and I was amazed on such thing being possible. You can read the step by step of the <em>RSA blind signatures</em> scheme in <a href="https://en.wikipedia.org/wiki/Blind_signature#Blind_RSA_signatures">this Wikipedia article</a>.
 85The main idea is that one party has a message and blinds it, then sends the blinded message to a signer. The signer generates a signature of that blinded message, who sends it to the initial party, who unblinds the signature, obtaining a valid signature for the original message, while the signer does not know what it is signing, but the signature can be verified for the original message for the signer&rsquo;s public key.</p>
 86
 87<p><div style="text-align:center; font-size:80%;">
 88    <img style="padding:50px;max-width:100%;" src="img/posts/blind-signatures-ec/flow0.png" />
 89    <i>Diagram showing the described steps.</i>
 90</div>
 91<br></p>
 92
 93<p>This has many applications, one of them could be to authenticate users in a &lsquo;traditional&rsquo; way (by user&amp;password, or by public key &amp; signature) in the Certification Authority (CA), and once the user is authenticated, the user can create a new key pair (ephemeral key), for which public key gets blinded and sent to the CA. The CA performs a blind signature on it, and sends the result back to the user. Then, the user can unblind the signature, and as result has their public key signed by the CA, but the CA does not know which is the public key (but the CA knows that the user while being authenticated by their &lsquo;traditional&rsquo; login, generated a new identity (key pair) and sent the public key blinded to the CA, who blindly signed it and returned the signature back to the user). Then the user has the ephemeral public key which is signed by the CA, and can use it to enter the system authenticating that they are an approved user without revealing which user they are.</p>
 94
 95<p>As most of the current ongoing protocols are using <em>elliptic curve</em> cryptography instead of <em>RSA</em>, the mentioned <em>RSA blind signatures</em> scheme is not much plugable in the existing systems that use <em>elliptic curve</em> keys. That&rsquo;s why I got interested into reading and learning about schemes that provide blind signatures over <em>elliptic curve</em>.</p>
 96
 97<h4>The scheme</h4>
 98
 99<p>In this notes, we will cover the scheme proposed at <em>&ldquo;<a href="https://sci-hub.do/10.1109/ICCKE.2013.6682844">New Blind Signature Schemes Based on the (Elliptic Curve) Discrete Logarithm Problem</a>&rdquo;</em> paper by Hamid Mala &amp; Nafiseh Nezhadansari (thanks to <a href="https://twitter.com/feministPLT">Daira Hopwood</a> who mentioned this paper in a Telegram group).</p>
100
101<p>First of all, the <em>signer</em> generates their key pair by generating a random scalar <span class="math inline">\(d \in \mathbb{Z}_n\)</span> (where <span class="math inline">\(\mathbb{Z}_n\)</span> is the elliptic curve field), which will be the <em>private key</em>. From <span class="math inline">\(d\)</span> they can compute the <em>public key</em> by <span class="math inline">\(Q = dG\)</span>, where <span class="math inline">\(G\)</span> is the generator point of <span class="math inline">\(\mathbb{G}\)</span> (the elliptic curve group).</p>
102
103<p>Appart from their key pair, the <em>signer</em> will generate for each request of signature another random value <span class="math inline">\(k \in \mathbb{Z}_n\)</span>, and its respective <span class="math inline">\(R'=kG\)</span>.</p>
104
105<p>The <em>user</em> has a message <em>m</em> that which they want to get signed by the <em>signer</em> (without the <em>signer</em> knowing the content of <em>m</em>). In order to achieve that, the user will generate a coupe of random values <span class="math inline">\(a, b \in \mathbb{Z}_n\)</span>, and from these parameters will compute the <em>blinding factor</em> <span class="math inline">\(R=aR' + bG = (ak + b)G\)</span>, and as <span class="math inline">\(R\)</span> is a point we can get <span class="math inline">\(R = (x, y)\)</span>.
106The user can <em>blind</em> the message by computing <span class="math inline">\(m' = a^{-1} \cdot x \cdot h(m)\)</span>, where <span class="math inline">\(h(m)\)</span> is the hash of the message.</p>
107
108<p>Then, the <em>user</em> sends the <em>blinded message</em> (<span class="math inline">\(m'\)</span>) to the <em>signer</em>, who will perform the <em>blind signature</em> by computing <span class="math inline">\(s' = d m' + k\)</span>, which is sent back to the <em>user</em>.</p>
109
110<p>The <em>user</em> can unblind the signature by <span class="math inline">\(s = a s' + b\)</span>, and the complete signature will be <span class="math inline">\((R, s)\)</span>.</p>
111
112<p>And now, we are in a point where the signature can be verified by a third party for the <em>signer</em>&rsquo;s public key by checking <span class="math inline">\(sG == R + x h(m) Q\)</span>.</p>
113
114<p><div style="text-align:center; font-size:80%;">
115    <img style="padding:50px;max-width:100%;" src="img/posts/blind-signatures-ec/flow1.png" />
116    <i>The previous diagram but with the operations from each step.</i>
117</div>
118<br></p>
119
120<p>From the verification <span class="math inline">\(sG == R + x h(m) Q\)</span>, we can unroll it and check that:</p>
121<p><span class="math display">\[
122\fbox{sG} = (a s' + b) G = (a (d m' + k) + b) G\newline
123= (a d m' + ak + b) G = ((a d (a^{-1} x h(m))) + ak + b) G\newline
124= (d x h(m) + ak + b) G\newline
125= dG x h(m) + (ak + b)G = \fbox{R + x h(m) Q}
126\]</span></p>
127<h4>Code</h4>
128
129<p>Here is an example of how this scheme on the <a href="https://en.bitcoin.it/wiki/Secp256k1">secp256k1</a> curve could be used using the implementation from <a href="https://github.com/arnaucube/go-blindsecp256k1">go-blindsecp256k1</a>.</p>
130
131<pre><code class="language-go">import (
132	[...]
133	&quot;github.com/arnaucube/go-blindsecp256k1&quot;
134)
135
136func main() {
137    // signer: create new signer key pair
138    sk := blindsecp256k1.NewPrivateKey()
139    signerPubK := sk.Public()
140
141    // signer: when user requests new R parameter to blind a new msg,
142    // create new signerR (public) with its secret k
143    k, signerR := blindsecp256k1.NewRequestParameters()
144
145    // user: blinds the msg using signer's R
146    msg := new(big.Int).SetBytes([]byte(&quot;test&quot;))
147    msgBlinded, userSecretData, err := blindsecp256k1.Blind(msg, signerR)
148    if err != nil {
149	panic(err)
150    }
151
152    // signer: signs the blinded message using its private key &amp; secret k
153    sBlind, err := sk.BlindSign(msgBlinded, k)
154    if err != nil {
155	panic(err)
156    }
157
158    // user: unblinds the blinded signature
159    sig := blindsecp256k1.Unblind(sBlind, userSecretData)
160
161    // signature can be verified with signer PublicKey
162    verified := blindsecp256k1.Verify(msg, sig, signerPubK)
163    if !verified {
164	fmt.Println(&quot;verification failed&quot;)
165    } else {
166	fmt.Println(&quot;blind signature verified&quot;)
167    }
168}
169</code></pre>
170
171<h4>Conclusions</h4>
172
173<p>Blind signatures are an interesting concept, which can be used in some use cases specially on voting systems. As we&rsquo;ve seen, the math background behind it&rsquo;s not quite complex compared for example to zkSNARKs, and it does not require <a href="https://medium.com/qed-it/diving-into-the-snarks-setup-phase-b7660242a0d7">trusted setups</a>. Although, for most of the cases zkSNARKs have more flexibility, and we could cover similar use cases by proving that the user knows some <em>private key</em> for which the corresponding <em>public key</em> is placed in a leaf of a <em>Merkle Tree</em> for a certain <em>Merkle Root</em> (but this would be out of scope for the current notes).</p>
174
175<p>An implementation of this scheme in Go can be found in: <a href="https://github.com/arnaucube/go-blindsecp256k1">https://github.com/arnaucube/go-blindsecp256k1</a> (and a compatible Typescript implementation <a href="https://github.com/arnaucube/blindsecp256k1-js">blindsecp256k1-js</a>). A next iteration could be to abstract the curve &amp; keys structures, to use the generic Go ones, so other curves and already existing keys could be used with the same code.</p>
176
177<p><em>Special thanks to <a href="https://github.com/dhole">@dhole</a> for reviewing this text.</em></p>
178
179<h3>Update 2022-10-29: Schnorr Blind Signatures</h3>
180
181<p><em>2022-10-29</em></p>
182
183<p><a href="https://sites.google.com/site/vincenzoiovinoit/">Vincenzo Iovino</a> recently showed me the paper <a href="https://eprint.iacr.org/2019/877">https://eprint.iacr.org/2019/877</a>, which describes the <em>Blind Schnorr Signature</em>. This subsection describes it. The concepts and parties are the same, the difference is in the values computed.</p>
184
185<p>The public parameters consist of a group <span class="math inline">\(\mathbb{G}\)</span> of order <span class="math inline">\(p\)</span> and generator <span class="math inline">\(G\)</span>, and a cryptographic hash function <span class="math inline">\(\mathcal{H} : \{0,1\}^* \rightarrow \mathbb{Z}_p\)</span>.</p>
186
187<p>The private key of the Signer is a random scalar <span class="math inline">\(x \in \mathbb{Z}_p\)</span> and the corresponding public key is <span class="math inline">\(X = xG\)</span>.</p>
188
189<p>Any User who wants to obtain a signature for some message <span class="math inline">\(m\)</span> without disclosing the content of that message to the Signer proceeds as follows:</p>
190
191<ol>
192<li>The User sends a signing request to the Signer. This request will typically be signed; thus the Signer knows whether the request is legitimate or not.</li>
193<li>If the request is legitimate, the Signer generates a random <span class="math inline">\(r \in \mathbb{Z}_p\)</span>, computes <span class="math inline">\(R = rG\)</span> and sends <span class="math inline">\(R\)</span> to the User.</li>
194<li>The User selects random scalars <span class="math inline">\(\alpha, \beta \in \mathbb{Z}_p\)</span>, computes the \emph{blinding factor} <span class="math inline">\(R' = R + \alpha G + \beta X\)</span>, sets <span class="math inline">\(c = \mathcal{H}(R', m) + \beta \bmod{p}\)</span> and sends <span class="math inline">\(c\)</span> to the Signer.</li>
195<li>The Signer computes <span class="math inline">\(s = r + cx \bmod{p}\)</span> and sends <span class="math inline">\(s\)</span> to the User.</li>
196<li>The User verifies that the value <span class="math inline">\(s\)</span> received is correct by verifying that <span class="math inline">\(sG = R + cX\)</span>. Setting <span class="math inline">\(s' = s + \alpha \bmod{p}\)</span>, the signature of the message <span class="math inline">\(m\)</span> is then <span class="math inline">\(\sigma = (R', s')\)</span>.</li>
197</ol>
198
199<p>Anyone can then verify the validity of the signature by checking the equality <span class="math inline">\(s'G \stackrel{?}{=} R' + \mathcal{H}(R', m)X\)</span>. To see why this must hold, we can unroll the equation:</p>
200<p><span class="math display">\[
201s'G = sG + \alpha G \\
202    = rG + cxG + \alpha G \\
203    = rG + (\mathcal{H}(R', m) + \beta) X + \alpha G \\
204    = R + \alpha G + \beta X + \mathcal{H}(R', m) X \\
205    = R' + \mathcal{H}(R', m) X
206\]</span></p><p>Note that blind Schnorr signatures can be subject to so-called ROS (Random inhomogeneities in a Overdetermined Solvable system of linear equations) attacks, but these attacks can be defended against by forbidding parallel sessions.</p>
207
208<p>An implementation of this scheme in Rust and also in R1CS circuits can be found at <a href="https://github.com/aragonzkresearch/ark-ec-blind-signatures">github.com/aragonzkresearch/ark-ec-blind-signatures</a> . We used this scheme in the <a href="https://github.com/aragonzkresearch/research/blob/main/blind-ovote/blind-ovote.pdf">Blind-OVOTE</a> project, a L2 validity rollup, which uses blind signatures over elliptic curves inside zkSNARK, to provide offchain anonymous voting with onchain binding execution on Ethereum.</p>
209
210    </div>
211
212    <footer style="text-align:center; margin-top:100px;margin-bottom:50px;">
213      <div class="container">
214        <br>
215        <a href="/blog">Go to main</a>
216        <br><br>
217        <div class="row">
218          <ul class="list-inline">
219            <li><a href="https://twitter.com/arnaucube"
220                   style="color:gray;text-decoration:none;"
221                   target="_blank">twitter.com/arnaucube</a>
222            </li>
223            <li><a href="https://github.com/arnaucube"
224                   style="color:gray;text-decoration:none;"
225                   target="_blank">github.com/arnaucube</a>
226            </li>
227          </ul>
228        </div>
229        <div class="row" style="display:inline-block;">
230          Blog made with <a href="http://github.com/arnaucube/blogo/"
231                            target="_blank" style="color: gray;text-decoration:none;">Blogo</a>
232        </div>
233      </div>
234    </footer>
235
236    <script>
237    </script>
238    <script src="js/external-links.js"></script>
239    <script>hljs.initHighlightingOnLoad();</script>
240    <script defer src="js/katex/katex.min.js"></script>
241    <script defer src="js/katex/auto-render.min.js"></script>
242    <script>
243      document.addEventListener("DOMContentLoaded", function() {
244        renderMathInElement(document.body, {
245          displayMode: false,
246          // customised options
247          // • auto-render specific keys, e.g.:
248          delimiters: [
249            {left: '$$', right: '$$', display: true},
250            {left: '$', right: '$', display: false},
251            {left: "\\[", right: "\\]", display: true},
252            {left: "\\(", right: "\\)", display: false},
253            {left: "\\begin{equation}", right: "\\end{equation}", display: true}
254          ],
255          // • rendering keys, e.g.:
256          throwOnError : true
257        });
258      });
259
260      ///
261      let theme = localStorage.getItem("theme");
262      if ((theme === "light-theme")||(theme==null)) {
263          theme = "light-theme";
264          document.getElementById("themeSwitcher").checked = false;
265      } else if (theme === "dark-theme") {
266          theme = "dark-theme";
267          document.getElementById("themeSwitcher").checked = true;
268      }
269      document.body.className = theme;
270      localStorage.setItem("theme", theme);
271
272      function switchTheme() {
273        theme = localStorage.getItem("theme");
274        if (theme === "light-theme") {
275          theme = "dark-theme";
276          document.getElementById("themeSwitcher").checked = true;
277        } else {
278          theme = "light-theme";
279          document.getElementById("themeSwitcher").checked = false;
280        }
281        document.body.className = theme;
282        localStorage.setItem("theme", theme);
283
284        console.log(theme);
285      }
286    </script>
287    <script>
288    function tagLinks(tagName) {
289      var tags = document.getElementsByTagName(tagName);
290      for (var i=0, hElem; hElem =  tags[i]; i++) {
291        if (hElem.parentNode.className=="row postThumb") {
292          continue;
293        }
294        hElem.id = hElem.innerHTML.toLowerCase().replace(" ", "-");
295        hElem.innerHTML = "<a style='color:black!important;' href='#"+hElem.id+"'>"+hElem.innerHTML+"</a>";
296      }
297    }
298    tagLinks("h2");
299    tagLinks("h3");
300    tagLinks("h4");
301    tagLinks("h5");
302    </script>
303    <script>
304function generateTOC(tocContainerId = "toc") {
305    const tocContainer = document.getElementById(tocContainerId);
306    if (!tocContainer) return;
307
308    const headings = document.querySelectorAll("h2, h3, h4, h5, h6");
309    if (!headings.length) return;
310
311    // Generate IDs if missing
312    headings.forEach((heading, index) => {
313        if (!heading.id) {
314            heading.id =
315                heading.textContent
316                    .trim()
317                    .toLowerCase()
318                    .replace(/[^\w\s-]/g, "")
319                    .replace(/\s+/g, "-") +
320                "-" +
321                index;
322        }
323    });
324
325    const toc = document.createElement("ul");
326    let currentLevel = 1;
327    let currentList = toc;
328    const stack = [toc];
329
330    headings.forEach((heading) => {
331        const level = parseInt(heading.tagName.substring(1), 10);
332
333        const li = document.createElement("li");
334        const a = document.createElement("a");
335
336        a.href = "#" + heading.id;
337        a.textContent = heading.textContent;
338
339        li.appendChild(a);
340
341        if (level > currentLevel) {
342            for (let i = currentLevel; i < level; i++) {
343                const nestedList = document.createElement("ul");
344
345                const lastLi =
346                    currentList.lastElementChild ||
347                    currentList.appendChild(document.createElement("ul"));
348
349                lastLi.appendChild(nestedList);
350
351                stack.push(nestedList);
352                currentList = nestedList;
353            }
354        } else if (level < currentLevel) {
355            for (let i = currentLevel; i > level; i--) {
356                stack.pop();
357            }
358            currentList = stack[stack.length - 1];
359        }
360
361        currentList.appendChild(li);
362        currentLevel = level;
363    });
364
365    tocContainer.innerHTML = "";
366    tocContainer.appendChild(toc);
367}
368
369document.addEventListener("DOMContentLoaded", () => {
370    generateTOC();
371});
372    </script>
373    <script src="js/mermaid.min.js"></script>
374
375  </body>
376</html>
377