libdpf/doc/pages/arith.md

# 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).