152 lines
7.2 KiB
Markdown
152 lines
7.2 KiB
Markdown
|
# Arithmetic share runtime {#arith_runtime}
|
|||
|
|
|
|||
|
|
\htmlonly
|
|||
|
|
<div class="eli5"><b>ELI5.</b> Beside FSS keys you get ordinary secret shares: add them locally, multiply with Beaver or RSS, flip between bits and numbers with edaBits, and truncate fixed-point products. The composer schedules those opens next to FSS walks.</div>
|
|||
|
|
\endhtmlonly
|
|||
|
|
|
|||
|
|
Semi-honest 2PC and honest-majority 3PC. Openings may carry Shark/SPDZ IT-MACs
|
|||
|
|
from the beaver session. A leaf that must enter a boolean netlist uses
|
|||
|
|
[b2y / a2y](@ref yao_leaf) and comes back with `y2b` / `y2a`. There is no
|
|||
|
|
Yao domain on the composer.
|
|||
|
|
|
|||
|
|
## Domains
|
|||
|
|
|
|||
|
|
| Domain | Meaning |
|
|||
|
|
| --- | --- |
|
|||
|
|
| `a` / `b` / `fss` | Existing additive, subtractive, FSS leaf |
|
|||
|
|
| `rss` / `y` | Existing replicated / product factor |
|
|||
|
|
| `bin` | (2,2) XOR bit shares (packed) |
|
|||
|
|
| `bin_rss` | (2,3) replicated bits |
|
|||
|
|
|
|||
|
|
`composer::as` never casts to or from `bin` / `bin_rss`. Use `bin_a2b` /
|
|||
|
|
`bin_b2a` / `bin_inject` (see [compose.hpp](@ref dpf/compose.hpp) opcodes
|
|||
|
|
400–405).
|
|||
|
|
|
|||
|
|
## Building blocks
|
|||
|
|
|
|||
|
|
| Header | Role |
|
|||
|
|
| --- | --- |
|
|||
|
|
| [rss_seed.hpp](@ref dpf/rss_seed.hpp) | Pairwise PRG seeds, zero-sharing, RSS mul local |
|
|||
|
|
| [ot_pack.hpp](@ref dpf/ot_pack.hpp) | Consumable B2A / bit pads or dealer dabits |
|
|||
|
|
| [edabit.hpp](@ref dpf/edabit.hpp) | daBits and edaBits; A2B |
|
|||
|
|
| [bit_inject.hpp](@ref dpf/bit_inject.hpp) | Bit × arithmetic (2PC / RSS) |
|
|||
|
|
| [trunc.hpp](@ref dpf/trunc.hpp) | Probabilistic and exact truncate; mul_trunc |
|
|||
|
|
| [share_cmp.hpp](@ref dpf/share_cmp.hpp) | Share–share compare, ReLU, max, range, div |
|
|||
|
|
| [share_vec.hpp](@ref dpf/share_vec.hpp) | Lane-block share vectors |
|
|||
|
|
| [fixed_share.hpp](@ref dpf/fixed_share.hpp) | `fixed<Int,Frac>` |
|
|||
|
|
| [share_expr.hpp](@ref dpf/share_expr.hpp) | Imperative recorder |
|
|||
|
|
| [gilboa.hpp](@ref dpf/gilboa.hpp) | One-off product / tape fill |
|
|||
|
|
| [matmul.hpp](@ref dpf/matmul.hpp) | Matrix triples and matmul |
|
|||
|
|
| [shuffle.hpp](@ref dpf/shuffle.hpp) | Hidden reorder of an RSS column. A secret index stays a DPF |
|
|||
|
|
| [arith_garble.hpp](@ref dpf/arith_garble.hpp) | Free add and a unary projection, after a word has left the key |
|
|||
|
|
| [flute.hpp](@ref dpf/flute.hpp) | Public table on short masked bits. A DPF point stays a key |
|
|||
|
|
| [cost_pass.hpp](@ref dpf/cost_pass.hpp) | DCF vs edaBit vs A2B strategy |
|
|||
|
|
| [yao.hpp](@ref dpf/yao.hpp) | Half-gates netlist on a leaf's XOR bits. Party 0 garbles |
|
|||
|
|
| [yao_share.hpp](@ref dpf/yao_share.hpp) | Leaf share to those bits and back (`b2y`, `a2y`, `fss2y`, `rss2y`) |
|
|||
|
|
| [yao_aes.hpp](@ref dpf/yao_aes.hpp) | The PRG's zero-key MMO block, and AES-128 under a shared key |
|
|||
|
|
|
|||
|
|
## When to use which comparison
|
|||
|
|
|
|||
|
|
- **One input public or keyed:** DCF / `geneval_*` / interval keys.
|
|||
|
|
- **Both inputs arithmetic shares:** `share_cmp` (mask, open, MSB / DCF at the public difference).
|
|||
|
|
- **The leaf must enter a deep bit circuit:** [Yao](@ref yao_leaf). Not a comparison, a mux, or a public-offset LUT.
|
|||
|
|
|
|||
|
|
## A small word after the key {#arith_garble_word}
|
|||
|
|
|
|||
|
|
Comparisons, intervals, and public-offset polynomials stay on the key.
|
|||
|
|
[Grotto](@ref jet_and_ring) covers a public offset. This section is the
|
|||
|
|
word you already hold as shares, when the next step is addition, a public
|
|||
|
|
scale, or a unary map, and you do not want an opening between the gates.
|
|||
|
|
|
|||
|
|
[arith_garble.hpp](@ref dpf/arith_garble.hpp) is that circuit
|
|||
|
|
([Ball, Malkin, and Rosulek, CCS 2016](@ref bib_garble_gadgets)). Addition
|
|||
|
|
is free. Scaling by a public constant coprime to the modulus is free. A
|
|||
|
|
unary map of a mod-`m` wire sends `m − 1` ciphertexts. A threshold of `b`
|
|||
|
|
bits that already live in `Z_{b+1}` is one such map, so the row count is
|
|||
|
|
`b`. A product in a small prime field is the discrete-log reduction: project
|
|||
|
|
to the exponent, add, project back, and drop the zero cases.
|
|||
|
|
|
|||
|
|
The beaver [session](@ref beaver_triples) is the other tool. It opens one
|
|||
|
|
masked wire and multiplies interactively. It does not garble these gadgets.
|
|||
|
|
|
|||
|
|
```cpp
|
|||
|
|
dpf::arith_garble::circuit c;
|
|||
|
|
auto x = c.input(7);
|
|||
|
|
auto y = c.input(7);
|
|||
|
|
c.out(c.mul(c.add(x, y), x));
|
|||
|
|
auto opened = dpf::arith_garble::eval_pair(c, in);
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
`opened.mask` is the garbler's share and `opened.color` is the evaluator's.
|
|||
|
|
`open_shares` subtracts them mod the output modulus.
|
|||
|
|
|
|||
|
|
## A public table on short shares {#flute_lut}
|
|||
|
|
|
|||
|
|
A secret point in a public table is a DPF dotted with that table. FLUTE is
|
|||
|
|
the case where the index is already a handful of masked bits sitting in an
|
|||
|
|
ABY2.0 or three-party XOR sharing, and the result has to stay in that
|
|||
|
|
sharing.
|
|||
|
|
|
|||
|
|
[flute.hpp](@ref dpf/flute.hpp) follows Brüggemann, Hundt, Schneider, Suresh,
|
|||
|
|
and Yalame, [IEEE S&P 2023](@ref bib_flute). The table is an inner product of
|
|||
|
|
those bits. The online exchange is two bits per output bit for two parties,
|
|||
|
|
and three bits per output bit for `eval_trio`, independent of how wide the
|
|||
|
|
index is. The index is at most 8 bits. Bit 0 of the index is the least
|
|||
|
|
significant bit of the row.
|
|||
|
|
|
|||
|
|
```cpp
|
|||
|
|
auto pair = dpf::flute::eval_pair(delta, n_out, columns, bits);
|
|||
|
|
auto trio = dpf::flute::eval_trio(delta, n_out, columns, bits);
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
`columns[w * 2^δ + row]` is output bit `w` on that row. `opened` is the
|
|||
|
|
clear bit. `masked` XOR the party's mask shares is the same bit.
|
|||
|
|
|
|||
|
|
## An array of shares, not a secret index {#share_shuffle}
|
|||
|
|
|
|||
|
|
A secret index is a DPF. One read of a shared memory is a unit key, a public
|
|||
|
|
rotate, and a dot product, as in [3-party Duoram](@ref app_duoram). The
|
|||
|
|
shuffle is the other job: the parties already hold a share of every row, and
|
|||
|
|
the next step opens values. The opened order must not be the stored order.
|
|||
|
|
|
|||
|
|
`shuffle_party` derives one permutation from `k01` and applies it to every
|
|||
|
|
component. A caller who passes the whole seed bundle can recompute that
|
|||
|
|
order. Use it when the order is allowed to be known.
|
|||
|
|
|
|||
|
|
`shuffle_hidden_pass` is the order no single party should learn. Three
|
|||
|
|
passes use the pairwise seeds `k01`, `k12`, and `k20`, leaving out the party
|
|||
|
|
who does not hold that seed (party 2, then 0, then 1). Each party is given
|
|||
|
|
`rss::party_seeds` only. On a pass, the two parties who share the seed
|
|||
|
|
permute a two-party split of the column. The left-out party sends nothing
|
|||
|
|
and receives one fresh component. Both messages go to the sender's RSS
|
|||
|
|
neighbor. `permute` means `out[i] = in[pi[i]]`. Replaying the clear column
|
|||
|
|
is `π01`, then `π12`, then `π20`.
|
|||
|
|
|
|||
|
|
```cpp
|
|||
|
|
auto opened = dpf::shuffle::shuffle_hidden_triple(column, bundle, /*index=*/0);
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
`composer::shuffle_hidden(n, value_bytes)` records those three exchanges as
|
|||
|
|
`shuffle_send`. `aux` on each node is the left-out party.
|
|||
|
|
|
|||
|
|
This is for a column you already share: a Duoram memory before a bulk open,
|
|||
|
|
a histogram, a PSI payload. It does not replace a key. One hidden cell is
|
|||
|
|
still a DPF. A comparison or a sort by a secret key is a DCF or
|
|||
|
|
`share_cmp`. A gather to data-dependent indices is a DPF per access. The
|
|||
|
|
seed permutation is chosen before the data.
|
|||
|
|
|
|||
|
|
## Truncation
|
|||
|
|
|
|||
|
|
- `trunc_prob` — local right shift, error in `{0,1}`, no round.
|
|||
|
|
- `trunc_exact` — edaBit / carry correction.
|
|||
|
|
- `mul_trunc` — product then shift (fixed-point multiply).
|
|||
|
|
|
|||
|
|
## Networking
|
|||
|
|
|
|||
|
|
`schedule_round` carries `phase::{setup,online}`, `round_dir::{duplex,send_next,recv_prev}`,
|
|||
|
|
and `receive_rule::ring_next`. `drive_options` adds `pipeline_credit`, `cleartext`,
|
|||
|
|
and `check_open`. Pairwise seeds replace `dealer_zero` via `rss_zero_mask`.
|
|||
|
|
|
|||
|
|
**Go deeper:** [Beaver](@ref beaver_triples), [compose](@ref protocol_compose),
|
|||
|
|
[Grotto carry](@ref jet_and_ring).
|