emp-toolkit / emp-ag2pc Goto Github PK

View Code? Open in Web Editor NEW

22.0 22.0 17.0 101 KB

Authenticated Garbling and Efficient Maliciously Secure Two-Party Computation

License: Other

C++ 96.23% CMake 2.60% Shell 0.89% C 0.28%

emp-ag2pc's People

Contributors

Stargazers

Watchers

Forkers

siamumar zicofish joyofeng bl4ck5un lucyq romilbhardwaj boltlabs-inc mskd12 devjpm themighty1 sarahscheffler tumberger supercrush lgtm-migrator joerowell octaviopk9

emp-ag2pc's Issues

Setting ```__debug``` in ```amortized_2pc.h``` is broken

If one sets __debug in amortized_2pc.h then the code doesn't compile. This is because variables like value aren't defined in the class anymore.

class C2PC does not accept FileIO type

Hi, thank you for your work in MPC research and for making this tool available.
I was trying to compile ag2pc into wasm and realized that I can't pass FileIO here;

emp-ag2pc/emp-ag2pc/2pc.h

Line 28 in b93a28a

C2PC(T * io, int party, BristolFormat * cf) {

Even though it is a template, it only works with NetIO and with FileIO I get erros like:
emp-ag2pc/fpre.h:51:51: error: no member named 'addr' in 'emp::FileIO'

Is it correct that FileIO could be passed to the constructor and then a file could be used for client<->server communication? That would be useful for my project.

Matrix-multiplication can be optimized

In delta-OT, "128 x 168 public matrix times n 168-vectors" can be optimized as "128 x 168 public matrix times n/128 168 x 128 -matrixes"

Run's out of memory for large circuits

The implementation seems to run out of memory during the function independent phase for circuits of size >10^8 ((|C| > 2^27). Is that an expected behaviour? or probably I'm doing something wrong?

on travis failure when that vm does not have bmi2

I found that it is a little bit random whether bmi2 instructions are supported in that Travis VM.

For those VMs that bmi2 is listed in CPU support, they are okay. For others, they fail.

I mean, can ignore Travis for a while

How can both parties receive the output?

Hi Xiao, thanks for your incredible work as always.

As the code is written, it appears that only Bob receives the output. You can test this by setting in[0] = true; after

emp-ag2pc/test/single_execution.h

Line 25 in 163985c

bool *in = new bool[max(cf.n1, cf.n2)];

and removing the condition

emp-ag2pc/test/single_execution.h

Line 32 in 163985c

if(party == BOB and check_output.size() > 0){

and finally running ./bin/simple_circuit 1 12345 & ./bin/simple_circuit 2 12345 (Bob will receive 000010 and Alice 000000).

Of course Bob could just send Alice the output after the protocol is done, but then she wouldn't trust its correctness.

Please let me know if there is an easy way to address this. Thanks!

Encounter Segmentation Fault when using external circuit file

Hi, thanks for the amazing implementation.

I encountered an issue when I try to use an external circuit file, it returns:

connected
Segmentation fault: 11

for both parties' terminals.

I got the file from https://homes.esat.kuleuven.be/~nsmart/MPC/adder_64bit.txt and saved it in emp-tool/circuit/files/bristol_format

Is there any operations required if we use some external circuit files?

Thank you!

emp-ag2pc no longer compiles: small issue with "triple" test

Hi, just wanted to let you know that this recent commit in emp-tool:
emp-toolkit/emp-tool@fa237b7

Has an impact on test/triple.cpp. It's not just the additional port now needed in the HighSpeedNetIO constructor: fpre assumes that the input io has an io->addr, which has been removed from HighSpeedNetIO.

This is the only dependency afaik, it compiles just fine without the "triple" test.

Communication compexity of the independent phase.

In the paper table 10 shows comm.complexity of indep.phase for AES circuit of 2.86MB.
Does this number scale linearly with the amount of AND gates in the circuit or with the amount of ALL gates in the circuit?
E.g. since AES circuit has 6600 AND gates, is it correct to estimate that a 100K circuit will have comm.complexity ~2.86MB*16 ?

incorrect output using ag2pc

Hi, I am trying out ag2pc to run a simple application (addition with values from two party). It turns out that the results after I reveal are incorrect. I have provided codes and detailed description in this repo: https://github.com/kzhong130/emp-ag2pc-max-example. I think this is related to @Issue8 but not exactly the same. Thank you! Please let me know if there is anything unclear.

Overview of this repository

Disclaimer ! !
I couldn't find a documenation for the toolkit library EMP-tool and the emp-ag2pc only has a paper (which I am currently still reading).
Because of a lack of docs and me not really having a very deep understanding of cpp I thus also have trouble understanding the code examples. If you think that both questions below I can answer easily after I have read the paper and listened to Wangs talk, you can also just tell me that. If you otherwise do not think that, then I would really appreciate an answer :) I really would just like to know into what I would like to invest my time into to be able to answer the below questions:

Question 1: (closely related to Q2 below)

How do i get the sample code of an SoK paper referenced here (which computes the dot product of two vectors) run in a malicious setting (so emp-ag2pc) with arbitrary input?

What i already tried:

I compiled this file https://github.com/MPC-SoK/frameworks/blob/master/emp/sh_test/test/innerprod.cpp with non-zero hardcoded input: Executed was actually just this part:
Generated a circuit (with innerprod -m)
Used the boilerplate code from https://github.com/MPC-SoK/frameworks/blob/master/emp/ag_test/test/agmult3.cpp subsituting the circuit text
Compiled, executed, got this:

[1] 1128
connected
./innerprod.circuit.txt
connected
./innerprod.circuit.txt
160 160 16 2602
160 160 16 2602
one time:	1	29461
one time:	2	30879
ABIT	3681
check	1509
permute	476
inde:	1	6023
inde:	2	4668
dep:	2	1279
input size: max 160	160
input for 2: 0
dep:	1	1367
input size: max 160	160
input for 1: 0
online:	1	12
0 no match GT!
1 no match GT!
2 no match GT!
[...]
2589 no match GT!
2600 no match GT!
2601 no match GT!
online:	2	2677
[1]+  Done                    ./bin/customluncher 1 12345

Among this stuff, i don't see my expected result printed.

I get a similar output when I just execute the build from https://github.com/MPC-SoK/frameworks/blob/master/emp/ag_test/test/agmult3.cpp as is.

Question 2 (related to Q1)

Now looking at this sample file:

What (on a high level) is twopc.function_independent(); and twopc.function_dependent(); and twopc.online(in, out); doing.

Should these loops iterate from 1?

It seems like these loops:

emp-ag2pc/emp-ag2pc/fpre.h

Line 314 in 1975122

for(int j = 1; j < bucket_size; ++j) {

emp-ag2pc/emp-ag2pc/fpre.h

Line 327 in 1975122

for(int j = 1; j < bucket_size; ++j) {

Iterate starting from 1.

Is this intentional? Given that the whole array is sent later, this means that an uninitialised value gets written, and I can't see why you'd want to do that...

Input Bits

Hi, I am using your paper and emp-ag2pc tool for a project and I encountered an issue (rather say a doubt). When I am running a simple circuit (just and gates) on inputs of different bits (2 bit for Alice and 1 bit for Bob), I am not getting desired outputs and sometimes segmentation fault error.

Alice input: 1 1
Bob Input: 0

Circuit File:
3 6
2 1 3

2 1 0 2 3 AND
2 1 1 2 4 AND
2 1 0 1 5 AND

I have attached my test file and execution logs.

The expected output is 0 0 1, but with every execution I am getting different outputs.

I am assuming that the order of input wires in the circuit follows from 0 to n-1 for Alice and henceforth for Bob.

Is only BOB getting the answer?

Thanks for making the code and the paper available for this project.

For our own research, we are trying to build upon your work.

Following your instructions and examples, we run the following code on both BOB and ALICE's server.

        C2PC twopc(io, party, &cf);
        twopc.function_independent();
        twopc.function_dependent();
        twopc.online(in, out);

However, looking at ALICE's code path in the online function, we find that ALICE is not computing the circuit and getting the result of the circuit: only BOB does the computation and only BOB gets the answer. So, effectively, in ALICE's case, running the above code sequence, leads to have no result written to out.

Looking at some of the tests you published, it does appear that you check that the output matches your expectations, but only when the user is BOB. That is, we cannot find evidence that you expect ALICE to get the result of the circuit.


	if(party == BOB){ // why only BOB????????????
	        string res = "";
		for(int i = 0; i < 160; ++i)
			res += (out[i]?"1":"0");
		cout << (res == hex_to_binary(string(out3))? "GOOD!":"BAD!")<<endl;
	}

Evidently, we could modify this code so that BOB sends the answer back to ALICE but this implies that ALICE trusts BOB. Another obvious fix is to run the exchange twice, flipping the role of BOB and ALICE, but that does not seem correct.

What if we wish that both parties get the output of the circuit? Could we modify your code, or the way we use your code, to get this desired result?

cc @owenkaser

Alice is party 2 in the circuit?

When using Bristol circuits, Alice's input actually corresponds to the 2nd party while Bob the first. This flip of order is really confusing. If it's intended, it better be clearly stated in the README.

E.g., Here

emp-ag2pc/emp-ag2pc/2pc.h

Lines 320 to 324 in 163985c

 if(party == ALICE) { 

 for(int i = cf->n1; i < cf->n1+cf->n2; ++i) { 

 mask_input[i] = logic_xor(input[i - cf->n1], value[i]); 

 mask_input[i] = logic_xor(mask_input[i], mask[i]); 

 }

, Alice reads n2 bits from the input. The tests didn't catch this because they use the same input from both parties.

About security of using leaky delta OT

Hi,

We are a little confused by the usage of leaky delta OT to generate TinyOT AND triples in the repo.

According to the original paper, the security proof is based on the assumption of a maliciously secure aBit:
https://eprint.iacr.org/2017/030

In the implementation section, you mentioned about using the following paper's approach, which gives a construction from leaky delta OT to non-leaky delta OT:
https://eprint.iacr.org/2016/1069.pdf

But we couldn't find such a construction in the code. The code turns out to directly to use leaky delta OT to construct TinyOT AND triples.

Could you explain this in more detail? Is there a missing reference for the implementation?

transmitting authenticated circuit in online phase

Hi, I'm looking at the online phase

emp-ag2pc/emp-ag2pc/2pc.h

Line 274 in b93a28a

void online (bool * input, bool * output, bool alice_output = false) {

and all I can see is that data related to parties's inputs is transmitted.
The paper says that the authenticated circuit is transmitted in the online phase

...the parties in our protocol use this information in the online phase to
generate a single “authenticated” garbled circuit. As in the semi-honest case, this garbled circuit can then
be transmitted and evaluated in just one additional round.

Am I misunderstanding the paper? At what stage is the authenticated circuit transmitted?

executing circuit error

I'm trying to execute a circuit with two input, flag1: "123456789012345678901234567890" and flag2: "a23456789012345678901234567890". I expect to get a binary result like "01111111111111111111111111111100". However, I got this output instead:

╰─$ ./sha256 1 12345 & ./sha256 2 12345
[1] 668223
connected
/home/chuan/git/emp-ag2pc/bin/circuit.txt
connected
/home/chuan/git/emp-ag2pc/bin/circuit.txt
240 240 32 210
240 240 32 210
one time:       1       24852
one time:       2       25459
ABIT    1033
check   507
permute 276
inde:   1       2218
inde:   2       1710
dep:    2       235
dep:    1       304
123456789012345678901234567890
online: 1       15
a23456789012345678901234567890
online: 2       268
00001111111111111111111111111100
[1]  + 668223 done       ./sha256 1 12345

Besides, sometimes, it shows a kind of randomness:

╭─chuan@cmp ~/git/emp-ag2pc ‹release-2*› 
╰─$ ./run ./bin/sha256 12345
connected
/home/chuan/git/emp-ag2pc/bin/circuit.txt
connected
/home/chuan/git/emp-ag2pc/bin/circuit.txt
240 240 32 210
240 240 32 210
one time:       1       49836
one time:       2       50545
ABIT    1100
check   390
permute 263
inde:   1       2175
inde:   2       1598
dep:    2       267
dep:    1       337

online: 1       22

online: 2       266
10011111111111111111111111111100
╭─chuan@cmp ~/git/emp-ag2pc ‹release-2*› 
╰─$ ./run ./bin/sha256 12345
connected
connected
/home/chuan/git/emp-ag2pc/bin/circuit.txt
/home/chuan/git/emp-ag2pc/bin/circuit.txt
240 240 32 210
240 240 32 210
one time:       1       53497
one time:       2       54495
ABIT    1088
check   430
permute 203
inde:   1       2024
inde:   2       1458
dep:    2       200
dep:    1       234

online: 1       17

online: 2       263
11001111111111111111111111111100

I'm not sure which part is wrong.

Here is my edit on the original code:

/test/sha256.cpp

#include <emp-tool/emp-tool.h>
#include "test/single_execution.h"
using namespace std;
using namespace emp;

int main(int argc, char** argv) {
	int party, port;
	parse_party_and_port(argv, &party, &port);
	NetIO* io = new NetIO(party==ALICE ? nullptr:IP, port);
//	io->set_nodelay();

	string data;
	if (party == ALICE)
	{
		ifstream in("./flag1.txt");
		getline(in, data);
	} else if (party == BOB) {
		ifstream in("./flag2.txt");
		getline(in, data);
	}

	const char * flag = data.c_str();
	test(party, io, "/home/chuan/git/emp-ag2pc/bin/circuit.txt", "", flag); 
	delete io;
	return 0;
}

I added some output on /test/single_execution.h, and a memcpy to setup the bool * in:

#include <emp-tool/emp-tool.h>
#include "emp-ag2pc/emp-ag2pc.h"
using namespace std;
using namespace emp;

inline const char* hex_char_to_bin(char c) {
	switch(toupper(c)) {
		case '0': return "0000";
		case '1': return "0001";
		case '2': return "0010";
		case '3': return "0011";
		case '4': return "0100";
		case '5': return "0101";
		case '6': return "0110";
		case '7': return "0111";
		case '8': return "1000";
		case '9': return "1001";
		case 'A': return "1010";
		case 'B': return "1011";
		case 'C': return "1100";
		case 'D': return "1101";
		case 'E': return "1110";
		case 'F': return "1111";
		default: return "0";
	}
}


inline std::string hex_to_binary(std::string hex) {
	std::string bin;
	for(unsigned i = 0; i != hex.length(); ++i)
		bin += hex_char_to_bin(hex[i]);
	return bin;
}

const string circuit_file_location = macro_xstr(EMP_CIRCUIT_PATH);

template<typename T>
void test(int party, T* io, string name, string check_output = "", const char * flag="") {
	string file = name;//circuit_file_location + name;
	CircuitFile cf(file.c_str());
	auto t1 = clock_start();
	C2PC<T> twopc(io, party, &cf);
	io->flush();
	cout << "one time:\t"<<party<<"\t" <<time_from(t1)<<endl;

	t1 = clock_start();
	twopc.function_independent();
	io->flush();
	cout << "inde:\t"<<party<<"\t"<<time_from(t1)<<endl;

	t1 = clock_start();
	twopc.function_dependent();
	io->flush();
	cout << "dep:\t"<<party<<"\t"<<time_from(t1)<<endl;

	bool *in = new bool[max(cf.n1, cf.n2)];
	bool * out = new bool[cf.n3];
	memset(in, false, max(cf.n1, cf.n2));
	memcpy(in, flag, 30);
	memset(out, false, cf.n3);
	t1 = clock_start();
	twopc.online(in, out);
	cout << (char *)in << endl;
	cout << "online:\t"<<party<<"\t"<<time_from(t1)<<endl;
	if(party == BOB /* and check_output.size() > 0*/){
		string res = "";
		for(int i = 0; i < cf.n3; ++i)
			res += (out[i]?"1":"0");
		cout << res << endl;
		// cout << (res == hex_to_binary(check_output)? "GOOD!":"BAD!")<<endl;
	}
	delete[] in;
	delete[] out;
}

The circuit's c file is:



typedef struct
{
	char a0;
	char a1;
	char a2;
	char a3;
	char a4;
	char a5;
	char a6;
	char a7;
	char a8;
	char a9;
	char a10;
	char a11;
	char a12;
	char a13;
	char a14;
	char a15;
	char a16;
	char a17;
	char a18;
	char a19;
	char a20;
	char a21;
	char a22;
	char a23;
	char a24;
	char a25;
	char a26;
	char a27;
	char a28;
	char a29;
} Array;

int mpc_main(Array INPUT_A, Array INPUT_B)
{
	int result = 0;
	int i = 1;
	if (!(INPUT_A.a0 ^ INPUT_B.a0)){
    	result += i;
	}
	i = i << 1;
	if (!(INPUT_A.a1 ^ INPUT_B.a1)){
		result += i;
	}
	i = i << 1;
	if (!(INPUT_A.a2 ^ INPUT_B.a2)){
		result += i;
	}
	i = i << 1;
	if (!(INPUT_A.a3 ^ INPUT_B.a3)){
		result += i;
	}
	i = i << 1;
	if (!(INPUT_A.a4 ^ INPUT_B.a4)){
		result += i;
	}
	i = i << 1;
	if (!(INPUT_A.a5 ^ INPUT_B.a5)){
		result += i;
	}
	i = i << 1;
	if (!(INPUT_A.a6 ^ INPUT_B.a6)){
		result += i;
	}
	i = i << 1;
	if (!(INPUT_A.a7 ^ INPUT_B.a7)){
		result += i;
	}
	i = i << 1;
	if (!(INPUT_A.a8 ^ INPUT_B.a8)){
		result += i;
	}
	i = i << 1;
	if (!(INPUT_A.a9 ^ INPUT_B.a9)){
		result += i;
	}
	i = i << 1;
	if (!(INPUT_A.a10 ^ INPUT_B.a10)){
		result += i;
	}
	i = i << 1;
	if (!(INPUT_A.a11 ^ INPUT_B.a11)){
		result += i;
	}
	i = i << 1;
	if (!(INPUT_A.a12 ^ INPUT_B.a12)){
		result += i;
	}
	i = i << 1;
	if (!(INPUT_A.a13 ^ INPUT_B.a13)){
		result += i;
	}
	i = i << 1;
	if (!(INPUT_A.a14 ^ INPUT_B.a14)){
		result += i;
	}
	i = i << 1;
	if (!(INPUT_A.a15 ^ INPUT_B.a15)){
		result += i;
	}
	i = i << 1;
	if (!(INPUT_A.a16 ^ INPUT_B.a16)){
		result += i;
	}
	i = i << 1;
	if (!(INPUT_A.a17 ^ INPUT_B.a17)){
		result += i;
	}
	i = i << 1;
	if (!(INPUT_A.a18 ^ INPUT_B.a18)){
		result += i;
	}
	i = i << 1;
	if (!(INPUT_A.a19 ^ INPUT_B.a19)){
		result += i;
	}
	i = i << 1;
	if (!(INPUT_A.a20 ^ INPUT_B.a20)){
		result += i;
	}
	i = i << 1;
	if (!(INPUT_A.a21 ^ INPUT_B.a21)){
		result += i;
	}
	i = i << 1;
	if (!(INPUT_A.a22 ^ INPUT_B.a22)){
		result += i;
	}
	i = i << 1;
	if (!(INPUT_A.a23 ^ INPUT_B.a23)){
		result += i;
	}
	i = i << 1;
	if (!(INPUT_A.a24 ^ INPUT_B.a24)){
		result += i;
	}
	i = i << 1;
	if (!(INPUT_A.a25 ^ INPUT_B.a25)){
		result += i;
	}
	i = i << 1;
	if (!(INPUT_A.a26 ^ INPUT_B.a26)){
		result += i;
	}
	i = i << 1;
	if (!(INPUT_A.a27 ^ INPUT_B.a27)){
		result += i;
	}
	i = i << 1;
	if (!(INPUT_A.a28 ^ INPUT_B.a28)){
		result += i;
	}
	i = i << 1;
	if (!(INPUT_A.a29 ^ INPUT_B.a29)){
		result += i;
	}
	
	return result;
}

and the circuit is:

1114 1594
240 240 32

2 1 7 247 480 XOR
1 1 480 481 INV
2 1 6 246 482 XOR
1 1 482 483 INV
2 1 481 483 484 AND
1 1 484 485 INV
1 1 485 486 INV
2 1 5 245 487 XOR
1 1 487 488 INV
2 1 4 244 489 XOR
1 1 489 490 INV
2 1 488 490 491 AND
1 1 491 492 INV
1 1 492 493 INV
2 1 486 493 494 AND
1 1 494 495 INV
1 1 495 496 INV
2 1 3 243 497 XOR
1 1 497 498 INV
2 1 2 242 499 XOR
1 1 499 500 INV
2 1 498 500 501 AND
1 1 501 502 INV
1 1 502 503 INV
2 1 1 241 504 XOR
1 1 504 505 INV
2 1 0 240 506 XOR
1 1 506 507 INV
2 1 505 507 508 AND
1 1 508 509 INV
1 1 509 510 INV
2 1 503 510 511 AND
1 1 511 512 INV
1 1 512 513 INV
2 1 496 513 514 AND
1 1 514 515 INV
1 1 515 1562 INV
2 1 15 255 516 XOR
1 1 516 517 INV
2 1 14 254 518 XOR
1 1 518 519 INV
2 1 517 519 520 AND
1 1 520 521 INV
1 1 521 522 INV
2 1 13 253 523 XOR
1 1 523 524 INV
2 1 12 252 525 XOR
1 1 525 526 INV
2 1 524 526 527 AND
1 1 527 528 INV
1 1 528 529 INV
2 1 522 529 530 AND
1 1 530 531 INV
1 1 531 532 INV
2 1 11 251 533 XOR
1 1 533 534 INV
2 1 10 250 535 XOR
1 1 535 536 INV
2 1 534 536 537 AND
1 1 537 538 INV
1 1 538 539 INV
2 1 9 249 540 XOR
1 1 540 541 INV
2 1 8 248 542 XOR
1 1 542 543 INV
2 1 541 543 544 AND
1 1 544 545 INV
1 1 545 546 INV
2 1 539 546 547 AND
1 1 547 548 INV
1 1 548 549 INV
2 1 532 549 550 AND
1 1 550 551 INV
1 1 551 1563 INV
2 1 23 263 552 XOR
1 1 552 553 INV
2 1 22 262 554 XOR
1 1 554 555 INV
2 1 553 555 556 AND
1 1 556 557 INV
1 1 557 558 INV
2 1 21 261 559 XOR
1 1 559 560 INV
2 1 20 260 561 XOR
1 1 561 562 INV
2 1 560 562 563 AND
1 1 563 564 INV
1 1 564 565 INV
2 1 558 565 566 AND
1 1 566 567 INV
1 1 567 568 INV
2 1 19 259 569 XOR
1 1 569 570 INV
2 1 18 258 571 XOR
1 1 571 572 INV
2 1 570 572 573 AND
1 1 573 574 INV
1 1 574 575 INV
2 1 17 257 576 XOR
1 1 576 577 INV
2 1 16 256 578 XOR
1 1 578 579 INV
2 1 577 579 580 AND
1 1 580 581 INV
1 1 581 582 INV
2 1 575 582 583 AND
1 1 583 584 INV
1 1 584 585 INV
2 1 568 585 586 AND
1 1 586 587 INV
1 1 587 1564 INV
2 1 31 271 588 XOR
1 1 588 589 INV
2 1 30 270 590 XOR
1 1 590 591 INV
2 1 589 591 592 AND
1 1 592 593 INV
1 1 593 594 INV
2 1 29 269 595 XOR
1 1 595 596 INV
2 1 28 268 597 XOR
1 1 597 598 INV
2 1 596 598 599 AND
1 1 599 600 INV
1 1 600 601 INV
2 1 594 601 602 AND
1 1 602 603 INV
1 1 603 604 INV
2 1 27 267 605 XOR
1 1 605 606 INV
2 1 26 266 607 XOR
1 1 607 608 INV
2 1 606 608 609 AND
1 1 609 610 INV
1 1 610 611 INV
2 1 25 265 612 XOR
1 1 612 613 INV
2 1 24 264 614 XOR
1 1 614 615 INV
2 1 613 615 616 AND
1 1 616 617 INV
1 1 617 618 INV
2 1 611 618 619 AND
1 1 619 620 INV
1 1 620 621 INV
2 1 604 621 622 AND
1 1 622 623 INV
1 1 623 1565 INV
2 1 39 279 624 XOR
1 1 624 625 INV
2 1 38 278 626 XOR
1 1 626 627 INV
2 1 625 627 628 AND
1 1 628 629 INV
1 1 629 630 INV
2 1 37 277 631 XOR
1 1 631 632 INV
2 1 36 276 633 XOR
1 1 633 634 INV
2 1 632 634 635 AND
1 1 635 636 INV
1 1 636 637 INV
2 1 630 637 638 AND
1 1 638 639 INV
1 1 639 640 INV
2 1 35 275 641 XOR
1 1 641 642 INV
2 1 34 274 643 XOR
1 1 643 644 INV
2 1 642 644 645 AND
1 1 645 646 INV
1 1 646 647 INV
2 1 33 273 648 XOR
1 1 648 649 INV
2 1 32 272 650 XOR
1 1 650 651 INV
2 1 649 651 652 AND
1 1 652 653 INV
1 1 653 654 INV
2 1 647 654 655 AND
1 1 655 656 INV
1 1 656 657 INV
2 1 640 657 658 AND
1 1 658 659 INV
1 1 659 1566 INV
2 1 47 287 660 XOR
1 1 660 661 INV
2 1 46 286 662 XOR
1 1 662 663 INV
2 1 661 663 664 AND
1 1 664 665 INV
1 1 665 666 INV
2 1 45 285 667 XOR
1 1 667 668 INV
2 1 44 284 669 XOR
1 1 669 670 INV
2 1 668 670 671 AND
1 1 671 672 INV
1 1 672 673 INV
2 1 666 673 674 AND
1 1 674 675 INV
1 1 675 676 INV
2 1 43 283 677 XOR
1 1 677 678 INV
2 1 42 282 679 XOR
1 1 679 680 INV
2 1 678 680 681 AND
1 1 681 682 INV
1 1 682 683 INV
2 1 41 281 684 XOR
1 1 684 685 INV
2 1 40 280 686 XOR
1 1 686 687 INV
2 1 685 687 688 AND
1 1 688 689 INV
1 1 689 690 INV
2 1 683 690 691 AND
1 1 691 692 INV
1 1 692 693 INV
2 1 676 693 694 AND
1 1 694 695 INV
1 1 695 1567 INV
2 1 55 295 696 XOR
1 1 696 697 INV
2 1 54 294 698 XOR
1 1 698 699 INV
2 1 697 699 700 AND
1 1 700 701 INV
1 1 701 702 INV
2 1 53 293 703 XOR
1 1 703 704 INV
2 1 52 292 705 XOR
1 1 705 706 INV
2 1 704 706 707 AND
1 1 707 708 INV
1 1 708 709 INV
2 1 702 709 710 AND
1 1 710 711 INV
1 1 711 712 INV
2 1 51 291 713 XOR
1 1 713 714 INV
2 1 50 290 715 XOR
1 1 715 716 INV
2 1 714 716 717 AND
1 1 717 718 INV
1 1 718 719 INV
2 1 49 289 720 XOR
1 1 720 721 INV
2 1 48 288 722 XOR
1 1 722 723 INV
2 1 721 723 724 AND
1 1 724 725 INV
1 1 725 726 INV
2 1 719 726 727 AND
1 1 727 728 INV
1 1 728 729 INV
2 1 712 729 730 AND
1 1 730 731 INV
1 1 731 1568 INV
2 1 63 303 732 XOR
1 1 732 733 INV
2 1 62 302 734 XOR
1 1 734 735 INV
2 1 733 735 736 AND
1 1 736 737 INV
1 1 737 738 INV
2 1 61 301 739 XOR
1 1 739 740 INV
2 1 60 300 741 XOR
1 1 741 742 INV
2 1 740 742 743 AND
1 1 743 744 INV
1 1 744 745 INV
2 1 738 745 746 AND
1 1 746 747 INV
1 1 747 748 INV
2 1 59 299 749 XOR
1 1 749 750 INV
2 1 58 298 751 XOR
1 1 751 752 INV
2 1 750 752 753 AND
1 1 753 754 INV
1 1 754 755 INV
2 1 57 297 756 XOR
1 1 756 757 INV
2 1 56 296 758 XOR
1 1 758 759 INV
2 1 757 759 760 AND
1 1 760 761 INV
1 1 761 762 INV
2 1 755 762 763 AND
1 1 763 764 INV
1 1 764 765 INV
2 1 748 765 766 AND
1 1 766 767 INV
1 1 767 1569 INV
2 1 71 311 768 XOR
1 1 768 769 INV
2 1 70 310 770 XOR
1 1 770 771 INV
2 1 769 771 772 AND
1 1 772 773 INV
1 1 773 774 INV
2 1 69 309 775 XOR
1 1 775 776 INV
2 1 68 308 777 XOR
1 1 777 778 INV
2 1 776 778 779 AND
1 1 779 780 INV
1 1 780 781 INV
2 1 774 781 782 AND
1 1 782 783 INV
1 1 783 784 INV
2 1 67 307 785 XOR
1 1 785 786 INV
2 1 66 306 787 XOR
1 1 787 788 INV
2 1 786 788 789 AND
1 1 789 790 INV
1 1 790 791 INV
2 1 65 305 792 XOR
1 1 792 793 INV
2 1 64 304 794 XOR
1 1 794 795 INV
2 1 793 795 796 AND
1 1 796 797 INV
1 1 797 798 INV
2 1 791 798 799 AND
1 1 799 800 INV
1 1 800 801 INV
2 1 784 801 802 AND
1 1 802 803 INV
1 1 803 1570 INV
2 1 79 319 804 XOR
1 1 804 805 INV
2 1 78 318 806 XOR
1 1 806 807 INV
2 1 805 807 808 AND
1 1 808 809 INV
1 1 809 810 INV
2 1 77 317 811 XOR
1 1 811 812 INV
2 1 76 316 813 XOR
1 1 813 814 INV
2 1 812 814 815 AND
1 1 815 816 INV
1 1 816 817 INV
2 1 810 817 818 AND
1 1 818 819 INV
1 1 819 820 INV
2 1 75 315 821 XOR
1 1 821 822 INV
2 1 74 314 823 XOR
1 1 823 824 INV
2 1 822 824 825 AND
1 1 825 826 INV
1 1 826 827 INV
2 1 73 313 828 XOR
1 1 828 829 INV
2 1 72 312 830 XOR
1 1 830 831 INV
2 1 829 831 832 AND
1 1 832 833 INV
1 1 833 834 INV
2 1 827 834 835 AND
1 1 835 836 INV
1 1 836 837 INV
2 1 820 837 838 AND
1 1 838 839 INV
1 1 839 1571 INV
2 1 87 327 840 XOR
1 1 840 841 INV
2 1 86 326 842 XOR
1 1 842 843 INV
2 1 841 843 844 AND
1 1 844 845 INV
1 1 845 846 INV
2 1 85 325 847 XOR
1 1 847 848 INV
2 1 84 324 849 XOR
1 1 849 850 INV
2 1 848 850 851 AND
1 1 851 852 INV
1 1 852 853 INV
2 1 846 853 854 AND
1 1 854 855 INV
1 1 855 856 INV
2 1 83 323 857 XOR
1 1 857 858 INV
2 1 82 322 859 XOR
1 1 859 860 INV
2 1 858 860 861 AND
1 1 861 862 INV
1 1 862 863 INV
2 1 81 321 864 XOR
1 1 864 865 INV
2 1 80 320 866 XOR
1 1 866 867 INV
2 1 865 867 868 AND
1 1 868 869 INV
1 1 869 870 INV
2 1 863 870 871 AND
1 1 871 872 INV
1 1 872 873 INV
2 1 856 873 874 AND
1 1 874 875 INV
1 1 875 1572 INV
2 1 95 335 876 XOR
1 1 876 877 INV
2 1 94 334 878 XOR
1 1 878 879 INV
2 1 877 879 880 AND
1 1 880 881 INV
1 1 881 882 INV
2 1 93 333 883 XOR
1 1 883 884 INV
2 1 92 332 885 XOR
1 1 885 886 INV
2 1 884 886 887 AND
1 1 887 888 INV
1 1 888 889 INV
2 1 882 889 890 AND
1 1 890 891 INV
1 1 891 892 INV
2 1 91 331 893 XOR
1 1 893 894 INV
2 1 90 330 895 XOR
1 1 895 896 INV
2 1 894 896 897 AND
1 1 897 898 INV
1 1 898 899 INV
2 1 89 329 900 XOR
1 1 900 901 INV
2 1 88 328 902 XOR
1 1 902 903 INV
2 1 901 903 904 AND
1 1 904 905 INV
1 1 905 906 INV
2 1 899 906 907 AND
1 1 907 908 INV
1 1 908 909 INV
2 1 892 909 910 AND
1 1 910 911 INV
1 1 911 1573 INV
2 1 103 343 912 XOR
1 1 912 913 INV
2 1 102 342 914 XOR
1 1 914 915 INV
2 1 913 915 916 AND
1 1 916 917 INV
1 1 917 918 INV
2 1 101 341 919 XOR
1 1 919 920 INV
2 1 100 340 921 XOR
1 1 921 922 INV
2 1 920 922 923 AND
1 1 923 924 INV
1 1 924 925 INV
2 1 918 925 926 AND
1 1 926 927 INV
1 1 927 928 INV
2 1 99 339 929 XOR
1 1 929 930 INV
2 1 98 338 931 XOR
1 1 931 932 INV
2 1 930 932 933 AND
1 1 933 934 INV
1 1 934 935 INV
2 1 97 337 936 XOR
1 1 936 937 INV
2 1 96 336 938 XOR
1 1 938 939 INV
2 1 937 939 940 AND
1 1 940 941 INV
1 1 941 942 INV
2 1 935 942 943 AND
1 1 943 944 INV
1 1 944 945 INV
2 1 928 945 946 AND
1 1 946 947 INV
1 1 947 1574 INV
2 1 111 351 948 XOR
1 1 948 949 INV
2 1 110 350 950 XOR
1 1 950 951 INV
2 1 949 951 952 AND
1 1 952 953 INV
1 1 953 954 INV
2 1 109 349 955 XOR
1 1 955 956 INV
2 1 108 348 957 XOR
1 1 957 958 INV
2 1 956 958 959 AND
1 1 959 960 INV
1 1 960 961 INV
2 1 954 961 962 AND
1 1 962 963 INV
1 1 963 964 INV
2 1 107 347 965 XOR
1 1 965 966 INV
2 1 106 346 967 XOR
1 1 967 968 INV
2 1 966 968 969 AND
1 1 969 970 INV
1 1 970 971 INV
2 1 105 345 972 XOR
1 1 972 973 INV
2 1 104 344 974 XOR
1 1 974 975 INV
2 1 973 975 976 AND
1 1 976 977 INV
1 1 977 978 INV
2 1 971 978 979 AND
1 1 979 980 INV
1 1 980 981 INV
2 1 964 981 982 AND
1 1 982 983 INV
1 1 983 1575 INV
2 1 119 359 984 XOR
1 1 984 985 INV
2 1 118 358 986 XOR
1 1 986 987 INV
2 1 985 987 988 AND
1 1 988 989 INV
1 1 989 990 INV
2 1 117 357 991 XOR
1 1 991 992 INV
2 1 116 356 993 XOR
1 1 993 994 INV
2 1 992 994 995 AND
1 1 995 996 INV
1 1 996 997 INV
2 1 990 997 998 AND
1 1 998 999 INV
1 1 999 1000 INV
2 1 115 355 1001 XOR
1 1 1001 1002 INV
2 1 114 354 1003 XOR
1 1 1003 1004 INV
2 1 1002 1004 1005 AND
1 1 1005 1006 INV
1 1 1006 1007 INV
2 1 113 353 1008 XOR
1 1 1008 1009 INV
2 1 112 352 1010 XOR
1 1 1010 1011 INV
2 1 1009 1011 1012 AND
1 1 1012 1013 INV
1 1 1013 1014 INV
2 1 1007 1014 1015 AND
1 1 1015 1016 INV
1 1 1016 1017 INV
2 1 1000 1017 1018 AND
1 1 1018 1019 INV
1 1 1019 1576 INV
2 1 127 367 1020 XOR
1 1 1020 1021 INV
2 1 126 366 1022 XOR
1 1 1022 1023 INV
2 1 1021 1023 1024 AND
1 1 1024 1025 INV
1 1 1025 1026 INV
2 1 125 365 1027 XOR
1 1 1027 1028 INV
2 1 124 364 1029 XOR
1 1 1029 1030 INV
2 1 1028 1030 1031 AND
1 1 1031 1032 INV
1 1 1032 1033 INV
2 1 1026 1033 1034 AND
1 1 1034 1035 INV
1 1 1035 1036 INV
2 1 123 363 1037 XOR
1 1 1037 1038 INV
2 1 122 362 1039 XOR
1 1 1039 1040 INV
2 1 1038 1040 1041 AND
1 1 1041 1042 INV
1 1 1042 1043 INV
2 1 121 361 1044 XOR
1 1 1044 1045 INV
2 1 120 360 1046 XOR
1 1 1046 1047 INV
2 1 1045 1047 1048 AND
1 1 1048 1049 INV
1 1 1049 1050 INV
2 1 1043 1050 1051 AND
1 1 1051 1052 INV
1 1 1052 1053 INV
2 1 1036 1053 1054 AND
1 1 1054 1055 INV
1 1 1055 1577 INV
2 1 135 375 1056 XOR
1 1 1056 1057 INV
2 1 134 374 1058 XOR
1 1 1058 1059 INV
2 1 1057 1059 1060 AND
1 1 1060 1061 INV
1 1 1061 1062 INV
2 1 133 373 1063 XOR
1 1 1063 1064 INV
2 1 132 372 1065 XOR
1 1 1065 1066 INV
2 1 1064 1066 1067 AND
1 1 1067 1068 INV
1 1 1068 1069 INV
2 1 1062 1069 1070 AND
1 1 1070 1071 INV
1 1 1071 1072 INV
2 1 131 371 1073 XOR
1 1 1073 1074 INV
2 1 130 370 1075 XOR
1 1 1075 1076 INV
2 1 1074 1076 1077 AND
1 1 1077 1078 INV
1 1 1078 1079 INV
2 1 129 369 1080 XOR
1 1 1080 1081 INV
2 1 128 368 1082 XOR
1 1 1082 1083 INV
2 1 1081 1083 1084 AND
1 1 1084 1085 INV
1 1 1085 1086 INV
2 1 1079 1086 1087 AND
1 1 1087 1088 INV
1 1 1088 1089 INV
2 1 1072 1089 1090 AND
1 1 1090 1091 INV
1 1 1091 1578 INV
2 1 143 383 1092 XOR
1 1 1092 1093 INV
2 1 142 382 1094 XOR
1 1 1094 1095 INV
2 1 1093 1095 1096 AND
1 1 1096 1097 INV
1 1 1097 1098 INV
2 1 141 381 1099 XOR
1 1 1099 1100 INV
2 1 140 380 1101 XOR
1 1 1101 1102 INV
2 1 1100 1102 1103 AND
1 1 1103 1104 INV
1 1 1104 1105 INV
2 1 1098 1105 1106 AND
1 1 1106 1107 INV
1 1 1107 1108 INV
2 1 139 379 1109 XOR
1 1 1109 1110 INV
2 1 138 378 1111 XOR
1 1 1111 1112 INV
2 1 1110 1112 1113 AND
1 1 1113 1114 INV
1 1 1114 1115 INV
2 1 137 377 1116 XOR
1 1 1116 1117 INV
2 1 136 376 1118 XOR
1 1 1118 1119 INV
2 1 1117 1119 1120 AND
1 1 1120 1121 INV
1 1 1121 1122 INV
2 1 1115 1122 1123 AND
1 1 1123 1124 INV
1 1 1124 1125 INV
2 1 1108 1125 1126 AND
1 1 1126 1127 INV
1 1 1127 1579 INV
2 1 151 391 1128 XOR
1 1 1128 1129 INV
2 1 150 390 1130 XOR
1 1 1130 1131 INV
2 1 1129 1131 1132 AND
1 1 1132 1133 INV
1 1 1133 1134 INV
2 1 149 389 1135 XOR
1 1 1135 1136 INV
2 1 148 388 1137 XOR
1 1 1137 1138 INV
2 1 1136 1138 1139 AND
1 1 1139 1140 INV
1 1 1140 1141 INV
2 1 1134 1141 1142 AND
1 1 1142 1143 INV
1 1 1143 1144 INV
2 1 147 387 1145 XOR
1 1 1145 1146 INV
2 1 146 386 1147 XOR
1 1 1147 1148 INV
2 1 1146 1148 1149 AND
1 1 1149 1150 INV
1 1 1150 1151 INV
2 1 145 385 1152 XOR
1 1 1152 1153 INV
2 1 144 384 1154 XOR
1 1 1154 1155 INV
2 1 1153 1155 1156 AND
1 1 1156 1157 INV
1 1 1157 1158 INV
2 1 1151 1158 1159 AND
1 1 1159 1160 INV
1 1 1160 1161 INV
2 1 1144 1161 1162 AND
1 1 1162 1163 INV
1 1 1163 1580 INV
2 1 159 399 1164 XOR
1 1 1164 1165 INV
2 1 158 398 1166 XOR
1 1 1166 1167 INV
2 1 1165 1167 1168 AND
1 1 1168 1169 INV
1 1 1169 1170 INV
2 1 157 397 1171 XOR
1 1 1171 1172 INV
2 1 156 396 1173 XOR
1 1 1173 1174 INV
2 1 1172 1174 1175 AND
1 1 1175 1176 INV
1 1 1176 1177 INV
2 1 1170 1177 1178 AND
1 1 1178 1179 INV
1 1 1179 1180 INV
2 1 155 395 1181 XOR
1 1 1181 1182 INV
2 1 154 394 1183 XOR
1 1 1183 1184 INV
2 1 1182 1184 1185 AND
1 1 1185 1186 INV
1 1 1186 1187 INV
2 1 153 393 1188 XOR
1 1 1188 1189 INV
2 1 152 392 1190 XOR
1 1 1190 1191 INV
2 1 1189 1191 1192 AND
1 1 1192 1193 INV
1 1 1193 1194 INV
2 1 1187 1194 1195 AND
1 1 1195 1196 INV
1 1 1196 1197 INV
2 1 1180 1197 1198 AND
1 1 1198 1199 INV
1 1 1199 1581 INV
2 1 167 407 1200 XOR
1 1 1200 1201 INV
2 1 166 406 1202 XOR
1 1 1202 1203 INV
2 1 1201 1203 1204 AND
1 1 1204 1205 INV
1 1 1205 1206 INV
2 1 165 405 1207 XOR
1 1 1207 1208 INV
2 1 164 404 1209 XOR
1 1 1209 1210 INV
2 1 1208 1210 1211 AND
1 1 1211 1212 INV
1 1 1212 1213 INV
2 1 1206 1213 1214 AND
1 1 1214 1215 INV
1 1 1215 1216 INV
2 1 163 403 1217 XOR
1 1 1217 1218 INV
2 1 162 402 1219 XOR
1 1 1219 1220 INV
2 1 1218 1220 1221 AND
1 1 1221 1222 INV
1 1 1222 1223 INV
2 1 161 401 1224 XOR
1 1 1224 1225 INV
2 1 160 400 1226 XOR
1 1 1226 1227 INV
2 1 1225 1227 1228 AND
1 1 1228 1229 INV
1 1 1229 1230 INV
2 1 1223 1230 1231 AND
1 1 1231 1232 INV
1 1 1232 1233 INV
2 1 1216 1233 1234 AND
1 1 1234 1235 INV
1 1 1235 1582 INV
2 1 175 415 1236 XOR
1 1 1236 1237 INV
2 1 174 414 1238 XOR
1 1 1238 1239 INV
2 1 1237 1239 1240 AND
1 1 1240 1241 INV
1 1 1241 1242 INV
2 1 173 413 1243 XOR
1 1 1243 1244 INV
2 1 172 412 1245 XOR
1 1 1245 1246 INV
2 1 1244 1246 1247 AND
1 1 1247 1248 INV
1 1 1248 1249 INV
2 1 1242 1249 1250 AND
1 1 1250 1251 INV
1 1 1251 1252 INV
2 1 171 411 1253 XOR
1 1 1253 1254 INV
2 1 170 410 1255 XOR
1 1 1255 1256 INV
2 1 1254 1256 1257 AND
1 1 1257 1258 INV
1 1 1258 1259 INV
2 1 169 409 1260 XOR
1 1 1260 1261 INV
2 1 168 408 1262 XOR
1 1 1262 1263 INV
2 1 1261 1263 1264 AND
1 1 1264 1265 INV
1 1 1265 1266 INV
2 1 1259 1266 1267 AND
1 1 1267 1268 INV
1 1 1268 1269 INV
2 1 1252 1269 1270 AND
1 1 1270 1271 INV
1 1 1271 1583 INV
2 1 183 423 1272 XOR
1 1 1272 1273 INV
2 1 182 422 1274 XOR
1 1 1274 1275 INV
2 1 1273 1275 1276 AND
1 1 1276 1277 INV
1 1 1277 1278 INV
2 1 181 421 1279 XOR
1 1 1279 1280 INV
2 1 180 420 1281 XOR
1 1 1281 1282 INV
2 1 1280 1282 1283 AND
1 1 1283 1284 INV
1 1 1284 1285 INV
2 1 1278 1285 1286 AND
1 1 1286 1287 INV
1 1 1287 1288 INV
2 1 179 419 1289 XOR
1 1 1289 1290 INV
2 1 178 418 1291 XOR
1 1 1291 1292 INV
2 1 1290 1292 1293 AND
1 1 1293 1294 INV
1 1 1294 1295 INV
2 1 177 417 1296 XOR
1 1 1296 1297 INV
2 1 176 416 1298 XOR
1 1 1298 1299 INV
2 1 1297 1299 1300 AND
1 1 1300 1301 INV
1 1 1301 1302 INV
2 1 1295 1302 1303 AND
1 1 1303 1304 INV
1 1 1304 1305 INV
2 1 1288 1305 1306 AND
1 1 1306 1307 INV
1 1 1307 1584 INV
2 1 191 431 1308 XOR
1 1 1308 1309 INV
2 1 190 430 1310 XOR
1 1 1310 1311 INV
2 1 1309 1311 1312 AND
1 1 1312 1313 INV
1 1 1313 1314 INV
2 1 189 429 1315 XOR
1 1 1315 1316 INV
2 1 188 428 1317 XOR
1 1 1317 1318 INV
2 1 1316 1318 1319 AND
1 1 1319 1320 INV
1 1 1320 1321 INV
2 1 1314 1321 1322 AND
1 1 1322 1323 INV
1 1 1323 1324 INV
2 1 187 427 1325 XOR
1 1 1325 1326 INV
2 1 186 426 1327 XOR
1 1 1327 1328 INV
2 1 1326 1328 1329 AND
1 1 1329 1330 INV
1 1 1330 1331 INV
2 1 185 425 1332 XOR
1 1 1332 1333 INV
2 1 184 424 1334 XOR
1 1 1334 1335 INV
2 1 1333 1335 1336 AND
1 1 1336 1337 INV
1 1 1337 1338 INV
2 1 1331 1338 1339 AND
1 1 1339 1340 INV
1 1 1340 1341 INV
2 1 1324 1341 1342 AND
1 1 1342 1343 INV
1 1 1343 1585 INV
2 1 199 439 1344 XOR
1 1 1344 1345 INV
2 1 198 438 1346 XOR
1 1 1346 1347 INV
2 1 1345 1347 1348 AND
1 1 1348 1349 INV
1 1 1349 1350 INV
2 1 197 437 1351 XOR
1 1 1351 1352 INV
2 1 196 436 1353 XOR
1 1 1353 1354 INV
2 1 1352 1354 1355 AND
1 1 1355 1356 INV
1 1 1356 1357 INV
2 1 1350 1357 1358 AND
1 1 1358 1359 INV
1 1 1359 1360 INV
2 1 195 435 1361 XOR
1 1 1361 1362 INV
2 1 194 434 1363 XOR
1 1 1363 1364 INV
2 1 1362 1364 1365 AND
1 1 1365 1366 INV
1 1 1366 1367 INV
2 1 193 433 1368 XOR
1 1 1368 1369 INV
2 1 192 432 1370 XOR
1 1 1370 1371 INV
2 1 1369 1371 1372 AND
1 1 1372 1373 INV
1 1 1373 1374 INV
2 1 1367 1374 1375 AND
1 1 1375 1376 INV
1 1 1376 1377 INV
2 1 1360 1377 1378 AND
1 1 1378 1379 INV
1 1 1379 1586 INV
2 1 207 447 1380 XOR
1 1 1380 1381 INV
2 1 206 446 1382 XOR
1 1 1382 1383 INV
2 1 1381 1383 1384 AND
1 1 1384 1385 INV
1 1 1385 1386 INV
2 1 205 445 1387 XOR
1 1 1387 1388 INV
2 1 204 444 1389 XOR
1 1 1389 1390 INV
2 1 1388 1390 1391 AND
1 1 1391 1392 INV
1 1 1392 1393 INV
2 1 1386 1393 1394 AND
1 1 1394 1395 INV
1 1 1395 1396 INV
2 1 203 443 1397 XOR
1 1 1397 1398 INV
2 1 202 442 1399 XOR
1 1 1399 1400 INV
2 1 1398 1400 1401 AND
1 1 1401 1402 INV
1 1 1402 1403 INV
2 1 201 441 1404 XOR
1 1 1404 1405 INV
2 1 200 440 1406 XOR
1 1 1406 1407 INV
2 1 1405 1407 1408 AND
1 1 1408 1409 INV
1 1 1409 1410 INV
2 1 1403 1410 1411 AND
1 1 1411 1412 INV
1 1 1412 1413 INV
2 1 1396 1413 1414 AND
1 1 1414 1415 INV
1 1 1415 1587 INV
2 1 215 455 1416 XOR
1 1 1416 1417 INV
2 1 214 454 1418 XOR
1 1 1418 1419 INV
2 1 1417 1419 1420 AND
1 1 1420 1421 INV
1 1 1421 1422 INV
2 1 213 453 1423 XOR
1 1 1423 1424 INV
2 1 212 452 1425 XOR
1 1 1425 1426 INV
2 1 1424 1426 1427 AND
1 1 1427 1428 INV
1 1 1428 1429 INV
2 1 1422 1429 1430 AND
1 1 1430 1431 INV
1 1 1431 1432 INV
2 1 211 451 1433 XOR
1 1 1433 1434 INV
2 1 210 450 1435 XOR
1 1 1435 1436 INV
2 1 1434 1436 1437 AND
1 1 1437 1438 INV
1 1 1438 1439 INV
2 1 209 449 1440 XOR
1 1 1440 1441 INV
2 1 208 448 1442 XOR
1 1 1442 1443 INV
2 1 1441 1443 1444 AND
1 1 1444 1445 INV
1 1 1445 1446 INV
2 1 1439 1446 1447 AND
1 1 1447 1448 INV
1 1 1448 1449 INV
2 1 1432 1449 1450 AND
1 1 1450 1451 INV
1 1 1451 1588 INV
2 1 223 463 1452 XOR
1 1 1452 1453 INV
2 1 222 462 1454 XOR
1 1 1454 1455 INV
2 1 1453 1455 1456 AND
1 1 1456 1457 INV
1 1 1457 1458 INV
2 1 221 461 1459 XOR
1 1 1459 1460 INV
2 1 220 460 1461 XOR
1 1 1461 1462 INV
2 1 1460 1462 1463 AND
1 1 1463 1464 INV
1 1 1464 1465 INV
2 1 1458 1465 1466 AND
1 1 1466 1467 INV
1 1 1467 1468 INV
2 1 219 459 1469 XOR
1 1 1469 1470 INV
2 1 218 458 1471 XOR
1 1 1471 1472 INV
2 1 1470 1472 1473 AND
1 1 1473 1474 INV
1 1 1474 1475 INV
2 1 217 457 1476 XOR
1 1 1476 1477 INV
2 1 216 456 1478 XOR
1 1 1478 1479 INV
2 1 1477 1479 1480 AND
1 1 1480 1481 INV
1 1 1481 1482 INV
2 1 1475 1482 1483 AND
1 1 1483 1484 INV
1 1 1484 1485 INV
2 1 1468 1485 1486 AND
1 1 1486 1487 INV
1 1 1487 1589 INV
2 1 231 471 1488 XOR
1 1 1488 1489 INV
2 1 230 470 1490 XOR
1 1 1490 1491 INV
2 1 1489 1491 1492 AND
1 1 1492 1493 INV
1 1 1493 1494 INV
2 1 229 469 1495 XOR
1 1 1495 1496 INV
2 1 228 468 1497 XOR
1 1 1497 1498 INV
2 1 1496 1498 1499 AND
1 1 1499 1500 INV
1 1 1500 1501 INV
2 1 1494 1501 1502 AND
1 1 1502 1503 INV
1 1 1503 1504 INV
2 1 227 467 1505 XOR
1 1 1505 1506 INV
2 1 226 466 1507 XOR
1 1 1507 1508 INV
2 1 1506 1508 1509 AND
1 1 1509 1510 INV
1 1 1510 1511 INV
2 1 225 465 1512 XOR
1 1 1512 1513 INV
2 1 224 464 1514 XOR
1 1 1514 1515 INV
2 1 1513 1515 1516 AND
1 1 1516 1517 INV
1 1 1517 1518 INV
2 1 1511 1518 1519 AND
1 1 1519 1520 INV
1 1 1520 1521 INV
2 1 1504 1521 1522 AND
1 1 1522 1523 INV
1 1 1523 1590 INV
2 1 239 479 1524 XOR
1 1 1524 1525 INV
2 1 238 478 1526 XOR
1 1 1526 1527 INV
2 1 1525 1527 1528 AND
1 1 1528 1529 INV
1 1 1529 1530 INV
2 1 237 477 1531 XOR
1 1 1531 1532 INV
2 1 236 476 1533 XOR
1 1 1533 1534 INV
2 1 1532 1534 1535 AND
1 1 1535 1536 INV
1 1 1536 1537 INV
2 1 1530 1537 1538 AND
1 1 1538 1539 INV
1 1 1539 1540 INV
2 1 235 475 1541 XOR
1 1 1541 1542 INV
2 1 234 474 1543 XOR
1 1 1543 1544 INV
2 1 1542 1544 1545 AND
1 1 1545 1546 INV
1 1 1546 1547 INV
2 1 233 473 1548 XOR
1 1 1548 1549 INV
2 1 232 472 1550 XOR
1 1 1550 1551 INV
2 1 1549 1551 1552 AND
1 1 1552 1553 INV
1 1 1553 1554 INV
2 1 1547 1554 1555 AND
1 1 1555 1556 INV
1 1 1556 1557 INV
2 1 1540 1557 1558 AND
1 1 1558 1559 INV
1 1 1559 1591 INV
2 1 0 0 1561 XOR
1 1 1561 1560 INV
1 1 1560 1592 INV
1 1 1560 1593 INV

Support non-flattened circuits?

Many (even combinational) circuits have efficient descriptions, but become impracticable when they have to be "flattened" or unrolled. This is discussed in detail in e.g. [KMsB13] and [SHSSK15].

The Bristol Format circuits which this library accepts have to be totally flattened. While this makes things easier for the developer (you), it significantly limits the circuits / functions on which the protocol can operate efficiently in practice. Moreover, the Bristol format makes it difficult to use modern hardware synthesis tools. Indeed, the only tool I could find which specifically targets this format is CBMC-GC-2, which is a bit buggy and performs poorly (huge memory consumption even on medium-sized circuits).

As a longer-term goal, I wonder if it would be possible to shift to a more modern / efficient circuit representation. For example, we could target the format output by yosys after running the sequence of commands

proc; opt; techmap; opt; abc; opt; write_verilog out.v

I recognize this would be a very large project, but I think it would significantly enhance the practical power of EMP-Toolkit, and could be worthwhile. I'd be happy to contribute.

Problem with amortized_2pc

There seems to be a bug in amortized_2pc.cpp, or I have misunderstanding on how to call it. I have freshly cloned and compiled emp-tool, emp-ot, and emp-ag2pc in /tmp.

user@tra:/tmp/emp-ag2pc (master)$ ./run bin/aes
connected
connected
128 128 128 6800
128 128 128 6800
one time:	1	29312
one time:	2	30083
ABIT	4598
check	2952
permute	927
inde:	1	9765
inde:	2	9247
dep:	2	6505
dep:	1	6777
online:	2	749
online:	1	756

Looking good. Now I would like to run amortized_2pc. First, sha-1.txt is there:

user@tra:/tmp/emp-ag2pc (master)$ ls /tmp/emp-tool/emp-tool/circuits/files/bristol_format//sha-1.txt
/tmp/emp-tool/emp-tool/circuits/files/bristol_format//sha-1.txt

However, calling amortized_2pc fails.

user@tra:/tmp/emp-ag2pc (master)$ ./run bin/amortized_2pc 
connected
connected
one time:	1	27762
one time:	2	27824
ABIT	576
check	969
permute	431
inde:	1	13281
inde:	2	12942
./run: line 29: 188700 Segmentation fault      $1 1 12345
./run: line 30: 188698 Segmentation fault      $1 2 12345

Interestingly, if I change the line which says
const static int runs = 4;
to
const static int runs = 1;
then the binary does not crash, but I get a lot of
no match GT!
errors in the console output.

What am I doing wrong?

Recommend Projects

React

A declarative, efficient, and flexible JavaScript library for building user interfaces.
Vue.js

🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript

TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
TensorFlow

An Open Source Machine Learning Framework for Everyone
Django

The Web framework for perfectionists with deadlines.
Laravel

A PHP framework for web artisans
D3

Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

javascript

JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
web

Some thing interesting about web. New door for the world.
server

A server is a program made to process requests and deliver data to clients.
Machine learning

Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Visualization

Some thing interesting about visualization, use data art
Game

Some thing interesting about game, make everyone happy.

Recommend Org

Facebook

We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft

Open source projects and samples from Microsoft.
Google

Google ❤️ Open Source for everyone.
Alibaba

Alibaba Open Source for everyone
D3

Data-Driven Documents codes.
Tencent

China tencent open source team.

	if(party == ALICE) {
	for(int i = cf->n1; i < cf->n1+cf->n2; ++i) {
	mask_input[i] = logic_xor(input[i - cf->n1], value[i]);
	mask_input[i] = logic_xor(mask_input[i], mask[i]);
	}