arnaucube.com/blog/ringsig.html
blog/ringsig.htmlRaw
1<!DOCTYPE html>
2<html lang="en">
3
4 <head>
5 <meta name="description" content="Notes on ring signatures" />
6 <meta charset="utf-8">
7 <title> bLSAG ring signatures overview - arnaucube - blog</title>
8 <meta name="title" content=" bLSAG ring signatures overview - arnaucube - blog">
9 <meta name="description" content="Notes on ring signatures">
10
11 <meta property="og:title" content=" bLSAG ring signatures overview - arnaucube - blog" />
12 <meta property="og:description" content="Notes on ring signatures" />
13 <meta property="og:url" content="https://arnaucube.com/blog/ringsig.html" />
14 <meta property="og:type" content="article" />
15 <meta property="og:image" content="https://arnaucube.com/blog/" />
16 <meta name="twitter:title" content=" bLSAG ring signatures overview - arnaucube - blog">
17 <meta name="twitter:description" content="Notes on ring signatures">
18 <meta name="twitter:image" content="https://arnaucube.com/blog/">
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:100%;">
44 <div class="container">
45 <div style="float:left;">
46 <a href="/blog" style="color:#000;display:inline-block;">blog</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;">notes</a>
49 </div>
50 <div style="float:right;">
51 <a href="/" style="color:#000;display:inline-block;margin-right:10px;">arnaucube.com</a>
52 <div class="onoffswitch" style="margin-left:0px;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:0px;max-width:800px;">
65 <h1>bLSAG ring signatures overview</h1>
66
67<p><em>2022-07-20</em></p>
68
69<blockquote>
70<p>Note: I’m not a mathematician, I’m just an amateur on math. These notes are just an attempt to try to sort the notes that I took while learning abut bLSAG.</p>
71</blockquote>
72
73<p><br>
74bLSAG: Back’s Linkable Spontaneous Anonymous Group signatures</p>
75
76<ul>
77<li>signer ambiguity</li>
78<li>linkability</li>
79<li>unforgeability</li>
80</ul>
81
82<h3>Setup</h3>
83
84<p>Let <span class="math inline">\(G\)</span> be the generator of an EC group.
85We use a hash function <span class="math inline">\(\mathcal{H}_p\)</span>, which maps to curve points in EC, and a normal hash <span class="math inline">\(\mathcal{H}_n\)</span>, which maps to <span class="math inline">\(\mathbb{Z}_p\)</span>.
86Signer’s key pair: <span class="math inline">\(k_{\pi}\)</span>, s.t. <span class="math inline">\(K_{\pi} = k_{\pi} \cdot G \in \mathcal{R}\)</span>, with secret index <span class="math inline">\(\pi\)</span>.
87Set of Public Keys: <span class="math inline">\(\mathcal{R} = \{ K_1, K_2, \ldots, K_n \}\)</span></p>
88
89<pre><code class="language-python">def new_key():
90 k = F.random_element()
91 K = g * k # g is the generator of the EC group
92 return K
93</code></pre>
94
95<h3>Signature</h3>
96
97<ol>
98<li><p>compute key image: <span class="math inline">\(\tilde{K} = k_{\pi} \mathcal{H_p} ( K_{\pi}) \in G\)</span></p>
99
100<pre><code class="language-python">key_image = k * hashToPoint(K)
101</code></pre></li>
102
103<li><p>Generate <span class="math inline">\(\alpha \in^R \mathbb{Z}_p\)</span>, and <span class="math inline">\(r_i \in^R \mathbb{Z}_p\)</span>, for <span class="math inline">\(i \in \{1, 2, \ldots, n \}\)</span>, with <span class="math inline">\(i \neq \pi\)</span></p>
104
105<ul>
106<li><p><span class="math inline">\(r_i\)</span> is used for the fake responses</p>
107
108<pre><code class="language-python">a = F.random_element()
109r = [None] * len(R)
110for i in range(0, len(R)):
111 if i==pi:
112 continue
113
114
115 r[i] = mod(F.random_element(), p)
116</code></pre></li>
117</ul></li>
118
119<li><p>Compute <span class="math inline">\(c_{\pi + 1} = \mathcal{H}_n ( m, [\alpha G], [\alpha \mathcal{H}_p(K_{\pi})])\)</span></p>
120
121<pre><code class="language-python">c[pi1] = hash(R, m, a * g, hashToPoint(R[pi]) * a, p)
122</code></pre></li>
123
124<li><p>for <span class="math inline">\(i=\pi + 1, \pi +2, \ldots, n, 1, 2, \ldots, \pi -1\)</span>, calculate, replacing <span class="math inline">\(n+1 \rightarrow 1\)</span>
125$<span class="math inline">\(
126c_{i+1} = \mathcal{H}_n (m, [r_i G + c_i K_i], [r_i \mathcal{H}_p (K_i) + c_i \tilde{K}])
127\)</span>$</p>
128
129<ul>
130<li>Notice that (from step 3 & 4):<br>
131<span class="math inline">\(\alpha \mathcal{H}_p (K_{\pi}) = r_{\pi} \mathcal{H}_p (K_{\pi}) + c_{\pi} \cdot (\tilde{K})\)</span>,<br>
132where <span class="math inline">\(\tilde{K}= k_{\pi} \mathcal{H_p} ( K_{\pi})\)</span>, so:<br>
133<span class="math inline">\(\alpha \mathcal{H}_p (K_{\pi}) = r_{\pi} \mathcal{H}_p (K_{\pi}) + c_{\pi} \cdot (k_{\pi} \mathcal{H}_p(K_{\pi}))\)</span><br>
134which is equal to,<br>
135<span class="math inline">\(\alpha \cdot \mathcal{H}_p (K_{\pi}) = (r_{\pi} + c_{\pi} \cdot k_{\pi}) \cdot \mathcal{H}_p(K_{\pi})\)</span><br>
136From where we can see: <span class="math inline">\(\alpha = r_{\pi} + c_{\pi} \cdot k_{\pi}\)</span><br>
137which we can rearrange to
138<span class="math inline">\(r_{\pi} = \alpha - c_{\pi} \cdot k_{\pi}\)</span>.<br><br></li>
139</ul>
140
141<pre><code class="language-python">for j in range(0, len(R)-1):
142 i = mod(pi1+j, len(R))
143 i1 = mod(pi1+j +1, len(R))
144
145
146 c[i1] = hash(R, m, r[i] * g + c[i] * R[i],
147 r[i] * hashToPoint(R[i]) + c[i] * key_image, p)
148</code></pre></li>
149
150<li><p>Define <span class="math inline">\(r_{\pi} = \alpha - c_{\pi} k_{\pi} \mod{p}\)</span></p></li>
151</ol>
152
153<pre><code class="language-python">r[pi] = mod(a - c[pi] * k, p)
154</code></pre>
155
156<p>Signature: <span class="math inline">\(\sigma(m) = (c_1, r_1, \ldots, r_n)\)</span>, with key image <span class="math inline">\(\tilde{K}\)</span> and ring <span class="math inline">\(\mathcal{R}\)</span>.
157- <span class="math inline">\(len(\sigma(m)) = 1+n\)</span></p>
158
159<pre><code class="language-python">return [c[0], r]
160</code></pre>
161
162<p><br><br><br></p>
163
164<h4>Step by step (simplified):</h4>
165
166<div style="overflow:auto;">
167<div style="width: 60%; float:left; height: 360px; overflow-y:scroll;">
168
169<img src="img/posts/ring-sig/step00.png" style="width:100%;" />
170<img src="img/posts/ring-sig/step00.png" style="width:100%;" />
171<img src="img/posts/ring-sig/step01.png" style="width:100%;" />
172<img src="img/posts/ring-sig/step02.png" style="width:100%;" />
173<img src="img/posts/ring-sig/step03.png" style="width:100%;" />
174<img src="img/posts/ring-sig/step04.png" style="width:100%;" />
175<img src="img/posts/ring-sig/step05.png" style="width:100%;" />
176<img src="img/posts/ring-sig/step06.png" style="width:100%;" />
177
178</div>
179
180<div style="width: 40%; float:right; margin-top:80px;">
181
182 <ul>
183<li>Generate $r_i \in^R \mathbb{Z_p}$</li>
184<li>Compute $c_{i+1}$ from $r_i$</li>
185<li>Link $r_{\pi}$ with $c_{\pi}$</li>
186</ul>
187
188</div>
189</div>
190
191<p><em>You can scroll down the images through the step-by-step diagrams.</em></p>
192
193<p><br></p>
194
195<p>It reminds in some way to the approach to close a box like the one in the picture:
196<img src="img/posts/ring-sig/box-closed.png" alt="" /></p>
197
198<p><br><br><br></p>
199
200<h3>Verification</h3>
201
202<ol>
203<li><p>check <span class="math inline">\(p \tilde{K} \stackrel{?}{=} 0\)</span></p>
204
205<ul>
206<li>to ensure that <span class="math inline">\(\tilde{K} \in G\)</span> (and not in a cofactor group of <span class="math inline">\(G\)</span>)</li>
207</ul></li>
208
209<li><p>for <span class="math inline">\(i = 1, 2, \ldots, n\)</span>, replacing <span class="math inline">\(n+1 \rightarrow 1\)</span>
210$<span class="math inline">\(
211c'_{i+1} = \mathcal{H}_n (m, [r_i G + c_i K_i], [r_i \mathcal{H}_p (K_i) + c_i \tilde{K}])
212\)</span>$</p></li>
213
214<li><p>check <span class="math inline">\(c_1 \stackrel{?}{=} c'_i\)</span></p>
215
216<pre><code class="language-python">c[0] = c1
217for j in range(0, len(R)):
218 i = mod(j, len(R))
219 i1 = mod(j+1, len(R))
220 c[i1] = hash(R, m, r[i] * g + c[i] * R[i],
221 r[i] * hashToPoint(R[i]) + c[i] * key_image, p)
222
223
224assert c1 == c[0]
225</code></pre></li>
226</ol>
227
228<p><br><br></p>
229
230<h2>Links</h2>
231
232<p>Toy implementation:</p>
233
234<ul>
235<li>Sage: <a href="https://github.com/arnaucube/math/blob/master/ring-signatures.sage">https://github.com/arnaucube/math/blob/master/ring-signatures.sage</a></li>
236<li>Rust: <a href="https://github.com/arnaucube/ring-signatures-rs">https://github.com/arnaucube/ring-signatures-rs</a></li>
237</ul>
238
239<p>Resources:</p>
240
241<ul>
242<li><em>“Zero to Monero”</em> - <a href="https://web.getmonero.org/library/Zero-to-Monero-2-0-0.pdf">https://web.getmonero.org/library/Zero-to-Monero-2-0-0.pdf</a>
243(section <em>“3.4 Back’s Linkable Spontaneous Anonymous Group (bLSAG) signatures”</em>)</li>
244</ul>
245
246 </div>
247
248 <footer style="text-align:center; margin-top:100px;margin-bottom:50px;">
249 <div class="container">
250 <br>
251 <a href="/blog">Go to main</a>
252 <br><br>
253 <div class="row">
254 <ul class="list-inline">
255 <li><a href="https://twitter.com/arnaucube"
256 style="color:gray;text-decoration:none;"
257 target="_blank">twitter.com/arnaucube</a>
258 </li>
259 <li><a href="https://github.com/arnaucube"
260 style="color:gray;text-decoration:none;"
261 target="_blank">github.com/arnaucube</a>
262 </li>
263 </ul>
264 </div>
265 <div class="row" style="display:inline-block;">
266 Blog made with <a href="http://github.com/arnaucube/blogo/"
267 target="_blank" style="color: gray;text-decoration:none;">Blogo</a>
268 </div>
269 </div>
270 </footer>
271
272 <script>
273 </script>
274 <script src="js/external-links.js"></script>
275 <script>hljs.initHighlightingOnLoad();</script>
276 <script defer src="js/katex/katex.min.js"></script>
277 <script defer src="js/katex/auto-render.min.js"></script>
278 <script>
279 document.addEventListener("DOMContentLoaded", function() {
280 renderMathInElement(document.body, {
281 displayMode: false,
282 // customised options
283 // • auto-render specific keys, e.g.:
284 delimiters: [
285 {left: '$$', right: '$$', display: true},
286 {left: '$', right: '$', display: false},
287 {left: "\\[", right: "\\]", display: true},
288 {left: "\\(", right: "\\)", display: false},
289 {left: "\\begin{equation}", right: "\\end{equation}", display: true}
290 ],
291 // • rendering keys, e.g.:
292 throwOnError : true
293 });
294 });
295
296 ///
297 let theme = localStorage.getItem("theme");
298 if ((theme === "light-theme")||(theme==null)) {
299 theme = "light-theme";
300 document.getElementById("themeSwitcher").checked = false;
301 } else if (theme === "dark-theme") {
302 theme = "dark-theme";
303 document.getElementById("themeSwitcher").checked = true;
304 }
305 document.body.className = theme;
306 localStorage.setItem("theme", theme);
307
308 function switchTheme() {
309 theme = localStorage.getItem("theme");
310 if (theme === "light-theme") {
311 theme = "dark-theme";
312 document.getElementById("themeSwitcher").checked = true;
313 } else {
314 theme = "light-theme";
315 document.getElementById("themeSwitcher").checked = false;
316 }
317 document.body.className = theme;
318 localStorage.setItem("theme", theme);
319
320 console.log(theme);
321 }
322 </script>
323 <script>
324 function tagLinks(tagName) {
325 var tags = document.getElementsByTagName(tagName);
326 for (var i=0, hElem; hElem = tags[i]; i++) {
327 if (hElem.parentNode.className=="row postThumb") {
328 continue;
329 }
330 hElem.id = hElem.innerHTML.toLowerCase().replace(" ", "-");
331 hElem.innerHTML = "<a style='color:black!important;' href='#"+hElem.id+"'>"+hElem.innerHTML+"</a>";
332 }
333 }
334 tagLinks("h2");
335 tagLinks("h3");
336 tagLinks("h4");
337 tagLinks("h5");
338 </script>
339 <script>
340function generateTOC(tocContainerId = "toc") {
341 const tocContainer = document.getElementById(tocContainerId);
342 if (!tocContainer) return;
343
344 const headings = document.querySelectorAll("h2, h3, h4, h5, h6");
345 if (!headings.length) return;
346
347 // Generate IDs if missing
348 headings.forEach((heading, index) => {
349 if (!heading.id) {
350 heading.id =
351 heading.textContent
352 .trim()
353 .toLowerCase()
354 .replace(/[^\w\s-]/g, "")
355 .replace(/\s+/g, "-") +
356 "-" +
357 index;
358 }
359 });
360
361 const toc = document.createElement("ul");
362 let currentLevel = 1;
363 let currentList = toc;
364 const stack = [toc];
365
366 headings.forEach((heading) => {
367 const level = parseInt(heading.tagName.substring(1), 10);
368
369 const li = document.createElement("li");
370 const a = document.createElement("a");
371
372 a.href = "#" + heading.id;
373 a.textContent = heading.textContent;
374
375 li.appendChild(a);
376
377 if (level > currentLevel) {
378 for (let i = currentLevel; i < level; i++) {
379 const nestedList = document.createElement("ul");
380
381 const lastLi =
382 currentList.lastElementChild ||
383 currentList.appendChild(document.createElement("ul"));
384
385 lastLi.appendChild(nestedList);
386
387 stack.push(nestedList);
388 currentList = nestedList;
389 }
390 } else if (level < currentLevel) {
391 for (let i = currentLevel; i > level; i--) {
392 stack.pop();
393 }
394 currentList = stack[stack.length - 1];
395 }
396
397 currentList.appendChild(li);
398 currentLevel = level;
399 });
400
401 tocContainer.innerHTML = "";
402 tocContainer.appendChild(toc);
403}
404
405document.addEventListener("DOMContentLoaded", () => {
406 generateTOC();
407});
408 </script>
409 <script src="js/mermaid.min.js"></script>
410
411 </body>
412</html>
413