# Wiretapped Commitment over Binary Channels

Anuj Kumar Yadav1, Manideep Mamindlapally2, and Amitalok J. Budkuley 3.
1School of Computer and Communication Sciences, EPFL, Switzerland.
2CWI and University of Amsterdam, The Netherlands.
3Department of Electronics and Electrical Communication Engg., IIT Kharagpur,
India.

###### Abstract

We propose the problem of _wiretapped commitment_ , where two parties, say
committer Alice and receiver Bob, engage in a commitment protocol using a
noisy channel as a resource, in the presence of a _eavesdropper_ , say Eve.
Noisy versions of Alice’s transmission over the wiretap channel are received
at both Bob and Eve. We seek to determine the maximum commitment throughput in
the presence of a eavesdropper, i.e., _wiretapped commitment capacity_ , where
in addition to the standard security requirements for two-party commitment,
one seeks to ensure that Eve doesn’t learn about the commit string.

A key interest in this work is to explore the effect of collusion (or lack of
it) between the eavesdropper Eve and either Alice or Bob. Toward the same, we
present results on the wiretapped commitment capacity under the so-called _$1$
-private regime_ (when Alice or Bob cannot collude with Eve) and the _$2$
-private regime_ (when Alice or Bob may possibly collude with Eve).

††A short version of this work has been accepted for publication at the 2024
IEEE International Symposium on Information Theory (ISIT), Athens, Greece.
This extended version includes detailed proofs of theorems, discussion and
open questions.

##  I Introduction

A classic _two-party_ primitive that finds wide application in cryptographic
applications is _commitment_ introduced by Blum [1]. In this work, we study a
_three-party variation_ of this problem, viz., _wiretapped commitment_ ,
involving committer Alice, receiver Bob and an eavesdropper Eve. Imagine Alice
and Bob engaging in a high-stakes business transaction, exchanging digital
contract details over a communication channel that may be susceptible to
wiretapping by an eavesdropper Eve. In this scenario, there’s a concern that
either Alice or Bob, individually or in possible collusion with Eve, may
interact with the aim of either revealing the contract terms prematurely or
altering them without detection at the time of finalization. We seek to devise
_eavesdropper-resilient_ commitment schemes, also called _wiretapped
commitment schemes_ henceforth, such that Alice and Bob can establish a secure
and tamper-evident commitment protocol, mitigating the risks associated with
wiretapping and possible collusion. Such a scheme would not only safeguard the
confidentiality of the contract terms but also maintain the integrity of the
agreement in the face of potential adversarial collaboration.

While Blum’s classic work introduced commitment, it also brought to the fore
the limitation that information-theoretically secure schemes were impossible
under entirely noiseless interactions between two-parties.111Blum’s work
established the possibility of _conditionally-secure_ commitment schemes under
computationally-limited parties. Wyner’s foundational work on _wiretap
channels_ [2] first demonstrated the use of _noisy channels_ to devise schemes
with information-theoretic security (albeit in the ‘weak’ sense). Through a
series of subsequent works [3, 4], positive rate unconditionally secure
commitment was shown to be possible over binary memoryless channels. Winter
_et al._ [5] characterized the commitment capacity over any _non-redundant_
discrete memoryless channel (DMC); this result was subsequently extended to
DMCs with ‘costs’ in [6]. Commitment has also been explored for other channel
models like the unfair noisy channels [7, 8, 9], elastic channels and their
cousins [10, 11], quantum channels [12], etc. Several other variants of
commitment too have been studied (see [13, 14, 15]).

Closer to the theme of this work, and a key motivation for our study, is the
work by Mishra _et al._ [16, 17] on _wiretapped oblivious transfer_ , where
the authors studied another related cryptographic primitive called the
_oblivious transfer_ [18, 19, 20] in the presence of an eavesdropper. The
presence of the eavesdropper necessitated additional security requirement
(w.r.t. the classical problem). Here the authors focused on certain sub-
classes of binary wiretap channels with erasures and studied their capacity
(with potentially _honest-but-curious_ users) under two versions of security
guarantees: (i) the _$1$ -privacy_ setting which precludes collusion with the
eavesdropper, and (ii) _$2$ -privacy_ setting where collusion is possible.
Inspired by their work, in our problem we study wiretap channels under
similarly inspired notions of privacy (with and without colluding parties);
see Section III for their formal definitions.

Our work formalizes the wiretapped commitment problem and presents new results
on their commitment capacity. In the following, we summarize our key
contributions:

  * •

We initiate a systematic study of wiretapped commitment in this work. For the
$1$-privacy setting, we completely characterize the commitment capacity for
the binary symmetric broadcast (BS-BC) wiretap channels in Theorem 1. Here we
present a converse (upper bound) for general alphabet wiretap channels, and
then specialize it for the BS-BC class of such channels, followed by a
matching lower bound using a scheme tailored for the BS-BC channels.

  * •

Next, we present capacity results under the more challenging $2$-privacy
setting where Alice or Bob may collude with Eve. Using a general wiretap
channel converse, and constructing a specialized achievability scheme matching
that bound, we completely characterize the $2$-private commitment capacity for
the _independent_ BS-BC wiretap channel (see Def. 5).

Organization of the paper: In the following, we briefly present the basic
notation in Section II. Following which we present our problem setup in
Section III. The main results of this work are presented in Section IV. We
present some details of the converse proof and achievability in Section V.
Finally, we make concluding remarks in Section VI.

##  II Notation and Preliminaries:

We denote random variables by upper case letters (eg. $X$), their values by
lower case letters (eg., $x$), and their alphabets by calligraphic letters
(eg. ${\cal X}$). Random vectors and their accompanying values are denoted by
boldface letters. For natural number $a\in\mathbb{N}$, let
$[a]:=\\{1,2,\cdots,a\\}$. Let $P_{X}$ denote the distribution of $X\in{\cal
X}$. Distributions for multiple random variables are similarly defined.
$P_{X|Y}$ and $[P_{X,Y}]_{X}$ denote the conditional distribution of $X$
(conditioned on $Y$) and the marginal distribution of $X$ (under the $P_{X,Y}$
joint distribution). Given $P_{X},Q_{X}\in{\cal P}({\cal X})$,
$||P_{X}-Q_{X}||$ denotes their statistical distance.

Let random variables $X,Y\in{\cal X}\times{\cal Y}$, where $(X,Y)\sim
P_{X,Y}$. The _min-entropy_ of $X$ is denoted by
$H_{\infty}(X):=\min_{x\in{\cal X}}\left(-\log(P_{X}(x))\right)$; the
conditional version is given by $H_{\infty}(X|Y):=\min_{y}H_{\infty}(X|Y=y).$
For $\epsilon\in[0,1)$, the _$\epsilon$ -smooth min entropy_ and its
conditional version is given by:
$H_{\infty}^{\epsilon}(X):=\max_{X^{\prime}:||P_{X^{\prime}}-P_{X}||\leq\hskip
2.84526pt\epsilon}H_{\infty}(X^{\prime})$ and
$H_{\infty}^{\epsilon}(X|Y):=\max_{X^{\prime},Y^{\prime}:||P_{X^{\prime},Y^{\prime}}-P_{X,Y}||\leq\hskip
2.84526pt\epsilon}H_{\infty}(X^{\prime}|Y^{\prime})$ respectively.

We also need universal hash functions and strong randomness extractors for our
commitment scheme; see [21, 22, 23] for detailed definitions.

######  Definition 1 ($\xi$-Universal hash functions).

Let $\mathcal{H}$ be a class of functions from ${\cal X}$ to ${\cal Y}$.
$\mathcal{H}$ is said to be $\xi-$universal hash function, where
$\xi\in\mathbb{N}$, if when $h\in\mathcal{H}$ is chosen uniformly at random,
then $(h(x_{1}),h(x_{2}),...h(x_{\xi}))$ is uniformly distributed over ${\cal
Y}^{\xi}$, $\forall x_{1},x_{2},...x_{\xi}\in{\cal X}$.

######  Definition 2 (Strong randomness extractors).

A probabilistic polynomial time function of the form Ext:
$\\{0,1\\}^{n}\times\\{0,1\\}^{d}\to\\{0,1\\}^{m}$ is an
$(n,k,m,\epsilon$)-strong extractor if for every probability distribution
$P_{Z}$ on ${\cal Z}=\\{0,1\\}^{n}$, and $H_{\infty}(Z)\geq k$, for random
variables $D$ (called ’seed’) and $M$, distributed uniformly in
$\\{0,1\\}^{d}$ and $\\{0,1\\}^{m}$ respectively, we have
$||P_{Ext(Z;D),D}-P_{M,D}||\leq\epsilon$.

##  III System Model and Problem Description

Our problem (refer Fig. 1) comprises three parties: _committer_ Alice,
_receiver_ Bob and _eavesdropper_ Eve. Alice and Bob are mutually distrustful
parties and employ a noisy wiretap channel (where potentially different noisy
versions of Alice’s transmission are broadcast to Bob and Eve) to realize
commitment in the presence of Eve. The commit string $C$ is chosen uniformly
at random by Alice, where $C\in[2^{nR}]$, and she transmits her encrypted data
or _codeword_ $\mathbf{X}$ over a one-way wiretap channel where channel
outputs $\mathbf{Y}$ and $\mathbf{Z}$ are received at Bob and Eve,
respectively. We formally define the wiretap channel below:

######  Definition 3 (Wiretap channel [24], [25]).

A wiretap channel is a memoryless broadcast channel with Alice’s input
$X\in{\cal X}$, and outputs $Y\in{\cal Y}$ and $Z\in{\cal Z}$ at Bob and Eve,
respectively. The memoryless channel law is given by
$W_{Y,Z|X}:\mathcal{X}\to\mathcal{Y}\times\mathcal{Z}$ and is known to all
parties.

In this work, we specifically focus on the following class of binary wiretap
channels.

######  Definition 4 (BS-BC wiretap channels [25]).

A binary input binary output (BIBO) memoryless broadcast channel $W_{Y,Z|X}$,
where ${\cal X}={\cal Y}={\cal Z}=\\{0,1\\},$ and the _marginal_ channel laws
$W_{Y|X}:=[W_{Y,Z|X}]_{Y|X}$ and $W_{Z|X}=[W_{Y,Z|X}]_{Z|X}$ are binary
symmetric channels (BSCs), say BSC($p$) and BSC($q$), where $0<p,q<1/2$, is
called a binary symmetric broadcast (BS-BC) wiretap channel and denoted by BS-
BC($p,q$). Note that the two BSCs may exhibit correlated behaviour. 222Note
that both $p$ and $q$ are strictly in the interior of the set $[0,1/2]$. We
include this restriction since (information-theoretic) the commitment capacity
can be easily characterized when either (or both) of $p$ and $q$ equal 0 or 1.

######  Remark 1.

For given $0<p,q<1/2$, BS-BC($p,q$) is not a unique channel but a class of
channels.

Next, we define two sub-classes of binary symmetric broadcast (BS-BC) wiretap
channels which are relevant for this work.

######  Definition 5 (I-BS-BC wiretap channel [25]).

An independent binary symmetric broadcast (I-BS-BC($p,q$)) wiretap channel is
a BS-BC$(p,q)$ wiretap channel where the channel law $W_{Y,Z|X}$ can be
decomposed in the following manner: $W_{Y,Z|X}=W_{Y|X}W_{Z|X}$ i.e., the
Markov chain $Y-X-Z$ holds. In other words, the binary symmetric channels
BSC($p$) and BSC($q$) have independent channel noise.

######  Definition 6 (D-BS-BC wiretap channel [25]).

A degraded binary symmetric broadcast (D-BS-BC($p,q$)) wiretap channel is a
BS-BC$(p,q)$ wiretap channel where the channel law $W_{YZ|X}$ can be
decomposed in the following manner: $W_{YZ|X}=W_{Y|X}W_{Z|Y},$ i.e., the
Markov chain $X-Y-Z$ holds. In other words, the binary symmetric channel from
Alice to Eve, i.e., BSC($q$) is a physically degraded version of the binary
symmetric channel from Alice to Bob, i.e., BSC($p$).

In addition to the noisy channel resource, as is common in such cryptographic
primitives, we also assume that Alice and Bob can interact over a two-way link
that is noiseless and where the interaction is public and fully authenticates
the transmitting party.333Recall from earlier that under unconditionally-
secure commitment, even single-bit commitment is impossible to realize under
purely noiseless interactions [7]. The eavesdropper Eve is assumed to also
have access to the interactions over the noiseless link.

To commit to her random string $C,$ Alice uses the BS-BC wiretap channel
$W_{Y,Z|X}$, $n$ times and transmits over it her encrypted string
$\mathbf{X}=(X_{1},X_{2},\cdots,X_{n})\in\\{0,1\\}^{n}$. Bob and Eve,
respectively, receive noisy versions $\mathbf{Y}\in\\{0,1\\}^{n}$ and
$\mathbf{Z}\in\\{0,1\\}^{n}$ of $\mathbf{X}.$ Alice and Bob can both privately
randomize their transmissions (over the noisy and noiseless links) via their
respective keys $K_{A}\in\mathcal{K_{A}}$ and $K_{B}\in\mathcal{K_{B}}.$ At
any point in time, say instant $i\in[n]$, Alice and Bob can also exchange
messages over the public, noiseless link prior to transmitting $X_{i}$; let
$M$ denote the entire collection of messages exchanged over the noiseless
link. We call $M$ the _transcript_ of the protocol. We assume that at any
point in time during the protocol, the transmissions of Alice and/or Bob can
depend _causally_ on the information previously available to them.

Figure 1: The problem setup: commitment over a wiretap channel

We now formally introduce an $(n,R)$-commitment protocol for the above setup.

######  Definition 7 (Commitment protocol).

An $(n,R)-$commitment protocol $\mathscr{P}$ is a message-exchange procedure
between Alice and Bob (in the presence of Eve) to realize commitment over the
random bit string $C\in[2^{nR}].$ Here $R$ is called the _rate_ of the above
$(n,R)$-commitment protocol $\mathscr{P}.$ There are two phases to
$\mathscr{P}:$ _commit phase_ followed by the _reveal phase._
(a) Commit phase: Given $C\in[2^{nR}]$, Alice uses the BS-BC $(p,q)$, $n$
times to transmit $\mathbf{X}$ over it. Correspondingly, Bob receives
$\mathbf{Y},$ and Eve receives $\mathbf{Z}$ over this channel. The two parties
(Alice and Bob) may also exchange messages over the noiseless link during the
transmission of $\mathbf{X}$. Let $M$ denote this transcript (over the
noiseless link) of protocol $\mathscr{P}$ at the end of Commit phase.444We
assume that the transcript may contain arbitrarily large, though finite,
messages. Let $V_{A}=(C,K_{A},\mathbf{X},M),V_{B}=(K_{B},\mathbf{Y},M)$ and
$V_{E}=(\mathbf{Z},M)$ denote, _Alice’s view_ , _Bob’s view_ and _Eve’s view_
respectively which includes all the random variables and vectors known to the
respective users at the end of the commit phase.
(b) Reveal phase: In this phase, Alice and Bob communicate only over the
noiseless public link and do not use the BS-BC wiretap channel 555We point
that in some works, unlike in this work, the noisy channel may be used to also
realize the bidirectional noiseless link, and the rate calculation is,
subsequently, normalized also over such channel uses. We do not study such a
definition of rate in this work.. Alice announces the commit string
$\tilde{c}\in[2^{nR}]$ and $\tilde{\mathbf{X}}\in\\{0,1\\}^{n}.$ Bob then
performs a test $T(\tilde{c},\tilde{\mathbf{X}},V_{B})$ and either accepts (by
setting $T=1$) the commit string $\tilde{c}$ or reject it (by setting $T=0$).

In this work, we study _achievability_ of rate $R$ (defined later) with
respect to two different notions of security metrics, viz., the $1-$privacy
(where none of the legitimate parties i.e., Alice and Bob are allowed to
collude with the eavesdropper Eve) and the $2-$privacy (where the collusion
between ‘a malicious Alice and Eve’ or ‘a malicious Bob and Eve’ is possible).
Toward defining the same, we first introduce the security metrics for any
$(n,R)-$commitment protocol $\mathscr{P}.$

######  Definition 8 ($\epsilon-$sound).

A protocol $\mathscr{P}$ is $\epsilon-$sound if for an honest Alice and an
honest Bob, $\mathbb{P}\left(T(C,\mathbf{X},V_{B})\neq 1\right)\leq\epsilon.$

######  Definition 9 ($\epsilon-1-$concealing).

A protocol $\mathscr{P}$ is $\epsilon-1-$concealing if for an honest Alice and
under any strategy of a malicious Bob, $I(C;V_{B})\leq\epsilon.$

######  Definition 10 ($\epsilon-1-$ binding).

A protocol $\mathscr{P}$ is $\epsilon-1-$binding if for an honest Bob and
under any cheating function $\mathcal{A}$ of a malicious Alice,

$\mathbb{P}\Big{(}T(\bar{c},\bar{\mathbf{x}},V_{B})=1\quad\&\quad
T(\hat{c},\hat{\mathbf{x}},V_{B})=1\Big{)}\leq\epsilon$

for any two pairs
$(\bar{c},\bar{\mathbf{x}}),(\hat{c},\hat{\mathbf{x}})=\mathcal{A}(V_{A})$
where $\bar{c}\neq\hat{c},$ and
$\bar{\mathbf{x}},\hat{\mathbf{x}}\in\\{0,1\\}^{n}$.

######  Definition 11 ($\epsilon-$secure).

A protocol $\mathscr{P}$ is $\epsilon-$secure if for any strategy of the
eavesdropper Eve, $I(C;V_{E})\leq\epsilon.$

######  Definition 12 ($\epsilon-2-$concealing).

A protocol $\mathscr{P}$ is $\epsilon-2-$concealing if for an honest Alice and
under any strategy of a malicious Bob possibly in collusion with Eve,
$I(C;V_{B},V_{E})\leq\epsilon.$

It might be of interest to note here that under the $2-$privacy caase,
$\epsilon-2-$concealing condition directly implies that the protocol is
$\epsilon-$secure as well (due to the chain rule of mutual information and the
fact that mutual information is non-negative). Alternatively, we could have
also defined $\epsilon-2-$secure condition which would be exactly similar to
$\epsilon-2-$concealing beacause the collusion between Bob and Eve leads to
both having the same view i.e., $(V_{B},V_{E})$.

######  Definition 13 ($\epsilon-2-$binding).

A protocol $\mathscr{P}$ is $\epsilon-2-$binding if for an honest Bob and
under any cheating function $\mathcal{A}$ of a malicious Alice possibly in
collusion with Eve,

$\mathbb{P}\Big{(}T(\bar{c},\bar{\mathbf{x}},V_{B})=1\quad\&\quad
T(\hat{c},\hat{\mathbf{x}},V_{B})=1\Big{)}\leq\epsilon$

for any two pairs
$(\bar{c},\bar{\mathbf{x}}),(\hat{c},\hat{\mathbf{x}})=\mathcal{A}(V_{A},V_{E})$
where $\bar{c}\neq\hat{c},$ and
$\bar{\mathbf{x}},\hat{\mathbf{x}}\in\\{0,1\\}^{n}$.

A rate $R$ is said to be _achievable under $1$-privacy_ (resp. achievable
under $2$-privacy) if for every $\epsilon>0$ arbitrarily small and $n$
sufficiently large, there exists a commitment protocol $\mathscr{P}$ such that
$\mathscr{P}$ is $\epsilon-$sound, $\epsilon-1-$concealing (resp.
$\epsilon-2-$concealing) and $\epsilon-1-$binding (resp. $\epsilon-2-$binding)
and $\epsilon-$secure.

The supremum of all achievable $1-$private rates (resp. $2-$private rates) is
called the _$1-$ private commitment capacity_ (resp. _$2-$ private commitment
capacity_), and the commitment capacity capacity is denoted by
$\mathbb{C}_{1}$ (resp. $\mathbb{C}_{2}$).

##  IV Our Main Results

We now state our key results in this section.

######  Theorem 1 (Capacity of BS-BC under $1-$privacy).

Consider a channel $W_{Y,Z|X}\in$ BS-BC$(p,q)$, where $0<p,q<1/2.$ Then, the
commitment capacity $\mathbb{C}_{1}$ of such a BS-BC($p,q$) under $1-$privacy
is

$\displaystyle\mathbb{C}_{1}=\min\\{H(p),H(q)\\}.$ (1)

We present the full proof in Section V-A and Section V-D.

We first a present a converse for a general (finite) alphabet wiretap channel
and then specialize the same for the BS-BC$(p,q)$ wiretap channel. Our
achievability (inspired from [7, 8, 26]) is tailored for the BS-BC wiretap
channels and utilizes random hash exchange challenge and a strong randomness
extractor based on 2-universal hash function. However, unlike any of the
previous works, our scheme just requires one round of random hash challenge
essentially to guarantee bindingness.

For the I-BS-BC($p,q$) the capacity expression remain unchanged from that in
(1) since that expression depends entirely on the marginal channel laws
$W_{Y|X}$ and $W_{Z|X}$ (which are specified via general parameters $p$ and
$q$). For the Degraded-BS-BC, however, we have the following immediate
corollary.

######  Corollary 1 (Capacity of D-BS-BC under $1-$privacy).

The commitment capacity for the degraded binary symmetric broadacst wiretap
channel, D-BS-BC($p,q$), under $1-$privacy is H$(p)$.

The result follows by noting that for the D-BS-BC($p,q$), we can express
$q=p*\theta,$ for some $\theta\in[0,1/2).$ Hence, $q\geq p,$ and the minimum
in (1) evaluates to $H(p)$.

Next, we state our results for capacity under 2-privacy. For this setting, we
completely characterize the 2-private commitment capacity for the I-BS-
BCO($p,q$). We state the following theorem:

######  Theorem 2 (Capacity of I-BS-BC under $2-$privacy).

Consider an I-BS-BC($p,q$) where $0<p,q<1/2.$ Then, the commitment capacity
$\mathbb{C}_{2}$ of such I-BS-BC($p,q$) under $2-$privacy is

$\displaystyle\mathbb{C}_{2}=H(p)+H(q)-H(p\circledast q).$ (2)

where $p\circledast q$ denotes the binary convolution of $p$ and $q$ i.e.,
$p\circledast q:=p(1-q)+q(1-p)$.

We present the proof in Section V. For the converse, we present a rate upper
bound, viz., $R\leq H(X|Y,Z),$ for any general wiretap channel. This bound is
then specialized to the binary setting (for I-BS-BC($p,q$)) and evaluates to
the expression given in Eq (2). It is pertinent to note that the above bound
holds for _any_ wiretap channel. For the I-BS-BC specifically, we present a
matching lower bound through an achievable scheme. It has similarities to the
scheme in the 1-private setting but crucially differs in the choice of the
hash families and the randomness extractor.

##  V Proofs

###  V-A $1$-privacy converse analysis for the wiretap channel $W_{Y,Z|X}$

In this subsection, we will first derive an upper bound on the rate of any
commitment protocol for a general wiretap channel $W_{Y,Z|X}$ under
$1$-privacy. Then, we specialize the result to get a tight upper bound for the
binary symmetric broadcast (BS-BC$(p,q)$) wiretap channel. Additionally, we
_strengthen_ our converse by proving that our upper bound on the commitment
rate holds even under a _weaker_ notion of $\epsilon$-$1$-concealment and
$\epsilon$-secrecy against Eve, which are defined below:666This is a security
notion directly inspired from the weak secrecy metric originally studied by
Wyner [2] for wiretap channels.

######  Definition 14 ($\epsilon$-weakly-$1$-concealing).

An $(n,R)$-commitment protocol is said to be $\epsilon$-weakly-$1$-concealing
if for an honest Alice and under _any_ strategy of Bob,

$\displaystyle\frac{1}{n}I(C;V_{B})\leq\epsilon.$ (3)

######  Definition 15 ($\epsilon$-weakly-secure).

An $(n,R)$-commitment protocol is said to be $\epsilon$-weakly-$1$-secure
against the eavesdropper Eve if under _any_ strategy of Eve,

$\displaystyle\frac{1}{n}I(C;V_{E})\leq\epsilon.$ (4)

Now, consider any sequence of commitment protocols $(\mathscr{P}_{n})_{n\geq
1}$, such that $\forall n$, $\mathscr{P}_{n}$ is $\epsilon_{n}$-sound,
$\epsilon_{n}$-weakly-$1$-concealing, $\epsilon_{n}$-$1$-binding, and
$\epsilon$-weakly-secure, such that $\epsilon_{n}\geq 0$ and
$\epsilon_{n}\rightarrow 0$ as $n\rightarrow\infty$.

For these sequence of protocols, we state the following lemma which upper
bounds the conditional entropy $\frac{1}{n}H(C|\mathbf{X},V_{B})$ using Fano’s
inequality; we will use this lemma later to upper bound the commitment rate.

######  Lemma 1.

For every commitment protocol $\mathscr{P}_{n}$ satisfying all the security
guarantees under $1-$privacy, we have
$\frac{1}{n}H(C|\mathbf{X},V_{B})\leq\epsilon^{\prime\prime}_{n}$, where
$\epsilon^{\prime\prime}_{n}\rightarrow 0$ as $n\rightarrow\infty$.

The proof appears in Appendix -A, and follows from the fact that each protocol
$\mathscr{P}_{n}$ satisfies $\epsilon_{n}-$soundness and
$\epsilon_{n}-$bindingness.

Let us now bound the commitment rate $R$ as follows:

$\displaystyle R$ $\displaystyle\stackrel{{\scriptstyle}}{{=}}\frac{1}{n}H(C)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\frac{1}{n}H(C|V_{B})+\frac{1}{n}I(C;V_{B})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\frac{1}{n}H(C|V_{B})+\epsilon_{n}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}\frac{1}{n}H(C|{\mathbf{Y}},K_{B},M)+\epsilon_{n}$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\leq}}\frac{1}{n}H(C,\mathbf{X}|{\mathbf{Y}},K_{B},M)+\epsilon_{n}$
$\displaystyle\stackrel{{\scriptstyle(e)}}{{=}}\frac{1}{n}H(\mathbf{X}|{\mathbf{Y}},K_{B},M)+\frac{1}{n}H(C|\mathbf{X},{\mathbf{Y}},K_{B},M)+\epsilon_{n}$
$\displaystyle\stackrel{{\scriptstyle}}{{=}}\frac{1}{n}H(\mathbf{X}|{\mathbf{Y}},K_{B},M)+\frac{1}{n}H(C|\mathbf{X},V_{B})+\epsilon_{n}$
$\displaystyle\stackrel{{\scriptstyle(f)}}{{\leq}}\frac{1}{n}H(\mathbf{X}|{\mathbf{Y}})+\epsilon^{\prime\prime}_{n}+\epsilon_{n}$
$\displaystyle\stackrel{{\scriptstyle}}{{\leq}}\frac{1}{n}\sum_{i=1}^{n}H(X_{i}|Y_{i})+\epsilon^{\prime\prime}_{n}+\epsilon_{n}$
$\displaystyle\stackrel{{\scriptstyle}}{{\leq}}\max_{P_{X}}H(X|Y)+\epsilon^{\prime\prime}_{n}+\epsilon_{n}$
(5)

Here,

  1. (a)

follows from the definition of mutual information.

  2. (b)

follows from the fact that every commitment protocol in the sequence
$\mathscr{P}_{n}$ is $\epsilon_{n}$-weakly-$1$-concealing.

  3. (c)

follows from noting that Bob’s view $V_{B}=(\mathbf{Y},M,K_{B}),$ where
$\mathbf{Y}$ denotes the output of the wiretap channel.

  4. (d)

follows from property of joint entropy.

  5. (e)

follows from the chain rule of joint entropy.

  6. (f)

follows from lemma 1 and noting that conditioning reduces entropy.

Therefore, finally we have:

$\displaystyle R$
$\displaystyle\stackrel{{\scriptstyle}}{{\leq}}\max_{P_{X}}H(X|Y)$ (6)

Let $W_{Y|X}:=[W_{Y,Z|X}]_{Y|X}$ and $W_{Z|X}:=[W_{Y,Z|X}]_{Z|X}$ denote the
effective channels from Alice to Bob and Alice to Eve, respectively. Suppose
there exists a channel $U_{\tilde{Y}|Z}:\mathcal{Z}\rightarrow\mathcal{Y}$
s.t.

$\displaystyle W_{Y|X}=W_{Z|X}U_{\tilde{Y}|Z},$ (7) 777Remember that
$W_{Z|X}U_{\tilde{Y}|Z}$ represents composition of $W_{Z|X}$ and
$U_{\tilde{Y}|Z}$. (c.f. definition 3).

This happens when the channel from Alice to Bob is a stochastically degraded
version of the channel from Alice to Eve. Consider a cheating strategy adopted
by the eavesdropper Eve to learn about the commit string $c$. The eavesdropper
Eve passes the received vector $\mathbf{Z}$ locally through the simulated
private channel $U_{\tilde{Y}|Z}$ to generate a $\tilde{\mathbf{Y}}$ which is
a candidate $\mathbf{Y}$ i.e., $P_{X,\tilde{Y}}=P_{X}W_{Y|X}=P_{XY}$. Note
that the view of Eve here is $V_{E}=(\mathbf{Z},\tilde{\mathbf{Y}},M)$.

Suppose such a $U_{\tilde{Y}|Z}$ exists. Then, from Lemma 1, we have that

$\displaystyle
H(C|\mathbf{X},\mathbf{Y},K_{B},M)\leq\epsilon^{\prime\prime}_{n}$
$\displaystyle
H(C|\mathbf{X},\mathbf{Y},M)\stackrel{{\scriptstyle(a)}}{{\leq}}\epsilon_{n}^{\prime\prime}$
$\displaystyle
H(C|\mathbf{X},\tilde{\mathbf{Y}},M)\stackrel{{\scriptstyle(b)}}{{\leq}}\epsilon^{\prime\prime}_{n}$
$\displaystyle
H(C|\mathbf{X},Z,\tilde{\mathbf{Y}},M)\stackrel{{\scriptstyle(c)}}{{\leq}}\epsilon^{\prime\prime}_{n}$
$\displaystyle
H(C|\mathbf{X},V_{E})\stackrel{{\scriptstyle}}{{\leq}}\epsilon^{\prime\prime}_{n}$
(8)

where,

  1. (a)

follows from noting that $K_{B}$ just models local randomness at Bob which is
independent.

  2. (b)

follows from the assumption of the markov chain $M-\mathbf{X}-\mathbf{Y}$ (see
Remark 2), and thus noting that the joint distributions of
$(C,\mathbf{X},\mathbf{Y},M)$ and $(C,\mathbf{X},\tilde{\mathbf{Y}},M)$ are
equal.

  3. (c)

follows from the fact that conditioning reduces entropy.

Now, we can also upper bound the commitment rate as follows:

$\displaystyle R$ $\displaystyle\stackrel{{\scriptstyle}}{{=}}\frac{1}{n}H(C)$
$\displaystyle\stackrel{{\scriptstyle}}{{=}}\frac{1}{n}H(C|V_{E})+\frac{1}{n}I(C;V_{E})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\frac{1}{n}H(C|V_{E})+\epsilon_{n}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\frac{1}{n}H(C,\mathbf{X}|V_{E})+\epsilon_{n}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}\frac{1}{n}H(\mathbf{X}|{\mathbf{Z}},\tilde{\mathbf{Y}},M)+\frac{1}{n}H(C|\mathbf{X},{\mathbf{Z}},\tilde{\mathbf{Y}},M)+\epsilon_{n}$
$\displaystyle\stackrel{{\scriptstyle}}{{=}}\frac{1}{n}H(\mathbf{X}|{\mathbf{Z}},\tilde{\mathbf{Y}},M)+\frac{1}{n}H(C|\mathbf{X},V_{E})+\epsilon_{n}$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\leq}}\frac{1}{n}H(\mathbf{X}|{\mathbf{Z}})+\epsilon^{\prime\prime}_{n}+\epsilon_{n}$
$\displaystyle\stackrel{{\scriptstyle}}{{\leq}}\frac{1}{n}\sum_{i=1}^{n}H(X_{i}|Z_{i})+\epsilon^{\prime\prime}_{n}+\epsilon_{n}$
$\displaystyle\stackrel{{\scriptstyle}}{{\leq}}\max_{P_{X}}H(X|Z)+\epsilon^{\prime\prime}_{n}+\epsilon_{n}$
(9)

Here,

  1. (a)

follows from the fact that every commitment protocol in the sequence
$\mathscr{P}_{n}$ is $\epsilon_{n}$-weakly-secure against any statregy of Eve.

  2. (b)

follows from the chain rule of joint entropy.

  3. (c)

follows from noting that Eve’s view $V_{E}=(\mathbf{Z},\tilde{\mathbf{Y}},M)$.

  4. (d)

follows from the fact that conditioning reduces entropy and from Eq. (8).

Finally, we also have:

$\displaystyle R$
$\displaystyle\stackrel{{\scriptstyle}}{{\leq}}\max_{P_{X}}H(X|Z)$ (10)

The above upper bound holds only if a $U_{\tilde{Y}|Z}$ satisfying Eq. (7)
exists.

######  Remark 2.

Note that the above approach includes a natural valid assuption of
$M-\mathbf{X}-\mathbf{Y}$ i.e., the transcript of the public communication $M$
and $\mathbf{Y}$ are independent given $\mathbf{X}$. Most of the commitment
protocols including the one presented below in our Achievability subsection
follows this markov chain. This assumption was aslo made by Crepeau et.al [8]
for proving the upper bound on the commitment rate for unfair noisy channels.
As of now, it seems challenging to come up with a general converse approach
without the above markov chain assumption, and is an interesting open problem.
(see Lemma $5.1$ and Final remarks in [8], for details).

From Eq. (6) and Eq. (10), we have the following upper bound on the commitment
rate.

$\displaystyle R$
$\displaystyle\stackrel{{\scriptstyle}}{{\leq}}\min\left\\{\max_{P_{X}}H(X|Y),\max_{P_{X}}H(X|Z)\right\\}$
(11)

Thus, we have the following upper bounds on the commitment rate for a wiretap
channel $W_{Y,Z|X}$:

  1. (i)

If Alice to Bob channel i.e., $W_{Y|X}$ is a stochastically degraded version
of the channel from Alice to Eve i.e., $W_{Z|X}$, then

$\displaystyle R$
$\displaystyle\stackrel{{\scriptstyle}}{{\leq}}\min\left\\{\max_{P_{X}}H(X|Y),\max_{P_{X}}H(X|Z)\right\\}$
(12)

  2. (ii)

Else,

$\displaystyle R\leq\max_{P_{X}}H(X|Y)$ (13)

On solving the Eq. (11) or collectively solving the Eqs. (12) and (13) for the
binary symmetric broadcast (BS-BC$(p,q)$) wiretap channels, we have the
similar following upper bound on the commitment rate for BS-BC$(p,q)$ under
$1-$privacy:

$\displaystyle R$
$\displaystyle\stackrel{{\scriptstyle}}{{\leq}}\min\big{\\{}H(p),H(q)\big{\\}}$
(14)

where we observe that the optimizing the input distribution is
$X\sim\text{Bernoulli}(1/2)$.

Here, we have the following: when Alice to Bob channel is stochastically
degraded version of Alice to Eve channel (i.e., $q<p$), the Eq. (12) evalautes
to $R\leq{H(q)}$. Otherwise (i.e., $q\geq p$), the Eq. (13) evalautes to
$R\leq{H(p)}$. Together, these reduce to the expression in the Eq. (14).

This completes our converse analysis for BS-BC$(p,q)$ wiretap channels under
$1-$privacy.

###  V-B $2$-privacy converse analysis for the wiretap channel $W_{Y,Z|X}$.

In this subsection, we will first derive an upper bound on the rate of any
commitment protocol for a general wiretap channel $W_{Y,Z|X}$ under
$2$-privacy. Then, we specialize the result to get an upper bound for the
Independent binary symmetric broadcast (I-BS-BC$(p,q)$) wiretap channel.

Additionally, similar to the previous case we _strengthen_ our converse by
proving that our upper bound on the commitment rate holds even under a
_weaker_ notion of $\epsilon$-$2$-concealment (defined below) and
$\epsilon$-secrecy against Eve.

######  Definition 16 ($\epsilon$-weakly-$2$-concealing).

An $(n,R)$-commitment protocol is said to be $\epsilon$-weakly-$2$-concealing
if for an honest Alice and under _any_ strategy of colluding Bob and Eve,

$\displaystyle\frac{1}{n}I(C;V_{B},V_{E})\leq\epsilon.$ (15)

Now, consider any sequence of commitment protocols $(\mathscr{P}_{n})_{n\geq
1}$, such that $\forall n$, $\mathscr{P}_{n}$ is $\epsilon_{n}$-sound,
$\epsilon_{n}$-weakly-$2$-concealing, $\epsilon_{n}$-$2$-binding, and
$\epsilon$-weakly-secure, such that $\epsilon_{n}\geq 0$ and
$\epsilon_{n}\rightarrow 0$ as $n\rightarrow\infty$.

For these sequence of protocols, we state the following lemma which upper
bounds the conditional entropy $\frac{1}{n}H(C|\mathbf{X},V_{B},V_{E})$ using
Fano’s inequality; similar to the $1$-privacy case, we will use this lemma
later to upper bound the commitment rate.

######  Lemma 2.

For every commitment protocol $\mathscr{P}_{n}$ satisfying all the security
guarantees under $2-$privacy, we have
$\frac{1}{n}H(C|\mathbf{X},V_{B},V_{E})\leq\epsilon^{\prime\prime}_{n}$, where
$\epsilon^{\prime\prime}_{n}\rightarrow 0$ as $n\rightarrow\infty$.

The proof appears in Appendix -A, and follows from the fact that each protocol
$\mathscr{P}_{n}$ satisfies $\epsilon_{n}-$soundness and
$\epsilon_{n}-$2$-$bindingness.

Let us now bound the commitment rate $R$ as follows:

$\displaystyle R$ $\displaystyle\stackrel{{\scriptstyle}}{{=}}\frac{1}{n}H(C)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\frac{1}{n}H(C|V_{B},V_{E})+\frac{1}{n}I(C;V_{B},V_{E})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\frac{1}{n}H(C|V_{B},V_{E})+\epsilon_{n}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}\frac{1}{n}H(C|{\mathbf{Y}},\mathbf{Z},K_{B},K_{E},M)+\epsilon_{n}$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\leq}}\frac{1}{n}H(C,\mathbf{X}|{\mathbf{Y}},\mathbf{Z},K_{B},K_{E},M)+\epsilon_{n}$
$\displaystyle\stackrel{{\scriptstyle(e)}}{{=}}\frac{1}{n}H(\mathbf{X}|{\mathbf{Y}},\mathbf{Z},K_{B},K_{E},M)$
$\displaystyle\hskip
28.45274pt+\frac{1}{n}H(C|\mathbf{X},{\mathbf{Y}},\mathbf{Z},K_{B},K_{E},M)+\epsilon_{n}$
$\displaystyle\stackrel{{\scriptstyle}}{{=}}\frac{1}{n}H(\mathbf{X}|{\mathbf{Y}},\mathbf{Z},K_{B},K_{E},M)+\frac{1}{n}H(C|\mathbf{X},V_{B},V_{E})+\epsilon_{n}$
$\displaystyle\stackrel{{\scriptstyle(f)}}{{\leq}}\frac{1}{n}H(\mathbf{X}|{\mathbf{Y},\mathbf{Z}})+\epsilon^{\prime\prime}_{n}+\epsilon_{n}$
$\displaystyle\stackrel{{\scriptstyle}}{{\leq}}\frac{1}{n}\sum_{i=1}^{n}H(X_{i}|Y_{i},Z_{i})+\epsilon^{\prime\prime}_{n}+\epsilon_{n}$
$\displaystyle\stackrel{{\scriptstyle}}{{\leq}}\max_{P_{X}}H(X|Y,Z)+\epsilon^{\prime\prime}_{n}+\epsilon_{n}$
(16)

Here,

  1. (a)

follows from the definition of mutual information.

  2. (b)

follows from the fact that every commitment protocol in the sequence
$\mathscr{P}_{n}$ is $\epsilon_{n}$-weakly-$2$-concealing.

  3. (c)

follows from noting that the collective view of colluding Bob and Eve is
$(V_{B},V_{E})=(\mathbf{Y},\mathbf{Z},K_{B},K_{E},M)$.

  4. (d)

follows from property of joint entropy.

  5. (e)

follows from the chain rule of joint entropy.

  6. (f)

follows from lemma 2 and noting that conditioning reduces entropy.

Therefore, finally we have the following upper bpund on the commitment rate
for a wiretapped broadcast channel $W_{Y,Z|X}$ under $2-$privacy:

$\displaystyle R$
$\displaystyle\stackrel{{\scriptstyle}}{{\leq}}\max_{P_{X}}H(X|YZ)$ (17)

On solving Eq. (17) for the independent binary symmetric broadcast (I-BS-
BC$(p,q)$) wiretap channels, we have the following upper bound on the
commitment rate for I-BS-BC$(p,q)$ under $2-$privacy:

$\displaystyle R$
$\displaystyle\stackrel{{\scriptstyle}}{{\leq}}H(p)+H(q)-H(p\circledast q)$
(18)

where $p\circledast q:=p(1-q)+(1-p)q$, $\forall p,q\in[0,1]$ is the binary
convolution between $p$ and $q$, and we observe that the optimizing the input
distribution is $X\sim\text{Bernoulli}(1/2)$. This completes our converse
analysis.

###  V-C Achievability for the BS-BC$({p,q})$ wiretap channel under
$1-$privacy.

Our achievability protocol is inspired by works in [7, 8, 26] which utilize
random hash exchange challenges and a strong randomness extractor based on
2-universal hash functions. However, unlike previous works, our scheme just
requires one round of random hash challenge essentially to _bind_ Alice to her
choice in the commit phase thereby ensuring Bob’s test $T$ can detect any
cheating attempt by a malicious Alice during the reveal phase. The strong
randomness extractor ‘Ext’ extracts a secret key $\text{Ext}(\mathbf{X})$ with
$nR$ nearly random bits from $\mathbf{X}$. (note that the leftover hash lemma
[27] allows us to quantify the size of this key). This secret key is then XOR-
ed with the commit string $c$ to realize a _one-time pad_ scheme, which
conceals the committed string against a malicious Bob and the wiretapper Eve
in the commit phase.

Here are the details of our protocol. The rate
$R:=\min\\{H(p),H(q)\\}-\beta_{2}$, where the choice of $\beta_{2}>0$ is
specified later. Let
$\mathcal{G}:=\\{g:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{n\beta_{1}}\\}$ be a
$2-$universal hash family, where $\beta_{2}>\beta_{1}>0$ is a small enough
constant. Further, let
$\mathcal{E}:=\\{\text{ext}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{nR}\\}$ be a
$2-$universal hash family. 888Note that $R$ can be made arbitrarily close to
$\mathbb{C}.$

We now describe the commit and reveal phases:

$\bullet$ _Commit Phase:_ To commit string $c\in[2^{nR}]$, the protocol
proceeds as follows:

(C1). Given $c$, Alice sends $\mathbf{X}\sim\text{Bernoulli}(1/2)$ independent
and identically distributed (i.i.d.) over the BS-BC$({p,q})$ wiretap channel;
Bob receives $\mathbf{Y}$ while Eve receives $\mathbf{Z}$.

(C2). Bob chooses a hash function $G\sim\text{Unif}\left(\mathcal{G}\right)$,
and sends the description of $G$ to Alice over the noiseless channel.

(C3). Alice computes $G(\mathbf{X})$ and sends it to Bob over the noiseless
channel.

(C4). Alice chooses an extractor function
$\text{Ext}\sim\text{Unif}\left(\mathcal{E}\right)$ and sends
$Q=c\oplus\text{Ext}(\mathbf{X})$ and the description of Ext to Bob i.e.,
$(Q,\text{Ext})$ over the noiseless link.999In the following expression,
operator $\oplus$ denotes component-wise XOR.

$\bullet$ _Reveal Phase:_ Alice proceeds as follows:

(R1). Having received $\mathbf{Y}=\mathbf{y}$, Bob creates list ${\cal
L}(\mathbf{y})$ of vectors given by:101010Here the parameter $\alpha_{1}>0$ is
chosen appropriately small.

$\displaystyle{\cal
L}(\mathbf{y}):=\\{\mathbf{x}\in\\{0,1\\}^{n}:n(p-\alpha_{1})\leq
d_{H}(\mathbf{x},\mathbf{y})\leq n(p+\alpha_{1})\\}.$

(R2). Alice announces $(\tilde{c},\tilde{\mathbf{x}})$ to Bob over the
noiseless link.

(R3). Bob accepts $\tilde{c}$ if all the following three conditions are
satisfied: $(i)$ $\tilde{\mathbf{x}}\in{\cal L}(\mathbf{y})$, $(ii)$
$g(\tilde{\mathbf{x}})=g({\mathbf{x}})$, and $(iii)$
$\tilde{c}=q~{}\oplus\text{ext}(\tilde{\mathbf{x}})$. Else, he rejects
$\tilde{c}$ and outputs ‘0’.

Note that the wiretapper Eve also has the access to the noiseless channel so
it observes everything shared between Alice and Bob over the noiseless channel
during the commit as well as the reveal phase.

We now analyse and prove the security guarantees under $1-$privacy in detail
for the $(n,R)$-commitment scheme, defined above:

[1] _$\epsilon-$ sound:_ For our protocol to be $\epsilon$-sound, it is
sufficient to show that $\mathbb{P}\left(\mathbf{X}\not\in{\cal
L}(\mathbf{Y})\right)\leq\epsilon$ when both the parties, Alice and Bob, are
honest; the proof for the same follows from classic Chernoff bounds.

[2] _$\epsilon-1-$ concealing & $\epsilon-$secure:_ It is known that a
positive rate commitment protocol is $\epsilon-1-$concealing and
$\epsilon-$secure 111111where $\epsilon>0$ is _exponentially decreasing_ in
blocklength $n$. if it satisfies the notion of _capacity-based secrecy_ (cf.
[28, Def. 3.2]) i.e., $I(C;V_{B})\leq\epsilon$ and $I(C;V_{E})\leq\epsilon$,
respectively and vice versa. We use a well established equivalence relation
between _capacity-based secrecy_ and the _bias-based secrecy_ (cf. [28, Th.
4.1]) to prove that our protocol is $\epsilon$-concealing.

To begin, we prove that our protocol satisfies bias-based secrecy by
essentially proving the perfect secrecy of the key $\text{Ext}(\mathbf{X})$;
here we crucially use the _leftover hash_ lemma. Several versions of this
lemma exists (cf. [29, 27] for instance); we use the following (without
proof):

######  Lemma 3 (Leftover hash lemma).

Let $\mathcal{G}=\\{G:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{l}\\}$ be a family of
universal hash functions. Then, for any hash function $G$ chosen uniformly at
random from $\mathcal{G}$, and $W$

$\displaystyle\|(P_{G(W),G}-P_{U_{l},G})\|$
$\displaystyle\leq\frac{1}{2}\sqrt{2^{-H_{\infty}(W)}2{{}^{l}}}$

where $U_{l}\sim\text{Unif}\left(\\{0,1\\}^{l}\right).$

We begin by establishing the following lower bounds in Lemma 4 and Lemma 5
which quantify the left-over uncertainity in $\mathbf{X}$, after the
information about $\mathbf{X}$ is lost to Bob and Eve due to the access of
$(\mathbf{Y},G,G(\mathbf{X}))$ and $(\mathbf{Z},G,G(\mathbf{X}))$,
respectively:

######  Lemma 4.

For any $\epsilon_{1}>0,\zeta_{1}>0$ and $n$ sufficiently large,

$\displaystyle H_{\infty}^{\epsilon_{1}}$
$\displaystyle(\mathbf{X}|\mathbf{Y},G,G(\mathbf{X}))$
$\displaystyle\stackrel{{\scriptstyle}}{{\geq}}{n(H(p)-\zeta_{1}-\beta_{1})}-\log(\epsilon_{1}^{-1})$
(19)

The proof appears in Appendix -B.

######  Lemma 5.

For any $\epsilon_{1}>0,\zeta_{2}>0$ and $n$ sufficiently large,

$\displaystyle H_{\infty}^{\epsilon_{1}}$
$\displaystyle(\mathbf{X}|\mathbf{Z},G,G(\mathbf{X}))$
$\displaystyle\stackrel{{\scriptstyle}}{{\geq}}{n(H(q)-\zeta_{2}-\beta_{1})}-\log(\epsilon_{1}^{-1})$
(20)

The proof appears in Appendix -B.

From Lemma 4 and Lemma 5, we have:

$\displaystyle H_{\infty}(\mathbf{X})$
$\displaystyle\geq\min\\{H_{\infty}(\mathbf{X}|\mathbf{Y},G,G(\mathbf{X})),H_{\infty}(\mathbf{X}|\mathbf{Z},G,G(\mathbf{X}))\\}$
$\displaystyle\geq
n\left\\{\min\\{H(p),H(q)\\}-\max\\{\zeta_{1},\zeta_{2}\\}-\beta_{1}\right\\}$
$\displaystyle\hskip 142.26378pt-\log(\epsilon_{1}^{-1})$ (21)

Now, we crucially use leftover hash lemma (Lemma 3) to show that $nR$ nearly
random bits can be extracted from $\mathbf{X}$ in the form of
$\text{Ext}(\mathbf{X})$ using the $2-$Universal hash function Ext (the key
$\text{Ext}(\mathbf{X})$ has nearly uniform distribution). This shows that the
protocol satisfies _bias-based secrecy_.

Let us fix $\epsilon_{1}:=2^{-n\alpha_{2}}$, where $\alpha_{2}>0$ is an
arbitrary small constant. We make the following correspondence in Lemma 3:
$G\leftrightarrow\text{Ext}$, $W\leftrightarrow\mathbf{X}$ and
$l\leftrightarrow nR$ to get the following:

$\displaystyle\|$ $\displaystyle
P_{\text{Ext}(\mathbf{X}),\text{Ext}}-P_{U_{l},\text{Ext}}\|$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\frac{1}{2}\sqrt{2^{-H_{\infty}(\mathbf{X})}2{{}^{nR}}}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\frac{1}{2}\sqrt{2^{-n(\min\\{H(p),H(q)\\}-\max\\{\zeta_{1},\zeta_{2}\\}-\beta_{1}-\alpha_{2})}}$
$\displaystyle\hskip 128.0374pt.\sqrt{2^{n(\min\\{H(p),H(q)\\}-\beta_{2})}}$
$\displaystyle=\frac{1}{2}\sqrt{2^{n(\max\\{\zeta_{1},\zeta_{2}\\}+\beta_{1}+\alpha_{2}-\beta_{2}))}}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}2^{-n\alpha_{3}}$ (22)

where, $\alpha_{3}>0$ and $n$ is sufficiently large. Here,

  1. (a)

follows directly from Lemma 3.

  2. (b)

follows from (21) and noting that the choice of Ext is random and uniform from
${\mathcal{E}}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{nR}$ where
$R:=\min\\{H(p),H(q)\\}-\beta_{2}$.

  3. (c)

follows from noting that $\beta_{2}$ is chosen such that
$\max\\{\zeta_{1},\zeta_{2}\\}+\beta_{1}+\alpha_{2}-\beta_{2}<0$; here, we
note that $\alpha_{2}$ is an arbitrarily chosen (small enough) constant, and
$\zeta_{1},\zeta_{2}>0$ can be made arbitrarily small for sufficiently large
$n$. Thus, a choice of $\beta_{2}>\beta_{1}$ is sufficient.

Thus, this proves that our commitment protocol satisfies bias-based secrecy
(cf. [28, Def. 3.1]). Recall from our discussion earlier (see also [28, Th.
4.1]) that bias-based secrecy under _exponentially decaying_ statistical
distance, as in (22), implies capacity-based secrecy; hence, it follows that
for $n$ sufficiently large, we have
$\max\\{I(C;V_{B}),I(C;V_{E})\\}\leq\epsilon$ and our protocol is
$\epsilon-1-$concealing as well as $\epsilon-$secure.

[3] _$\epsilon-1-$ binding:_ A commitment protocol satisfies
$\epsilon-1-$bindingness if under _any_ behaviour of a malicicous Alice
(without colluding with Eve), Bob can verify (with high probability) if
Alice’s revelation in the reveal phase $(\tilde{c},\tilde{\mathbf{x}})$ are
similar or different to it’s choices in the commit phase.

Note that here in the $1-$privacy case, we only need to guarantee bindingness
only between a malicious Alice (who does not colludes with the wiretapper Eve)
and a honest Bob. Therefore, the $1-$bindingess analysis is almost similar to
the case in which the wiretapper Eve is absent and there is a one-way BSC(p)
from Alice to Bob.

Thus, let $\mathbf{X}=\mathbf{x}$ be the transmitted bit string and
$\mathbf{Y}=\mathbf{y}$ be the bit string received by Bob’s over the I-BS-
BC$(p,q)$. Alice can cheat successfully by confusing Bob in the reveal phase
only if she can find two distinct bit strings $\mathbf{x}^{\prime}$ and
$\tilde{\mathbf{x}}$ such that (i)
$\mathbf{x}^{\prime},\tilde{\mathbf{x}}\in{\cal L}(\mathbf{y})$, and (ii)
$\mathbf{x}^{\prime}$, $\tilde{\mathbf{x}}$ pass the random hash exchange
challenge (w.r.t hash functon $G(\cdot)$). The number of such strings that
Alice can use to confuse Bob and that can pass the Bob’s first test in the
reveal phase are exponentially many in $n$; in particular, if ${\cal A}$
denotes this set of strings that Alice can choose to reveal in the reveal
phase. Then, we have

$\displaystyle|{\cal A}|$
$\displaystyle\stackrel{{\scriptstyle}}{{\leq}}2^{n\eta}$ (23)

where $\eta>0$.

Next, we show that the probability of hash collision for any two bit strings
$\mathbf{x}$ and $\mathbf{x}^{\prime}$ in $\mathcal{A}$ is exponentially
decaying in $n$, i,e., the hash challenge prevents any malicious action of
Alice.

######  Claim 1.

For $n$ sufficiently large,

$\displaystyle\mathbb{P}$
$\displaystyle\Bigg{(}\exists\mathbf{x}\neq\mathbf{x}^{\prime}\in\mathcal{A}:G(\mathbf{x})=G(\mathbf{x}^{\prime})\Bigg{)}\leq
2^{-n\beta^{\prime}}$ (24)

The proof of the Claim appears in the Appendix -C.

The fact that the secuirty parameter $\beta^{\prime}>0$, shows that our
commitment protocol is $\epsilon-$binding.

###  V-D Achievability for I-BS-BC$(p,q)$ wiretap channel under $2-$privacy.

Similar to the previous case, this achievability protocol is also inspired by
works in [7, 8, 26] and just requires one round of random hash challenge
essentially to _bind_ Alice to her choice in the commit phase.

Here are the details of our protocol. The rate
$R:=\min\\{H(p)+H(q)-H(p\circledast q)\\}-\beta_{2}$, where the choice of
$\beta_{2}>0$ is specified later. Let
$\mathcal{G}:=\\{g:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{n\beta_{1}}\\}$ be a
$2-$universal hash family, where $\beta_{2}>\beta_{1}>0$ is a small enough
constant. Further, let
$\mathcal{E}:=\\{\text{ext}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{nR}\\}$ be a
$2-$universal hash family. 121212Note that $R$ can be made arbitrarily close
to $\mathbb{C}.$

We now describe the commit and reveal phases:

$\bullet$ _Commit Phase:_ To commit string $c\in[2^{nR}]$, the protocol
proceeds as follows:

(C1). Given $c$, Alice sends $\mathbf{X}\sim\text{Bernoulli}(1/2)$ independent
and identically distributed (i.i.d.) over the I-BS-BC$(p,q)$ wiretap channel;
Bob receives $\mathbf{Y}$ and Eve receives $\mathbf{Z}$.

(C2). Bob chooses a hash function $G\sim\text{Unif}\left(\mathcal{G}\right)$,
and sends the description of $G$ to Alice over the noiseless channel.

(C3). Alice computes $G(\mathbf{X})$ and sends it to Bob over the noiseless
channel.

(C4). Alice chooses an extractor function
$\text{Ext}\sim\text{Unif}\left(\mathcal{E}\right)$ and sends
$Q=c\oplus\text{Ext}(\mathbf{X})$ and the description of Ext to Bob i.e.,
$(Q,\text{Ext})$ over the noiseless link.131313In the following expression,
operator $\oplus$ denotes component-wise XOR.

$\bullet$ _Reveal Phase:_ Alice proceeds as follows:

(R1). Having received $\mathbf{Y}=\mathbf{y}$, Bob creates list ${\cal
L}(\mathbf{y})$ of vectors given by:141414Here the parameter $\alpha_{1}>0$ is
chosen appropriately small.

$\displaystyle{\cal
L}(\mathbf{y}):=\\{\mathbf{x}\in\\{0,1\\}^{n}:n(p-\alpha_{1})\leq
d_{H}(\mathbf{x},\mathbf{y})\leq n(p+\alpha_{1})\\}.$

(R2). Alice announces $(\tilde{c},\tilde{\mathbf{x}})$ to Bob over the
noiseless link.

(R3). Bob accepts $\tilde{c}$ if all the following three conditions are
satisfied:
$(i)$ $\tilde{\mathbf{x}}\in{\cal L}(\mathbf{y})$,
$(ii)$ $g(\tilde{\mathbf{x}})=g({\mathbf{x}})$, and
$(iii)$ $\tilde{c}=q~{}\oplus\text{ext}(\tilde{\mathbf{x}})$.

Else, he rejects $\tilde{c}$ and outputs ‘0’.

Note that the eavesdropper Eve also has the access to the noiseless channel so
it observes everything shared between Alice and Bob over the noiseless channel
during the commit as well as the reveal phase.

We now analyse and prove the security guarantees under $2-$privacy in detail
for the $(n,R)$-commitment scheme, defined above:

[1] _$\epsilon-$ sound:_ This is similar to proving the $\epsilon-$soundness
for the case of $1-$privacy. For our protocol to be $\epsilon$-sound, it is
sufficient to show that $\mathbb{P}\left(\mathbf{X}\not\in{\cal
L}(\mathbf{Y})\right)\leq\epsilon$ when both the parties, Alice and Bob, are
honest; the proof for the same follows from classic Chernoff bounds.

[2] _$\epsilon-2-$ concealing:_ It is known that a positive rate commitment
protocol is $\epsilon-2-$concealing if it satisfies the notion of _capacity-
based secrecy_ (cf. [28, Def. 3.2]) i.e., $I(C;V_{B},V_{E})\leq\epsilon$, and
vice versa. We use a well established relation between _capacity-based
secrecy_ and the _bias-based secrecy_ (cf. [28, Th. 4.1]) to prove that our
protocol is $\epsilon-2-$concealing.

We begin by establishing the following lower bound in Lemma 6 and Lemma 5
which quantify the left-over uncertainity in $\mathbf{X}$, after the
information about $\mathbf{X}$ is lost to colluding Bob and Eve due to the
collective access of $(\mathbf{Y},\mathbf{Z},G,G(\mathbf{X}))$:

######  Lemma 6.

For any $\epsilon_{1}>0,\zeta_{1}>0$ and $n$ sufficiently large,

$\displaystyle H_{\infty}^{\epsilon_{1}}$
$\displaystyle(\mathbf{X}|\mathbf{Y},\mathbf{Z},G,G(\mathbf{X}))$
$\displaystyle\stackrel{{\scriptstyle}}{{\geq}}{n(H(p)+H(q)-H(p\circledast
q)-\zeta_{1}-\beta_{1})}-\log(\epsilon_{1}^{-1})$ (25)

The proof appears in Appendix -D.

Now, we crucially use leftover hash lemma (Lemma 3) to show that $nR$ nearly
random bits can be extracted from $\mathbf{X}$ in the form of
$\text{Ext}(\mathbf{X})$ using the $2-$Universal hash function Ext (the key
$\text{Ext}(\mathbf{X})$ has nearly uniform distribution). This shows that the
protocol satisfies _bias-based secrecy_.

Let us fix $\epsilon_{1}:=2^{-n\alpha_{2}}$, where $\alpha_{2}>0$ is an
arbitrary small constant. We make the following correspondence in Lemma 3:
$G\leftrightarrow\text{Ext}$, $W\leftrightarrow\mathbf{X}$ and
$l\leftrightarrow nR$ to get the following:

$\displaystyle\|(P_{\text{Ext}(\mathbf{X}),\text{Ext}}$ $\displaystyle-
P_{U_{l},\text{Ext}})\|$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\frac{1}{2}\sqrt{2^{-H_{\infty}(\mathbf{X})}2{{}^{l}}}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\frac{1}{2}\sqrt{2^{-H_{\infty}(\mathbf{X}|\mathbf{Y},\mathbf{Z},G(\mathbf{X}),G)}2{{}^{l}}}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\frac{1}{2}\sqrt{2^{-n(H(p)+H(q)-H(p\circledast
q)-\zeta-\beta_{1}-\alpha_{2})}}$ $\displaystyle\hskip
51.21495pt.\sqrt{2^{n(H(p)+H(q)-H(p\circledast q)-\beta_{2})}}$
$\displaystyle=\frac{1}{2}\sqrt{2^{n(\zeta+\beta_{1}-\beta_{2}+\alpha_{2}))}}$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\leq}}2^{-n\alpha_{3}}$ (26)

where, $\alpha_{3}>0$ and $n$ is sufficiently large. Here,

  1. (a)

follows from Lemma 3.

  2. (b)

follows from noting that min-entropy upper bounds conditional min-entropy.

  3. (c)

follows from Lemma 4 and noting that $R:=H(p)+H(q)-H(p\circledast
q)-\beta_{2}$ for arbitrarily small $\beta_{2}$.

  4. (d)

follows from noting that $\beta_{2}$ is chosen such that
$\zeta+\beta_{1}+\alpha_{2}-\beta_{2}<0$; here, we note that $\zeta$ and
$\alpha_{2}$ can be made arbitrarily small for sufficiently large $n$,
therefore, a choice of $\beta_{2}>\beta_{1}$ is sufficient.

From (26) and Lemma 3, it follows that the specified commitment protocol
satisfies biased-based secrecy which further implies capacity-based secrecy.
Thus, our protocol satisfies $\epsilon$-concealment for sufficiently large
$n$.

[3] _$\epsilon-2-$ binding:_ A commitment protocol satisfies
$\epsilon$-bindingness if under _any_ behaviour of colluding Alice and Eve,
Bob is able to verify (with high probability) if Alice’s revelation in the
reveal phase $(\tilde{c},\tilde{\mathbf{x}})$ are similar to it’s choices in
the commit phase or are different.

Note that for the independent broadcast wiretap channel $W_{Y,Z|X}$, we have
the following decomposition $W_{Y,Z|X}=W_{Y|X}W_{Z|X}$, and thus the following
markov chain $Y-X-Z$ holds.

It implies that eventually Alice colluding with Eve doesn’t helps Alice in
extracting any extra information about the vector $\mathbf{Y}$ received by Bob
i.e., $H(\mathbf{Y}|\mathbf{X},\mathbf{Z})=H(\mathbf{Y}|\mathbf{X})$. Thus,
the sender Alice in the $2-$privacy case is only as powerful as in the
$1-$privacy case without colluding with Eve. Thus, our bindingness analysis
for the $2-$privacy case is similar to the analysis for the $1-$privacy case,
in the previous subsection. This completes our analysis for
$\epsilon-2-$bindingness.

[4] _$\epsilon-$ secure:_ A commitment protocol is $\epsilon-$secure if for
any behaviour of the wiretapper Eve, we have $I(C;V_{E})\leq\epsilon$.

This directly holds due to the fact that our commitment protocol satisfies
$\epsilon-2-$concealment. As a result, we have

$\displaystyle I(C;V_{E})$ $\displaystyle\leq I(C;V_{E},V_{B})$
$\displaystyle\leq\epsilon$ (27)

where $\epsilon$ is exponentially decaying in the blocklength $n$. Therefore,
our commitment protocol is $\epsilon-$secure against Eve.

##  VI Concluding Remarks and Discussion

We initiated the study of wiretapped commitment in the presence of an
eavesdropper in this work. We studied the maximum commitment throughput a.k.a
commitment capacity of certain subclasses of wiretap channels by providing
security guarantees under two regimes i.e., $1-$privacy - where the
eavesdropper cannot collude with any of the legitimate parties of the
commitment protocol, and $2-$privacy - in which the eavesdropper can collude
with (atmost) one of the legitimate (malicious) parties to affect the
protocol.

Our converse bounds under the $1-$privacy regime as well as under the
$2-$privacy regime hold for any wiretap channel. Then, under $1-$privacy we
provided a matching achievability for BS-BC wiretap channels and completely
characterized their $1-$privacy commitment capacity. In the $2-$privacy
regime, we provided a matching achievability for I-BS-BC wiretap channel
(which form a sub-class of the BS-BC wiretap channels) and thus, also
completely characterized the $2-$privacy commitment capacity of the I-BS-BC
wiretap channel. Also, it is important to note that our $1-$privacy converse
proof for $R\leq\max_{P_{X}}H(X|Z)$ assumes the independence of the public
communication and the channel output, given the channel input. While, it seems
a fairly natural assumption in commitment protocols, we believe there might
exist a more general converse proof which bypasses this asumption of the
markov chain.

The degraded binary symmetric broadcast (D-BS-BC) wiretap channel presents an
interesting challenge in the $2-$privacy regime. While the upper bound in Eq.
(2) holds, it can be shown that the bound is quite weak (we conjecture that
the capacity in this case will be strictly lower than in Eq. (2) for
meaningful values of $p,q$). The key challenge for this setup resides in
analysing the effect of collusion between Alice and Eve (and the accompanying
commitment rate penalty).

##  VII Acknowledgements

A. K. Yadav was partially supported by the Swiss National Science Foundation
(SNSF) grant No 211337\. M. Mamindlapally was partially supported by the Dutch
Research Council (NWO) as part of the project Divide and Quantum ‘D&Q’
NWA.1389.20.241 of the program ‘NWA-ORC’. A. J. Budkuley was partially
supported by Dept. of Science and Technology, Govt. of India, through grant
MTR/2023/001412.

## References

  * [1] M. Blum, “Coin flipping by telephone a protocol for solving impossible problems,” _ACM SIGACT News_ , vol. 15, no. 1, pp. 23–27, Jan. 1983.
  * [2] A. D. Wyner, “The wire-tap channel,” _Bell system technical journal_ , vol. 54, no. 8, pp. 1355–1387, 1975.
  * [3] C. Crépeau and J. Kilian, “Achieving oblivious transfer using weakened security assumptions,” in _[Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science_. IEEE Computer Society, 1988, pp. 42–52.
  * [4] C. Crépeau, “Efficient cryptographic protocols based on noisy channels,” in _Proceedings of the 16th annual international conference on Theory and application of cryptographic techniques_ , ser. EUROCRYPT’97. Berlin, Heidelberg: Springer-Verlag, May 1997, pp. 306–317.
  * [5] A. Winter, A. C. A. Nascimento, and H. Imai, “Commitment capacity of discrete memoryless channels,” in _IMA International Conference on Cryptography and Coding_. Springer, 2003, pp. 35–51.
  * [6] M. Mamindlapally, A. K. Yadav, M. Mishra, and A. J. Budkuley, “Commitment capacity under cost constraints,” in _2021 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2021, pp. 3208–3213.
  * [7] I. Damgård, J. Kilian, and L. Salvail, “On the (im) possibility of basing oblivious transfer and bit commitment on weakened security assumptions,” in _International Conference on the Theory and Applications of Cryptographic Techniques_. Springer, 1999, pp. 56–73.
  * [8] C. Crépeau, R. Dowsley, and A. C. A. Nascimento, “On the commitment capacity of unfair noisy channels,” _IEEE Transactions on Information Theory_ , vol. 66, no. 6, pp. 3745–3752, 2020.
  * [9] A. Budkuley, P. Joshi, M. Mamindlapally, and A. K. Yadav, “On the (im) possibility of commitment over gaussian unfair noisy channels,” in _2023 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2023, pp. 483–488.
  * [10] D. Khurana, H. K. Maji, and A. Sahai, “Secure computation from elastic noisy channels,” in _Annual International Conference on the Theory and Applications of Cryptographic Techniques_. Springer, 2016, pp. 184–212.
  * [11] A. J. Budkuley, P. Joshi, M. Mamindlapally, and A. K. Yadav, “On reverse elastic channels and the asymmetry of commitment capacity under channel elasticity,” _IEEE Journal on Selected Areas in Communications_ , 2022.
  * [12] H.-K. Lo and H. F. Chau, “Why quantum bit commitment and ideal quantum coin tossing are impossible,” _Physica D: Nonlinear Phenomena_ , vol. 120, no. 1-2, pp. 177–187, 1998.
  * [13] M. Fischlin, “Trapdoor commitment schemes and their applications,” Ph.D. dissertation, Frankfurt (Main), Univ., Diss., 2001, 2001.
  * [14] A. Juels and M. Wattenberg, “A fuzzy commitment scheme,” in _Proceedings of the 6th ACM conference on Computer and communications security_ , 1999, pp. 28–36.
  * [15] R. Chou and M. R. Bloch, “Commitment over multiple-access channels,” in _2022 58th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , 2022, pp. 1–6.
  * [16] M. Mishra, B. K. Dey, V. M. Prabhakaran, and S. N. Diggavi, “Wiretapped oblivious transfer,” _IEEE Transactions on Information Theory_ , vol. 63, no. 4, pp. 2560–2595, 2017.
  * [17] M. Mishra, B. K. Dey, V. M. Prabhakaran, and S. Diggavi, “The oblivious transfer capacity of the wiretapped binary erasure channel,” in _2014 IEEE International Symposium on Information Theory_ , 2014, pp. 1539–1543.
  * [18] H. Imai, K. Morozov, A. C. A. Nascimento, and A. Winter, “Efficient protocols achieving the commitment capacity of noisy correlations,” in _2006 IEEE International Symposium on Information Theory_ , 2006, pp. 1432–1436.
  * [19] A. C. B. Pinto, R. Dowsley, K. Morozov, and A. C. A. Nascimento, “Achieving oblivious transfer capacity of generalized erasure channels in the malicious model,” _IEEE Transactions on Information Theory_ , vol. 57, no. 8, pp. 5566–5571, 2011.
  * [20] A. K. Yadav and P. Kumar, “Oblivious transfer over compound binary erasure channels,” _IEEE Communications Letters_ , vol. 26, no. 5, pp. 979–983, 2022.
  * [21] N. Nisan and D. Zuckerman, “Randomness is linear in space,” _Journal of Computer and System Sciences_ , vol. 52, no. 1, pp. 43–52, 1996.
  * [22] Y. Dodis, L. Reyzin, and A. Smith, “Fuzzy extractors: How to generate strong keys from biometrics and other noisy data,” in _International conference on the theory and applications of cryptographic techniques_. Springer, 2004, pp. 523–540.
  * [23] M. Bloch and J. Barros, _Physical-Layer Security: From Information Theory to Security Engineering_. Cambridge: Cambridge University Press, 2011.
  * [24] A. D. Wyner, “The rate-distortion function for source coding with side information at the decoder-ii: General source,” _Information and Control_ , vol. 38, pp. 60–80, 1978.
  * [25] A. E. Gamal and Y.-H. Kim, _Network Information Theory_. Cambridge University Press, 2011.
  * [26] A. K. Yadav, M. Mamindlapally, A. J. Budkuley, and M. Mishra, “Commitment over compound binary symmetric channels,” in _2021 National Conference on Communications (NCC)_. IEEE, 2021, pp. 1–6.
  * [27] Y. Dodis, L. Reyzin, and A. Smith, “Fuzzy extractors: How to generate strong keys from biometrics and other noisy data,” in _International conference on the theory and applications of cryptographic techniques_. Springer, 2004, pp. 523–540.
  * [28] I. B. Damgard, T. P. Pedersen, and B. Pfitzmann, “Statistical secrecy and multibit commitments,” _IEEE Transactions on Information Theory_ , vol. 44, no. 3, pp. 1143–1151, 1998.
  * [29] R. Impagliazzo, L. A. Levin, and M. Luby, “Pseudo-random generation from one-way functions,” in _Proceedings of the twenty-first annual ACM symposium on Theory of computing_ , 1989, pp. 12–24.
  * [30] A. Vitanov, F. Dupuis, M. Tomamichel, and R. Renner, “Chain rules for smooth min- and max-entropies,” _IEEE Transactions on Information Theory_ , vol. 59, no. 5, pp. 2603–2612, 2013.
  * [31] R. Renner and S. Wolf, “Simple and tight bounds for information reconciliation and privacy amplification,” in _Advances in Cryptology - ASIACRYPT 2005_ , B. Roy, Ed. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005, pp. 199–216.
  * [32] A. C. A. Nascimento, J. Barros, S. Skludarek, and H. Imai, “The Commitment Capacity of the Gaussian Channel Is Infinite,” _IEEE Transactions on Information Theory_ , vol. 54, no. 6, pp. 2785–2789, Jun. 2008.

###  -A Proof of Lemma 1 and Lemma 2

Recall that $V_{B}$ denotes the view of Bob at the end of commit phase.

Let’s define151515Although Bob’s test $T$ is a randomized test, it can be
shown that one can construct from $T$ a deterministic test with essentially
the same soundness and bindingness performance. Hence, for the rest of the
converse, we consider that Bob’s test is a deterministic function; as such,
$\tilde{c}$ is well defined for such a deterministic test.
$\tilde{c}:=\arg\max_{c\in[2^{nR}]}T(\tilde{c},\mathbf{X},V_{B}).$ Now, we
will bound from above $\mathbb{P}(\hat{C}\neq C)$, where
$\hat{C}=\hat{C}(V_{B},\mathbf{X})=\tilde{c}$. As the commitment scheme is
$\epsilon_{n}-2-$binding for the $2-$privacy case (similarly, $1-$binding for
the $1-$privacy case), we know that,

$\displaystyle\mathbb{P}\left(T(\bar{c},\bar{\mathbf{X}},V_{B})=1\quad\&\quad
T(\hat{c},\hat{\mathbf{X}},V_{B})=1\right)\leq\epsilon_{n}$ (28)

for any two distinct $(\bar{c},\bar{\mathbf{X}})$ and
$(\hat{c},\hat{\mathbf{X}})$ under any behaviour of Alice under possible
collusion with Eve (any behaviour of Alice under no collusion with Eve, in the
$1-$privacy case). Thus, for the given decoder, we have

$\displaystyle\mathbb{P}(\hat{C}\neq C)$
$\displaystyle=\mathbb{P}(\hat{C}=0)+\mathbb{P}(\hat{C}\neq C|C\neq 0)$
$\displaystyle\leq\epsilon_{n}+\epsilon_{n}$ $\displaystyle=2\epsilon_{n}.$
(29)

where in the penultimate inequality, the first part follows from noting that
$\mathscr{P}_{n}$ is $\epsilon_{n}-2-$binding, and the second part follows
from the fact that conditioned on $\mathscr{P}_{n}$ being
$\epsilon_{n}-2-$binding, the probability that $\hat{C}$ is different from $C$
is at most $\epsilon_{n}$ due to $\mathscr{P}_{n}$ being $\epsilon_{n}$-sound.

We now use Fano’s inequality (cf. [25]) to upper bound the following
conditional entropy.

$\displaystyle H(C|\mathbf{X},V_{B},V_{E})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}H(C|\mathbf{X},V_{B})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}1+\mathbb{P}(\hat{C}\neq
C)nR$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}n\left(\frac{1}{n}+2\epsilon_{n}R\right)$
$\displaystyle\leq n\epsilon^{\prime}_{n}$ (30)

where $\epsilon^{\prime}_{n}\rightarrow 0$ as $n\rightarrow\infty$, and

  1. (a)

follows from noting that conditioning reduces entropy.

  2. (b)

follows from the Fano’s inequality (cf. [25]).

  3. (c)

follows from Eq. (29).

This completes the proof of the Lemma 1 as well as Lemma 2.

###  -B Proof of Lemma 4 and Lemmma 5

Before we start with the proof, we recap a few well known results (without
proof) which will be needed in our proof.

######  Claim 2 (Min-entropy [30, 31]).

For any $0\leq\mu,\mu^{\prime},\mu_{1},\mu_{2}<1$ and any set of jointly
distributed random variables $(X,Y,W)$, we have

$\displaystyle
H_{\infty}^{\mu+\mu^{{}^{\prime}}}(X,Y|W)-H_{\infty}^{\mu^{{}^{\prime}}}(Y|W)$
$\displaystyle\geq H_{\infty}^{\mu}(X|Y,W)$ (31) $\displaystyle\geq
H_{\infty}^{\mu_{1}}(X,Y|W)-H_{0}^{\mu_{2}}(Y|W)-\log\left[\frac{1}{\mu-\mu_{1}-\mu_{2}}\right]$
(32)

######  Claim 3 (Max-entropy [30, 31]).

For any $0\leq\mu,\mu^{\prime},\mu_{1},\mu_{2}<1$ and any set of jointly
distributed random variables $(X,Y,W)$, we have

$\displaystyle
H_{0}^{\mu+\mu^{{}^{\prime}}}(X,Y|W)-H_{0}^{\mu^{{}^{\prime}}}(Y|W)$
$\displaystyle\leq H_{0}^{\mu}(X|Y,W)$ (33) $\displaystyle\leq
H_{0}^{\mu_{1}}(X,Y|W)-H_{\infty}^{\mu_{2}}(Y|W)+\log\left[\frac{1}{\mu-\mu_{1}-\mu_{2}}\right]$
(34)

Using the above two claims establishing a lower bound on the following smooth-
min-entropy:

$\displaystyle H_{\infty}^{\epsilon_{1}}$
$\displaystyle(\mathbf{X}|\mathbf{Y},G(\mathbf{X}),G)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}H_{\infty}(\mathbf{X},G(\mathbf{X}),|\mathbf{Y},G)$
$\displaystyle\hskip 28.45274pt-
H_{0}(G(\mathbf{X})|\mathbf{Y},G)-\log(\epsilon_{1}^{-1})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\geq}}H_{\infty}(\mathbf{X}|\mathbf{Y},G)+H_{\infty}(G(\mathbf{X})|\mathbf{Y},G,\mathbf{X})$
$\displaystyle\hskip 28.45274pt-
H_{0}(G(\mathbf{X})|\mathbf{Y},G)-\log(\epsilon_{1}^{-1})$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\geq}}H_{\infty}(\mathbf{X}|\mathbf{Y},G)$
$\displaystyle\hskip 28.45274pt-
H_{0}(G(\mathbf{X})|\mathbf{Y},G)-\log(\epsilon_{1}^{-1})$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{=}}H_{\infty}(\mathbf{X}|\mathbf{Y})-H_{0}(G(\mathbf{X})|\mathbf{Y},G)-\log(\epsilon_{1}^{-1})$
$\displaystyle\stackrel{{\scriptstyle(e)}}{{\geq}}(H(\mathbf{X}|\mathbf{Y})-\zeta_{1})-H_{0}(G(\mathbf{X})|\mathbf{Y},G)-\log(\epsilon_{1}^{-1})$
$\displaystyle\stackrel{{\scriptstyle(f)}}{{\geq}}{n(H(p)-\zeta_{1})}-n\beta_{1}-\log(\epsilon_{1}^{-1})$
$\displaystyle\stackrel{{\scriptstyle}}{{=}}{n(H(p)-\zeta_{1}-\beta_{1})}-\log(\epsilon_{1}^{-1})$
(35)

where we have

  1. (a)

from the chain rule for smooth min-entropy; see Claim 2 and substitute
$\mu=\epsilon_{1}$, $\mu_{1}=0$ and $\mu_{2}=0$ in Eq. (32).

  2. (b)

from the chain rule for min-entropy; see Claim 2 and and substitute $\mu=0$
and $\mu^{\prime}=0$ in Eq. (31).

  3. (c)

from the fact that $G(\mathbf{X})$ is a deterministic function of $G$ and
$\mathbf{X}$.

  4. (d)

by the Markov chain $\mathbf{X}-\mathbf{Y}-G$.

  5. (e)

from [32, Th. 1] which allows us to lower bound
$H_{\infty}(\mathbf{X}|\mathbf{Y})$ in terms of $H(\mathbf{X}|\mathbf{Y})$

  6. (f)

by noting that the effective channel from Alice to Bob is a BSC(p), and from
definition of max-entropy (also noting that the range of $G$ is
$\\{0,1\\}^{n\beta_{1}}$).

######  Remark 3.

The proof for Lemma 5 follows similarly. Note that in this case, the following
markov chain $\mathbf{X}-\mathbf{Z}-G$ exists. Additionally, we have
$H_{\infty}(\mathbf{X}|\mathbf{Z})\geq
H(\mathbf{X}|\mathbf{Z})-\zeta_{2}=H(q)-\zeta_{2}$, for arbitrarily small
constant $\zeta_{2}>0$.

###  -C Proof of Claim 1

Recall that $G\sim\text{Unif}\left(\mathcal{G}\right)$, where
$\mathcal{G}=\\{g:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{n\beta_{1}}\\}$.
Therefore for any $\mathbf{x},\mathbf{x}^{\prime}$ $\in$ $\\{0,1\\}^{n}$, we
have

$\displaystyle\mathbb{P}\Bigg{(}G(\mathbf{x})=G(\mathbf{x}^{\prime})\Bigg{)}\leq\frac{1}{2^{n\beta_{1}}}$
(36)

Now,

$\displaystyle\mathbb{P}$
$\displaystyle\Bigg{(}\exists\mathbf{x}\neq\mathbf{x}^{\prime}\in\mathcal{A}:G(\mathbf{x})=G(\mathbf{x}^{\prime})\Bigg{)}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}{|\mathcal{A}|\choose{2}}\mathbb{P}\left(G(\mathbf{x})=G(\mathbf{x}^{\prime})\right)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}{{2^{n\eta}}\choose{2}}2^{-n\beta_{2}}$
$\displaystyle\stackrel{{\scriptstyle}}{{<}}2^{2n\eta}2^{-n\beta_{1}}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}2^{-n\beta^{\prime}}$ (37)

where $(a)$ follows from the definition of $\mathcal{A}$, and using the union
bound (on distinct pairs of vectors in $\mathcal{A}$); we get $(b)$ from the
definition of $\mathcal{G}$. Further, $(c)$ follows from the fact that
$\beta_{1}$ is chosen such that $\beta^{\prime}:=\beta_{1}-2\eta>0$. This
completes the proof of the claim.

###  -D Proof of Lemma 6

Using the Claim 2 and Claim 3, we establish a lower bound on the following
smooth-min-entropy:

$\displaystyle H_{\infty}^{\epsilon_{1}}$
$\displaystyle(\mathbf{X}|\mathbf{Y},\mathbf{Z},G,G(\mathbf{X}))$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}H_{\infty}(\mathbf{X},G(\mathbf{X}),|\mathbf{Y},\mathbf{Z},G)$
$\displaystyle\hskip 28.45274pt-
H_{0}(G(\mathbf{X})|\mathbf{Y},\mathbf{Z},G)-\log(\epsilon_{1}^{-1})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\geq}}H_{\infty}(\mathbf{X}|\mathbf{Y},\mathbf{Z},G)+H_{\infty}(G(\mathbf{X})|\mathbf{Y},\mathbf{Z},G,\mathbf{X})$
$\displaystyle\hskip 28.45274pt-
H_{0}(G(\mathbf{X})|\mathbf{Y},\mathbf{Z},G)-\log(\epsilon_{1}^{-1})$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\geq}}H_{\infty}(\mathbf{X}|\mathbf{Y},\mathbf{Z},G)$
$\displaystyle\hskip 28.45274pt-
H_{0}(G(\mathbf{X})|\mathbf{Y},G)-\log(\epsilon_{1}^{-1})$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{=}}H_{\infty}(\mathbf{X}|\mathbf{Y},\mathbf{Z})-H_{0}(G(\mathbf{X})|\mathbf{Y},\mathbf{Z},G)-\log(\epsilon_{1}^{-1})$
$\displaystyle\stackrel{{\scriptstyle(e)}}{{\geq}}(H(\mathbf{X}|\mathbf{Y},\mathbf{Z})-\zeta_{1})-H_{0}(G(\mathbf{X})|\mathbf{Y},\mathbf{Z},G)-\log(\epsilon_{1}^{-1})$
$\displaystyle\stackrel{{\scriptstyle(f)}}{{\geq}}{n(H(p)+H(q)-H(p\circledast
q)-\zeta_{1})}-n\beta_{1}-\log(\epsilon_{1}^{-1})$
$\displaystyle\stackrel{{\scriptstyle}}{{=}}{n(H(p)+H(q)-H(p\circledast
q)-\zeta_{1}-\beta_{1})}-\log(\epsilon_{1}^{-1})$ (38)

where we have

  1. (a)

from the chain rule for smooth min-entropy; see Claim 2 and substitute
$\mu=\epsilon_{1}$, $\mu_{1}=0$ and $\mu_{2}=0$ in Eq. (32).

  2. (b)

from the chain rule for min-entropy; see Claim 2 and and substitute $\mu=0$
and $\mu^{\prime}=0$ in Eq. (31).

  3. (c)

from the fact that $G(\mathbf{X})$ is a deterministic function of $G$ and
$\mathbf{X}$.

  4. (d)

by the Markov chain $\mathbf{X}-(\mathbf{Y},\mathbf{Z})-G$.

  5. (e)

from [32, Th. 1] which allows us to lower bound
$H_{\infty}(\mathbf{X}|\mathbf{Y},\mathbf{Z})$ in terms of
$H(\mathbf{X}|\mathbf{Y},\mathbf{Z})$.

  6. (f)

by noting that $H(\mathbf{X}|\mathbf{Y},\mathbf{Z})=H(p)+H(q)-H(p\circledast
q)$, and from definition of max-entropy (also noting that the range of $G$ is
$\\{0,1\\}^{n\beta_{1}}$).