# US 2023/0409748 A1 · Garbling enhancements

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2023/0409748 A1
- Document ID: US20230409748A1
- Status: Published application
- Kind: A1
- Application number: 17/807,758
- Filed: 2022-06-20
- Published: 2023-12-21
- Earliest claimed: 2022-06-20
- Assignees: VMware, Inc.
- Applicants: VMware, Inc.
- Inventors: Avishay YANAI
- Web page: https://patentgrep.com/patent/US20230409748A1

## CPC

- G06F 21/6254: {by anonymising data, e.g. decorrelating personal data from the owner's identification}
- G06F 21/645: {using a third party}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

The disclosure provides an approach for data security. Embodiments include determining, by one or more garbling components running on one or more processing devices, first labels Ka0 and Ka1 representing values of 0 and 1 for a first input wire a of a gate g in a circuit, second labels Kb0 and Kb1 representing the values of 0 and 1 for a second input wire b of the gate g, and third labels Kc0 and Kc1 representing the values of 0 and 1 for an output wire c of the gate g. Embodiments include defining, by the one or more garbling components, four interpolation points based on Ka0, Ka1, Kb0, Kb1, Kc0, and Kc1 and determining, by the garbling component, using polynomial interpolation based on the four interpolation points, a polynomial Pg representing a garbled gate corresponding to gate g.

## Claims

### Claim 1

A method of data security, comprising:
determining, by one or more garbling components running on one or more processing devices:
first labels Ka0 and Ka1 representing values of 0 and 1 for a first input wire a of a gate g in a circuit;
second labels Kb0 and Kb1 representing the values of 0 and 1 for a second input wire b of the gate g; and
third labels Kc0 and Kc1 representing the values of 0 and 1 for an output wire c of the gate g;
defining, by the one or more garbling components, four interpolation points based on Ka0, Ka1, Kb0, Kb1, Kc0, and Kc1;
determining, by the garbling component, using polynomial interpolation based on the four interpolation points, a polynomial Pg representing a garbled gate corresponding to gate g;
sending, by the one or more garbling components, to an evaluator component running on one or more additional processing devices:
the polynomial Pg; and
a map indicating that Kc0 corresponds to 0 and that Kc1 corresponds to 1;
obtaining, by the evaluator component, input labels Ka and Kb for the first input wire a and the second input wire b, wherein at least one of Ka or Kb corresponds to a private input value that is not provided to the evaluator component;
evaluating, by the evaluator component, the polynomial Pg using Ka and Kb to determine an output label Kc for the output wire c; and
determining, by the evaluator component, an output bit yc based on the output label Kc and the map.

### Claim 2 (depends on 1)

The method of claim 1, wherein the four interpolation points comprise:
a first interpolation point (x1, y1), wherein:
x1 is based on Ka0 and Kb0; and
y1 is based on Kc0 or Kc1;
a second interpolation point (x2, y2), wherein:
x2 is based on Kao and Kb1; and
y2 is based on Kc0 or Kc1;
a third interpolation point (x3, y3), wherein:
x3 is based on Ka1 and Kb0; and
y3 is based on Kc0 or Kc1; and
a fourth interpolation point (x4, y4), wherein:
x4 is based on Ka1 and Kb1; and
y4 is based on Kc0 or Kc1.

### Claim 3 (depends on 2)

The method of claim 2, wherein:
x1 is determined by applying a hash function H to a concatenation of Ka0 and Kb0;
X2 is determined by applying the hash function H to a concatenation of Ka0 and Kb1;
X3 is determined by applying the hash function H to a concatenation of Ka1 and Kb0; and
x4 is determined by applying the hash function H to a concatenation of Ka1 and Kb1.

### Claim 4 (depends on 3)

The method of claim 3, wherein the hash function H is a second-preimage resistant hash function (SPRHF).

### Claim 5 (depends on 2)

The method of claim 2, wherein:
y1 is determined based on concatenating a first random value R1 with Kc0 or Kc1;
y2 is determined based on concatenating a second random value R2 with Kc0 or Kc1;
y3 is determined based on concatenating a third random value R3 with Kc0 or Kc1; and
y4 is determined based on concatenating a fourth random value R4 with Kc0 or Kc1.

### Claim 6 (depends on 1)

The method of claim 1, further comprising receiving, by the evaluator component, from an additional one or more garbling components, an additional polynomial Pm representing an additional garbled gate corresponding to an additional gate m of the circuit, wherein the evaluator component determines an overall output for the circuit based on yc and a result of evaluating Pm.

### Claim 7 (depends on 1)

The method of claim 1, wherein the gate g is one of:
an AND gate; or
an exclusive OR (XOR) gate.

### Claim 8

A system for data security, the system comprising:
at least one memory; and
at least one processor coupled to the at least one memory, the at least one processor and the at least one memory configured to:
determine, by one or more garbling components running on one or more processing devices:
first labels Ka0 and Ka1 representing values of 0 and 1 for a first input wire a of a gate g in a circuit;
second labels Kb0 and Kb1 representing the values of 0 and 1 for a second input wire b of the gate g; and
third labels Kc0 and Kc1 representing the values of 0 and 1 for an output wire c of the gate g;
define, by the one or more garbling components, four interpolation points based on Ka0, Ka1, Kb0, Kb1, Kc0, and Kc1;
determine, by the garbling component, using polynomial interpolation based on the four interpolation points, a polynomial Pg representing a garbled gate corresponding to gate g;
send, by the one or more garbling components, to an evaluator component running on one or more additional processing devices:
the polynomial Pg; and
a map indicating that Kc0 corresponds to 0 and that Kc1 corresponds to 1;
obtain, by the evaluator component, input labels Ka and Kb for the first input wire a and the second input wire b, wherein at least one of Ka or Kb corresponds to a private input value that is not provided to the evaluator component;
evaluate, by the evaluator component, the polynomial Pg using Ka and Kb to determine an output label Kc for the output wire c; and
determine, by the evaluator component, an output bit yc based on the output label Kc and the map.

### Claim 9 (depends on 8)

The system of claim 8, wherein the four interpolation points comprise:
a first interpolation point (x1, y1), wherein:
x1 is based on Kao and Kb0; and
y1 is based on Kc0 or Kc1;
a second interpolation point (x2, y2), wherein:
x2 is based on Kao and Kb1; and
y2 is based on Kc0 or Kc1;
a third interpolation point (x3, y3), wherein:
x3 is based on Ka1 and Kb0; and
y3 is based on Kc0 or Kc1; and
a fourth interpolation point (x4, y4), wherein:
x4 is based on Ka1 and Kb1; and
y4 is based on Kc0 or Kc1.

### Claim 10 (depends on 9)

The system of claim 9, wherein:
x1 is determined by applying a hash function H to a concatenation of Ka0 and Kb0;
x2 is determined by applying the hash function H to a concatenation of Ka0 and Kb1;
X3 is determined by applying the hash function H to a concatenation of Ka1 and Kb0; and
x4 is determined by applying the hash function H to a concatenation of Ka1 and Kb1.

### Claim 11 (depends on 10)

The system of claim 10, wherein the hash function H is a second-preimage resistant hash function (SPRHF).

### Claim 12 (depends on 9)

The system of claim 9, wherein:
y1 is determined based on concatenating a first random value R1 with Kc0 or Kc1;
y2 is determined based on concatenating a second random value R2 with Kc0 or Kc1;
y3 is determined based on concatenating a third random value R3 with Kc0 or Kc1; and
y4 is determined based on concatenating a fourth random value R4 with Kc0 or Kc1.

### Claim 13 (depends on 8)

The system of claim 8, wherein the at least one processor and the at least one memory are further configured to receive, by the evaluator component, from an additional one or more garbling components, an additional polynomial Pm representing an additional garbled gate corresponding to an additional gate m of the circuit, wherein the evaluator component determines an overall output for the circuit based on yc and a result of evaluating Pm.

### Claim 14 (depends on 8)

The system of claim 8, wherein the gate g is one of:
an AND gate; or
an exclusive OR (XOR) gate.

### Claim 15

A non-transitory computer-readable medium storing instructions that, when executed by one or more processors, cause the one or more processors to:
determine, by one or more garbling components running on one or more processing devices:
first labels Ka0 and Ka1 representing values of 0 and 1 for a first input wire a of a gate g in a circuit;
second labels Kb0 and Kb1 representing the values of 0 and 1 for a second input wire b of the gate g; and
third labels Kc0 and Kc1 representing the values of 0 and 1 for an output wire c of the gate g;
define, by the one or more garbling components, four interpolation points based on Ka0, Ka1, Kb0, Kb1, Kc0, and Kc1;
determine, by the garbling component, using polynomial interpolation based on the four interpolation points, a polynomial Pg representing a garbled gate corresponding to gate g;
send, by the one or more garbling components, to an evaluator component running on one or more additional processing devices:
the polynomial Pg; and
a map indicating that Kc0 corresponds to 0 and that Kc1 corresponds to 1;
obtain, by the evaluator component, input labels Ka and Kb for the first input wire a and the second input wire b, wherein at least one of Ka or Kb corresponds to a private input value that is not provided to the evaluator component;
evaluate, by the evaluator component, the polynomial Pg using Ka and Kb to determine an output label Kc for the output wire c; and
determine, by the evaluator component, an output bit yc based on the output label Kc and the map.

### Claim 16 (depends on 15)

The non-transitory computer-readable medium of claim 15, wherein the four interpolation points comprise:
a first interpolation point (x1, y1), wherein:
x1 is based on Ka0 and Kb0; and
y1 is based on Kc0 or Kc1;
a second interpolation point (x2, y2), wherein:
x2 is based on Ka0 and Kb1; and
y2 is based on Kc0 or Kc1;
a third interpolation point (x3, y3), wherein:
x3 is based on Ka1 and Kb0; and
y3 is based on Kc0 or Kc1; and
a fourth interpolation point (x4, y4), wherein:
x4 is based on Ka1 and Kb1; and
y4 is based on Kc0 or Kc1.

### Claim 17 (depends on 16)

The non-transitory computer-readable medium of claim 16, wherein:
x1 is determined by applying a hash function H to a concatenation of Ka0 and Kb0;
x2 is determined by applying the hash function H to a concatenation of Ka0 and Kb1;
X3 is determined by applying the hash function H to a concatenation of Ka1 and Kb0; and
x4 is determined by applying the hash function H to a concatenation of Ka1 and Kb1.

### Claim 18 (depends on 17)

The non-transitory computer-readable medium of claim 17, wherein the hash function H is a second-preimage resistant hash function (SPRHF).

### Claim 19 (depends on 16)

The non-transitory computer-readable medium of claim 16, wherein:
y1 is determined based on concatenating a first random value R1 with Kc0 or Kc1;
y2 is determined based on concatenating a second random value R2 with Kc0 or Kc1;
y3 is determined based on concatenating a third random value R3 with Kc0 or Kc1; and
y4 is determined based on concatenating a fourth random value R4 with Kc0 or Kc1.

### Claim 20 (depends on 15)

The non-transitory computer-readable medium of claim 15, wherein the instructions, when executed by the one or more processors, further cause the one or more processors to receive, by the evaluator component, from an additional one or more garbling components, an additional polynomial Pm representing an additional garbled gate corresponding to an additional gate m of the circuit, wherein the evaluator component determines an overall output for the circuit based on yc and a result of evaluating Pm.
