1 /*******************************************************************************
2 StiglicMPC.cc, secure |M|ulti-|P|arty |C|omputation with a deck of cards
3
4 Anton Stiglic: 'Computations with a deck of cards',
5 Theoretical Computer Science, 259 (1-2) (2001) pp. 671-678
6
7 Copyright (C) 2002, 2003, 2005, 2015 Heiko Stamer <HeikoStamer@gmx.net>
8
9 This program is free software; you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation; either version 2 of the License, or
12 (at your option) any later version.
13
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, write to the Free Software
21 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
22 *******************************************************************************/
23
24 // include headers
25 #ifdef HAVE_CONFIG_H
26 #include "libTMCG_config.h"
27 #endif
28 #include "StiglicMPC.hh"
29
MPC_ProveBitCommitment(MPC_Bit & bit,bool b)30 void StiglicMPC::MPC_ProveBitCommitment
31 (MPC_Bit &bit, bool b)
32 {
33 MPC_BitSecret bs;
34 size_t cyc = 0;
35 do
36 cyc = tmcg->TMCG_CreateStackSecret(bs, true, base.size(), vtmf);
37 while ((b && (cyc == 0)) || (!b && (cyc == 1)));
38 bit.clear();
39 tmcg->TMCG_MixStack(base, bit, bs, vtmf);
40
41 for (size_t i = 0; i < participants.size(); i++)
42 {
43 if (i != index)
44 {
45 *participants[i]->out << bit << std::endl << std::flush;
46 tmcg->TMCG_ProveStackEquality(base, bit, bs, true, vtmf,
47 *participants[i]->in, *participants[i]->out);
48 }
49 }
50 }
51
MPC_ProveBitCommitment_Hoogh(MPC_Bit & bit,bool b)52 void StiglicMPC::MPC_ProveBitCommitment_Hoogh
53 (MPC_Bit &bit, bool b)
54 {
55 MPC_BitSecret bs;
56 size_t cyc = 0;
57 do
58 cyc = tmcg->TMCG_CreateStackSecret(bs, true, base.size(), vtmf);
59 while ((b && (cyc == 0)) || (!b && (cyc == 1)));
60 bit.clear();
61 tmcg->TMCG_MixStack(base, bit, bs, vtmf);
62
63 for (size_t i = 0; i < participants.size(); i++)
64 {
65 if (i != index)
66 {
67 *participants[i]->out << bit << std::endl << std::flush;
68 tmcg->TMCG_ProveStackEquality_Hoogh(base, bit, bs, vtmf, vrhe,
69 *participants[i]->in, *participants[i]->out);
70 }
71 }
72 }
73
74
75
MPC_VerifyBitCommitment(MPC_Bit & bit,size_t from)76 bool StiglicMPC::MPC_VerifyBitCommitment
77 (MPC_Bit &bit, size_t from)
78 {
79 *participants[from]->in >> bit;
80
81 if (!participants[from]->in->good())
82 return false;
83 if (bit.size() != 2)
84 return false;
85 if (!tmcg->TMCG_VerifyStackEquality(base, bit, true, vtmf,
86 *participants[from]->in, *participants[from]->out))
87 return false;
88
89 return true;
90 }
91
MPC_VerifyBitCommitment_Hoogh(MPC_Bit & bit,size_t from)92 bool StiglicMPC::MPC_VerifyBitCommitment_Hoogh
93 (MPC_Bit &bit, size_t from)
94 {
95 *participants[from]->in >> bit;
96
97 if (!participants[from]->in->good())
98 return false;
99 if (bit.size() != 2)
100 return false;
101 if (!tmcg->TMCG_VerifyStackEquality_Hoogh(base, bit, vtmf, vrhe,
102 *participants[from]->in, *participants[from]->out))
103 return false;
104
105 return true;
106 }
107
MPC_OpenCardCommitment(const VTMF_Card & card,bool & b)108 bool StiglicMPC::MPC_OpenCardCommitment
109 (const VTMF_Card &card, bool &b)
110 {
111 VTMF_CardSecret cs;
112 tmcg->TMCG_SelfCardSecret(card, vtmf);
113
114 for (size_t i = 0; i < participants.size(); i++)
115 {
116 if (i == index)
117 {
118 // use the non-interactiveness of the proof (only VTMF!)
119 std::stringstream proof;
120 tmcg->TMCG_ProveCardSecret(card, vtmf, proof, proof);
121
122 for (size_t j = 0; j < participants.size(); j++)
123 {
124 if (j != index)
125 *participants[j]->out << proof.str() << std::flush;
126 }
127 }
128 else
129 {
130 if (!tmcg->TMCG_VerifyCardSecret(card, vtmf,
131 *participants[i]->in, *participants[i]->out))
132 return false;
133 }
134 }
135
136 if (tmcg->TMCG_TypeOfCard(card, vtmf) == 0)
137 b = false;
138 else if (tmcg->TMCG_TypeOfCard(card, vtmf) == 1)
139 b = true;
140 else
141 return false;
142
143 return true;
144 }
145
MPC_OpenBitCommitment(const MPC_Bit & bit,bool & b)146 bool StiglicMPC::MPC_OpenBitCommitment
147 (const MPC_Bit &bit, bool &b)
148 {
149 bool cb[2];
150 if (bit.size() != 2)
151 return false;
152 if (!MPC_OpenCardCommitment(bit[0], cb[0]))
153 return false;
154 if (!MPC_OpenCardCommitment(bit[1], cb[1]))
155 return false;
156
157 if (!cb[0] && cb[1])
158 b = false;
159 else if (cb[0] && !cb[1])
160 b = true;
161 else
162 return false;
163
164 return true;
165 }
166
MPC_CyclicShift(TMCG_Stack<VTMF_Card> & result,TMCG_Stack<VTMF_Card> stack)167 bool StiglicMPC::MPC_CyclicShift
168 (TMCG_Stack<VTMF_Card> &result, TMCG_Stack<VTMF_Card> stack)
169 {
170 assert(stack.size() > 0);
171
172 for (size_t i = 0; i < participants.size(); i++)
173 {
174 TMCG_Stack<VTMF_Card> s1;
175 TMCG_StackSecret<VTMF_CardSecret> cs1;
176
177 if (i == index)
178 {
179 tmcg->TMCG_CreateStackSecret(cs1, true, stack.size(), vtmf);
180 tmcg->TMCG_MixStack(stack, s1, cs1, vtmf);
181
182 for (size_t j = 0; j < participants.size(); j++)
183 {
184 if (j != index)
185 {
186 *participants[j]->out << s1 << std::endl << std::flush;
187 tmcg->TMCG_ProveStackEquality(stack, s1, cs1, true, vtmf,
188 *participants[j]->in, *participants[j]->out);
189 }
190 }
191 }
192 else
193 {
194 *participants[i]->in >> s1;
195 if (!participants[i]->in->good())
196 return false;
197 if (!tmcg->TMCG_VerifyStackEquality(stack, s1, true, vtmf,
198 *participants[i]->in, *participants[i]->out))
199 return false;
200 }
201 stack = s1;
202 }
203 result = stack;
204
205 return true;
206 }
207
MPC_CyclicShift_Hoogh(TMCG_Stack<VTMF_Card> & result,TMCG_Stack<VTMF_Card> stack)208 bool StiglicMPC::MPC_CyclicShift_Hoogh
209 (TMCG_Stack<VTMF_Card> &result, TMCG_Stack<VTMF_Card> stack)
210 {
211 assert(stack.size() > 0);
212
213 for (size_t i = 0; i < participants.size(); i++)
214 {
215 TMCG_Stack<VTMF_Card> s1;
216 TMCG_StackSecret<VTMF_CardSecret> cs1;
217
218 if (i == index)
219 {
220 tmcg->TMCG_CreateStackSecret(cs1, true, stack.size(), vtmf);
221 tmcg->TMCG_MixStack(stack, s1, cs1, vtmf);
222
223 for (size_t j = 0; j < participants.size(); j++)
224 {
225 if (j != index)
226 {
227 *participants[j]->out << s1 << std::endl << std::flush;
228 tmcg->TMCG_ProveStackEquality_Hoogh(stack, s1, cs1, vtmf, vrhe,
229 *participants[j]->in, *participants[j]->out);
230 }
231 }
232 }
233 else
234 {
235 *participants[i]->in >> s1;
236 if (!participants[i]->in->good())
237 return false;
238 if (!tmcg->TMCG_VerifyStackEquality_Hoogh(stack, s1, vtmf, vrhe,
239 *participants[i]->in, *participants[i]->out))
240 return false;
241 }
242 stack = s1;
243 }
244 result = stack;
245
246 return true;
247 }
248
MPC_ComputeNEG(MPC_Bit & result,const MPC_Bit bit)249 void StiglicMPC::MPC_ComputeNEG
250 (MPC_Bit &result, const MPC_Bit bit)
251 {
252 assert(bit.size() == 2);
253
254 result.clear(), result.push(bit[1]), result.push(bit[0]);
255 }
256
MPC_ComputeAND(MPC_Bit & result,const MPC_Bit bitA,const MPC_Bit bitB,bool use_vrhe)257 bool StiglicMPC::MPC_ComputeAND
258 (MPC_Bit &result, const MPC_Bit bitA, const MPC_Bit bitB, bool use_vrhe)
259 {
260 assert((bitA.size() == 2) && (bitB.size() == 2));
261
262 TMCG_Stack<VTMF_Card> las_vegas;
263 bool cb[3];
264
265 // step 1. -- place the public and secret cards
266 las_vegas.push(bitA), las_vegas.push(negbase);
267 las_vegas.push(bitB), las_vegas.push(base);
268
269 while (1)
270 {
271 // step 2. and 3. -- apply a cyclic shift
272 if (use_vrhe)
273 {
274 if (!MPC_CyclicShift_Hoogh(las_vegas, las_vegas))
275 return false;
276 }
277 else
278 {
279 if (!MPC_CyclicShift(las_vegas, las_vegas))
280 return false;
281 }
282
283 // step 4. -- turn over the cards
284 if (!MPC_OpenCardCommitment(las_vegas[0], cb[0]))
285 return false;
286 if (!MPC_OpenCardCommitment(las_vegas[1], cb[1]))
287 return false;
288 if ((!cb[0] && cb[1]) || (cb[0] && !cb[1]))
289 {
290 if (!MPC_OpenCardCommitment(las_vegas[2], cb[2]))
291 return false;
292 if ((!cb[0] && cb[1] && cb[2]) || (cb[0] && !cb[1] && !cb[2]))
293 break;
294 }
295 else
296 break;
297 };
298
299 // step 5. -- choose result
300 if (cb[0] && cb[1])
301 {
302 result.clear(), result.push(las_vegas[5]), result.push(las_vegas[6]);
303 }
304 else if (!cb[0] && cb[1] && cb[2])
305 {
306 result.clear(), result.push(las_vegas[6]), result.push(las_vegas[7]);
307 }
308 else if (!cb[0] && !cb[1])
309 {
310 result.clear(), result.push(las_vegas[3]), result.push(las_vegas[4]);
311 }
312 else if (cb[0] && !cb[1] && !cb[2])
313 {
314 result.clear(), result.push(las_vegas[4]), result.push(las_vegas[5]);
315 }
316 else
317 return false;
318
319 return true;
320 }
321
MPC_ComputeOR(MPC_Bit & result,const MPC_Bit & bitA,const MPC_Bit & bitB)322 bool StiglicMPC::MPC_ComputeOR
323 (MPC_Bit &result, const MPC_Bit &bitA, const MPC_Bit &bitB)
324 {
325 MPC_Bit nA, nB, nAB;
326
327 MPC_ComputeNEG(nA, bitA), MPC_ComputeNEG(nB, bitB);
328 if (!MPC_ComputeAND(nAB, nA, nB))
329 return false;
330 MPC_ComputeNEG(result, nAB);
331
332 return true;
333 }
334
MPC_ComputeXOR(MPC_Bit & result,const MPC_Bit & bitA,const MPC_Bit & bitB)335 bool StiglicMPC::MPC_ComputeXOR
336 (MPC_Bit &result, const MPC_Bit &bitA, const MPC_Bit &bitB)
337 {
338 MPC_Bit nA, nB, nAB, AnB;
339
340 MPC_ComputeNEG(nA, bitA), MPC_ComputeNEG(nB, bitB);
341 if (!MPC_ComputeAND(nAB, nA, bitB))
342 return false;
343 if (!MPC_ComputeAND(AnB, bitA, nB))
344 return false;
345 if (!MPC_ComputeOR(result, nAB, AnB))
346 return false;
347
348 return true;
349 }
350
MPC_CopyBitCommitment(MPC_Bit & copy1,MPC_Bit & copy2,const MPC_Bit & bit,bool use_vrhe)351 bool StiglicMPC::MPC_CopyBitCommitment
352 (MPC_Bit ©1, MPC_Bit ©2, const MPC_Bit &bit, bool use_vrhe)
353 {
354 assert(bit.size() == 2);
355
356 TMCG_Stack<VTMF_Card> copyshop, left;
357 bool cb[4];
358
359 // protocol by Crepeau and Kilian (proceedings of Crypto '93)
360 // step 1. -- create a stack with three MPC_Bit (set to true)
361 copyshop.push(negbase), copyshop.push(negbase), copyshop.push(negbase);
362
363 // step 2a. -- apply a cyclic shift to the six rightmost cards
364 if (use_vrhe)
365 {
366 if (!MPC_CyclicShift_Hoogh(copyshop, copyshop))
367 return false;
368 }
369 else
370 {
371 if (!MPC_CyclicShift(copyshop, copyshop))
372 return false;
373 }
374
375 // step 2b. -- create the necessary configuration
376 left.push(bit), left.push(copyshop[0]), left.push(copyshop[1]);
377 copyshop.stack.erase(copyshop.stack.begin(), copyshop.stack.begin() + 2);
378 assert(copyshop.size() == 4);
379
380 // step 3. -- apply a cyclic shift to the four topmost cards
381 if (use_vrhe)
382 {
383 if (!MPC_CyclicShift_Hoogh(left, left))
384 return false;
385 }
386 else
387 {
388 if (!MPC_CyclicShift(left, left))
389 return false;
390 }
391
392 // step 4. -- open the four topmost cards
393 if (!MPC_OpenCardCommitment(left[0], cb[0]))
394 return false;
395 if (!MPC_OpenCardCommitment(left[1], cb[1]))
396 return false;
397 if (!MPC_OpenCardCommitment(left[2], cb[2]))
398 return false;
399 if (!MPC_OpenCardCommitment(left[3], cb[3]))
400 return false;
401 if ((cb[0] && !cb[1] && cb[2] && !cb[3]) ||
402 (!cb[0] && cb[1] && !cb[2] && cb[3]))
403 {
404 copy1.clear(), copy1.push(copyshop[0]), copy1.push(copyshop[1]);
405 copy2.clear(), copy2.push(copyshop[2]), copy2.push(copyshop[3]);
406 }
407 else
408 {
409 copy1.clear(), copy1.push(copyshop[0]), copy1.push(copyshop[1]);
410 copy2.clear(), copy2.push(copyshop[2]), copy2.push(copyshop[3]);
411 MPC_ComputeNEG(copy1, copy1), MPC_ComputeNEG(copy2, copy2);
412 }
413
414 return true;
415 }
416
MPC_RandomBitCommitment(MPC_Bit & result,bool use_vrhe)417 bool StiglicMPC::MPC_RandomBitCommitment
418 (MPC_Bit &result, bool use_vrhe)
419 {
420 result.clear(), result.push(base);
421 if (use_vrhe)
422 {
423 if (!MPC_CyclicShift_Hoogh(result, result))
424 return false;
425 }
426 else
427 {
428 if (!MPC_CyclicShift(result, result))
429 return false;
430 }
431 return true;
432 }
433