3 ms·

> The "and gate" are encrypted and-gates: a table which maps encrypted bits to encrypted output bits. But the encryption scheme has only two possible inputs; c

> The "and gate" are encrypted and-gates: a table which maps encrypted bits to encrypted output bits. But the encryption scheme has only two possible inputs; can't this be brute forced? Perhaps an example would help me understand here.

nullc 11y ago
Here are commitments to an encrypted and-gate: a333e6e99e94fad05473f31ea377060a d967b456aa43ede06840994d5ce8547c 8ad297f72e49a1a6a48d343ec40661ae 88d626c9c58efd6d144f585e1fa6f436 Lets assume that the rest of the circuit gives us encrypted bits, 0 and 0 for the two inputs. So I reveal this to you: echo -n "0,0,1,bcxbxewrewtererwre" | md5sum - 8ad297f72e49a1a6a48d343ec40661ae Which is the third entry in the table, and we see the correct encrypted output for this gate is 1 (assuming my table was actually an encrypted and-gate table). You still have idea if in1/in2/out are are zero or one. I could tell you that in1's encryption key was 1 (so now you know that in1 was one), and you still don't know if In2/out are zero or one. Making any more more sense?
- Manishearth 11y ago
  Sort of, but not exactly: > So I reveal this to you: echo -n "0,0,1,bcxbxewrewtererwre" | md5sum - 8ad297f72e49a1a6a48d343ec40661ae what is 1 in 0,0,1? the encrypted output? Since this salted hash must be verifiable, I must know the bcx... string, and I can brute force all 8 possible pairs of numbers to get the gate. Isn't this a problem? > and we see the correct encrypted output for this gate is 0 Where did the zero come from?
  - nullc 11y ago
    > what is 1 in 0,0,1? the encrypted output? Yes, the encrypted output. > Since this salted hash must be verifiable, I must know the bcx... string, and I can brute force all 8 possible pairs of numbers to get the gate. Isn't this a problem? I tell you it when I give you the table entry. You have the commitments, go ahead and tell me the rest of the gate if you think you can brute force it. (You can't-- the nonces are per table entry). > Where did the zero come from? From the third field in the table entry. Edit: HN won't let me respond to you, but the fact that it's the Nth entry is irrelevant; I called out the number so you'd see if was one of the values that were committed to. Sorry for adding confusion.
    - Manishearth 11y ago
      > the nonces are per table entry Ah, I see. > The output. But you just said that the output was zero? Perhaps I'm missing something here, you got the output as 1 from "0,0,1", and you got the output as 0 from "it being the third entry in the table" (additionally, how does it being the third entry tell you anything? This isn't an AND gate, this is an encrypted-and-shuffled AND gate, so you might have three outputs that are 1 instead of three 0 outputs, and they might be shuffled anyhow)

nullc 11y ago

Here are commitments to an encrypted and-gate: a333e6e99e94fad05473f31ea377060a d967b456aa43ede06840994d5ce8547c 8ad297f72e49a1a6a48d343ec40661ae 88d626c9c58efd6d144f585e1fa6f436 Lets assume that the rest of the circuit gives us encrypted bits, 0 and 0 for the two inputs. So I reveal this to you: echo -n "0,0,1,bcxbxewrewtererwre" | md5sum - 8ad297f72e49a1a6a48d343ec40661ae Which is the third entry in the table, and we see the correct encrypted output for this gate is 1 (assuming my table was actually an encrypted and-gate table). You still have idea if in1/in2/out are are zero or one. I could tell you that in1's encryption key was 1 (so now you know that in1 was one), and you still don't know if In2/out are zero or one. Making any more more sense?

Manishearth 11y ago
Sort of, but not exactly: > So I reveal this to you: echo -n "0,0,1,bcxbxewrewtererwre" | md5sum - 8ad297f72e49a1a6a48d343ec40661ae what is 1 in 0,0,1? the encrypted output? Since this salted hash must be verifiable, I must know the bcx... string, and I can brute force all 8 possible pairs of numbers to get the gate. Isn't this a problem? > and we see the correct encrypted output for this gate is 0 Where did the zero come from?
- nullc 11y ago
  > what is 1 in 0,0,1? the encrypted output? Yes, the encrypted output. > Since this salted hash must be verifiable, I must know the bcx... string, and I can brute force all 8 possible pairs of numbers to get the gate. Isn't this a problem? I tell you it when I give you the table entry. You have the commitments, go ahead and tell me the rest of the gate if you think you can brute force it. (You can't-- the nonces are per table entry). > Where did the zero come from? From the third field in the table entry. Edit: HN won't let me respond to you, but the fact that it's the Nth entry is irrelevant; I called out the number so you'd see if was one of the values that were committed to. Sorry for adding confusion.
  - Manishearth 11y ago
    > the nonces are per table entry Ah, I see. > The output. But you just said that the output was zero? Perhaps I'm missing something here, you got the output as 1 from "0,0,1", and you got the output as 0 from "it being the third entry in the table" (additionally, how does it being the third entry tell you anything? This isn't an AND gate, this is an encrypted-and-shuffled AND gate, so you might have three outputs that are 1 instead of three 0 outputs, and they might be shuffled anyhow)