secretflow/yacl

Problems in ferret_ote

maths644311798 opened this issue · 9 comments

maths644311798 commented

(1) In /ot/ferret_ote_rn.h, the formulas for calculating batch_size are different in MpCotRNHelper() and MpCotRNSend(). This may lead to inaccurate evaluation of number of bits needed.

(2) In /ot/ferret_ote_un.h, there is an annotation // https://eprint.iacr.org/2020/924.pdf, section 4, figure 6. I think it should be figure 7.

(3) In inline void MpCotUNSend( ), /ot/ferret_ote_un.h.
GywzOtExtSend(ctx, cot_slice, spot_option, absl::MakeSpan(s[i])) should be
GywzOtExtSend(ctx, cot_slice, spcot_range_n, absl::MakeSpan(s[i])) .
slice_begin += math::Log2Ceil(spcot_range_n); can be slice_begin += spot_option;
The same problem appears in MpCotUNRecv().
(4)

if (!cuckoo_index.bins()[i].IsEmpty()) {  // if bin is not empty
      spcot_idx = simple_map->operator[](i).at(
          idxes[cuckoo_index.bins()[i].InputIdx()]);
    }

Due to cuckoo_index.Insert(), the InputIndex will have input_offset = hashes_.size() (in cuckoo_index.cc). Then this behavior is different from MakeSimpleMap() which does not have such an offset.

Jamie-Cui commented

I can confirm that (2) (3) are typos and bugs.

maths644311798 commented

As for (4), I doubt the sentence candidates[i].set_encoded(input_offset + i) in CuckooIndex::Insert is wrong because what we want to encode is i .

Jamie-Cui commented

The encoded bin looks like the following,

  // |----------uint64_t---------------------|
  // |  8-bit  |        56-bit               |
  // | hashidx |     input idx               |
  //   00000001_0000000000000...0000000000010
  // |---------------------------------------|

Therefore, what we actually do in Insert(), is to initiate a vector<Bin> with the size of inserted values (say, n). Then we set each Bin elements with its input index (that's input_offset +1).

Why input_offset + i?

The cuckoo table may insert many vectors, say we have vector a and vector b, the cuckoo table first insert all elements in a, which set the cuckoo's input_offset to a.size(). That makes b's insertion starting with the index a.size().

Later if we want to use cuckoo table, and gets an index x, if x>=a.size(), we will know x refers to b[x-a.size()], if x <a.size(), x refers to a[x].

maths644311798 commented

OK, I understand the design of input_offset now. Then (4) is solved.

Jamie-Cui commented

@liang-xiaojian would you like to answer to (1) ?

liang-xiaojian commented

Thanks for your comments. :)
For question (1), extreme values for LpnParam might lead to some problems. Currently, we set LpnParam to {10485760, 452000, 1280}. As result, batch_size is fixed at 8196 in MpCotRNHelper().

FYI, the purpose of MpCotRNHelper is to evaluate the number of 'base COT' for FerretOte, not for MpCot.

maths644311798 commented

the purpose of MpCotRNHelper is to evaluate the number of 'base COT' for FerretOte, not for MpCot.

The purpose of MpCotRNHelper is to evaluate the number of base COT for MpCot, which is consumed in FerretOte, right? FerretOte would call MpCot for several times until it generates enough COTs.

liang-xiaojian commented

Yes, more detail could be found in the paper, figure 5.

maths644311798 commented

As for (1), batch_size in MpCotRNHelper() is always bigger than or equal to the one in MpCotRNSend, when idx_range and idx_num are the same in the two functions. So this will not cause big problems.
I have pulled a request for (2) and (3). :)

  • 👍2