Garbled Circuits and cryptography in cybersecurity

 Introduction - 

The concept of garbled circuits originates from the millionaire's problem.

Millionaire's problem - Suppose a gathering of 5-6 millionaires on a round table and they want to know the highest net worth among among them without disclosing each's net worth. It can be done by by taking information about each's net worth to a trusted third party, the third party then evaluates the highest net worth without knowing each's net worth and gives it to the millionaires.

An Overview of Garbled circuits - 

The garbled circuits work on the same principle as above mentioned "Millionaire's problem". The concept of garbled circuit works on multi-party computation (MPC) where it has 2 parties primarily garbler and the evaluator. The garbler has following roles in this problem.

The roles of the garbler are following - 

In garbled circuits, the "garbler" is a participant in secure multi-party computation protocols. Their role is to create a garbled version of a circuit. Here's a breakdown of their role:

1. Circuit Description : The garbler starts with a Boolean circuit description representing the computation that needs to be performed securely. This circuit could represent any function, such as addition, multiplication, or even more complex computations.

2. Garbling : The garbler then encrypts each gate in the circuit in such a way that the input and output wires of the gate are obfuscated. This is typically achieved using cryptographic techniques like Yao's garbled circuit construction.

3. Garbled Tables : For each gate in the circuit, the garbler creates a set of encrypted "garbled tables" that represent all possible combinations of input values to the gate along with their corresponding output values. These tables are encrypted in such a way that only the correct output for a given input combination can be decrypted.

4. Output Encoding : Finally, the garbler encodes the output wires of the circuit, ensuring that only the intended recipient can decode and interpret the final result.

To explain the Garbled circuit simply, the two parties work on a function which is encrypted by one of the party called garbler, the function is performed by using logic gates.

Here' how the logic gate encryption is done -

First the garbler creates the function based truth table of the logic gate and then the key is selected from the inputs and outputs; the evaluator party then needs to find the key on which the decryption will be done and the output will be obtained.

Truth table of a function which has AND Gate- 

The input and output are then encrypted using keys -

Then the evaluator party decrypts based on the input set of keys provided by the garbler, so the evaluator will now have to evaluate through the truth table of the row which contains the key.

The output is finally provided upon decryption only when the correct key is selected.

Here are some of the additional methods used -

Authenticated Encryption - In simpler terms, this type of encryption relies mainly on key such that the output is provided only when the key is correct.

Oblivious Transfer - Oblivious transfer allows one party to obtain one of multiple pieces of information without revealing which one they chose to the other party. The receiver learns only the selected piece of data, while the sender remains oblivious to the choice made. It's used in cryptographic protocols to enable secure and private information exchange. 

In this way both the parties have their data secured and the output is obtained.