Operators

The operators/ directory implements MPC-enabled data-parallel operators used by ORQ queries.

Contents:

• aggregation_selector.h - Internal helper class to select between aggregation types at runtime

• aggregation.h – Secure aggregation functions (SUM, COUNT, etc.) and oblivious aggregation network

• circuits.h - Implementation of various boolean circuits.

• common.h – Common utilities shared by operators.

• distinct.h – Distinct operator.

• join.h - Join operator.

• merge.h – Oblivious Merge.

• quicksort.h – Quicksort implementation.

• radixsort.h – Radixsort implementation.

• shuffle.h – Oblivious shuffle operators.

• sorting.h – Sorting helper functions.

• streaming.h – Streaming operators.

Note: For documentation on the join functions, see orq::relational::EncodedTable::_join().

Boolean Circuits

Implementation of various boolean circuits.

(moved out of BSharedVector.h)

template<>
struct DoubleWidth<int8_t>

#include <circuits.h>

Public Types

using type = int32_t

template<>
struct DoubleWidth<int16_t>

#include <circuits.h>

Public Types

using type = int32_t

template<>
struct DoubleWidth<int32_t>

#include <circuits.h>

Public Types

using type = int64_t

template<>
struct DoubleWidth<int64_t>

#include <circuits.h>

Public Types

using type = __int128_t

namespace orq

namespace operators

Typedefs

template<typename S, typename E>
using unique_B = std::unique_ptr<BSharedVector<S, E>>

Alias for a unique pointer to a BSharedVector.

Template Parameters:

• S –

• E –

Functions

template<typename Share, typename EVector>
static unique_B<Share, EVector> ripple_carry_adder(const BSharedVector<Share, EVector> &a, const BSharedVector<Share, EVector> &b, const bool carry_in)

Computes vectorized boolean addition using a ripple carry adder. We use a slightly non-traditional circuit to achieve exactly \(\ell - 1\) rounds of computation (where \(\ell\) is the bitwidth of the shares), and bit packing, which achieves asymptotically optimal bandwidth as the input vectors grow. Thus, in many cases, RCA is actually superior to PPA, since we are usually not round-constrained.

Parameters:

• a –

• b –

• carry_in – the carry-in bit. used for subtraction. default false.

Returns:

A unique pointer to a new shared vector that contains boolean shares of the elementwise additions

template<typename S, typename E>
static unique_B<S, E> rca_compare(const BSharedVector<S, E> &a, const BSharedVector<S, E> &b)

Implements a comparison circuit using ripple_carry_adder; i.e., via boolean subtraction. a < b implies a - b < 0, and we can check ltz() for free with boolean shares. So, subtract the two inputs and return (a secret sharing of) the sign bit.

This runs a slightly optimized version of RCA, since we only need to compute carries (no sum bits). In most cases it is a bit faster, but is not round optimal.

Parameters:

• a –

• b –

Returns:

unique pointer to a BSharedVector

template<typename S, typename E>
std::pair<BSharedVector<S, E>, BSharedVector<S, E>> prefix_sum(const std::pair<BSharedVector<S, E>, BSharedVector<S, E>> &x, const std::pair<BSharedVector<S, E>, BSharedVector<S, E>> &y)

Computes a prefix graph component for the parallel prefix adder.

Template Parameters:

• Share – Share data type

• EVector – Share container type

Parameters:

• x – A pair containing the non-shifted generate and propagate vectors of x

• y – A pair containing the shifted generate and propagate vectors of y

Returns:

A new pair containing the output generate and propagate vectors, respectively.

template<typename S, typename E>
unique_B<S, E> parallel_prefix_adder(const BSharedVector<S, E> &current, const BSharedVector<S, E> &other, const bool carry_in)

Computes vectorized boolean addition using a parallel prefix adder (specifically, a Kogge-Stone circuit).

A prior version used the Sklansky circuit, which has half the bandwidth, but the bandwidth savings don’t matter here: we always compute over the full-width types. Additionally, the greater fan-out of Sklansky had higher local compute overheads due to data movement.

Parameters:

• current – the first BSharedVector

• other – the second BSharedVector

• carry_in – the carry bit (default false)

Returns:

A unique pointer to a new shared vector that contains boolean shares of the elementwise additions

Shuffle

Defines

random_buffer_size

namespace orq

namespace operators

Typedefs

template<typename E>
using AElementwisePermutation = ASharedVector<int, orq::EVector<int, E::replicationNumber>>

template<typename E>
using BElementwisePermutation = BSharedVector<int, orq::EVector<int, E::replicationNumber>>

Functions

template<typename Share, typename EVector>
void oblivious_apply_sharded_perm(SharedVector<Share, EVector> &x, std::shared_ptr<ShardedPermutation> &perm)

Protocol agnostic function to apply sharded permutations.

Template Parameters:

• Share – Share data type.

• EVector – Share container type.

Parameters:

• x – The secret-shared vector to permute.

• perm – The permutation to apply.

template<typename Share, typename EVector>
void oblivious_apply_inverse_sharded_perm(SharedVector<Share, EVector> &x, std::shared_ptr<ShardedPermutation> &perm)

Protocol agnostic function to apply sharded permutations.

Template Parameters:

• Share – Share data type.

• EVector – Share container type.

Parameters:

• x – The secret-shared vector to permute.

• perm – The permutation whose inverse to apply.

template<typename Share, typename EVector, typename EVectorPerm>
void oblivious_apply_elementwise_perm(SharedVector<Share, EVector> &x, ElementwisePermutation<EVectorPerm> &perm)

Obliviously apply an elementwise secret-shared permutation.

Template Parameters:

• Share – Share data type.

• EVector – Share container type.

• EVectorPerm – Permutation type.

Parameters:

• x – The secret-shared vector to permute.

• perm – The permutation to apply.

std::vector<int> gen_perm(size_t size, std::shared_ptr<random::CommonPRG> generator)

Generate a pseudorandom local permutation using Fisher-Yates shuffle.

Creates a vector {0, 1, …, size-1}, permutes it, and returns it.

Parameters:

• size – The size of the permutation.

• generator – The common PRG object used as the pseudorandomness source.

Returns:

The permutation as a vector of destination indices.

template<typename T>
void local_apply_perm(Vector<T> &x, const LocalPermutation &permutation)

Apply a local permutation to a vector.

Template Parameters:

T – Data type of vector elements.

Parameters:

• x – The vector to permute (modified in place).

• permutation – The permutation to apply.

template<typename T>
void local_apply_perm(Vector<T> &x, Vector<int> &permutation)

Overload for both vector and permutation represented as ORQ Vector.

Template Parameters:

T – Data type of vector elements.

Parameters:

• x – The vector to permute (modified in place).

• permutation – The permutation to apply as ORQ Vector.

template<typename T>
void local_apply_perm_single_threaded(Vector<T> &x, const LocalPermutation &permutation)

Single-threaded version of local_apply_perm.

Avoids reentering the runtime within a thread.

Template Parameters:

T – Data type of vector elements.

Parameters:

• x – The vector to permute (modified in place).

• permutation – The permutation to apply.

template<typename T>
void local_apply_perm_single_threaded(Vector<T> &x, Vector<int> &permutation)

Single-threaded overload for both vector and permutation represented as ORQ Vector.

Template Parameters:

T – Data type of vector elements.

Parameters:

• x – The vector to permute (modified in place).

• permutation – The permutation to apply.

template<typename T, int R, typename P>
void local_apply_perm(EVector<T, R> &x, P &permutation)

Catch-all overload for arbitrary vector types and permutation as ORQ Vector

Template Parameters:

• T – Data type of vector elements.

• R – Replication number.

• P – Permutation type.

Parameters:

• x – The vector to permute (modified in place).

• permutation – The permutation to apply.

template<typename EVector>
void local_apply_perm(ElementwisePermutation<EVector> &x, Vector<int> &permutation)

Overload when vector is an ElementwisePermutation.

Template Parameters:

EVector – Share container type.

Parameters:

• x – The vector to permute (modified in place).

• permutation – The permutation to apply.

template<typename S, typename E, typename P>
void local_apply_perm(SharedVector<S, E> &x, P &permutation)

Overload for permutation a SharedVector. Permutation type P can be a LocalPermutation or Vector<int>.

Template Parameters:

• S – Share data type.

• E – Share container type.

• P – Permutation type.

Parameters:

• x – The vector to permute (modified in place).

• permutation – The permutation to apply.

template<typename T, typename S = int>
void local_apply_inverse_perm(Vector<T> &x, const std::vector<S> &permutation)

Apply the inverse of a local permutation to a vector.

NOTE: this can also be implemented by just applying permutation as a new mapping. However, this is currently less efficient.

Template Parameters:

• T – Data type of vector elements.

• S – Permutation data type.

Parameters:

• x – The vector to permute.

• permutation – The permutation whose inverse to apply.

template<typename T, typename S = int>
void local_apply_inverse_perm(Vector<T> &x, const Vector<S> &permutation)

Overload when both are ORQ Vectors.

Template Parameters:

• T – Data type of vector elements.

• S – Permutation data type.

Parameters:

• x – The vector to permute.

• permutation – The permutation whose inverse to apply.

template<typename T, int R, typename S = int>
void local_apply_inverse_perm(EVector<T, R> &x, const std::vector<S> &permutation)

Overload when we are permutation an EVector.

Template Parameters:

• T – Data type of vector elements.

• R – Replication number.

• S – Permutation data type.

Parameters:

• x – The vector to permute.

• permutation – The permutation whose inverse to apply.

template<typename Share, typename EVector, typename S = int>
void local_apply_inverse_perm(SharedVector<Share, EVector> &x, const std::vector<S> &permutation)

Overload when vector is a SharedVector.

Template Parameters:

• Share – Share data type.

• EVector – Share container type.

• S – Permutation data type.

Parameters:

• x – The vector to permute.

• permutation – The permutation whose inverse to apply.

template<typename Share, typename EVector>
void local_apply_inverse_perm(SharedVector<Share, EVector> &x, Vector<int> &permutation)

Overload when vector is a SharedVector and permutation is a ORQ Vector

Template Parameters:

• Share – Share data type.

• EVector – Share container type.

Parameters:

• x – The vector to permute.

• permutation – The permutation whose inverse to apply.

template<typename EVector>
void local_apply_inverse_perm(ElementwisePermutation<EVector> &x, Vector<int> &permutation)

Overload when the vector is an ElementwisePermutation and permutation is a ORQ Vector

Template Parameters:

EVector – Share container type.

Parameters:

• x – The vector to permute.

• permutation – The permutation whose inverse to apply.

template<typename Share, typename EVector>
void hm_oblivious_apply_sharded_perm(SharedVector<Share, EVector> &x, std::shared_ptr<HMShardedPermutation> &permutation)

Obliviously apply a sharded secret-shared permutation (Honest Majority).

Template Parameters:

• Share – Share data type.

• EVector – Share container type.

Parameters:

• x – The secret-shared vector to permute.

• permutation – The permutation to apply.

template<typename EVector>
void hm_oblivious_apply_sharded_perm(ElementwisePermutation<EVector> &x, std::shared_ptr<HMShardedPermutation> &permutation)

Obliviously apply a sharded secret-shared permutation (Honest Majority).

This overloaded function just passes the ElementwisePermutation’s underlying SharedVector.

Parameters:

• x – The ElementwisePermutation to permute.

• permutation – The permutation to apply.

template<typename Share, typename EVector>
void hm_oblivious_apply_inverse_sharded_perm(SharedVector<Share, EVector> &x, std::shared_ptr<HMShardedPermutation> &permutation)

Obliviously apply the inverse of a sharded secret-shared permutation.

Template Parameters:

• Share – Share data type.

• EVector – Share container type.

Parameters:

• x – The secret-shared vector to permute.

• permutation – The permutation whose inverse to apply.

template<typename EVector>
void hm_oblivious_apply_inverse_sharded_perm(ElementwisePermutation<EVector> &x, std::shared_ptr<HMShardedPermutation> &permutation)

Obliviously apply the inverse of a sharded secret-shared permutation (Honest Majority).

Template Parameters:

EVector – Share container type.

Parameters:

• x – The ElementwisePermutation to permute.

• permutation – The permutation whose inverse to apply.

template<typename Share, typename EVector>
void permute_and_share(SharedVector<Share, EVector> &x, std::shared_ptr<DMShardedPermutation<Share>> &perm, int send_party)

Apply a permutation correlation to a secret-shared vector (2PC only).

Template Parameters:

• Share – Share data type.

• EVector – Share container type.

Parameters:

• x – The secret-shared vector to permute and share.

• perm – The permutation correlation.

• send_party – The index of the party acting as the sender.

template<typename Share, typename EVector>
void permute_and_share_inverse(SharedVector<Share, EVector> &x, std::shared_ptr<DMShardedPermutation<Share>> &perm, int send_party)

Apply the inverse of a permutation correlation to a secret-shared vector (2PC only).

Template Parameters:

• Share – Share data type.

• EVector – Share container type.

Parameters:

• x – The secret-shared vector to permute and share.

• perm – The permutation correlation whose inverse to apply.

• send_party – The index of the party acting as the sender.

template<typename Share, typename EVector>
void dm_oblivious_apply_sharded_perm(SharedVector<Share, EVector> &x, std::shared_ptr<DMShardedPermutation<Share>> &permutation)

Obliviously apply a sharded secret-shared permutation (Dishonest Majority).

Template Parameters:

• Share – Share data type.

• EVector – Share container type.

Parameters:

• x – The secret-shared vector to permute.

• permutation – The permutation to apply.

template<typename Share, typename EVector>
void dm_oblivious_apply_inverse_sharded_perm(SharedVector<Share, EVector> &x, std::shared_ptr<DMShardedPermutation<Share>> &permutation)

Obliviously apply the inverse of a sharded secret-shared permutation (Dishonest Majority).

Template Parameters:

• Share – Share data type.

• EVector – Share container type.

Parameters:

• x – The secret-shared vector to permute.

• permutation – The permutation whose inverse to apply.

template<typename EVector>
void oblivious_apply_sharded_perm(ElementwisePermutation<EVector> &x, std::shared_ptr<ShardedPermutation> &permutation)

Protocol agnostic function to apply sharded permutations.

This overloaded function just passes the ElementwisePermutation’s underlying SharedVector.

Template Parameters:

EVector – Share container type.

Parameters:

• x – The secret-shared vector to permute.

• permutation – The permutation to apply.

template<typename EVector>
void oblivious_apply_inverse_sharded_perm(ElementwisePermutation<EVector> &x, std::shared_ptr<ShardedPermutation> &permutation)

Protocol agnostic function to apply inversesharded permutations.

Template Parameters:

EVector – Share container type.

Parameters:

• x – The secret-shared vector to permute.

• permutation – The permutation whose inverse to apply.

template<typename EVector>
ElementwisePermutation<EVector> compose_permutations(ElementwisePermutation<EVector> &sigma, ElementwisePermutation<EVector> &rho)

Compose two elementwise secret-shared permutations.

Template Parameters:

EVector – Share container type.

Parameters:

• sigma – The first permutation to be applied in the composition.

• rho – The second permutation to be applied in the composition.

Returns:

An elementwise secret-sharing of the composed permutation.

template<typename Share, typename EVector>
static void shuffle(SharedVector<Share, EVector> &x)

Obliviously shuffle a secret-shared vector.

Template Parameters:

• Share – Share data type.

• EVector – Share container type.

Parameters:

x – The vector to shuffle.

template<typename Share, typename EVector>
static void shuffle(std::vector<ASharedVector<Share, EVector>*> _data_a, std::vector<BSharedVector<Share, EVector>*> _data_b, size_t size)

Obliviously shuffle a table of secret-shared vectors.

Template Parameters:

• Share – Share data type.

• EVector – Share container type.

Parameters:

• _data_a – List of pointers to all arithmetic columns.

• _data_b – List of pointers to all binary columns.

• size – Size of the vectors to shuffle.

Sorting

Defines

DEFAULT_SORT_PROTO

namespace orq

Enums

enum SortingProtocol

Available sorting protocols.

Values:

enumerator BITONICSORT

enumerator QUICKSORT

enumerator RADIXSORT

enumerator BITONICMERGE

enumerator DEFAULT

namespace operators

Typedefs

template<typename T>
using PadWidth = typename std::conditional<std::is_same<T, int64_t>::value, __int128_t, int64_t>::type

template<typename E>
using PaddedBSharedVector = BSharedVector<PadWidth<typename E::ShareT>, orq::EVector<PadWidth<typename E::ShareT>, E::replicationNumber>>

Enums

enum SortOrder

Sorting order enumeration.

Values:

enumerator ASC

enumerator DESC

Functions

template<typename Share, typename EVector> static DOXYGEN_IGNORE BSharedVector< Share, EVector > compare (BSharedVector< Share, EVector > &x_vec, BSharedVector< Share, EVector > &y_vec, const std::vector< SortOrder > &order)

Compares two vectors element-wise.

Template Parameters:

• Share – Share data type.

• EVector – Share container type.

Parameters:

• x_vec – Left vector.

• y_vec – Right vector.

• order – Comparison order.

Returns:

Comparison result bits.

template<typename Share, typename EVector>
static BSharedVector<Share, EVector> compare_rows(const std::vector<BSharedVector<Share, EVector>*> &x_vec, const std::vector<BSharedVector<Share, EVector>*> &y_vec, const std::vector<SortOrder> &order)

Compares two MxN arrays row-wise by applying M greater-than comparisons on N keys.

NOTE: The i-th row, let l, from the left array is greater than the i-th row, let r, from the right array if l’s first key is greater than r’s first key, or the first keys are the same and l’s second key is greater than r’s second key, or the first two keys are the same and so forth, for all keys.

Template Parameters:

• Share – Share data type.

• EVector – Share container type.

Parameters:

• x_vec – The left column-first array with M rows and N columns.

• y_vec – The right column-first array with M rows and N columns.

• order – A vector that denotes the order of comparison per key.

Returns:

A new shared vector that contains the result bits of the M greater-than comparisons.

template<typename Share, typename EVector>
static BSharedVector<Share, EVector> compare_rows(std::vector<BSharedVector<Share, EVector>> &x_vec, std::vector<BSharedVector<Share, EVector>> &y_vec, const std::vector<SortOrder> &order)

Same as above but accepts the N columns by reference.

Template Parameters:

• Share – Share data type.

• EVector – Share container type.

Parameters:

• x_vec – The left column-first array with M rows and N columns.

• y_vec – The right column-first array with M rows and N columns.

• order – A vector that denotes the order of comparison per key.

Returns:

A new shared vector that contains the result bits of the M greater-than comparisons.

template<typename Share, typename EVector>
static void swap(std::vector<BSharedVector<Share, EVector>*> &x_vec, std::vector<BSharedVector<Share, EVector>*> &y_vec, const BSharedVector<Share, EVector> &bits)

Swaps rows of two MxN arrays in place using the provided bits.

Template Parameters:

• Share – Share data type.

• EVector – Share container type.

Parameters:

• x_vec – The left column-first array with M rows and N columns.

• y_vec – The right column-first array with M rows and N columns.

• bits – The B-shared vector that contains ‘M’ bits to use for oblivious swapping (if bits[i]=True, the i-th rows will be swapped).

template<typename Share, typename EVector>
static void swap(std::vector<ASharedVector<Share, EVector>*> &x_vec, std::vector<ASharedVector<Share, EVector>*> &y_vec, const ASharedVector<Share, EVector> &bits)

Swaps rows of two arithmetic arrays using selection bits.

Template Parameters:

• Share – Share data type.

• EVector – Share container type.

Parameters:

• x_vec – Left array.

• y_vec – Right array.

• bits – Selection bits for swapping.

template<typename Share, typename EVector>
static void swap(std::vector<BSharedVector<Share, EVector>> &x_vec, std::vector<BSharedVector<Share, EVector>> &y_vec, const BSharedVector<Share, EVector> &bits)

Same as above but accepts the N columns by reference.

Template Parameters:

• Share – Share data type.

• EVector – Share container type.

Parameters:

• x_vec – The left column-first array with M rows and N columns.

• y_vec – The right column-first array with M rows and N columns.

• bits – The B-shared vector that contains ‘M’ bits to use for oblivious swapping (if bits[i]=True, the i-th rows will be swapped).

template<typename Share, typename EVector>
static void swap(std::vector<ASharedVector<Share, EVector>> &x_vec, std::vector<ASharedVector<Share, EVector>> &y_vec, const ASharedVector<Share, EVector> &bits)

Swaps arithmetic arrays using selection bits (reference overload).

Template Parameters:

• Share – Share data type.

• EVector – Share container type.

Parameters:

• x_vec – Left array.

• y_vec – Right array.

• bits – Selection bits for swapping.

template<typename Share, typename EVector>
void swap(BSharedVector<Share, EVector> &x_vec, BSharedVector<Share, EVector> &y_vec, BSharedVector<Share, EVector> &bits)

Same as above but accepts the N columns by reference.

Template Parameters:

• Share – Share data type.

• EVector – Share container type.

Parameters:

• x_vec – The left column-first array with M rows and N columns.

• y_vec – The right column-first array with M rows and N columns.

• bits – The B-shared vector that contains ‘M’ bits to use for oblivious swapping (if bits[i]=True, the i-th rows will be swapped).

template<typename Share, typename EVector>
static void bitonic_sort(std::vector<BSharedVector<Share, EVector>*> _columns, std::vector<ASharedVector<Share, EVector>*> _data_a, std::vector<BSharedVector<Share, EVector>*> _data_b, const std::vector<SortOrder> &order)

Sorts rows in the given array on all columns. Updates array in place.

Template Parameters:

• Share – Share data type.

• EVector – Share container type.

Parameters:

• _columns – The columns of the array.

• order – The sorting direction per column.

template<typename Share, typename EVector>
static void bitonic_sort(std::vector<BSharedVector<Share, EVector>> _columns, std::vector<ASharedVector<Share, EVector>> _data_a, std::vector<BSharedVector<Share, EVector>> _data_b, const std::vector<SortOrder> &order)

Same as above but accepts the columns by reference.

Template Parameters:

• Share – Share data type.

• EVector – Share container type.

Parameters:

• _columns – The columns of the array.

• order – The sorting direction per column.

template<typename Share, typename EVector>
static void bitonic_sort(BSharedVector<Share, EVector> &vec, SortOrder order = SortOrder::ASC)

Sorts rows in the given array on all columns. Updates array in place.

Template Parameters:

• Share – Share data type.

• EVector – Share container type.

Parameters:

• _columns – The columns of the array.

• order – The sorting direction per column (default ascending).

template<typename Share, typename EVector>
static PaddedBSharedVector<EVector> pad_input(BSharedVector<Share, EVector> &v, bool reverse_order)

Extend <=32 bit elements to 64 bit elements.

Shift original value into most significant 32 bits. Set least significant 32 bits equal to the initial index. If reverse_order is set, pad with the values -1 to -n, otherwise pad with 0 to n-1.

Template Parameters:

• Share – Share data type.

• EVector – Share container type.

Parameters:

• v – The input vector with <=32 bits.

• reverse_order – Indicates whether the upcoming sort is in reverse order.

Returns:

The 64 bit shared vector.

template<typename S, typename E>
static ElementwisePermutation<E> remove_padding(BSharedVector<S, E> &v, PaddedBSharedVector<E> &padded, bool reverse_order)

Remove the padding from the 64 bit result to obtain the original <=32 bit values.

Template Parameters:

• Share – Share data type.

• EVector – Share container type.

Parameters:

• v – The original input vector to place the result in.

• padded – The 64 bit shared vector.

• reverse_order – Indicates whether the upcoming sort is in reverse order.

Returns:

The extracted permutation.

template<typename Share, typename EVector>
static void table_sort(std::vector<BSharedVector<Share, EVector>*> _columns, std::vector<ASharedVector<Share, EVector>*> _data_a, std::vector<BSharedVector<Share, EVector>*> _data_b, const std::vector<SortOrder> &order, const std::vector<bool> &single_bit, const SortingProtocol protocol)

Sorts rows in the given array on all columns. Updates array in place.

Template Parameters:

• Share – Share data type.

• EVector – Share container type.

Parameters:

• _columns – The columns to sort by.

• _data_a – The AShared columns of the array to be sorted.

• _data_b – The BShared columns of the array to be sorted.

• single_bit – which columns are single-bit columns (thus use 1-bit radixsort)

• protocol – which sorting protocol to use

• order – The sorting direction per column.

namespace orq

namespace operators

Functions

template<typename T, typename E>
void partition(BSharedVector<T, E> &v, Vector<T> &comparisons, int start, int end, Vector<long> &pivots)

Partitions a vector segment based on comparison results.

Rearranges elements between start and end indices based on pivot comparisons. Elements equal to 0 in comparisons are moved to the left partition.

Template Parameters:

• T – Share data type.

• E – Share container type.

Parameters:

• v – Vector to partition (modified in place).

• comparisons – Comparison results for each element.

• start – Starting index (inclusive).

• end – Ending index (inclusive).

• pivots – Vector tracking pivot positions.

template<typename T, typename EVector>
static void quicksort_body(BSharedVector<T, EVector> &v)

Core quicksort algorithm implementation.

Performs the main quicksort logic on a padded vector.

Template Parameters:

• T – Share data type.

• EVector – Share container type.

Parameters:

v – Vector to sort (modified in place).

template<typename Share, typename EVector>
static ElementwisePermutation<EVector> quicksort(BSharedVector<Share, EVector> &v, SortOrder order)

Main quicksort entry point.

Sorts a vector using the quicksort algorithm with padding for stability. Handles both ascending and descending order sorting.

Template Parameters:

• Share – Share data type.

• EVector – Share container type.

Parameters:

• v – Vector to sort (modified in place).

• order – Sorting direction (ASC or DESC).

Returns:

Permutation representing the applied sort order.

namespace orq

namespace operators

Typedefs

template<typename E>
using ASharedPerm = ASharedVector<int, orq::EVector<int, E::replicationNumber>>

template<typename E>
using BSharedPerm = BSharedVector<int, orq::EVector<int, E::replicationNumber>>

Functions

template<typename S, typename E>
static ElementwisePermutation<E> radix_sort_ccs(BSharedVector<S, E> &v, const int bits, const bool full_width = true)

Direct implementation of the AHI+22 radix sort algorithm.

Template Parameters:

• S – Share data type.

• E – Share container type.

Parameters:

• v – Vector to sort.

• bits – Number of bits to sort on.

• full_width – Whether sorting on full bitwidth (affects sign bit handling).

Returns:

Permutation representing the sort order.

template<typename S, typename E>
static void radix_sort_body(BSharedVector<S, E> &v, const int bits, const bool full_width = true)

The radix sort protocol.

Implements the radix sort protocol for a given number of bits.

Template Parameters:

• S – Share data type.

• E – Share container type.

Parameters:

• v – Vector to sort.

• bits – Number of bits to sort on.

• full_width – Whether sorting on full bitwidth (affects sign bit handling).

template<typename S, typename E>
static ElementwisePermutation<E> radix_sort(BSharedVector<S, E> &v, SortOrder order, const size_t bits)

The radix sort protocol entry point.

Template Parameters:

• S – Share data type.

• E – Share container type.

Parameters:

• v – Vector to sort.

• order – Sort order (ascending or descending).

• bits – Number of bits to sort on.

Returns:

Permutation representing the applied sort order.

Merge

namespace orq

namespace operators

Functions

template<typename Share, typename EVector>
static void compare_swap(BSharedVector<Share, EVector> &x, BSharedVector<Share, EVector> &y)

Performs conditional swap on two boolean shared vectors.

Swaps elements between x and y based on comparison result (x >= y). After the swap, x contains the smaller values and y contains the larger values.

Template Parameters:

• Share – The underlying data type of the shared vectors.

• EVector – Share container type.

Parameters:

• x – First vector (modified in place).

• y – Second vector (modified in place).

template<typename Share, typename EVector>
static void odd_even_merge(BSharedVector<Share, EVector> &v)

Performs odd-even merge on a boolean shared vector.

Implements the odd-even merge algorithm. The vector size must be a power of two.

Template Parameters:

• Share – The underlying data type of the shared vectors.

• EVector – Share container type.

Parameters:

v – Vector to be merged (modified in place).

template<typename Share, typename EVector>
static void bitonic_merge(std::vector<BSharedVector<Share, EVector>*> _columns, std::vector<ASharedVector<Share, EVector>*> _data_a, std::vector<BSharedVector<Share, EVector>*> _data_b, const std::vector<SortOrder> &order)

Sorts vectors based on some keys.

Each key needs to have two already sorted halves in the same order.

Template Parameters:

• Share – The underlying data type of the shared vectors.

• EVector – Share container type.

Parameters:

• _columns – The keys to merge based on.

• _data_a – The AShared data vectors to merge.

• _data_b – The BShared data vectors to merge.

• order – The sorting direction per column.

template<typename Share, typename EVector>
static void bitonic_merge(std::vector<BSharedVector<Share, EVector>> _columns, std::vector<ASharedVector<Share, EVector>> _data_a, std::vector<BSharedVector<Share, EVector>> _data_b, const std::vector<SortOrder> &order)

Sorts vectors based on some keys.

Each key needs to have two already sorted halves in the same order.

Template Parameters:

• Share – The underlying data type of the shared vectors.

• EVector – Share container type.

Parameters:

• _columns – The keys to merge based on.

• _data_a – The AShared data vectors to merge.

• _data_b – The BShared data vectors to merge.

• order – The sorting direction per column (default ascending).

template<typename Share, typename EVector>
static void bitonic_merge(BSharedVector<Share, EVector> &vec, SortOrder order = SortOrder::ASC)

Sorts a vector that has two already sorted halves in the same order.

Template Parameters:

• Share – The underlying data type of the shared vectors.

• EVector – Share container type.

Parameters:

• vec – The vector to merge based on.

• order – The sorting direction (default ascending).

Relational

namespace orq

namespace aggregators

Typedefs

template<typename Share, typename EVector>
using A_ = ASharedVector<Share, EVector>

template<typename Share, typename EVector>
using B_ = BSharedVector<Share, EVector>

Enums

enum class Direction

Denotes the direction of an aggregation.

Values:

enumerator Forward

enumerator Reverse

Functions

template<typename A>
void sum(const A &group, A &a, const A &b)

Arithmetic sum aggregation.

Template Parameters:

A – Arithmetic shared vector type.

Parameters:

• group – Grouping bits indicating which elements to aggregate.

• a – Accumulator vector (modified in place).

• b – Input vector to be aggregated.

template<typename B>
void bit_or(const B &group, B &a, const B &b)

Boolean OR aggregation.

Template Parameters:

B – Boolean shared vector type.

Parameters:

• group – Grouping bits indicating which elements to aggregate.

• a – Accumulator vector (modified in place).

• b – Input vector to be aggregated.

template<typename A>
void count(const A &group, A &a, const A &b)

Count aggregation (delegates to sum).

Template Parameters:

A – Arithmetic shared vector type.

Parameters:

• group – Grouping bits indicating which elements to count.

• a – Accumulator vector (modified in place).

• b – Input vector (typically all ones for counting).

template<typename B>
void _min_max_agg(const B &group, B &a, const B &b, const bool &minimum = false)

Internal helper for min/max aggregation.

Template Parameters:

B – Boolean shared vector type.

Parameters:

• group – Grouping bits indicating which elements to aggregate.

• a – Accumulator vector (modified in place).

• b – Input vector to be aggregated.

• minimum – If true, computes minimum; if false, computes maximum.

template<typename B>
void max(const B &group, B &a, const B &b)

Maximum aggregation.

Template Parameters:

B – Boolean shared vector type.

Parameters:

• group – Grouping bits indicating which elements to aggregate.

• a – Accumulator vector (modified in place).

• b – Input vector to be aggregated.

template<typename B>
void min(const B &group, B &a, const B &b)

Minimum aggregation.

Template Parameters:

B – Boolean shared vector type.

Parameters:

• group – Grouping bits indicating which elements to aggregate.

• a – Accumulator vector (modified in place).

• b – Input vector to be aggregated.

template<typename T>
void copy(const T &group, T &a, const T &b)

Identity “aggregation”, used for non-aggregated joins. Templated to accept either arithmetic or boolean types. Copies rows from left to the right.

Parameters:

• group – grouping bits.

• a – first vector, which will be updated.

• b – second vector.

template<typename B>
void valid(const B &group, B &a, const B &b)

validity aggregation. For internal use while updating valid column.

Template Parameters:

B – Boolean shared vector type.

Parameters:

• group – Grouping bits.

• a – Accumulator vector (modified in place).

• b – Input vector.

template<typename S, typename E>
void aggregate(std::vector<B_<S, E>> &keys, const std::vector<std::tuple<B_<S, E>, B_<S, E>, void (*)(const B_<S, E>&, B_<S, E>&, const B_<S, E>&)>> &agg_spec_b, const std::vector<std::tuple<A_<S, E>, A_<S, E>, void (*)(const A_<S, E>&, A_<S, E>&, const A_<S, E>&)>> &agg_spec_a, const enum Direction dir = Direction::Forward, std::optional<B_<S, E>> sel_b = {})

Sorting-network based agregation. Assumes all vectors are the same size.

Template Parameters:

• S – underlying data type of vectors

• E – Share container type.

Parameters:

• keys – vector of keys to join and aggregate on

• agg_spec_b – boolean aggregations

• agg_spec_a – arithmetic aggregations

• dir – which direction to run the aggregation

• sel_b – selection column (for table operations, usually table ID)

template<typename S, typename E>
void aggregate(std::vector<B_<S, E>> &keys, const std::vector<std::tuple<B_<S, E>, B_<S, E>, void (*)(const B_<S, E>&, B_<S, E>&, const B_<S, E>&)>> &agg_spec_b, const std::vector<std::tuple<A_<S, E>, A_<S, E>, void (*)(const A_<S, E>&, A_<S, E>&, const A_<S, E>&)>> &agg_spec_a, B_<S, E> sel_b)

Aggregation, with additional selection (window) argument. Performs reverse aggregation.

Template Parameters:

• S –

• E –

Parameters:

• keys –

• agg_spec_b –

• agg_spec_a –

• sel_b –

template<typename T>
void tree_prefix_sum(T v, const bool &reverse = false)

Compute a prefix sum over a vector using a log-depth aggregation tree. Based on sorting network aggregation but entirely local computation, with the simplification that all entries belong to the same group.

TODO: extend this to any user-supplied associative operation

Template Parameters:

T – vector type (shared or plaintext)

Parameters:

• v – input vector

• reverse – whether to compute a suffix sum instead

Variables

enum orq::aggregators::Direction Direction

namespace orq

namespace operators

Functions

template<typename Share, typename EVector>
static void distinct(std::vector<BSharedVector<Share, EVector>*> &keys, BSharedVector<Share, EVector> *res)

Obliviously marks distinct rows based on keys (adjacent rows only).

Only adjacent rows are considered, so vectors should be sorted before calling for global uniqueness.

Template Parameters:

• Share – The underlying data type of the shared vectors.

• EVector – Share container type.

Parameters:

• keys – List of keys to consider for uniqueness.

• res – Vector to place the result in.

template<typename Share, typename EVector>
static void distinct(std::vector<BSharedVector<Share, EVector>> &keys, BSharedVector<Share, EVector> &res)

Marks distinct rows based on keys (vector reference overload).

Template Parameters:

• Share – The underlying data type of the shared vectors.

• EVector – Share container type.

Parameters:

• keys – Vector of keys to consider for uniqueness.

• res – Vector to place the result in.

namespace orq

namespace aggregators

template<typename A, typename B>
class AggregationSelector

#include <aggregation_selector.h>

A helper type to store an aggregation of either AShared or BShared type.

Template Parameters:

• A –

• B –

Public Functions

inline AggregationSelector(bf_t bFunc)

inline AggregationSelector(af_t aFunc)

inline af_t getA()

Get the AShared function. If this object does not store an AShared function, abort.

Returns:

af_t

inline bf_t getB()

Get the BShared function. If this object does not store a BShared function, abort.

Returns:

bf_t

inline bool isAggregation()

Check if the stored function is a copy aggregation or aggregation.

Returns:

true the stored function is an aggregation (non-copy)

Returns:

false the stored function is a copy function

Private Types

using af_t = void (*)(const A&, A&, const A&)

using bf_t = void (*)(const B&, B&, const B&)

Private Members

bf_t bFunc

af_t aFunc

struct JoinOptions

Options struct for join. Construct an instance and pass it in, or use inline struct initializer syntax.

Available fields:

• left_outer: if this is a left outer join.

• right_outer: if this is a right outer join.

• anti: if this is an anti join.

• trim_invalid: whether to trim invalid rows from the output (bounded by the size of the right table)

The join options generalize the other kinds of joins: inner joins are neither left outer nor right outer; full outer joins are both left outer and right outer. The default is an inner join; i.e., both are false.

struct AggregationOptions

Options struct for aggregation.

Available fields:

• reverse: whether this is a forward or reverse aggregation. (default false)

• do_sort: whether to sort first. (default true)

• mark_valid: whether to mark valid rows post-aggregation. (default true)

• table_id: an optional string pointing to the name of the table ID column.

Streaming

namespace orq

namespace operators

Functions

template<typename Share, typename EVector>
static void tumbling_window(ASharedVector<Share, EVector> &key, const Share &window_size, ASharedVector<Share, EVector> &res)

Computes tumbling window identifiers for stream processing.

A tumbling window divides the stream into non-overlapping windows of fixed size. This function computes the window identifier for each element by dividing the key (typically a timestamp or sequence number) by the window size.

Template Parameters:

• Share – The underlying data type of the shared vectors.

• EVector – Share container type.

Parameters:

• key – Input vector containing keys/timestamps for window assignment.

• window_size – The size of each tumbling window.

• res – Output vector that will contain the computed window identifiers.

template<typename Share, typename EVector>
void mark_gap_session(ASharedVector<Share, EVector> &timestamp, BSharedVector<Share, EVector> &session_start, const Share &gap)

Marks the start of new gap-based sessions in a timestamp sequence.

This function identifies session boundaries based on gaps in timestamps. A new session starts when the gap between consecutive timestamps exceeds the specified threshold. The first element is always marked as a session start.

Template Parameters:

• Share – The underlying data type of the shared vectors.

• EVector – Share container type.

Parameters:

• timestamp – Input vector of timestamps in ascending order.

• session_start – Output boolean vector marking session start positions.

• gap – The maximum allowed gap between timestamps within a session.

template<typename Share, typename EVector>
void gap_session_window(std::vector<BSharedVector<Share, EVector>> &keys, ASharedVector<Share, EVector> &timestamp_a, BSharedVector<Share, EVector> &timestamp_b, BSharedVector<Share, EVector> &window_id, const Share &gap)

Creates gap-based session windows for stream aggregation.

This function implements session windowing based on timestamp gaps. Sessions are identified using the mark_gap_session function, then window identifiers are computed using reverse aggregation to assign the same window ID to all elements within a session.

Template Parameters:

• Share – The underlying data type of the shared vectors.

• EVector – Share container type.

Parameters:

• keys – Vector of key vectors used for aggregation operations.

• timestamp_a – Arithmetic shared vector of timestamps.

• timestamp_b – Boolean shared vector of timestamps (for multiplexing).

• window_id – Output vector that will contain the computed window identifiers.

• gap – The maximum allowed gap between timestamps within a session.

template<typename Share, typename EVector>
void mark_threshold_session(BSharedVector<Share, EVector> &function_res, BSharedVector<Share, EVector> &session_start, BSharedVector<Share, EVector> &potential_window, const Share &threshold)

Marks the start of new threshold-based sessions.

This function identifies session boundaries based on a threshold applied to a function result (e.g., sensor readings, activity levels). A new session starts when the function result exceeds the threshold and the previous element was below the threshold.

Template Parameters:

• Share – The underlying data type of the shared vectors.

• EVector – Share container type.

Parameters:

• function_res – Input vector containing function results to compare against threshold.

• session_start – Output boolean vector marking session start positions.

• potential_window – Output boolean vector indicating elements above threshold.

• threshold – The threshold value for session detection.

template<typename Share, typename EVector>
void threshold_session_window(std::vector<BSharedVector<Share, EVector>> &keys, BSharedVector<Share, EVector> &function_res, BSharedVector<Share, EVector> &timestamp_b, BSharedVector<Share, EVector> &window_id, const Share &gap)

Creates threshold-based session windows for stream aggregation.

This function implements session windowing based on threshold detection. Sessions are identified when function results exceed a threshold, and window identifiers are computed using aggregation with the potential_window as a selection mask to only include elements that meet the threshold criteria.

Template Parameters:

• Share – The underlying data type of the shared vectors.

• EVector – Share container type.

Parameters:

• keys – Vector of key vectors used for aggregation operations.

• function_res – Input vector containing function results for threshold comparison.

• timestamp_b – Boolean shared vector of timestamps (for multiplexing).

• window_id – Output vector that will contain the computed window identifiers.

• gap – The threshold value for session detection (note: parameter name is misleading).

Common

namespace orq

namespace operators

Functions

template<typename Share, typename EVector>
static BSharedVector<Share, EVector> multiplex(const BSharedVector<Share, EVector> &sel, const BSharedVector<Share, EVector> &a, const BSharedVector<Share, EVector> &b)

Conditional selection between two boolean shared vectors.

Performs oblivious selection: returns a if sel is false, b if sel is true.

Template Parameters:

Share – The underlying data type of the shared vectors.

Parameters:

• sel – Boolean selector vector (extended to full bit width).

• a – First input vector (returned when sel is false).

• b – Second input vector (returned when sel is true).

Returns:

The multiplexed result vector.

template<typename Share, typename EVector>
static ASharedVector<Share, EVector> multiplex(const ASharedVector<Share, EVector> &sel, const ASharedVector<Share, EVector> &a, const ASharedVector<Share, EVector> &b)

Conditional selection between two arithmetic shared vectors.

Performs oblivious selection: returns a if sel is 0, b if sel is 1. Uses linear combination for arithmetic shares.

Template Parameters:

Share – The underlying data type of the shared vectors.

Parameters:

• sel – Arithmetic selector vector.

• a – First input vector (returned when sel is 0).

• b – Second input vector (returned when sel is 1).

Returns:

The multiplexed result vector.

template<typename Share, typename EVector>
static void auto_conversion(BSharedVector<Share, EVector> &x, BSharedVector<Share, EVector> &res)

Identity conversion for boolean shared vectors.

Template Parameters:

Share – The underlying data type of the shared vectors.

Parameters:

• x – Input boolean shared vector.

• res – Output boolean shared vector (copy of input).

template<typename Share, typename EVector>
static void auto_conversion(ASharedVector<Share, EVector> &x, ASharedVector<Share, EVector> &res)

Identity conversion for arithmetic shared vectors.

Template Parameters:

Share – The underlying data type of the shared vectors.

Parameters:

• x – Input arithmetic shared vector.

• res – Output arithmetic shared vector (copy of input).

template<typename Share, typename EVector>
static void auto_conversion(BSharedVector<Share, EVector> &x, ASharedVector<Share, EVector> &res)

Converts boolean shared vector to arithmetic shared vector.

Template Parameters:

Share – The underlying data type of the shared vectors.

Parameters:

• x – Input boolean shared vector.

• res – Output arithmetic shared vector.

template<typename Share, typename EVector>
static void auto_conversion(ASharedVector<Share, EVector> &x, BSharedVector<Share, EVector> &res)

Converts arithmetic shared vector to boolean shared vector.

Template Parameters:

Share – The underlying data type of the shared vectors.

Parameters:

• x – Input arithmetic shared vector.

• res – Output boolean shared vector.

template<typename Share, typename EVector>
static void secret_share_vec(const Vector<Share> &data, BSharedVector<Share, EVector> &out, const PartyID data_party = 0)

Creates boolean shared vector from plaintext data.

Template Parameters:

Share – The underlying data type of the shared vectors.

Parameters:

• data – Plaintext vector to be secret-shared.

• out – Output boolean shared vector.

• data_party – The party that provides the input data.

template<typename Share, typename EVector>
static void secret_share_vec(const Vector<Share> &data, ASharedVector<Share, EVector> &out, const PartyID data_party = 0)

Creates arithmetic shared vector from plaintext data.

Template Parameters:

Share – The underlying data type of the shared vectors.

Parameters:

• data – Plaintext vector to be secret-shared.

• out – Output arithmetic shared vector.

• data_party – The party that provides the input data.