How to modify the implementation of oblivious transfer from SimplestOT to libOTe?

[DoctorJackson]

Hi, I'm unsure about the default implementation of oblivious transfer, especially when using garbled circuits. Is it SimpleOT (https://github.com/mkskeller/SimpleOT), SimplestOT_C (https://github.com/mkskeller/SimplestOT_C), or libOTe (https://github.com/mkskeller/softspoken-implementation)? I would like to know how to modify the implementation of oblivious transfer to use libOTe, specifically enabling the Masny Rindal [MR19] protocol (Kyber fork) called ENABLE_MR_KYBER.

deps/libOTe/libOTe:
    git submodule update --init --recursive deps/libOTe || git clone --recurse-submodules https://github.com/mkskeller/softspoken-implementation deps/libOTe
boost: deps/libOTe/libOTe
    cd deps/libOTe; \
    python3 build.py --setup --boost --install=$(CURDIR)/local

OTE_OPTS += -DENABLE_SOFTSPOKEN_OT=ON -DCMAKE_CXX_COMPILER=$(CXX) -DCMAKE_INSTALL_LIBDIR=lib

To build libOTe with Kyber implementation, I'm attempting to modify line 306 of the Makefile: OTE_OPTS += -DENABLE_SOFTSPOKEN_OT=ON -DCMAKE_CXX_COMPILER=$(CXX) -DCMAKE_INSTALL_LIBDIR=lib to OTE_OPTS += -DENABLE_SOFTSPOKEN_OT=ON -DCMAKE_CXX_COMPILER=$(CXX) -DCMAKE_INSTALL_LIBDIR=lib -DENABLE_MR_KYBER=ON

However, I'm uncertain if this modification will work.

I look forward to your response. Thank you!

[mkskeller]

OT consists of two steps, base OT (just a few) and OT extension (the bulk of them generated from the base OTs). MP-SPDZ uses SimpleOT (both implementations compute the same, but SimpleOT is optimized for post-2010 x86 CPUs) for base OTs, and SoftSpoken from libOTe for OT extension. You cannot replace the OT extension by changing the build process. Instead, you would need to change OTExtensionWithMatrix::soft_sender and OTExtensionWithMatrix::soft_receiver in OT/OTExtensionWithMatrix.cpp to use the desired functionality from libOTe.

[DoctorJackson]

Thank you for your response and clarification. I would like to express my gratitude for the explanation you provided about modifying the OT extension. However, my intention is to replace the base OT implementation from SimpleOT to softspoken-implementation/libOTe/Base/MasnyRindalKyber. I apologize for any confusion caused. Could you please guide me on how to make this replacement? Thank you for your help.

[mkskeller]

In this case, you need to replace BaseOT::exec_base() in OT/BaseOT.cpp. However, it's not a trivial change because the libOTe code uses a different communication infrastructure than MP-SPDZ, so I cannot any concrete guidance.

[DoctorJackson]

Thank you very much. I will give it a try on my own.

[DoctorJackson]

I'm having difficulty understanding the communication infrastructure in MP-SPDZ. Could you please provide me with relevant documentation that offers more detailed explanations? Thank you.

[mkskeller]

The documentation is here: https://mp-spdz.readthedocs.io/en/latest/networking.html#internal-infrastructure

[DoctorJackson]

Thanks a lot. I would also like to inquire if there is any introduction available that provides explanations for the meanings of the variables and function names used in BaseOT.c or SimpleOT/ot_sender.c?

[mkskeller]

82b2b533e146fddaa051da36ba98412a7a64c1ba adds documentation throughout OT/BaseOT.h and OT/BaseOT.cpp.

[DoctorJackson]

WOW! Thanks!

[DoctorJackson]

Hi! I added something like printf("Hi. This is a SENDER. I will send the A.\n");in BaseOT.cpp.

And I noticed that party 1 in yao-party (as an evaluator) appears to be acting as the SENDER of the baseOT. I'm wondering if this conflicts with yao's protocol, where the SENDER, who knows both labels of the garbled circuits, should be the Garbler. Maybe I misunderstood the protocol or the code. Please enlighten me. Thanks!

[mkskeller]

Two things:

1. Base OTs are executed both ways by default even when not needed.
2. The Yao protocol implementation doesn't use base OTs but extended OTs.

[DoctorJackson]

I'm sorry, I have once again confused a few concepts between the OTs. Are the Softspoken extended OTs of The Yao protocol implementation based on DotMaliciousLeakyReceiver or some other protocol, rather than SimpleOT? Can I use KyberOT as the baseOT to generate the SoftSpoken (or KOS) implementation of these extended OTs and apply them to the Yao Protocol? Which code files do I need to review and modify?

[DoctorJackson]

In fact, I am still uncertain about how the OT extension is invoked in The Yao protocol implementation. I could only find the following code snippets in YaoGarbler.cpp and YaoEvaluator.cpp:

In YaoGarbler.cpp:

ot_ext(OTExtensionWithMatrix::setup(player, {}, RECEIVER, true))

In YaoEvaluator.cpp:

ot_ext(OTExtensionWithMatrix::setup(player,
        master.get_delta().get<__m128i>(), SENDER, true))

However, I believe it is relevant that "Base OTs are executed both ways by default even when not needed."

OTExtensionWithMatrix OTExtensionWithMatrix::setup(TwoPartyPlayer& player,
        int128 delta, OT_ROLE role, bool passive)
{
    BaseOT baseOT(128, 128, &player, INV_ROLE(role));
    PRNG G;
    G.ReSeed();
    baseOT.set_receiver_inputs(delta);
    baseOT.exec_base(false);
    return OTExtensionWithMatrix(baseOT, &player, passive);
}

Thank you for your patient response throughout.

[mkskeller]

I'm sorry, I have once again confused a few concepts between the OTs. Are the Softspoken extended OTs of The Yao protocol implementation based on DotMaliciousLeakyReceiver or some other protocol, rather than SimpleOT?

Yes, the OT extension in the Yao protocol does invoke said class in libOTe.

Can I use KyberOT as the baseOT to generate the SoftSpoken (or KOS) implementation of these extended OTs and apply them to the Yao Protocol? Which code files do I need to review and modify?

If you want to plug in another base OT, you only need to to modify BaseOT.cpp.

[mkskeller]

In fact, I am still uncertain about how the OT extension is invoked in The Yao protocol implementation. I could only find the following code snippets in YaoGarbler.cpp and YaoEvaluator.cpp:

In YaoGarbler.cpp:

ot_ext(OTExtensionWithMatrix::setup(player, {}, RECEIVER, true))

In YaoEvaluator.cpp:

ot_ext(OTExtensionWithMatrix::setup(player,
        master.get_delta().get<__m128i>(), SENDER, true))

This calls the base OT for once.

However, I believe it is relevant that "Base OTs are executed both ways by default even when not needed."

OTExtensionWithMatrix OTExtensionWithMatrix::setup(TwoPartyPlayer& player,
        int128 delta, OT_ROLE role, bool passive)
{
    BaseOT baseOT(128, 128, &player, INV_ROLE(role));
    PRNG G;
    G.ReSeed();
    baseOT.set_receiver_inputs(delta);
    baseOT.exec_base(false);
    return OTExtensionWithMatrix(baseOT, &player, passive);
}

Indeed, I was wrong about this. The role is set to the relevant one, but the roles are reversed for the base OTs.

[DoctorJackson]

Yes, the OT extension in the Yao protocol does invoke said class in libOTe.

If you want to plug in another base OT, you only need to to modify BaseOT.cpp.

I want to understand that since the Yao protocol only invokes DotMaliciousLeaky instead of SimpleOT written in BaseOT.cpp, how would modifying BaseOT.cpp affect the implementation of OT in the Yao protocol? Because my ultimate goal is to use KyberOT as the BaseOT to implement the Yao protocol. Thanks!

Indeed, I was wrong about this. The role is set to the relevant one, but the roles are reversed for the base OTs.

BTW, do I need to reverse the incorrect role assignment back to its original state? Like:

BaseOT baseOT(128, 128, &player, role );

[mkskeller]

I don't understand the first question. Can you rephrase it?

The role reversal is an inherent property of IKNP-style OT extension.

[DoctorJackson]

Of course.

I want to use KyberOT as the BaseOT to implement the Yao protocol finally. But Q1: Do the Yao protocol invoke BaseOT.cpp?

(Because you said, The Yao protocol implementation doesn't use base OTs but extended OTs. ) Q2: Or do the extended OTs in the Yao protocol invoke BaseOT.cpp?

Q3: If I modify BaseOT.cpp. to plug in Kyber OT, could I achieve my goal?

[mkskeller]

Q1: Yes Q2: Not directly, the base OTs are delivered to the OT extension in OTExtensionWithMatrix.cpp. Q3: Yes

[DoctorJackson]

Thanks a lot!!!

And I apologize for the misunderstanding caused by my unfamiliarity with IKNP-Extension.

[DoctorJackson]

Thanks to your help, I have successfully achieved my goal. I have some new questions:

Q1: How can I output the inputs and outputs of both parties in Yao's Protocol? Could you please tell me which file to modify?

Q2: I noticed the line "Global data sent = 204.801 MB (all parties)" in the final output of Yao's Protocol. Does this communication cost include the preprocessing phase (i.e., OT)?

Q3: I'm also interested in the implementation of Shamir's secret sharing [Sha79] itself (but not MPC based on secret sharing). I want to try generating a random string and create a (t, n) secret sharing for it, obtaining n shares, and finally reconstructing the string using t+1 shares. Which files should I check and modify for this?

I hope these questions don't bother you. Thank you for your patient assistance all along. You are truly a kind person, and SPDZ is an incredibly powerful and useful project.

[mkskeller]

Q1: What do you mean by inputs/outputs? Q2: Yes Q3: The two operations are defined in Protocols/ShamirInput.hpp and Protocols/ShamirMC.hpp, see https://mp-spdz.readthedocs.io/en/latest/low-level.html#_CPPv4I0E9InputBase and https://mp-spdz.readthedocs.io/en/latest/low-level.html#_CPPv4I0E14MAC_Check_Base for a documentation of the interface.

[DoctorJackson]

Sorry, I mean the inputs and outputs of the evaluator, i.e., the inputs and outputs of the circuits. For example, I run the aes_circuit.mpc, and I want to know the plaintext and ciphertext of the AES circuit.

aes_circuit.mpc

from circuit import Circuit
sb128 = sbits.get_type(128)
key = sb128(0x2b7e151628aed2a6abf7158809cf4f3c)
plaintext = sb128(0x6bc1bee22e409f96e93d7e117393172a)
n = 1
aes128 = Circuit('aes_128')
ciphertexts = aes128(sbitvec([key] * n), sbitvec([plaintext] * n))
ciphertexts.elements()[n - 1].reveal().print_reg()

Q1: Is the input of the evaluator plaintext = sb128(0x6bc1bee22e409f96e93d7e117393172a)？ Q2: Is the input of the garbler key = sb128(0x2b7e151628aed2a6abf7158809cf4f3c)？

On the other hand, I see the output of yao-party.x: Reg[0] = 0x3ad77bb40d7a3660a89ecaf32466ef97 # Q3: Is it the output of the evaluator?

[mkskeller]

Q1/Q2: No, assuming you mean input labels. For publicly known values (as such specified in the code), the evaluator input is always 0, and the garbler inputs are 0/delta or delta/0 depending on the public bit. The delta is the global delta according to the free-XOR garbling scheme. Q3: This is the combination of the bits forming an AES ciphertext. The evaluator doesn't learn it directly, instead the output labels are sent to the garbler who deduces them and sends the bits back to the evaluator.

[DoctorJackson]

Thanks. Q1/Q2: I don't mean input labels. I mean the actual original input, i.e, the plaintext of AES circuits.

For publicly known values (as such specified in the code) Are you referring to the key and the plaintext of AES here? Do you mean both parties must know the key and the plaintext when executing the Yao's Protocol?

I am confused because I believed that the key is only known to the garbler, while the plaintext is only known to the evaluator.

Q3: I see now. Thanks.

[mkskeller]

Are you referring to the key and the plaintext of AES here? Do you mean both parties must know the key and the plaintext when executing the Yao's Protocol?

No, that would contradict the premise of MPC. That's just how it's done in the example program to simplify the specification. MP-SPDZ works by both parties agreeing on a representation of the computation. Any data contained in this specification will be known by both parties and treated accordingly, but if converted to a secret type, secret computation will be run even though the data is publicly known. See the documentation on how to input data only known to one party: https://mp-spdz.readthedocs.io/en/latest/io.html#private-inputs-from-computing-parties

I am confused because I believed that the key is only known to the garbler, while the plaintext is only known to the evaluator.

This is not the case for the example program but possible using the private input functionality mentioned above.

[DoctorJackson]

Thank you! I will carefully read it and try again. Could you please let me know if there are specific examples provided in the source code for invoking the functionality of "Private Inputs from Computing Parties"?

[mkskeller]

tutorial.mpc contains examples of private inputs.

[DoctorJackson]

Thanks.