arnaucube.com/public/blind-signatures-ec.html
public/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 </head>
38
39 <body>
40
41 <!-- o_gradient_background" -->
42 <nav id="mainNav" class="navbar navbar-default navbar-fixed-top"
43 style="height:50px;font-size:130%;">
44 <div class="container">
45 <div style="float:left;">
46 <a href="/blog" style="color:#000;display:inline-block;">Blog index</a>
47 <span style="margin-right:20px; margin-left:20px;">|</span>
48 <a href="/blog/notes.html" style="font-size:90%;color:#000;display:inline-block;">other-notes</a>
49 </div>
50 <div style="float:right;">
51 <a href="/" style="color:#000;display:inline-block;">arnaucube.com</a>
52 <div class="onoffswitch" style="margin:10px;display:inline-block;" title="change theme">
53 <input onclick="switchTheme()" type="checkbox" name="onoffswitch" class="onoffswitch-checkbox"
54 id="themeSwitcher">
55 <label class="onoffswitch-label" for="themeSwitcher"></label>
56 </div>
57 </div>
58 </div>
59 <img style="height:5px; width:100%; margin-top:8px;" src="img/gradient-line.jpg" />
60 </nav>
61
62
63
64 <div class="container" style="margin-top:40px;max-width:800px;">
65 <h1>Notes on blind signatures over elliptic curves</h1>
66
67<p><em>2021-07-30</em></p>
68
69<blockquote>
70<p><strong>Warning</strong>: I want to state clearly that I’m not a mathematician, I’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>
71</blockquote>
72
73<h4>Blind signatures</h4>
74
75<p>Few years ago I read about the RSA blind signatures scheme (thanks to <a href="https://futur.upc.edu/JuanBautistaHernandezSerrano">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>.
76The 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’s public key.</p>
77
78<p><div style="text-align:center; font-size:80%;">
79 <img style="padding:50px;max-width:100%;" src="img/posts/blind-signatures-ec/flow0.png" />
80 <i>Diagram showing the described steps.</i>
81</div>
82<br></p>
83
84<p>This has many applications, one of them could be to authenticate users in a ‘traditional’ way (by user&password, or by public key & 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 ‘traditional’ 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>
85
86<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’s why I got interested into reading and learning about schemes that provide blind signatures over <em>elliptic curve</em>.</p>
87
88<h4>The scheme</h4>
89
90<p>In this notes, we will cover the scheme proposed at <em>“<a href="https://sci-hub.do/10.1109/ICCKE.2013.6682844">New Blind Signature Schemes Based on the (Elliptic Curve) Discrete Logarithm Problem</a>”</em> paper by Hamid Mala & Nafiseh Nezhadansari (thanks to <a href="https://twitter.com/feministPLT">Daira Hopwood</a> who mentioned this paper in a Telegram group).</p>
91
92<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>
93
94<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>
95
96<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>.
97The 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>
98
99<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>
100
101<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>
102
103<p>And now, we are in a point where the signature can be verified by a third party for the <em>signer</em>’s public key by checking <span class="math inline">\(sG == R + x h(m) Q\)</span>.</p>
104
105<p><div style="text-align:center; font-size:80%;">
106 <img style="padding:50px;max-width:100%;" src="img/posts/blind-signatures-ec/flow1.png" />
107 <i>The previous diagram but with the operations from each step.</i>
108</div>
109<br></p>
110
111<p>From the verification <span class="math inline">\(sG == R + x h(m) Q\)</span>, we can unroll it and check that:</p>
112<p><span class="math display">\[
113\fbox{sG} = (a s' + b) G = (a (d m' + k) + b) G\newline
114= (a d m' + ak + b) G = ((a d (a^{-1} x h(m))) + ak + b) G\newline
115= (d x h(m) + ak + b) G\newline
116= dG x h(m) + (ak + b)G = \fbox{R + x h(m) Q}
117\]</span></p>
118<h4>Code</h4>
119
120<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>
121
122<pre><code class="language-go">import (
123 [...]
124 "github.com/arnaucube/go-blindsecp256k1"
125)
126
127func main() {
128 // signer: create new signer key pair
129 sk := blindsecp256k1.NewPrivateKey()
130 signerPubK := sk.Public()
131
132 // signer: when user requests new R parameter to blind a new msg,
133 // create new signerR (public) with its secret k
134 k, signerR := blindsecp256k1.NewRequestParameters()
135
136 // user: blinds the msg using signer's R
137 msg := new(big.Int).SetBytes([]byte("test"))
138 msgBlinded, userSecretData, err := blindsecp256k1.Blind(msg, signerR)
139 if err != nil {
140 panic(err)
141 }
142
143 // signer: signs the blinded message using its private key & secret k
144 sBlind, err := sk.BlindSign(msgBlinded, k)
145 if err != nil {
146 panic(err)
147 }
148
149 // user: unblinds the blinded signature
150 sig := blindsecp256k1.Unblind(sBlind, userSecretData)
151
152 // signature can be verified with signer PublicKey
153 verified := blindsecp256k1.Verify(msg, sig, signerPubK)
154 if !verified {
155 fmt.Println("verification failed")
156 } else {
157 fmt.Println("blind signature verified")
158 }
159}
160</code></pre>
161
162<h4>Conclusions</h4>
163
164<p>Blind signatures are an interesting concept, which can be used in some use cases specially on voting systems. As we’ve seen, the math background behind it’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>
165
166<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 & keys structures, to use the generic Go ones, so other curves and already existing keys could be used with the same code.</p>
167
168<p><em>Special thanks to <a href="https://github.com/dhole">@dhole</a> for reviewing this text.</em></p>
169
170 </div>
171
172 <footer style="text-align:center; margin-top:100px;margin-bottom:50px;">
173 <div class="container">
174 <br>
175 <a href="/blog">Go to main</a>
176 <br><br>
177 <div class="row">
178 <ul class="list-inline">
179 <li><a href="https://twitter.com/arnaucube"
180 style="color:gray;text-decoration:none;"
181 target="_blank">twitter.com/arnaucube</a>
182 </li>
183 <li><a href="https://github.com/arnaucube"
184 style="color:gray;text-decoration:none;"
185 target="_blank">github.com/arnaucube</a>
186 </li>
187 </ul>
188 </div>
189 <div class="row" style="display:inline-block;">
190 Blog made with <a href="http://github.com/arnaucube/blogo/"
191 target="_blank" style="color: gray;text-decoration:none;">Blogo</a>
192 </div>
193 </div>
194 </footer>
195
196 <script>
197 </script>
198 <script src="js/external-links.js"></script>
199 <script>hljs.initHighlightingOnLoad();</script>
200 <script defer src="js/katex/katex.min.js"></script>
201 <script defer src="js/katex/auto-render.min.js"></script>
202 <script>
203 document.addEventListener("DOMContentLoaded", function() {
204 renderMathInElement(document.body, {
205 displayMode: false,
206 // customised options
207 // • auto-render specific keys, e.g.:
208 delimiters: [
209 {left: '$$', right: '$$', display: true},
210 {left: '$', right: '$', display: false},
211 {left: "\\[", right: "\\]", display: true},
212 {left: "\\(", right: "\\)", display: false},
213 {left: "\\begin{equation}", right: "\\end{equation}", display: true}
214 ],
215 // • rendering keys, e.g.:
216 throwOnError : true
217 });
218 });
219
220 ///
221 let theme = localStorage.getItem("theme");
222 if ((theme === "light-theme")||(theme==null)) {
223 theme = "light-theme";
224 document.getElementById("themeSwitcher").checked = false;
225 } else if (theme === "dark-theme") {
226 theme = "dark-theme";
227 document.getElementById("themeSwitcher").checked = true;
228 }
229 document.body.className = theme;
230 localStorage.setItem("theme", theme);
231
232 function switchTheme() {
233 theme = localStorage.getItem("theme");
234 if (theme === "light-theme") {
235 theme = "dark-theme";
236 document.getElementById("themeSwitcher").checked = true;
237 } else {
238 theme = "light-theme";
239 document.getElementById("themeSwitcher").checked = false;
240 }
241 document.body.className = theme;
242 localStorage.setItem("theme", theme);
243
244 console.log(theme);
245 }
246 </script>
247 <script>
248 function tagLinks(tagName) {
249 var tags = document.getElementsByTagName(tagName);
250 for (var i=0, hElem; hElem = tags[i]; i++) {
251 if (hElem.parentNode.className=="row postThumb") {
252 continue;
253 }
254 hElem.id = hElem.innerHTML.toLowerCase().replace(" ", "-");
255 hElem.innerHTML = "<a style='text-decoration:none;color:black;' href='#"+hElem.id+"'>"+hElem.innerHTML+"</a>";
256 }
257 }
258 tagLinks("h2");
259 tagLinks("h3");
260 tagLinks("h4");
261 tagLinks("h5");
262 </script>
263 <script src="js/mermaid.min.js"></script>
264
265
266 </body>
267</html>
268