Overview:

1. What is WE?
2. What are KZG Commitments?
3. Extractable Witness Encryption for KZG Commitments
4. Application to Efficient Laconic OT

1. What is WE?

Regular Public Key Encryption

Witness Encryption

Replace Key Generation with an NP relation.

2. What are KZG Commitments?

KZG Commitment Scheme is:

• Hiding
• Binding

3. Extractable Witness Encryption for KZG Commitments

Idea of WE for KZG commimtments is to encrypt a message towards a triple \(com, \alpha, \beta\) and let somebody that knows a correct opening proof be able to decrypt that message.

BUT this wouldn't satisfy the security definition of Witness Encryption, therefore the authors focuses on the notion of Extractable Witness Encryption. (Check HackMD for more info on that)

To construct such scheme, the authors start by describing a simpler algorithm that is Extractable Witness KEM for KZG, which is simpler but very similar to WE. But first of all, what is even a KEM?

KEM stands for Key Encapsulation Mechanism, this is commonly used to securely exchange a symmetric key between two parties over a public insecure channel. There are two algorithms:

\begin{flalign*} \text{Encap}(pk) &\rightarrow \text{k, ct} \\ \text{Decap}(ct, sk) &\rightarrow k \\ \end{flalign*}

KEM is very similar to regular asymetric encryption. The main difference is that in asymmetric encryption you specify the message you want to encrypt while in KEM the thing that you want to encrypt (symmetric key, in practice) is randomly generated as part of the algorithm.

We encapsulate a key \(k\) inside a ciphertext towards the triple \(com, \alpha, \beta\). Only who knows a valid opening proof \(\pi\) is able to decapsulate the key \(k\).

So how to derive extractable WE from that?

We can use the encapsulated/decapsulated key \(k\) into a symmetric encryption scheme to encrypt arbitrary messages \(m\).

KEM : Public Key Encryption = Extractable Witness KEM : Extractable WE

4. Application to Efficient Laconic OT

This is a traditional OT between Alice and Bob

In the traditional version, each message requires 2 round of communication between Alice and Bob

Laconic version of OT. The main difference is in the efficiency of such scheme. Bob compresses all their \(n\) bits into a dictionary and sends to Alice the digest of the dictionary \(D\). In this way, a transfer of \(n\) messages between Alice and Bob always require a constant number of communication rounds (namely 2). We kinda batch all the Oblivious Transfers together.

WE for KZG is used to compress the dictionary sent by Bob in the first place. Then Alice will encrypt their contractitory messages under the KZG triple. For example she will encrypt \({m_0}^1\) under the opening of the commitment to \(0\) at the point \(1\) and the message \({m_1}^1\) under the opening of the commitment to \(1\) at the point \(1\).

Check performance improvements in the paper