fast instantiation or Low communication instantiation?

[qxzhou1010]

In the paper: Blazing Fast PSI from Improved OKVS and Subfield VOLE. On Page-22, the paper proposes two constructions: one is fast instantiation, and the other is low communication instantiation. Which one is realized in this code?

I suspect the default is the Fast construction because I do not see any keywords related to Subfield Vole in the code."

[ladnir]

correct, the low comm version was never fully functional and has not been released. Might finish implementing it at some point but no promises.

[qxzhou1010]

Thank you for your reply.

However, I don’t fully understand the statement, “low comm version was never fully functional.” Could you clarify what is meant by “never fully functional”?

Additionally, why was the “low comm version” never fully functional?

I suspect that the issue might be related to the OKVS not supporting the low comm version. Is this a possible reason?

[ladnir]

it means the performance numbers in the paper were obtains by a version that didn't actual perform the right computation. Instead, I implemented something that aimed to perform the same amount of computation to get an estimate on the running time. At the time this was because "subfield vole" was not implemented in libOTe. It is now implemented and so it would be a relatively simple task to add it. If you're interested, I could tell you how.

The OKVS does support it. or could be configured to.

[qxzhou1010]

Thank you for your quick response.

I am very interested in learning how to add the "subfield vole." Could you please let me know how to implement?

[ladnir]

ok, well the main protocol is in the paper obviously. You will need to update this repo to use the latest libOTe version. you can do this be deleting the out/ folder and changing the libOTe commit in thirdparty/getlibOTe.cmake to be the latest commit. Then rebuilding.

You might need to update some stuff if the code no longer compiles.

then you will need to copy the existing volepsi implementation and replace the old VOLE using GF128 with a subfield VOLE of the appropriate fields. I guess you can figure what fields to use. libOTe has the subfield vole here https://github.com/osu-crypto/libOTe/blob/master/libOTe/Vole/Silent/SilentVoleSender.h#L37

G is the subfield and F is the larger field. You need to define types for these. In particular, you need to implement a CoeffCtx helper type https://github.com/osu-crypto/libOTe/blob/master/libOTe/Tools/CoeffCtx.h#L18C12-L18C27 that knows how to perform the relevant operations on F,G. eg how to add and multiply, serialize, etc. Its possible that if you define G,F that the default CoeffCtx will work.

Then basically you just need to do the same for the OKVS, it has something similar to CoeffCtx. In particular, you can use something like the PxMatrix or PxVector type to store your values where the nested Helper type is used to define how you add values and do the other operations.

[qxzhou1010]

Thank you for your help.

I will try to implement the Low Comm version according to your instructions in the volepsi repo.

If I successfully implement the Low Comm version, I would like to contribute a pull request to volepsi. Would you be willing to merge this pull request?

[ladnir]

should be possible. You'd be the first. Depending on what the visa lawyers say you might have to agree to a Contributor License Agreement (CLA). TDB. I can look into once you start making progress.

[qxzhou1010]

Thank you once again.

I will try my best to accomplish it.

[ladnir]

OK, let me know if you have questions. Happy to help.

[ladnir]

FYI, i updated the library to use the latest libOTe...

[qxzhou1010]

Thank you very much for your reminder.

In addition, I seem to have implemented LowCommMode correctly. I used such a combination: Subfield Vole + DenseType::Binary + encode<u64>(u128, u64, u64), so I got a u64 encoded object P. I followed the subsequent process described in the Figure 9 of RR22 paper.

In short, according to the above implementation, I have currently conducted a large number of PSI tests, running about 10,000 times in a loop, each time randomly generating 1<<16 data, and no calculation errors have been found.

[ladnir]

ok, are you wanting to make a pull request? I could review it at some point (current a bit busy bit should find time in the next month or so). And then I can ask the lawyers about what we need to do to merge the PR.

[qxzhou1010]

Of course, I will make a pull request. However, I need some time to refine my codes.

Thank you again for your help. I will submit the pull request as soon as possible

[ladnir]

No rush, might take me some time to review and everything else

[qxzhou1010]

ok, well the main protocol is in the paper obviously. You will need to update this repo to use the latest libOTe version. you can do this be deleting the out/ folder and changing the libOTe commit in thirdparty/getlibOTe.cmake to be the latest commit. Then rebuilding.

You might need to update some stuff if the code no longer compiles.

then you will need to copy the existing volepsi implementation and replace the old VOLE using GF128 with a subfield VOLE of the appropriate fields. I guess you can figure what fields to use. libOTe has the subfield vole here https://github.com/osu-crypto/libOTe/blob/master/libOTe/Vole/Silent/SilentVoleSender.h#L37

G is the subfield and F is the larger field. You need to define types for these. In particular, you need to implement a CoeffCtx helper type https://github.com/osu-crypto/libOTe/blob/master/libOTe/Tools/CoeffCtx.h#L18C12-L18C27 that knows how to perform the relevant operations on F,G. eg how to add and multiply, serialize, etc. Its possible that if you define G,F that the default CoeffCtx will work.

Then basically you just need to do the same for the OKVS, it has something similar to CoeffCtx. In particular, you can use something like the PxMatrix or PxVector type to store your values where the nested Helper type is used to define how you add values and do the other operations.

As you said: "you need to implement a CoeffCtx helper type https://github.com/osu-crypto/libOTe/blob/master/libOTe/Tools/CoeffCtx.h#L18C12-L18C27 that knows how to perform the relevant operations on F,G. eg how to add and multiply, serialize, etc. '

However, the CoeffCtx in libOTe repo, So, in which repo should I implement this CoeffCtx helper?

Now, I init Vole Object as follows:

oc::SilentVoleSender<block, u64, oc::CoeffCtxGF128> mVoleSender;
....
oc::SilentVoleReceiver<block, u64, oc::CoeffCtxGF128> mVoleRecver;

but I have encount a build error:

/*/volepsi_pr/volepsi/out/install/linux/include/libOTe/Vole/Silent/SilentVoleReceiver.h:648:41: error: cannot convert ‘long unsigned int’ to ‘const osuCrypto::block&’
  648 |                                 mCtx.mul(tempF[1], delta[0], mBaseC[i]);
      |                                 ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Is there a simpler way to use Subfield related interfaces?

[ladnir]

You have to tell the protocol how yo work with your types. What does it mean to multiple a block and a u64?

The context class you used has mul(block, block). It doesn't know how to multiply block, u64.

You'll need top copy oc::CoeffCtxGF128> into vole psi and modify it to work with your types. You need to define multiplication, etc.