Confusion on implementions of KKRT-PSI

[tiantianwangwang]

I found that the implemention process is slightly different from the original paper DOI:10.1145/2976749.2978381 Here are my questions:

1. When doing KKRT-PSI we first do an OPRF protocol. After the OPRF ,the sender will get keys(or called seeds) and the receiver will get F(k,d) I want to do something with these two items, but I couldn't find where they are in the code.

2. After OPRF, do keys, F(k,d) and the data that I inputted correspond in order? Or the output of keys, F(k,d) are disordered?

Any ideas help explaining?

[ladnir]

the ot code is here https://github.com/osu-crypto/libOTe/tree/master/libOTe/NChooseOne/Kkrt

here is where the receiver processes their values https://github.com/osu-crypto/libOTe/blob/master/libOTe/NChooseOne/Kkrt/KkrtNcoOtReceiver.cpp#L210 here is the sender https://github.com/osu-crypto/libOTe/blob/master/libOTe/NChooseOne/Kkrt/KkrtNcoOtSender.cpp#L193

[tiantianwangwang]

That's really helpful! Thank you.

But I have met a new problem: the sender need to rebuild F(k,a). //a is the input of the sender. According to the paper, I find the formulation should be I think q matrix is here https://github.com/osu-crypto/libPSI/blob/2eb0514f66a0a0d8ce0ffcead73485886f21306f/libPSI/PSI/Kkrt/KkrtPsiSender.cpp#L374

s is here https://github.com/osu-crypto/libOTe/blob/b6e3a9d157cb3c2ea43815c105eb7b4cac292dda/libOTe/NChooseOne/Kkrt/KkrtNcoOtSender.cpp#L15

C(r) is here https://github.com/osu-crypto/libOTe/blob/b6e3a9d157cb3c2ea43815c105eb7b4cac292dda/libOTe/NChooseOne/Kkrt/KkrtNcoOtSender.cpp#L79

Is it right?

[ladnir]

C(r) is the codeword https://github.com/osu-crypto/libOTe/blob/b6e3a9d157cb3c2ea43815c105eb7b4cac292dda/libOTe/NChooseOne/Kkrt/KkrtNcoOtSender.cpp#L206

that equation is computed here https://github.com/osu-crypto/libOTe/blob/b6e3a9d157cb3c2ea43815c105eb7b4cac292dda/libOTe/NChooseOne/Kkrt/KkrtNcoOtSender.cpp#L221

[tiantianwangwang]

Hi Iadnir! Thank you for your help. I fixed this problem successfully, and now there is the last error: How the sender transmits the message to the receiver.

The sender wants to send the message to the receiver， I tried to use std::array to generate a two-dimensional array std::array<std::array<block, 2>, mSenderSize> but it will result in an error.

So I try to use std::vector, store the message in a vector and then use chl.asyncSend((u8*)&v, v.size()*sizeof(block)); to send the vector, and the receiver try to use auto futest1 = chl0.asyncRecv((u8*)&v, v.size()*sizeof(block)); to get the message. The error is like this

Any ideas help explaining?

[ladnir]

it basically tells you. The receive buffer does not have the same size as the send buffer. Either they are different sizes or maybe you aren't matching the correct send/receive pair.

[tiantianwangwang]

OK, I will test it

[tiantianwangwang]

Hello Iadnir, In kkrt protocol I met two problems here.

1. How to pass a std::vector data from sender to receiver. Which function can do this in this lib.

2. How to extend the output of OPRF, such as now the output of OPRF is 128bit, and I need the output 256bit.

[ladnir]

How to send data? There are lots of examples in the code base...

channel.send(vec));

Receive is the same but .recv(...).

The vector must have some basic data type for its elements...

See the tutorial if you're confused https://github.com/ladnir/cryptoTools/blob/master/frontend_cryptoTools/Tutorials/Network.cpp

You can expand the oprf output size by rehashing the 128 bit output to your desired size. Either use RandomOracle ro(32); ro.Update(v); to.Finalize(out); or PRNG prng(v); out=prng.get(); to do this. Where v is 128 bit and out is your 256 not output.

[tiantianwangwang]

That is really useful! Thanks.

Also is there any hash function in this library? LIke sha-256,md5... can you give me some examples?

[ladnir]

RandomOracle is a hash function. Its Blake2. Its at least as secure as sha-256.

Never use md5. Forget that it exists.

[tiantianwangwang]

Hello Iadnir, It's about the class blake2 and some problems. I try to use the blake2 to hash some std::string. There may be some mistake when using .Update() to input the std::string. Can you give me some examples? And if I remove the code hashone.Reset(); const std::string &r1 = n; hashone.Update(&r1); hashone.Final((u8 *)&hashdata); The Segmentation fault will disappear, this is so weird.

[ladnir]

Idk about the seg fault but certainly your hashing the string wrong. A std string is a pointer to memory and a size. So your currently hashing a pointer and size. Not the content of the string... Use Update(string.data(), string.size())

[tiantianwangwang]

yeah, your are right.

I fixed the problem about .update(). But the Segmentation fault is a more serious problem. In the code below I used blake2 to process strings and set up four cout to find the code that went wrong.

while (std::getline(file, buffer))
        {
            std::string ID = buffer.substr(0,18);
            hashone.Update(ID.data(),ID.size());
            hashone.Final((u8 *)&hashdata);
            std::cout<<'1'<<std::endl;
            hashone.Reset();
            v_ID_hash.push_back(hashdata);
            std::cout<<'1'<<std::endl;
            buffer = buffer.substr(19); 
            std::string buffer1 = buffer.substr(0, 32);
            std::string buffer2 = buffer.substr(32);
            myBuffer[0] = block(std::stoll(buffer1.substr(0, 16), 0, 16), std::stoll(buffer1.substr(16), 0, 16));
            myBuffer[1] = block(std::stoll(buffer2.substr(0, 16), 0, 16), std::stoll(buffer2.substr(16), 0, 16));
            std::cout<<'1'<<std::endl;
            v_data.push_back(Aestest.ecbEncBlock(myBuffer[0]));
            std::cout<<'1'<<std::endl;
            v_data.push_back(Aestest.ecbEncBlock(myBuffer[1]));
        }

The Segmentation fault occurred in v_data.push_back(Aestest.ecbEncBlock(myBuffer[0]));, and it seems because of the blake2. If I remove the code of it, the error will disappear.

[ladnir]

I'm not sure and not very motivated to debug your segfaults. My suggestion is to turn on asan. That will help you find where you are accessing bad memory.

Build libOTe with

python3 build.py -D ENABLE_ASAN=true

[tiantianwangwang]

Hello Iadnir, It's about how to change the type from block to std::string. I try to use block.data(), apparently there's some error here. Can you give me some examples? To change the type from block to std::string.

[ladnir]

Don't change the libPSI code. Take your chosen type and hash out into a block... Then call libPSI.

[tiantianwangwang]

Hello Iadnir, it's been a long time. I recently encountered another problem in KKRT, in addition to the already completed OPRF how can the sender and receiver do another OPRF with NcoOT code? In fact I'm not quite sure how NcoOT relates to OPRF. (What means NcoOT?)

[ladnir]

Nco ot is n choose one ot. Oprf is more like n choose t ot.

Nco ot: the library allows the sender to compute t ots. For the i'th ot, the sender gets a random key ki. With this key the sender can evaluate a random function F{k_i} (x) for any x in {1,2,...,n}. In total, the sender can therefore compute t * n possible output values.

For the i'th ot, the receiver is allowed to choose exactly one value y_i in {1,2,...,n} and learn the random looking value zi = F{k_i} (y_i). So the receiver can only learn t outputs, with each being derived from a different key.

The receiver has no idea what the keys are. They can not compute any other outputs... From this interaction, sender has no way of knowing what y_i values the receiver used. The sender can compute zi = F{k_i} (y_i) if they, by some other means, know to use y_i as an input.

Normal Oprf: oprf is very similar but there is only one key, k. The sender knows the key and therefore can compute F_k(x) for any x in {1,...,n}.

The other difference is the the receiver is allowed to choose t values, y_1,...,y_t and learn the values z_i=F_k(y_i) for each i in {1,...,t}.

Again, the receiver has know idea what the key is and the sender has no idea what y_i values were used.

KKRT is an Nco ot protocol, not a normal oprf protocol. The kkrt paper might use the oprf term but it's not exactly a oprf. In particular, kkrf uses the term bark-oprf to describe their construction which is the same thing as a Nco ot protocol.

I'm not sure if I understand your first question. If it's how do you allow the receiver to learn multiple outputs for a single key, k_i, then the answer is that you can not do this with kkrt. Kkrt specifically only works when the receiver is allowed to learn exactly one value z_i per key k_i held by the sender.

If you want multiple values per key, then you need a normal oprf. If this is the case I can give some pointers on what oprf to use.

[tiantianwangwang]

Get it, and I I would like to expand on Nco ot. In the new protocol, for the i'th ot, the sender gets two random key k_i_1 and k_i_2. The sender can compute z_i1 = F{k_i_1} (x) and z_i2 = F{k_i_2} (x). In total, the sender can therefore compute 2t * n possible output values. Do you have any idea?

[ladnir]

Do you want to make sure the receiver uses the same input for key k_i_1 and k_i_2?

[tiantianwangwang]

Yes.

[ladnir]

OK, you can do this. Generate t noc ots like normal. The sender gets key k_i for the ith ot. Define new keys k_i_j = (k_i, j). Then

F'_{k_i_j} (x) = H(F_{k_i} (x), j)

Where H is a hash function or similar. That is, if you want to use the "1" key you simply rehash the normal output F_{k_i} (x) with the value 1. For the 2 key you do the same but with value 2.

[tiantianwangwang]

Perfect, I will try it. Thank you very much!