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