##  1 Secure Large-Precision Construction

We are now ready to proceed with our solution for secure and accurate
floating-point number summation based on the superaccumulator structure of
Section LABEL:sec:superaccu. As before, a floating-point number $x_{i}$ is
represented as a tuple $\langle b_{i},v_{i},p_{i}\rangle$. Our solution takes
a sequence of $n$ secret-shared floating-point inputs
$\langle[b_{i}],[v_{i}],[p_{i}]\rangle$ and produces a secret-shared floating-
point sum. At high level, it proceeds by first converting the inputs into
superaccumulators, then computing the sum of the superaccumulators,
regularizing the result, and converting the resulting superaccumulator to a
floating-point number. The protocol, denoted as $\sf FLSum$, is given in
Algorithm 1 (superaccumulator summation and regularization are combined into
$\sf SASum$). [t] $[s]\leftarrow{\sf
FLSum}(\langle[b_{1}],[v_{1}],[p_{1}]\rangle,\ldots,\langle[b_{n}],[v_{n}],[p_{n}]\rangle)$
[1] let $\alpha=\lceil\frac{2^{e}+m}{w}\rceil$ and
$\beta=\lceil\frac{m+1}{w}\rceil+1$; $i=1,\ldots,n$ in parallel
$\langle[y_{i,\alpha}],\ldots,[y_{i,1}]\rangle\leftarrow{\sf
FL2SA}([b_{i}],[v_{i}],[p_{i}],\alpha,\beta)$;
$\langle[y_{\alpha}],\ldots,[y_{1}]\rangle\leftarrow{\sf
SASum}(\langle[y_{1,\alpha}],\ldots,[y_{1,1}]\rangle,\ldots,\langle[y_{n,\alpha}],\ldots$,
$[y_{n,1}]\rangle)$; $\langle[b],[v],[p]\rangle\leftarrow{\sf
SA2FL}([y_{\alpha}],\ldots,[y_{1}])$; $\langle[b],[v],[p]\rangle$; Data
representation parameters $e$, $m$, and $w$ are fixed throughout the
computation (as given in Equation LABEL:eq:float) and are implicit inputs.

When constructing a privacy-preserving solution, the computation that we
perform must be data-independent or data-oblivious, as not to disclose any
information about the underlying values. In the context of working with the
superaccumulator representation, we need to be accessing all superaccumulator
slots in the same way regardless of where the relevant data might be located.
In particular, when converting a floating-point value to a superaccumulator,
at most $\beta$ slots will contain non-zero values, but their location cannot
be disclosed. Similarly, when converting a regularized superaccumulator
corresponding to the sum to its floating-point representation, only most
significant non-zero slots are of relevance, but we need to hide their
position within the superaccumulator.

It is important to note that, unless specified otherwise, the computation is
performed over $2w$-bit shares (or ring $\mathbb{Z}_{2^{2w}}$ in our
implementation) to facilitate superaccumulator operations. We denote the
default element bitlength by $k$. This default bitlength is sufficient to
represent all values with a single exception: the bitlength $m$ mantissa $v$
in the floating-point representation can often exceed the value of $2w$. For
that reason, we represent mantissa $v$ as as a sequence of
$\lceil\frac{m+1}{w}\rceil$, or $\beta-1$, secret-shared blocks storing $w$
bits of $v$ per block. For clarity of exposition, each $v_{i}$ is written as a
single shared value in $\sf FLSum$, while in the more detailed protocols that
follow we make this representation explicit.

For most protocols in this paper, including $\sf FLSum$ in Algorithm 1,
security follows as a straightforward composition of the building blocks
assuming that the sub-protocols are themselves secure. Then using a standard
definition of security that requires a simulator without access to private
data to produce corrupt parties’ view indistinguishable from the protocol’s
real execution, we can invoke the simulators corresponding to the sub-
protocols and obtain security of the overall construction. Thus, in the
remainder of this work we discuss security of a specific protocol only when
demonstrating its security involves going beyond a simple composition of its
sub-protocols. In addition, for some protocols it is important to ensure that
they are data-oblivious (i.e., data-independent) such that the executed
instructions and accessed memory locations are independent of private inputs.
Data obliviousness is necessary for achieving security because we need the
ability to simulate corrupt parties’ view without access to private data.

###  1.1 Floating-Point to Superaccumulator Conversion

The first component is to convert floating-point inputs to their
superaccumulator representation. Because this operation is rather complex and
needs to be performed for each input, it dominates the cost of the overall
summation and thus it is important to optimize the corresponding computation.
The conversion procedure takes a floating point value
$([b],\langle[v_{\beta-1}],\ldots,[v_{1}]\rangle,[p])$ representing normalized
$x=(-1)^{b}\cdot(1+2^{-m}v)\cdot 2^{p-2^{e-1}-1}$ and needs to produce a
regularized superaccumulator as a vector of $\alpha$ $2w$-bit integers, where
$\alpha=\lceil\frac{2^{e}+m}{w}\rceil$.

####  1.1.1 The Overall Construction

To perform the conversion, the computation needs to determine the position
within the superaccumulator where the mantissa is to be written based on
exponent $[p]$, represent the mantissa as $\beta$ superaccumulator blocks, and
write the blocks in the right locations without disclosing what locations
within the superaccumulator those are. The protocol details are given as
protocol $\sf FL2SA$ (Algorithm 1.1.1), which we consequently explain. [t]
$\langle[y_{\alpha}],\ldots,[y_{1}]\rangle\leftarrow{\sf
FL2SA}([b],[v],[p],\alpha,\beta)$ 2 [1] $[p^{\mathit{high}}]\leftarrow{\sf
Trunc}([p],e,\log w)$; $[p^{\mathit{low}}]=[p]-[p^{\mathit{high}}]\cdot w$;
$[z]\leftarrow{\sf EQZ}([p])$; $[v]=[v]+2^{m}\cdot(1-[z])$; $[v]\leftarrow{\sf
LeftShift}([v],[p^{\mathit{low}}],\log w)$;
$\langle[v_{1}],\ldots,[v_{\beta}]\rangle={\sf Split}([v],\beta,w,m)$;
$i=1,\ldots,\beta$ in parallel $[v_{i}]\leftarrow([1]-2\cdot[b])\cdot[v_{i}]$;
$\langle[d_{\alpha}],\ldots,[d_{1}]\rangle={\sf
B2U}([p^{\mathit{high}}],\alpha)$; $i=1,\ldots,\alpha$ in parallel $i<\beta$
$[y_{i}]\leftarrow\sum^{i}_{j=0}[d_{i-j}]\cdot[v_{j}]$; $i\leq\alpha-\beta+1$
$[y_{i}]\leftarrow\sum^{\beta-1}_{j=0}[d_{i-j}]\cdot[v_{j}]$;
$[y_{i}]\leftarrow\sum^{\alpha-1-i}_{j=0}[d_{i-\beta+1+j}]\cdot[v_{\beta-1-j}]$;
$\langle[y_{\alpha}],\ldots,[y_{1}]\rangle$; [t]
$\langle[y_{\alpha}],\ldots,[y_{1}]\rangle\leftarrow{\sf
FL2SA}([b],\langle[v_{\beta-1}],\ldots,[v_{1}]\rangle$, $[p],\alpha,\beta)$
[1] $[p^{\mathit{high}}]\leftarrow{\sf Trunc}([p],e,\log w)$;
$[p^{\mathit{low}}]=[p]-[p^{\mathit{high}}]\cdot w$; $[z]_{1}\leftarrow{\sf
EQZ}([p])$; $[v_{\beta-1}]=[v_{\beta-1}]+2^{m-w(\beta-2)}\cdot{\sf
B2A}(1-[z]_{1},2w)$; $\langle[v_{\beta}],\ldots,[v_{1}]\rangle\leftarrow{\sf
Shift}(\langle[v_{\beta-1}],\ldots,[v_{1}]\rangle,$ $[p^{\mathit{low}}],w)$;
$i=1,\ldots,\beta$ in parallel $[v_{i}]\leftarrow([1]-2\cdot[b])\cdot[v_{i}]$;
$\langle[d_{\alpha}],\ldots,[d_{1}]\rangle\leftarrow{\sf
B2U}([p^{\mathit{high}}]+1,\alpha)$; $i=1,\ldots,\alpha$ in parallel $i<\beta$
$[y_{i}]\leftarrow\sum^{i}_{j=0}[d_{i-j}]\cdot[v_{j}]$; $i\leq\alpha-\beta+1$
$[y_{i}]\leftarrow\sum^{\beta-1}_{j=0}[d_{i-j}]\cdot[v_{j}]$;
$[y_{i}]\leftarrow\sum^{\alpha-1-i}_{j=0}[d_{i-\beta+1+j}]\cdot[v_{\beta-1-j}]$;
$\langle[y_{\alpha}],\ldots,[y_{1}]\rangle$;

Recall that the superaccumulator’s step is $2^{w}$. This means that $e-\log w$
most significant bits of the exponent $[p]$ represent the index of the first
non-zero slot in the accumulator. The $\log w$ least significant bits of the
exponent are used to shift the mantissa so that it is aligned with the block
representation of the superaccumulator. Thus, in the beginning of $\sf FL2SA$
we divide the exponent $[p]$ into two parts: the most significant $e-\log w$
are denoted by $p^{\mathit{high}}$ and the remaining $\log w$ bits are denoted
by $p^{\mathit{low}}$ (lines 1–2).

The next task is to use the mantissa (represented as $\beta-1$ blocks) and
$[p^{\mathit{low}}]$ to generate $\beta$ superaccumulator blocks. First,
recall that normalized floating-point representation assumes that the most
significant bit of the mantissa is 1 and is implicit in the floating-point
representation. Thus, we need to prepend 1 as the $(m+1)$st bit of $v$. In
$\sf FL2SA$ we do this conditionally only when the exponent is non-zero (lines
3–4) because when $p=0$, normalization might not be possible (e.g., if the
floating-point value represents a zero). Second, we need to shift the updated
mantissa blocks by a private $\log w$-bit value $p^{low}$ to be aligned with
the boundaries of superaccumulator blocks and update each value to be $w$ bits
by carrying the overflow into the next block.

To perform re-partitioning, we considered solutions based on bit decomposition
and truncation for re-partitioning the blocks, and the second approach was
determined to be faster. Our final solution – a protocol called $\sf Shift$
that takes the original mantissa blocks – left shifts the values by private
$[p^{\mathit{low}}]$ positions, where $w$ is the upper bound on the amount of
shift, and re-aligns the blocks to contain $w$ bits each using truncation. The
details of the $\sf Shift$ protocol are deferred to the next sub-section.
After producing the superaccumulator blocks (line 5), we update the sign of
each block using bit $[b]$ (lines 6–8). The desired superaccumulator
representation is depicted in Figure 1, where the produced superaccumulator
blocks are intended to be written in positions $p^{\mathit{high}}$ \+ 1
through $p^{\mathit{high}}+\beta$.

Figure 1: Illustration of floating-point to superaccumulator conversion.

The last task is to write the generated $\beta$ superaccumulator blocks
$[v_{i}]$s into the right positions of our $\alpha$-block superaccumulator, as
specified by the value of $[p^{\mathit{high}}]$. Because the computation must
be data-oblivious, the location of writing cannot be revealed and the access
pattern must be the same for any value of $p^{\mathit{high}}$. To accomplish
the task, we considered two possible solutions: (i) turning the value of
$p^{high}$ into a bit array of size $\alpha$ with the $p^{\mathit{high}}$
value set to 1 and all others set to 0 and using the bit array to create
superaccumulator blocks and (ii) creating a bit array with a single 1 in the
first location and rotating the bit array by a private amount
$p^{\mathit{high}}$. The first approach was determined to be faster and we
describe it next.

The conversion of $[p^{\mathit{high}}]+1$, the value of which ranges between 1
and $\alpha$, to a bit array of private bits with the
($p^{\mathit{high}}$+1)th bit set to 1 can be viewed as binary to unary
conversion, denoted by $\sf B2U$. Prior work considered this building block,
and specifically in the context of secure floating-point computation
[ali2013], but prior implementations were over a field. Because computation
over a ring of the form $\mathbb{Z}_{2^{k}}$ can be substantially faster, we
design a new protocol suitable over a ring using recent results, as described
later in this section. After the binary-to-unary conversion of
$p^{\mathit{high}}+1$ (line 9 of $\sf FL2SA$), each slot of the
superaccumulator $[y_{i}]$ is computed as the dot product of the previously
computed data blocks $[v_{i}]$s and at most $\beta$ bits $[d_{j}]$s (lines
10–18) because the data blocks need to be written at positions
$p^{\mathit{high}}-\beta+1$ through $p^{\mathit{high}}$. In particular, for
the middle superaccumulator blocks, there are $\beta$ bits and data blocks to
consider when creating each superaccumulator block $[y_{i}]$, while the
boundary blocks would iterate over fewer options. For example, the block
$[y_{1}]$ will be updated to $[v_{1}]$ only if $[d_{1}]=[1]$, while block
$[y_{2}]$ will be updated to $[v_{1}]$ or $[v_{2}]$ in the case of
$[d_{1}]=[1]$ or $[d_{2}]=[1]$, respectively. All superaccumulator blocks are
updated in parallel with communication cost equivalent to that of $\alpha$
multiplications.

####  1.1.2 New Building Blocks.

What remains is to describe our $\sf Shift$ and $\sf B2U$ protocols. The $\sf
Shift$ protocol takes an integer value (mantissa in the context of this work)
stored in $\beta-1$ blocks $[v_{\beta-1}],\ldots,[v_{1}]$, shifts the value
left by a private amount specified by the second argument $[p]$, where the
value of $p$ ranges between 0 and $w$ specified by the third argument, and
outputs $\beta$ new blocks $[v_{\beta}],\ldots,[v_{1}]$. It is implicit in the
interface specification that each original block representation has (at least)
$w$ unused bits, so that the content of each block can be shifted by up to $w$
positions without losing information. In particular, we assume that each block
has $w$ bits occupied, so that after the shift the intermediate result can
grow to $2w$ bits before being reorganized to occupy $w$ bits per block.

[t] $\langle[v_{\beta}],\ldots,[v_{1}]\rangle\leftarrow{\sf
Shift}(\langle[v_{\beta-1}],\ldots,[v_{1}]\rangle,[p],w)$ [1] let $\gamma=\log
w$; $\langle[p_{\gamma}]_{1},\ldots,[p_{1}]_{1}\rangle\leftarrow{\sf
BitDec}([p],\gamma)$; $j=1,\ldots,\gamma$ in parallel $[p_{j}]\leftarrow{\sf
B2A}([p_{j}]_{1})$;
$[s]\leftarrow\prod^{\gamma}_{j=1}(2^{2^{j-1}}[p_{j}]+1-[p_{j}])$;
$i=1,\ldots,\beta-1$ in parallel $[u_{i}]\leftarrow[v_{i}][s]$;
$[d_{i}]\leftarrow{\sf Trunc}([u_{i}],2w,w)$; $i=2,\ldots,\beta-1$ in parallel
$[v_{i}]=[u_{i}]-2^{w}[d_{i}]+[d_{i-1}]$; $[v_{1}]=[u_{1}]-2^{w}[d_{1}]$;
$[v_{\beta}]=[d_{\beta-1}]$; $\langle[v_{\beta}],\ldots,[v_{1}]\rangle$;

The computation, given in Algorithm 1.1.2, starts by bit-decomposing the
private amount of shift $[p]$ and converting the resulting bits to ring
elements (lines 1–5). The content of each block $[v_{i}]$ is shifted left (as
multiplication by a power of 2) by the appropriate number of positions
depending on the value of each bit of the amount of shift: when bit $[p_{j}]$
is 0, the value is multiplied by 1; otherwise it is multiplied by a power of 2
that depends on the index $j$ (lines 6–8). We then truncate each shifted block
(line 9) to split the value into the least significant $w$ bits that the block
will retain and the most significant $w$ bits which are the carry for the next
block. Each block is consequently updated by taking the carry from the prior
block and keeping its $w$ least significant bits (lines 11–15). Because we
shift all blocks in the same way, this operation corresponds to a shift with
block re-aligning on the boundary of $w$ bits per block.

Our ring-based solution for binary-to-unary conversion $\sf B2U$ takes a
private integer $[a]$ and public range, where $0<a\leq\ell$, and produces a
bit array $\langle[b_{1}],\ldots,[b_{\ell}]\rangle$ with the $a$th bit set to
1 and all other bits set to 0. Our goal is to have a variant suitable for
computation over ring $\mathbb{Z}_{2^{k}}$ using most efficient currently
available tools. Our solution, shown as Algorithm 1.1.2, is based on ideas
used for retrieving an element of an array at a private index in [bla20]. [t]
$\langle[b_{1}],\ldots,[b_{\ell}]\rangle\leftarrow{\sf B2U}([a],\ell)$ [1]
$q=\lceil\log\ell\rceil$; $[r],[r_{q-1}]_{1},\ldots,[r_{0}]_{1}\leftarrow{\sf
edaBit}(q)$; $\langle[d_{0}]_{1},\ldots,[d_{2^{q}-1}]_{1}\rangle\leftarrow{\sf
AllOr}([r_{q-1}]_{1},\ldots,[r_{0}]_{1})$; $c={\sf Open}([a]-1+[r],q)$;
$i=0,\ldots,\ell-1$ in parallel $[b_{i+1}]\leftarrow{\sf B2A}(1-[d_{(c-i)\mod
2^{q}}]_{1})$; $\langle[b_{1}],\ldots,[b_{\ell}]\rangle$;

The high-level idea consists of generating $\lceil\log\ell\rceil$ random bits
$[r_{i}]$ that collectively represent a random $\lceil\log\ell\rceil$-bit
integer $[r]$, generating $\lceil\log\ell\rceil$-ary ORs of $[r]-i$ for all
$\log\ell$-bit $i$ and flipping the resulting bits. This creates a bit array
with all values set to 0 except the element at private location $[r]$ set to
1. The ORs are computed simultaneously for all values using protocol $\sf
AllOr$. Consequently, the algorithm opens the value of $c=r+a$ (modulo
$2^{\lceil\log\ell\rceil}$) and uses the disclosed value to position the only
1 bit of the array in location $a$ (i.e., the bit will be set at position $i$
for which $c-i=r+a-i=r$).

Note that the protocol explicitly calls $\sf edaBit$ for random bit generation
(and inherits its properties) and there are alternatives. We enhance
performance by carrying out the most time-consuming portion of the
computation, namely $\sf AllOr$, over a small ring $\mathbb{Z}_{2}$ because
the computation uses Boolean values. This means that after producing
$2^{\lceil\log\ell\rceil}$ bits through a sequence of calls to $\sf edaBit$,
$\sf AllOr$, and $\sf Open$ and array rotation, we need to convert their
shares from $\mathbb{Z}_{2}$ to $\mathbb{Z}_{2^{k}}$, which we do using
binary-to-arithmetic share conversion $\sf B2A$ (line 6). In addition,
reconstruction of $c=r+a$ on line 4 needs to be performed using $q$-bit shares
to enforce modulo reduction and prevent information leakage, where share
truncation prior to the reconstruction is performed by $\sf Open$ itself using
the modulus specified as the second argument.

As far as security goes, we note that besides composing sub-protocols the
protocol also reconstructs a value which is a function of private input $[a]$
on line 8. Security is still achieved because $[r]$ is a private value
uniformly distributed in $\mathbb{Z}_{2^{q}}$. Thus, the value of $[a]$ is
perfectly protected and the opened element of $\mathbb{Z}_{2^{q}}$ is also
uniformly distributed over the entire range. This means that the view is
easily simulatable by choosing a random element of $\mathbb{Z}_{2^{q}}$ as the
output of $\sf Open$ and getting the parties to reconstruct that value.

The last component that we would like to discuss is the $\sf B2A$ protocol.
Solutions for converting a bit $b$ secret shared over $\mathbb{Z}_{2}$ to the
same value secret shared over larger ring $\mathbb{Z}_{2^{k}}$,
$[b]_{k}\leftarrow{\sf B2A}([b]_{1},k)$, appear in the literature.
Conventional solutions that use square root computation to generate a random
bit (e.g., [dam2019]) temporarily increase the ring to be
$\mathbb{Z}_{2^{k+2}}$ for computing intermediate results. In the context of
this work, this effectively doubles the size of the ring elements during the
computation when we use a ring $\mathbb{Z}_{2^{32}}$ or $\mathbb{Z}_{2^{64}}$.
When the number of participants is not large, an alternative is to cast each
local share in $\mathbb{Z}_{2}$ as a share in $\mathbb{Z}_{2^{k}}$ and have
the parties compute XOR of those values over $\mathbb{Z}_{2^{k}}$. This
approach is used in Araki et al. [ara18] in the three-party setting with
honest majority based on replicated secret sharing (RSS) that costs two
consecutive multiplications. The approach of Mohassel and Rindal [moh18] would
also require the same communication in two rounds, but the use of the three-
party OT procedure in that work reduces the number of rounds to one.

Protocol | Communication | Rounds
---|---|---
[dam2019] | $6(k+2)$ | 2
[ara18] | $6k$ | 2
[moh18] | $6k$ | 1
Ours | $3k$ | 2
Table 1: Comparison of three-party $\sf B2A$ protocols in the honest majority
setting with target ring $\mathbb{Z}_{2^{k}}$. Total protocol communication is
reported in bits.

In this work, we design a new solution in the three-party setting using RSS
that does not increase the ring size and lowers the cost of prior protocols as
illustrated in Table 1. Unlike many protocols in this work that can be adapted
to different types of underlying arithmetic and the number of computational
parties, this is the only protocol that specifically uses RSS with $N=3$ and
threshold $t=1$.

With RSS when $N=3$, there are three shares representing any secret-shared
$[x]$ which we denote as $[x]^{(1)}$, $[x]^{(2)}$, and $[x]^{(3)}$. Each
computational party $P_{i}$ holds two shares with indices different from $i$.
For example, $P_{2}$ holds shares $[x]^{(1)}$ and $[x]^{(3)}$. We use notation
$[x]^{(i)}_{k}$ to denote a share in ring $\mathbb{Z}_{2^{k}}$. In addition,
each participant with access to shares indexed by $i$ holds a (sufficiently
long) key ${\sf key}_{i}$ used as the seed to a pseudorandom generation. For
clarity, we refer to a PRG keyed by ${\sf key}_{i}$ as ${\sf G}_{i}$. A call
to ${\sf G}_{i}.{\sf next}$ produces a pseudorandom ring element.

The input to $\sf B2A$ is a bit secret-shared over $\mathbb{Z}_{2}$ and we
need to convert the bit to the shares over $\mathbb{Z}_{2^{k}}$ as specified
by the second argument. The protocol is given as Algorithm 1. [t]
$[x]_{k}\leftarrow{\sf B2A}([x]_{1},k)$ Setup: Party $P_{i}$ holds shares and
has access to PRGs $\sf G_{j}$ with indices $j\neq i$.

set $[a]_{k}=\langle[x]^{(1)}_{1},0,0\rangle$, $[b]_{k}=\langle
0,[x]^{(2)}_{1},0\rangle$, and $[c]_{k}=\langle 0,0,[x]^{(3)}_{1}\rangle$;

evaluate $[s]_{k}=[a]_{k}\cdot[b]_{k}$ as follows:

$P_{3}$ computes $[s]^{(2)}_{k}={\sf G}_{2}.{\sf next}$,
$[s]^{(1)}_{k}=[a]^{(1)}_{k}\cdot[b]^{(2)}_{k}-[s]^{(2)}_{k}$ (in
$\mathbb{Z}_{2^{k}}$), and sends $[s]^{(1)}_{k}$ to $P_{2}$;

$P_{2}$ sets $[s]^{(1)}_{k}$ to the received value and $[s]^{(3)}_{k}=0$;

$P_{1}$ computes $[s]^{(2)}_{k}={\sf G}_{2}.{\sf next}$ and sets
$[s]^{(3)}_{k}=0$;

$[s]_{k}=[a]_{k}+[b]_{k}-2[s]_{k}$;

evaluate $[u]_{k}=[s]_{k}\cdot[c]_{k}$ as follows:

$P_{2}$ computes $[u]^{(1)}_{k}={\sf G}_{1}.{\sf next}$,
$u^{\prime}=[s]^{(1)}_{k}\cdot[c]^{(3)}_{k}-[u]^{(1)}_{k}$ (in
$\mathbb{Z}_{2^{k}}$), sends $u^{\prime}$ to $P_{1}$, and computes
$[u]^{(3)}_{k}=u^{\prime}+{\sf G}_{3}.{\sf next}$ (in $\mathbb{Z}_{2^{k}}$).

$P_{1}$ receives $u^{\prime}$, computes $u^{\prime\prime}={\sf G}_{3}.{\sf
next}$, $[u]^{(2)}_{k}=[s]^{(2)}_{k}\cdot[c]^{(3)}_{1}-u^{\prime\prime}$, and
$[u]^{(3)}_{k}=u^{\prime}+u^{\prime\prime}$ (all computation is in
$\mathbb{Z}_{2^{k}}$), and sends $[u]^{(2)}_{k}$ to $P_{3}$;

$P_{3}$ sets $[u]^{(2)}_{k}$ to the received value and $[u]^{(1)}_{k}={\sf
G}_{1}.{\sf next}$.

$[x]_{k}=[s]_{k}+[c]_{k}-2[u]_{k}$;

return $[x]_{k}$ The high-level idea behind the solution is that
$x=[x]^{(1)}_{1}\oplus[x]^{(2)}_{1}\oplus[x]^{(3)}_{1}$ and we use the
knowledge of the input shares by the parties to evaluate the two XOR
operations in the target ring. In particular, we can conceptualize the bit
shares $[x]^{(i)}_{1}$ as secret-shared values over $\mathbb{Z}_{2^{k}}$
represented as $[a]_{k}=\langle[x]^{(1)}_{1},0,0\rangle$, $[b]_{k}=\langle
0,[x]^{(2)}_{1},0\rangle$, and $[c]_{k}=\langle 0,0,[x]^{(3)}_{1}\rangle$. If
we securely evaluate $[a]_{k}\oplus[b]_{k}\oplus[c]_{k}$, we will obtain
secret-shared $[x]_{k}$ in the desired ring, which could be generically
accomplished by two sequential multiplications (i.e.,
$[a]\oplus[b]=[a]+[b]-2[a]\cdot[b]$). This is also the logic used in [ara18].

However, given that our shares of $a$, $b$, and $c$ have a special form, the
cost of that computation can be reduced. In particular, a typical
implementation of the multiplication operation involves multiplying accessible
shares locally and re-sharing the products with other parties using fresh
randomization to hide patterns. Because in our case some shares are set to 0,
their product will be 0 as well, and no re-sharing is needed. For example,
when computing $[a]_{k}\cdot[b]_{k}$, the only contributing term to the
product is the product of $[a]^{(1)}_{k}$ and $[b]^{(2)}$, which is computable
by $P_{3}$ in its entirety. As a result of such optimizations, the
communication cost of the overall protocol is one ring element per party.

Referring to Algorithm 1, as mentioned above, the product of $[a]$ and $[b]$
(step 2) can be computed locally by $P_{3}$, after which the product is re-
shared. The re-sharing uses proper $k$-bit elements to hide information about
the product and is split by $P_{3}$ in two shares to which it has access,
namely $[s]^{(1)}$ and $s^{(2)}$. This is similar to the re-sharing in regular
multiplication (see, e.g., [bac2020]) and involves $P_{3}$ communicating a
single ring element.

After turning the product into XOR (line 3), the parties need to compute the
product of $[s]_{k}$ and $[c]_{k}$, where $[s]_{k}$ has two non-empty shares
($[s]^{(1)}_{k}$ and $[s]^{(2)}_{k}$) and $[c]_{k}$ has one non-empty share
($[c]^{(3)}_{k}$). This involves $P_{2}$ computing the product
$[s]^{(1)}_{k}\cdot[c]^{(3)}_{k}$ and re-sharing by splitting it into two
shares and $P_{1}$ computing the product $[s]^{(2)}_{k}\cdot[c]^{(3)}_{1}$ and
also re-sharing it. As described in step 4 of Algorithm 1, $P_{2}$’s product
is split into $[u]^{(1)}_{k}$ and value $u^{\prime}$, which becomes a part of
$[u]^{(3)}_{k}$. Similarly, $P_{1}$’s product is split into $[u]^{(2)}_{k}$
and value $u^{\prime\prime}$, which becomes the second component of
$[u]^{(3)}_{k}$. Both $P_{1}$ and $P_{2}$ communicate one ring element each to
finish re-sharing and let everyone obtains the shares of the product $u$. The
party then finish the computation by turning the product into XOR (line 5).
The total communication is equivalent to that of a single multiplication.

We prove the following result:

######  Claim 1.

$\sf B2A$ protocol in Algorithm 1 is 1-private in the semi-honest model in the
three-party setting in the presence of a single computationally-bounded
corrupt party assuming $\sf G$ is a pseudo-random generator.

Proof We prove that our $\sf B2A$ protocol in Algorithm 1 is secure in the
presence of a single corrupt party. We consider corruption of party $P_{1}$,
$P_{2}$, and $P_{3}$ in turn and build a corresponding simulator for each
case.

Party $P_{1}$ is corrupt. We first assume that party $P_{1}$ is corrupt, and
build the corresponding simulator $S_{1}$ to simulate its view in the ideal
model. The simulator $S_{1}$ is constructed as follows:

  * •

In step 4(a), $S_{1}$ draws a uniformly random element
$u^{\prime}\leftarrow\mathbb{Z}_{2^{k}}$ and sends it to party $P_{1}$ on
behalf of party $P_{2}$.

  * •

In step 4(b), $S_{1}$ receives $[u]^{(2)}_{k}$ from $P_{1}$ on behalf of
$P_{3}$.

We next compare the view of $P_{1}$ that the simulator $S_{1}$ produces with
the view of the corrupt party $P_{1}$ in the real execution. In the beginning
of the protocol, $P_{1}$ holds $[b]_{k}^{(2)}=[x]_{1}^{(2)}$ and
$[c]_{k}^{(3)}=[x]_{1}^{(3)}$ and has access to ${\sf G}_{2}$ and ${\sf
G}_{3}$. The simulated view consists of $P_{1}$ receiving a randomly generated
$u^{\prime}$ in step 4(a), while in the real execution it was computed as
$u^{\prime}=[s]_{k}^{(1)}\cdot[c]_{k}^{(1)}-{\sf G}_{1}.{\sf next}$. Now
because $P_{1}$ does not have access to ${\sf G}_{1}$, the pseudo-random pad
${\sf G}_{1}.{\sf next}$ information-theoretically protects the value of the
product $[s]_{k}^{(1)}\cdot[c]_{k}^{(1)}$. Thus, the value of $u^{\prime}$ in
the real execution is pseudo-random. Then because by definition of a pseudo-
random generator its output is indistinguishable from a truly random string of
the same size to a computationally-bounded adversary, we obtain that the
simulated and real views are indistinguishable.

Party $P_{2}$ is corrupt. Next, consider the case that party $P_{2}$ is
corrupt. We construct simulator $S_{2}$ as follows:

  * •

In step 2(a), $S_{2}$ draws a uniformly random
$[s]^{(1)}_{k}\leftarrow\mathbb{Z}_{2^{k}}$ and sends it to $P_{2}$ on behalf
of party $P_{3}$.

  * •

In step 4(b), $S_{2}$ receives $u^{\prime}$ from $P_{2}$ on behalf of $P_{1}$.

At computation initiation time, $P_{2}$ holds $[a]_{k}^{(1)}=[x]_{1}^{(1)}$
and $[c]_{k}^{(3)}=[x]_{1}^{(3)}$ and has access to ${\sf G}_{1}$ and ${\sf
G}_{3}$. Similar to the case of corrupt $P_{1}$, $S_{2}$ only communicates a
random value as $[s]^{(1)}_{k}$ to $P_{2}$ in step 2(a). In a real execution,
$[s]^{(1)}_{k}$ is computed as $[a]_{k}^{(1)}\cdot[b]_{k}^{(2)}-{\sf
G}_{2}.{\sf next}$, where ${\sf G}_{2}$ is inaccessible to $P_{2}$ and thus
its output information-theoretically protects the product. Because the PRG’s
output is computationally indistinguishable from a truly random string to a
computationally-bounded adversary, $P_{2}$’s simulated view is computationally
indistinguishable from the view in the real execution.

Party $P_{3}$ is corrupt. Finally, we construct simulator $S_{3}$ for the case
that party $P_{3}$ is corrupt:

  * •

In step 2(a), $S_{3}$ receives $[s]^{(1)}_{k}$ from party $P_{3}$ on behalf of
party $P_{2}$.

  * •

In step 4(b), $S_{3}$ draws a uniformly random value
$[u]^{(2)}_{k}\leftarrow\mathbb{Z}_{2^{k}}$ and sends it to $P_{3}$ on behalf
of $P_{1}$.

In the beginning of the computation, $P_{3}$ has access to
$[a]_{k}^{(1)}=[x]_{1}^{(1)}$, $[b]_{k}^{(2)}=[x]_{1}^{(2)}$, ${\sf G}_{1}$,
and ${\sf G}_{2}$. It then receives a random $[u]^{(2)}_{k}$ from $S_{3}$ in
the simulated view, while in the real execution the value is computed as
$u^{\prime}+u^{\prime\prime}$, where $u^{\prime\prime}={\sf G}_{3}.{\sf
next}$. Due to security of the PRG, its output is pseudo-random and
information-theoretically protects $u^{\prime}$. We obtain that the value
$P_{3}$ is indistinguishable from a truly random string to a computationally-
bounded $P_{3}$. Thus, we obtain that $P_{3}$’s views in real execution and
simulation are computationally indistinguishable.

We conclude that our $\sf B2A$ protocol is secure in the presence of a single
semi-honest adversary. $\Box$ $\sf B2A$ is an important building blocks of
many other protocols including truncation, ring conversion, bit decomposition,
etc. Thus, the above efficient three-party $\sf B2A$ impact performance of the
computation. For that reason, we analyze performance of building blocks and
our protocols in the three-party setting using RSS as given in Table 2. Note
that we separate input-independent computation that can be pre-computed and
the remaining (input-dependent) computation.

2*Protocol | Precomputable | After precomputation
---|---|---
| Communication | Rounds | Communication | Rounds
$\sf Mult$ | 0 | 0 | $3k$ | 1
${\sf Open}(\ell)$, $\ell\leq k$ | 0 | 0 | $3\ell$ | 1
$\sf B2A$ | 0 | 0 | $3k$ | 2
$\sf RandBit$ | $3k$ | 2 | 0 | 0
${\sf edaBit}(k)$ | $3k\log(k)+7k$ | $\log(k)+2$ | 0 | 0
${\sf edaBit}(\ell)$, $\ell<k$ | $3\ell\log(\ell)+5\ell+5k$ | $\log(\ell)+4$ | 0 | 0
${\sf PrefixOr}(n)$ (in $\mathbb{Z}_{2}$) | 0 | 0 | $1.5n\log(n)$ | $\log(n)$
${\sf PrefixAnd}(n)$ (in $\mathbb{Z}_{2}$) | 0 | 0 | $1.5n\log(n)$ | $\log(n)$
${\sf MSB}(k)$ | $3k\log(k)+10k$ | $\log(k)+2$ | $12k-12$ | $\log(k)+2$
${\sf EQZ}(k)$ | $3k\log(k)+7k$ | $\log(k)+2$ | $6k-3$ | $\log(k)+1$
${\sf Trunc}(\ell,u)$ | $3k\log(k)+18k$ | $\log(u)+3$ | $3k+3\ell+6u-6$ | $\log(u)+3$
${\sf BitDec}(\ell)$, $\ell<k$ | $3\ell\log(\ell)+5\ell+5k$ | $\log(\ell)+4$ | $3\ell\log(\ell)+3\ell$ | $\log(\ell)+1$
${\sf Convert}(k,k^{\prime})$ | $3k\log(k)+7k$ | $\log(k)+2$ | $3k^{\prime}k+3k\log(k)+3k$ | $\log(k)+3$
2*${\sf Shift}(\beta,w)$ | $(\beta-1)(3k\log(k)+18k)+$ |  $\max(\log(\gamma)+4$, | $6(\beta-1)(2k+w-1)+$ |  2*$\gamma+2\log(\gamma)+7$
| $3\gamma\log(\gamma)+5\gamma+5k$ | $\gamma+3)$ | $3\gamma(k+\log(\gamma)+1)-3k$ |
${\sf B2U}(\alpha)$ |  $[1.2$–$1.5]3\cdot 2^{\delta}+3\delta\log(\delta)+5\delta+5k$ | $2\log(\delta)+4$ | $3\alpha k+3\delta$ | 3
3*${\sf Normalize}(\beta,w)$ | $\beta(3k\log(k)+7k)+$ | $\max(\log(k)+2,$ | $3k(\beta l+\beta\log(k)+2l+\beta-1)+$ | $2\log(l)+\log(k)+$
| $6l\log(l)+17l$ | $\log(l)+2)$ | $1.5(l-m-2)\log(l-m-2)+$ | $\log(l-m-2)+10$
|  |  | $3l(\log(l)+6)-12$ |
Table 2: Performance of protocols in the three-party setting based on RSS
using ring $\mathbb{Z}_{2^{k}}$ (bit-level operations are over
$\mathbb{Z}_{2}$). Protocol parameters affecting performance are listed. Total
communication across all parties in bits. $\gamma=\lceil\log(w)\rceil$,
$\delta=\lceil\log(\alpha)\rceil$, and $l=w\beta$; $\alpha$, $\beta$, $w$, and
$m$ are computation parameters.

Random bit generation $[r]\leftarrow{\sf RandBit}$ (as used, e.g., in $\sf
MSB$) is implemented by using local randomness to generate shares of $[r]_{1}$
over $\mathbb{Z}_{2}$ and converting them to the larger ring using $\sf B2A$.
We favor the use of $\sf edaBit$ in sub-protocols in place of conventional
$\sf RandBit$ random bit generation. This lowers the amount of communication,
but increases the number of rounds.

The cost of $\sf AllOr$ as specified in [bla20] varies based on the size given
as an input. For that reason, in Table 2 we list a range of constants for
values $\alpha$ used with single and double precision in this work (the
smallest $\alpha=9$ with single precision and $w=32$ results in constant 1.5
and the largest $\alpha=132$ with double precision and $w=16$ results in
constant 1.2).

###  1.2 Superaccumulator Summation

Once we convert the floating-point inputs into superaccumulators, the next
step is to do the summation and regularize the result. This corresponds to the
protocol $\sf SASum$ given in Algorithm 1.2. [t]
$\langle[y_{\alpha}],\ldots,[y_{1}]\rangle\leftarrow{\sf
SASum}(\langle[y_{1,\alpha}],\ldots,[y_{1,1}]\rangle,\ldots$,
$\langle[y_{n,\alpha}],\ldots,[y_{n,1}]\rangle)$ [1] $i=1,\ldots,\alpha$ in
parallel $[s_{i}]=\sum^{n}_{j=1}[y_{j,i}]$; $[b_{i}]\leftarrow{\sf
MSB}([s_{i}])$; $[y_{i}]\leftarrow[s_{i}]\cdot(2[b_{i}]-1)$;
$[c_{i+1}]\leftarrow{\sf Trunc}([y_{i}],2w,w)$;
$[r_{i}]=[y_{i}]-[c_{i+1}]\cdot 2^{w}$;
$[y_{i}]\leftarrow[r_{i}]\cdot[b_{i}]+[c_{i}]\cdot[b_{i-1}]$
$\langle[y_{\alpha}],\ldots,[y_{1}]\rangle$; The summation of
superaccumulators is straightforward, where we sum each superaccumulator block
as $[s_{i}]=\sum^{n}_{i=1}[y_{i,j}]$ for $i=1,\ldots,\alpha$ (line 2). The
remaining computation regularizes the resulting superaccumulator. We first
compute the absolute value of each block $y_{i}$ (lines 3–4) and then split
the result into $w$ most significant bits (carry for the next block
$[c_{i+1}]$) and $w$ least significant bits ($[r_{i}]$) using truncation
(lines 5–6). The final block value is assembled from the carry of the prior
block and the remaining portion of the current block using their corresponding
signs (line 7). The carry into block 1 is 0.

Recall that each superaccumulator block is represented as a $2w$-bit integer
and we can add at most $n=2^{w-2}$ inputs without an overflow. If one needs to
sum more than $2^{w-2}$ inputs, the computation will proceed in layers, where
we first sum accumulators in batches of $2^{w-2}$, regularize the result and
then do another layer of summation and regularization to arrive at the final
regularized superaccumulator.

###  1.3 Superaccumulator to Floating-Point Conversion

What remains to discuss is the conversion of the regularized superaccumulator
representing the summation to the floating-point representation. To maintain
security, our protocols needs to obliviously select $\beta$ superaccumulator
blocks starting from the first non-zero block without disclosing the location
of the selected blocks. In the event that there are fewer than $\beta$ blocks
to extract, the solution will still return $\beta$ blocks.

The superaccumulator to floating-point conversion protocol $\sf SA2FL$ is
given as Algorithm 1.3 and proceeds as follows. [t]
$\langle[b],[p],[v]\rangle\leftarrow{\sf SA2FL}([y_{\alpha}],\ldots,[y_{1}])$
2 [1] $i=\beta,\ldots,\alpha-1$ in parallel $[c_{i}]=1-{\sf EQZ}([y_{i}])$;
$[d_{\alpha-1}]=[c_{\alpha-1}]$; $i=\alpha-2,\ldots,\beta$
$[d_{i}]=[d_{i+1}]+[c_{i}]$;

$i=\beta,\ldots,\alpha-2$ in parallel $[c^{\prime}_{i}]=1-{\sf EQZ}([d_{i}])$;
$[c^{\prime}_{\alpha-1}]=[c_{\alpha-1}]$; $i=\beta,\ldots,\alpha-2$ in
parallel $[d^{\prime}_{i}]=[c^{\prime}_{i}]-[c^{\prime}_{i+1}]$;
$[d^{\prime}_{\beta-1}]=[1]-[d_{\beta}]$;
$[d^{\prime}_{\alpha-1}]=[c_{\alpha-1}]$; $i=0,\ldots,\beta-1$ in parallel
$[v^{\prime}_{i}]\leftarrow\sum^{\alpha-\beta+i}_{j=i}[d^{\prime}_{j+\beta-1-i}]\cdot[y_{j}]$;
$[v^{\prime\prime}_{i}]\leftarrow{\sf Convert}([v^{\prime}_{i}],2w,w\beta)$;
$[v^{\prime}]=\sum^{\beta-1}_{i=0}[v^{\prime\prime}_{i}]\cdot 2^{w\times i}$;
$\langle[b],[p^{\prime}],[v]\rangle\leftarrow{\sf Normalize}([v],w\beta,m)$;
$[p]\leftarrow[p^{\prime}]+\sum^{\alpha-\beta}_{i=0}[d^{\prime}_{i+\beta-1}]\cdot
i\cdot w$; $\langle[b],[p],[v]\rangle$; [t]
$\langle[b],[v_{\beta-1}],\ldots,[v_{1}],[p]\rangle\leftarrow{\sf
SA2FL}([y_{\alpha}],\ldots,[y_{1}])$ [1] $i=\beta,\ldots,\alpha$ in parallel
$[c_{i}]_{1}\leftarrow{\sf EQZ}([y_{i}])$;
$\langle[d_{\alpha}]_{1},\ldots,[d_{\beta+1}]_{1}\rangle\leftarrow{\sf
PrefixAND}([c_{\alpha}]_{1},\ldots$, $[c_{\beta+1}]_{1})$;
$i=\beta,\ldots,\alpha$ in parallel $[d_{i}]\leftarrow{\sf B2A}([d_{i}]_{1})$;
$i=\beta+1,\ldots,\alpha-1$ in parallel $[u_{i}]=[d_{i+1}]-[d_{i}]$;
$[u_{\alpha}]=1-[d_{\alpha}]$; $[u_{\beta}]=[d_{\beta+1}]$; $i=1,\ldots,\beta$
in parallel
$[v_{i}]\leftarrow\sum^{\alpha-\beta+i}_{j=i}[u_{j+\beta-1-i}]\cdot[y_{j}]$;
$\langle[b],[v_{\beta-1}],\ldots,[v_{1}],[p]\rangle\leftarrow{\sf
Normalize}([v_{\beta}]$, $\ldots,[v_{1}])$;
$[p]=[p]+\sum^{\alpha-\beta+1}_{i=1}[u_{i+\beta-1}]\cdot i\cdot w$;
$\langle[b],[v_{\beta-1}],\ldots,[v_{1}],[p]\rangle$; Let $\sf ind$ denote the
(private) index of the first non-zero superaccumulator block. We restrict the
value we work with to be in the range $\alpha,\ldots,\beta$ to ensure that we
can always extract $\beta$ blocks, i.e., ${\sf ind}=\beta$ even if the first
non-zero block has the index smaller than $\beta$. Given a regularized
superaccumulator $[y_{\alpha}],\ldots,[y_{1}]$, we first test each block with
the index between $\beta$ and $\alpha$ for equality to zero. Once it is
determined which blocks are zero, we need to compute the prefix AND of the
computed bits (or, equivalently, the prefix OR of their complements) to
determine the first non-zero block. Recall that $\sf PrefixAND$, on input
$[x_{1}],\ldots,[x_{n}]$ outputs $[y_{1}],\ldots,[y_{n}]$, where
$y_{i}=\prod_{j=1}^{i}x_{j}$. Also, for performance reasons, we do not convert
the resulting bits of equality comparisons to full ring element and instead
proceed with prefix computation on bits.

For prefix AND, we start with the highest index and thus the output will be a
sequence of 1s followed by 0s starting from the high indices. The first 0 is
the value we want to mark differently from others, indicating the first non-
zero block. This is accomplished by computing the difference between two
adjacent block values (lines 8–12) and we obtain the first non-zero block
marked with 1, while all other blocks are as 0. It is important to note that
the $\beta$th block will be marked even if all of the blocks
$\alpha,\ldots,\beta$ are 0, because in that case we still need to retrieve
$\beta$ blocks with the smallest values, i.e., $\sf ind$ is set to $\beta$ and
the actual content of the $\beta$th block is irrelevant.

The next step is to extract $\beta$ blocks starting from the marked block,
i.e., using the previously introduced notation, we extract the blocks $[y_{\sf
ind}],\ldots,[y_{{\sf ind}-\beta+1}]$ (lines 13–15). We consequently normalize
the block using a sub-protocol $\sf Normalize$ that returns a floating-point
representation of the blocks, which is consequently updated on line 17 to
modify the exponent according to the position of the extracted blocks in the
superaccumulator.

The next protocol, $\sf Normalize$, corresponds to the conversion of $\beta$
extracted superaccumulator blocks to a normalized floating-point value. As
before, each block $[v_{i}]$ is assumed to contain $w$ bits and we normalize
the value by finding the first non-zero bit and creating an $m$-bit mantissa
with the $(m+1)$st bit set to 1 and the remaining bits partitioned among the
output blocks $[v_{\beta-1}],\ldots,[v_{1}]$. [t]
$\langle[b],[v_{\beta-1}],\ldots,[v_{1}],[p]\rangle\leftarrow{\sf
Normalize}([v_{\beta}],\ldots$, $[v_{1}])$ [1] let $l=w\cdot\beta$;
$i=1,\ldots,\beta$ in parallel $[v_{i}]_{l}\leftarrow{\sf Convert}([v],k,l)$;
$[s]_{l}=\sum_{i=1}^{\beta}2^{w(i-1)}[v_{i}]_{l}$; $[b]_{l}\leftarrow
1-2\cdot{\sf MSB}([s]_{l})$; $[v]_{l}\leftarrow[b]_{l}\cdot[s]_{l}$;
$\langle[c_{l-1}]_{1},\ldots,[c_{0}]_{1}\rangle\leftarrow{\sf
BitDec}([v]_{l},l)$;
$\langle[d_{l-2}]_{1},\ldots,[d_{m+1}]_{1}\rangle\leftarrow{\sf
PrefixOR}([c_{l-2}]_{1}$, $\ldots,[c_{m+1}]_{1})$; $i=0,\ldots,l-1$ in
parallel $[c_{i}]\leftarrow{\sf B2A}([c_{i}]_{1})$; $i=m+1,\ldots,l-2$ in
parallel $[d_{i}]\leftarrow{\sf B2A}([d_{i}]_{1})$; $[z_{l-1}]=[d_{l-1}]$;
$i=m+1,\ldots,l-2$ in parallel $[z_{i}]=[d_{i}]-[d_{i+1}]$;
$[z_{m}]=1-[d_{m+1}]$; $i=0,\ldots,m-1$ in parallel
$[u_{i}]\leftarrow\sum^{l-1-m+i}_{j=i}[z_{j+m-i}]\cdot[c_{j}]$;
$i=1,\ldots,\beta-2$ $[v_{i}]=\sum^{w-1}_{j=0}[u_{j+(i-1)w}]\cdot 2^{j}$;
$[v_{\beta-1}]=\sum_{i=w(\beta-2)}^{m-1}[u_{i}]\cdot 2^{i-w(\beta-2)}$;
$[z_{m}]\leftarrow[z_{m}]\cdot[c_{m}]$;
$[p]=\sum^{l-m-1}_{i=0}i\cdot[z_{i+m}]$
$\langle[b],[v_{\beta-1}],\ldots,[v_{1}],[p]\rangle$;

The protocol is given as Algorithm 1.3 and proceeds as follows. The first
portion of the computation is concerned with assembling the input blocks as a
single integer and consequently determining the first non-zero bit. A
complicating factor is that different blocks can have different signs, which
makes it non-trivial to work at the level of individual blocks. Therefore, the
first step of the computation is to convert the shares of the input blocks
from the ring with $k=2w$-bit elements to longer $l=w\beta$-bit elements
(lines 2–4). The blocks are consequently added together as $[s]_{l}$ (line 5)
and the absolute value of $[s]_{l}$ is computed as $[v]_{l}$ (lines 6–7). We
next bit-decompose the computed value (line 8) and from this point on the
computation can return to shorter $k$-bit shares, but we additionally optimize
the computation to skip immediate conversion of bits to $k$-bit shares and run
the next step on bit shares as well.

Given the bits of the value we need to normalize, we determine the first non-
zero bit and grab the next $m$ bits (as the $(m+1)$st bit is 1 and is
implicit). If there are fewer than $m+1$ non-zero bits, the value must
correspond to the lowest blocks of the superaccumulator (as otherwise, the
$w\beta$ bits are guaranteed to contain $m+1$ non-zero bits) and cannot be
represented in the properly normalized form. In that case we store the $m$
least significant bits in the mantissa and the floating-point value’s exponent
will be 0. Thus, we first call the prefix OR operation on the most significant
$l-m-2$ bits (line 9) and compute the difference between the adjacent bits. As
a result, the most significant non-zero bit of $v$ will be set to 1 in
$[z_{i}]$s, with all others set to 0 (lines 16–19). If the first non-zero bit
is at position $m$ (when counting from 0) or a lower index, $z_{m}$ is set to
1 to permit retrieval of $m$ least significant bits (line 20). Then the $m$
bits after the marked bit are extracted (lines 21–23) and are stored in
$\beta-1$ blocks (lines 24–27).

What remains is to form the exponent based on the position of the first non-
zero bit. This time we need to distinguish between normalized $(m+1)$-bit
mantissas that start from position $m$ and mantissas with fewer than $m+1$
non-zero bits. For that reason, we update the bit $[z_{m}]$ (line 28) prior to
computing the exponent $[p]$ (line 29).


# Inequality indices for heterogeneous systems: a tool for failure prediction

Tarun Ram Kanuri 1,∗, Subhadeep Roy 2, Soumyajyoti Biswas 1 1 Department of
Physics, SRM University - AP, Andhra Pradesh 522240, India.
2 Department of Physics, BITS Pilani Hyderabad Campus, Secunderabad, Telangana
500078, India<EMAIL_ADDRESS><EMAIL_ADDRESS>pilani.ac.in<EMAIL_ADDRESS>
###### Abstract

We have numerically studied a mean-field fiber bundle model of fracture at a
non-zero temperature and acted by a constant external tensile stress. The
individual fibers fail (local damage) due to creep-like dynamics that lead up
to a catastrophic breakdown (global failure). We quantify the variations in
sizes of the resulting avalanches by calculating the Lorenz function and two
inequality indices – Gini ($g$) and Kolkata ($k$) indices – derived from the
Lorenz function. We show that the two indices cross just prior to the failure
point when the dynamics goes through intermittent avalanches. For a continuous
failure dynamics (finite numbers of fibers breaking at each time step), the
crossing does not happen. However, in that phase, the usual prediction method
i.e., linear relation between the time of minimum strain-rate and failure
time, holds. The boundary between continuous and intermittent dynamics is very
close to the boundary between crossing and non-crossing of the two indices in
the temperature-stress phase space.

###### pacs:

64.60.av

##  I Introduction

Failure process in disordered solids hr90  depends on environment, such as
pressure, temperature; driving condition such as applied stress, strain rate;
as well as structural or material properties such as defects, micro-cracks,
plasticity, etc. One important scenario in this regard is that a material can
break with time even if a constant stress, less than the critical value is
applied on it - a phenomena widely know as the creep nhgs05 ; nhgs05a ; scirep
in the material science community. Especially, the creep process shows a
remarkable change as the temperature is tuned due to the temperature-dependent
dislocation motion, which becomes even easier when the thermal fluctuation is
higher. A detailed study of the creep failure giving an estimation of creep
time is very crucial for damage control regarding foundations like bridges,
building blocks and other constructions where the material in constantly under
an external load. Apart from the obvious effect of temperature on the creep
process, structural randomness and heterogeneity also plays an important role
as the creep takes place with the accumulation of plastic strain and damages
with time. The difficultly of handling the creep in heterogeneous solids leads
to other approaches, i.e, sub-critical crack growth dynamics m00  and
phenomenological Voight’s model for precursory strain v89 , where a time-
dependent strain similar to experiments are observed assuming a heterogeneous
feedback system.

For the present work, we will adopt a fiber bundle model hansen15_book , which
is a statistical model lead by threshold activated dynamics rc85 . The model
is simple yet very powerful to simulate failure dynamics under different
scenarios including a time-dependent creep process. Some studies considered
fluctuation in applied stress in form of thermal fluctuation cgs01 . In some
studies, the failure events are assumed to be probabilistic and not
deterministic in presence of a finite temperature pcc13 . Other studies
involve complex rheological properties that depend on specific rheological
properties of fibers. For instance, the Kelvin-Voigt rheology hkh02 ; kmhh03 ,
a nonlocal rheology j11  or a damage rheology for each fiber dk13 . Here, we
consider a ELS fiber bundle model but at a constant temperature instead. A
non-zero temperature will add an extra source of fluctuation, the thermal one,
in addition to the fluctuation in local strength we already have among the
fibers. Though FBM has shown athermal creep rh18  when the applied stress is
closer to the critical value, a finite temperature makes the rupture events
probabilistic, making the failure process reminiscent of a thermal creep
failure where a material can break under any stress no matter how low it is.
Such a probabilistic approach has been reported in the in the literature
exploring a time-dependent relaxation dynamics rh20 . For the present paper,
we want to combine the probabilistic approach in FBM to mimic creep with the
inequality indices obtain from a generic form of the Lorenz function lorenz05
to predict an upcoming catastrophic failure.

Figure 1: The figure shows the variation of Gini index $g$ and Kolkata index
$k$ as a function of temperature $T$ and $\sigma=0.2$, 0.3, 0.4, and 0.5.
$g$-index and $k$-index compete with each other and becomes equal at 0.87. The
threshold distribution is a delta function at 1.0.

Lorenz function $L(p)$ has been introduced in the context of wealth
distribution and represents cumulative wealth fraction possessed by the $p$
fraction of the population. For poorest and richest the $L(p)$ function takes
the form $0$ and $1$ respectively; $L(p)=p$ being the line of equality,
showing equal distribution of wealth. The two most popular equality index in
this context are as follows: (i) Gini index (g) gini21 : $g=0$ corresponds to
perfect equality, $g=0$ for extreme inequality and (ii) Kolkata index (k)
ghosh14 : $k=1/2$ corresponds to perfect equality, $g=1$ for extreme
inequality. We get $g=k$, as per the law old Pareto pareto71  at an extremely
competitive situation between equality and inequality. In the present paper,
we have used the same framework by replacing wealth by the avalanches during a
failure process, where an avalanche of size $s$ can occur with a probability
$p$.

##  II Model Description

Numerically, we have studied a mean-field fiber bundle model (FBM)
hansen15_book  at a non-zero temperature with an external load applied on it.
A conventional FBM consists of a bunch (say $L$) of vertical fibers attached
between two parallel bars (in case of 1d) or plates (in case of 2d), which are
pulled apart with an external force $F$ creating a stress $\sigma(=F/L)$ on
each fiber. The disorder is introduced in the model through the fluctuation in
strength from fiber to fiber. This is done by choosing the threshold stress of
each fiber randomly from a distribution. For the present work, we have chosen
both the Uniform and the Weibull distribution given as follows:

$\rho(x)=\begin{cases}\displaystyle\frac{1}{2\Delta}\ \text{for}\ 1-\Delta\leq
x\leq 1+\Delta,\\\ 0\ \text{elsewhere}\end{cases}$ (1)
$\rho(x)=\displaystyle\frac{k}{\lambda}\left(\displaystyle\frac{x}{\lambda}\right)^{k-1}e^{(-x/\lambda)^{k}}$
(2)

In case of the Uniform distribution, the span $\Delta$ of the distribution is
the measure of disorder while for Weibull, the disorder strength is tuned by
varying the shape ($k$) and scale parameter ($\lambda$).

Figure 2: The figure shows the number of zeros versus the temperature for
$\sigma=0.2$ and a delta-distribution. As $T$ increases, we observe a decrease
in the number of zeros and finally they saturates at a low value at high
temperature.

Figure 3: The figure shows the variation of Gini index $g$ and Kolkata index
$k$ as a function of temperature $T$ and $\sigma=0.3$. As a threshold
distribution, we have used a uniform distribution spanning from $1-\Delta$ to
$1+\Delta$. The disorder strength $\Delta$ is set to be 0.3, 0.4, 0.5, and
0.6. $\mu$ and $\sigma_{c}$ are respectively the mean strength and the
critical stress for quasi-static lading. $g$-index and $k$-index compete with
each other and becomes equal at 0.87.

Once the external stress crosses the threshold value for a certain fiber, that
fiber breaks irreversibly and the stress carried by the broken fiber is
redistributed among the rest of the model. In this paper, we adopted a equal-
load sharing (ELS) scheme p26  where the stress after each rupture is
redistributed equally among all surviving fibers. This is also the mean-field
limit of the model. Apart from ELS scheme there are other redistribution
schemes that has been explored in the context of FBM: (i) local load sharing
(LLS) scheme p79  where the stress is redistributed among the nearest
neighbours only, (ii) mixed mode redistribution pch05  where the stress
redistribution depends on how far a fiber is from the broken one, etc.

As mentioned in the introduction, inclusion of temperature makes the rupture
events probabilistic depending on the temperature as well as applied stress:

$P(\sigma,T)=\frac{\sigma}{\sigma_{c}}exp\left[-\frac{1}{T}\left(\frac{\sigma_{c}}{\sigma}-1\right)\right]$
(3)

where, $\sigma$ and $\sigma_{c}$ are respectively the local stress and
threshold stress of a fiber. $\sigma_{c}$ is either set to be either 1 (equal
for all fibers) or chosen from a random distribution (say Uniform or Weibull).
Due to such a probabilistic approach, a fiber can break even when
$\sigma<\sigma_{c}$. The relaxation dynamics of the model goes as follows:

  1. 1.

At each time we chose a probability $P_{i}(\sigma,T)$ for a fiber $i$ and
compare it with a random number $r$ chosen with uniform probability between 0
and 1.

  2. 2.

A fiber breaks irreversibly if $P_{i}(\sigma,T)>r$ and the stress of the fiber
is redistributed equally among all other surviving fibers increasing the value
of $\sigma$ and hence the probability $P$ (see Eq.3).

  3. 3.

In the next time step we chose another $P$ depending on temperature $T$ and
the updated local stress $\sigma$ and repeat the previous step.

  4. 4.

This process goes on until all fibers are broken suggesting global failure.

We want to stress the following point here. For $T=0$, $P(\sigma,T)$ in
equation 3 becomes zero suggesting no fibers will break unless
$\sigma\approx\sigma_{c}$.

##  III Analysis

Consider an equal load sharing FBM, where all fibers have the same failure
threshold $\sigma_{c}$. There is an external noise $T$. Now, under a load
$\sigma$, a fiber will break if $\sigma\geq\sigma_{c}$. But even when
$\sigma<\sigma_{c}$, the fiber can break with a probability given by Eq.3.

Now, if a time step $t$ is defined as one step of load redistribution, then
the fraction of surviving fibers is given by

$U(t,\sigma,\sigma_{c},T)=\frac{\sigma
T}{\sigma_{c}}ln\left[\frac{\tau-t}{Texp(-1/T)}+1\right],$ (4)

where $\tau$ is the failure time of the system, given by

$\tau=Texp\left(-\frac{1}{T}\right)\left[exp\left(\frac{\sigma_{c}}{\sigma
T}\right)-1\right].$ (5)

The magnitude of an avalanche, defined as the number of fibers failing in one
time step, is then

$\displaystyle S(t)=\left|\frac{dU}{dt}\right|=\frac{\sigma
T}{\sigma_{c}}\frac{1}{(\tau-t)+Texp(-1/T)}.$ (6)

The Lorenz function is then

$L(p)=\frac{\int\limits_{0}^{p\tau}S(t)dt}{\int\limits_{0}^{\tau}S(t)dt}.$ (7)

This on simplification gives,

$L(p)=\frac{ln\left|Texp(-1/T)+\tau\right|-ln\left|Texp(-1/T)+(1-p)\tau\right|}{ln\left|Texp(-1/T)+\tau\right|-ln\left|Texp(-1/T)\right|}$
(8)

The value of the Gini index $g$ at the failure point can be calculated from

$g_{f}=1-2\int\limits_{0}^{1}L(p)dp.$ (9)

This on simplification gives

$g=1+2\left[exp\left(1-\frac{\sigma_{c}}{\sigma
T}\right)-\frac{1}{ln\left(1+exp\left(\frac{\sigma_{c}}{\sigma
T}\right)-1\right)}\right].$ (10)

The value of the Kolkata index ($k$) at the failure point can be obtained from

$1-k=L(k),$ (11)

which needs to be numerically solved.

##  IV Numerical Results

In this section, we will discuss the numerical results that will build towards
the discussion as well as the main finding of the present article. As already
mentioned in the Model Description section, the numerical simulation is done
for a mean field fiber bundle model with system size $10^{5}$ and $10^{4}$
realizations. For the first part of the numerical results, we have considered
that all fibers have the same breaking threshold equals to unity while in the
later part Uniform and Weibull distributions are considered.

Figure 1 the variation of the Gini index and Kolkata index as we vary the
external temperature, which tunes the strength of the thermal fluctuation. The
distribution of the threshold values are chosen from a $delta$ function with
it’s peak at 0.5. Due to the choice of the distribution, the fluctuation among
the local threshold values is eliminated. Though, this does not eliminate the
thermal fluctuation (equation 3) and the rupture events are still
probabilistic and not deterministic. The model is observed under four
different external stress values: 0.2, 0.3, 0.4 and 0.5. The points
corresponds to the numerical results for a $\delta$-distribution at 0.5. The
dotted lines on the other hand is the comparison of the numerical results with
our analytically observed g-index and k-index. The behavior can be divided in
two different regions:

  * •

Region I: This region is observed at a higher temperature where the thermal
fluctuation is sufficiently large. We observe the Gini index here to be less
than the $k$-index. Such behavior is evident through both analytical results
as well as numerical data.

  * •

Region II: This region takes place where the temperature is low and hence the
thermal fluctuation is much less. The fiber rupture events are almost
deterministic here since the probabilistic element is negligible due to this
very small temperature. Here the $g-$index overcomes $k-$index and becomes
larger.

Figure 4: Boundaries showing the separation of Region I and Region II.
Boundary 1 is drawn from the direct comparison of $g-$index and $k-$index.
Boundary 2 is drawn where the number of zeroes disappears from the system
dynamics.

Figure 5: The figure shows the variation of Gini index $g$ and Kolkata index
$k$ as a function of temperature $T$ and $\sigma=0.3$. As a threshold
distribution, we have used a Weibull distribution of scale parameter $\lambda$
and shape parameter $k$. $\mu$ and $\sigma_{c}$ are respectively the mean and
the critical stress for quasi-static lading. $g$-index and $k$-index compete
with each other and becomes equal at 0.87. .

As $\sigma$ increases, we observe the crossover between region I and region II
starts to take place at a lower temperature. Lets call this point $T^{\ast}$.
We observe $T^{\ast}\approx 0.38$ for $\sigma=0.2$ while for $\sigma=0.5$, we
get $T^{\ast}\approx 0.15$. Though $T^{\ast}$ changes with $\sigma$, the
crossover takes place for $g=k=0.87$ irrespective of the value of external
stress. This universal value has been observed earlier in the context of other
statistical systems as well, like Bak-Tang-Wiesenfeld (BTW) bcw87 , Manna
model m91 , Edwards-Wilkinson (EW) ew82 , interface dynamics based on fiber
bundle model bc13 , etc.

Next we turn to find another way to understand the crossover point when $g$
becomes more than $k$. Since the dynamics of the model is lead by the thermal
fluctuation, the probability that a certain fiber will break decreases as we
go to lower temperature or lower applied stress. Which means, at lower $T$ and
$\sigma$, there will be many time steps in-between where no rupture events
happen. We call this the zeroes of the model evolution. Figure 2 shows the
number of zeroes as a function of temperature when the external stress is kept
at $\sigma=0.2$. For low $T$ there are many zeroes observed while it decreases
and becomes gradually 0 after a certain temperature (say $T^{\prime}$). Figure
3 shows the same result as figure 1 but for a uniform distribution spanning
between $1-\Delta$ to $1+\Delta$, $\Delta$ being the strength of disorder.
Since the analysis becomes complicated due the fluctuation of strength from
fiber to fiber (since its a distribution now instead of a delta-function). To
chose a certain $\sigma_{c}$ in equation 10 and 11, we adopted the following
assumptions: (i) since its a uniform distribution, we can assume the mean
($\mu$) to be the critical value; (ii) we can drive the system in a quasi-
static manner at zero temperature and found out the average critical stress
and use it.

In figure 3, we have kept the same external stress $\sigma=0.3$ but changed
the width of the uniform distribution, and hence the strength of disorder. We
observe a far better fit for $g-$index (equation 10) and $k-$index (equation
11) when we consider $\sigma_{c}$ to be the critical stress for quasi-static
loading rather than the mean strength. Also, quality of such fit decays as we
go to higher disorder strength (high $\Delta$).

We want to argue here that, $T^{\ast}$ where $g$ becomes greater than $k$, and
$T^{\prime}$ where number of zeroes itself becomes 0 has the same values. We
will discuss this in details next. Figure 4 shows this boundary between Region
I and Region II, independently calculated from (i) intermittence behaviour of
the system (study of fraction of zeroes) and (ii) the interplay of $g$ and
$k$, respectively. The points corresponds to the numerical results found from
direct simulation. The solid lines, on the other hand, are drawn from the
following analytical approaches: (i) Boundary 1: This shows the ($\sigma,T$)
coordinates beyond which there are no zeroes in avalanches, suggesting that at
least one fiber will break at each time step. This is done by using the
analytical results from the paper by Pradhan et al pcc13 . (ii) Boundary 2:
This boundary consists of the coordinates below which $g$ overcomes $k$. This
boundary is obtained by numerically solving the equations 10 and 11. The
bottom line this these boundaries, Boundary 1 or Boundary 2, separates two
regions I and II where the method of failure prediction is vastly different.
Region I, is the area above the boundary which is accessible by increasing
either the temperature of the external stress. In this region, we observe
fiber ruptures at each and every time step. The usual linear relation between
the time of minimum strain-rate and failure time holds here and the prediction
of upcoming failure can be done through this relation. On the other hand, for
low $T$ and $\sigma$, we obtain Region II, where intermittent behavior is
observe during the rupture events and above linear relationship does not hold
good. However, in this region the failure point can be predicted from the the
competition of $g$ and $k$ index and the Gini index is observed to show higher
value than $k$-index just before the catastrophic failure.

Figure 5 finally shows the comparison of the analytical and numerical behavior
of $g$ and $k$ indices for a Weibull distribution of shape parameter $k$ and
scale parameter $\lambda$. This shows the same fact that the fitting is better
by considering the critical stress for a quasi-brittle loading rather than the
mean of the distribution. This strengthen our claim regarding the universality
of our results irrespective of the choice of the threshold distribution.

##  V Discussion

Under a constant load, which is less than the critical load of a disordered
solid, there are creep induced failures that lead to the eventual collapse of
the system in presence of external noise e.g., temperature. The fiber bundle
model of fracture reproduces essential features of such failure through a
simple mean-field dynamics.

Here we have shown that the resulting avalanches of the creep failure can be
quantified in terms of their variations in sizes. Particularly, a Lorenz
function for the avalanches under a constant load and temperature can be
analytically calculated for a delta-function threshold distribution with it’s
peak at 1. Consequently, the Gini ($g$) and Kolkata ($k$) indices can also be
derived (see Eq. (10) and (11)). Curiously, the time variations of $g$ and $k$
(cumulative measured of inequality until that time) cross each other just
prior to the failure for sufficiently low values of external load and thermal
noise that ensure an intermitten avalanche dynamics. For large load and/or
thermal noise, the avalanche dynamics become continuous, where such crossing
do not happen. In that region, however, the linear relation between the time
of strain-rate minimum and failure time is well maintained.

For wides distributions of failure thresholds, for example Weibull or uniform,
the observations are qualitatively similar (see Figs. 3, 5). However, the
analytical expression for such cases could be done by approximating the
threshold distribution by its smallest value (for narrow threshold
distributions) or the average value (for wide distributions).

In conclusion, for intermittent creep rupture dynamics, the variations in
sizes of the resulting avalanches grow with time and provide a very reliable
precursory signal for the imminent failure in a wide range of the temperature-
stress phase space, where traditional precursory indications do not work.

## References

  * (1) H. J. Herrmann and S. Roux, Statistical Models for the Fracture of Disordered Media, North-Holland, Amsterdam (1990).
  * (2) H. Nechad, A. Helmstetter, R. El Guerjouma, and D. Sornette, J. Mech. Phys. Solids 53, 1099 (2005).
  * (3) H. Nechad, A. Helmstetter, R. El Guerjouma, and D. Sornette, Phys. Rev. Lett. 94, 045501 (2005).
  * (4) S. Biswas, D. F. Castellanos, M. Zaiser, Sci. Rep. 10, 16910 (2020).
  * (5) I. G. Main, Geophys. J. Int. 142, 151 (2000).
  * (6) B. Voight, Science 243, 200 (1989).
  * (7) A. Hansen A, P. C. Hemmer, S. Pradhan. The Fibre Bundle Model. Germany: Wiley VCH (2015).
  * (8) P. Ray and B. K. Chakrabarti, Solid State Commun. 53, 477 (1985).
  * (9) S. Ciliberto, A. Guarino, and R. Scorretti, Physica D 158, 83 (2001).
  * (10) S. Pradhan, A. K. Chandra, and B. K. Chakrabarti, Phys. Rev. E 88, 012123, (2013).
  * (11) B. K. Chakrabarti, S. Biswas, S. Pradhan. Front Phys 8, 613392 (2021).
  * (12) R. C. Hidalgo, F. Kun, and H. J. Herrmann, Phys. Rev. E 65, 032502 (2002).
  * (13) F. Kun, Y. Moreno, R. C. Hidalgo, and H. J. Herrmann, Europhys. Lett. 63, 347 (2003).
  * (14) E. A. Jagla, Phys. Rev. E 83, 046119 (2011).
  * (15) Z. Danku and F. Kun, Sci. Rep. 3, 2688 (2013).
  * (16) S. Roy and T. Hatano, Phys. Rev. E 97, 062149 (2018).
  * (17) S. Roy and T. Hatano, Phys. Rev. Research 2, 023104 (2020).
  * (18) M. O. Lorenz, Publication of the American Statistical Association 9, 209219 (1905).
  * (19) C. Gini, Economics Journal 31, 124126 (1921).
  * (20) A. Ghosh, N. Chattopadhyay and B. K. Chakrabarti, Physica A: Statistical Mechanics and Applications 410, 3034 (2014).
  * (21) V. Pareto, A. N. Page, Translation of Manuale di economia politica (Manual of political economy), A.M. Kelley Publishing, New York (1971).
  * (22) T. Pierce, J. Text. Ind. 17, T355 (1926).
  * (23) S. L. Phoenix, Adv Appl Probab. 11, 153 (1979).
  * (24) S. Pradhan, B. K. Chakrabarti, and A. Hansen, Phys. Rev. E 71, 036149 (2005).
  * (25) P. Bak, C. Tang and K. Wiesenfeld, Phys. Rev. Lett. 59, 381 (1987).
  * (26) S. S. Manna, J. Phys. A: Math. Gen. 24, L363 (1991).
  * (27) S. F. Edwards, D. R. Wilkinson, Proc. R. Soc. Lond. A 381, 17 (1982).
  * (28) S. Biswas, B. K. Chakrabarti, Phys. Rev. E 88, 042112 (2013).


# A Left passage explorer model

Tomas Kojar

###### Abstract

This is a short note describing a model generalizing the Harmonic explorer [6]
that might be of interest and it is not intended for publication in a journal.
The conjectured continuous model should have the same left-passage probability
as $\mathrm{SLE}_{\kappa}$ but possibly be a different curve.

††for comments and questions please contact<EMAIL_ADDRESS>
##  1 Introduction

In the article [6], they constructed a model that converges to the SLE curve
for $\kappa=4$. Later in their work in [7], they showed that the chordal
contour lines of the discrete Gaussian free field converge to forms of SLE(4);
after proving a height gap result, they then used techniques developed in the
”toy” case of the harmonic explorer.
This note initially started in motivation of developing a family discrete
models for each $\kappa\in(0,4)$ each of which will converge to
$\mathrm{SLE}_{\kappa}$. So a natural move was to extend the harmonic explorer
model. There the key observable is the left passage probability of the
harmonic explorer path $\gamma$, namely the function
$h(z):=\mathbb{P}\left[\gamma\text{ passes to the left of}z\right]$ and this
function has nice analytical properties, namely it is a harmonic function that
is equal to $\pi$ on the right side of $\gamma$ and $0$ on the left.

### Acknowledgements:

I thank Ilya Binder for his help in defining the model.

##  2 The Left-Passage pde (LP-pde)

Schramm had developed in [5] a formula for the left passage probability for
$\mathrm{SLE}_{\kappa}$ for each $\kappa\in[0,8)$.

######  Theorem 2.1.

Let $\kappa\in[0,8)$, and let $z_{0}=x_{0}+i\,y_{0}\in\mathbb{H}$. Then the
trace $\gamma$ of chordal $\mathrm{SLE}_{\kappa}$ satisfies

$h(z_{0}):=\mathbb{P}\left[\gamma\hbox{ passes to the left of
}z_{0}\right]=\frac{1}{2}+\frac{\Gamma(4/\kappa)}{\sqrt{\pi}\,\Gamma\bigl{(}\frac{8-\kappa}{2\kappa}\bigr{)}}\,\frac{x_{0}}{y_{0}}\,F_{2,1}\Bigl{(}\frac{1}{2},\frac{4}{\kappa},\frac{3}{2},-\frac{x_{0}^{2}}{y_{0}^{2}}\Bigr{)}\,.$

, where $F_{2,1}$ is the hypergeometric function.

Similarly in [4, section 5], Lawler obtains a formula that is reminiscent of
the argument function from the harmonic explorer:

######  Theorem 2.2.

Let $h(z)$ again denote the probability that z is on the left side of the
$\mathrm{SLE}_{\kappa}$ path $\gamma(0,\infty)$, then [4, section 5]

$h(z)=\int^{arg(z)}\frac{1}{sin(\theta)^{2-\frac{8}{\kappa}}}d\theta.$

Using either this formula or starting with the ODEs derived in their proofs,
it is easy to show that the function
$f(arg(x+iy))=f(\theta)=\int^{\theta}_{0}\dfrac{1}{sin(s)^{2-\frac{8}{\kappa}}}\mathrm{d}s$
will satisfy the degenerate elliptic pde:

$2(\frac{4}{\kappa}-1)\frac{\partial f}{\partial y}+y\Delta
f=0\quad\Leftrightarrow\quad div(y^{\beta}\nabla u)=0,$ (LP-pde)

where $\beta:=2(\frac{4}{\kappa}-1)$. We see that in the case $\kappa=4$ we
obtain the harmonic function observable for the harmonic explorer. So starting
from here it is natural to study a generalized harmonic explorer built out of
the observable satisfying (LP-pde). (One should note that this pde doesn’t
satisfy conformal invariance for $\kappa\neq 4$ and so this fact probably will
show that this model has no relation with $\mathrm{SLE}_{\kappa}$).
The formulation of the harmonic explorer model and its the convergence to the
limit, is done studying the two-dimensional random walk $(R_{1},R_{2})$
studied in the domain $D\setminus\gamma[0,n]$ where $\gamma$ is the harmonic
explorer up to time $n$. So naturally, we study the diffusion corresponding to
the (LP-pde). Because of the degeneracy of the pde we need the following
Feynman-Kac theorem from [2].
They generally consider a time-dependent, degenerate-elliptic differential
operator defined by _unbounded_ coefficients $(a,b)$ on the half-space
$\mathbb{H}:=\mathbb{R}^{d-1}\times(0,\infty)$ with $d\geq 1$,

$\frac{1}{2}\sum_{i,j=1}^{d}x_{d}a_{ij}(t,x)v_{x_{i}x_{j}}(x)+\sum_{i=1}^{d}b_{i}(t,x)v_{x_{i}}(x),\quad(t,x)\in[0,\infty)\times\mathbb{H},$
(1)

and $a=(a_{ij})$, $b=(b_{i})$, and $v\in C^{2}(\overline{\mathbb{H}})$. In our
case $a_{ii}=2,a_{i,j}=0,i\neq j$ and $b_{1}=0,b_{2}=\beta$. So it satisfies
the list of assumptions in their ”assumptions 2.2”. So we get the
correspondence to the following degenerated SDE system

$\left\\{\begin{matrix}dX_{1,t}=2\sqrt{X_{2.t}}dW_{1,t}\\\
dX_{2,t}=2\sqrt{X_{2.t}}dW_{2,t}+\beta\mathrm{d}t\end{matrix}\right..$

By Itô and time change we get

$\left\\{\begin{matrix}dX_{1,t}=dW_{1,t}\\\
dX_{2,t}=dW_{2,t}+\frac{1}{X_{2,t}}\frac{\beta-1}{2}\mathrm{d}t\end{matrix}\right..$

So this a two dimensional tupple of (Brownian motion, Bessel process). For the
Brownian motion part the natural discretization is the random walk. For the
Bessel part we use the result in [1]. In that paper they consider a nearest
neighbor (NN) random walk, defined as follows: let $X_{0}=0,\
X_{1},X_{2},\ldots$ be a Markov chain with

$\displaystyle E_{i}:=$ $\displaystyle\mathbb{P}\left[(X_{n+1}=i+1\mid
X_{n}=i\right]=1-\mathbb{P}\left[X_{n+1}=i-1\mid X_{n}=i\right]$ (2)
$\displaystyle=$ $\displaystyle\left\\{\begin{array}[]{ll}1&{\rm if}\quad
i=0\\\ 1/2+p_{i}&{\rm if}\quad i=1,2,\ldots,\end{array}\right.$

where $-1/2\leq p_{i}\leq 1/2,\ i=1,2,\ldots$. In case $0<p_{i}\leq 1/2$ the
sequence $\\{X_{i}\\}$ describes the motion of a particle which starts at
zero, moves over the nonnegative integers and going away from 0 with a larger
probability than to the direction of 0. They take $p_{i}\sim B/4i$ with $B>0$
as $i\to\infty$. Then they show that in certain sense, this Markov chain is a
discrete analogue of continuous Bessel process and establish a strong
invariance principle between these two processes. In particular, consider
$Y_{\nu}(t),\,t\geq 0$, a Bessel process of order $\nu$, $Y_{\nu}(0)=0$, and
let $X_{n},\,n=0,1,2,\ldots$ be an NN random walk with $p_{0}=p_{1}=1/2$,

$p_{R}=\frac{(R-1)^{-2\nu}-R^{-2\nu}}{(R-1)^{-2\nu}-(R+1)^{-2\nu}}-\frac{1}{2},\qquad
R=2,3,\ldots$ (5)

One main result is a strong invariance principle concerning Bessel process and
NN random walk

######  Theorem 2.3.

On a suitable probability space they construct a Bessel process
$\\{Y_{\nu}(t),\,t\geq 0\\},$ $\nu>0$ and an NN random walk
$\\{X_{n},\,n=0,1,2,\ldots\\}$ with $p_{R}$ as in (5) such that for any
$\varepsilon>0$, as $n\to\infty$ we have

$Y_{\nu}(n)-X_{n}=O(n^{1/4+\varepsilon})\qquad{\rm a.s.}$ (6)

##  3 The LP-model

We consider lattice $\delta\mathbb{Z}^{2}\cap\mathbb{H}$ ,for some $\delta>0$,
and rectangle D with bottom side centered at the origin. We also include its
medial lattice, which in the figure below we colored its lines with dashed
lines and its vertices with black dots. Finally, for fixed boundary vertices
$v_{0},v_{end}$, we impose boundary conditions 0 (darkgray) and 1 (lightgray)
on separate segments of $\partial D=\partial_{0}D\sqcup\partial_{1}D$, see
figure 1 (dark-gray on left and light gray on the right respectively).

Figure 1: Entire rectangle D with boundary conditions

The model is similar to the harmonic explorer model in [6] with the exception
that we replace the two dimensional random walk on the hexagonal grid by
running a random walk along the x-coordinate and a discretization of the
Bessel process along the y-coordinate, which we denote by (R,B). In
particular, we assign to each vertex $w$ on the original lattice (black dots),
the value

$\mathfrak{h}_{n}(w):=\mathbb{P}_{w}[(R_{T_{D_{n}}},B_{T_{D_{n}}})\in\partial_{1}D_{n}],$

where $T_{D_{n}}$ is the exit time of (R,B) from domain
$D_{n}:=D\setminus\gamma[0,n]$, for path $\gamma$ as described below. The
exploration path $\gamma$ runs along the medial lattice from $v_{0}$ to
$v_{end}$. It moves in three posible directions: left, straight or right. We
will try to use similar notation as in [6, section 3.1] as much as possible
even though here the lattice is square and not triangular.

Figure 2: The first step of the path

First let $V_{0}$ the set of vertices in $\partial D$, $A^{-}$ the dark-
gray/negative-vertices in $V_{0}$ going from $v_{0}$ to $v_{end}$ but on the
left and $A^{+}$ the light-gray/positive ones on the right also going from
$v_{0}$ to $v_{end}$.
For the first-step we let $h_{0}:V_{0}\to\left\\{0,1\right\\}$ to be 0 on
$V_{0}\cap A^{-}:=\partial_{0}D$ and to be 1 on $V_{0}\cap
A^{+}:=\partial_{1}D$. On the original lattice we have two vertices $w_{0,L}$
and $w_{0,R}$ on the square containing $v_{0}$ (see figure 2). We let
$p_{0,L},p_{0,R}$ equal the value of the probabilities

$p_{0,L}:=\mathfrak{h}_{0}(w_{0,L})=\mathbb{P}_{w_{0,L}}[(R_{T_{D}},B_{T_{D}})\in\partial_{1}D]\text{
and
}p_{0,R}:=\mathfrak{h}_{0}(w_{0,R})=\mathbb{P}_{w_{0,R}}[(R_{T_{D}},B_{T_{D}})\in\partial_{1}D].$

This is the analogous step of considering the harmonic extension of $h_{0}$.
From here there are two possible variations.

### variation 1

If one could show that $p_{0,L}\leq p_{0,R}$, then as in the Harmonic explorer
we consider an iid sequence of $\left\\{X_{n}\right\\}_{n\geq 1}$ with uniform
distribution Unif([0,1]). Then we decide whether the path moves left,straight
or right depending on whether:

$X_{1}\leq p_{0,L},X_{1}\in(p_{0,L},p_{0,R})\text{ or }p_{0,R}\leq X_{1}.$

The statement $p_{0,L}\leq p_{0,R}$ is clear by a path-reflection/swapping
argument. Suppose there is a trajectory $G(k):=(B_{k},R_{k})_{k=0}^{T_{D}}$
with $G(0)=w_{0,L}$ that exits on the right side $\partial_{1}D$. Then a
different trajectory $\widetilde{G}(k)$ starting with
$\widetilde{G}(0)=w_{0,R}$ either exists through $\partial_{1}D$ earlier or is
forced to intersect with $G(k)$ at some point $\tau$ and from then on it is
identified with it till their exit at $\partial_{1}D$. Therefore, we have an
inclusion of paths.

### variation 2

We consider two independent sequences $\left\\{X_{n,L}\right\\}_{n\geq
1}$,$\left\\{X_{n,R}\right\\}_{n\geq 1}$ to be iid with uniform distribution
Unif([0,1]) to help us decide which of the three directions to pick. Then We
make our choice starting clockwise from $w_{0,L}$ i.e. by by first flipping
the $X_{1,L}$-coin. If $X_{1,L}\leq p_{0,L}$, we go left and if $X_{1,L}\geq
p_{0,L}$ we will move either straight or right of $w_{0,R}$. So next we flip
the second coin $X_{1,R}$ to help us i.e. if $X_{1,R}\leq p_{0,R}$ we move
left of $w_{0,R}$ and if $X_{1,R}\geq p_{0,R}$ we move right of it.

Figure 3: The first two steps of the path

After the first step is done, we extend the boundary to
$V_{1}:=V_{0}\cup\left\\{w_{0,L},w_{0,R}\right\\}$ and assign labels 0 or 1
depending on whether the path moved left, straight or right. We let
$D_{1}:=D\setminus\gamma[0,1]$ denote the new domain and
$\partial_{0}D_{1},\partial_{1}D_{1}$ its new labeled boundaries. For the next
steps we similarly decide whether to move on the left, straight or right by
using
$p_{2,i}:=\mathfrak{h}_{1}(w_{2,i})=\mathbb{P}_{w_{2},i}[(R_{T_{D_{1}}},B_{T_{D_{1}}})\in\partial_{1}D_{1}]$
for $i=L,R$.

##  4 Questions

Here are some questions

  1. 1.

If shown to converge to a continuous limit, this model might serve as a
counterexample of a model having having same left-passage probability as
$\mathrm{SLE}_{\kappa}$ but not being related to it or even having conformal
invariance.

  2. 2.

Continuing on the program in [7], it would be interesting to consider a
possible coupling of those continuous limits with the Generalized Gaussian
field whose covariance is the Green function for the divergence operator
$div(y^{\beta}\nabla u)$ (eg. see the fields studied in [3]).

  3. 3.

It would be interesting to further generalize this model to other 2d-discrete
processes such as for the discretization of two general Itô diffusions.

## References

  * [1] Endre Csáki, Antónia Földes, and Pál Révész.  Transient nearest neighbor random walk and bessel process.  Journal of Theoretical Probability, 22(4):992–1009, 2009.
  * [2] Paul Feehan and Camelia Pop.  On the martingale problem for degenerate-parabolic partial differential operators with unbounded coefficients and a mimicking theorem for ito processes.  Transactions of the American Mathematical Society, 367(11):7565–7593, 2015.
  * [3] Yu Gu and Jean-Christophe Mourrat.  On generalized gaussian free fields and stochastic homogenization.  Electronic Journal of Probability, 22:1–21, 2017.
  * [4] Gregory Lawler.  Conformal invariance and 2 statistical physics.  Bulletin of the American Mathematical Society, 46(1):35–54, 2009\.
  * [5] Oded Schramm.  A percolation formula.  Electronic Communications in Probability, 6:115–120, 2001.
  * [6] Oded Schramm and Scott Sheffield.  Harmonic explorer and its convergence to sle4.  The Annals of Probability, 33(6):2127–2148, 2005.
  * [7] Oded Schramm and Scott Sheffield.  Contour lines of the two-dimensional discrete gaussian free field.  Acta mathematica, 202(1):21–137, 2009.