Question about slient VOLE #125
Comments
|
yes, you can do this but it requires some manual work. So each silent protocol consumes some number of base OT. This has to happen and there is no avoiding it (well technically a PCF would avoid it but those can't implemented and less efficient). First, there is the simple but less efficient way. Each Vole internally has an IKNP-styled OT extension protocol. You can simply set the 128 base OTs for these and then this will be used to generate the consumed silent base OTs. In this way, you dont need to run public key-based OTs each time. However, this adds to the round complexity. The more efficient alternative:
You should perform
where
|
|
Thank you very much for your reply. I have some following questions:
Here is an example of manually set the base OT which works fine: void testBatch(u64 m, u64 n) {
auto chl = cp::LocalAsyncSocket::makePair();
PRNG prng(sysRandomSeed());
NoisyVoleSender ns;
NoisyVoleReceiver nr;
IknpOtExtReceiver otr;
IknpOtExtSender ots;
SilentVoleSender sender;
sender.configure(m);
SilentVoleReceiver receiver;
receiver.configure(m);
u64 b = sender.silentBaseOtCount();
cout << "b: " << b << endl;
cout << "prepare ok" << endl;
for (u64 i = 0; i < n; i++) {
sender.configure(m);
receiver.configure(m);
vector<block> rMsgs(b);
vector<array<block, 2>> sMsgs(b);
auto choice = receiver.sampleBaseChoiceBits(prng);
cp::sync_wait(
macoro::when_all_ready(otr.receive(choice, rMsgs, prng, chl[0]),
ots.send(sMsgs, prng, chl[1])));
auto AA = receiver.sampleBaseVoleVals(prng);
vector<block> rShare(AA.size());
vector<block> sShare(AA.size());
block delta = prng.get();
cp::sync_wait(
macoro::when_all_ready(ns.send(delta, sShare, prng, otr, chl[0]),
nr.receive(AA, rShare, prng, ots, chl[1])));
cout << "delta " << delta << endl;
cout << "send { " << sShare[0] << ", " << sShare[1] << "}" << endl;
cout << "recv { " << rShare[0] << ", " << rShare[1] << "}" << endl;
cout << "choice " << AA[0] << ", " << AA[1] << endl;
cout << "left " << (rShare[0] ^ sShare[0]) << endl;
cout << "right " << AA[0].gf128Mul(delta) << endl;
receiver.setSilentBaseOts(rMsgs, rShare);
sender.setSilentBaseOts(sMsgs, sShare);
vector<block> z0(m);
vector<block> z1(m);
vector<block> c(m);
cp::sync_wait(
macoro::when_all_ready(sender.silentSend(delta, z1, prng, chl[0]),
receiver.silentReceive(c, z0, prng, chl[1])));
cout << "delta " << delta << endl;
cout << "send { " << z1[0] << ", " << z1[1] << "}" << endl;
cout << "recv { " << z0[0] << ", " << z0[1] << "}" << endl;
cout << "choice " << c[0] << ", " << c[1] << endl;
cout << "left " << (z0[0] ^ z1[0]) << endl;
cout << "right " << c[0].gf128Mul(delta) << endl;
}
}but when I try it batch the base OT for silent VOLE, it crashes for the second void testBatch(u64 m, u64 n) {
auto chl = cp::LocalAsyncSocket::makePair();
PRNG prng(sysRandomSeed());
NoisyVoleSender ns;
NoisyVoleReceiver nr;
IknpOtExtReceiver otr;
IknpOtExtSender ots;
SilentVoleSender sender;
sender.configure(m);
SilentVoleReceiver receiver;
receiver.configure(m);
u64 b = sender.silentBaseOtCount();
cout << "b: " << b << endl;
BitVector combined;
vector<block> rMsgs(b * n);
vector<array<block, 2>> sMsgs(b * n);
span<block> rMsgSpan(rMsgs);
span<array<block, 2>> sMsgSpan(sMsgs);
auto choice = receiver.sampleBaseChoiceBits(prng);
auto AA = receiver.sampleBaseVoleVals(prng);
u64 shareSize = AA.size();
cout << "shareSize: " << shareSize << endl;
vector<block> rShares(shareSize * n);
vector<block> sShares(shareSize * n);
span<block> rShareSpan(rShares);
span<block> sShareSpan(sShares);
vector<block> deltas;
for (u64 i = 0; i < n; i++) {
auto choice = receiver.sampleBaseChoiceBits(prng);
combined.append(choice);
auto AA = receiver.sampleBaseVoleVals(prng);
block delta = prng.get();
deltas.push_back(delta);
auto rs = rShareSpan.subspan(i * shareSize, shareSize);
auto ss = sShareSpan.subspan(i * shareSize, shareSize);
cp::sync_wait(
macoro::when_all_ready(ns.send(delta, rs, prng, otr, chl[0]),
nr.receive(AA, ss, prng, ots, chl[1])));
cout << "delta " << delta << endl;
cout << "send { " << rs[0] << ", " << rs[1] << "}" << endl;
cout << "recv { " << ss[0] << ", " << ss[1] << "}" << endl;
cout << "choice " << AA[0] << ", " << AA[1] << endl;
cout << "left " << (rs[0] ^ ss[0]) << endl;
cout << "right " << AA[0].gf128Mul(delta) << endl;
}
cp::sync_wait(
macoro::when_all_ready(otr.receive(combined, rMsgs, prng, chl[0]),
ots.send(sMsgs, prng, chl[1])));
cout << "prepare ok" << endl;
for (u64 i = 0; i < n; i++) {
sender.configure(m);
receiver.configure(m);
auto rs = rShareSpan.subspan(i * shareSize, shareSize);
auto ss = sShareSpan.subspan(i * shareSize, shareSize);
receiver.setSilentBaseOts(rMsgSpan.subspan(i * b, b), rs);
sender.setSilentBaseOts(sMsgSpan.subspan(i * b, b), ss);
vector<block> z0(m);
vector<block> z1(m);
vector<block> c(m);
cp::sync_wait(
macoro::when_all_ready(sender.silentSend(deltas[i], z1, prng, chl[0]),
receiver.silentReceive(c, z0, prng, chl[1])));
cout << "delta " << deltas[i] << endl;
cout << "send { " << z1[0] << ", " << z1[1] << "}" << endl;
cout << "recv { " << z0[0] << ", " << z0[1] << "}" << endl;
cout << "choice " << c[0] << ", " << c[1] << endl;
cout << "left " << (z0[0] ^ z1[0]) << endl;
cout << "right " << c[0].gf128Mul(deltas[i]) << endl;
}
} |
In general, each batch can have its own delta. Below i show how to do it for one delta that is shared between all batches. This way, you get one large vole. If you want different batches to have different deltas, you will need to run
void senderReceiver() {
auto chl = cp::LocalAsyncSocket::makePair();
u64 numBatches = 10;
u64 batchSize = 1 << 16;
PRNG prng(oc::ZeroBlock);
// each vole will have the correlation
// mA + mB = mC * delta
//
// We do this by first computing a sparse C' and
// the defining C = G * C' where G is a compressing
// matrix. We have a special way of generating a
// secret sharing of C' * delta. Let these shares be A',B'.
// Then we have
//
// A' + B' = C' * delta
//
// We can simply multiply A', and B' by G to get
//
// A = G * A'
// B = G * B'
//
// such that
//
// A + B = C * delta
//
// This "special way" generating of C' requires two things
//
// 1) Base OTs there the choice bits for these OT index the
// non-zero of C'. That is, say we have choice bits
//
// b00,b01,...,b0m,
// ...
// bn0,bn1,...,bnm,
//
// Then we will define C'_{bi} as a random value, where the
// bits of bi are (bi0,bi1,...,bim).
//
// 2) We need to choose what the value of the C'_{bi} position
// are. This is done with recv.sampleBaseVoleVals(...); We then
// need generate the secret sharing of these values times delta.
// That is, perform a noisy vole with input delta and the C'_{bi}
// values.
//
SilentVoleReceiver recv;
SilentVoleSender send;
recv.configure(batchSize);
send.configure(batchSize);
u64 baseOtsPer = send.silentBaseOtCount();
u64 baseVolePer = send.baseVoleCount();
NoisyVoleReceiver nRecv;
NoisyVoleSender nSend;
std::vector<block> seeds(numBatches);
//std::vector<RecvSetup> recvSetups(numBatches);
//std::vector<SendSetup> sendSetups(numBatches);
BitVector baseChoice; baseChoice.reserve(baseOtsPer * numBatches);
std::vector<block> baseVole; baseVole.reserve(baseVolePer * numBatches);
for (u64 i = 0; i < numBatches; ++i)
{
seeds[i]= prng.get();
PRNG setupSeed(seeds[i]);
auto bits = recv.sampleBaseChoiceBits(setupSeed);
auto CC = recv.sampleBaseVoleVals(setupSeed);
baseChoice.append(bits);
baseVole.insert(baseVole.end(), CC.begin(), CC.end());
}
SoftSpokenShOtSender<> baseSend;
SoftSpokenShOtReceiver<> baseRecv;
std::vector<std::array<block, 2>> baseSendOtMsg(baseOtsPer * numBatches);
std::vector<block> baseRecvOtMsg(baseOtsPer * numBatches);
std::vector<block> baseRecvVole(baseVolePer * numBatches);
std::vector<block> baseSendVole(baseVolePer * numBatches);
block delta = prng.get();
oc::DefaultBaseOT noisyBaseSendGen, noisyBaseRecvGen;
// generate the base OTs and the VOLE.
auto res = macoro::sync_wait(macoro::when_all_ready(
baseSend.send(baseSendOtMsg, prng, chl[0]),
baseRecv.receive(baseChoice, baseRecvOtMsg, prng, chl[1]),
nSend.send(delta, baseSendVole, prng, noisyBaseSendGen, chl[0].fork()),
nRecv.receive(baseVole, baseRecvVole, prng, noisyBaseRecvGen, chl[1].fork())
));
// make sure they succeeded.
std::get<0>(res).result();
std::get<1>(res).result();
std::get<2>(res).result();
std::get<3>(res).result();
for (u64 i = 0; i < numBatches; ++i)
{
PRNG setupSeed(seeds[i]);
recv.configure(batchSize);
send.configure(batchSize);
auto ithBaseRecvOtMsg = std::vector<block>(
baseRecvOtMsg.begin() + i * baseOtsPer,
baseRecvOtMsg.begin() + i * baseOtsPer + baseOtsPer);
auto ithBaseRecvVole = std::vector<block>(
baseRecvVole.begin() + i * baseVolePer,
baseRecvVole.begin() + i * baseVolePer + baseVolePer);
auto ithBaseSendOtMsg = std::vector<std::array<block, 2>>(
baseSendOtMsg.begin() + i * baseOtsPer,
baseSendOtMsg.begin() + i * baseOtsPer + baseOtsPer);
auto ithBaseSendVole = std::vector<block>(
baseSendVole.begin() + i * baseVolePer,
baseSendVole.begin() + i * baseVolePer + baseVolePer);
// if you simply have a different recv'er for each batch then you dont need to resample.
recv.sampleBaseChoiceBits(setupSeed);
recv.sampleBaseVoleVals(setupSeed);
recv.setSilentBaseOts(ithBaseRecvOtMsg, ithBaseRecvVole);
send.setSilentBaseOts(ithBaseSendOtMsg, ithBaseSendVole);
// A + B = C * delta
std::vector<block> A(batchSize), B(batchSize), C(batchSize);
auto res = macoro::sync_wait(macoro::when_all_ready(
send.silentSend(delta, B, prng, chl[0]),
recv.silentReceive(C, A, prng, chl[1])
));
std::get<0>(res).result();
std::get<1>(res).result();
for (u64 j = 0; j < batchSize; ++j)
{
if((A[j] ^ B[j]) != delta.gf128Mul(C[j]))
throw RTE_LOC;
}
}
} |
|
Thank you so much for your help! The code and explanation are awesome and work great for me. A new question is, to have independent delta for the VOLE, we should have one small noisy VOLE for each silent VOLE we need. I tried to implement this and it worked, but it seems this method have similar running time vs separate silent VOLE instances, and using noisy VOLE has better running time. I think it might make sense since my VOLE size is small( |
|
For multiple delta values you'll want to not use DefaultBaseOt. Instead you'll want to use another soft-spoken ot there. Do you care what the value of delta is or you just want the to be different? |
|
I just want different deltas, I used iknp to replace BaseOt and SoftSpoken. |
|
Here is the most computationally efficient way of doing it. Compared to the previous, this one
void senderReceiver() {
auto chl = cp::LocalAsyncSocket::makePair();
u64 numBatches = 10;
u64 batchSize = 1 << 16;
PRNG prng(oc::ZeroBlock);
// each vole will have the correlation
// mA + mB = mC * delta
//
// We do this by first computing a sparse C' and
// the defining C = G * C' where G is a compressing
// matrix. We have a special way of generating a
// secret sharing of C' * delta. Let these shares be A',B'.
// Then we have
//
// A' + B' = C' * delta
//
// We can simply multiply A', and B' by G to get
//
// A = G * A'
// B = G * B'
//
// such that
//
// A + B = C * delta
//
// This "special way" generating of C' requires two things
//
// 1) Base OTs there the choice bits for these OT index the
// non-zero of C'. That is, say we have choice bits
//
// b00,b01,...,b0m,
// ...
// bn0,bn1,...,bnm,
//
// Then we will define C'_{bi} as a random value, where the
// bits of bi are (bi0,bi1,...,bim).
//
// 2) We need to choose what the value of the C'_{bi} position
// are. This is done with recv.sampleBaseVoleVals(...); We then
// need generate the secret sharing of these values times delta.
// That is, perform a noisy vole with input delta and the C'_{bi}
// values.
//
SilentVoleReceiver recv;
SilentVoleSender send;
recv.configure(batchSize);
send.configure(batchSize);
u64 baseOtsPer = send.silentBaseOtCount();
u64 baseVolePer = send.baseVoleCount();
//////////////////////////////////////////////////////
// Each silent Vole will require baseOtsPer OTs. Additionally
// we will generate 128 extra. These will be used to initialize
// a second softspoken in the other direction. This second softspoken
// will generate OTs corresponding to the delta values that we will
// be using. One OT for each bit of the 128s of the numBatches delta values.
// Lets get the choice bits that each silent OT will use along with the
// base vole values.
std::vector<block> seeds(numBatches);
BitVector baseChoice; baseChoice.reserve(baseOtsPer * numBatches + 128);
std::vector<block> baseVole; baseVole.reserve(baseVolePer * numBatches);
std::vector<std::array<block, 2>> baseSendOtMsg(baseOtsPer * numBatches + 128);
std::vector<block> baseRecvOtMsg(baseOtsPer * numBatches + 128);
BitVector noisySoftSpokenChoice(128);
{
for (u64 i = 0; i < numBatches; ++i)
{
seeds[i] = prng.get();
PRNG setupSeed(seeds[i]);
auto bits = recv.sampleBaseChoiceBits(setupSeed);
auto CC = recv.sampleBaseVoleVals(setupSeed);
baseChoice.append(bits);
baseVole.insert(baseVole.end(), CC.begin(), CC.end());
}
// extra 128 bits that are used later.
noisySoftSpokenChoice.randomize(prng);
baseChoice.append(noisySoftSpokenChoice);
// generate the base OTs.
SoftSpokenShOtSender<> baseSend;
SoftSpokenShOtReceiver<> baseRecv;
auto res0 = macoro::sync_wait(macoro::when_all_ready(
baseSend.send(baseSendOtMsg, prng, chl[0]),
baseRecv.receive(baseChoice, baseRecvOtMsg, prng, chl[1])
));
// make sure they succeeded.
std::get<0>(res0).result();
std::get<1>(res0).result();
}
// now we will generate the OTs for the bits of the deltas.
// The extra 128 ots we generated above will be used to initialize
// this second instance of softspoken.
// sample the deltas
BitVector deltas(numBatches * 128);
deltas.randomize(prng);
std::vector<block> deltaRecvOts(numBatches * 128);
std::vector<std::array<block, 2>> deltaSendOts(numBatches * 128);
{
SoftSpokenShOtSender<> noisyBaseSendGen;
SoftSpokenShOtReceiver<> noisyBaseRecvGen;
auto noisyBaseRecvOtMsg = std::vector<block>(
baseRecvOtMsg.begin() + numBatches * baseOtsPer,
baseRecvOtMsg.end());
auto noisyBaseSendOtMsg = std::vector<std::array<block, 2>>(
baseSendOtMsg.begin() + numBatches * baseOtsPer,
baseSendOtMsg.end());
noisyBaseSendGen.setBaseOts(noisyBaseRecvOtMsg, noisySoftSpokenChoice);
noisyBaseRecvGen.setBaseOts(noisyBaseSendOtMsg);
auto res1 = macoro::sync_wait(macoro::when_all_ready(
noisyBaseRecvGen.receive(deltas, deltaRecvOts, prng, chl[0]),
noisyBaseSendGen.send(deltaSendOts, prng, chl[1])
));
// make sure they succeeded.
std::get<0>(res1).result();
std::get<1>(res1).result();
}
//////////////////////////////////////////////////////
// now we will generate the base Voles with the
// OTs for the delta values.
std::vector<block> baseRecvVole(baseVolePer * numBatches);
std::vector<block> baseSendVole(baseVolePer * numBatches);
{
NoisyVoleReceiver nRecv;
NoisyVoleSender nSend;
std::vector<macoro::eager_task<>> tasks; tasks.reserve(numBatches * 2);
for (u64 i = 0; i < numBatches; ++i)
{
auto ithDelta = deltas.getSpan<block>()[i];
auto ithDeltaRecvOtMsg = span<block>(
deltaRecvOts.begin() + i * 128,
deltaRecvOts.begin() + i * 128 + 128);
auto ithDeltaSendOtMsg = span<std::array<block, 2>>(
deltaSendOts.begin() + i * 128,
deltaSendOts.begin() + i * 128 + 128);
auto ithBaseRecvVole = span<block>(
baseRecvVole.begin() + i * baseVolePer,
baseRecvVole.begin() + i * baseVolePer + baseVolePer);
auto ithBaseSendVole = span<block>(
baseSendVole.begin() + i * baseVolePer,
baseSendVole.begin() + i * baseVolePer + baseVolePer);
auto ithBaseVole = span<block>(
baseVole.begin() + i * baseVolePer,
baseVole.begin() + i * baseVolePer + baseVolePer);
// here we start the noisy vole protocols but don't wait for them
// to finish. In this way we can start all of them.
auto ithRecvTask = nRecv.receive(ithBaseVole, ithBaseRecvVole, prng, ithDeltaSendOtMsg, chl[0].fork());
auto ithSendTask = nSend.send(ithDelta, ithBaseSendVole, prng, ithDeltaRecvOtMsg, chl[1].fork());
tasks.emplace_back(std::move(ithRecvTask) | macoro::make_eager());
tasks.emplace_back(std::move(ithSendTask) | macoro::make_eager());
}
// Now wait for all of them to complete.
for (u64 i = 0; i < tasks.size(); ++i)
{
macoro::sync_wait(tasks[i]);
}
}
// Now we can execute the main phase whenever we want.
for (u64 i = 0; i < numBatches; ++i)
{
auto ithDelta = deltas.getSpan<block>()[i];
PRNG setupSeed(seeds[i]);
recv.configure(batchSize);
send.configure(batchSize);
auto ithBaseRecvOtMsg = span<block>(
baseRecvOtMsg.begin() + i * baseOtsPer,
baseRecvOtMsg.begin() + i * baseOtsPer + baseOtsPer);
auto ithBaseRecvVole = span<block>(
baseRecvVole.begin() + i * baseVolePer,
baseRecvVole.begin() + i * baseVolePer + baseVolePer);
auto ithBaseSendOtMsg = span<std::array<block, 2>>(
baseSendOtMsg.begin() + i * baseOtsPer,
baseSendOtMsg.begin() + i * baseOtsPer + baseOtsPer);
auto ithBaseSendVole = span<block>(
baseSendVole.begin() + i * baseVolePer,
baseSendVole.begin() + i * baseVolePer + baseVolePer);
// if you simply have a different recv'er for each batch then you dont need to resample.
recv.sampleBaseChoiceBits(setupSeed);
recv.sampleBaseVoleVals(setupSeed);
recv.setSilentBaseOts(ithBaseRecvOtMsg, ithBaseRecvVole);
send.setSilentBaseOts(ithBaseSendOtMsg, ithBaseSendVole);
// A + B = C * delta
std::vector<block> A(batchSize), B(batchSize), C(batchSize);
auto res = macoro::sync_wait(macoro::when_all_ready(
send.silentSend(ithDelta, B, prng, chl[0]),
recv.silentReceive(C, A, prng, chl[1])
));
std::get<0>(res).result();
std::get<1>(res).result();
for (u64 j = 0; j < batchSize; ++j)
{
if ((A[j] ^ B[j]) != ithDelta.gf128Mul(C[j]))
throw RTE_LOC;
}
}
} |
|
Makes sense. Thank you so much! |
|
Another question I got is, in volepsi(https://github.com/Visa-Research/volepsi/blob/687ca2dd03fd663a216b6ede9d2707f6d5b10b00/volePSI/GMW/SilentTripleGen.h#L100), we got |
|
Given an ot: (m0, m1), (a, ma) One can get an Ole for bits: (a, b), (c, d) such that ac=b + d Observe Where b=lsb(ma), c=lsb(m0+m1), d=lsb(m0). So that's what the code is doing. Generating a lot of a, b, c, d. These are each a single bit. |
|
Thank you very much. I still have questions about the Noisy VOLE. I want to learn how it worked, why we got |
|
Yeah, that comment isn't accurate. The protocol is simple. The sender has a k-bit value d=(d_{k-1},...,d0) where d=sum_i 2^i d_i. The receiver has n values v_0,...,v_{n-1}. Each is k bits. We do k ots, the sender is the ot receiver with choice bit di for the ith ot. The receiver is the ot sender. For the ith ot,the receiver gives two messages m_{i,0}=(r_{i,0},...,r_{i,n-1}) The sender learns m_{i,d_i}= (r_{i,0}+d_i2^i * v_0,...,r_{i,n-1}+d_i2^i * v_{n-1}) By adding all these m_{i,d_i} together, the sender obtains (t_0,...,t_{n-1})=(s_0+d* v_0,...,s_{n-1}*d_i v_{n-1}) where s_j= sum_i r_{i,j} The receiver can compute s_j and the sender t_j. These are the desired output, a sharing of d*(v_0,...,v_{n-1}) Instead of sending mi0 as the ot message, you can simply defines these as the prng output of the random ot zero message. |
From my understanding, the
SilentVoleSenderandSilentVoleReceivermust be pre-configured with the size of VOLE, and they got reset once a pair ofsilentSendandsilentReceiveis finished, so reusing a pair of instances is not very different from creating new instances, and every pair ofsilentSendandsilentReceiveneeds new base silent OT operations, which is very different from IKNP style OT extensions. Is my understanding correct? If so, is possible to make slient VOLE behave like IKNP?The text was updated successfully, but these errors were encountered: