# Asynchronous Authentication

Marwa Mouallem
Technion
<EMAIL_ADDRESS>Ittay Eyal  Technion
<EMAIL_ADDRESS>

###### Abstract

A myriad of authentication mechanisms embody a continuous evolution from
verbal passwords in ancient times to contemporary multi-factor authentication.
Nevertheless, digital asset heists and numerous identity theft cases
illustrate the urgent need to revisit the fundamentals of user authentication.

We abstract away credential details and formalize the general, common case of
_asynchronous authentication_ , with unbounded message propagation time. Our
model, which might be of independent interest, allows for eventual message
delivery, while bounding execution time to maintain cryptographic guarantees.
Given credentials’ fault probabilities (e.g., loss or leak), we seek
mechanisms with the highest success probability.

We show that every mechanism is dominated by some _Boolean mechanism_ —defined
by a monotonic Boolean function on presented credentials. We present an
algorithm for finding approximately optimal mechanisms. Previous work analyzed
Boolean mechanisms specifically, but used brute force, which quickly becomes
prohibitively complex. We leverage the problem structure to reduce complexity
by orders of magnitude.

The algorithm is readily applicable to practical settings. For example, we
revisit the common approach in cryptocurrency wallets that use a handful of
high-quality credentials. We show that adding low-quality credentials improves
security by orders of magnitude.

##  1 Introduction

Authentication is a cornerstone of access control and security [1, 2]. From
ancient times [3] to the early days of the Internet, passwords were often
sufficient [4]. As stakes grow higher with the adoption of online services,
companies deploy advanced _authentication mechanisms_ [5, 6, 7]. Yet nascent
technologies raise the bar further: In cryptocurrencies, in the event of
credential loss or leak, there is no central authority that can assist in
asset recovery; and AI tools render even identification by video call
inconclusive [8]. The challenge is demonstrated by numerous incidents of
identity theft in the US [9], frequent loss of Bitcoin [10], and a recent
heist of $600M in digital assets due to a single company’s key mismanagement
[11].

Previous work (§2) proposed and employed various authentication solutions.
These encompass numerous _credential_ types, like passwords, biometrics, and
smart cards [12]. But Zimmermann et al. [13] and Vashi et al. [14] show that
no single credential can be completely relied on, leading to the development
of advanced mechanisms such as multi-factor authentication (MFA) and
interactive protocols [5, 6, 7]. However, these works leave open the question
of how to model and compare mechanisms’ security. Eyal [15] analyzes a
specific type of mechanisms, defined by monotonic Boolean functions on
presented credentials for a small number of credentials. Maram et al. [16]
study the authentication problem but assume a bounded-delay communication
channel between the mechanism and the user.

In this work, we study general authentication mechanisms in the common
asynchronous setting. First, we define the _asynchronous authentication
problem_ (§3), where an authentication mechanism interacts with a _user_ and
an _attacker_ (representing all adversarial entities [15, 16]) and tries to
identify the user. The mechanism utilizes credentials to identify the user.
Each credential can be known to the user, the attacker, both, or neither. The
states of all credentials define a _scenario_. A mechanism is _successful_ in
a scenario if it correctly identifies the user, for all attacker behaviors and
message delivery times, except with negligible probability. The _profile_ of a
mechanism is the set of all scenarios in which it is successful.

We seek to reason about a mechanism’s success when message delivery time is
unbounded, yet cryptographic assumptions bound running time according to a
security parameter. Therefore, we use _mechanism families_ —sets of mechanisms
that work similarly for different security parameters. Roughly, we require
success when the security parameter is large enough. This approach may be of
independent interest for analyzing distributed protocols that rely on
cryptography in asynchronous networks.

To design a mechanism, one must estimate the probabilities of credential
faults, e.g., loss or leak. An optimal mechanism has the maximum probability
of success given those estimates. To find optimal mechanisms we turn our
attention to _Boolean mechanisms_ : mechanisms that decide according to a
Boolean function of the credentials presented to them. For any authentication
mechanism, there exists a Boolean mechanism that dominates it—one that
succeeds in the same scenarios or more (§4.1). The proof uses a series of
reductions. First, interactive message exchanges do not enhance mechanism
security—every interactive mechanism is dominated by a non-interactive
mechanism. Second, decisions can be made solely on credential availability
proofs. Third, randomness does not improve the mechanism’s security. The
proofs are constructive and rely on a mechanism’s ability to simulate an
execution of another. Finally, for any deterministic mechanism, there exists a
dominating mechanism defined by a monotonic Boolean function of the
credentials’ availability—a _monotonic Boolean mechanism_.

Let us thus focus on such mechanisms. Any monotonic Boolean mechanism defined
by a non-trivial function is not dominated (maximal), and any maximal
mechanism is equivalent (same profile) to a monotonic Boolean mechanism
(§4.2). This result shows that studying such mechanisms suffices in the
asynchronous setting and reveals a somewhat surprising fact: There is no
probability-agnostic hierarchy of Boolean mechanisms in the asynchronous
setting unlike under synchrony [16]. For example, with two credentials $c_{1}$
and $c_{2}$, consider the mechanism where both $c_{1}$ and $c_{2}$ are
required to authenticate and the mechanism where only $c_{1}$ is required. One
can easily verify that neither mechanism dominates the other. In fact, this is
true in general, for any two non-trivial $n$-credential Boolean mechanisms.

Since there is no hierarchy of Boolean mechanisms, in general, any such
mechanism could be optimal. But evaluating all possible mechanisms, as done by
Eyal [15], quickly becomes prohibitively complex, as their number grows super-
exponentially with the number of credentials [17].

Instead, we present a scenario-based algorithm to find approximately optimal
mechanisms (§5). Given $\delta>0$, the algorithm finds a _$\delta$ -optimal
mechanism_, i.e., a mechanism whose success probability is at most $\delta$
lower than that of an optimal mechanism. The algorithm works greedily by
building a mechanism that succeeds in scenarios with the highest probability.
Once no more scenarios can be added, it removes existing scenarios to add new
ones. An analysis of different probability distributions shows that it is
sufficient to focus on a small number of high-probability scenarios. Rather
than searching all mechanisms, the algorithm stops when the scenarios that
might be added have additional probability lower than $\delta$. This is
calculated by bounding the number of scenarios in which a mechanism can
succeed.

Our algorithm allows designing approximately optimal mechanisms with many
credentials. This is directly useful for mechanism design. For example, when
designing a cryptocurrency wallet, users tend to use a handful of high-quality
credentials [18, 19], like hardware keys and long memorized mnemonics.
However, we show that adding a few easy-to-lose credentials (e.g., passwords
that the user remembers but does not back up) reduces wallet failure
probability by orders of magnitude. Similarly, incorporating easy-to-leak
credentials (e.g., the name of the user’s pet) with high-quality credentials
achieves a similar effect. (Though note this is not the typical use of such
credentials.)

In summary (§6), our contributions are: (1) formalization of the asynchronous
authentication problem; (2) proof that all maximal mechanisms can be defined
by a monotonic Boolean function; (3) proof that any two non-trivial monotonic
Boolean mechanisms are either equivalent or neither is better, (4) an
approximation algorithm of optimal mechanisms given the credentials fault
probabilities, and (5) concrete lessons for the design of cryptocurrency
wallets and online service authentication.

##  2 Related Work

Authentication is a fundamental aspect of security [1, 20, 21, 22, 2] that
continues to be an active area of research [23, 24]. Whether explicitly or
implicitly, previous work mostly addressed two perspectives: credentials and
protocols. Credentials are the information used to authenticate a user such as
passwords [25], one-time passwords (OTPs) [26], biometrics [27], and physical
devices [28]. Protocols define the procedures for authenticating a user based
on her credentials. Examples include Kerberos [29] for devices across a
network and cryptocurrency wallets [30, 31, 32]. Our focus is on protocols,
particularly the abstract mechanisms behind the protocols, which have received
only scant attention.

Vashi et al. [14] and Bonneau et al. [12] analyzed various credential types.
However, both surveys ultimately concluded that no single credential type
offers perfect security, underscoring the importance of protocols that
incorporate multiple credentials. Velásquez et al. [33] survey single and
multi-factor authentication schemes, examining different credentials combined
into multi-factor methods. Zimmermann et al. [13] rate dozens of deployed
authentication methods, focusing on user challenges in credential protection
rather than the security of the authentication mechanism.

Burrows et al. [34] describe the beliefs of parties involved in authentication
protocols as a consequence of communication to realize who has which
credentials. Delegation Logic [35] is a logic-based approach to distributed
authorization, offering a formal framework for reasoning about delegation
relationships. Neither work compares mechanism security, which is the goal of
this work.

The importance of authentication mechanisms has grown significantly due to the
increasing value of digital assets, such as cryptocurrencies [36] and NFTs
[37]. This is especially true in decentralized systems, where users are
responsible for securing their assets and, unlike centralized systems, no
fallback authority exists. Consequently, numerous cryptocurrency wallets have
been developed. The wide variety of authentication mechanisms used in
cryptocurrency wallets highlights the need for a formal way to compare them.
Nevertheless, previous work focused on credential management and
implementation [38, 39].

Hammann et al. [40] uncover vulnerabilities arising from the links between
different user credentials and accounts, where one can be used to log into the
other. The paper focuses on the connection between different credentials and
accounts. However, it does not address the security of different mechanisms,
which we do in this work.

Eyal [15] analyzes mechanisms that are Boolean functions of credential
availability. We analyze general mechanisms in an asynchronous network and
show that all maximally secure mechanisms in this setting can be reduced to
mechanisms that are Boolean functions of credentials availability. Eyal finds
optimal mechanisms given the probabilities of credential faults for up to $5$
credentials using a brute force search and bounds the failure probabilities of
optimal mechanisms using a heuristic approach. Although the brute-force search
ensures optionality, it is not computationally feasible for more credentials.
We provide an approximation method for near optimal mechanisms with a large
number of credentials based on our observations on the structure of maximally
secure mechanisms.

Maram et al. [16] study interactive authentication, where the user and the
attacker interact with the mechanism over a synchronous network. They also
introduce security profiles of mechanisms, which we use in our analysis.
However, unlike our work, the paper assumes a synchronous communication model,
which is not practical in many cases, e.g., when logging in to an email
service or issuing small cryptocurrency transactions. In contrast to the
synchronous case, we show that in the asynchronous case, mechanisms do not
benefit from interactivity. All maximally secure mechanisms can be reduced to
mechanisms that are Boolean functions of credentials availability, which is
not the case in the synchronous model.

Although our analysis uses methods similar to those used in distributed
systems’ theory like asynchronous communication and simulations, the
authentication problem is distinct from classical problems like consensus or
broadcast [41]: Success is defined by the decision of a single party and not
multiple ones, and credentials take a central role.

##  3 Model

We formalize the asynchronous authentication problem (§3.1), specifying an
execution, its participants, and their behavior. Then we define mechanism
success and the relation between different mechanisms (§3.2).

###  3.1 Asynchronous Authentication

The system comprises three entities, an _authentication mechanism_ $M$ and two
_players_ : a _user_ $U$ and an _attacker_ $A$. All three are finite
deterministic automata that can draw randomness from a _random tape_ $v$, an
infinite stream of random bits. We specify the automata as computer programs
[42].

An execution is orchestrated by a _scheduler_ , whose pseudocode is given in
Appendix A. Each of the players interacts with the mechanism by sending and
receiving messages. The scheduler, parametrized by
$\gamma_{\textit{ID}}\in\\{0,1\\}$, assigns the user identifier
$\gamma_{\textit{ID}}$ and the attacker identifier
${(1-\gamma_{\textit{ID}})}$. E.g., if $\gamma_{\textit{ID}}=0$, then the user
is player $0$ and the attacker is player $1$. The identifiers serve a similar
purpose to that of cookies that identify a website visitor during a single
session. They allow the mechanism to identify and distinguish between the
players during an execution without revealing which is the user.

To facilitate authentication, the players take advantage of private
information to convince the mechanism that they are the user. This information
is a set of credentials that might be data (e.g., passwords), biometric
properties (e.g., fingerprints), and physical objects (e.g., phones or smart
cards). Each credential has two parts: a public part, known to the mechanism,
and a secret part. For example, when using a password to authenticate to a
website, the user remembers the password (the secret part) and the website
stores its hash (the public part); or when using public key authentication, a
blockchain has the public key (the public part) and the user has the private
key (the secret part).

######  Definition 1 (Credential).

A _credential_ $c$ is a tuple ${c=(c^{P},c^{S})}$ where $c^{P}$ is the _public
part_ of the credential and $c^{S}$ is the _secret part_ of the credential.

The system uses a set of $n$ credentials, $\\{c_{1},...,c_{n}\\}$. A
credential can be _available_ to a player. An _availability vector_ represents
the availability of all credentials to a player. Each entry $i$ in the vector
indicates the availability of credential $i$. Denote by $\sigma_{U}$,
$\sigma_{A}$ the availability vector of the user and the attacker
respectively. A scenario $\sigma$ is a tuple of availability vectors
$(\sigma_{U},\sigma_{A})$. Denote by $C_{U}^{\sigma}$, $C_{A}^{\sigma}$ the
set of credentials available to the user and attacker in scenario $\sigma$
respectively.

The system uses a credential generation function
$\textit{gen}^{\lambda}({n})$, parametrized by a security parameter
$\lambda\in\mathbb{N}^{+}$. The function generates a set of $n$ credentials
$\\{(c_{i}^{P},c_{i}^{S})\\}_{i=1}^{n}$. Let
$T:\mathbb{N}^{+}\rightarrow\mathbb{N}^{+}$ be a polynomial function in the
security parameter $\lambda$ that maps it to the maximum number of steps that
an attacker is allowed to perform. A credential generation function is
_secure_ if the attacker’s probability of guessing information about the
credentials correctly in $T(\lambda)$ steps is negligibly better than a random
guess. That is, if the security parameter is large enough, the attacker cannot
guess the secrets better than a random guess in a polynomial number of steps
[43].

An _authentication mechanism_ exchanges messages with the players to decide
which is the user.

######  Definition 2 (Authentication mechanism).

An _authentication mechanism_ $M^{\lambda}$ is a finite deterministic
automaton, parametrized by the security parameter $\lambda$ and specified by
two functions, $\textit{gen}_{M^{\lambda}}({\cdot})$ and
$\textit{step}_{M^{\lambda}}({\cdot})$:

  * •

$\textit{gen}_{M^{\lambda}}({n})$, where $n$ is the number of credentials
(Note that the security parameter is given implicitly with $M^{\lambda}$), is
a secure credential generator. And

  * •

$\textit{step}_{M^{\lambda}}({\textit{msg},i})$, where msg is the message the
mechanism received (perhaps no message, represented by ${\textit{msg}=\bot}$),
sent from player $i$, is a function that updates the state of the mechanism
and returns a pair $(\textit{msg}s_{0},\textit{msg}s_{1})$ of sets of messages
(maybe empty) to send to the players by their identifiers. It can access and
update the mechanism’s state and the set of credentials public part
$\\{c_{i}^{P}\\}_{i=1}^{n}$.

The mechanism uses a variable $\textit{decide}_{M^{\lambda}}$ that marks which
identifier it decides belongs to the user. The variable’s initial value is
$\bot$. When $M^{\lambda}$ reaches a decision, it updates the variable to an
identifier value.

A _player_ is defined by its _strategy_ , a function that defines its
behavior. Formally,

######  Definition 3 (Strategy).

A _strategy_ $S^{\lambda}$ of a player is a function, parametrized by the
security parameter $\lambda$, that takes a message from the mechanism as input
(which may be empty, denoted by $\bot$), and has access to the player’s state
and credentials $C_{p}^{\sigma}$. It updates the player’s state and returns a
set of messages to be sent back to the mechanism.

We now describe the execution of the system. Full details including pseudocode
are in Appendix A. The execution consists of two parts: _setup_ (Setup
function) and a _main loop_ (Execute function). The setup generates a set of
$n$ credentials using the function $\textit{gen}_{M^{\lambda}}({n})$, and
assigns each player credentials according to the scenario $\sigma$. Then it
assigns an identifier to each player based on
$\gamma_{\textit{ID}}\in\\{0,1\\}$. Whenever a random coin is used by
$M^{\lambda}$ or the players, the result is the next bit of $v$.

Once the setup is complete, the main loop begins and both players
$p\in\\{U,A\\}$ can send messages to the mechanism, each based on her strategy
$S_{p}^{\lambda}$ and set of credentials $C_{p}^{\sigma}$. Time progresses in
discrete steps. The communication network is reliable but asynchronous.
Messages arrive eventually, but there is no bound on the time after they were
sent and no constraints on the arrival order.

This is implemented as follows. The scheduler maintains three sets of pending
messages, one for each entity. The scheduler is parametrized by an ordering
function $\gamma_{\textit{ord}}$ and a random tape $v_{\gamma}$. In each step,
it uses $\gamma_{\textit{ord}}$ to choose a subset of messages (maybe empty)
from each of the pending message sets, and returns them as an ordered list.
The scheduler’s random coins used in $\gamma_{\textit{ord}}$ are taken from
$v_{\gamma}$. The scheduler removes the chosen messages from the pending
messages sets.

Each player receives the messages chosen by the ordering function
$\gamma_{\textit{ord}}$ and sends messages to the mechanism according to her
strategy. These messages are added to the mechanism’s pending messages set.
Similarly, the mechanism receives the messages chosen by
$\gamma_{\textit{ord}}$. After every message msg it receives from player with
identifier $i\in\\{0,1\\}$, the mechanism runs its function
$\textit{step}_{M^{\lambda}}({\textit{msg},i})$ and sends messages to the
players.

In each step, the scheduler checks if $\textit{decide}_{M^{\lambda}}\neq\bot$,
meaning that the mechanism has reached a decision. Once it does, the execution
ends and the player with the matching index (either $0$ or $1$) wins. The
tuple $(\gamma_{\textit{ID}},\gamma_{\textit{ord}},v_{\gamma})$ thus defines
the _scheduler_ ’s behavior. And an execution $E^{\lambda}$ is thus defined by
its parameter tuple
$(M^{\lambda},\sigma,S_{U}^{\lambda},S_{A}^{\lambda},\gamma,v)$; by slight
abuse of notation we write
${E^{\lambda}=(M^{\lambda},\sigma,S_{U}^{\lambda},S_{A}^{\lambda},\gamma,v)}$.

The number of operations that the mechanism and the players can perform in a
single execution step is polynomial in the security parameter $\lambda$. The
number of steps in an execution is thus the minimum between the number of
steps the mechanism takes to decide and $T(\lambda)$. This ensures the
guarantees of the credentials are maintained. We assume that the attacker
cannot affect the delivery time of user messages, in particular, she cannot
perform a denial of service attack (details in Appendix A.1).

We define the _winner_ of an execution as the player with the identifier that
the mechanism decides on in that execution. If the mechanism does not reach a
decision within the execution’s runtime, we say that the execution _times
out_.

###  3.2 Mechanism Success

In an asynchronous environment we cannot guarantee that the mechanism
correctly identifies the user in any scenario within any bounded time due to
the simple fact that the scheduler can delay messages indefinitely. Thus, if
we bound execution time we cannot require termination and must allow the
mechanism to timeout even in scenarios where it supposedly identifies the
user. This allows for a trivial solution where the mechanism always times out.

However, to maintain cryptographic security, execution time must be bounded,
in our case by the polynomial $T(\lambda)$. If we allow the execution to run
longer we can no longer bound the attacker’s probability of guessing
credentials beyond those given to her by the scheduler.

Previous work [44, 45, 46] sidesteps this issue with protocols that use an
abstract signature scheme that cannot be broken indefinitely. However, in our
case this abstraction is not possible as we make claims on general mechanisms
using standard communication channels, so for any bounded message length we
cannot rule out forgery.

We therefore define success as follows. If the mechanism times out in a given
execution, we would like to extend the execution and allow it to succeed in
the extended execution. To extend the execution without violating
cryptographic security, we must increase the security parameter. Intuitively,
we are interested in mechanisms that behave similarly for all security
parameters, e.g., verify a signature and send a message independent of the
signature details. But a different security parameter implies changes to the
mechanism and the behavior of the players and the scheduler, which might
extend the decision time further, beyond the new bound. Therefore, to keep the
extension meaningful, the scheduler must also behave in a similar way for
different security parameters, that is, it is oblivious to the security
parameter and message content. The requirement is that given such a scheduler,
for all sufficiently large security parameters, the mechanism succeeds.

Rather than mechanisms, success is therefore defined for mechanism families
that behaves similarly for different security parameters. A _mechanism family_
${M}$ is a function that maps a security parameter $\lambda$ to a mechanism
$M^{\lambda}$. Similarly, a _strategy family_ $S$ is a function that maps a
security parameter $\lambda$ to a strategy $S^{\lambda}$. A mechanism family
is _successful_ in a scenario $\sigma$ if, for a large enough security
parameter, the user wins against all attacker strategies and schedulers.
Formally,

######  Definition 4 (Mechanism success).

A mechanism family ${M}$ is _successful_ in a scenario $\sigma$, if there
exists a user strategy family $S_{U}$ such that for all attacker strategy
families $S_{A}$, schedulers $\gamma$, and random tapes $v$, there exists a
security parameter $\lambda_{0}$ such that:

  1. 1.

for all security parameters $\lambda\geq\lambda_{0}$, the user wins the
execution
$E^{\lambda}=(M^{\lambda},\sigma,S_{U}^{\lambda},S_{A}^{\lambda},\gamma,v)$.
And,

  2. 2.

for all security parameters $\lambda$, either the user wins or the execution
times out.

Such a user strategy family $S_{U}$ is a _winning user strategy family_ in
$\sigma$ with $M$. Otherwise, the mechanism family _fails_.

The set of scenarios in which the mechanism succeeds is its _profile_ (as
Maram et al. [16] defined for a synchronous network).

######  Definition 5 (Profile [16]).

A _profile_ is a set of scenarios. The _profile of a mechanism family_ $M$,
denoted $\Pi({M})$, is the set of all scenarios in which $M$ succeeds.

We are now ready to define the _asynchronous authentication problem_.

######  Definition 6 (Asynchronous authentication).

Given a profile $\pi$, a mechanism family $M$ solves the _$\pi$ asynchronous
authentication_ problem if $M$ is successful in all scenarios in $\pi$ (maybe
more), i.e., ${\pi\subseteq\Pi({M})}$.

In the asynchronous setting, the profile defines a relation between any two
mechanism families $M_{1}$ and $M_{2}$ with the same number of credentials.
The following definition is similar to that given by Maram et al. [16] for a
synchronous network, but as we will consider individual credential
probabilities, our definition is permutation sensitive.

######  Definition 7 (Mechanisms order).

A mechanism family $M_{1}$ _dominates_ (resp., _strictly dominates_) a
mechanism family $M_{2}$ with the same number of credentials if the profile of
$M_{1}$ is a superset (resp., strict superset) of the profile of $M_{2}$:
$\Pi({M_{2}})\subseteq\Pi({M_{1}})$ (resp.,
$\Pi({M_{2}})\subset\Pi({M_{1}})$).

Two mechanism families $M_{1}$ and $M_{2}$ are _equivalent_ if they have the
same profile $\Pi({M_{1}})=\Pi({M_{2}})$. And _incomparable_ if neither
dominates the other $\Pi({M_{1}})\nsubseteq\Pi({M_{2}})$ and
$\Pi({M_{2}})\nsubseteq\Pi({M_{1}})$.

##  4 Maximal Mechanisms

Having defined partial ordering on mechanisms, we proceed to identify _maximal
mechanisms_ , i.e., mechanisms that are not strictly dominated. We show that
for any mechanism family there exists a dominating mechanism family that is a
Boolean function of the credentials’ availability (§4.1). Then we show that
mechanism families defined by monotonic Boolean functions are maximal, and all
maximal mechanisms are equivalent to a Boolean mechanism (§4.2).

###  4.1 Domination by Boolean Mechanisms

We show that any mechanism family, is dominated by a mechanism family that is
a Boolean function of the credentials’ availability. We take 4 similar steps.
First, we show that for all mechanism families there exists a dominating _one-
shot_ mechanism family in which mechanisms decide based on up to a single
message from each player (§4.1.2). Second, we show that decisions can be made
solely on credential availability proofs (§4.1.3). Then we show that
randomness does not help (§4.1.4). Finally, we show that for any deterministic
mechanism family, there exists a dominating mechanism defined by a monotonic
Boolean function of the credentials’ availability (§4.1.5).

####  4.1.1 Step template

Each step in our proof has the following parts: Given a mechanism family
$M_{1}$ we show it is dominated by a mechanism family $M_{2}$ with a certain
property. We prove constructively by defining a mechanism family $M_{2}$ and
show the required property holds. The domination proof takes advantage of a
mechanism’s ability to simulate the execution of another mechanism. That is,
for $\lambda\in\mathbb{N}^{+}$ the mechanism $M_{2}^{\lambda}$ takes a
mechanism $M_{1}^{\lambda}$, two strategies $S_{0}$ and $S_{1}$, the sets of
credentials each strategy uses $C_{0}$ and $C_{1}$, an ordering function
$\gamma_{\textit{ord}}$, a scheduler random tape $v_{\gamma}$, and a random
tape $v$, and runs
$\textit{Execute}(M_{1}^{\lambda},S_{0},C_{0},S_{1},C_{1},\gamma_{\textit{ord}},v_{\gamma},v)$
(Appendix A). The simulation result is the identifier that
$\textit{decide}_{M_{1}^{\lambda}}$ gets during the execution of Execute, if
it terminates, and $\bot$ if it times out.

######  Note 1 (Mechanism’s computational resorces).

In the following proofs, we assume that the constructed mechanism has
sufficient computational resources to simulate the original mechanism within a
single step. At the end of this section we show that there always exists a
dominating polynomial $O(\lambda)$ mechanism.

######  Note 2 (Plaintext credentials).

In the following proofs, we assume the user sends the secret part of her
credentials (as with passwords). Although this is not always the case (e.g.,
with cryptographic signatures), this is only a theoretical construction and
does not suggest that the user should generally send her secrets in plaintext.
In practice, she must only be able to prove she can access them.

######  Note 3 (Mechanism as a function).

When constructing a mechanism $M_{\textit{new}}^{\lambda}$ given a mechanism
$M^{\lambda}$, we use the notation $M_{\textit{new}}^{\lambda}(M^{\lambda})$
to denote the mechanism $M_{\textit{new}}^{\lambda}$ is a function of
$M^{\lambda}$. When it is clear from the context, we omit the argument
$M^{\lambda}$ and write $M_{\textit{new}}^{\lambda}$.

####  4.1.2 One-shot Mechanisms

We define a _one-shot_ (OS) mechanism as one that, in every execution, reaches
a decision based only on the first message it receives (if any) from each
player. If a player sends multiple messages, the mechanism ignores all but the
first it receives.

######  Definition 8 (One-shot mechanism).

A mechanism $M^{\lambda}$ is a _one-shot mechanism_ if for all scenarios
$\sigma$, schedulers $\gamma$, and random tapes $v$, and for all user
strategies $S_{U}^{\lambda},S_{U}^{\prime\lambda}$ and attacker strategies
$S_{A}^{\lambda}$, $S_{A}^{\prime\lambda}$ such that the first message that
$M^{\lambda}$ receives from each player (if any) in the executions
${E_{1}=(M^{\lambda},\sigma,S_{U}^{\lambda},S_{A}^{\lambda},\gamma,v)}$ and
${E_{2}=(M^{\lambda},\sigma,S_{U}^{\prime\lambda},S_{A}^{\prime\lambda},\gamma,v)}$
is the same and in the same order, then $M^{\lambda}$ reaches the same
decision or times out in both executions.

We say that a mechanism family has a property if all the mechanisms in the
family have the property. For example a mechanism family is a _one-shot
mechanism family_ if all the mechanisms in the family are one-shot mechanisms.

1

_$\textit{step}_{M_{\textit{OS}}^{\lambda}}({\textit{msg},i})$_

2

3if  _$\textit{msg}=\bot$_ then // No message was received

4 $\textit{return }\bot,\bot$

5 if  _$\textit{processing}_{i}=1$_ then // A message was received from $i$
before

6 $\textit{return }\bot,\bot$

7

$\textit{processing}_{i}\leftarrow 1$

// The mechanism has received a message from $i$

$S_{i},C_{i}\leftarrow\textit{extractStrategy}(\textit{msg})$

// Extract the strategy from the message

8 $S_{1-i},C_{i}\leftarrow\bot,\bot$

9

10 if  _$S_{i}=\bot$_ then

$\textit{decide}_{M_{\textit{OS}}^{\lambda}}\leftarrow 1-i$

// Invalid strategy means the other player wins

11

12 else

$\textit{decide}_{M_{\textit{OS}}^{\lambda}}\leftarrow\textit{Execute}(M^{\lambda},S_{0},C_{0},S_{1},C_{1},\gamma_{\textit{ord}}^{\textit{v}},v_{\gamma},v^{\prime})$

// Simulating the main loop of $M^{\lambda}$

13

14 $\textit{return }\bot,\bot$

15

Algorithm 1 $M_{\textit{OS}}^{\lambda}(M^{\lambda})$’s step function

Given any mechanism family we construct a dominating one-shot mechanism family
by simulating the original mechanism’s execution.

######  Construction 1.

For all $\lambda\in\mathbb{N}^{+}$, we define $M_{\textit{OS}}^{\lambda}$ by
specifying the functions $\textit{gen}_{M_{\textit{OS}}^{\lambda}}({\cdot})$
and $\textit{step}_{M_{\textit{OS}}^{\lambda}}({\cdot})$. The credentials’
generation function $\textit{gen}_{M_{\textit{OS}}^{\lambda}}({\cdot})$ is the
same as $\textit{gen}_{M^{\lambda}}({\cdot})$. The mechanism’s step function
is described in Algorithm 1.

A behavior of $M_{\textit{OS}}^{\lambda}$ is as follows: If it does not
receive a message during its execution, it times out. If it receives multiple
messages from a player, it ignores all but the first one (lines 1-1). This is
implemented using the variables $\textit{processing}_{0}$ and
$\textit{processing}_{1}$ that indicate whether the mechanism has received a
message from player $0$ and $1$, respectively, both initialized to $0$. If
$M_{\textit{OS}}^{\lambda}$ receives a message that is not a valid strategy
and credentials pair, then it decides the identifier of the other player (line
1).

Consider the first message it receives. If it is a valid strategy and
credentials pair, then $M_{\textit{OS}}^{\lambda}$ simulates an execution of
$M^{\lambda}$ (line 1) with the given strategy and credentials while setting
both the opponent’s strategy and credentials to $\bot$ each (lines 1-1). It
uses a scheduler random tape $v_{\gamma}$ and an execution random tape
$v^{\prime}$ drawn from $v$, and an ordering function
$\gamma_{\textit{ord}}^{v_{\gamma}}$ that chooses the time and ordering of
message delivery randomly based on $v_{\gamma}$. If $M^{\lambda}$’s execution
decides, then $M_{\textit{OS}}^{\lambda}$ decides the same value. Otherwise,
$M_{\textit{OS}}^{\lambda}$ waits for the next message.

If a message arrives from the other player, then similar to the previous case
$M_{\textit{OS}}^{\lambda}$ simulates an execution of $M^{\lambda}$ with the
given strategy and credentials while setting the opponent’s to $\bot$. And
again, if $M^{\lambda}$’s simulated execution decides, then
$M_{\textit{OS}}^{\lambda}$ decides the same value. Otherwise,
$M_{\textit{OS}}^{\lambda}$ waits until $T(\lambda)$ execution steps pass and
then times out. So it can decide after receiving the first message from either
player or time out.

The mechanism family $M_{\textit{OS}}(M)$ is one-shot as each of its
mechanisms decides based only on the first message it receives from each
player. To prove it dominates $M$, we first show that the attacker’s message
does not lead to her wining.

######  Lemma 1.

Let $\sigma$ be a scenario and let $M$ be a mechanism family successful in
$\sigma$. Then, for all $\lambda$ and all executions of
$M_{\textit{OS}}^{\lambda}(M^{\lambda})$ in scenario $\sigma$ in which the
function $\textit{step}_{M_{\textit{OS}}^{\lambda}(M^{\lambda})}({\cdot})$
receives a message from the attacker for the first time, either the function
sets $\textit{decide}_{M_{\textit{OS}}^{\lambda}}$ to the user’s identifier or
the simulated execution of $M^{\lambda}$ times out.

###### Proof.

Let $\sigma$ be a scenario and let $M$ be a mechanism family successful in
$\sigma$. Let $\lambda\in\mathbb{N}^{+}$ and consider an execution of
$M_{\textit{OS}}^{\lambda}$ in scenario $\sigma$ in which the function
$\textit{step}_{M_{\textit{OS}}^{\lambda}}({\cdot})$ receives an attacker’s
message for the first time. Denote the identifier of the attacker by
$i\in\\{0,1\\}$. If the attacker’s message is not a valid encoding of a
strategy and credentials set, then $M_{\textit{OS}}^{\lambda}$ decides the
identifier of the user, and we are done because it sets
$\textit{decide}_{M_{\textit{OS}}^{\lambda}}$ to the user’s identifier.

Otherwise, the attacker’s message is an encoding of a valid strategy and
credentials pair $(S_{A}^{\lambda},~{}C_{A}^{\lambda})$. In this case,
$M_{\textit{OS}}^{\lambda}$ sets the strategies and credentials to
$S_{i}=S_{A}^{\lambda}$, $C_{i}=C_{A}^{\lambda}$, $S_{1-i}=\bot$, and
$C_{1-i}=\bot$, $\gamma_{\textit{ord}}^{v_{\gamma}}$, $v_{\gamma}$ and
$v^{\prime}$ as in the definition of $M_{\textit{OS}}^{\lambda}$, and
simulates $M^{\lambda}$’s execution by running
$\textit{Execute}(M^{\lambda},S_{0},C_{0},S_{1},C_{1},\gamma_{\textit{ord}}^{v_{\gamma}},v_{\gamma},v^{\prime})$.
If the simulation times-out or returns the identifier of the user we are done.
The only remaining option is that the simulation returns the identifier of the
attacker. To show this is impossible, assume by contradiction that the
attacker wins in this simulated execution.

First, we show that there exists an execution of $M^{\lambda}$ that is
identical to the simulated one. Let
${\gamma=(\gamma_{\textit{ID}}^{\textit{OS}},\gamma_{\textit{ord}}^{v_{\gamma}},v_{\gamma})}$
be a scheduler such that the user gets the same identifier as in the execution
of $M_{\textit{OS}}^{\lambda}$, with the same ordering function and scheduler
random tape that $M_{\textit{OS}}^{\lambda}$ uses to simulate $M^{\lambda}$’s
main loop. And let $v_{M}$ be a random tape such that when the execution
$E^{\lambda}=(M^{\lambda},\sigma,\bot,S_{A}^{\lambda},\gamma,v_{M})$ reaches
the main loop, all the next bits of $v_{M}$ are equal to $v^{\prime}$. Note
that the main loop of $E^{\lambda}$ is the same as the one
$M_{\textit{OS}}^{\lambda}$ simulates in $E_{\textit{OS}}^{\lambda}$. And the
attacker wins in the execution $E^{\lambda}$ (by the contradiction
assumption).

We thus established a simulated execution in which the attacker wins, and in
this simulation there exists a time $\tau<T(\lambda)$ when the simulated
$M^{\lambda}$ decides the identifier of the attacker. Since $M$ is successful
in scenario $\sigma$, there exists a winning user strategy family $S_{U}$. Let
$\gamma^{\prime}$ be a scheduler such that in the execution
$E^{\prime\lambda}=(M^{\lambda},\sigma,S_{U}^{\lambda},S_{A}^{\lambda},\gamma^{\prime},v_{M})$
it behaves like $\gamma$ except $M^{\lambda}$ receives the user’s messages not
before $\tau$ and before $T(\lambda$). Such a scheduler exists since the
communication is asynchronous and message delivery time is unbounded.

At any time step before $\tau$, the mechanism $M^{\lambda}$ sees the same
execution prefix whether it is in the execution $E^{\lambda}$ with an empty
user strategy or in the execution $E^{\prime\lambda}$ with a winning user
strategy. Thus, it cannot distinguish between the case where it is in
$E^{\lambda}$ or $E^{\prime\lambda}$ at $\tau$. Since in $E^{\lambda}$ the
mechanism $M^{\lambda}$ decides at $\tau$, $M^{\lambda}$ must decide the same
value at $\tau$ in $E^{\prime\lambda}$. That is, the attacker wins also in the
execution $E^{\prime\lambda}$, contradicting the fact that $S_{U}$ is a
winning user strategy for $M$ in $\sigma$. Thus, the attacker cannot win in
the simulated execution of $M^{\lambda}$. ∎

Now we can prove domination.

######  Proposition 1.

For all profiles $\pi$, an authentication mechanism family that solves the
$\pi$ asynchronous authentication problem is dominated by a one-shot mechanism
family.

###### Proof.

Assume that $M$ is successful in a scenario $\sigma$. Then, there exists a
user strategy family $S_{U}$ such that for every attacker strategy family
$S_{A}$, scheduler $\gamma$, and random tape $\widetilde{v}$, there exists a
security parameter $\lambda_{\textit{suc}}$, such that for all
$\lambda>\lambda_{\textit{suc}}$, the user wins the corresponding execution
$(M^{\lambda},\sigma,S_{U}^{\lambda},S_{A}^{\lambda},\gamma,\widetilde{v})$.
And for all $\lambda>0$, either the user wins or the execution times out.

We now show that $M_{\textit{OS}}$ is successful in scenario $\sigma$ as well.
Denote by $S_{U}^{\textit{OS}}$ the user strategy family such that for all
$\lambda>0$, $S_{U}^{\textit{OS},\lambda}$ sends an encoding of the strategy
$S_{U}^{\lambda}$ from the winning user strategy family $S_{U}$ and a set of
credentials $C_{U}\subseteq C_{U}^{\sigma}$ that $S_{U}^{\lambda}$ uses in a
single message on the first step. And consider any execution of
$M_{\textit{OS}}^{\lambda}$ in scenario $\sigma$ with the user strategy
$S_{U}^{\textit{OS},\lambda}$. Note: In the Setup function of an execution,
the first player in the tuple is always the user and the second is the
attacker. However, in the Execute function, the first player is the player
with identifier $0$, which can be the user or the attacker, and the second is
the player with identifier $1$.

As for all $\lambda>0$, $S_{U}^{\textit{OS},\lambda}$ sends a message in the
first step, there exists a security parameter $\lambda_{0}^{\textit{OS}}$ such
that for all $\lambda^{\textit{OS}}>\lambda_{0}^{\textit{OS}}$, the user’s
message arrives before $T(\lambda)$. It might be the case that an attacker’s
message arrives first. If the mechanism does not receive any messages, it
times out. This is possible only if $\lambda<\lambda_{0}^{\textit{OS}}$, as
the user strategy we chose does send a message. Otherwise,
$M_{\textit{OS}}^{\lambda}$ eventually receives and processes at least one
message during its execution, then we consider two cases separately: a user’s
message arrives first, or an attacker’s message arrives first.

Denote by $i\in\\{0,1\\}$ the identifier of the player whose message arrives
first. If the user’s message msg arrives first with the encoded strategy and
credential set
${(S_{U}^{\lambda},~{}C_{U})=\textit{extractStrategy}(\textit{msg})}$, then
$M_{\textit{OS}}^{\lambda}$ sets the strategies to $S_{i}=S_{U}^{\lambda}$,
$C_{i}=C_{U}$, ${S_{1-i}=\bot}$, and $C_{1-i}=\bot$, the scheduler random tape
$\gamma_{v}$, the ordering function $\gamma_{\textit{ord}}^{v_{\gamma}}$, and
the random tape $v^{\prime}$ as described in $M_{\textit{OS}}$’s definition,
and simulates $M^{\lambda}$’s execution by running
$\textit{Execute}(M^{\lambda},S_{0},C_{0},S_{1},C_{1},\gamma_{\textit{ord}}^{v_{\gamma}},v_{\gamma},v^{\prime})$.
Denote by
$\gamma=(\gamma_{\textit{ID}}^{\textit{OS}},\gamma_{\textit{ord}}^{v_{\gamma}},v_{\gamma})$
the scheduler such that the user gets the same identifier as in the execution
of $M_{\textit{OS}}^{\lambda}$, with the same ordering function and scheduler
random tape that $M_{\textit{OS}}^{\lambda}$ uses to simulate $M^{\lambda}$’s
main loop. Because $S_{U}$ is a winning user strategy family in $M$, there
exists $\lambda_{\textit{suc}}$ such that for all
$\lambda>\lambda_{\textit{suc}}$, the user wins the execution
$E^{\lambda}=(M^{\lambda},\sigma,S_{U}^{\lambda},\bot,\gamma,v^{\prime})$. If
$\lambda>\lambda_{\textit{suc}}$, the simulation terminates and returns the
user’s identifier $i$, so $M_{\textit{OS}}^{\lambda}$ also returns $i$.

Otherwise, as $\lambda\leq\lambda_{\textit{suc}}$, and because $S_{U}$ is a
winning user strategy family for $M^{\lambda}$, if the simulation terminates
then it must return the identifier of the user. And so does the mechanism
$M_{\textit{OS}}^{\lambda}$. If the simulation does not terminate, then
$M_{\textit{OS}}^{\lambda}$ waits for the next message from the other player
(the attacker). If no message arrives before $T(\lambda)$, then
$M_{\textit{OS}}^{\lambda}$ times out as well (note this is possible only if
$\lambda\leq\lambda_{\textit{suc}}$ because otherwise
$M_{\textit{OS}}^{\lambda}$ would have already returned the user’s
identifier). Otherwise, $M_{\textit{OS}}^{\lambda}$’s step function receives
the attacker’s message, and by Lemma 1, either $M_{\textit{OS}}^{\lambda}$
decides the user or the simulated execution of $M^{\lambda}$ times out. If the
simulation times out, then $M_{\textit{OS}}^{\lambda}$ times out as well.
Overall we showed that if $\lambda>\lambda_{0}^{\textit{OS}}$, a user’s
message is received by $M_{\textit{OS}}^{\lambda}$. And if the user’s message
arrives first, then if $\lambda>\lambda_{\textit{suc}}$, the user wins, and
for all $\lambda$, either the user wins or the execution times out.

Now assume the attacker’s message arrives first to
$M_{\textit{OS}}^{\lambda}$. Again by Lemma 1, either
$M_{\textit{OS}}^{\lambda}$ decides the user or the simulated execution of
$M^{\lambda}$ in $M_{\textit{OS}}^{\lambda}$ times out. If
$M_{\textit{OS}}^{\lambda}$ decides the user, then we are done. Otherwise, the
simulation times out, and $M_{\textit{OS}}^{\lambda}$ waits for the next
message from the other player (the user). If no other message arrives before
$T(\lambda)$, then $M_{\textit{OS}}^{\lambda}$ times out. This is possible
only if $\lambda<\lambda_{0}^{\textit{OS}}$ by definition of
$\lambda_{0}^{\textit{OS}}$.

Otherwise, $M_{\textit{OS}}^{\lambda}$ receives the user’s message with her
encoded strategy and credentials set. Then similar to the previous case,
$M_{\textit{OS}}^{\lambda}$ sets the strategies, credential sets, scheduler
random tape, ordering function, and random tape as described in Construction
1, and simulates $M^{\lambda}$’s execution by running
$\textit{Execute}(M^{\lambda},S_{0},C_{0},S_{1},C_{1},\gamma_{\textit{ord}}^{v_{\gamma}},v_{\gamma},v^{\prime})$.
By the same argument as before, we get that if
$\lambda>\lambda_{\textit{suc}}$, the simulation terminates and returns the
user’s identifier, so $M_{\textit{OS}}^{\lambda}$ also returns it. Otherwise,
$\lambda\leq\lambda_{\textit{suc}}$, if the simulation terminates, it must
return the identifier of the user. And so does the mechanism
$M_{\textit{OS}}^{\lambda}$. If the simulation does not terminate, then
$M_{\textit{OS}}^{\lambda}$ times out.

Overall we showed that if
$\lambda>max(\lambda_{\textit{suc}},\lambda_{0}^{\textit{OS}})$, the user
wins. And for $\lambda\leq
max(\lambda_{\textit{suc}},\lambda_{0}^{\textit{OS}})$, either the user wins
or the execution times out. Therefore, $M_{\textit{OS}}$ is successful in
scenario $\sigma$. We thus conclude that the one shot mechanism family
$M_{\textit{OS}}$ dominates $M$. ∎

####  4.1.3 Credential-based mechanisms

A one-shot mechanism is a _credential-based_ mechanism if it reaches a
decision based only on a function of the credentials it receives from players.

######  Definition 9 (Credential-based mechanism).

A mechanism $M^{\lambda}$ is a _credential-based_ mechanism if it is a one
shot mechanism and for all scenarios $\sigma$, schedulers $\gamma$ and random
tapes $v$, and for all user and attacker strategies
$S_{U}^{\lambda},S_{U}^{\prime\lambda},S_{A}^{\lambda}$ and
$S_{A}^{\prime\lambda}$ such that $S_{U}^{\lambda}$ and $S_{A}^{\lambda}$ send
only messages that are subsets of the corresponding player’s credentials’
vector, and $S_{U}^{\prime\lambda}$ and $S_{A}^{\prime\lambda}$ send messages
with the same subsets of credentials but with any additional strings, then
$M^{\lambda}$ reaches the same decision in both executions
$E_{1}=(M^{\lambda},\sigma,S_{U}^{\lambda},S_{A}^{\lambda},\gamma,v)$ and
$E_{2}=(M^{\lambda},\sigma,S_{U}^{\prime\lambda},S_{A}^{\prime\lambda},\gamma,v)$.

######  Lemma 2.

For all one-shot mechanism families $M_{\textit{OS}}$ there exists a
credential-based mechanism family $M_{\textit{cred}}$ that dominates
$M_{\textit{OS}}$.

The proof of Lemma 2 is similar to that of Proposition 1 and is omitted for
brevity. The key difference is the observation that any message a player can
send is a function of (1) common information [47] available to everyone, (2)
credentials of the sender, and (3) randomly bits.

Denote by $M_{\textit{OS}}$ a one-shot mechanism family. If a player has a
winning strategy for $M_{\textit{OS}}$, knowing some common information, her
credentials, and the random bits, she can generate the messages she needs to
send to win in the credential-base mechanism family as well.

Formally, for all $\lambda\in\mathbb{N}^{+}$ we define a function
$S_{\textit{OS}}^{\lambda}$ that maps a set of credentials to a strategy. Let
$c$ be a set of credentials known to player $i\in\\{0,1\\}$, the function
$S_{\textit{OS}}^{\lambda}(c)$ returns a strategy for player $i$ for
$M_{\textit{OS}}^{\lambda}$ using $c$ such that if the first message that
$M_{\textit{OS}}^{\lambda}$ receives is from player $i$, it leads to player
$i$ winning the execution. If no such a strategy exists,
$S_{\textit{OS}}^{\lambda}(c)=\bot$. Then the construction of a credential-
based mechanism $M_{\textit{cred}}^{\lambda}$ is similar to that of
$M_{\textit{OS}}^{\lambda}$ with the following change: Instead of extracting
the strategy and credentials from the message, $M_{\textit{cred}}^{\lambda}$
uses the function $S_{\textit{OS}}^{\lambda}$ to obtain the strategy given the
credentials.

The mechanism family $M_{\textit{cred}}$ is credential-based as each of its
mechanisms is a one-shot mechanism that decides based only on the credentials
it receives.

####  4.1.4 Deterministic mechanisms

Next we show that using randomness to determine if a player is the user or the
attacker does not help the mechanism design.

######  Lemma 3.

For all credential-based mechanism families $M_{\textit{cred}}$ there exists a
deterministic credential-based mechanism family $M_{\textit{det}}$ that
dominates $M_{\textit{cred}}$.

Denote by $M_{\textit{cred}}$ a credential-based authentication mechanism
family. A deterministic mechanism family $M_{\textit{det}}$ that behaves the
same as $M_{\textit{cred}}$ except that its step function does not use any
randomness can be constructed by artificially replacing the randomness used in
$\textit{step}_{M_{\textit{cred}}^{\lambda}}({\cdot})$ with a stream of
zeroes. Thus, preventing $M_{\textit{det}}^{\lambda}$ from using any
randomness in its step function and making it deterministic. Again, the proof
of Lemma 3 is similar to that of Proposition 1 and Lemma 2 and is omitted for
brevity.

####  4.1.5 Boolean mechanisms

We show that every deterministic credential-based mechanism is dominated by a
mechanism defined by a monotonic Boolean function.

######  Definition 10 (Boolean mechanism).

Given a Boolean function on $n$ variables
${f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}}$, we define the _Boolean mechanism_
$M_{f}$ as follows: The credential generation function
$\textit{gen}_{M_{f}}({\cdot})$ is a secure credential generation function.
The step function $\textit{step}_{M_{f}}({\textit{msg},i})$ receives a single
message msg from a player with identifier $i$ that contains a set of
credentials $c$. The mechanism $M_{f}$ extracts the credentials’ availability
vector $q$ from $c$. If $c$ is not a valid set of credentials, $M_{f}$ decides
the identifier of the other player $1-i$. If $f(q)=1$, $M_{f}$ decides $i$.
Otherwise, $f(q)=0$ and the mechanism decides $1-i$. If the $f$ is monotonic,
then $M_{f}$ is a _monotonic Boolean mechanism_.

######  Lemma 4.

Let $M_{\textit{det}}$ a deterministic credential-based mechanism family and
let the function $f$ be as constructed above. Then $f$ is monotonic.

Intuitively, for a deterministic credential-based mechanism, the only
information that matters is whether a player can prove she has a set of
credentials or not. And if a player can authenticate to a mechanism, being
able to access additional credentials will not prohibit her from
authenticating to the same mechanism.

######  Construction 2.

Denote by $M_{\textit{det}}$ a deterministic credential-based mechanism family
with $n$ credentials. Define $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ as follows:
For all $q\in\\{0,1\\}^{n}$:

$\displaystyle
f(q)=\begin{cases}\text{1}&\>q\in\\{\sigma_{U}\in\\{0,1\\}|\exists\sigma=(\sigma_{U},\sigma_{A})\in\Pi({M_{\textit{det}}})\\}\\\
\text{0}&\>\text{otherwise}\end{cases}$

$f$ is the function derived from $M_{\textit{det}}$. For all $\lambda>0$,
$M_{f}^{\lambda}$ is the mechanism defined by $f$, with the function
$\textit{gen}_{M_{f}^{\lambda}}({}):=\textit{gen}_{M_{\textit{det}}^{\lambda}}({})$.
It is easy to see that $f$ is well-defined. It remains to show that it is
monotonic and that it dominates $M_{\textit{det}}$.

######  Lemma 5.

Let $M_{\textit{det}}$ a deterministic credential-based mechanism family and
let the function $f$ be the function derived from $M_{\textit{det}}$. Then $f$
is monotonic.

###### Proof.

Given two binary vectors ${x},{y}\in\\{0,1\\}^{n}$, we denote ${x}\geq{y}$ if
for every index $i\in[n]$, ${x}_{i}\geq{y}_{i}$. In other words, if an element
is set to $1$ in ${y}$, it is also set to $1$ in ${x}$.

We now prove that the function $f$ is monotonic. Let ${x},{y}\in\\{0,1\\}^{n}$
such that ${y}\geq{x}$ and $f(x)=1$. By definition of $f$, $f(x)=1$ if and
only if there exists a scenario $\sigma$ in which the user’s availability
vector is $x$ and $M_{\textit{det}}$ succeeds in $\sigma$. Let $S_{U}$ be the
winning user strategy family for $M_{\textit{det}}$ in $\sigma$.

As $M_{\textit{det}}$ is a credential-based mechanism, for all $\lambda$,
$S_{U}^{\lambda}$ sends only a set of credentials $c_{U}^{\lambda}$ in a
single message. Now consider the scenario $\sigma^{\prime}$ in which the
user’s availability vector is $y$ and the attacker’s availability vector is
the same as in $\sigma$. The user can use the exact same strategy
$S_{U}^{\lambda}$ in $\sigma^{\prime}$, as she has access to all credentials
she has in $\sigma$ and more. Thus, for all attacker strategy families
$S_{A}$, schedulers $\gamma$ and random tapes $v$, there exists a security
parameter $\lambda_{\textit{suc}}$ (same as in $\sigma$) such that for all
$\lambda>\lambda_{\textit{suc}}$, the user wins the execution
$E^{\lambda}=(M_{\textit{det}}^{\lambda},\sigma^{\prime},S_{U}^{\lambda},S_{A}^{\lambda},\gamma,v)$.
And for all $\lambda$, either the user wins or the execution either times out.
Therefore, $M_{\textit{det}}$ succeeds in $\sigma^{\prime}$ as well,
${f(y)=1}$ and $f$ is monotonic. ∎

To prove Lemma 4, we show that if $M_{\textit{det}}$ is successful in a
scenario $\sigma$, then $M_{f}$ is successful in $\sigma$ as well. We build on
the observation that based on the scheduler and the security parameter
$\lambda>0$, an execution of $M_{f}^{\lambda}$ has 3 possible paths: either
(1) $M_{f}^{\lambda}$ receives no message before $T(\lambda$), thus it times
out. Or (2) the user’s message arrives first, with her set of credentials
corresponding to the availability vector $\sigma_{U}$. As $M_{\textit{det}}$
is successful in $\sigma$, by definition of $f$ we get that $f(\sigma_{U})=1$
and $M_{f}^{\lambda}$ decides the user.

The last possibility is that (3) the attacker’s message arrives first, if it
is not a valid set of credentials, then $M_{f}^{\lambda}$ decides the user.
Otherwise, if it is a valid set of credentials, we show that it is not
possible that $f$ evaluates to $1$ on the attacker’s availability vector. The
proof is somewhat similar to that of Lemma 1 and is done by contradiction. If
$f$ evaluates to $1$ on the attacker’s availability vector, then there exists
two execution prefixes of $M_{\textit{det}}^{\lambda}$ that are
indistinguishable to the mechanism $M_{\textit{det}}^{\lambda}$ and lead to
the attacker winning. In one of which the attacker wins, although the user
uses her winning strategy, contradicting the fact that $M_{\textit{det}}$ is
successful in $\sigma$. Thus, $M_{f}^{\lambda}$ decides the user. As in all
cases, if a message arrives to $M_{f}^{\lambda}$, then $M_{f}^{\lambda}$
decides the user. We conclude that $M_{f}$, is a monotonic Boolean mechanism
family that dominates $M_{\textit{det}}$. The proof can be found in Appendix
B.

####  4.1.6 Any mechanism is dominated by a Boolean one

We now show that every mechanism is dominated by a monotonic Boolean
mechanism.

######  Theorem 1.

For all profiles $\pi$, for all mechanism families $M$ that solve the
$\pi$-asynchronous authentication problem, there exists a monotonic Boolean
mechanism family $M_{f}$ that dominates $M$.

###### Proof.

Let $\pi$ be a profile and let $M$ be a mechanism family that solves the $\pi$
asynchronous authentication problem. By Proposition 1 there exists a one-shot
mechanism family $M_{\textit{OS}}$ dominating $M$, from Lemma 2 there exists a
credential-based mechanism family $M_{\textit{cred}}$ dominating
$M_{\textit{OS}}$, and by Lemma 3, $M_{\textit{cred}}$ is dominated by a
deterministic credential-based mechanism family $M_{\textit{det}}$. Finally,
by Lemma 4 there exists a monotonic Boolean mechanism family that dominates
$M_{\textit{det}}$. Overall we get that any mechanism family is dominated by a
monotonic Boolean mechanism family. ∎

Note that it is not true that for every mechanism there exists an equivalent
Boolean mechanism. We show an example of a mechanism family such that there
exists no equivalent monotonic Boolean mechanism family.

######  Example 1.

Let $c_{1},c_{2}$ be two credentials and consider a mechanism $M$ that if it
receives both credentials, it decides identifier of the sender, if it receives
only one credential, it decides an identifier uniformly at random. Otherwise,
if it receives no credentials, it does nothing. It is easy to confirm that the
profile of $M$ includes only the scenario where both credentials are available
to the user and not to the attacker. That is, $\Pi({M})=\\{((1,1),(0,0))\\}$.
However, there exists no Boolean mechanism with the same profile.

There are six monotonic Boolean functions with two variables. Two of which are
the constant functions $f_{1}(v)=0$ and $f_{2}(v)=1$ for all
$v\in\\{0,1\\}^{2}$ and one can easily confirm that their profiles are empty.
The other four functions are $f_{3}(c_{1},c_{2})=c_{1}$,
$f_{4}(c_{1},c_{2})=c_{2}$, $f_{5}(c_{1},c_{2})=c_{1}\vee c_{2}$, and
$f_{6}(c_{1},c_{2})=c_{1}\wedge c_{2}$. None of these functions has a profile
that includes only a single scenario.

###  4.2 Monotonic Boolean Mechanisms are Maximal

We now prove that every non-trivial monotonic Boolean mechanism is maximal.
First, we show that a Boolean mechanism family is successful in a scenario
$(\sigma_{U},\sigma_{A})$ if and only if the user has sufficient credentials
and the attacker does not, that is, $f(\sigma_{U})=1$ and $f(\sigma_{A})=0$.
The proof can be found in Appendix C.

As the success of a mechanism family $M_{f}$ in a given scenario is determined
solely by the function $f$, we omit the notation of mechanism families and
assume that the security parameter is sufficiently large so that the mechanism
receives at least one message from the user (if sent).

######  Observation 1.

Let $M_{f}$ be a monotonic Boolean mechanism defined by the function $f$. Let
$T=\\{v\in\\{0,1\\}^{n}\mid f(v)=1\\}$ and let $F=\\{v\in\\{0,1\\}^{n}\mid
f(v)=0\\}$. The profile of $M_{f}$ is the Cartesian product of $T$ and $F$.

$\Pi({M_{f}})=\\{(\sigma_{U},\sigma_{A})\in\\{0,1\\}^{n}\times\\{0,1\\}^{n}\mid\sigma_{U}\in
T,\sigma_{A}\in F\\}.$

And the profile’s size is $|\Pi({M_{f}})|=|T|\cdot|F|$.

We intend to gradually build the mechanism’s function. To this end, we recall
the definition of a partially-defined Boolean function—a function that defines
output values for a subset of the Boolean vectors.

######  Definition 11 (Partially-defined Boolean function).

[48] A _partially-defined Boolean function_ (or _partial Boolean function_) is
a pair of disjoint sets $(T,F)$ of binary $n$-vectors. The set $T$ denotes the
set of true vectors and $F$ denotes the set of false vectors. A Boolean
function ${f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}}$ is called an _extension_ of
$(T,F)$ if $f(x)=1$ for all $x\in T$ and $f(y)=0$ for all $y\in F$.

We extend the definition of a Boolean mechanism to a partial Boolean
mechanism.

######  Definition 12 (Partial Boolean mechanism).

Given a partial Boolean function on $n$ variables $(T,F)$, we define the
mechanism $M_{(T,F)}$ as follows: The credential generation function
$\textit{gen}_{M_{(T,F)}}({\cdot})$ is a secure credential generation
function. The step function $\textit{step}_{M_{(T,F)}}({\textit{msg},i})$
receives a single message msg from a player with identifier $i$ that contains
a set of credentials $c$. The mechanism $M_{(T,F)}$ extracts the credentials’
availability vector $q$ from $c$. If $c$ is not a valid set of credentials,
$M_{(T,F)}$ decides the identifier of the other player $1-i$. If $q\in T$, the
mechanism $M_{(T,F)}$ decides $i$. And if $q\in F$, the mechanism decides
$1-i$. Otherwise, $q\notin T\cup F$, and the step function of $M_{(T,F)}$ does
nothing. $M_{(T,F)}$ is the mechanism that is the _partial Boolean mechanism
of $(T,F)$_.

Similar to Observation 1, the profile of a partial Boolean mechanism of
$(T,F)$ is the set of all scenarios in which the user’s availability vector is
in $T$ and the attacker’s is in $F$. We define a monotonic partial Boolean
function as follows:

######  Definition 13 (Monotonic partial Boolean function).

A _monotonic partial Boolean function_ is a partial Boolean function that has
an extension that is a monotonic function.

In our Example 1, the tuple $(T,F)$ where $T=\\{(1,1)\\}$ and $F=\\{(0,0)\\}$
is a monotonic partial Boolean function, as the function $f(x,y)=x$ is a
monotonic extension of $(T,F)$.

To prove we can indeed extend a partial Boolean function, we make use of the
following observation. We show that if a mechanism $M_{1}$ dominates $M_{2}$
then the set of user availability vectors in $\Pi({M_{1}})$ is a subset of the
set of user availability vectors in $\Pi({M_{2}})$, and the same holds for the
attacker availability vectors.

######  Observation 2.

Let $M_{1}$ and $M_{2}$ be two mechanisms such that
${\emptyset\neq\Pi({M_{1}})\subseteq\Pi({M_{2}})}$. Let $T_{1}$ and $T_{2}$ be
the sets of all user availability vectors and $F_{1}$ and $F_{2}$ be the sets
of all attacker availability vectors in $\Pi({M_{1}})$ and $\Pi({M_{2}})$
respectively. Then, $T_{1}\subseteq T_{2}$ and $F_{1}\subseteq F_{2}$.

For example, the mechanisms $M_{1}=M$ from our Example 1, and the mechanism
$M_{2}=M_{c_{1}}$ that requires only the fist credential to authenticate, both
have non-empty profiles, and $\Pi({M})\subseteq\Pi({M_{c_{1}}})$. Then
$T_{1}=\\{(1,1)\\}$, $T_{2}=\\{(1,1),(1,0)\\}$, $F_{1}=\\{(0,0)\\}$ and
${F_{2}=\\{(0,0),(0,1)\\}}$. And it holds that $T_{1}\subseteq T_{2}$ and
$F_{1}\subseteq F_{2}$.

###### Proof.

Let $M_{1}$, $M_{2}$, $T_{1}$, $T_{2}$, $F_{1}$ and $F_{2}$ be as in the
claim. We show that, $T_{1}\subseteq T_{2}$ and $F_{1}\subseteq F_{2}$. First,
note that as $\Pi({M_{1}})\neq\emptyset$, then $T_{1}$ and $F_{1}$ are both
not empty. Because the profile of a mechanism is the Cartesian product of the
set of user availability vectors ($T_{1}$) with the set of attacker
availability vectors ($F_{1}$) (Observation 1). Similarly, $T_{2}$ and $F_{2}$
are both not empty. Assume for contradiction this at least one of the
following holds: $T_{1}\not\subseteq T_{2}$ or $F_{1}\not\subseteq F_{2}$.

Without loss of generality, assume that $T_{1}\not\subseteq T_{2}$. As
$\Pi({M_{1}})\neq\emptyset$, there exists ${q\in T_{1}}$ such that $q\notin
T_{2}$. Consider a scenario $\sigma$ such that $\sigma_{U}=q$ and
$\sigma_{A}\in F_{1}$. Then, $\sigma\in\Pi({M_{1}})$ and
$\sigma\notin\Pi({M_{2}})$, contradicting the fact
$\Pi({M_{1}})\subseteq\Pi({M_{2}})$. Thus, $T_{1}\subseteq T_{2}$. Similarly,
$F_{1}\subseteq F_{2}$. ∎

We now show that every mechanism is equivalent to a monotonic partial Boolean
one.

######  Lemma 6.

For all mechanisms, there exists an equivalent monotonic partial Boolean
mechanism.

In our Example 1, the pair $(T,F)$ where $T=\\{(1,1)\\}$ and $F=\\{(0,0)\\}$
is a monotonic partial Boolean function and $M$ is equivalent to $M_{(T,F)}$.

###### Proof.

Let $M$ be a mechanism with $n$ credentials. If $M$’s profile is empty, then
$M$ is equivalent to the Boolean mechanism of constant Boolean function
$f(x)=0$. A constant function is monotonic, and thus we are done.

Otherwise, by Theorem 1, there exists a monotonic Boolean function $f$ such
that the Boolean mechanism $M_{f}$ dominates $M$. That is,
$\Pi({M})\subseteq\Pi({M_{f}})$. Let $T$ be the set of all user availability
vectors in $\Pi({M})$ and $F$ be the set of all attacker availability vectors
in $\Pi({M})$.

By definition, To prove that $(T,F)$ is a partial Boolean function, we must
show that $T\cap F=\emptyset$. Let $T_{f}$ and $F_{f}$ be the sets of all user
and attacker availability vectors in $\Pi({M_{f}})$ respectively. As $M$ and
$M_{f}$’s profiles are not empty, by Observation 2, we get that $T\subseteq
T_{f}$ and $F\subseteq F_{f}$.

We show that $T\cap F=\emptyset$. If there exists a vector ${q\in T\cap
F\subseteq T_{f}\cap F_{f}}$, then for $q$, it holds that $f(q)=1$ and
$f(q)=0$, contradicting the fact that $f$ is a well-defined function. Thus,
$T\cap F=\emptyset$ and $(T,F)$ is a partial Boolean function. It is monotonic
because $f$ is an extension of $(T,F)$ and $f$ is monotonic. And the mechanism
$M$ is equivalent to the monotonic partial Boolean mechanism of $(T,F)$. ∎

Now we show that every maximal mechanism equivalent to a Boolean mechanism.

######  Theorem 2.

For all monotonic Boolean mechanisms of non-constant functions, there exists
no strictly dominating mechanism.

###### Proof.

Let $f$ be a non-constant monotonic Boolean function, $M_{f}$ the mechanism
defined by $f$, and $M^{\prime}$ a mechanism dominating $M_{f}$. We show that
$\Pi({M_{f}})=\Pi({M^{\prime}})$.

By Lemma 6, there exists a monotonic partial Boolean mechanism that
$M^{\prime}$ is equivalent to. Let $(T^{\prime},F^{\prime})$ be the partial
Boolean function defining $M^{\prime}$. And let $T$ be the set of all user
availability vectors in $\Pi({M_{f}})$ and $F$ be the set of all attacker
availability vectors in $\Pi({M_{f}})$.

First we show that the profile of $M_{f}$ is not empty. As $f$ is non-
constant, there exists a vector $q$ such that $f(q)=1$ and a vector
$q^{\prime}$ such that $f(q^{\prime})=0$. Consider the scenario $\sigma$ such
that $\sigma_{U}=q$ and $\sigma_{A}=q^{\prime}$. Then, from Observation 1,
${\sigma\in\Pi({M_{f}})}$, and thus $\Pi({M_{f}})\neq\emptyset$.

Then, as $\Pi({M_{f}})\subseteq\Pi({M^{\prime}})$, from Observation 2, we get
that $T\subseteq T^{\prime}$ and $F\subseteq F^{\prime}$. However, as $f$ is a
Boolean function, $T\cup F=\\{0,1\\}^{n}$ and $T\cap F=\emptyset$. Therefore,
$T=T^{\prime}$ and $F=F^{\prime}$. And thus, $\Pi({M_{f}})=\Pi({M^{\prime}})$.
∎

Finally, we prove that there exists no hierarchy between monotonic Boolean
mechanisms of non-constant functions.

######  Lemma 7.

Let $f,g:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ be two different non-constant
monotonic Boolean functions. Denote by $M_{f}$ and $M_{g}$ the monotonic
Boolean mechanisms of $f$ and $g$ respectively. If $f$ or $g$ is not constant,
then $\Pi({M_{f}})\neq\Pi({M_{g}})$.

###### Proof.

Let $f,g:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ be two different monotonic Boolean
functions. There exists a vector $v\in\\{0,1\\}^{n}$ such that $f(v)\neq
g(v)$. Assume without loss of generality that $f(v)=1$ and $g(v)=0$. As both
functions are non-constant, there exists a vector $u\in\\{0,1\\}^{n}$ such
that ${f(u)=0}$. Consider the scenario $\sigma=(v,u)$. We have $f(v)=1$ and
$f(u)=0$, and thus $\sigma\in\Pi({M_{f}})$. We also have $g(v)=0$, and thus
$\sigma\notin\Pi({M_{g}})$. Therefore, $\Pi({M_{f}})\neq\Pi({M_{g}})$. ∎

Overall, we showed that for every mechanism that solves the $\pi$ asynchronous
authentication problem, there exists a partial Boolean function that defines
it. And there exists monotonic Boolean mechanism that dominates it. In
addition, every monotonic Boolean mechanism of a non-constant function is
maximal. Thus concluding that every two monotonic Boolean mechanisms of non-
constant functions are either equivalent or incomparable.

##  5 Probabilistic Analysis

Using the properties we found of maximal mechanisms, we present an efficient
method for finding mechanisms with approximately maximal success probability.

###  5.1 Preliminaries

As in previous work [15], we derive the probability of scenarios from the
fault probability of credentials. Each credential $c_{i}$ can be in one of the
four states, (1) _safe_ : Only available to the user, (2) _loss_ : Not
available to either player, (3) _leak_ : Available to both players, or (4)
_theft_ : Available only to the attacker. Its $c_{i}^{S}$ is available to each
player accordingly by the scheduler.

Each credential has a probability of being in each of the four states. For
example, a complex password that the user memorized has a low probability of
being leaked (guessed) but a high probability of being lost (forgotten). While
a simple password has a high probability of being leaked but a low probability
of being lost. The states of the different credentials are determined by a
probability space specified by independent probabilities of each of the
credentials. The probabilities of a credential $c_{i}$ being in each of the
four states are denoted by $P_{i}^{\textit{safe}}$, $P_{i}^{\textit{loss}}$,
$P_{i}^{\textit{leak}}$, and $P_{i}^{\textit{theft}}$, respectively,
$P_{i}^{\textit{safe}}+P_{i}^{\textit{loss}}+P_{i}^{\textit{leak}}+P_{i}^{\textit{theft}}=1$.
We assume the mechanism designer estimates the fault probabilities of the
credential. But note that this is always the case, even if done implicitly.

The probability of a scenario given the probability vector tuple of each
credential is the product of the probabilities of each credential being in the
state it is in the scenario. Let $M_{f}$ be the Boolean mechanism of the
function $f$. The success probability of $M_{f}$ is the sum of the
probabilities of all scenarios in which $M_{f}$ is successful, denoted by
$P^{\textit{suc}}(M_{f})$, and the failure probability is its complement
$P^{\textit{fail}}(M_{f})=1-P^{\textit{suc}}(M_{f})$. A mechanism is _better_
than another if its success probability is higher.

###  5.2 Profiles and Scenarios

Given the number of credentials $n$, and the probability vectors of each
state, our goal is to find a mechanism with the highest success probability.
Using exhaustive search over the space of all possible mechanisms
(equivalently, all monotonic Boolean functions) is infeasible for more than
just a few credentials [15]. The number of different Boolean functions with
$n$ credentials is the Dedekind number of $n$ [17] which grows super-
exponentially and is only known up to $n=9$ [49]. Therefore, we need to find a
way to choose a mechanism that is close to optimal while exploring only a
small fraction of the space of all mechanisms. We achieve this by searching by
scenarios. For this purpose, we bound the cardinality of any mechanism’s
profile.

######  Claim 1.

For all maximal $n$-credential mechanisms $M$, the cardinality of $M$’s
profile ${|\Pi({M})|}$ is bounded by ${2^{2n-2}}$.

###### Proof.

Let $M$ be a maximal mechanism of $n$ credentials. By Theorem 1 and Theorem 2,
there exists an equivalent mechanism defined by the monotonic Boolean function
$f$. Consider the truth table of $f$. The number of entries in the truth table
is $2^{n}$. Let $T=\\{v\in\\{0,1\\}^{n}\mid f(v)=1\\}$ and
$F=\\{v\in\\{0,1\\}^{n}\mid f(v)=0\\}$. By the previous Observation 1, we have
$|\Pi({M})|=|T|\cdot|F|$. And $|\Pi({M})|$ is maximized when the number of
vectors $v$ such that $f(v)=1$ is equal to the number of vectors $u$ such that
$f(u)=0$. That is, $|T|=|F|=2^{n-1}$. Therefore, $|\Pi({M})|\leq 2^{2n-2}$. ∎

We now show that there is no need to consider scenarios with no safe
credentials.

######  Definition 14 (Viable scenarios).

A _non-viable scenario_ $\sigma$ is a scenario in which there exists no
credential that is both available to the user and unavailable to the attacker.
That is, $\sigma_{U}\leq\sigma_{A}$. A scenario is  _viable_ if it is not Non-
viable.

######  Claim 2.

A non-viable scenario is not in the profile of any mechanism.

###### Proof.

First, we show that a non-viable scenario is not in the profile of any maximal
mechanism. Let $M$ be any maximal mechanism of $n$ credentials. Let
$\sigma=(u,a)$ be a scenario such that there exists no credential that is both
available to the user and unavailable to the attacker ($u$ and $a$ are the
user and attacker availability vectors). That is, for all ${i\in[n]}$,
$u_{i}=1\Rightarrow a_{i}=1$. Let $f$ be a monotonic Boolean function such
that $M$ is equivalent to the monotonic Boolean mechanism $M_{f}$. Since $f$
is monotonic, we have $f(u)=1\Rightarrow f(a)=1$. Therefore,
$\sigma\notin\Pi({M})$.

Assume for contradiction there exists a mechanism $M$ with a non-viable
scenario $\sigma$ in its profile. Such mechanism is either maximal or is
dominated by a maximal mechanism. In both cases, there exists a maximal
mechanism with $\sigma$ in its profile. Contradicting the above. Thus, a non-
viable scenario is not in the profile of any mechanism. ∎

######  Observation 3.

Let $(T,F)$ be a partial Boolean function of $n$ credentials. Let
$s=max(|T|,|F|)$. The maximum number of scenarios that can be added to the
profile of the mechanism $M_{(T,F)}$ without contradicting it is
${s\cdot(2^{n}-s)-|\Pi({M_{(T,F)}})|}$ if $s\geq 2^{n-1}$, and
${2^{2n-2}-|\Pi({M_{(T,F)}})|}$ otherwise.

###### Proof.

Let $(T,F)$ be a partial Boolean function of $n$ credentials, and let
$s=max(|T|,|F|)$. For $n$ credentials, the number of Boolean vectors is
$2^{n}$. By Observation 1, we have $|\Pi({M_{(T,F)}})|=|T|\cdot|F|$. There are
three separate cases:

(1) If $s\geq 2^{n-1}$ and $s=|T|$ then the maximal size of a profile is
reachable if all vectors $v\notin T\cup F$ are added to $F$. That is, the
number of scenarios that can be added to the profile is at most
${|T|\cdot(2^{n}-|T|)-|\Pi({M_{(T,F)}})|}$

(2) If $s\geq 2^{n-1}$ and $s=|F|$ the case is symmetric to the previous one
and the number of scenarios that can be added to the profile is at most
${|F|\cdot(2^{n}-|F|)-\Pi({M_{(T,F)}})}$

(3) Otherwise, we get that $s<2^{n-1}$, then the maximal size of a profile is
$2^{2n-2}$ (as in Claim 1). In that case, the number of scenarios that can be
added to the profile is at most $2^{2n-2}-|\Pi({M_{(T,F)}})|$ Thus proving the
bound on the number of scenarios that can be added to $\Pi({M_{(T,F)}})$. ∎

To maximize success probability, we limit our search to mechanisms with
maximal profiles. We notice that the probability distribution of viable
scenarios is highly concentrated on a small number of scenarios. And when some
fault probabilities are $0$, the number of scenarios with non-zero probability
drops even further. Thus, the number of scenarios that our algorithm needs to
consider is much smaller than the total number of scenarios. For example,
Figure 1(a) shows the probability distribution of the scenarios for a system
with 9 credentials where the first credentials might be lost or leaked with
probability $P_{i}^{\textit{loss}}=P_{i}^{\textit{leak}}=0.01$ and the rest of
the credentials might be stolen with probability
$P_{i}^{\textit{theft}}=0.01$. Again, the number of scenarios with $9$
credentials is $4^{9}=262,144$ with $242,461$ viable scenarios, but only $766$
have non-zero probability. Similarly, Figure 1(b) shows the probability
distribution of the scenarios for a system with 7 credentials where the only
fault possible is theft with probability
$P_{i}^{\textit{loss}}=0.05,P_{i}^{\textit{leak}}=0.03,P_{i}^{\textit{theft}}=0.01$
for all credentials. The number of different scenarios with 7 credentials is
$4^{7}=16,384$, out of which $14,197$ viable scenarios with positive
probability. Note that this case assumes all credentials are prone to all
faults, with different probabilities. Yet, over $91\%$ of the probability is
concentrated on the first $50$ scenarios and over $95\%$ on the first $100$
scenarios. This is a key observation for the efficiency of our algorithm that
allows us to direct our search towards viable scenarios with high probability.

(a) $n=9$: ${P_{1}^{\textit{loss}}=P_{1}^{\textit{leak}}=0.01}$, for $i>1$
$P_{i}^{\textit{theft}}=0.01$.

(b) $n=7$ with ${P^{\textit{loss}}=0.05}$,
$P^{\textit{leak}}=0.03,P^{\textit{theft}}=0.01$.

Figure 1: Probability of scenarios for $n$ credentials and different
probabilities.

###  5.3 Scenario-Based Search Algorithm

Our algorithm finds a mechanism with success probability
$\delta\in\mathbb{R}^{+}$ close to that of an optimal mechanism. It takes
advantage of three key observations: (1) The number of scenarios that might be
added to a profile of a partial Boolean mechanism is bounded (Observation 3).
(2) Non-viable scenarios can be ignored (Claim 2). And (3) the probability of
different scenarios drops exponentially fast (Figures 1(a) and 1(a)).

Instead of searching all possible mechanisms to find the optimal one, we build
the truth table (and thus mechanism) incrementally: Given the number of
credentials $n$, we start with the empty truth table of $n$ variables of the
function (total of $2^{n}$ rows) and add one row’s value at a time. By Lemma
6, for all mechanisms $M$ there exists a monotonic partial Boolean function
$(T,F)$ such that $M$ is equivalent to the mechanism defined by $(T,F)$. The
monotonic partial truth table corresponding to $(T,F)$ has the value $1$ for
all vectors in $T$, the value $0$ for all vectors in $F$, and the rest of the
vectors $v\notin T\cup F$ are not set yet (_don’t care_ , denoted by $*$).
Changing a value of a row in the truth table from $*$ to $0$ is equivalent to
adding the vector to $F$ and changing a value from $*$ to $1$ is equivalent to
adding the vector to $T$.

By Theorem (Theorem 1) every mechanism is dominated by a Boolean mechanism.
Because every maximal mechanism is a monotonic Boolean mechanism (Theorem 2),
and every monotonic Boolean function yields a maximal mechanism (Lemma 7) We
extend the monotonic partial Boolean function that defines the mechanism until
it is full (representing a Boolean function).

Note that if the value of the all zeroes row is set to $1$ in the truth table,
from monotonicity, we get the constant function $f(x)=1$. As for all
${x\in\\{0,1\\}^{n}}$ we have that $x\geq 0^{n}$, then to ensure monotonicity,
we must set $f(x)=1$ for all $x\in\\{0,1\\}^{n}$. Similarly, if the value of
the all ones row is set to $0$, we get the constant function $f(x)=0$.

It is easy to confirm that the profile of a Boolean mechanism of a constant
function is empty. Let $M_{\textit{F}}$ and $M_{\textit{T}}$ be the mechanisms
defined by the constant Boolean functions $\forall v,\textit{F}(v)=0$, and
$\textit{T}(v)=1$. Let ${\sigma=(\sigma_{U},\sigma_{A})}$ be a scenario.
Because ${\forall v,\textit{F}(v)=0}$, we get that
${\textit{F}(\sigma_{U})\wedge\neg\textit{F}(\sigma_{A})=0}$, thus
$M_{\textit{F}}$ fails. Similarly, we have
${\textit{T}(\sigma_{U})\wedge\neg\textit{T}(\sigma_{A})=0}$. Therefore, both
mechanisms have empty profile. So we consider only non-constant monotonic
Boolean functions, and set the value of the all zeroes row to $0$ and the
value of the all ones row to $1$.

Given the credentials’ probability vectors, we calculate the probability of
each viable scenario. Then we progress greedily, from scenarios with the
highest to the lowest probabilities. For each scenario, there are two options:
either include it in the profile or not. Given a scenario $\sigma$ and a
partially filled truth table, we check whether the scenario contradicts the
truth table. We do so by checking if the value of the user’s availability
vector $\sigma_{U}$ is set to $1$ or not chosen yet and the value of the
attacker’s availability vector $\sigma_{A}$ is set to $0$ or not chosen yet.
If so, the scenario does not contradict the truth table, and we can include it
in the profile.

To include a scenario $\sigma$ in the profile, we update the truth table by
setting the entry corresponding to $\sigma_{U}$ to $1$ and the entry
$\sigma_{A}$ to $0$. Then, to have the truth table represent a monotonic
Boolean function, we update it by setting all the entries $x\in\\{0,1\\}^{n}$
such that $x>\sigma_{U}$ to $1$. And setting all entries $y\in\\{0,1\\}$ such
that $y<\sigma_{A}$ to $0$.

######  Claim 3.

After each update, the partial monotonic truth table remains a (possibly
partial) monotonic truth table, and the above update does not contradict
previous ones.

###### Proof.

Given a monotonic partial truth table, it holds that for all
$x,y\in\\{0,1\\}^{n}$ such that $x>y$ we have that if $f(y)=1$ then $f(x)=1$,
and if $f(x)=0$ then $f(y)=0$. According to the algorithm, in every step where
we add a viable scenario $\sigma$, we check that $\sigma_{U}$ is not set to
$0$ and $\sigma_{A}$ is not set to $1$. If so, we set $\sigma_{U}$ to $1$ and
$\sigma_{A}$ to $0$. As $\sigma$ is viable, we have that
$\sigma_{U}\nleq\sigma_{A}$, so this update preserves monotonicity.

Because $\sigma_{U}$ was not set to $0$ before, for all $x>\sigma_{U}$ we have
that $f(x)\neq 0$, and we can set them to $1$. Similarly, because $\sigma_{A}$
was not set to $1$ before, for all ${y<\sigma_{A}}$, $f(y)\neq 1$, and we can
set them to $0$. Therefore, the truth table can still be completed into a
monotonic Boolean function. ∎

In each step, first the algorithm checks if it tried all viable scenarios or
if the truth table is full. The latter means we reached a Boolean function
that cannot be further extended. In both cases, it returns the success
probability of the mechanism defined by the function, and the truth table.
Otherwise, the algorithm checks if it is beneficial to continue extending the
current table. It does so by computing the success probability of the current
partial truth table. Then, calculating an upper bound on the additional
success probability for the current branch by considering the next $k$
scenarios in the sorted list and summing their probabilities where $k$ is the
maximum number of scenarios that may be added to the current truth table
without contradicting it (Observation 3). If the potential best solution is
not better by at least $\delta$ than the global best, we prune this branch and
do not consider any of the mechanisms it results in. This is a key step in
ensuring the algorithm’s efficiency.

If, at any step, all the next scenarios have a probability of $0$, we can
complete the truth table arbitrarily as long as the function stays monotonic.
That is because additional scenarios would contribute $0$ to the success
probability.

For the recursive exploration, given a scenario, we have two options: (1)
Include the scenario in the truth table and recursively call the algorithm
(only if it does not contradict the current truth table). Or (2) Exclude this
scenario and recursively call the algorithm with the next scenario.

After exploring both options, we update the global best solution probability
if a better solution is found. Finally, the algorithm returns the best
solution probability and the corresponding truth table. The result is thus a
mechanism that is $\delta$ close to the optimal mechanism.

###  5.4 Case Studies

The algorithm allows designers choose approximately optimal mechanisms given
their credentials. The ability to study mechanisms with larger number of
credentials compared to previous work allows taking advantage of more
elaborate schemes. We demonstrate this with two use cases.

Our algorithm takes advantage of the fact that the probability of different
scenarios drops exponentially (Figure 1). Instead of searching all possible
mechanisms, it builds them incrementally, exploring only a small fraction of
the space of all possible mechanisms. This improves the efficiency by orders
of magnitude compared to previous work.

We demonstrate the efficacy of our method by comparing the results to the
optimal mechanisms found using exhaustive search, a heuristic genetic
algorithm [15], and guessing based on previous examples [15]. As expected, the
number of credentials has major effect on wallet security. Figure 2 shows the
security for different number of credentials when the first credential can be
lost or leaked, but not stolen ($P_{\textit{loss}}=P_{\textit{leak}}=0.01$),
and the rest of the credentials can only be stolen
($P_{\textit{theft}}=0.01$). We use a parameter $\delta$ ranging from
$10^{-5}$ for smaller number of credentials to $10^{-7}$ for larger number of
credentials. Our algorithm efficiently finds the same optimal mechanism as the
exhaustive search, and is able to find an approximately optimal mechanism for
up to 12 credentials. In some cases, it finds better mechanisms than the ones
found by guessing a symmetric mechanism, e.g., Figure 2 with 6 or 8
credentials.

We show how weak credentials can bolster the success probability of a
mechanism based on strong credentials. Consider for example the common crypto
wallet with a 2/2 multisig mechanism, whose signing keys are secured well with
a small probability of loss or leak. We can get much better security by taking
advantage of additional keys, even if they are easy to lose. Two additional
keys reduce the failure probability by an order of magnitude from $2\cdot
10^{-2}$ to $6\cdot 10^{-3}$. Figure 3 shows the failure probability for
different number of credentials when all credentials can be lost or leaked,
but not stolen ($P_{\textit{loss}}=P_{\textit{leak}}=0.01$), compared to the
security when using the same credentials but adding credentials that can only
be lost with higher probability ($P_{\textit{loss}}=0.3$). Here we used the
parameter $\delta=10^{-6}$. We find that for $n$ regular credentials and $k$
easy-to-lose credentials, the optimal mechanism design is to require any of
the easy-to-lose credentials or $\lfloor n/2\rfloor+1$ out of $n$ regular
credentials.

This also applies for logging in to online services like email or social
networks. An MFA scheme can be similarly improved by adding easily leaked,
hard to lose credentials (e.g., name of pet or ID number).

In terms of usability, our suggestions do not add much overhead to the
user—the added credentials are information the user already knows. However, a
comprehensive study is needed to evaluate the usability of any authentication
mechanism.

Figure 2: Failure probability with
$P_{1}^{\textit{loss}}=P_{1}^{\textit{leak}}=0.01$ and for $i>1$
$P_{i}^{\textit{theft}}=0.01$. Figure 3: Failure probability with
$P^{\textit{loss}}=P^{\textit{leak}}=0.01$ with easy-to-lose credentials.

##  6 Conclusion

We formalize the common asynchronous authentication problem, overcoming the
apparent tension between asynchrony and cryptographic security. We show every
mechanism is dominated by a non-trivial monotonic Boolean mechanism, which are
not strictly dominated themselves. So in every pair of distinct such
mechanisms, neither strictly dominates the other. We present an efficient
algorithm for finding approximately optimal mechanisms, given the credential
fault probabilities. This highlights the need for user studies to quantify
credential fault probabilities.

One case study shows that a user designing her cryptocurrency wallet can
reduce the failure probability by orders of magnitude by incorporating with
her carefully-guarded credentials a few additional ones that are perhaps easy
to lose. More generally, both individuals and companies can use these results
directly to rigorously design authentication mechanisms addressing the demands
of current and forthcoming challenges.

## Acknowledgments

This work was supported in part by Avalanche Foundation and by IC3.

## References

  * [1] R. E. Smith, _Authentication: from passwords to public keys_. Addison-Wesley Longman Publishing Co., Inc., 2001.
  * [2] W. Stallings and L. Brown, _Computer security : principles and practice / William Stallings, Lawrie Brown ; with contributions by Mick Bauer, Michael Howard_ , 2nd ed. Pearson Boston, 2012.
  * [3] J. EATON, “The political significance of the imperial watchword in the early empire,” _Greece and Rome_ , vol. 58, no. 1, 2011.
  * [4] L. Bošnjak and B. Brumen, “Rejecting the death of passwords: Advice for the future,” _Computer Science and Information Systems_ , vol. 16, 01 2019.
  * [5] K. Abhishek, S. Roshan, P. Kumar, and R. Ranjan, “A comprehensive study on multifactor authentication schemes,” in _Advances in Computing and Information Technology_ , N. Meghanathan, D. Nagamalai, and N. Chaki, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013.
  * [6] “Using timelocks to protect digital assets,” https://github.com/BlockchainCommons/SmartCustody/blob/master/Docs/Timelocks.md, 2021, accessed, December 2023.
  * [7] “Argent smart wallet specification,” https://github.com/argentlabs/argent-contracts/blob/develop/specifications/specifications.pdf, 2021, accessed, December 2023.
  * [8] C. Li, L. Wang, S. Ji, X. Zhang, Z. Xi, S. Guo, and T. Wang, “Seeing is living? rethinking the security of facial liveness verification in the deepfake era,” in _31st USENIX Security Symposium (USENIX Security 22)_. Boston, MA: USENIX Association, Aug. 2022. [Online]. Available: https://www.usenix.org/conference/usenixsecurity22/presentation/li-changjiang
  * [9] Federal Trade Commission, “Consumer sentinel network data book 2021,” February 2022.
  * [10] C. Team, “60% of bitcoin is held long term as digital gold. what about the rest?” https://blog.chainalysis.com/reports/bitcoin-market-data-exchanges-trading/, June 2020.
  * [11] P. Jha, “The aftermath of Axie Infinity’s $650m Ronin Bridge hack,” _Cointelegraph_ , April 2022, https://cointelegraph.com/news/the-aftermath-of-axie-infinity-s-650m-ronin-bridge-hack.
  * [12] J. Bonneau, C. Herley, P. C. v. Oorschot, and F. Stajano, “The quest to replace passwords: A framework for comparative evaluation of web authentication schemes,” in _2012 IEEE Symposium on Security and Privacy_ , 2012.
  * [13] V. Zimmermann, N. Gerber, P. Mayer, M. Kleboth, A. von Preuschen, and K. Schmidt, “Keep on rating – on the systematic rating and comparison of authentication schemes,” _Information and computer security._ , vol. 27, no. 5, 2019-11-11.
  * [14] A. Vaish, A. Sharma, and A. Sharma, “Review reports on user authentication methods in cyber security,” _WSEAS TRANSACTIONS ON COMMUNICATIONS_ , vol. 19, 10 2020.
  * [15] I. Eyal, “On cryptocurrency wallet design,” in _3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021)_. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022.
  * [16] D. Maram, M. Kelkar, and I. Eyal, “Interactive authentication,” Cryptology ePrint Archive, Paper 2022/1682, 2022, https://eprint.iacr.org/2022/1682. [Online]. Available: https://eprint.iacr.org/2022/1682
  * [17] R. Dedekind, _Über Zerlegungen von Zahlen Durch Ihre Grössten Gemeinsamen Theiler_. Wiesbaden: Vieweg+Teubner Verlag, 1897. [Online]. Available: https://doi.org/10.1007/978-3-663-07224-9_1
  * [18] G. Mcshane, “What is a multisig wallet?” https://www.coindesk.com/learn/what-is-a-multisig-wallet/, 2022, accessed, December 2023.
  * [19] S. Nevil, “Bitcoin safe storage - cold wallet,” https://www.investopedia.com/news/bitcoin-safe-storage-cold-wallet/, 2023, accessed, December 2023.
  * [20] B. Schneier, _Applied cryptography: protocols, algorithms, and source code in C_ , 2nd ed. New York: Wiley, 1996.
  * [21] C. P. Pfleeger and S. L. Pfleeger, _Security in Computing, 4th Edition_. Prentice Hall, 2012.
  * [22] W. Stallings, _Cryptography and network security - principles and practice (3. ed.)_. Prentice Hall, 2003.
  * [23] S. P. Otta, S. Panda, M. Gupta, and C. Hota, “A systematic survey of multi-factor authentication for cloud infrastructure,” _Future Internet_ , vol. 15, no. 4, 2023. [Online]. Available: https://www.mdpi.com/1999-5903/15/4/146
  * [24] Z. A. Zukarnain, A. Muneer, and M. K. Ab Aziz, “Authentication securing methods for mobile identity: Issues, solutions and challenges,” _Symmetry_ , vol. 14, no. 4, 2022. [Online]. Available: https://www.mdpi.com/2073-8994/14/4/821
  * [25] R. Morris and K. Thompson, “Password security: A case history,” _Communications of the ACM_ , vol. 22, 05 2002.
  * [26] L. Lamport, “Password authentication with insecure communication,” _Commun. ACM_ , vol. 24, no. 11, nov 1981. [Online]. Available: https://doi.org/10.1145/358790.358797
  * [27] Y. Zhu, T. Tan, and Y. Wang, “Biometric personal identification based on iris patterns,” in _Proceedings 15th International Conference on Pattern Recognition. ICPR-2000_ , vol. 2, 2000.
  * [28] N. F. H. Salah Machani (RSA Security), “Fido alliance white paper: Choosing fido authenticators for enterprise use cases,” FIDO Alliance, Tech. Rep., 2022.
  * [29] J. G. Steiner, B. C. Neuman, and J. I. Schiller, “Kerberos: An authentication service for open network systems,” in _USENIX Winter_ , 1988.
  * [30] “Coinbase wallet,” https://www.coinbase.com/wallet, accessed, December 2023.
  * [31] “Ledger hardware wallet,” https://www.ledger.com/, accessed, December 2023.
  * [32] “Trezor hardware wallet,” https://trezor.io/, accessed, December 2023.
  * [33] I. Velásquez, A. Caro, and A. Rodríguez, “Authentication schemes and methods: A systematic literature review,” _Information and Software Technology_ , vol. 94, 2018. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0950584916301501
  * [34] M. Burrows, M. Abadi, and R. Needham, “A logic of authentication,” _ACM Trans. Comput. Syst._ , vol. 8, no. 1, feb 1990. [Online]. Available: https://doi.org/10.1145/77648.77649
  * [35] N. Li, B. N. Grosof, and J. Feigenbaum, “Delegation logic: A logic-based approach to distributed authorization,” _ACM Trans. Inf. Syst. Secur._ , vol. 6, no. 1, feb 2003. [Online]. Available: https://doi.org/10.1145/605434.605438
  * [36] “Cryptocurrency market size, share and growth report, 2030,” https://www.grandviewresearch.com/industry-analysis/cryptocurrency-market-report#, 2023, accessed, December 2023.
  * [37] “Non-fungible tokens (nft): Global market,” https://www.bccresearch.com/market-research/information-technology/nft-market.html, accessed: June 2023.
  * [38] J. Bonneau, A. Miller, J. Clark, A. Narayanan, J. A. Kroll, and E. W. Felten, “Sok: Research perspectives and challenges for bitcoin and cryptocurrencies,” in _2015 IEEE Symposium on Security and Privacy_ , 2015.
  * [39] S. Barber, X. Boyen, E. Shi, and E. Uzun, “Bitter to better — how to make bitcoin a better currency,” in _Financial Cryptography and Data Security_ , A. D. Keromytis, Ed. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012.
  * [40] S. Hammann, S. Radomirović, R. Sasse, and D. Basin, “User account access graphs,” in _Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security_ , ser. CCS ’19. New York, NY, USA: Association for Computing Machinery, 2019. [Online]. Available: https://doi.org/10.1145/3319535.3354193
  * [41] C. Dwork and A. Roth, “The algorithmic foundations of differential privacy,” _Found. Trends Theor. Comput. Sci._ , vol. 9, no. 3–4, p. 211–407, aug 2014. [Online]. Available: https://doi.org/10.1561/0400000042
  * [42] F. B. Schneider, “Implementing fault-tolerant services using the state machine approach: A tutorial,” _ACM Comput. Surv._ , vol. 22, no. 4, dec 1990. [Online]. Available: https://doi.org/10.1145/98163.98167
  * [43] R. L. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” _Commun. ACM_ , vol. 21, no. 2, p. 120–126, feb 1978. [Online]. Available: https://doi.org/10.1145/359340.359342
  * [44] Y. Pu, A. Farahbakhsh, L. Alvisi, and I. Eyal, “Gorilla: Safe permissionless byzantine consensus,” in _37th International Symposium on Distributed Computing_ , 2023.
  * [45] Y. Pu, L. Alvisi, and I. Eyal, “Safe permissionless consensus,” in _36th International Symposium on Distributed Computing_ , 2022.
  * [46] J. Wang and H. Wang, “Monoxide: Scale out blockchains with asynchronous consensus zones,” in _16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19)_. Boston, MA: USENIX Association, Feb. 2019. [Online]. Available: https://www.usenix.org/conference/nsdi19/presentation/wang-jiaping
  * [47] J. Y. Halpern and Y. Moses, “Knowledge and common knowledge in a distributed environment,” _J. ACM_ , vol. 37, no. 3, jul 1990. [Online]. Available: https://doi.org/10.1145/79147.79161
  * [48] E. Boros, V. Gurvich, P. L. Hammer, T. Ibaraki, and A. Kogan, “Decomposability of partially defined boolean functions,” _Discrete Applied Mathematics_ , vol. 62, no. 1-3, 1995.
  * [49] L. V. Hirtum, P. D. Causmaecker, J. Goemaere, T. Kenter, H. Riebler, M. Lass, and C. Plessl, “A computation of d(9) using fpga supercomputing,” 2023.

##  Appendix A Execution

We now describe the execution of the system. It consists of two parts: _setup_
(Setup function, Algorithm 2) and a _main loop_ (Execute function, Algorithm
3). The setup generates a set of $n$ credentials
$\\{c_{i}=(c_{i}^{P},c_{i}^{S})\\}_{i=1}^{n}$ using the function
$\textit{gen}_{M^{\lambda}}({n})$ (line 2). The credential generation function
$\textit{gen}_{M^{\lambda}}({n})$ draws randomness from the random tape $v$
and returns a set of $n$ credentials. Then the setup function assigns each
player credentials according to the scenario $\sigma$ (lines 2-2), and the
mechanism receives all the credentials’ public parts (line 2). Then it assigns
an identifier to each player: $\gamma_{\textit{ID}}\in\\{0,1\\}$ to the user
(line 2) and $(1-\gamma_{\textit{ID}})$ to the attacker (line 2). Whenever a
random coin is used by $M^{\lambda}$ or the players, the result is the next
bit of $v$.

Once the setup is complete, the main loop begins (line 4). From this point
onwards in the execution, both players $p\in\\{U,A\\}$ can send messages to
the mechanism, each based on her strategy $S_{p}^{\lambda}$ and the set of
credentials available to her $C_{p}^{\sigma}$.

Time progresses in discrete steps $t$, accessible to the mechanism and
players. The communication network is reliable but asynchronous. Messages
arrive eventually, but there is no bound on the time after they were sent and
no constraints on the arrival order. This is implemented as follows. The
scheduler maintains three sets of pending messages, one for each entity
identifier $e\in\\{0,1,M^{\lambda}\\}$, denoted by $\textit{Pending}_{e}$. The
scheduler is parametrized by an ordering function $\gamma_{\textit{ord}}$.

In each step, it uses $\gamma_{\textit{ord}}$ to choose a subset of messages
(maybe empty) from each of the pending message sets, and returns them as an
ordered list (lines 3). The scheduler removes the chosen messages from the
pending messages sets (line 3). The function $\gamma_{\textit{ord}}$ gets as
input the identifier of the entity $e\in\\{0,1,M^{\lambda}\\}$ that the
messages are sent to. It also has access to the state of the execution and a
separate scheduler random tape $v_{\gamma}$. However, $\gamma_{\textit{ord}}$
does not have access to the messages themselves, the security parameter nor to
the entities’ random tape $v$. We use an ordering function that’s oblivious to
the messages content and the security parameter to model a system in which,
for a sufficiently large security parameter, messages eventually arrive during
the execution. The ordering function’s lack of access to the messages and the
security parameter ensures that it cannot delay messages until after the
execution ends for all $\lambda$.

Using two separate random tapes, one for the scheduler and another for all
other entities in the system, is only for presentation purpose. This is
equivalent to using a single global random tape. Because there exists a
mapping between the two, e.g., given a global random tape, we map it into two
separate tapes such that the elements in the odd indices are mapped to the
scheduler tape and the elements in the even indices are mapped to the other
entities’ tape.

Each player $p\in\\{U,A\\}$ receives the messages chosen by the ordering
function $\gamma_{\textit{ord}}$ and sends messages to the mechanism according
to her strategy $S_{p}^{\lambda}$ (lines 3-3). Messages sent by the players
are added to the mechanism’s pending messages set $\textit{Pending}_{M}$.
Similarly, the mechanism receives the messages chosen by
$\gamma_{\textit{ord}}$. After every message msg it receives, the mechanism
updates its state using its function
$\textit{step}_{M^{\lambda}}({\textit{msg}})$ and returns messages to add to
the players’ pending messages sets $\textit{Pending}_{0},\textit{Pending}_{1}$
(line 3). It then checks if the mechanism has decided which one of the players
is recognized as the user by checking its variable
$\textit{decide}_{M^{\lambda}}$ (lines 3-3). Once the mechanism reaches a
decision, the execution ends and the player with the matching index (either
$0$ or $1$) wins. The tuple
$(\gamma_{\textit{ID}},\gamma_{\textit{ord}},v_{\gamma})$ thus defines the
_scheduler_ ’s behavior. And an execution $E^{\lambda}$ (Algorithm 4) is thus
defined by its parameter tuple
$(M^{\lambda},\sigma,S_{U}^{\lambda},S_{A}^{\lambda},\gamma,v)$; by slight
abuse of notation we write
${E^{\lambda}=(M^{\lambda},\sigma,S_{U}^{\lambda},S_{A}^{\lambda},\gamma,v)}$.

###  A.1 Denial of Service attacks

We assume that the attacker cannot affect the delivery time of user messages.
In particular, she cannot perform a denial of service attack by sending
messages in a way that causes $\gamma_{\textit{ord}}$ to always delay the
user’s messages. This is implemented by using two separate ordering functions
$\gamma_{\textit{ord}}^{0},\gamma_{\textit{ord}}^{1}$ for the player with
identifier $0$ and the player with identifier $1$ respectively.

1

2

_$\textit{Setup}(M^{\lambda},\sigma,S_{U}^{\lambda},S_{A}^{\lambda},\gamma,v)$_

3

$C\leftarrow\textit{gen}_{M^{\lambda}}({n})$

// Generating the set of credentials
$C=\\{c_{i}=(c_{i}^{P},c_{i}^{S})\\}_{i=1}^{n}$

$C_{U}^{\sigma}\leftarrow\\{c_{i}^{S}|{\sigma_{U}}_{i}=1\\}$

// Assigning the credentials’ secret parts to the user

$C_{A}^{\sigma}\leftarrow\\{c_{i}^{S}|{\sigma_{A}}_{i}=1\\}$

// Assigning the credentials’ secret parts to the attacker

$C_{M}^{\sigma}\leftarrow\\{c_{i}^{P}|i\in\\{1,...,n\\}\\}$

// Assigning the credentials’ public parts to the mechanism

4

$S_{\gamma_{\textit{ID}}},C_{\gamma_{\textit{ID}}}\leftarrow
S_{U}^{\lambda},C_{U}^{\sigma}$

// Assugning $\gamma_{\textit{ID}}$ to the user

$S_{1-\gamma_{\textit{ID}}},C_{1-\gamma_{\textit{ID}}}\leftarrow
S_{A}^{\lambda},C_{A}^{\sigma}$

// Assugning $1-\gamma_{\textit{ID}}$ to the attacker

5

6return $M^{\lambda},S_{0},C_{0},S_{1},C_{1},v^{\prime}$

Algorithm 2 Setup of the system, with mechanism $M^{\lambda}$ in scenario
$\sigma$

1

2

_$\textit{Execute}(M^{\lambda},S_{0},C_{0},S_{1},C_{1},\gamma_{\textit{ord}},v_{\gamma},v_{\gamma},v)$_

3

$\textit{decide}_{M^{\lambda}}\leftarrow\bot$

// Initialize $M^{\lambda}$’s decision variable

4

5for  _$e\in\\{0,1,M^{\lambda}\\}$_ do

$\textit{Pending}_{e}\leftarrow\emptyset$

// Initialize the message sets

6

7

8 for  _$t=0,1,2,...,T(\lambda)$_ do

9 for  _$e\in\\{0,1,M^{\lambda}\\}$_ do // The scheduler chooses which
messages to deliver

10 $l_{e}\leftarrow\gamma_{\textit{ord}}(e)+[\bot]$

11 $\textit{Pending}_{e}\leftarrow\textit{Pending}_{e}\setminus l_{e}$

12

13

14 $\textit{Pending}_{M^{\lambda}}^{\prime}\leftarrow\emptyset$

15

16 for  _msg in $l_{0}$_ do

$\textit{Pending}_{M^{\lambda}}^{\prime}\leftarrow\textit{Pending}_{M^{\lambda}}^{\prime}\cup
S_{0}(\textit{msg})$

// Player 0 sends messages to the mechanism

17

18 for  _msg in $l_{1}$_ do

$\textit{Pending}_{M^{\lambda}}^{\prime}\leftarrow\textit{Pending}_{M^{\lambda}}^{\prime}\cup
S_{1}(\textit{msg})$

// Player 1 sends messages to the mechanism

19

20

21 for  _msg in $l_{M}$_ do

$(\textit{Pending}_{0}^{\prime},\textit{Pending}_{1}^{\prime})\leftarrow\textit{step}_{M^{\lambda}}({\textit{msg}})$

// The mechanism sends messages to the players

$\textit{Pending}_{0}\leftarrow\textit{Pending}_{0}\cup\textit{Pending}_{0}^{\prime}$

// Player 0’s messages are added to the message set

$\textit{Pending}_{1}\leftarrow\textit{Pending}_{1}\cup\textit{Pending}_{1}^{\prime}$

// Player 1’s messages are added to the message set

22

23 if  _$\textit{decide}_{M^{\lambda}}\neq\bot$_ then // Check if the
mechanism reached a decision

$\textit{Return }\textit{decide}_{M^{\lambda}}$

// The chosen player wins

24

25

$\textit{Pending}_{M^{\lambda}}\leftarrow\textit{Pending}_{M^{\lambda}}\cup\textit{Pending}_{M^{\lambda}}^{\prime}$

// The mechanism’s messages are added to the message set

26

Algorithm 3 Execution main loop of $M^{\lambda}$

1

2$M^{\lambda},S_{0},C_{0},S_{1},C_{1},v\leftarrow\textit{Setup}(M^{\lambda},\sigma,S_{U}^{\lambda},S_{A}^{\lambda},\gamma,v)$

3
$\textit{Execute}(M^{\lambda},S_{0},C_{0},S_{1},C_{1},\gamma_{\textit{ord}},v_{\gamma},v)$

4

Algorithm 4 Execution of $M^{\lambda}$ in scenario $\sigma$

##  Appendix B Deterministic Mechanisms are Dominated by Boolean Mechanisms

  * Lemma 4 (restated).  Let $M_{\textit{det}}$ a deterministic credential-based mechanism family and let the function $f$ be as constructed above. Then $f$ is monotonic.

###### Proof.

Let $M_{\textit{det}}$ be a deterministic mechanism and let $f$ be as defined
in Construction 2. We prove that if $M_{\textit{det}}$ is successful in a
scenario, then $M_{f}$ is successful as well. Assume $M_{\textit{det}}$ is
successful in scenario $\sigma=(\sigma_{U},\sigma_{A})$, by definition of $f$,
we get that $f(\sigma_{U})=1$.

As $M_{\textit{det}}^{\lambda}$ is successful in $\sigma$, there exists a
winning user strategy family $S_{U}^{\textit{det}}$ for $M_{\textit{det}}$.
And because $M_{\textit{det}}$ is a credential-based mechanism, for each
$\lambda$, $S_{U}^{\textit{det},\lambda}$ sends a set of credentials
$c_{U}^{\lambda}$ in a single message. Let $\lambda\in\mathbb{N}^{+}$ be any
security parameter, let $S_{U}^{f,\lambda}$ be the user strategy for
$M_{f}^{\lambda}$ that sends the same subset of the user’s credentials as
$S_{U}^{\textit{det},\lambda}$ in a single message in the first step. Let
$S_{A}^{f}$ be an attacker strategy family for $M_{f}$, $\gamma_{f}$ a
scheduler, and $v$ a random tape.

Consider the execution
$E_{f}^{\lambda}=(M_{f}^{\lambda},\sigma,S_{U}^{f,\lambda},S_{A}^{f,\lambda},\gamma_{f},v)$.
Because $S_{U}^{f,\lambda}$ sends a message in the first step, there exists a
security parameter $\lambda_{0}^{f}$ such that for all
$\lambda>\lambda_{0}^{f}$, the user’s message arrives before $T(\lambda)$. It
might be the case that an attacker’s message arrives first. If the mechanism
does not receive any messages, it times out. This is possible only if
$\lambda\leq\lambda_{0}^{f}$, by definition of $\lambda_{0}^{f}$.

Otherwise, $M_{f}^{\lambda}$ eventually receives and processes at least one
message during its execution, then we consider two cases separately: a user’s
message arrives first, or an attacker’s message arrives first. If the user’s
message arrives first to $M_{f}^{\lambda}$, with her set of credentials, then
as $f(\sigma_{U})=1$ (because $\sigma\in\Pi({M_{\textit{det}}})$),
$M_{f}^{\lambda}$ decides the user. We get that if $\lambda>\lambda_{0}^{f}$,
then $M_{f}^{\lambda}$ decides the user. And if $\lambda\leq\lambda_{0}^{f}$,
then $M_{f}^{\lambda}$ either decides the user or times out. Overall we showed
that if the user’s message arrives first, then if $\lambda>\lambda_{0}^{f}$
the user wins, otherwise, either the user wins or the execution times out. So
$\lambda_{\textit{suc}}^{f}=\lambda_{0}^{f}$.

Otherwise, the attacker’s message arrives first to $M_{f}^{\lambda}$. If
$f(\sigma_{A})=0$, then $M_{f}^{\lambda}$ decides the user, and we are done,
because the user wins. The only other option is if ${f(\sigma_{A})=1}$. We
show that this is not possible.

By definition of $f$, $f(q)=1$ if and only if there exists a scenario
$\sigma_{U:q}$ in which the user’s availability vector is $q$ and
$M_{\textit{det}}$ succeeds in $\sigma_{U:q}$. Let $S_{U:q}$ be the winning
user strategy for $M_{\textit{det}}$ in $\sigma_{U:q}$. Then for all attacker
strategy families $S_{A}$, schedulers
$\gamma=(\gamma_{\textit{ID}},\gamma_{\textit{ord}},v_{\gamma})$ and random
tapes $v$, there exists a security parameter $\lambda_{\textit{suc}}$ such
that for all $\lambda>\lambda_{\textit{suc}}$, the user wins the execution
$E_{U:q}^{\lambda}=(M_{\textit{det}}^{\lambda},\sigma_{U:q},S_{U:q}^{\lambda},S_{A}^{\lambda},\gamma,v)$.
This includes the attacker strategy that does not send any messages
$S_{A}^{\lambda}=\bot$. Then during the execution $E_{U:q}^{\lambda}$’s main
loop there exists a time $\tau<T(\lambda)$ when $M_{\textit{det}}^{\lambda}$
decides the identifier of the user.

Now consider the execution of $M_{\textit{det}}^{\lambda}$ in $\sigma$, in
which the attacker uses the same strategy as the users’ $S_{U:q}^{\lambda}$
from $\sigma_{U:q}$. This is possible as the attacker has access to all
credentials the user had in $\sigma_{U:q}$. Let $\gamma^{\prime}$ be a
scheduler in which the user and the attacker’s identifiers are opposite to the
ones in $\gamma$, the attacker’s message arrives first and the user’s message
is delayed beyond $\tau$. And let $v^{\prime}$ be any random tape. Denote this
execution by $E^{\lambda}$.

At any time step before $\tau$, the mechanism $M_{\textit{det}}^{\lambda}$
sees the same execution prefix whether it is in $E^{\lambda}$ or in
$E_{U:q}^{\lambda}$, and thus, it cannot distinguish between the case where it
is in $E^{\lambda}$ or $E_{U:q}^{\lambda}$. As $M_{\textit{det}}^{\lambda}$
decides the user in $E_{U:q}^{\lambda}$’s main loop at time $\tau$, then it
must decide the attacker at the same time $\tau$ in $E^{\lambda}$’s main loop
(as the identifiers are reversed, and the mechanism sees the exact same
execution prefix). Therefore, $M_{\textit{det}}^{\lambda}$ decides the
attacker in $E^{\lambda}$ contradicting the assumption that
$M_{\textit{det}}^{\lambda}$ succeeds in $\sigma$. We conclude that
$f(\sigma_{A})=0$ and $M_{f}^{\lambda}$ decides the user also in this case.
Therefore, $M_{\textit{f}}$ is successful in $\sigma$. Overall we showed that
the mechanism family $M_{\textit{f}}$ a monotonic Boolean mechanism family and
dominates $M_{\textit{det}}$. ∎

##  Appendix C Success Equivalence

######  Lemma 8.

Let $f$ be a monotonic Boolean function, and let $M_{f}$ be the mechanism
family of $f$. $M_{f}$ is successful in a scenario $\sigma$ if and only if
$f(\sigma_{U})=1$ and $f(\sigma_{A})=0$.

###### Proof.

For the first direction, assume that $M_{f}$ is successful in a scenario
$\sigma$. Then, there exists a winning user strategy family $S_{U}$ for
$M_{f}$ in $\sigma$ that sends her set of credentials in a single message on
the first step. For every attacker strategy $S_{A}$, scheduler $\gamma$ and
random tape $v$, there exists a security parameter $\lambda_{\textit{suc}}$
such that for all $\lambda>\lambda_{\textit{suc}}$ the user wins the execution
$(M_{f}^{\lambda},\sigma,S_{U},S_{A},\gamma,v)$.

Because $S_{U}^{\lambda}$ sends a message in the first step, there exists a
security parameter $\lambda_{0}^{f}$ such that for all
$\lambda>\lambda_{0}^{f}$, the user’s message eventually arrive before
$T(\lambda)$. It might be the case that an attacker’s message arrives first.
If the mechanism does not receive any messages, it times out. This is possible
only if $\lambda<\lambda_{0}^{f}$, as the user strategy we chose always send a
message.

Let $\lambda>\lambda_{0}^{f}$ and consider a scheduler $\gamma$ for which the
user’s message arrives first. Consider the execution
$E=(M_{f}^{\lambda},\sigma,S_{U},S_{A},\gamma,v)$. As the user’s message
arrives first, with her set of credentials, $M_{f}$ will extract the
availability vector $\sigma_{U}$ of the credentials. Then, as $M_{f}$ is
successful in $\sigma$, it will return the identifier of the user. This can
happen only if $f(\sigma_{U})=1$.

Now let $S_{U}$ be a winning user strategy and $S_{A}$ an attacker strategy
that sends any subset of the attacker’s credentials. Let $\gamma^{\prime}$ and
$v^{\prime}$ be a scheduler and random tape such that the attacker’s message
arrives first, and consider the execution
${E^{\prime}=(M_{f}^{\lambda},\sigma,S_{U},S_{A},\gamma^{\prime},v^{\prime})}$.
In that case, as the attacker sends a subset of her credentials,
$M_{f}^{\lambda}$ will extract the availability vector $\sigma_{A}^{\prime}$
of the credentials. Then, as $M_{f}$ is successful in $\sigma$, it will return
the identifier of the user. This is possible only if
$f(\sigma_{A}^{\prime})=0$. This is true for any subset of credentials the
attacker chooses, including the set of all her credentials. Thus,
$f(\sigma_{A})=0$. Therefore, we showed that if $M_{f}$ is successful in a
scenario $\sigma$, then $f(\sigma_{U})=1$ and $f(\sigma_{A})=0$.

For the second direction, assume that $f(\sigma_{U})=1$ and $f(\sigma_{A})=0$.
Let $S_{U}$ be a user strategy family that sends the set of credentials
corresponding to $\sigma_{U}$ in the first step. And let $S_{A}$,$\gamma$ and
$v$ be any attacker strategy, scheduler and random tape. We show that $S_{U}$
is a winning user strategy for $M_{f}$ in $\sigma$.

Consider the execution ${(M_{f}^{\lambda},\sigma,S_{U},S_{A},\gamma,v)}$. If
no message was received, then $M_{f}^{\lambda}$ times out. This is possible
only if $\lambda<\lambda_{0}^{f}$, as the user strategy we chose sends a
message on the first step. Otherwise, $M_{f}^{\lambda}$ receives a message.

If the user’s message arrives first to $M_{f}^{\lambda}$ with the credentials
corresponding to $\sigma_{U}$, then $M_{f}^{\lambda}$ extracts the
availability vector $\sigma_{U}$ of the credentials. Then, as
$f(\sigma_{U})=1$, the mechanism $M_{f}^{\lambda}$ returns the identifier of
the user, thus the user wins the execution. Otherwise, the attacker’s message
$\textit{msg}_{A}$ arrives first to $M_{f}^{\lambda}$. If $\textit{msg}_{A}$
does not contain a valid set of credentials, then $M_{f}^{\lambda}$ returns
the identifier of the user, and she wins the execution. Otherwise,
$M_{f}^{\lambda}$ extracts the availability vector $q\leq\sigma_{A}$ of the
credentials in $\textit{msg}_{A}$ (the attacker might send any subset of
credentials she knows). Then, because $f$ is monotonic and $f(\sigma_{A})=0$,
also $f(q)=0$ and $M_{f}^{\lambda}$ returns the identifier of the user, thus
the user wins the execution. In both cases, if $\lambda>\lambda_{0}^{f}$, the
execution terminates and the user wins. And if $\lambda<\lambda_{0}^{f}$,
either the user wins or the execution times out. Thus, $M_{f}$ is successful
in $\sigma$, concluding the proof that $M_{f}$ is successful in a scenario
$\sigma$ if and only if $f(\sigma_{U})=1$ and ${f(\sigma_{A})=0}$. ∎