This is the 3rd post in the series of interactive zero-knowledge(IZK) blogs. Check out the rest of the posts in the series:
Previously, we delved into the generation of Standard OT, using Random OT (ROT) to create OT instances during the preprocessing phase. Unfortunately, both Standard OT and ROT require public key encryption for each instance, making them rather costly. To address this, we’ve introduced a technique that allows for the creation of a vast number of OT instances (over a million) using a fixed number of public key encryption operations (128). In this post, we’ll be detailing an efficient protocol for OT Extension.
While there are numerous methods to implement OTE, today we’ll be concentrating specifically on the [IKNP03] approach.
IKNP Details
1）Initialization
Alice chooses a random s∈GF(2¹²⁸) of length 128 bits.
Bob chooses a random r∈GF(2)^n, |r|=n(length of r is n), n is up to 10k rows.
Initially, Alice acts as the receiver, and Bob acts as the sender.
2）Extended to matrix
Bob expands r to a matrix R with the same elements in each row (10,000 rows * 128 columns), randomly generates a matrix T of the same size, and obtains a matrix T’ = T ⊕ R.
3）128 times Base OT
When Alice’s s[i] = 0, get the matrix T[i] column through Base OT; when s[i] = 1, get the matrix T’[i] column. after 128 times Base OT, Alice obtains a new matrix Q (10,000 rows * 128 columns) which columns are composed of corresponding columns of T and T’.
It can be found that when
Bob’s r = 0, Alice’s row Q = Bob’s row T;
when Bob’s r = 1, Alice’s row Q = Bob’s row T ⊕ s.
4）Role Reversal
Initially, Alice acts as the receiver, and Bob acts as the sender. However, now Alice assumes the role of the sender, and Bob becomes the receiver.
After completing the above process, Alice has 10,000 128-bit random keys ti and ti ⊕ s, and Bob has 10,000-bit r∈{0,1}. Each row is a ROT instance(qi=ti ⊕(ri * s)).
By using only 128 instances of Base OT, we are able to create 10k ROT instances.
(1) Bob enters r1=0, r2=1, r3=1 into the IKNP protocol.
(2) Alice uses the keys t1, t1 ⊕ s, t2 ⊕ s, t2, t3 ⊕ s, t3 to encrypt the messages m0_1, m1_1, m0_2, m1_2, m0_3, m1_3 respectively, and then sends the encrypted results to Bob.
(3) Bob uses the decryption keys k=t1, t2, t3 to decrypt them respectively, and finally gets:
(m0_1 ⊕ t1) ⊕ t1 = m0_1
(m1_2 ⊕ t2) ⊕ t2 = m1_2
(m1_3 ⊕ t3) ⊕ t3 = m1_3
Next
In upcoming posts, we’ll explore cryptography using Base OT and IKNP as foundational components. These building blocks will help us create advanced protocols. Stay tuned for discussions on more cryptographic protocols.
