# Constant-Round Linear-Broadcast
Secure Computation with Penalties

Takeshi Nakai1, Kazumasa Shinagawa2 3
1 Toyohashi University of Technology, Aichi, Japan
2 Ibaraki University, Ibaraki, Japan
3 National Institute of Advanced Industrial Science and Technology, Tokyo,
Japan

###### Abstract

It is known that Bitcoin enables achieving fairness in secure computation by
imposing monetary penalties on adversarial parties. This functionality is
called secure computation with penalties. Bentov and Kumaresan (Crypto 2014)
introduced the claim-or-refund functionality that can be implemented via
Bitcoin. They achieved secure computation with penalties with $O(n)$ rounds
and $O(n)$ broadcasts for any function, where $n$ is the number of parties.
After that, Kumaresan and Bentov (CCS 2014) showed a constant-round protocol.
Unfortunately, this protocol requires $O(n^{2})$ broadcasts. As far as we
know, no protocol achieves $O(1)$ rounds and $O(n)$ broadcasts based on
Bitcoin. This work accomplishes such efficiency in secure computation with
penalties. We first show a protocol in a slightly relaxed setting called
secure computation with non-equivalent penalties. This setting is the same as
secure computation with penalties except that every honest party receives more
than a predetermined amount of compensation, while the previous one requires
that every honest party receives the same amount of compensation. Namely, our
setting allows the compensations for honest parties to be non-equivalent.
Moreover, we present a technique to remove the non-equivalence of our protocol
without sacrificing efficiency. We then propose a new ideal functionality
called claim-refund-or-give that can be implemented via Bitcoin.

##  1 Introduction

###  1.1 Backgrounds

Secure computation enables distrustful parties to jointly compute a function
on their private inputs [1]. There are several notions of security, such as
privacy, correctness, independence of inputs, guaranteed output delivery, and
fairness. Fairness requires that at the end of a protocol, either all parties
learn the output value or none of them learn it. Namely, it guarantees that no
corrupted parties aborts the protocol, with only the aborting parties learning
the output value. Unfortunately, it is known that fairness cannot always be
achieved in the standard model if a majority of parties are corrupted [2].

There are works to circumvent the impossibility result by imposing monetary
penalties on aborting parties [3]. It prevents the aborting attack since a
corrupted party loses money when he/she aborts the protocol. The monetary
penalty mechanism can be implemented by decentralized cryptocurrencies, e.g.,
Bitcoin [4]. There is a line of research on constructing cryptographic
protocols using decentralized cryptocurrencies [5, 6, 7, 8, 9, 10, 11, 12, 13,
14, 15].

Back and Bentov [5] and Andrychowicz, Dziembowski, Malinowski, and Mazurek [6]
introduced secure computation on Bitcoin. They studied fair lottery protocols
that guarantee any aborting party learning the output is forced to pay
penalties to all other parties. After that, Bentov and Kumaresan [9]
formalized such a model of computation as secure computation with penalties.
In particular, they defined a claim-or-refund functionality
$\mathcal{F}^{*}_{\mathrm{CR}}$ that plays a crucial role in secure
computation with penalties. It enables a sender to send coins with a predicate
$\phi_{s,r}(\cdot)$ and a time period $\tau$ to a receiver. The receiver gets
the coins if he/she reveals a witness $w$ such as $\phi_{s,r}(w)=1$ in $\tau$,
and the sender gets back the coins if the receiver does not publish the
solution in $\tau$. They showed that secure computation with penalties can be
realized for any function in the
$(\mathcal{F}_{\mathrm{OT}},\mathcal{F}^{*}_{\mathrm{CR}})$-hybrid model,
where $\mathcal{F}_{\mathrm{OT}}$ is an ideal functionality of oblivious
transfer. Their protocol requires $O(n)$ rounds and $O(n)$ broadcasts, where
$n$ is the number of parties. Here, the number of broadcasts refers to the
number of transactions in Bitcoin. Kumaresan and Bentov [8] introduced an
ideal transaction functionality $\mathcal{F}^{*}_{\mathrm{ML}}$ and showed
that secure computation with penalties can be realized in the
$(\mathcal{F}_{\mathrm{OT}},\mathcal{F}^{*}_{\mathrm{ML}})$-hybrid model with
only $O(1)$ rounds.111Roughly speaking, $\mathcal{F}^{*}_{\mathrm{ML}}$ allows
multiple parties to lock their coins. Each party gets the coins back only if
he/she reveals a predetermined private witness. However, this protocol
requires $O(n^{2})$ broadcasts. To the best of our knowledge, there is no
protocol for secure computation with penalties on Bitcoin with $O(1)$ rounds
and $O(n)$ broadcasts.

###  1.2 Related works and the scope of this paper

Kumaresan, Moran, and Bentov [10] extended secure computation with penalties
to the reactive model that can also handle multistage functionalities, such as
Texas Holdem Poker. Also, they defined a new security model for the reactive
model and proposed a fair protocol in the reactive model. This paper focuses
on the single-stage (i.e., non-reactive) model following the same setting in
[9].

Kumaresan and Bentov [12] improved the efficiency of protocols by amortizing
the cost over multiple executions. Kumaresan, Vaikuntanathan, and Vasudevan
[13] reduced the script complexity of $\phi_{s,r}$. We focus on reducing the
number of rounds and the number of broadcasts.

There is an approach to combining covert security and monetary penalty. It
provides a mechanism for imposing financial penalties on parties whose
malicious behavior is detected [16, 17]. This paper focuses on the aborting
attack and does not deal with other malicious behaviors.

To realize monetary penalties, every party must pay deposit money at the
beginning of a protocol. There are works to reduce the deposit amount [14, 15]
since a large deposit amount may discourage parties from participating in the
protocol. In this paper, we also tackle to reduce the deposit amount.

There are several works [18, 19, 20, 15, 21] based on the model with stateful
contracts, e.g., Ethereum [22]. This model is stronger than our model since it
requires an advanced blockchain techniques beyond Bitcoin.

###  1.3 Our contributions

We introduce new functionality, secure computation with non-equivalent
penalties, which is a slightly relaxed model of secure computation with
penalties. It guarantees that each honest party is compensated with more than
a predetermined amount of coins, while secure computation with penalties
guarantees that every honest party is compensated for the same amount of
coins. That is, two honest parties may be compensated with different amounts
of coins, although they are at least a predetermined amount. We note that the
non-equivalent penalty also prevents the aborting attack since it is the same
with secure computation with penalties in that it imposes a monetary penalty
on the aborting parties.

See Table 1, which summarizes our contributions. We first show that secure
computation with non-equivalent penalties can be realized in the
$(\mathcal{F}_{\mathrm{OT}},\mathcal{F}^{*}_{\mathrm{CR}})$-hybrid model. Our
technical contribution is to propose a new fair reconstruction protocol, which
is a subprotocol of a secure computation protocol with (non-equivalent)
penalties, with $O(1)$ rounds and $O(n)$ broadcasts. As a result, we obtain a
secure computation protocol with non-equivalent penalties with $O(1)$ rounds
and $O(n)$ broadcasts by using our fair reconstruction protocol in the
Bentov–Kumaresan’s construction.

Although this protocol achieves a constant round, there are two issues to be
addressed. The first issue is to increase the deposit amount. While the
deposit amount of Bentov–Kumaresan’s protocol is $O(nq)$, our protocol
requires $O(n^{2}q)$, where $q$ is a parameter of the penalty amount. To solve
the first issue, we propose a technique to reduce the deposit by about
$1/(l+1)$ increasing the number of rounds by $2l$.

The second issue is the non-equivalence of compensations. While our protocol
achieves fairness, it is undesirable to force all parties to accept the
unfairness of the compensations. To solve the second issue, we propose a new
ideal functionality called claim-refund-or-give functionality, which is an
extension of $\mathcal{F}^{*}_{\mathrm{CR}}$, and show that it can be used to
construct a secure computation protocol with penalties, with $O(1)$ rounds and
$O(n)$ broadcasts.

###  1.4 Organization

The remaining part of this paper is organized as follows: In Section 2, we
introduce basic notations, a security model, and ideal functionalities.
Section 3 describes Bentov–Kumaresan’s protocol for secure computation with
penalties [9]. Section 4 introduces secure computation with non-equivalent
penalties and proposes a protocol for it with $O(1)$ rounds and $O(n)$
broadcasts. Section 5 shows a technique to reduce the deposit amount of our
protocol. Section 6 presents a technique for removing the non-equivalence of
compensation amounts from our protocol. We conclude this paper in Section 7.
(Sections 5–6 and the appendixes are newly added from the earlier version
[23].)

Table 1: Comparison of secure computation protocols with penalties: $n$ is the number of parties, and $q$ refers to a parameter of the penalty amount. |  $\\#$ of |  $\\#$ of | Deposit |
---|---|---|---|---
References | Rounds | Broadcasts | amount | Compensations
Bentov–Kumaresan [9] | $O(n)$ | $O(n)$ | $O(nq)$ | Equivalent
Kumaresan-Bentov [8] | $O(1)$ | $O(n^{2})$ | $O(nq)$ | Equivalent
This work (Sect. 4) | $O(1)$ | $O(n)$ | $O(n^{2}q)$ | Non-equivalent
This work (Sect. 6) | $O(1)$ | $O(n)$ | $O(n^{2}q)$ | Equivalent

##  2 Preliminaries

###  2.1 Basic notations

For any positive integer $i\in\mathbb{N}$, $[i]$ denotes the set of integers
$\\{1,\ldots,i\\}$. We denote by $n$ the number of parties in a protocol. We
denote by $H\subseteq[n]$ (resp. $C\subseteq[n]$) the set of honest (resp.
corrupted) parties. Since each party is either honest or corrupted, it must
hold $h+c=n$ for $h:=|H|$ and $c:=|C|$. We consider settings where $c<n$. We
denote by $k$ a security parameter. We assume that all parties are non-uniform
probabilistic polynomial-time algorithms in $k$.

###  2.2 Secure computation with coins

Bentov–Kumaresan [9] introduced a new secure computation model called secure
computation with coins (SCC) model. It is the same model as the standard model
except that entities (i.e., parties, adversaries, ideal functionalities, and
an environment) can deal with a non-standard entity called coins, which is an
atomic entity representing electronic money. Coins are assumed to be having
the following properties.

  * •

Coins cannot be duplicated and forged.

  * •

No multiple parties hold the same coin simultaneously.

  * •

Any parties can transfer their coins to other parties freely.

  * •

Each coin is perfectly indistinguishable from one another.

We use the notation ${\sf coins}(\cdot)$ to express the amount of coins. If a
party owning ${\sf coins}(x)$ receives ${\sf coins}(y)$ from another party,
then the party holds ${\sf coins}(x+y)$ as a result.

In the SCC model, some ideal functionalities can deal with coins. We call such
a functionality a special ideal functionality. These functionalities are
described with the superscript $*$, e.g., $\mathcal{F}^{*}_{\mathrm{xxx}}$. We
call an ideal functionality without handling coins a standard ideal
functionality. Our protocol is realized in the hybrid model where parties have
access to a standard functionality $\mathcal{F}_{\mathrm{OT}}$, which is the
ideal functionality for oblivious transfer, and a special ideal functionality
$\mathcal{F}^{*}_{\mathrm{CR}}$, described later.

The SCC model follows the real/ideal simulation paradigm as with the standard
secure computation model. Let
$\mathrm{IDEAL}_{\mathcal{F},\mathcal{S},\mathcal{Z}}(k,z)$ denote the output
of an environment $\mathcal{Z}$ in the ideal world for realizing an ideal
functionality $\mathcal{F}$, where $\mathcal{Z}$ (with an auxiliary input $z$)
is interacting with an ideal adversary $\mathcal{S}$ on security parameter
$k$. Let $\mathrm{HYBRID}^{\mathcal{G}}_{\pi,\mathcal{A},\mathcal{Z}}(k,z)$
denote the output of environment $\mathcal{Z}$ in the real (hybrid) world for
executing a hybrid protocol $\pi$ with an ideal functionality $\mathcal{G}$,
where $\mathcal{Z}$ is interacting with a real adversary $\mathcal{A}$. The
difference with the standard secure computation is that all entities (i.e.,
parties, adversaries, special ideal functionalities, and an environment) can
deal with coins: sending coins, storing coins, and receiving coins.

###### Definition 1

Let $\pi$ be a probabilistic polynomial-time protocol with $n$ parties, and
$\mathcal{F}$ be a probabilistic polynomial-time $n$-party (standard or
special) ideal functionality. We say that $\pi$ SCC realizes $\mathcal{F}$
with abort in the $\mathcal{G}$ hybrid model (where $\mathcal{G}$ is a
standard or special ideal functionality) if for every non-uniform
probabilistic polynomial-time adversary $\mathcal{A}$, there exists a non-
uniform probabilistic polynomial-time adversary $\mathcal{S}$ such that for
every non-uniform probabilistic polynomial-time environment $\mathcal{Z}$, two
families of probability distributions
$\\{\mathrm{IDEAL}_{\mathcal{F},\mathcal{S},\mathcal{Z}}(k,z)\\}_{k\in\mathbb{N},z\in\\{0,1\\}^{*}}$
and
$\\{\mathrm{HYBRID}^{\mathcal{G}}_{\pi,\mathcal{A},\mathcal{Z}}(k,z)\\}_{k\in\mathbb{N},z\in\\{0,1\\}^{*}}$
are computationally indistinguishable.

###  2.3 Special ideal functionalities

####  2.3.1 Claim-or-refund functionality $\mathcal{F}^{*}_{\mathrm{CR}}$

This functionality $\mathcal{F}^{*}_{\mathrm{CR}}$ [9] can be seen as an
analogue of puzzles with bounty. Roughly speaking, for a puzzle $\phi_{s,r}$
with coins submitted by a sender, a receiver gets the coins if and only if
he/she submits a solution $w$ of the puzzle (i.e., $\phi_{s,r}(w)=1$).
$\mathcal{F}^{*}_{\mathrm{CR}}$ consists of three phases: deposit, claim, and
refund. In the deposit phase, a sender $P_{s}$ sends to a receiver $P_{r}$
“conditional” coins together with a circuit $\phi_{s,r}$. The coins also have
a round number $\tau$ specified by the sender. In the claim phase, the
receiver $P_{r}$ claims to receive the coins. $P_{r}$ can receive the coins
only if he/she broadcasts the witness $w$ of $\phi_{s,r}$ (i.e.,
$\phi_{s,r}(w)=1$) in $\tau$. Note that the witness $w$ published in the claim
phase is made public to all parties. In the refund phase, if $P_{r}$ does not
claim in $\tau$, then the coins are refunded to the sender $P_{s}$. See
Functionality 1 for a formal description of
$\mathcal{F}^{*}_{\mathrm{CR}}$.222[24, 12] show how to realize
$\mathcal{F}^{*}_{\mathrm{CR}}$ using Bitcoin. At least one broadcast is
necessary to realize $\mathcal{F}^{*}_{\mathrm{CR}}$ on Bitcoin. Thus, the
number of calling $\mathcal{F}^{*}_{\mathrm{CR}}$ corresponds to the number of
broadcasts.

We call the message in the deposit phase a deposit transaction. We use the
following “arrow” notation to denote the deposit transaction for the sender
$P_{s}$ and the receiver $P_{r}$.

$\displaystyle
P_{s}\xrightarrow[\,\,\,\,\,\,\,\,\,c,\tau\,\,\,\,\,\,\,\,\,]{w}P_{r}$

After making an arrow from $P_{r}$ to $P_{s}$ as above (i.e., after the
deposit phase), $P_{r}$ can claim to receive ${\sf coins}(c)$ only if he/she
publishes the witness $w$ in round $\tau$. ${\sf coins}(c)$ is refunded back
to the original holder $P_{s}$ if $P_{r}$ does not publish $w$ in $\tau$.

####  2.3.2 Secure computation with penalties $\mathcal{F}^{*}_{f}$

This functionality $\mathcal{F}^{*}_{f}$ is the same as the standard secure
function evaluation except that aborting players are forced to pay penalties
[9]. In principle, it guarantees the following properties.

  * •

No honest party pays any penalty.

  * •

If a party aborts after learning the output value and does not tell the value
to the other parties, then every party who does not learn the value is
compensated with coins.

See Functionality 2 for a formal description of $\mathcal{F}^{*}_{f}$. The
parameters $q$ and $d$ specify the amounts of coins. At the beginning of the
protocol, each party submits ${\sf coins}(d)$ together with input $x_{i}$. If
a party aborts after learning the output and does not tell the value to the
other parties, then $\mathcal{F}^{*}_{f}$ gives ${\sf coins}(q)$ to every
party who does not learn the output as compensation. Then, it is important
note that the compensation amount is always $q$ for any parties.

$H$ is a set of honest parties and $H^{\prime}\subseteq H$ is a subset chosen
by $\mathcal{S}$, which represents parties who are compensated. At first
glance, it is somewhat strange that $\mathcal{S}$ chooses a subset of honest
parties. The reason why $H^{\prime}$ is needed is that there are two types of
aborting in secure computation with abort. The first one is that an adversary
aborts after obtaining the output and thus honest parties cannot obtain the
outputs. In this case, $\mathcal{S}$ chooses $H^{\prime}=H$ and all honest
parties are compensated with ${\sf coins}(q)$ although the output is stolen by
the adversary. The second one is that an adversary aborts before obtaining the
output so the protocol just terminates. In this case, $\mathcal{S}$ chooses
$H^{\prime}\subsetneq H$ (possibly empty) and the parties in $H^{\prime}$ are
compensated with ${\sf coins}(q)$.333$H^{\prime\prime}$ is required for a
technical reason in order to prove the security. See [9] for a detail. In
order to prove the security of our protocol, our new functionality follows the
same strategy.

###  2.4 Non-malleable secret sharing with public verifiability and public
reconstructibility

A non-malleable secret sharing scheme with public verifiability and public
reconstructibility (in short, pubNMSS) [9] is a variant of non-malleable
secret sharing scheme. The share algorithm of pubNMSS takes a secret $s$ as
input, generates “tag-token” pairs $({\sf Tag}_{i},{\sf
Token}_{i})_{i\in[n]}$, and outputs ${\sf Token}_{i}$ and $({\sf
Tag}_{1},\dots,{\sf Tag}_{n})$ to each party $P_{i}$. The parties can
reconstruct $s$ by collecting all $t$ tokens, where $t$ is a predetermined
threshold value. For all $i\in[n]$, the parties can verify if the published
${\sf Token}_{i}$ is valid with ${\sf Tag}_{i}$. The tag-token pairs have the
following properties.

  * •

All tags $({\sf Tag}_{1},\dots,{\sf Tag}_{n})$ leak no information about $s$.

  * •

Any sets of $t^{\prime}(<t)$ tokens leak no information about $s$.

  * •

For any $i\in[n]$, the adversary cannot generate ${\sf
Token}^{\prime}_{i}(\neq{\sf Token}_{i})$ such that $({\sf Tag}_{i},{\sf
Token}^{\prime}_{i})$ is a valid tag-token pair.

A pubNMSS scheme can be obtained from the honest-binding commitment, which can
be constructed from one-way functions [25]. Roughly speaking, the honest
binding commitment is a commitment that a malicious sender can decommit to any
value, which is known as the equivocation property.

${\sf Tag}_{i}$ is an (honest-binding) commitment that is computed by a secret
share $sh_{i}$ and a randomness $r_{i}$ as input, and ${\sf
Token}_{i}:=(sh_{i},r_{i})$. Namely, the parties can verify if the published
${\sf Token}^{\prime}_{i}=(sh^{\prime}_{i},r^{\prime}_{i})$ is valid by
comparing ${\sf Tag}_{i}$ and the commitment whose input is $sh^{\prime}_{i}$
and $r^{\prime}_{i}$. In the following discussions, this verification
corresponds to $\phi_{s,r}$ in $\mathcal{F}^{*}_{\mathrm{CR}}$ executions.

Functionality 1 Claim-or-refund functionality $\mathcal{F}^{*}_{\mathrm{CR}}$

Setup:

The session identifier is $sid$. Running with parties $P_{1},\dots,P_{n}$ and
an ideal adversary $\mathcal{S}$.

Deposit phase:

Receiving $(\mathrm{deposit},sid,ssid,s,r,\phi_{s,r},\tau,{\sf coins}(c))$
from $P_{s}$, perform the following process.

  1. 1.

Record the message $(\mathrm{deposit},sid,ssid,s,r,\phi_{s,r},\tau,c)$

  2. 2.

Send all parties $(\mathrm{deposit},sid,ssid,s,r,\phi_{s,r},\tau,c)$

     * -

Ignore any future messages with the same $ssid$ from $P_{s}$ to $P_{r}$.

Claim phase:

Receiving $(\mathrm{claim},sid,ssid,s,r,\phi_{s,r},\tau,c,w)$ from $P_{r}$ in
round $\tau$, perform the following process.

  1. 1.

Check the two conditions:

     * -

$(\mathrm{deposit},sid,ssid,s,r,\phi_{s,r},\tau,c)$ was recorded,

     * -

$\phi_{s,r}(w)=1$.

  2. 2.

If both checks are passed, perform the following process:

    1. (a)

send $(\mathrm{claim},sid,ssid,s,r,\phi_{s,r},\tau,c,w)$ to all parties,

    2. (b)

send $(\mathrm{claim},sid,ssid,s,r,\phi_{s,r},\tau,{\sf coins}(c))$ to
$P_{r}$,

    3. (c)

delete the record $(\mathrm{deposit},sid,ssid,s,r,\phi_{s,r},\tau,c)$.

Refund phase:

In $\tau+1$, if the record $(\mathrm{deposit},sid,ssid,s,r,\phi_{s,r},\tau,c)$
was not deleted, then perform the following process:

  1. 1.

send $(\mathrm{refund},sid,ssid,s,r,\phi_{s,r},\tau,{\sf coins}(c))$ to
$P_{s}$,

  2. 2.

delete the record $(\mathrm{deposit},sid,ssid,s,r,\phi_{s,r},\tau,c)$.

Functionality 2 Secure computation with penalties $\mathcal{F}^{*}_{f}$

Setup:

The session identifier is $sid$. Running with parties $P_{1},\dots,P_{n}$, and
an ideal adversary $\mathcal{S}$ that corrupts parties $\\{P_{i}\\}_{i\in C}$.
Let $d$ be a parameter representing the safety deposit, and let $q$ denote the
penalty amount.

Input phase:

Wait to receive the following messages.

  * -

$(\mathrm{input},sid,ssid,i,x_{i},{\sf coins}(d))$ from $P_{i}$ for all $i\in
H$

  * -

$(\mathrm{input},sid,ssid,\\{y_{i}\\}_{i\in C},H^{\prime},{\sf
coins}(h^{\prime}q))$ from $\mathcal{S}$, where $H^{\prime}\subseteq H$ and
$h^{\prime}=|H^{\prime}|$

Output phase:

Perform the following process.

  1. 1.

Send $(\mathrm{return},sid,ssid,{\sf coins}(d))$ to each $P_{i}$ for $i\in H$.

  2. 2.

Compute $(y_{1},\dots,y_{n})\leftarrow f(x_{1},\dots,x_{n})$.

     * -

if $h^{\prime}=0$, then send message $(\mathrm{output},sid,ssid,y_{i})$ to
$P_{i}$ for $i\in H$, and terminate.

     * -

If $0<h^{\prime}<h$, then send $(\mathrm{extra},sid,ssid,{\sf coins}(q))$ to
$P_{i}$ for each $i\in H^{\prime}$, and terminate, where $h:=|H|$.

     * -

If $h^{\prime}=h$, then send message
$(\mathrm{output},sid,ssid,\\{y_{i}\\}_{i\in C})$ to $\mathcal{S}$.

  3. 3.

If $\mathcal{S}$ returns $(\mathrm{continue},sid,ssid,H^{\prime\prime})$,
where $H^{\prime\prime}\subseteq H$, then perform the following process:

    1. (a)

send $(\mathrm{output},sid,ssid,y_{i})$ to $P_{i}$ for all $i\in H$,

    2. (b)

send $(\mathrm{payback},sid,ssid,{\sf coins}((h-h^{\prime\prime})q))$ to
$\mathcal{S}$ where $h^{\prime\prime}=|H^{\prime\prime}|$,

    3. (c)

send $(\mathrm{extrapay},sid,ssid,{\sf coins}(q))$ to $P_{i}$ for each $i\in
H^{\prime\prime}$.

  4. 4.

Else if $\mathcal{S}$ returns $(\mathrm{abort},sid,ssid)$, send
$(\mathrm{penalty},sid,ssid,{\sf coins}(q))$ to $P_{i}$ for all $i\in H$.

##  3 Existing Protocol for Secure Computation with Penalties

In this section, we introduce Bentov–Kumaresan’s protocol [9] for secure
computation with penalties in the
$(\mathcal{F}_{\mathrm{OT}},\mathcal{F}^{*}_{\mathrm{CR}})$-hybrid model.

###  3.1 Bentov–Kumaresan’s protocol

For a function $f$, an augmented function denoted by $\hat{f}$ is defined by a
function that takes an input $x$ and distributes secret shares of the output
value $f(x)$. The underlying secret sharing scheme is non-malleable secret
sharing with publicly verifiability and publicly reconstructibility (Section
2.4), where the threshold value is $n$. Thus the augmented function $\hat{f}$
outputs a token ${\sf Token}_{i}$ (i.e., a share of $f(x)$) and a set of tags
$({\sf Tag}_{1},\dots,{\sf Tag}_{n})$ to party $P_{i}$.

Bentov–Kumaresan’s protocol proceeds as follows:

  1. (i)

The parties execute a secure computation protocol for $\hat{f}$, and then each
party $P_{i}$ obtains a token ${\sf Token}_{i}$ of $f(x)$ and a set of tags
$({\sf Tag}_{1},\dots,{\sf Tag}_{n})$. (Note that this is the standard
computation without Bitcoin).

  2. (ii)

For the reconstruction of tokens, the parties execute the fair reconstruction
protocol, where each party $P_{i}$ is forced to broadcast a token ${\sf
Token}_{i}$. The validity of the submitted token ${\sf Token}_{i}$ is verified
with the tag ${\sf Tag}_{i}$. (Note that this computation is based on
Bitcoin).

It is well known that the OT functionality $\mathcal{F}_{\mathrm{OT}}$ is
sufficient to achieve secure computation for any standard functionality [26,
27]. Moreover, this can be performed in constant rounds [27]. Therefore, the
secure computation stage (i) is performed in constant rounds in the
$\mathcal{F}_{\mathrm{OT}}$-hybrid model.

The main step of Bentov–Kumaresan’s protocol is the fair reconstruction
protocol (ii). By collecting all tokens, the parties can reconstruct the
output value $f(x)$. However, malicious parties may abort so as to learn the
output value while other parties do not. The fair reconstruction protocol
prevents parties from aborting in the reconstruction phase. When malicious
parties abort, they have to pay some amount of money for compensation to
honest parties. It satisfies the following conditions:

  1. (A)

No honest party pays any penalty.

  2. (B)

If an adversary learns the reconstruction result, but an honest party cannot,
then the honest party is compensated with coins. Furthermore, the compensation
amounts are the same for any honest parties.

Note that honest parties are not guaranteed to receive compensation if an
adversary aborts without learning the output value.

In summary, secure computation with penalties can be realized by executing a
secure computation protocol for $\hat{f}$ and the fair reconstruction
protocol. The next section shows Bentov–Kumaresan’s fair reconstruction
protocol in the $\mathcal{F}^{*}_{\mathrm{CR}}$-hybrid model.

###  3.2 Bentov–Kumaresan’s fair reconstruction protocol

Hereafter, we use $T_{i}$ to denote ${\sf Token}_{i}$. Suppose that each party
$P_{i}$ has a token $T_{i}$ and a set of tags $({\sf Tag}_{1},\dots,{\sf
Tag}_{n})$ at the beginning of the fair reconstruction protocol. We assume
that all parties agree on the penalty amount $q$, where honest parties are
compensated with ${\sf coins}(q)$ when malicious parties abort with obtaining
the output value. In the below, we successively explain a naïve approach, a
solution for the two-party setting, and a solution for the $n$-party setting.

#### Naïve approach

Suppose that the number of parties is two. A naïve approach is to make a
deposit transaction from $P_{1}$ to $P_{2}$ and a deposit transaction of the
reverse direction as follows:

$\displaystyle
P_{1}\xrightarrow[\,\,\,\,\,\,\,\,\,q,\tau\,\,\,\,\,\,\,\,\,]{T_{2}}P_{2}$ (1)
$\displaystyle
P_{2}\xrightarrow[\,\,\,\,\,\,\,\,\,q,\tau\,\,\,\,\,\,\,\,\,]{T_{1}}P_{1}$ (2)

The above arrow means that “$P_{2}$ can receive ${\sf coins}(q)$ only if
$P_{2}$ publishes the token $T_{2}$, otherwise ${\sf coins}(q)$ is refunded
back to $P_{1}$” (see Section 2.3). The bottom arrow is similar. At first
glance, it seems a fair reconstruction protocol satisfying conditions (A) and
(B) in Section 3.1. However, it is not the case. For instance, when $P_{2}$ is
malicious, $P_{2}$ can steal ${\sf coins}(q)$ from $P_{1}$ as follows: after
establishing transaction (1), $P_{2}$ publishes the token $T_{2}$ without
making transaction (2). As a result, honest $P_{1}$ loses ${\sf coins}(q)$.
This violates condition (A).

#### Bentov-Kumaresan’s solution

In order to avoid the above attack, Bentov–Kumaresan’s fair reconstruction
protocol for the two-party setting proceeds as follows:

$\displaystyle
P_{1}\xrightarrow[\,\,\,\,\,\,\,\,\,\,\,q,\tau_{2}\,\,\,\,\,\,\,\,\,\,\,]{T_{1}\wedge
T_{2}}P_{2}$ (1) $\displaystyle
P_{2}\xrightarrow[\,\,\,\,\,\,\,\,\,\,\,q,\tau_{1}\,\,\,\,\,\,\,\,\,\,\,]{T_{1}}P_{1}$
(2)

where the rounds satisfy $\tau_{1}<\tau_{2}$. (Hereafter, we assume
$\tau_{i}<\tau_{i+1}$ for any integer $i$.) $P_{1}$ first makes a deposit
transaction for $T_{1}\wedge T_{2}$. Transaction (1) means that $P_{2}$ can
receive ${\sf coins}(q)$ only if $P_{2}$ publishes both $T_{1}$ and $T_{2}$ in
$\tau_{2}$. Namely, it is necessary that both $({\sf Tag}_{1},T_{1})$ and
$({\sf Tag}_{2},T_{2})$ are valid tag-token pairs to satisfy
$\phi_{s,r}(T_{1}\wedge T_{2})=1$. After making the first deposit transaction,
$P_{2}$ makes a deposit transaction for $T_{1}$. Transaction (2) means that
$P_{1}$ can receive ${\sf coins}(q)$ only if $P_{1}$ publishes $T_{1}$ in
$\tau_{1}$. In the claim phase, $P_{1}$ first publishes $T_{1}$, and then
$P_{2}$ publishes both $T_{1}$ and $T_{2}$.

It is important to note that $P_{1}$ needs to make transaction (1) first. As a
result, $P_{2}$ cannot claim this transaction without making transaction (2)
since $P_{2}$ does not know $T_{1}$ yet. Also, the claims are performed in the
reverse order of making the transactions, i.e., $P_{1}$ first claims.

If $P_{2}$ aborts after $P_{1}$ claims, then $P_{2}$ is penalized with ${\sf
coins}(q)$ and $P_{1}$ is compensated with that coins. Thus, $P_{2}$ needs to
publish $T_{2}$ in order not to lose ${\sf coins}(q)$. Also, both parties
never are penalized if they behave honestly. Therefore, the above protocol
satisfies the conditions (A) and (B) in Section 3.1.

We show Bentov-Kumaresan’s solution for the $n$-party setting in Protocol 3.
In the deposit phase, the transactions are created from top to bottom, i.e.,
(1) to ($2n-2$). In the claim phase, the transactions are claimed in the
reverse direction, i.e., ($2n-2$) to (1). The horizontal lines separate each
round. Namely, in the deposit (resp. claim) phase, transactions belonging to
the same section are created (resp. claimed) in one round.

Here, we describe an intuitive explanation that Bentov-Kumaresan’s fair
reconstruction protocol satisfies the condition (A) and (B). (See [24] for a
formal security proof based on Definition 1.) It is trivial that no party
loses coins if all parties behave honestly. Thus, we consider the case where
there is a party to abort.

Let us consider the case where an adversary aborts in the deposit phase. Since
no honest party publishes his/her token, the adversary does not learn the
reconstruction result nor receives any coins from honest parties. This case
satisfies the condition (A) and (B).

Let us consider the case where an adversary aborts in the claim phase. In
order to learn the reconstruction result, the adversary must collude all
parties that have not claimed yet to learn tokens that are not published.
Every honest party holds ${\sf coins}(q)$ since he/she has already claimed and
has got coins. This case also satisfies the condition (A) and (B).

#### Efficiency

Bentov–Kumaresan’s fair reconstruction protocol requires $n$ rounds for
deposit phase and $n$ rounds for claim phase, and thus it requires a total of
$2n$ rounds. (See the left side of Figure 1 that shows a flow of the claim
phase of Bentov–Kumaresan’s fair reconstruction protocol.444For ease of
understanding, Figure 1 omits the transactions (among $P_{n}$ and other
parties) in the last round. (See transactions $(1),(2),\ldots,(n-1)$ in
Protocols 3 and 4.) This also holds for Figure 4.) Also, it requires $2n-2$
calls of $\mathcal{F}^{*}_{\mathrm{CR}}$. Recall that the augmented function
can be computed in a constant round for any function. Therefore, for any
function, Bentov–Kumaresan’s protocol for the secure computation with
penalties can be SCC realized in the
$(\mathcal{F}_{\mathrm{OT}},\mathcal{F}^{*}_{\mathrm{CR}})$-hybrid model with
$O(n)$ rounds and $O(n)$ calls of $\mathcal{F}^{*}_{\mathrm{CR}}$.

Protocol 3 Bentov–Kumaresan’s Fair Reconstruction Protocol $\displaystyle P_{1}\xrightarrow[\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,q,\tau_{n}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,]{T_{1}\wedge\dots\wedge T_{n}}P_{n}$ (1) $\displaystyle P_{2}\xrightarrow[\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,q,\tau_{n}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,]{T_{1}\wedge\dots\wedge T_{n}}P_{n}$ (2) $\displaystyle\vdots\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$ $\displaystyle P_{n-1}\xrightarrow[\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,q,\tau_{n}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,]{T_{1}\wedge\dots\wedge T_{n}}P_{n}$ ($n-1$) $\displaystyle P_{n}\xrightarrow[\,\,\,\,\,\,\,\,\,\,(n-1)q,\tau_{n-1}\,\,\,\,\,\,\,\,\,\,\,\,]{T_{1}\wedge\dots\wedge T_{n-1}}P_{n-1}$ ($n$) $\displaystyle P_{n-1}\xrightarrow[\,\,\,\,\,\,\,\,\,\,(n-2)q,\tau_{n-2}\,\,\,\,\,\,\,\,\,\,\,\,]{T_{1}\wedge\dots\wedge T_{n-2}}P_{n-2}$ ($n+1$) $\displaystyle\vdots\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$ $\displaystyle P_{4}\xrightarrow[\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,3q,\tau_{3}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,]{T_{1}\wedge T_{2}\wedge T_{3}}P_{3}$ ($2n-4$) $\displaystyle P_{3}\xrightarrow[\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,2q,\tau_{2}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,]{T_{1}\wedge T_{2}}P_{2}$ ($2n-3$) $\displaystyle P_{2}\xrightarrow[\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,q,\tau_{1}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,]{T_{1}}P_{1}$ ($2n-2$) Protocol 4 Our Fair Reconstruction Protocol $\displaystyle P_{1}\xrightarrow[\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,q,\tau_{4}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,]{T_{1}\wedge\dots\wedge T_{n}}P_{n}$ (1) $\displaystyle P_{2}\xrightarrow[\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,q,\tau_{4}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,]{T_{1}\wedge\dots\wedge T_{n}}P_{n}$ (2) $\displaystyle\vdots\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$ $\displaystyle P_{n-1}\xrightarrow[\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,q,\tau_{4}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,]{T_{1}\wedge\dots\wedge T_{n}}P_{n}$ ($n-1$) $\displaystyle P_{n}\xrightarrow[\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(n-1)q,\tau_{3}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,]{T_{1}\wedge\dots\wedge T_{n-1}}P_{n-1}$ ($n$) $\displaystyle P_{n-1}\xrightarrow[\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(n-1)q,\tau_{2}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,]{T_{n-1}\wedge T_{n-2}}P_{n-2}$ ($n+1$) $\displaystyle P_{n-1}\xrightarrow[\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(n-1)q,\tau_{2}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,]{T_{n-1}\wedge T_{n-3}}P_{n-3}$ ($n+2$) $\displaystyle\vdots\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$ $\displaystyle P_{n-1}\xrightarrow[\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(n-1)q,\tau_{2}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,]{T_{n-1}\wedge T_{1}}P_{1}$ ($2n-2$) $\displaystyle P_{n-2}\xrightarrow[\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(n-2)q,\tau_{1}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,]{T_{n-1}}P_{n-1}$ ($2n-1$) $\displaystyle P_{n-3}\xrightarrow[\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(n-2)q,\tau_{1}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,]{T_{n-1}}P_{n-1}$ ($2n$) $\displaystyle\vdots\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$ $\displaystyle P_{1}\xrightarrow[\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(n-2)q,\tau_{1}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,]{T_{n-1}}P_{n-1}$ ($3n-4$) Table 2: Comparison of fair reconstruction protocols References |  $\\#$ of Rounds |  $\\#$ of Calling $\mathcal{F}^{*}_{\mathrm{CR}}$ | Compensations
---|---|---|---
Bentov–Kumaresan [9] | $2n$ | $2n-2$ | Equivalent
This work (Sect. 4) | $8$ | $3n-4$ | Non-equivalent

##  4 Proposed Protocol

In this section, we introduce a special functionality called secure
computation with non-equivalent penalties (Section 4.1). Then we design a
protocol achieving this functionality in the
$(\mathcal{F}_{\mathrm{OT}},\mathcal{F}^{*}_{\mathrm{CR}})$-hybrid model. In
particular, we design a new fair reconstruction protocol in the
$\mathcal{F}^{*}_{\mathrm{CR}}$-hybrid model (Section 4.3), and putting it
with a secure computation protocol for an augmented function into the
$\mathcal{F}_{\mathrm{OT}}$-hybrid model as in Section 3.1. Notably, our
protocol requires $O(1)$ rounds and $O(n)$ broadcasts only (See Table 1).

###  4.1 Secure computation with non-equivalent penalties

In secure computation with penalties $\mathcal{F}^{*}_{f}$, all honest parties
are compensated with the same amount of money ${\sf coins}(q)$. A new
functionality, secure computation with penalties
$\mathcal{F}^{*}_{f,\mathrm{neq}}$, is the same as $\mathcal{F}^{*}_{f}$
except that each honest party is compensated with ${\sf coins}(q)$ or more,
i.e., the amount of compensation may be different with each party. For
example, in $\mathcal{F}^{*}_{f,\mathrm{neq}}$, we allow the following
situation: An honest $P_{1}$ is compensated with ${\sf coins}(q)$ but an
honest $P_{2}$ is compensated with ${\sf coins}(2q)$.

See Functionality 5 for a formal definition of
$\mathcal{F}^{*}_{f,\mathrm{neq}}$. The difference with $\mathcal{F}^{*}_{f}$
is that a simulator can decide the amount $q_{i}$ for each $i\in H^{\prime}$
and inputs ${\sf coins}(\sum_{i\in H^{\prime}}q_{i})$ while a simulator in
$\mathcal{F}^{*}_{f}$ must input ${\sf coins}(h^{\prime}q)$ for
$h^{\prime}:=|H^{\prime}|$. We require that $q_{i}\geq q$ for all $i\in
H^{\prime}$, where $q$ is the minimum amount of compensation.

We note that compensation happens only when a malicious party has stolen the
output value. That is, $\mathcal{F}^{*}_{f}$ and
$\mathcal{F}^{*}_{f,\mathrm{neq}}$ are the same if all parties behave
honestly. By choosing $q$ appropriately, it is possible to prevent malicious
behavior, and then we obtain a protocol with fairness. In this sense, a new
functionality $\mathcal{F}^{*}_{f,\mathrm{neq}}$ brings almost the same effect
on $\mathcal{F}^{*}_{f}$.

###  4.2 Fair reconstruction for secure computation with non-equivalent
penalties

Following Bentov-Kumaresan’s protocol, we construct a fair reconstruction
protocol to realize secure computation with non-equivalent penalties. In order
to realize secure computation with non-equivalent penalties, a fair
reconstruction protocol needs to satisfy the following conditions:

  * (A)

No honest party pays any penalty.

  * (B*)

If an adversary learns the reconstruction result, but an honest party cannot,
then the honest party is compensated with coins. Furthermore, the compensation
is more than a predetermined amount.

Note that the difference between condition (B*) and condition (B) in Section
3.1 is the amount of compensations only. Namely, our fair reconstruction
protocol does not guarantee that each honest party is compensated with the
same amount of coins.

###  4.3 Our fair reconstruction protocol

Our fair reconstruction protocol proceeds as follows (see also Protocol 4 that
shows the protocol expressed by using the arrow notation.)555Protocol 4 is
described based on the same rules as protocol 3. Namely, the transactions are
created from top to bottom and claimed in the reverse direction. The
horizontal lines separate each round.:

Deposit phase:

  1. 1.

For $i\in\\{1,\dots,n-1\\}$, $P_{i}$ makes a transaction to send $P_{n}$ ${\sf
coins}(q)$ with a predicate $\phi_{i,n}$ and a round number $\tau_{4}$, where
$\phi_{i,n}(x)=1$ only if $x=T_{1}\wedge\dots\wedge T_{n}$.

  2. 2.

$P_{n}$ makes a transaction to send $P_{n-1}$ ${\sf coins}((n-1)q)$ with a
predicate $\phi_{n,n-1}$ and a round number $\tau_{3}$, where
$\phi_{n,n-1}(x)=1$ only if $x=T_{1}\wedge\dots\wedge T_{n-1}$.

  3. 3.

For $i\in\\{1,\dots,n-2\\}$, $P_{n-1}$ makes a transaction to send $P_{i}$
${\sf coins}((n-1)q)$ with a predicate $\phi_{n-1,i}$ and a round number
$\tau_{2}$, where $\phi_{n-1,i}(x)=1$ only if $x=T_{n-1}\wedge T_{i}$.

  4. 4.

For $i\in\\{1,\dots,n-2\\}$, $P_{i}$ makes a transaction to send $P_{n-1}$
${\sf coins}((n-2)q)$ with a predicate $\phi_{i,n-1}$ and a round number
$\tau_{1}$, where $\phi_{i,n-1}(x)=1$ only if $x=T_{n-1}$.

Claim phase:

  1. 5.

$P_{n-1}$ claims by publishing $T_{n-1}$ in round $\tau_{1}$ and receives
${\sf coins}((n-2)q)$ from each of $P_{1},\dots,P_{n-2}$.

  2. 6.

For $i\in\\{1,\dots,n-2\\}$, $P_{i}$ claims by publishing $T_{n-1}\wedge
T_{i}$ in round $\tau_{2}$ and receives ${\sf coins}((n-1)q)$ from $P_{n-1}$.

  3. 7.

$P_{n-1}$ claims by publishing $T_{1}\wedge\dots\wedge T_{n-1}$ in round
$\tau_{3}$ and receives ${\sf coins}((n-1)q)$ from $P_{n}$.

  4. 8.

$P_{n}$ claims by publishing $T_{1}\wedge\dots\wedge T_{n}$ in round
$\tau_{4}$ and receives ${\sf coins}(q)$ from each of $P_{1},\dots,P_{n-1}$.

Our fair reconstruction protocol requires eight rounds and $3n-4$ calls of
$\mathcal{F}^{*}_{\mathrm{CR}}$. Since $\mathcal{F}_{\mathrm{OT}}$ is
sufficient to compute any standard functionality in constant rounds, we can
derive the following theorem.

###### Theorem 1

Assuming the existing of one-way functions, for every $n$-party functionality
$f$ there exists a protocol that SCC realizes
$\mathcal{F}^{*}_{f,\mathrm{neq}}$ in the
$(\mathcal{F}_{\mathrm{OT}},\mathcal{F}^{*}_{\mathrm{CR}})$-hybrid model. The
protocol requires $O(1)$ rounds and $O(n)$ calls of
$\mathcal{F}^{*}_{\mathrm{CR}}$.

###  4.4 Idea behind our protocol

See the right side of Figure 1 that shows a flow of the claim phase of our
fair reconstruction protocol. In Bentov–Kumaresan’s protocol, parties
publishes his/her token in serial order, i.e., each token is published in each
round. (Token $T_{i}$ is published in round $\tau_{i}$.) Thus, their protocol
requires $O(n)$ rounds.

On the other hand, our protocol enables to publish multiple tokens in one
round to improve the round complexity. See step 6) in Section 4.3, the parties
$P_{1},\dots,P_{n-2}$ publish their token in one round.

In the claim phase, our protocol proceeds as follows: We call
$P_{1},\dots,P_{n-2}$ middle parties and $P_{n-1}$ aggregator. In round
$\tau_{1}$, the aggregator $P_{n-1}$ collects coins from all middle parties by
publishing token $T_{n-1}$. After that, the middle parties publishes their
tokens $T_{1},\dots,T_{n-2}$ and receive coins, which are more than they sent
in round $\tau_{1}$, from the aggregator $P_{n-1}$ in round $\tau_{2}$. In
round $\tau_{3}$, the aggregator $P_{n-1}$ receives coins from $P_{n}$ by
publishing his/her token and all of middle parties’ tokens. In the last round
$\tau_{4}$, $P_{n}$ publishes the last token $T_{n}$ and receives coins from
every other party. As a result, all parties learn the reconstruction result
and every party’s wallet are balanced, i.e., it has neither loss nor gain.

We discuss the amount of coins sent in each transaction to satisfy the
conditions (A) and (B*) below.

#### The amount of coins

In our protocol, $P_{n}$ receives ${\sf coins}(q)$ from every other party in
the last round $\tau_{4}$. In order to satisfy the condition (A), every wallet
of $P_{1},\dots,P_{n-1}$ must hold ${\sf coins}(q)$ at the end of round
$\tau_{3}$. We show that our protocol satisfies this condition in Figure 2.

When we decide the amount of coins in rounds $\tau_{1}$ and $\tau_{2}$, we
should note that the aggregator $P_{n-1}$ cannot claim in round $\tau_{3}$ if
at least one of the middle parties abort in round $\tau_{2}$. Since the
aggregator sends more coins in round $\tau_{2}$ than he/she received in round
$\tau_{1}$, his/her wallet holds negative amount of coins at the end of round
$\tau_{2}$. In order to satisfy the conditions (A) and (B*), it is necessary
to satisfy that the aggregator’s wallet holds positive amount of coins at the
end of round $\tau_{2}$ if at least one of the middle parties abort in round
$\tau_{2}$. The amounts of coins sent in rounds $\tau_{1}$ and $\tau_{2}$ are
derived as follows.

Suppose that $P_{n-1}$ gets ${\sf coins}(xq)$ from each of
$P_{1},\dots,P_{n-2}$ in round $\tau_{1}$, and each of $P_{1},\dots,P_{n-2}$
get ${\sf coins}((x+1)q)$ from $P_{n-1}$ in round $\tau_{2}$. In round
$\tau_{2}$, $P_{n-1}$’s wallet should have positive amount of coins unless all
of $P_{1},\dots,P_{n-2}$ claims. Thus, we can derive $x$ from the following
equation: $(n-2)x>(n-3)(x+1)$. The least solution of the equation is $x=n-2$.
Therefore, each middle party sends ${\sf coins}((n-2)q)$ to the aggregator in
round $\tau_{1}$ and the aggregator sends ${\sf coins}((n-1)q)$ to each middle
party in round $\tau_{2}$.

#### Security intuition

Let us consider the case where one of the middle parties aborts in round
$\tau_{2}$. (See Figure 3.) Suppose that $P_{1}$ aborts in round $\tau_{2}$,
i.e., he/she does not publish $T_{1}$ and does not receive ${\sf
coins}((n-1)q)$ from $P_{n-1}$. Note that $P_{1}$ must collude with $P_{n}$ to
learn the reconstruction result. Thus, the condition (B*) is satisfied since
every wallet of $P_{2},\dots,P_{n-1}$ holds ${\sf coins}(q)$ as the
compensation at the end of the protocol. Furthermore, since no honest party
does not pay a penalty, the condition (A) is satisfied. We can confirm that
our protocol satisfies the conditions (A) and (B*) by the same way in the
other cases.

#### Remark 1

Compensations to honest parties may not be the same amount of coins. See
$P_{n-1}$ who receives ${\sf coins}((n-2)q)$ from each of
$P_{1},\dots,P_{n-2}$ in round $\tau_{1}$. The amount of $P_{n-1}$’s
compensation depends on the number of aborting parties in them. On the other
hand, compensations for other parties are ${\sf coins}(q)$. Namely, $P_{n-1}$
is the only party who can be compensated with more than ${\sf coins}(q)$.

#### Remark 2

At first glance, it seems that rounds $\tau_{3}$ and $\tau_{4}$ need not be
separated since $P_{n}$ can already claim in $\tau_{3}$. However, if these
rounds are combined into one (i.e., $\tau_{4}=\tau_{3}$), the modified
protocol violates condition (A). Suppose all but $P_{n}$ are malicious. First,
in the deposit phase, the adversary makes the $n-1$ transactions to $P_{n}$
honestly. However, after $P_{n}$ makes the deposit transaction to $P_{n-1}$,
the adversary waits for time to pass without making the subsequent
transactions. Just before the end of $\tau_{3}$, the adversary claims the
transaction made by $P_{n}$ and obtains ${\sf coins}((n-1)q)$. $P_{n-1}$ can
get that coins back by claiming $n-1$ transactions made by the adversary,
however $P_{n}$ may not claim due to the lack of time remaining. As a result,
$P_{n}$ may lose the coins, which violates the condition (A).

Functionality 5 Secure computation with non-equivalent penalties
$\mathcal{F}^{*}_{f,\mathrm{neq}}$

Setup

The session identifier is $sid$. Running with parties $P_{1},\dots,P_{n}$, and
an ideal adversary $\mathcal{S}$ that corrupts parties $\\{P_{i}\\}_{i\in C}$.
Let $d$ be a parameter representing the safety deposit. Let $q$ denote the
minimum penalty amount.

Input phase

Wait to receive the following messages.

  * -

$(\mathrm{input},sid,ssid,i,x_{i},{\sf coins}(d))$ from $P_{i}$ for all $i\in
H$

  * -

$(\mathrm{input},sid,ssid,\\{x_{i}\\}_{i\in C},H^{\prime},{\sf
coins}(\sum_{i\in H^{\prime}}q_{i}))$ from $\mathcal{S}$, where
$H^{\prime}\subseteq H$ and $q_{i}\,(\geq q)$ is the penalty amount for each
$i\in H^{\prime}$.

Output phase

Perform the following process.

  1. 1.

Send $(\mathrm{return},sid,ssid,{\sf coins}(d))$ to each $P_{r}$ for $r\in H$.

  2. 2.

Compute $(y_{1},\dots,y_{n})\leftarrow f(x_{1},\dots,x_{n})$.

     * -

if $h^{\prime}=0$, then send message $(\mathrm{output},sid,ssid,z_{r})$ to
$P_{r}$ for $r\in H$, and terminate.

     * -

If $0<h^{\prime}<h$, then send $(\mathrm{extra},sid,ssid,{\sf coins}(q_{i}))$
to $P_{i}$ for each $i\in H^{\prime}$, and terminate, where $h:=|H|$.

     * -

If $h^{\prime}=h$, then send message
$(\mathrm{output},sid,ssid,\\{y_{i}\\}_{i\in C})$ to $\mathcal{S}$.

  3. 3.

If $\mathcal{S}$ returns $(\mathrm{continue},sid,ssid,H^{\prime\prime})$,
where $H^{\prime\prime}\subseteq H$, then perform the following process:

    1. (a)

send $(\mathrm{output},sid,ssid,y_{i})$ to $P_{i}$ for all $i\in H$,

    2. (b)

send $(\mathrm{payback},sid,ssid,{\sf coins}(\sum_{i\in
H^{\prime}}q_{i}-\sum_{j\in H^{\prime\prime}}q_{j})$ to $\mathcal{S}$ where
$h^{\prime\prime}=|H^{\prime\prime}|$,

    3. (c)

send $(\mathrm{extrapay},sid,ssid,{\sf coins}(q_{i}))$ to $P_{i}$ for each
$i\in H^{\prime\prime}$.

  4. 4.

Else if $\mathcal{S}$ returns $(\mathrm{abort},sid,ssid)$, send
$(\mathrm{penalty},sid,ssid,{\sf coins}(q_{i}))$ to $P_{i}$ for each $i\in H$.

Figure 1: Flow of Bentov–Kumaresan’s fair reconstruction (left) and ours
(right)

Figure 2: Coins flow in round $\tau_{1}$ to $\tau_{3}$ in the case where all
parties behave honestly

Figure 3: Coins flow in round $\tau_{1}$ to $\tau_{2}$ in the case where
$P_{1}$ aborts

Figure 4: Our fair reconstruction in the case where $l=1$ (left) and $l=2$
(right)

##  5 Reducing Deposit Amount

This section focuses on the amount of coins required to run our protocol. Our
protocol requires larger deposits than Bentov-Kumaresan’s protocol. This
section shows a technique to reduce the deposit amount of our protocol.

###  5.1 Deposit amount

We first discuss the largest amount of coins for participation. In Bentov-
Kumaresan’s protocol, $P_{n}$ needs to deposit ${\sf coins}((n-1)q)$ to
$P_{n-1}$, which is the largest amount in all parties. Thus, he/she must hold
${\sf coins}((n-1)q)$ at the beginning of the protocol to participate in the
protocol.

On the other hand, in our protocol, $P_{n-1}$ needs to make deposit
transactions $(n-1)$ and $(n+1)$ to $(2n-2)$. Thus, he/she must hold the total
amount ${\sf coins}(((n-1)(n-2)+1)q)$ at the beginning of the protocol.
Although our protocol is efficient in terms of the round complexity, the
deposit amount increases from $O(nq)$ to $O(n^{2}q)$.

###  5.2 Reducing the deposit amount

We present a technique of reducing the deposit amount in our protocol. Our
technique can reduce $P_{n-1}$’s deposit to ${\sf
coins}(((n-1)(n-2)/(l+1)+1)q)$ instead of increasing the number of rounds by
$2l$. (Each of the deposit phase and the claim phase is increased by $l$
rounds.)

The reason for $P_{n-1}$’s large deposit is that he/she has to make deposit
transactions for all of the middle parties, i.e., $P_{1},\dots,P_{n-2}$. Our
main idea is to reduce the number of deposit transactions to the middle
parties from $P_{n-1}$. Figure 4 shows flows of our protocol applied the above
idea in the case of $l=1$ and $l=2$. (See also Protocol 6, which shows the
specific process in the case where $l=1$.) In order to reduce $P_{n-1}$’s
deposit, the middle parties make deposit transactions within them. For
instance, when $l=1$, the number of deposit transactions that $P_{n-1}$ makes
for the middle parties is halved instead of increasing the number of rounds by
two. As a result, $P_{n-1}$’s deposit is reduced to ${\sf
coins}((n-1)(n-2)/2+1)q)$. Similarly, when $l=2$, his/her deposit is reduced
to $1/3$ instead of increasing the number of rounds by four. We remark that
our technique can be applied even if $n-2$ is not divided by $l+1$ by having
one of the middle parties be responsible for multiple middle parties.

Protocol 6 Reducing the deposit amount (case of $l=1$) $\displaystyle
P_{1}\xrightarrow[\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,q,\tau_{5}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,]{T_{1}\wedge\dots\wedge
T_{n}}P_{n}$ (1)
$\displaystyle\vdots\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$
$\displaystyle
P_{n-1}\xrightarrow[\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,q,\tau_{5}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,]{T_{1}\wedge\dots\wedge
T_{n}}P_{n}$ ($n-1$) $\displaystyle
P_{n}\xrightarrow[\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(n-1)q,\tau_{4}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,]{T_{1}\wedge\dots\wedge
T_{n-1}}P_{n-1}$ ($n$) $\displaystyle
P_{n-1}\xrightarrow[\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(n-1)q,\tau_{3}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,]{T_{n-1}\wedge
T_{n-2}\wedge T_{n/2}}P_{n/2-1}$ ($n+1$)
$\displaystyle\vdots\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$
$\displaystyle
P_{n-1}\xrightarrow[\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(n-1)q,\tau_{3}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,]{T_{n-1}\wedge
T_{n/2+1}\wedge T_{1}}P_{1}$ ($3n/2-1$) $\displaystyle
P_{n/2-1}\xrightarrow[\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(n-2)q,\tau_{2}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,]{T_{n-1}\wedge
T_{n-2}}P_{n-2}$ ($3n/2$)
$\displaystyle\vdots\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$
$\displaystyle
P_{1}\xrightarrow[\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(n-2)q,\tau_{2}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,]{T_{n-1}\wedge
T_{n/2+1}}P_{n/2+1}$ ($2n-2$) $\displaystyle
P_{n-2}\xrightarrow[\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(n-3)q,\tau_{1}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,]{T_{n-1}}P_{n-1}$
($2n-1$)
$\displaystyle\vdots\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$
$\displaystyle
P_{n/2+1}\xrightarrow[\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(n-3)q,\tau_{1}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,]{T_{n-1}}P_{n-1}$
($5n/2-4$) Functionality 7 Claim-refund-or-give functionality
$\mathcal{F}^{*}_{\mathrm{CRG}}$

Setup:

The session identifier is $sid$. Running with parties $P_{1},\dots,P_{n}$ and
an ideal adversary $\mathcal{S}$.

Deposit phase:

Receiving
$(\mathrm{deposit},sid,ssid,s,r,\phi_{s,r},\phi_{\mathrm{refund}},\tau_{\mathrm{claim}},\tau_{\mathrm{refund}},{\sf
coins}(c))$ from $P_{s}$, and $\phi_{\mathrm{refund}}^{\prime}$ from $P_{r}$,
perform the following process.

  1. 1.

Check $\phi_{\mathrm{refund}}=\phi_{\mathrm{refund}}^{\prime}$ holds.

  2. 2.

Record the message
$(\mathrm{deposit},sid,ssid,s,r,\phi_{s,r},\phi_{\mathrm{refund}},\tau_{\mathrm{claim}},\tau_{\mathrm{refund}},c)$

  3. 3.

Send all parties
$(\mathrm{deposit},sid,ssid,s,r,\phi_{s,r},\phi_{\mathrm{refund}},\tau_{\mathrm{claim}},\tau_{\mathrm{refund}},c)$

     * -

Ignore any future messages with the same $ssid$ from $P_{s}$ to $P_{r}$.

Claim phase:

Receiving
$(\mathrm{claim},sid,ssid,s,r,\phi_{s,r},\phi_{\mathrm{refund}},\tau_{\mathrm{claim}},\tau_{\mathrm{refund}},c,w_{r})$
from $P_{r}$ in round $\tau_{\mathrm{claim}}$, perform the following process.

  1. 1.

Check that both
$(\mathrm{deposit},sid,ssid,s,r,\phi_{s,r},\phi_{\mathrm{refund}},\tau_{\mathrm{claim}},\tau_{\mathrm{refund}},c)$
was recorded, and $\phi_{s,r}(w_{r})=1$ hold.

  2. 2.

send
$(\mathrm{claim},sid,ssid,s,r,\phi_{s,r},\phi_{\mathrm{refund}},\tau_{\mathrm{claim}},\tau_{\mathrm{refund}},c,w_{r})$
to all parties, and
$(\mathrm{claim},sid,ssid,s,r,\phi_{s,r},\phi_{\mathrm{refund}},\tau_{\mathrm{claim}},\tau_{\mathrm{refund}},{\sf
coins}(c))$ to $P_{r}$,

  3. 3.

delete the record
$(\mathrm{deposit},sid,ssid,s,r,\phi_{s,r},\phi_{\mathrm{refund}},\tau_{\mathrm{claim}},\tau_{\mathrm{refund}},c)$.

Refund phase:

In $\tau_{\mathrm{claim}}+1$, if the record
$(\mathrm{deposit},sid,ssid,s,r,\phi_{s,r},\phi_{\mathrm{refund}},\tau_{\mathrm{claim}},\tau_{\mathrm{refund}},c)$
was not deleted and the message
$(\mathrm{refund},sid,ssid,s,r,\phi_{s,r},\phi_{\mathrm{refund}},\tau_{\mathrm{claim}},\tau_{\mathrm{refund}},c,w_{r})$
is received from $P_{r}$, then perform the following process:

  1. 1.

Check that both
$(\mathrm{deposit},sid,ssid,s,r,\phi_{s,r},\phi_{\mathrm{refund}},\tau_{\mathrm{claim}},\tau_{\mathrm{refund}},c)$
was recorded, and $\phi_{\mathrm{refund}}(w_{r})=1$ hold.

  2. 2.

Send
$(\mathrm{claim},sid,ssid,s,r,\phi_{s,r},\phi_{\mathrm{refund}},\tau_{\mathrm{claim}},\tau_{\mathrm{refund}},c,w_{s})$
to all parties, and
$(\mathrm{refund},sid,ssid,s,r,\phi_{s,r},\phi_{\mathrm{refund}},\tau_{\mathrm{claim}},\tau_{\mathrm{refund}},{\sf
coins}(c))$ to $P_{s}$.

  3. 3.

Delete the record
$(\mathrm{deposit},sid,ssid,s,r,\phi_{s,r},\phi_{\mathrm{refund}},\tau_{\mathrm{claim}},\tau_{\mathrm{refund}},c)$.

Give phase:

In $\tau_{\mathrm{refund}}+1$, if the record
$(\mathrm{deposit},sid,ssid,s,r,\phi_{s,r},\phi_{\mathrm{refund}},\tau_{\mathrm{claim}},\tau_{\mathrm{refund}},c)$
was not deleted, then perform the following process:

  1. 1.

Send
$(\mathrm{give},sid,ssid,s,r,\phi_{s,r},\phi_{\mathrm{refund}},\tau_{\mathrm{claim}},\tau_{\mathrm{refund}},{\sf
coins}(c))$ to $P_{r}$.

  2. 2.

Delete the record
$(\mathrm{deposit},sid,ssid,s,r,\phi_{s,r},\phi_{\mathrm{refund}},\tau_{\mathrm{claim}},\tau_{\mathrm{refund}},c)$.

##  6 Achieving Equivalent Compensation

In this section, we describe how to achieve secure computation with equivalent
penalties with $O(1)$ rounds and $O(n)$ broadcasts.

We first recall the reason for the non-equivalence. $P_{n-1}$’s compensation
amount depends on the number of parties who aborts in step 6). (See Section
4.2.) Let $x\in[n-2]$ be the number of parties who abort in step 6). Then,
$P_{n-1}$’s compensation amount is ${\sf coins}(((x-1)n+2-x)q)={\sf
coins}(((n-2)^{2}-(n-2-x)(n-1))q)$. (Note that $n-2-x$ is the number of
parties who claim in step 6).) Thus, $P_{n-1}$ is compensated with more than
${\sf coins}(q)$ if two or more parties abort in step 6), although
compensation amounts for the other parties are always ${\sf coins}(q)$. In
order to remove the non-equivalence, it is necessary that $P_{n-1}$ is
compensated with the same amount of coins as the other honest parties even if
two or more parties abort in step 6).

###  6.1 A solution based on the honesty of the parties

A simple solution is that $P_{n-1}$ distributes coins to the other honest
parties so that the compensation amounts are equivalent. More precisely, when
$x\,(\geq 2)$ parties abort in step 6), $P_{n-1}$ transfers coins666Since the
sum of the compensations is ${\sf coins}((n-2)xq)={\sf
coins}(((x-1)n+2-x)q+(n-2+x)q)$, $P_{n-1}$ sends ${\sf
coins}((n-2)xq/(n-1+x))$ to each of parties who claim in step 6).  $n-2-x$
parties who claim in step 6) to make the compensations equivalent for
$P_{n-1}$ and them, after terminating the protocol.

However, this solution has no enforcement for $P_{n-1}$ to distribute coins
since $P_{n-1}$ is imposed no penalty if he/she refuses to distribute coins.
It is undesirable since it relies too much on $P_{n-1}$’s honest behaviour. In
the below, we present a technique of achieving the equivalent compensation in
a more enforceable way.

###  6.2 Claim-refund-or-give functionality

The main idea of satisfying the equivalent compensation is to build a
mechanism whereby $P_{n-1}$ cannot refund for more than one transaction in
step 6). For instance, when $P_{1}$ and $P_{2}$ abort in step 6), the
mechanism forces $P_{n-1}$ to only get ${\sf coins}((n-1)q)$ back. Namely, if
$P_{n-1}$ gets back ${\sf coins}((n-1)q)$ from the transaction made for
$P_{1}$, then $P_{n-1}$ is forced to give ${\sf coins}((n-1)q)$ to $P_{2}$. As
a result, $P_{n-1}$ is compensated with ${\sf coins}(q)$ as the other honest
parties.

To put the above idea, we introduce a new functionality called claim-refund-
or-give functionality $\mathcal{F}^{*}_{\mathrm{CRG}}$, which is an extension
of the claim-or-refund functionality. $\mathcal{F}^{*}_{\mathrm{CRG}}$ is the
same as $\mathcal{F}^{*}_{\mathrm{CR}}$ except that there is a condition for a
sender to get the coins back in the refund phase. When a receiver does not
reveal the witness in the claim phase, a sender can refund only if the sender
reveals his/her witness $w_{s}$. If the sender does not reveal the witness
$w_{s}$ in the refund phase, the sender is forced to give the receiver the
coins.

$\mathcal{F}^{*}_{\mathrm{CRG}}$ consists of four phases: deposit, claim,
refund, and give. (See Functionality 7 for a formal description of
$\mathcal{F}^{*}_{\mathrm{CRG}}$.) In the deposit phase, a sender $P_{s}$
sends conditional coins with two predicates
$\phi_{s,r},\phi_{\mathrm{refund}}$ and two round numbers
$\tau_{\mathrm{claim}},\tau_{\mathrm{refund}}$ where
$\tau_{\mathrm{claim}}<\tau_{\mathrm{refund}}$. (We note that, in our
protocol, $\phi_{s,r}$ is determined by the sender, but
$\phi_{\mathrm{refund}}$ is collaboratively designed with the sender and the
receiver.) In the claim phase, the receiver $P_{r}$ gets the coins only if
he/she submits a witness $w_{r}$ such as $\phi_{s,r}(w_{r})=1$ within
$\tau_{\mathrm{claim}}$. In the refund phase, the sender $P_{s}$ gets back the
coins only if $P_{r}$ does not claim in $\tau_{\mathrm{claim}}$ and $P_{s}$
reveals a witness $w_{s}$ such as $\phi_{\mathrm{refund}}(w_{s})=1$ within
$\tau_{\mathrm{refund}}$. In the give phase, if $P_{s}$ does not claim and
$P_{r}$ does not refund, $P_{r}$ receives the coins. Note that
$\mathcal{F}^{*}_{\mathrm{CRG}}$ is the same as
$\mathcal{F}^{*}_{\mathrm{CR}}$ if $\phi_{\mathrm{refund}}$ is a tautology
since $P_{r}$ can refund unconditionally in the refund phase.

###  6.3 How to resolve the non-equivalence

Using $\mathcal{F}^{*}_{\mathrm{CRG}}$, we construct a mechanism to prevent
$P_{n-1}$ refunds two or more transactions in step 6). Our solution is as
follows: In the first phase, i.e., secure computation for the augmented
function $\hat{f}$, the parties generate the following values in addition to
the secret shares of $\hat{f}$.

  * •

$(S_{1},\dots,S_{n-2})$: the token $S_{i}$ is a pair $(s_{i},d_{i})$ of a
secret share $s_{i}$ of the $P_{n-1}$’s witness $w$, and the de-commitment
$d_{i}$ of the secret share. Here, the witness $w$ is chosen from
$\\{0,1\\}^{k}$ uniformly at random. The underlying secret sharing scheme is
pubNMSS where the threshold value is two. Only $P_{n-1}$ receives all of these
values.

  * •

$(c_{1},\dots,c_{n-2})$: each $c_{i}$ is a commitment of the secret share
$s_{i}$. All parties receive these values.

  * •

$\mathrm{com}_{w}$: a commitment of the $P_{n-1}$’s witness $w$. This value is
revealed for all parties.

We make two changes in the second phase, i.e., the fair reconstruction
protocol. The first one is to add a condition for $P_{n-1}$ to refund the
transactions created in step 3), i.e., the transactions claimed in step 6).
(See Protocol 4. The relevant transactions are ($n+1$) to ($2n-2$).) In our
solution, $P_{n-1}$ must reveal the secret share $s_{i}$ within
$\tau^{\prime}_{2}\,(>\tau_{2})$ to refund the coins from $P_{i}$. Note that
the commitments $(c_{1},\dots,c_{n-2})$ are used to verify the validity in
this refund phase. We do not change for the other transactions.

The second change is to add the following transactions. (Suppose that
$\tau^{\prime\prime}_{2}>\tau^{\prime}_{2}$.)

$\displaystyle
P_{n-1}\xrightarrow[\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(n-1)q,\tau^{\prime\prime}_{2}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,]{w}P_{1}$
$\displaystyle
P_{n-1}\xrightarrow[\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(n-1)q,\tau^{\prime\prime}_{2}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,]{w}P_{2}$
$\displaystyle\vdots\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$
$\displaystyle
P_{n-1}\xrightarrow[\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(n-1)q,\tau^{\prime\prime}_{2}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,]{w}P_{n-2}$

These transactions are prepared to penalize $P_{n-1}$ when he/she refunds two
or more transactions in step 6). Recall that $P_{n-1}$ must publish the secret
share $S_{i}$ to refund the coins from $P_{i}$. Since the threshold value is
two, the secret value $w$ is revealed for all parties if $P_{n-1}$ refunds two
or more transactions in step 6). Further, the middle parties can claim the
added transactions when they learn $w$. (Note that the commitment
$\mathrm{com}_{w}$ is used here to verify the validities.) Thus, the added
transactions prevent $P_{n-1}$ from the excessive refund.

We confirm that the above-mentioned way obtains the equivalent compensations
below. If $P_{n-1}$ refunds $x$ transactions ($2\leq x\leq n-2$) and gets back
${\sf coins}(x(n-1)q)$, then he/she loses ${\sf coins}((n-2)(n-1)q)$, which is
more than or equal to ${\sf coins}(x(n-1)q)$ for all $x$. Namely, the added
transactions prevent $P_{n-1}$ to refund two or more transactions in step 6).
Also, if corrupted $P_{n-1}$ refunds two or more transactions in step 6), then
the compensation amounts are ${\sf coins}(nq)$ for all honest parties. Thus,
the compensation amounts always are the same for all honest parties. As a
result, we resolve the non-equivalence and obtain secure computation with
penalties in $O(1)$ rounds and $O(n)$ broadcasts.

We note that $P_{n-1}$ needs to create the added transactions before step 4),
i.e., before transactions ($2n-1$) to ($3n-4$) are created. Otherwise,
corrupted $P_{n-1}$ can initiate step 5) without making the transactions.
Since it is sufficient to create the added transactions at the same round as
steps 1)-3), our solution can be applied without increasing the number of
rounds. (We suppose that the added transactions are created in step 3) below.)

In summary, our fair reconstruction protocol that resolves the non-equivalence
proceeds as follows.777For a deposit transaction that does not specify a
predicate for refund, we suppose that the predicate is set as a tautology.

Deposit phase:

  1. 1.

For $i\in\\{1,\dots,n-1\\}$, $P_{i}$ makes a transaction to send $P_{n}$ ${\sf
coins}(q)$ with a predicate for claim $\phi_{i,n}$ and a round number for
claim $\tau_{4}$, where $\phi_{i,n}(x)=1$ only if $x=T_{1}\wedge\dots\wedge
T_{n}$.

  2. 2.

$P_{n}$ makes a transaction to send $P_{n-1}$ ${\sf coins}((n-1)q)$ with a
predicate for claim $\phi_{n,n-1}$ and a round number for claim $\tau_{3}$,
where $\phi_{n,n-1}(x)=1$ only if $x=T_{1}\wedge\dots\wedge T_{n-1}$.

  3. 3.

For $i\in\\{1,\dots,n-2\\}$, $P_{n-1}$ makes a transaction to send $P_{i}$
${\sf coins}((n-1)q)$ with a predicate for claim $\phi_{n-1,i}$, a predicate
for refund $\phi^{\prime}_{n-1,i}$, a round number for claim $\tau_{2}$, and a
round number for refund $\tau^{\prime}_{2}$ where $\phi_{n-1,i}(x)=1$ only if
$x=T_{n-1}\wedge T_{i}$ and $\phi^{\prime}_{n-1,i}(x)=1$ only if $x=S_{i}$.
Further, $P_{n-1}$ makes a transaction to send $P_{i}$ ${\sf coins}((n-1)q)$
with a predicate for claim $\psi_{n-1,i}$ a round number for claim
$\tau^{\prime\prime}_{2}$, where $\psi_{n-1,i}(x)=1$ only if $x=w$.

  4. 4.

For $i\in\\{1,\dots,n-2\\}$, $P_{i}$ makes a transaction to send $P_{n-1}$
${\sf coins}((n-2)q)$ with a circuit $\phi_{i,n-1}$ and a round number
$\tau_{1}$, where $\phi_{i,n-1}(x)=1$ only if $x=T_{n-1}$.

Claim phase:

  1. 5.

$P_{n-1}$ claims by publishing $T_{n-1}$ in round $\tau_{1}$ and receives
${\sf coins}((n-2)q)$ from each of $P_{1},\dots,P_{n-2}$.

  2. 6.

For $i\in\\{1,\dots,n-2\\}$, $P_{i}$ claims by publishing $T_{n-1}\wedge
T_{i}$ in round $\tau_{2}$ and receives ${\sf coins}((n-1)q)$ from $P_{n-1}$.

  3. 7.

$P_{n-1}$ claims by publishing $T_{1}\wedge\dots\wedge T_{n-1}$ in round
$\tau_{3}$ and receives ${\sf coins}((n-1)q)$ from $P_{n}$.

  4. 8.

$P_{n}$ claims by publishing $T_{1}\wedge\dots\wedge T_{n}$ in round
$\tau_{4}$ and receives ${\sf coins}(q)$ from each of $P_{1},\dots,P_{n-1}$.

Note that there is no change in the claim phase from the protocol described in
Section 4.3 if all parties behave honestly. In the claim phase, the procedure
changes only when adversarial parties abort in step 6). For the deposit phase,
the change is in step 3) only. In step 3), $P_{n-1}$ creates two deposit
transactions for each of $P_{1},\dots,P_{n-1}$ in one round.

#### Remark 3

In the functionality of secure computation with penalties (Functionality 2),
the compensation amount is always $q$. On the other hand, we allow the
compensation amount to be $aq$ for $a\geq 1$, where $a$ is chosen by a
simulator. We note that adversaries always choose $a=1$ if they are rational
since they want to minimize the compensation amount. Thus, if adversaries are
rational, there is no difference between the original functionality and ours.
We remark that the compensation amounts for honest parties are always the same
regardless of the value $a$.

##  7 Conclusion

This paper focused on secure computation with penalties based on Bitcoin.
Bentov and Kumaresan [9] showed that secure computation with penalties can be
constructed with $O(n)$ rounds and $O(n)$ broadcasts for any function in the
$(\mathcal{F}_{\mathrm{OT}},\mathcal{F}^{*}_{\mathrm{CR}})$-hybrid model. As
far as we know, no protocol achieves $O(1)$ rounds and $O(n)$ broadcasts.

This paper showed a first protocol that needs only $O(1)$ rounds and $O(n)$
broadcasts. First, we introduced secure computation with non-equivalent
penalties that is a relaxed variant of secure computation with penalties in
terms of the compensation amount. In secure computation with penalties, every
honest party can be compensated with the same amount of coins when an
adversary aborts after learning the output value. On the other hand, in our
setting, every honest party is guaranteed to be compensated with more than a
predetermined amount of coins, but not the same amount. We showed that secure
computation with non-equivalent penalties can be realized with $O(1)$ rounds
and $O(n)$ broadcasts for arbitrary functions in the
$(\mathcal{F}_{\mathrm{OT}},\mathcal{F}^{*}_{\mathrm{CR}})$-hybrid model. In
particular, we improved the round complexity of the fair reconstruction
protocol, which is a key ingredient for realizing secure computation with
penalties.

In addition to the above result, we showed two techniques to solve issues of
our protocol. First technique was to solve the issue of increasing the deposit
amount to $O(n^{2}q)$ from $O(nq)$, which is the deposit amount of the Bentov-
Kumaresan’s protocol. Our technique reduces the deposit amount by about
$1/(l+1)$ instead of the number of rounds is increased by $2l$. We leave the
following open problem: Is it possible to design secure computation with
penalties that needs $O(1)$ rounds, $O(n)$ broadcasts, and $O(nq)$ deposit
amount?

The second technique was to solve the non-equivalence of the compensation
amount. In order to achieve this result, we proposed new functionality called
claim-refund-or-give functionality. It achieved the equivalent compensation
without sacrificing efficiency. Thus, a fair protocol can be realized with
$O(1)$ rounds and $O(n)$ broadcasts based on Bitcoin.

## References

  * [1] A. C.-C. Yao, How to generate and exchange secrets, in: Proceedings of the 27th Annual Symposium on Foundations of Computer Science, FOCS ’86, IEEE Computer Society, USA, 1986, p. 162–167.  doi:10.1109/SFCS.1986.25.
  * [2] R. Cleve, Limits on the security of coin flips when half the processors are faulty, in: Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, STOC ’86, Association for Computing Machinery, New York, NY, USA, 1986, p. 364–369.  doi:10.1145/12130.12168.
  * [3] A. Y. Lindell, Legally-enforceable fairness in secure two-party computation, in: T. Malkin (Ed.), Topics in Cryptology – CT-RSA 2008, Springer Berlin Heidelberg, Berlin, Heidelberg, 2008, pp. 121–137.
  * [4] S. Nakamoto, Bitcoin: A peer-to-peer electronic cash system, Cryptography Mailing list at https://metzdowd.com (03 2009).
  * [5] A. Back, I. Bentov, Note on fair coin toss via bitcoin, CoRR abs/1402.3698 (2014).  arXiv:1402.3698.
URL http://arxiv.org/abs/1402.3698

  * [6] M. Andrychowicz, S. Dziembowski, D. Malinowski, L. Mazurek, Secure multiparty computations on bitcoin, in: 2014 IEEE Symposium on Security and Privacy, 2014, pp. 443–458.  doi:10.1109/SP.2014.35.
  * [7] M. Andrychowicz, S. Dziembowski, D. Malinowski, Ł. Mazurek, Fair two-party computations via bitcoin deposits, in: R. Böhme, M. Brenner, T. Moore, M. Smith (Eds.), Financial Cryptography and Data Security, Springer Berlin Heidelberg, Berlin, Heidelberg, 2014, pp. 105–121.
  * [8] R. Kumaresan, I. Bentov, How to use bitcoin to incentivize correct computations, in: Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, CCS ’14, Association for Computing Machinery, New York, NY, USA, 2014, p. 30–41.  doi:10.1145/2660267.2660380.
  * [9] I. Bentov, R. Kumaresan, How to use bitcoin to design fair protocols, in: J. A. Garay, R. Gennaro (Eds.), Advances in Cryptology – CRYPTO 2014, Springer Berlin Heidelberg, Berlin, Heidelberg, 2014, pp. 421–439.
  * [10] R. Kumaresan, T. Moran, I. Bentov, How to use bitcoin to play decentralized poker, in: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, CCS ’15, Association for Computing Machinery, New York, NY, USA, 2015, p. 195–206.  doi:10.1145/2810103.2813712.
  * [11] Z. Zhao, T. H. Chan, How to vote privately using bitcoin, in: S. Qing, E. Okamoto, K. Kim, D. Liu (Eds.), Information and Communications Security - 17th International Conference, ICICS 2015, Beijing, China, December 9-11, 2015, Revised Selected Papers, Vol. 9543 of Lecture Notes in Computer Science, Springer, 2015, pp. 82–96.  doi:10.1007/978-3-319-29814-6_8.
  * [12] R. Kumaresan, I. Bentov, Amortizing secure computation with penalties, in: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS ’16, Association for Computing Machinery, New York, NY, USA, 2016, p. 418–429.  doi:10.1145/2976749.2978424.
  * [13] R. Kumaresan, V. Vaikuntanathan, P. N. Vasudevan, Improvements to secure computation with penalties, in: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS ’16, Association for Computing Machinery, New York, NY, USA, 2016, p. 406–417.  doi:10.1145/2976749.2978421.
  * [14] M. Bartoletti, R. Zunino, Constant-deposit multiparty lotteries on bitcoin, in: Financial Cryptography and Data Security, Springer International Publishing, Cham, 2017, pp. 231–247.
  * [15] A. Miller, I. Bentov, Zero-collateral lotteries in bitcoin and ethereum, in: 2017 IEEE European Symposium on Security and Privacy Workshops, EuroS&P Workshops 2017, Paris, France, April 26-28, 2017, IEEE, 2017, pp. 4–13.  doi:10.1109/EuroSPW.2017.44.
  * [16] R. Zhu, C. Ding, Y. Huang, Efficient publicly verifiable 2pc over a blockchain with applications to financially-secure computations, CCS ’19, Association for Computing Machinery, New York, NY, USA, 2019, p. 633–650.  doi:10.1145/3319535.3363215.
  * [17] S. Faust, C. Hazay, D. Kretzler, B. Schlosser, Financially backed covert security, in: Public-Key Cryptography - PKC 2022 - 25th IACR International Conference on Practice and Theory of Public-Key Cryptography, Virtual Event, Proceedings, Part II, Vol. 13178 of Lecture Notes in Computer Science, Springer, 2022, pp. 99–129.  doi:10.1007/978-3-030-97131-1_4.
  * [18] A. Kiayias, H.-S. Zhou, V. Zikas, Fair and robust multi-party computation using a global transaction ledger, in: Proceedings, Part II, of the 35th Annual International Conference on Advances in Cryptology — EUROCRYPT 2016 - Volume 9666, Springer-Verlag, Berlin, Heidelberg, 2016, p. 705–734.
  * [19] I. Bentov, R. Kumaresan, A. Miller, Instantaneous decentralized poker, in: T. Takagi, T. Peyrin (Eds.), Advances in Cryptology – ASIACRYPT 2017, Springer International Publishing, Cham, 2017, pp. 410–440.
  * [20] B. David, R. Dowsley, M. Larangeira, Kaleidoscope: An efficient poker protocol with payment distribution and penalty enforcement, in: S. Meiklejohn, K. Sako (Eds.), Financial Cryptography and Data Security, Springer Berlin Heidelberg, Berlin, Heidelberg, 2018, pp. 500–519.
  * [21] B. David, R. Dowsley, M. Larangeira, ROYALE: A framework for universally composable card games with financial rewards and penalties enforcement, in: Financial Cryptography and Data Security - 23rd International Conference, FC 2019, Revised Selected Papers, Vol. 11598 of Lecture Notes in Computer Science, Springer, 2019, pp. 282–300.  doi:10.1007/978-3-030-32101-7_18.
  * [22] G. Wood, Ethereum: A secure decentralised generalised transaction ledger, Ethereum project yellow paper 151 (2014) 1–32.
  * [23] T. Nakai, K. Shinagawa, Secure Computation with Non-Equivalent Penalties in Constant Rounds, in: 3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021), Vol. 97 of Open Access Series in Informatics (OASIcs), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2022, pp. 5:1–5:16.  doi:10.4230/OASIcs.Tokenomics.2021.5.
  * [24] I. Bentov, R. Kumaresan, How to use bitcoin to design fair protocols, Cryptology ePrint Archive, Report 2014/129 (2014).
  * [25] J. A. Garay, J. Katz, R. Kumaresan, H.-S. Zhou, Adaptively secure broadcast, revisited, in: Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC ’11, Association for Computing Machinery, New York, NY, USA, 2011, p. 179–186.  doi:10.1145/1993806.1993832.
  * [26] J. Kilian, Founding crytpography on oblivious transfer, in: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC ’88, Association for Computing Machinery, New York, NY, USA, 1988, p. 20–31.  doi:10.1145/62212.62215.
  * [27] Y. Ishai, M. Prabhakaran, A. Sahai, Founding cryptography on oblivious transfer – efficiently, in: D. Wagner (Ed.), Advances in Cryptology – CRYPTO 2008, Springer Berlin Heidelberg, Berlin, Heidelberg, 2008, pp. 572–591.

##  Appendix A Proof of Theorem 1

In the SCC model, a simulator $\mathcal{S}$ needs to simulate two parts: one
is the standard functionality for $f$ and another one is coins.

###  A.1 Simulation for the standard functionality

The simulation for the former is almost the same as the proof of Bentov-
Kumaresan’s protocol [24]. A simulator $\mathcal{S}$ performs one of the two
simulations depending on whether $P_{n}$ is honest. If $P_{n}$ is honest, then
an adversary $\mathcal{A}$’s decision to abort is independent of the output
because of the assumption of pubNMSS. In this case, $\mathcal{S}$ can simulate
in the same way as in standard secure computation. If $P_{n}$ is corrupted,
then $\mathcal{A}$’s decision to abort can depend on the output. In order to
simulate this, $\mathcal{S}$ must send $\mathcal{F}^{*}_{f,\mathrm{neq}}$
corrupted parties’ inputs to receive the output. Although the output and the
shares distributed to corrupted parties may contradict, $\mathcal{S}$ can
simulate it by using the equivocation property of the honest-binding
commitment.

###  A.2 Simulation for coins

We here show how to simulate coins. In the SCC model, an environment
$\mathcal{Z}$ can initialize parties’ wallets and choose parties’ inputs. We
note that $\mathcal{S}$ cannot create coins, and thus it must complete the
simulation using only the coins provided by $\mathcal{Z}$. Suppose that
$\mathcal{Z}$ provides each party with the minimum amount of coins necessary
to run the protocol. If $\mathcal{Z}$ provides fewer coins than this, then
$\mathcal{S}$ terminates the simulation. We use ${\sf SimWallet}$, which
accounts for coins provided by corrupted parties. At the beginning of the
simulation, ${\sf SimWallet}$ has no coins since all coins are provided to
$\mathcal{A}$. ${\sf SimWallet}$ must hold a compensation amount to run
$\mathcal{F}^{*}_{f,\mathrm{neq}}$ when an adversary aborts to steal the
output, i.e., aborts without telling the value to honest parties. In secure
computation with penalties, when $\mathcal{A}$ steals the output,
$\mathcal{S}$ sends ${\sf coins}(h^{\prime}q)$ to $\mathcal{F}^{*}_{f}$ to
learn the output. Note that $h^{\prime}=|H^{\prime}|$ means the number of
honest parties who should be compensated. On the other hand, in secure
computation with non-equivalent penalties, when $\mathcal{A}$ aborts,
$\mathcal{S}$ sends $\mathcal{F}^{*}_{f,\mathrm{neq}}$ more than ${\sf
coins}(h^{\prime}q)$, which is the main difference from the proof of Bentov-
Kumaresan’s protocol.

If an adversary $\mathcal{A}$ aborts in the deposit phase, a simulator
$\mathcal{S}$ sends all coins in ${\sf SimWallet}$ to $\mathcal{A}$. And then
it terminates the simulation. Next, suppose that the adversary performs
honestly in the deposit phase. Note that ${\sf SimWallet}$ has all coins
deposited by $\mathcal{A}$ at the beginning of the claim phase.

Let us consider the case where an adversary $\mathcal{A}$ aborts in the claim
phase. As mentioned above, $P_{n-1}$ is the only party to be able to receive
more than ${\sf coins}(q)$ as compensation. Also, the deposit amount is ${\sf
coins}((n^{2}-3n+3)q)$ for $P_{n-1}$ and ${\sf coins}((n-1)q)$ for all other
parties. Hence, we discuss the claim phase separating the cases where $n-1\in
C$ or not. Also, we suppose that $n\in C$ since we mainly discuss the case
where $\mathcal{A}$ aborts to steal the output.

Case of $n-1\in C$: In this case, all honest parties in $H^{\prime}$ must
receive ${\sf coins}(q)$ as compensation. Note that all of them belong to the
middle parties. At the beginning of the claim phase, ${\sf SimWallet}$ holds
${\sf coins}((c-1)(n-1)q+(n^{2}-3n+3)q)$ that are the sum of deposited coins
by the corrupted parties, where $c=|C|$. If corrupted $P_{n-1}$ reveals
$T_{n-1}$ honestly, then $\mathcal{S}$ sends ${\sf coins}((n-2)^{2}q)$, which
are taken from ${\sf SimWallet}$, to $\mathcal{A}$. As a result, ${\sf
SimWallet}$ holds ${\sf coins}(c(n-1)q)$. Let us consider the case where
$\mathcal{A}$ aborts in step 6) (see Section 4.3) and steals the output. For
the sake of simplicity, we here assume that every corrupted party aborts in
step 6). 888Note that $\mathcal{A}$ only needs one of the corrupted parties
aborts in step 6) to steal the output. $\mathcal{S}$ can also similarly
simulate such a case. Then, $\mathcal{S}$ sends ${\sf coins}((n-c)q)$ to
$\mathcal{F}^{*}_{f,\mathrm{neq}}$ to learn the output. Furthermore,
$\mathcal{S}$ here needs to send $\mathcal{A}$ coins to simulate refunds for
corrupted parties. The transactions that are not claimed consist of (A) ones
created by corrupted parties in steps 1)–2) and (B) ones created in step 3) by
$P_{n-1}$ to corrupted parties. The amount of coins in (A) and (B) are ${\sf
coins}((c-1)q+(n-1)q)$ and ${\sf coins}((n-1)(c-2)q)$, respectively. Namely,
$\mathcal{S}$ sends ${\sf coins}(n(c-1)q)$, which is the sum of (A) and (B),
to $\mathcal{A}$. Since $\mathcal{S}$ must send ${\sf coins}((n-c)q)$ to
$\mathcal{F}^{*}_{f,\mathrm{neq}}$ and ${\sf coins}(n(c-1)q)$ to
$\mathcal{A}$, ${\sf SimWallet}$ must hold ${\sf coins}(c(n-1)q)$. This is the
same amount of coins ${\sf SimWallet}$ holds. Thus, it completes to simulate
the case where $\mathcal{A}$ aborts to steal the output in step 6).

If an adversary $\mathcal{A}$ behaves honestly in step 6), then a simulator
$\mathcal{S}$ sends ${\sf coins}((n-1)(c-2)q)$ to $\mathcal{A}$. Also, suppose
that $\mathcal{A}$ behaves in step 7) honestly. Then, $\mathcal{S}$ sends
${\sf coins}((n-1)q)$ to $\mathcal{A}$.999Since $P_{n}$ and $P_{n-1}$ are
corrupted, $\mathcal{S}$ sends the same coins to $\mathcal{A}$ as refunded if
$P_{n-1}$ aborts in this step. As a result, ${\sf SimWallet}$ holds ${\sf
coins}((n-1)q)$. Let us consider the case where $\mathcal{A}$ aborts in step
8) and steals the output. Then, $\mathcal{S}$ sends
$\mathcal{F}^{*}_{f,\mathrm{neq}}$ ${\sf coins}((n-c)q)$ to learn the output.
Furthermore, $\mathcal{S}$ sends ${\sf coins}((c-1)q)$, which is the refund,
to $\mathcal{A}$. Thus, ${\sf SimWallet}$ must hold ${\sf coins}((n-1)q)={\sf
coins}((n-c)q+(c-1)q)$. This is the same amount of coins ${\sf SimWallet}$
holds. Thus, it completes to simulate the case where $\mathcal{A}$ aborts to
steal the output in step 8).

Case of $n-1\notin C$: At the beginning of the claim phase, ${\sf SimWallet}$
holds ${\sf coins}(c(n-1)q)$. Note that $\mathcal{S}$ uses no coins in ${\sf
SimWallet}$ to simulate step (5) since $P_{n-1}$ is honest. Let us consider
the case where an adversary $\mathcal{A}$ aborts in step 6) and steals the
output. $P_{n-1}$ is compensated with ${\sf coins}((nc-2n-c+3)q)={\sf
coins}((n-2)^{2}q-(n-c-1)(n-1)q)$. The other honest parties are compensated
with ${\sf coins}(q)$. Thus, $\mathcal{S}$ sends ${\sf coins}((nc-n-2c+2)q)$
to $\mathcal{F}^{*}_{f,\mathrm{neq}}$ to learn the output. Furthermore,
$\mathcal{S}$ sends ${\sf coins}((n+c-2)q)$, which is the refund, to
$\mathcal{A}$. ${\sf SimWallet}$ must hold ${\sf coins}(c(n-1)q)={\sf
coins}((nc-n-2c+2)q)+{\sf coins}((n+c-2)q)$, and this is the same amount of
coins ${\sf SimWallet}$ holds. Thus, it completes to simulate the case where
$\mathcal{A}$ aborts to steal the output in step 6).

Suppose that an adversary behaves honestly in steps 6) and 7). Then,
$\mathcal{S}$ sends ${\sf coins}((nc-n-c+1)q)$ to $\mathcal{A}$ to simulate
step 6) and no coins to simulate step 7). As a result, ${\sf SimWallet}$ holds
${\sf coins}((n-1)q)$. Let us consider the case where $\mathcal{A}$ aborts in
step 8) and steals the output. Then, $\mathcal{S}$ sends
$\mathcal{F}^{*}_{f,\mathrm{neq}}$ ${\sf coins}((n-c)q)$ to learn the output.
Furthermore, $\mathcal{S}$ sends ${\sf coins}((c-1)q)$, which is the refund,
to $\mathcal{A}$. Thus, ${\sf SimWallet}$ must hold ${\sf coins}((n-1)q)={\sf
coins}((n-c)q+(c-1)q)$. This is the same amount of coins ${\sf SimWallet}$
holds. Thus, it completes to simulate the case where $\mathcal{A}$ aborts to
steal the output in step 8). $\Box$

##  Appendix B Realization of $\mathcal{F}^{*}_{\mathrm{CRG}}$ via Bitcoin

Suppose that a Bitcoin transaction consists of $(id,x,\sigma,\pi,\tau)$, where
$id$ is an identifier of a previous transaction, $x$ is the amount of coins,
$\sigma$ is an input script, $\pi$ is an output script, and $\tau$ is a time-
bound. For a Bitcoin transaction $txn$, $\mathrm{simp}(txn)$ means a
simplified form of $txn$. The simplified form refers to $(id,x,\pi,\tau)$,
i.e., it expresses a transaction excluding its input script. Note that Bitcoin
script opcodes are allowed to take a simplified form of a transaction itself
as an input.

Protocol 8 shows an implementation of the claim-refund-or-give functionality
$\mathcal{F}^{*}_{\mathrm{CRG}}$. In this implementation, the parties create
four transactions, $txn_{\mathrm{CRG}}$, $txn_{\mathrm{claim}}$,
$txn_{\mathrm{refund}}$, $txn_{\mathrm{give}}$. $P_{s}$ broadcasts transaction
$txn_{\mathrm{CRG}}$ in the deposit phase. The remaining three transactions
are used to redeem $txn_{\mathrm{CRG}}$. Depending on which of the claim,
refund, or give is executed, one of the three transactions is broadcast to the
Bitcoin network.

See the opcode of $txn_{\mathrm{CRG}}$ in step 4). We can read that this
opcode consists of three parts by dividing the opcode by OR operation:

  * •

$\mathrm{OP\\_CHECKSIG}(pk_{r},\cdot)$ AND $\phi_{s,r}(\cdot)$

  * •

$\mathrm{OP\\_CHECKSIG}(pk_{r},\cdot)$ AND
$\mathrm{OP\\_CHECKSIG}(pk_{s},\cdot)$ AND $\phi_{\mathrm{refund}}(\cdot)$

  * •

$\mathrm{OP\\_CHECKSIG}(pk_{r},\cdot)$ AND
$\mathrm{OP\\_CHECKSIG}(pk_{s},\cdot)$ AND $H(\cdot)$

Thus, a party can redeem $txn_{\mathrm{CRG}}$ only if he/she provides an input
script that satisfies one of the three conditions.

The first opcode is prepared for the claim phase. In order to redeem
$txn_{\mathrm{CRG}}$ using this opcode, $P_{r}$ must reveals a witness $w_{r}$
such as $\phi_{s,r}(w_{r})=1$.

The second opcode is prepared for the refund phase. In order to redeem
$txn_{\mathrm{CRG}}$ using this opcode, $P_{s}$ must reveal a witness $w_{s}$
such as $\phi_{\mathrm{refund}}(w_{s})=1$. Also, $P_{s}$ uses $sig_{r}$, which
is generated by $P_{r}$ in step 12), to clear the opcode
$\mathrm{OP\\_CHECKSIG}(pk_{s},\cdot)$. $\mathrm{OP\\_CHECKSIG}(pk_{r},\cdot)$
is prepared to prevent $P_{s}$ from refunding before $\tau_{\mathrm{claim}}$.

The third opcode is for the give phase. If $txn_{\mathrm{CRG}}$ is not
redeemed at $\tau_{\mathrm{refund}}+1$, then $P_{r}$ can receive the coins by
revealing the random value $\lambda$ that is generated by $P_{r}$ in step 2).
$P_{r}$ uses $sig_{s}$, which is generated by $P_{s}$ in step 8), to satisfy
the opcode $\mathrm{OP\\_CHECKSIG}(pk_{s},\cdot)$.
$\mathrm{OP\\_CHECKSIG}(pk_{s},\cdot)$ is used to prevent $P_{r}$ from
refunding before $\tau_{\mathrm{refund}}$ by redeeming $txn_{\mathrm{CRG}}$
with other than $txn_{\mathrm{give}}$. Also, $H(\cdot)$ prevents $P_{s}$ from
redeeming $txn_{\mathrm{CRG}}$ by using the third opcode. If $H(\cdot)$ is not
included the third opcode, $P_{s}$ can redeem $txn_{\mathrm{CRG}}$ by using
$sig_{r}$ in step 12).

Protocol 8 Implementation of $\mathcal{F}^{*}_{\mathrm{CRG}}$ via Bitcoin.

Deposit phase:

Perform the following process.

  1. 1.

$P_{s}$ requests a fresh public key by sending
$(\mathsf{deposit\\_init},sid,ssid,s,r,\tau_{\mathrm{claim}},\tau_{\mathrm{refund}})$
to $P_{r}$.

  2. 2.

$P_{r}$ generates a fresh $(sk_{r},pk_{r})$ pair, a random value
$\lambda\in\\{0,1\\}^{k}$, and a predicate $\phi_{\mathrm{refund}}$.

  3. 3.

$P_{r}$ sends
$(\mathsf{deposit\\_ack},sid,ssid,s,r,\tau_{\mathrm{claim}},\tau_{\mathrm{refund}},pk_{r},H(\lambda),\phi_{\mathrm{refund}})$
to $P_{s}$ where $H$ is a hash function.

  4. 4.

$P_{s}$ takes his/her public key $pk_{s}$ and creates a Bitcoin transaction
$txn_{\mathrm{CRG}}$ that redeems ${\sf coins}(c)$. The output script $\pi$ is
set as follows:

$\displaystyle\pi(\cdot)=\mathsf{OP\\_CHECKSIG}(pk_{r},\cdot)\,\,\mathrm{AND}\,\,$
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,(\phi_{s,r}(\cdot)\,\,\mathrm{OR}\,\,(\mathrm{OP\\_CHECKSIG}(pk_{s},\cdot)\,\,\mathrm{AND}\,\,$
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\phi_{\mathrm{refund}}(\cdot))\,\,\mathrm{OR}\,\,(\mathrm{OP\\_CHECKSIG}(pk_{s},\cdot)\,\,\mathrm{AND}\,\,H(\cdot)))$

  5. 5.

$P_{s}$ computes the identifier $id_{\mathrm{CRG}}$ of $txn_{\mathrm{CRG}}$
and sends it to $P_{r}$.

  6. 6.

$P_{r}$ prepares a transaction $txn_{\mathrm{give}}$ that takes
$id_{\mathrm{CRG}}$ as its input script. $txn_{\mathrm{give}}$ has the
locktime $\tau_{\mathrm{refund}}$ and an output script $\pi^{\prime}(\cdot)$
that $P_{r}$ controls, i.e.,
$\mathrm{simp}(txn_{\mathrm{give}}):=(id_{\mathrm{CRG}},x,\pi^{\prime},\tau_{\mathrm{refund}})$.

  7. 7.

$P_{r}$ sends
$(\mathsf{deposit\\_sign\\_give},sid,ssid,s,r,\mathrm{simp}(txn_{\mathrm{give}}))$
to $P_{s}$.

  8. 8.

$P_{s}$ computes
$sig_{s}:=\mathrm{Sign}_{sk_{s}}(\mathrm{simp}(txn_{\mathrm{give}}))$. and
sends $(\mathsf{deposit\\_sign\\_give\\_ack},sid,ssid,s,r,sig_{s})$ to
$P_{r}$.

  9. 9.

$P_{r}$ checks whether
$\mathrm{Vrfy}_{pk_{s}}(\mathrm{simp}(txn_{\mathrm{give}}),sig_{s})=1$.

  10. 10.

$P_{s}$ prepares a transaction $txn_{\mathrm{refund}}$ that takes
$id_{\mathrm{CRG}}$ as its input script. $txn_{\mathrm{refund}}$ has the
locktime $\tau_{\mathrm{claim}}$ and an output script
$\pi^{\prime\prime}(\cdot)$ that $P_{s}$ controls, i.e.,
$\mathrm{simp}(txn_{\mathrm{refund}}):=(id_{\mathrm{CRG}},x,\pi^{\prime\prime},\tau_{\mathrm{refund}})$.

  11. 11.

$P_{s}$ sends
$(\mathsf{deposit\\_sign\\_refund},sid,ssid,s,r,\mathrm{simp}(txn_{\mathrm{refund}}))$
to $P_{r}$.

  12. 12.

$P_{r}$ computes
$sig_{r}:=\mathrm{Sign}_{sk_{r}}(\mathrm{simp}(txn_{\mathrm{refund}}))$ and
sends $(\mathsf{deposit\\_sign\\_refund\\_ack},sid,ssid,s,r,sig_{r})$ to
$P_{s}$.

  13. 13.

If $\mathrm{Vrfy}_{pk_{r}}(\mathrm{simp}(txn_{\mathrm{refund}}),sig_{r})=1$,
then $P_{s}$ broadcasts $txn_{\mathrm{CRG}}$ to the Bitcoin network.

Claim phase: $P_{r}$ broadcasts to the Bitcoin network a transaction
$txn_{\mathrm{claim}}$ that redeems $txn_{\mathrm{CRG}}$, by providing
$\mathrm{Sign}_{sk_{r}}(\mathrm{simp}(txn_{\mathrm{refund}}))$ and $w_{r}$
such as $\phi_{s,r}(w_{r})=1$.

Refund phase: At $\tau_{\mathrm{claim}}+1$, $P_{s}$ broadcasts to the Bitcoin
network the transaction $txn_{\mathrm{refund}}$ that redeems
$txn_{\mathrm{CRG}}$, by providing $sig_{r}$,
$\mathrm{Sign}_{sk_{s}}(\mathrm{simp}(txn_{\mathrm{refund}}))$, and $w_{s}$
such as $\phi_{\mathrm{refund}}(w_{s})=1$.

Give phase: At $\tau_{\mathrm{refund}}+1$, $P_{r}$ broadcasts to the Bitcoin
network the transaction $txn_{\mathrm{give}}$ that redeems
$txn_{\mathrm{CRG}}$, by providing
$\mathrm{Sign}_{sk_{r}}(\mathrm{simp}(txn_{\mathrm{give}}))$, $sig_{s}$, and
$\lambda$.