123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746 |
- #ifndef __DUORAM_HPP__
- #define __DUORAM_HPP__
- #include <optional>
- #include <functional>
- #include "types.hpp"
- #include "mpcio.hpp"
- #include "coroutine.hpp"
- #include "rdpf.hpp"
- template <typename T>
- class Duoram {
-
-
-
-
-
-
- int player;
- size_t oram_size;
-
-
- std::vector<T> database;
- std::vector<T> blind;
- std::vector<T> &p0_blind;
- std::vector<T> peer_blinded_db;
- std::vector<T> &p1_blind;
- public:
-
- using type = T;
-
- class Shape;
-
- class Flat;
- class Pad;
- class Stride;
- class Path;
-
- template <typename U, nbits_t WIDTH>
- class OblivIndex;
-
- Duoram(int player, size_t size);
-
- inline size_t size() { return oram_size; }
-
- Flat flat(MPCTIO &tio, yield_t &yield, size_t start = 0,
- size_t len = 0) {
- return Flat(*this, tio, yield, start, len);
- }
-
- void dump() const;
- };
- template <typename T>
- class Duoram<T>::Shape {
-
-
- friend class Flat;
- friend class Pad;
- friend class Stride;
- friend class Path;
- template <typename U, nbits_t WIDTH>
- friend class OblivIndex;
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- template <typename U, typename FT, typename FST, typename Sh, nbits_t WIDTH>
- class MemRefS;
-
- template <typename FT, typename FST>
- class MemRefExpl;
-
-
-
-
- template <typename U, typename Sh>
- class MemRefInd;
- protected:
-
-
-
- const Shape &parent;
-
- Duoram &duoram;
-
- size_t shape_size;
-
-
- nbits_t addr_size;
-
- address_t addr_mask;
-
- MPCTIO &tio;
- yield_t &yield;
-
-
-
-
-
-
-
- bool explicitmode;
-
-
- void set_shape_size(size_t sz);
-
-
- Shape(const Shape &parent, Duoram &duoram, MPCTIO &tio,
- yield_t &yield) : parent(parent), duoram(duoram), shape_size(0),
- tio(tio), yield(yield), explicitmode(false) {}
-
- Shape(const Shape ©_from, MPCTIO &tio, yield_t &yield) :
- parent(copy_from.parent), duoram(copy_from.duoram),
- shape_size(copy_from.shape_size),
- addr_size(copy_from.addr_size), addr_mask(copy_from.addr_mask),
- tio(tio), yield(yield),
- explicitmode(copy_from.explicitmode) {}
-
-
-
-
-
-
-
- virtual size_t indexmap(size_t idx) const = 0;
-
-
- virtual inline std::tuple<T&,T&> get_server(size_t idx,
- std::nullopt_t null = std::nullopt) const {
- size_t parindex = indexmap(idx);
- if (&(this->parent) == this) {
- return std::tie(
- duoram.p0_blind[parindex],
- duoram.p1_blind[parindex]);
- } else {
- return this->parent.get_server(parindex, null);
- }
- }
-
-
- virtual inline std::tuple<T&,T&,T&> get_comp(size_t idx,
- std::nullopt_t null = std::nullopt) const {
- size_t parindex = indexmap(idx);
- if (&(this->parent) == this) {
- return std::tie(
- duoram.database[parindex],
- duoram.blind[parindex],
- duoram.peer_blinded_db[parindex]);
- } else {
- return this->parent.get_comp(parindex, null);
- }
- }
-
-
- template <typename FT>
- inline std::tuple<FT&,FT&> get_server(size_t idx, FT T::*field) const {
- size_t parindex = indexmap(idx);
- if (&(this->parent) == this) {
- return std::tie(
- duoram.p0_blind[parindex].*field,
- duoram.p1_blind[parindex].*field);
- } else {
- return this->parent.get_server(parindex, field);
- }
- }
-
-
-
- template <typename FT>
- inline std::tuple<FT&,FT&,FT&> get_comp(size_t idx, FT T::*field) const {
- size_t parindex = indexmap(idx);
- if (&(this->parent) == this) {
- return std::tie(
- duoram.database[parindex].*field,
- duoram.blind[parindex].*field,
- duoram.peer_blinded_db[parindex].*field);
- } else {
- return this->parent.get_comp(parindex, field);
- }
- }
- public:
-
- inline size_t size() const { return shape_size; }
-
-
-
- void init(size_t value) {
- T v;
- v.set(value);
- init([v] (size_t i) { return v; });
- }
-
- void init(const T &value) {
- init([value] (size_t i) { return value; });
- }
-
-
- void init() {
- T deflt;
- init(deflt);
- }
-
-
-
-
- void init(std::function<size_t(size_t)> f) {
- int player = tio.player();
- if (player < 2) {
- for (size_t i=0; i<shape_size; ++i) {
- auto [DB, BL, PBD] = get_comp(i);
- BL.set(0);
- if (player) {
- DB.set(f(i));
- PBD.set(0);
- } else {
- DB.set(0);
- PBD.set(f(i));
- }
- }
- } else {
- for (size_t i=0; i<shape_size; ++i) {
- auto [BL0, BL1] = get_server(i);
- BL0.set(0);
- BL1.set(0);
- }
- }
- }
-
-
-
-
- void init(std::function<T(size_t)> f) {
- int player = tio.player();
- if (player < 2) {
- for (size_t i=0; i<shape_size; ++i) {
- auto [DB, BL, PBD] = get_comp(i);
- BL = T();
- if (player) {
- DB = f(i);
- PBD = T();
- } else {
- DB = T();
- PBD = f(i);
- }
- }
- } else {
- for (size_t i=0; i<shape_size; ++i) {
- auto [BL0, BL1] = get_server(i);
- BL0 = T();
- BL1 = T();
- }
- }
- }
-
-
-
-
-
-
-
- RegAS basic_binary_search(RegAS &target);
-
-
-
- RegXS binary_search(RegAS &target);
-
-
-
-
-
-
-
-
-
-
- void explicitonly(bool enable);
-
-
-
-
- OblivIndex<RegXS,1> oblivindex(const RegXS &idx, nbits_t depth=0) {
- if (depth == 0) {
- depth = this->addr_size;
- }
- typename Duoram<T>::template OblivIndex<RegXS,1>
- res(this->tio, this->yield, idx, depth);
- return res;
- }
-
- OblivIndex<RegAS,1> oblivindex(const RegAS &idx, nbits_t depth=0) {
- if (depth == 0) {
- depth = this->addr_size;
- }
- typename Duoram<T>::template OblivIndex<RegAS,1>
- res(this->tio, this->yield, idx, depth);
- return res;
- }
-
- OblivIndex<RegXS,1> oblivindex(nbits_t depth=0) {
- if (depth == 0) {
- depth = this->addr_size;
- }
- typename Duoram<T>::template OblivIndex<RegXS,1>
- res(this->tio, this->yield, depth);
- return res;
- }
-
-
-
- std::vector<T> reconstruct() const;
-
- T reconstruct(const T& share) const;
- };
- template <typename T>
- class Duoram<T>::Flat : public Duoram<T>::Shape {
-
- size_t start;
- size_t len;
- inline size_t indexmap(size_t idx) const {
- size_t paridx = idx + start;
- return paridx;
- }
-
- void butterfly(address_t start, address_t len, bool dir);
- public:
-
-
- Flat(Duoram &duoram, MPCTIO &tio, yield_t &yield, size_t start = 0,
- size_t len = 0);
-
-
- Flat(const Shape &parent, MPCTIO &tio, yield_t &yield, size_t start = 0,
- size_t len = 0);
-
- Flat(const Flat ©_from, MPCTIO &tio, yield_t &yield) :
- Shape(copy_from, tio, yield), start(copy_from.start),
- len(copy_from.len) {}
-
-
-
- Flat context(MPCTIO &new_tio, yield_t &new_yield) const {
- return Flat(*this, new_tio, new_yield);
- }
- Flat context(yield_t &new_yield) const {
- return Flat(*this, this->tio, new_yield);
- }
-
- typename Duoram::Shape::template MemRefS<RegAS,T,std::nullopt_t,Flat,1>
- operator[](const RegAS &idx) {
- typename Duoram<T>::Shape::
- template MemRefS<RegAS,T,std::nullopt_t,Flat,1>
- res(*this, idx, std::nullopt);
- return res;
- }
- typename Duoram::Shape::template MemRefS<RegXS,T,std::nullopt_t,Flat,1>
- operator[](const RegXS &idx) {
- typename Duoram<T>::Shape::
- template MemRefS<RegXS,T,std::nullopt_t,Flat,1>
- res(*this, idx, std::nullopt);
- return res;
- }
- template <typename U, nbits_t WIDTH>
- typename Duoram::Shape::template MemRefS<U,T,std::nullopt_t,Flat,WIDTH>
- operator[](OblivIndex<U,WIDTH> &obidx) {
- typename Duoram<T>::Shape::
- template MemRefS<RegXS,T,std::nullopt_t,Flat,WIDTH>
- res(*this, obidx, std::nullopt);
- return res;
- }
- typename Duoram::Shape::template MemRefExpl<T,std::nullopt_t>
- operator[](address_t idx) {
- typename Duoram<T>::Shape::
- template MemRefExpl<T,std::nullopt_t>
- res(*this, idx, std::nullopt);
- return res;
- }
- template <typename U>
- Duoram::Shape::MemRefInd<U, Flat>
- operator[](const std::vector<U> &indcs) {
- typename Duoram<T>::Shape::
- template MemRefInd<U,Flat>
- res(*this, indcs);
- return res;
- }
- template <typename U, size_t N>
- Duoram::Shape::MemRefInd<U, Flat>
- operator[](const std::array<U,N> &indcs) {
- typename Duoram<T>::Shape::
- template MemRefInd<U,Flat>
- res(*this, indcs);
- return res;
- }
-
-
-
-
-
-
-
- template<typename U,typename V>
- void osort(const U &idx1, const V &idx2, bool dir=0);
-
-
-
-
- void bitonic_sort(address_t start, address_t len, bool dir=0);
- };
- template <typename T>
- template <typename U, nbits_t WIDTH>
- class Duoram<T>::OblivIndex {
- template <typename Ux,typename FT,typename FST,typename Sh,nbits_t WIDTHx>
- friend class Shape::MemRefS;
- int player;
- std::optional<RDPFTriple<WIDTH>> dt;
- std::optional<RDPFPair<WIDTH>> dp;
- nbits_t curdepth, maxdepth;
- nbits_t next_windex;
- bool incremental;
- U idx;
- public:
-
- OblivIndex(MPCTIO &tio, yield_t &yield, const U &idx, nbits_t depth) :
- player(tio.player()), curdepth(depth), maxdepth(depth),
- next_windex(0), incremental(false), idx(idx)
- {
- if (player < 2) {
- dt = tio.rdpftriple<WIDTH>(yield, depth);
- } else {
- dp = tio.rdpfpair<WIDTH>(yield, depth);
- }
- }
-
- OblivIndex(MPCTIO &tio, yield_t &yield, nbits_t depth) :
- player(tio.player()), curdepth(0), maxdepth(depth),
- next_windex(0), incremental(true), idx(RegXS())
- {
- if (player < 2) {
- dt = tio.rdpftriple<WIDTH>(yield, depth, true);
- } else {
- dp = tio.rdpfpair<WIDTH>(yield, depth, true);
- }
- }
-
-
-
-
- std::vector<RegBS> unit_vector(MPCTIO &tio, yield_t &yield, size_t nitems, RegXS foundidx)
- {
- std::vector<RegBS> standard_basis(nitems);
- if (player < 2) {
- U indoffset;
- dt->get_target(indoffset);
- indoffset -= foundidx;
- U peerindoffset;
- tio.queue_peer(&indoffset, BITBYTES(curdepth));
- yield();
- tio.recv_peer(&peerindoffset, BITBYTES(curdepth));
- auto indshift = combine(indoffset, peerindoffset, curdepth);
-
- auto se = StreamEval(dt->dpf[1], 0, indshift, tio.aes_ops(), true);
- for (size_t j = 0; j < nitems; ++j) {
- typename RDPF<WIDTH>::LeafNode leaf = se.next();
- standard_basis[j] = dt->dpf[1].unit_bs(leaf);
- }
- } else {
- yield();
- }
- return standard_basis;
- }
-
- void incr(RegBS bit)
- {
- assert(incremental);
- idx.xshare = (idx.xshare << 1) | value_t(bit.bshare);
- ++curdepth;
- if (player < 2) {
- dt->depth(curdepth);
- } else {
- dp->depth(curdepth);
- }
- }
-
- U index() { return idx; }
- nbits_t depth() {return curdepth;}
-
- nbits_t windex() { assert(next_windex < WIDTH); return next_windex++; }
- };
- template <typename T>
- template <typename U, typename FT, typename FST, typename Sh, nbits_t WIDTH>
- class Duoram<T>::Shape::MemRefS {
- Sh &shape;
-
-
-
-
-
-
-
- std::optional<Duoram<T>::OblivIndex<U,WIDTH>> our_oblividx;
- Duoram<T>::OblivIndex<U,WIDTH> *oblividx;
- FST fieldsel;
- private:
-
-
- MemRefS<U,FT,FST,Sh,WIDTH> &oram_update(const FT& M, const prac_template_true&);
-
-
- MemRefS<U,FT,FST,Sh,WIDTH> &oram_update(const FT& M, const prac_template_false&);
- public:
- MemRefS<U,FT,FST,Sh,WIDTH>(Sh &shape, const U &idx, FST fieldsel) :
- shape(shape), fieldsel(fieldsel) {
- our_oblividx.emplace(shape.tio, shape.yield, idx,
- shape.addr_size);
- oblividx = &(*our_oblividx);
- }
- MemRefS<U,FT,FST,Sh,WIDTH>(Sh &shape, OblivIndex<U,WIDTH> &obidx, FST fieldsel) :
- shape(shape), fieldsel(fieldsel) {
- oblividx = &obidx;
- }
-
- template <typename SFT>
- MemRefS<U,SFT,SFT T::*,Sh,WIDTH> field(SFT T::*subfieldsel) {
- auto res = MemRefS<U,SFT,SFT T::*,Sh,WIDTH>(this->shape,
- *oblividx, subfieldsel);
- return res;
- }
-
- operator FT();
-
- MemRefS<U,FT,FST,Sh,WIDTH> &operator+=(const FT& M);
-
- MemRefS<U,FT,FST,Sh,WIDTH> &operator=(const FT& M);
- };
- template <typename T> template <typename FT, typename FST>
- class Duoram<T>::Shape::MemRefExpl {
- Shape &shape;
- address_t idx;
- FST fieldsel;
- public:
- MemRefExpl(Shape &shape, address_t idx, FST fieldsel) :
- shape(shape), idx(idx), fieldsel(fieldsel) {}
-
- template <typename SFT>
- MemRefExpl<SFT,SFT T::*> field(SFT T::*subfieldsel) {
- auto res = MemRefExpl<SFT,SFT T::*>(this->shape, idx, subfieldsel);
- return res;
- }
-
- operator FT();
-
- MemRefExpl &operator+=(const FT& M);
-
- MemRefExpl &operator=(const FT& M);
-
- MemRefExpl &operator-=(const FT& M) { *this += (-M); return *this; }
- };
- template <typename T> template <typename U, typename Sh>
- class Duoram<T>::Shape::MemRefInd {
- Sh &shape;
- std::vector<U> indcs;
- public:
- MemRefInd(Sh &shape, std::vector<U> indcs) :
- shape(shape), indcs(indcs) {}
- template <size_t N>
- MemRefInd(Sh &shape, std::array<U,N> aindcs) :
- shape(shape) { for ( auto &i : aindcs ) { indcs.push_back(i); } }
-
- operator std::vector<T>();
-
- MemRefInd &operator+=(const std::vector<T>& M);
- template <size_t N>
- MemRefInd &operator+=(const std::array<T,N>& M);
-
- MemRefInd &operator=(const std::vector<T>& M);
- template <size_t N>
- MemRefInd &operator=(const std::array<T,N>& M);
-
- MemRefInd &operator-=(const std::vector<T>& M) { *this += (-M); return *this; }
- template <size_t N>
- MemRefInd &operator-=(const std::array<T,N>& M) { *this += (-M); return *this; }
- };
- #include "duoram.tcc"
- #endif
|