libdpf/doc/pages/repr_and_twist.md

# Representation shift and twisted jets {#repr_and_twist}

One opened offset `eta = x - r` also drives linear-recurrence checkpoints and
twisted monomials. Representation shift advances a dealer-keyed state vector
by a public matrix power. Twisted jets key \f$c^{m}\lambda^{c}\f$ and correct
with a public Pascal shift plus \f$\lambda^{\kappa}\f$.

## Representation shift {#offset_repr}

\htmlonly
<div class="eli5"><b>ELI5.</b> Offset Horner is the Pascal-matrix case of a shift-invariant recurrence. Representation shift is the same idea for a general linear recurrence: a public step count kappa advances the shared state without rebuilding the key.</div>
\endhtmlonly

Offset Horner is the unipotent (Pascal) case of a shift-invariant module.
Here the dealer keys an arbitrary state
\f$S_c\in(\mathbb{Z}/2^{64})^d\f$ at the hidden center. After `eta` opens, each
refined piece has a public carry `kappa`, and the parties apply

\f[
S_{c+\kappa}=M^{\kappa}S_c.
\f]

Negative `kappa` uses \f$M^{-1}\f$ (the determinant must be odd, hence a unit
in \f$\mathbb{Z}/2^{64}\f$). The wrap branch is multiplication by the public
constant \f$M^{\mp 2^n}\f$; when \f$M^{2^n}=I\f$ it is free.

Built-in examples:

- **Fibonacci.** Companion matrix of \f$T^2-T-1\f$ with
  \f$S_n=(F_{n+1},F_n)\f$. The Lucas addition formula is exactly
  \f$S_{c+\kappa}=M^{\kappa}S_c\f$. Helpers:
  `offset_repr_fibonacci_matrix`, `offset_repr_fibonacci_state`.
- **Geometric.** The \f$1\times 1\f$ matrix \f$[\lambda]\f$ advances
  \f$\lambda^{c}\f$ by the public factor \f$\lambda^{\kappa}\f$.
- **CRC / LFSR.** Over \f$\mathrm{GF}(2)\f$ the same checkpoint uses XOR
  shares. `offset_repr_crc32_jump` is the cleartext public twin
  (ISO / Ethernet polynomial); keyed CRC is deferred to XOR payload shares.

A state of `s` lanes (`s ≤ offset_repr_max_dim`, which is 8) is one
incremental comparison. The seed spine is `Θ(n λ)` bits with `λ` the
seed width, and the value words grow with the `s` lanes.
`offset_repr_eval` is one
sequence-shaped walk on the knots. `offset_repr_matrix_pow` then
squares the `s × s` matrix once per bit of `|kappa|` (`Θ(s³)` per
squaring, at most 63 squarings) and applies it on every refined piece,
`Θ(P · bitlength(kappa) · s³)` field operations. Negative exponents need
`M^{-1}`, so the determinant has to be odd.

`make_offset_repr_keys(center, state)` keys one incremental `gt` of the state vector.
`offset_repr_eval` returns one party's share of the advanced state.
`offset_repr_matrix_pow` is the public \f$M^{e}\f$ used after `eta` opens.

**Code samples**\n
<div class="tabbed">

  - <b class="tab-title">repr_and_twist.cpp</b>  \include{cpp} grotto/repr_and_twist.cpp

</div>

## Twisted jets {#offset_twist}

\htmlonly
<div class="eli5"><b>ELI5.</b> The dealer keys one comparison whose payload is the vector of twisted powers c^m λ^c, including the dyadic case c = 1/2. After eta opens, the parties scale that vector. They do not re-expand the tree.</div>
\endhtmlonly

The dealer keys one comparison whose payload is the vector of twisted powers
\f$c^{m}\lambda^{c}\f$ in \f$\mathbb{Z}/2^{64}\f$. After `eta` opens, the segment
walk returns those shares on the hot piece. A public binomial shift of the
coefficient vector by `kappa`, followed by a public factor \f$\lambda^{\kappa}\f$,
yields

\f[
\sum_{m}a_m(c+\kappa)^{m}\lambda^{c+\kappa}
  =\lambda^{\kappa}\sum_{m}q_m\,c^{m}\lambda^{c},
\f]

where \f$q=\mathrm{Pascal}(\kappa)\,a\f$. Odd \f$\lambda\f$ are units, so negative
`kappa` is \f$(\lambda^{-1})^{|\kappa|}\f$.

Dyadic decay \f$\lambda=1/2\f$ is the tag `twist_half`. A right shift does
not distribute over additive shares, so keygen plants \f$c^{m}\f$ and
`offset_twist_eval` returns shares of the untwisted
\f$\sum a_m(c+\kappa)^{m}\f$. After opening, a public right shift by the
wrapped point yields \f$\sum a_m x^{m}/2^{x}\f$. `offset_twist_clear` with
`twist_half` evaluates that dyadic target in the clear.

The closed form

\f[
\sum_{k=1}^{n}k\lambda^{k}
  =\lambda\frac{1-(n+1)\lambda^{n}+n\lambda^{n+1}}{(1-\lambda)^{2}}
\f]

(for odd \f$\lambda\neq 1\f$) is `offset_twist_arithmetico_geometric`. It is a
readout of the same twisted table (degree-1 coefficients against
\f$\lambda^{k}\f$ powers).

`make_offset_twist_keys(center, degree, lambda)` and the `twist_half`
overload key the table. `lambda` must be odd. `offset_twist_eval<Party>`
returns one party's share of the twisted polynomial at the wrapped point.
`offset_twist_clear` is the same value in the clear.

Degree `d` is at most 16: one comparison key. The seed spine is
`Θ(n λ)` bits with `λ` the seed width, and the value words grow with
`d`. Then one sequence-shaped walk on the knots and
an `O(d^2)` Pascal shift. `twist_half` skips the public multiply by
the odd base and leaves a shift for after the shares are opened.
`offset_twist_arithmetico_geometric` is a constant amount of arithmetic
on its two public arguments.

\code{cpp}
const std::uint8_t center = 10;
const std::uint8_t eta = 5;
auto twist_keys = grotto::make_offset_twist_keys<std::uint8_t>(
    center, 2, std::uint64_t{3});
std::vector<std::uint8_t> knots{0};
std::vector<std::uint64_t> coeff{2, 5, 1};
auto s0 = grotto::offset_twist_eval<0>(twist_keys, knots, coeff, eta);
auto half_keys = grotto::make_offset_twist_keys<std::uint8_t>(
    center, 2, grotto::twist_half);
\endcode

Offset Horner, offset polynomials, a union of several LUTs on one
comparison, carry, prefix parity, and the cleartext
LUTs are on [jet and ring](@ref jet_and_ring).

\htmlonly
<div class="tldr"><b>TL;DR.</b> Both start from the opened offset eta = x − r. Representation shift advances a linear recurrence by a public step count. Twisted jets scale a vector of powers that already includes the constant factor.</div>
\endhtmlonly