main.tex

\documentclass[fullpage]{article}

	\addtolength{\oddsidemargin}{-.875in}
	\addtolength{\evensidemargin}{-.875in}
	\addtolength{\textwidth}{1.75in}

	\addtolength{\topmargin}{-.875in}
	\addtolength{\textheight}{1.75in}


\usepackage[utf8]{inputenc}
\usepackage[english]{babel}
\usepackage{amsthm}
\usepackage{placeins}

\makeatletter
\def\th@plain{%
  \thm@notefont{}% same as heading font
  \itshape % body font
}
\def\th@definition{%
  \thm@notefont{}% same as heading font
  \normalfont % body font
}
\makeatother

\usepackage{hyperref}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{mdframed}
\usepackage{extarrows}
\usepackage{caption}
\usepackage{xspace}
\usepackage{graphicx}
\usepackage{fixltx2e}
\usepackage[n,advantage,operators,sets,adversary,landau,probability,notions,logic,ff, mm, primitives,events,complexity,asymptotics,keys]{cryptocode}
\captionsetup[figure]{labelfont={bf},name={Fig.},labelsep=period}

\newtheorem{claim}{Claim}[section]
\newtheorem{conjecture}{Conjecture}[section]
\newtheorem{lemma}{Lemma}[section]
\newtheorem{theorem}{Theorem}[section]
\theoremstyle{definition}
\newtheorem{definition}{Definition}[section]
\newtheorem{remark}{Remark}

\def\SPSB#1#2{\rlap{\textsuperscript{#1}}\SB{#2}}
\def\SP#1{\textsuperscript{#1}}
\def\SB#1{\textsubscript{#1}}

\newcommand{\EUFCMA}{\textsf{EUF-CMA}\xspace}
\newcommand{\EUFCMAVES}{\textsf{EUF-CMA}[\textsf{VES}]\xspace}
\newcommand{\EUFCMAVESot}{\textsf{EUF-CMA}[\textsf{VES}\textsubscript{ot}]\xspace}
\newcommand\getsdollar{\mathrel{{\leftarrow}\vcenter{\hbox{\tiny\rmfamily\upshape\$}}}}
\newcommand{\SE}{SE}
\newcommand{\otVES}{\textsf{VES}\textsubscript{ot}}
\newcommand{\OPCHECKMULTISIG}{\texttt{OP\_CHECKMULTISIG}\xspace}
\newcommand{\Dec}{\textsf{Dec}}


\newcommand{\Enc}{\textsf{Enc}}
\newcommand{\EncGen}{\textsf{EncGen}}
\newcommand{\EncSign}{\textsf{EncSign}}
\newcommand{\EncVer}{\textsf{EncVrfy}}

\newcommand{\DecSig}{\textsf{DecSig}}
\newcommand{\KeyGen}{\textsf{Gen}}
\newcommand{\Sign}{\textsf{Sign}}
\newcommand{\Verify}{\textsf{Vrfy}}
\newcommand{\Rec}{\textsf{Rec}}
\newcommand{\RecKey}{\textsf{RecKey}}
\newcommand{\rec}{\delta}
\newcommand{\VESALG}{\EncGen, \EncSign, \EncVer, \DecSig}
\newcommand{\SIGNALG}{\KeyGen, \Sign, \Verify}
\newcommand{\ENCALG}{\EncGen, \Enc, \Dec}

\newcommand{\skSign}{sk_S}

\newcommand{\pkSign}{pk_S}
\newcommand{\kSign}{(\skSign,\pkSign)}
\newcommand{\skEnc}{sk_E}
\newcommand{\pkEnc}{pk_E}
\newcommand{\kEnc}{(\skEnc, \pkEnc)}
\newcommand{\F}{\mathcal{F}}
\newcommand{\hatsigma}{\hat{\sigma}}
\newcommand{\hatSigma}{\hat{\Sigma}}
\newcommand{\FullEncVer}{\EncVer(\pkSign, \pkEnc, m, \hatsigma)}
\newcommand{\FullVer}{\Verify(\pkSign,m,\sigma)}
\newcommand{\R}{\mathcal{R}}
\newcommand{\RDL}{\mathcal{R}_{\DLOG}}
\newcommand{\hatR}{\hat{\mathcal{R}}}
\newcommand{\hardproblem}{\mathcal{H}}
\newcommand{\G}{\mathbb{G}}
\newcommand{\DLOG}{\textsf{DL}\xspace}
\newcommand{\Setup}{\textsf{Setup}}


\begin{document}

\title{One-Time Verifiably Encrypted Signatures \\ A.K.A. Adaptor Signatures}
\author{Lloyd Fournier\footnote{\texttt{lloyd.fourn@gmail.com}}}
\date{October 2019}

\maketitle

\begin{abstract}
  On Bitcoin-like ledgers, smart contract functionality can be realised without using the ledger's native smart contract language through the ``adaptor signature'' technique\cite{poelstra-adaptor}. An adaptor signature is a kind of partial signature that, if completed, will reveal valuable information to the signer. In this work, we conduct the first formal analysis of the adaptor signature as an isolated primitive. We find that it offers similar functionality to the already well established concept of \emph{verifiably encrypted signatures} (VES) with one notable difference: the decryption key can be recovered from the ciphertext and the decrypted signature. To capture this property, we formally introduce the notion of \emph{one-time verifiably encrypted signatures}. To properly define their security in the Bitcoin layer-2 setting we revisit the original VES definitions and modify them to remove the ingrained assumption of a trusted third party.

  After the extending our VES definitions to the one-time VES, we attempt to prove that the existing Schnorr and ECDSA adaptor signature schemes satisfy them. In the case of Schnorr, we succeed unconditionally but our definitions expose a (non-fatal) flaw in the ECDSA scheme. Nevertheless, we show how to use the ECDSA scheme to realise functionality in Bitcoin that was previously thought to be out of reach without Schnorr signatures or complex two-party ECDSA protocols.
\end{abstract}

\section{Introduction}

In 2017, Andrew Poelstra posted a message to the Mimblewimble mailing list\cite{poelstra-bitcoin-dev-scriptless} demonstrating an interesting feature of the Schnorr signature scheme. He showed that through a small tweak to the signing algorithm the core lock construction of the lightning payment channel network\cite{poon2016bitcoin} could be realised without using Bitcoin's \emph{smart contract} language called \emph{script}. This was a remarkable discovery as the existing proposal relied heavily on enforcing the lock logic using script based hash locks. His explanation ended with ``I'm very excited about this'' and in retrospect his excitement seems justified. This breakthrough has been used to create ``scriptless'' variants of most Bitcoin layer-2\footnote{In this work we will use layer-2 to refer to any protocol that requires a direct communication channel between participants not just "off-chain" payment channel type protocols} protocols (we give a fairly comprehensive list in Section~\ref{exisitng-protocols}).

\textbf{Scriptless scripts.} Achieving smart contract logic without script has been termed \emph{scriptless scripts} within the Bitcoin research community. It is a significant challenge to the usual conception of smart contracts. Instead of being expressed in a programming language, a smart contract becomes a kind of multi-party computation that outputs transaction signatures according to the desired contract logic. In other words, if according to a contract Alice is meant to receive funds when event X occurs, instead of expressing event X in some way using the smart contract language, the contract is set up such that Alice is only able to compute a signature on a transaction that claims the funds due to her when event X occurs. This is clearly beneficial to Alice because no passive observer of the blockchain can tell that the transaction depended on event X, rather it (optimistically) looks just like a normal payment transaction.

\textbf{Verifiably Encrypted Signatures.} In this work we frame the adaptor signature, the key building block of scriptless protocols, as a kind of signature encryption. In particular, we find it almost fits the definition of \emph{verifiably encrypted signatures}\cite{Boneh:2003:AVE:1766171.1766207} (VES) introduced for the BLS signature scheme\cite{Boneh:2001:SSW:647097.717005}. A VES scheme enables a signer to produce an encrypted signature whose validity can be verified non-interactively. The adaptor signature is a VES where the encryption is \emph{one-time} in a similar sense to a one-time pad: the decryption key can easily be recovered from the ciphertext and its plaintext (the signature).

\textbf{Fair Exchange of Signatures Without a Trusted Party}. This ``one-time'' property may seem like a bug, but in many settings it is actually a powerful feature. Consider the motivating example for the original VES scheme\cite{Boneh:2003:AVE:1766171.1766207}: two parties, Alice and Bob, wish to fairly exchange signatures with the assistance of a trusted third party named the \emph{adjudicator}. First, Alice sends to Bob her signature encrypted under the adjudicator's public key. Bob verifies the validity of the signature encryption and then sends his signature to Alice. If Alice refuses to reciprocate, Bob may ask the adjudicator to intervene by decrypting the encryption of Alice's signature he already has. If we assume the adjudicator is able to correctly assess the situation (i.e.\ will not be tricked by a malicious Bob) then this a secure optimistic fair signature exchange protocol.

With a one-time VES we can achieve the fair exchange of signatures \emph{without} a trusted party under the assumption that the signatures need to be published publicly to be useful. The one-time property gives the Bitcoin layer-2 protocol designer leverage over malicious parties by forcing them to leak a secret key when they publish a decrypted signature. This leaked key can then be used by honest parties to carry on the protocol and claim the funds due to them. A simple one-time VES fair signature exchange protocol can be described as follows: Alice generates her signature encryption under a public encryption key she herself generates and sends the key and the ciphertext to Bob. Bob responds by generating a signature encrypted under the same key. Alice decrypts this signature and publishes it. Due to the one-time property of the VES, Bob is able to recover the Alice's decryption key and decrypt the signature from the ciphertext given to him by Alice.

% Perhaps note that this fair exchange is possible by using script

\subsection{Survey of Scriptless Protocols}
\label{exisitng-protocols}

In order to motivate our formalisation, we first review how one-time VES schemes (i.e.\ adaptor signatures) are used in existing scriptless layer-2 protocol proposals. We give a simplified explanation of each protocol below focusing on the role the VES plays in the construction. Interestingly not every proposal requires the VES to have the one-time property; the ``Discreet Log Contracts'' and lottery protocols only need an ordinary VES\@. In practice, each protocol requires a VES scheme with a two-party encrypted signing algorithm but we leave this out to simplify the description (Section~\ref{semi-scriptless} focuses on this point). In general, each scriptless protocol is more efficient in terms of transaction footprint and more confidential than its script based counterpart.

\hfill \break \textbf{Atomic swaps.}  In an atomic swap, two parties, Alice and Bob, exchange the ownership of two assets, $A$ and $B$, on two different ledgers, $\alpha$ and $\beta$. As initially conceived\cite{atomic-swap}, Alice generates a random secret $y$ and shares the hash of it $Y \gets H(y)$ with Bob. Alice then locks $A$ in a smart contract on $\alpha$ that will only release $A$ if the Bob activates it with $y'$ such that $Y = H(y')$. Bob locks $B$ into a similar contract on $\beta$. Alice then claims $B$, by activating the contract on $\beta$ with $y$. Bob then learns $y$ and claims $A$ with it on $\alpha$.

The scriptless atomic swap protocol\cite{scriptless-atomic-swap} is the classic example of how to apply adaptor signatures to create a practically identical structure without requiring smart contract based hash operations. Rather than a hash pre-image, Alice generates an encryption key-pair $(y,Y)$. On $\alpha$ Alice gives Bob a one-time VES under $Y$ on a transaction giving Bob $A$ should he be able to decrypt it. Bob then sends Alice a one-time VES under $Y$ on a transaction giving Alice $B$. Alice decrypts he signature with $y$ and broadcasts it claiming $B$. Bob then sees the decrypted signature, and due to the one-time property of the VES, he is able to extract $y$ from it and decrypts his own signature to claim $A$. Note that unlike the hash based protocol, the secret $y$ is never placed into any transaction on either ledger making it much harder to link the transactions on $\alpha$ and $\beta$ with each other.

\hfill \break \textbf{Payment channels.} Poelstra's original mailing list post applies the same transformation used in the scriptless atomic swap to the Lightning Network\cite{poon2016bitcoin}. Payment channels gain an additional benefit from having a group element (the encryption key) as the lock, rather than a hash. Using the homomorphic properties of the group, the lock can be randomised at each hop making it difficult to link a payments traveling through the network just based on them having the same lock. This was formalised in \cite{cryptoeprint:2018:472}. Informal discussions on the lightning network development mailing list also suggest other benefits of using group elements, rather than hashes as the lock\cite{lightning-dev-scriptless-scripts}.

\hfill \break \textbf{Discreet Log Contracts.} In layer-2 protocols, ``oracles'' are parties who are trusted to cryptographically attest to the outcome of real world events. In his work, ``Discreet Log Contracts''\cite{dryja2017discreet}, Dryja proposes a model where rather than interacting with smart contracts directly, oracles publicly reveal secret information (usually a signature) depending on the outcome of the real world event. Two parties who wish to engage in a bet can construct a set of jointly signed transactions where only one of them becomes valid determined by the signature the oracle reveals. Importantly, the oracle remains oblivious to the existence of the bet.

The protocol in the original work required three on-chain transactions to settle a bet. We observe that by using a one-time VES we can construct a more efficient two transaction protocol. The oracle announces it will reveal the decryption key corresponding to public encryption key $A$ or $B$ depending on the outcome of some event. Alice and Bob wish to bet 1 BTC on outcomes $A$ and $B$ respectively with even odds. To securely set up this contract, they both pay their 1 BTC into a single joint 2 BTC output and Alice gives a VES on a transaction paying Bob the 2 BTC encrypted by $B$ and Bob gives a VES on a transaction paying Alice the 2 BTC encrypted by $A$. When the oracle releases the decryption key for one of $A$ or $B$, the winner can decrypt their transaction signature and claim the 2 BTC with 1 BTC profit. Note that this protocol does not require the VES to be one-time.

\hfill \break \textbf{Tumblers.}  Inspired by Chaumian eCash\cite{chaum1983blind}, the first tumbler protocol, TumbleBit\cite{tumblebit} enabled Bitcoin payments through an untrusted intermediary called the \emph{tumbler} to be mixed so it is hard (even for the tumbler) to link the incoming and outgoing payments. TumbleBit requires script in the un-cooperative case to verify that the tumbler correctly releases blinded RSA decryptions.

Tairi et al.\ recently proposed a more efficient scriptless tumbler called A$^2$L\cite{cryptoeprint:2019:589}. The tumbler first locks coins up and gives a VES on a transaction releasing the coins to the \emph{receiver} encrypted under $A = g^{\alpha_i}$. The tumbler also gives the sender a homomorphic encryption of the decryption key $\alpha_i$. The \emph{sender} then attempts to pay the tumbler for $\alpha_i$ without letting the tumbler know which $\alpha$ she paid for (the tumbler is presumed to be executing many such protocols at once each with a different $\alpha$). The sender purchases $\alpha_i$ by giving the tumbler a one-time VES on a payment transaction encrypted under a blinded version of the encryption key e.g. $g^{\alpha_i + \beta}$ where the sender knows $\beta$. When the tumbler takes the payment $\alpha_i + \beta$ is revealed to the sender allowing them to decrypt receiver's signature.

In addition, a scriptless tumbler protocol based on blind Schnorr signatures is proposed in \cite{blind-tumbler}.

\hfill \break  \textbf{Lotteries.} The possibility of Bitcoin lotteries without a trusted party\cite{bitcoin_talk} was one of the first ideas academic Bitcoin researchers formally explored\cite{bentov_how_to_use_bitcoin}\cite{andrychowicz_lottery}. In its simplest form two parties both bet 1 Bitcoin and at the end of the protocol, the randomly chosen winner has 2 Bitcoin and the loser has 0. Most proposals, including more recent ones\cite{bartoletti_lottery}\cite{DBLP:journals/corr/MillerB16} are based on hash commitment coin tossing to produce the random outcome. The protocols use script to check the commitment openings on-chain.

A scriptless lottery was recently proposed\cite{fournier_lottery} which uses the \emph{oblivious signatures} from \cite{1-of-n-oblivious-signatures} rather than hash commitment coin tossing. The oblivious signature scheme is essentially built on a VES: The receiver first sends a Pedersen commitment $T = g^xh^c$ where $c \in \bin$, to the signer. The singer then sends a VES for each of $m_0$ and $m_1$ encrypted under $T$ and $Th^{-1}$ respectively. Due to the binding property of the commitment, the receiver only knows the decryption key $x$ for the signature on $m_c$ but the sender never learns $c$. The proposed protocol uses the adaptor signature style one-time VES but in principle the idea works with any VES as long as there is an algorithm that allows the receiver to verifiably produce a set of public keys for which it only knows one of the private keys (without anyone else knowing which one).

\hfill \break  \textbf{Pay for commitment opening.} A script based smart contract to pay for an opening hash commitment is straightforward to construct. A scriptless alternative for paying for the opening of a Pedersen commitment has been proposed in \cite{pay-for-pedersen}.

\subsection{Our Contribution}

In Section~\ref{VES-section}, we contribute to theory of verifiably encrypted signatures in general. The original security definitions\cite{Boneh:2003:AVE:1766171.1766207} only required the scheme to be secure if the encryption key-pair was chosen by the trusted adjudicator. VES schemes secure by these definitions are generally inappropriate for use in layer-2 protocols where a  trusted party is rarely assumed. We propose new security definitions without reference to trusted parties and show that all existing schemes satisfy our new definitions.

In Section~\ref{otVES} we formally introduce one-time verifiably encrypted signatures. We then frame the existing Schnorr and ECDSA ``adaptor signature'' schemes as one-time VES schemes. We prove the Schnorr scheme secure but find that the ECDSA one-time VES unintentionally leaks a Diffie-Hellman tuple for the signing key and the encryption key. We incorporate this weakness and prove that this is at least the only problem with the scheme.

Finally in Section~\ref{semi-scriptless} we introduce the practical ``semi-scriptless'' paradigm where protocols can only have scripts with a single \texttt{OP\_CHECKMULTISIG} script opcode. We show how to generically transform any scriptless protocol into a semi-scriptless protocol using the ECDSA one-time VES\@. This allows any scriptless protocol to be practically realised on Bitcoin as it is today without a complex two-party ECDSA multi-signature scheme.

\subsection{Previous Work with Adaptor Signatures In Security Proofs}

As far as we are aware, this work is the first attempt to formalise the adaptor signature as a primitive on its own. However, the works of \cite{cryptoeprint:2018:472} and \cite{cryptoeprint:2019:589} use the idea of the adaptor signature and formally argue their security in the \emph{Universal Composability} (UC) model\cite{UC}. Their UC simulation ensures that corrupted parties may learn nothing but the signature itself from any adaptor signatures they receive. In general, the UC simulation is achieved through efficient \emph{non-interactive zero knowledge proofs of knowledge} for discrete logarithms. This allows the simulator in the ideal world to extract the secret keys of the corrupted party and use them to synthetically create adaptor signatures to simulate the view of the adversary in the real world.

In our work, we use a weaker game-based model of security. This ensure that the corrupted party learns nothing \emph{useful}, rather than nothing at all, from a signature encryption other than the signature itself. In particular, we will define security for VES and one-time VES schemes such that an adversary cannot learn anything from a signature encryption that will help them forge a signature on another message. We believe this is a viable approach in general, but it is especially reasonable in the context of Bitcoin style ledgers. In layer-2 Bitcoin protocols, the keys that own coins are not re-used between protocol executions so it is easy to ensure that a key is only used in the particular ways our game-based definitions can ensure is secure.

\subsection{Future Work}

\textbf{Multi-party VES.} All proposed scriptless protocols require signature encryptions generated through a two-party encrypted signing protocol. The security of Schnorr two-party one-time VES protocols deserves attention since it is being put forward as the main primitive for the protocols listed in Section~\ref{exisitng-protocols} above in the long-term. We limit ourselves to focusing on defining formal security for single singer VES schemes and leave this analysis for future work.

\hfill \break \textbf{Schnorr vs BLS.} This work suggests a significant trade-off between the choice of Schnorr and BLS as the main signature scheme for Bitcoin-like systems. BLS admits an efficient VES scheme\cite{Boneh:2003:AVE:1766171.1766207} and extremely attractive non-interactive signature aggregation \cite{compact-blockchains-bls}. On the other hand, Schnorr admits a less elegant interactive multi-signature scheme\cite{musig} but a very efficient one-time VES scheme. Additionally, it should be possible to create a Schnorr (not one-time) VES scheme with general zero-knowledge proof techniques where as a one-time VES for BLS looks much less likely. This trade off deserves further exploration including  the possibility of a signature scheme that admits both an efficient VES and one-time VES scheme.

\section{Preliminaries}

\subsection{Bitcoin}
We assume a fair amount of familiarity with the Bitcoin transaction structure in Section~\ref{semi-scriptless}. A Bitcoin transaction has the following elements:
\begin{itemize}
    \item A set of inputs, each of which refer to a previous output.
    \item For each input, a witness that satisfies the spending constraints specified in the output it references.
    \item For each input, a \emph{relative} time-lock which prevents the transaction from being included in the ledger until enough time has passed since the output it references was included in the ledger.
    \item A set of new outputs, each with a value and spending constraint.
    \item An \emph{absolute} time-lock, which prevents the transaction from being included in the ledger until a specific time.
\end{itemize}
Whenever a transaction is included in the ledger, its outputs are considered ``spent'' and their value is transferred to the new outputs created by the transaction (and a small fee to the miner who included them).

When we refer to a ``layer-2'' protocol we mean any protocol that is composed of messages sent between the participants and transactions sent to the ledger. A scriptless protocol means any protocol where the transactions only use a basic public key spending constraint which can only be satisfied by a signature on the spending transaction under that public key. It's important to note that a scriptless protocol can still use the time-lock constraints (and most do).

\subsection{Notation}
We analyse security asymptotically with our security parameter as $k$. We assume that the algorithms for each scheme have been generated by some $\textsf{Setup}(1^k)$ algorithm which generates the a concrete instance of the scheme according to $k$. By $\negl[k]$ we denote any negligible function of $k$ i.e.  $\negl[k] < 1/p(k)$  for all positive polynomials $p(k)$ and all sufficiently large values of $k$. We say a probability is ``negligible'' if it can be expressed as $\negl[k]$ or overwhelming if it can be expressed as $1 - \negl[k]$.  A polynomial time adversary runs in time that can be upper bounded by some polynomial of $k$. A \emph{probabilistic} algorithm is also implicitly given a long string of random bits in addition to its other arguments. We denote invoking a probabilistic algorithm with $\sample$. If an algorithm is probabilistic and polynomial time we say it is a \emph{PPT} algorithm.

\subsection{The Discrete Logarithm Problem}

The concrete signature schemes we deal with (Schnorr and ECDSA) are based on the discrete logarithm problem (\DLOG). Written multiplicatively, the \DLOG problem is to find $x \in \ZZ_q$ given $(X,g)$ such that $g^x = X$, in a group $\G$ of prime order by $q$. We denote the fixed generator of a $\DLOG$ based scheme by $g$. In reality $(\G,q,g)$ are fixed by the ledger i.e.\ the Secp256k1 elliptic curve group for Bitcoin, but we reason about them as if the they were generated by the $\textsf{Setup}(1^k)$ algorithm relative to $k$. Note that when we describe schemes based on the \DLOG problem, all scalar operations are implicitly done modulo $q$.


% CDH problem?

% VERIFIABLY ENCRYPTED SIGNATURES
\section{Verifiably Encrypted Signatures Without a Trusted Third Party}
\label{VES-section}

Verifiably encrypted signatures (VES) were introduced by Boneh, Gentry, Lynn and Shacham (BGLS) \cite{Boneh:2003:AVE:1766171.1766207} in 2003 for the BLS signature scheme\cite{Boneh:2001:SSW:647097.717005}. A VES scheme lets a signer create a signature encryption that can be non-interactively verified. Just by knowing the message and public signing key, a verifier can tell that a ciphertext contains a valid signature encrypted by a particular encryption key. This separates it from the earlier notion of \emph{signcryption}\cite{signcryption-book} where the message is also encrypted and the verification is often interactive.

This idea is somewhat unintuitive. If I can verify that the signer has indeed signed the message then what's the point of decrypting the ciphertext? A VES is only useful in settings where the signature itself is what has value rather than the fact that someone has signed it. In layer-2 protocols we have exactly this situation. Having a verifiably encrypted transaction signature is not enough to make the transaction valid --- it must first be decrypted and attached to the transaction. Skipping ahead a bit, with our new definitions we do not even require that a valid encrypted signature was created by the signer for it to be a secure VES scheme.

The original definitions of BGLS were made relative to a trusted third party, the \emph{adjudicator}. The original idea was that two parties could optimistically exchange signatures, by first exchanging verifiably encrypted signatures, then should one of them fail to provide their signature, the other could go to the adjudicator to have it decrypted. This is not appropriate for our setting. In most of the protocols described in Section~\ref{exisitng-protocols}, one of the possibly malicious parties generates the encryption key-pair. We take our first step towards a trusted party free definition by removing references to the ``adjudicator'' from the definition of VES:

\newcommand{\rightsample}{\hskip2.3pt{\mbox{\tiny${\$}$\normalsize}}\!\!\rightarrow\,}


\begin{definition}[Verifiably Encrypted Signature Scheme]
\label{VES}
 A verifiably encrypted signature scheme (VES) $\hatSigma$ is defined with an ordinary \emph{underlying} signature scheme $\Sigma := (\SIGNALG)$ and four additional algorithms:
    \begin{itemize}
        \item $\EncGen \rightsample \kEnc$: A probabilistic encryption key generation algorithm which outputs an encryption key $\pkEnc$ and a decryption key $\skEnc$. There should also exist an efficient predicate $\textsf{valid}\kEnc$ that returns 1 when $\kEnc$ is a valid key-pair.
        \item $\EncSign(\skSign, \pkEnc, m) \rightsample \hatsigma$: A possibly probabilistic encrypted signing algorithm, which on input of a secret signing key $\skSign$, a public encryption key $\pkEnc$ and a message $m$ outputs a ciphertext $\hatsigma$.
        \item $\EncVer(\pkSign, \pkEnc, m, \hatsigma) \rightarrow \bin$: A deterministic encrypted signature verification algorithm which on input of a public signing key $\pkSign$, a public encryption key $\pkEnc$, a message $m$ and a ciphertext $\hatsigma$ outputs 1 only if $\hatsigma$ is a valid encryption of a signature on $m$ for $\pkSign$ under $\pkEnc$.
        \item $\DecSig(\skEnc, \hatsigma) \rightarrow \sigma$: A (usually) deterministic signature decryption algorithm which on input of a decryption key $\skEnc$ and a valid ciphertext $\hatsigma$ under that encryption key  outputs a valid signature $\sigma$.
    \end{itemize}

Any coherent VES should satisfy a basic notion of completeness such that for all messages $m$, valid encryption and signing key pairs $\kEnc$ and $\kSign$ and for all coin tosses of $\EncSign$ the following always holds:
    \[ \hatsigma = \EncSign(\skSign, \pkEnc, m) \implies \EncVer(\pkSign, \pkEnc, m, \hatsigma) = 1 \land \Verify(\pkSign, m, \DecSig(\skEnc, \hatsigma)) = 1 \]
\end{definition}

The original work BGLS proposed three security properties: \emph{validity}, \emph{unforgeability}, and \emph{opacity}. To meet the requirements of our setting, we will restate validity without reference to a trusted party and replace unforgeability with a new \emph{existential unforgeability under chosen message attack} (\EUFCMAVES) property. We keep the original definition of opacity. Therefore our VES requirements are informally as follows:

\begin{itemize}
    \item \textbf{Validity:} It is infeasible to generate a valid looking ciphertext that does not yield a valid signature upon decryption.
    \item \EUFCMAVES: A VES ciphertext does not help an adversary forge signatures. In other words, an adversary cannot learn anything useful from a VES ciphertext other than the signature that is encrypted.
    \item \textbf{Opacity:} The encrypted signature cannot be extracted from the ciphertext without the decryption key.
\end{itemize}


We formally present our new definitions for validity and introduce \EUFCMAVES after summarizing previous work on improving VES definitions. We do not formally describe opacity as the original definitions are not applicable the one-time VES (see Section~\ref{otVES}).

\subsection{Previous Revisions of the VES Security Definitions}

Rückert et al.\ \cite{Ruckert:2009:SVE:1615384.1615387} noticed that \emph{key independent} schemes (which we call Sign then Encrypt (StE)) whose underlying signature schemes are \EUFCMA secure can be proved unforgeable generically. This is remarkable as the original BGLS scheme, which is StE, had AN involved proof for unforgeability that spanned several pages. We use a similar idea to prove any StE scheme satisfies \EUFCMAVES\@. Hanser et al.\ \cite{VES-structure-preserving} also identified the importance of the \EUFCMA security of the underlying signature scheme. They proved that the underlying signature scheme is unforgeable if the VES scheme is unforgeable based on a different property.

Calderon et al.\ \cite{calderon2014rethinking} discuss the original definitions in detail. They show a pathological VES scheme which is secure according to the original definitions but can be constructed only using a signature scheme i.e.\ without any encryption. They introduce two additional properties to address this. Our definitions allow for the same pathological constructions as we see no reason to prevent them in our setting.

Shao \cite{SHAO20081961} addresses the assumption of trust in the adjudicator by providing a stronger definition of unforgeability which prevents forging a VES even if the adjudicator is corrupted. Unfortunately, the original and highly practical VES scheme of BGLS does not meet this stronger requirement. Our approach to removing trust in a third party is to simply replace the concept of unforgeability with \EUFCMAVES\@. The ability of malicious parties to forge signature encryptions is not a concern in our setting as long as they cannot forge signatures (which is already ensured by the \EUFCMA security of the signature scheme).

\subsection{Validity}

Validity protects against an adversary who attempts to create a valid looking ciphertext that when decrypted will not yield a valid signature. The original BGLS definition of validity was inadequate as it only guaranteed a valid signature upon decryption if the ciphertext was generated by the $\EncSign$ algorithm. Rückert et al. \cite{Ruckert:2009:SVE:1615384.1615387} noticed this problem and introduced the additional property of \emph{extractability} which ensured the adversary could not find a malicious ciphertext against the trusted adjudicator's encryption key.

This definition of extractability is not appropriate for our setting as we have no trusted party. In layer-2 protocols, the encryption key and the signing key may be generated by the same malicious party. For example, imagine an adversary who maliciously generates a VES ciphertext on some transaction signature and attempts to sell the decryption key to someone who wishes to know the signature. If they are successful they can get paid for the decryption key but even after obtaining the decryption key the buyer will be unable to get their desired signature. Thus in our setting the adversary must be free to choose the signing and encryption keys. We choose to use the original name of validity to capture this idea as it ensures that the validity of a ciphertext carries through to the validity of the encrypted signature.

\begin{definition}[Validity]
 A VES scheme is valid if, for all PPT algorithms $\adv$, the $\textsf{VES-Validity}$ experiment outputs 1 except with negligible probability over coin tosses of $\adv$ and $\Setup$:

\begin{center}
    \fbox{%
          \procedure{$\textsf{VES-Validity}^{\adv}_{\Setup}$}{%
          \hatSigma \sample \Setup(1^k) \\
          (\pkSign,(\skEnc, \pkEnc),m, \hatsigma ) \sample \adv(\hatSigma) \\
          \sigma \gets \hatSigma.\DecSig(\skEnc, \hatsigma) \\
          \pcreturn \hatSigma.\pcalgostyle{valid}(\skEnc, \pkEnc) \implies \hatSigma.\EncVer(\pkSign, \pkEnc, m, \hatsigma) = \hatSigma.\Verify(\pkSign, m, \sigma)
    }
    }

\end{center}
\end{definition}
\subsection{\EUFCMAVES}

Our goal in this section is to formally capture the requirement that from a VES ciphertext nothing can be learned except the signature encrypted within. We start with the typical \EUFCMA security definition for signature schemes which ensures that from a signature, nothing can be learned about a signature on any other message under the same signing key. The experiment tests this by giving the forger a signature oracle $S$ from which it can query signatures under the signing key on messages of its choosing. For a secure scheme, no algorithm should exist that is able to forge signatures even with access to $S$. By implication, the forger learns nothing useful from the signatures other than the signatures themselves.

To show that a ciphertext equally offers no extra information to the forger, we modify the experiment so the forger also has access to a signature encryption oracle $E$. The forger is allowed to query this oracle under any encryption key and message it wants. This allows, for example, the forger to request a ciphertext where the encryption key is the signing key they are trying to forge against in the hope that will leak something about the signing key. We call denote this modified experiment \EUFCMAVES and define it as follows.

\begin{definition}[\EUFCMAVES]
 A VES scheme $\hatSigma$ is \emph{existentially unforgeable under a chosen message attack} (\EUFCMAVES) if its underlying \EUFCMA signature scheme remains unforgeable in a modified experiment where in addition to the signature oracle $S$ the forger has access to a signature encryption oracle $E$.
\begin{center}
\fbox{
    \procedure{$\EUFCMAVES^{\F}_{\hat{\Sigma}}$}{
        Q := \emptyset \\
        (\skSign,\pkSign) \sample \KeyGen \\
        (m^*, \sigma) \sample \F^{E,S}(\pkSign) \\
        \pcreturn \Verify(\pkSign, m^*, \sigma) \land m^* \notin Q \\
    }
    \pchspace
    \procedure{Oracle $E(\pkEnc, m)$}{
        Q := Q \cup \{m\}\\
        \pcreturn \EncSign(\skSign,\pkEnc,m) \\
    }
    \pchspace
    \procedure{Oracle $S(m)$}{
        Q := Q \cup \{m\} \\
        \pcreturn \Sign(\skSign, m) \\
    }
}
\end{center}
\end{definition}

\EUFCMAVES effectively replaces the original definition of \emph{unforgeability} so we now discuss and prove the relationship between the two. The original unforgeability property referred to signature encryptions being unforgeable under the trusted adjudicator's encryption key. \EUFCMAVES says nothing about the unforgeability of signature encryptions. In fact, an adversary who can produce valid VES ciphertexts without the secret signing key is perfectly compatible. Of course, they will never be able to forge a VES ciphertext under a particular encryption key. If they could do that, then they could trivially forge an encrypted signature under a key for which they know the decryption key and decrypt it. The original definitions seem to have missed this intuition: it is not the security of the VES scheme that prevents there being a successful forger of signature encryptions under a particular key, the \EUFCMA security of the underlying signature scheme already ensures that no such algorithm can exist. After recalling the original BGLS definition of unforgeability, we use this intuition to prove that any \EUFCMAVES scheme is also unforgeable.

\begin{definition}[VES Unforgeability \cite{Boneh:2003:AVE:1766171.1766207}]
\label{original-unforgeability}

A VES scheme $\hatSigma$ is unforgeable if for every PPT algorithm $\F$, with access to an encryption oracle $\tilde{E}$ and a decryption oracle $\tilde{D}$ the $\textsf{VES-Forge}$ experiment outputs 1 with at most negligible probability over the coin tosses of $\EncGen$, $\KeyGen$, $\EncSign$ and $\F$.

 \begin{center}
 \fbox{
 \begin{pchstack}
       \procedure{$\textsf{VES-Forge}^{\F}_{\hatSigma}$}{
        Q \gets \emptyset \\
        \kSign \sample \KeyGen \\
        \kEnc \sample \EncGen \\
        (m^*, \hatsigma^*) \sample \F^{\tilde{E},\tilde{D}}(\pkSign,\pkEnc) \\
        \pcreturn \EncVer(\pkSign, \pkEnc, m^*, \hatsigma^*) \land m^* \notin Q \\
     }
     \pchspace
     \procedure{Oracle $\tilde{E}(m)$}{
        Q := Q \cup \{m\} \\
        \hatsigma \sample \EncSign(\skSign,\pkEnc,m) \\
        \pcreturn \hatsigma
     }
     \pchspace
     \procedure{Oracle $\tilde{D}(\hatsigma)$}{
        \EncVer(\pkSign, \pkEnc, \hatsigma) \stackrel{?}{=} 1 \\
        \pcreturn \DecSig(\skEnc,\hatsigma) \\
     }
 \end{pchstack}
 }
 \end{center}
Note that the oracles in $\textsf{VES-Forge}$ only provide encryptions and decryption on a particular key, representing the trusted adjudicator's key-pair.

\end{definition}

\begin{theorem}[\EUFCMAVES $\implies$ Unforgeability]
If a VES scheme is \EUFCMAVES secure and has the \emph{validity} property then it also has the original BGLS unforgeability property of Definition~\ref{original-unforgeability}.
\end{theorem}

\begin{proof}
Let $\hatSigma$ be a VES scheme and let $\F$ be PPT a forger with non-negligible advantage $\epsilon$ in forging signature encryptions in the original $\textsf{VES-Forge}^{\F}_{\hatSigma}$ experiment. We can construct a reduction $\R$ with non-negligible advantage $\epsilon'$ in forging signatures in the $\EUFCMAVES^{\R}_{\hatSigma}$ experiment just given black-box access to $\F$ as follows.

\begin{center}
\fbox{
\begin{pchstack}
\procedure{$\R^{S, E}_{\EUFCMAVES}(\pkSign)$}{%
    (\skEnc, \pkEnc) \sample \EncGen \\
    (m^*, \hatsigma^*) \sample \F^{\tilde{E},\tilde{D}}_{\textsf{VES-Forge}}(\pkSign, \pkEnc) \\
    \sigma^* \gets \DecSig(\skEnc, \hatsigma^*) \\
    \pcreturn (m^*, \sigma^*) \\
}
\pchspace
\procedure{Simulate $\tilde{E}(m)$}{
    \pcreturn E(\pkEnc,m) \\
}
\pchspace
\procedure{Simulate $\tilde{D}(\hatsigma)$}{
    \EncVer(\pkSign, \pkEnc, \hatsigma) \stackrel{?}{=} 1 \\
    \pcreturn \DecSig(\skEnc, \hatsigma)
}
\end{pchstack}
}
\end{center}
Clearly $\R$ perfectly simulates $\tilde{E}$ and $\tilde{D}$ and runs in polynomial time.
Denote $\FullEncVer$ by $EV$, $\FullVer$ by $V$ and start with the following inequality:
\[  \prob{V} \geq \prob{V \mid EV }\prob{EV}  \]
Since validity ensures that $\prob{V \mid EV} = 1 - \negl[k]$, we have
\[ \prob{V} \geq (1 - \negl[k])\prob{EV} = \prob{EV} - \negl[k] \]
By definition, $\epsilon = \prob{EV}$  and $\epsilon' = \prob{V}$
\[ \epsilon' \geq  \epsilon - \negl[k] \]
Which shows $\epsilon'$ is non-negligible if $\epsilon$ is non-negligible, completing the proof.
\end{proof}

As we have already argued, \EUFCMAVES captures our requirement that the scheme be secure without reference to a trusted party. We now propose using \EUFCMAVES as the standard VES security definition even in the trusted party setting since it implies BGLS unforgeability and it is much easier to prove for the schemes that have been developed so far. We can prove all existing schemes we are aware of \cite{Boneh:2003:AVE:1766171.1766207, Ruckert:2009:SVE:1615384.1615387, waters-ves, SHAO20081961, VES-structure-preserving} \EUFCMAVES secure just by the \emph{Sign then Encrypt} (StE) structure they all share. That is, internally the $\EncSign$ algorithm first generates a normal signature using $\Sign$ and then encrypts the result. Formally:

\begin{definition}[Sign then Encrypt VES]
A \emph{Sign then Encrypt} (StE) VES scheme is defined with an ordinary \emph{underlying} signature scheme $\Sigma := (\SIGNALG)$ an \emph{associated} public key encryption scheme $\Pi = (\ENCALG)$ and a VES verification algorithm $\EncVer$ such that if we define $\DecSig := \Dec$ and $\EncSign(\skSign, \pkEnc, m) := \Enc(\pkEnc, \Sign(\pkSign, m))$ then $\hatSigma := (\EncGen, \EncSign, \EncVer, \DecSig)$ is a VES scheme according to Definition~\ref{VES}.
\end{definition}

It is easy to see that any valid StE scheme must be \EUFCMAVES secure. The extra encryption oracle $E$ the forger has access to in the \EUFCMAVES experiment can be simulated just by encrypting the result of a query to the signature oracle $S$ that the \EUFCMA experiment provides.

\begin{theorem}[StE $\implies$ \EUFCMAVES]
Let $\hatSigma$ be a StE VES scheme,  $\Sigma$ be its underlying signature scheme and $\Pi = (\ENCALG)$ be its associated public key encryption scheme.
If there is reduction $\R$ from some hard problem $\hardproblem$ to the \EUFCMA security of $\Sigma$, then there is a reduction $\hatR$ from $\hardproblem$ to the \EUFCMAVES security of $\hatSigma$.
\end{theorem}

\begin{proof}
The only difference between the \EUFCMA and \EUFCMAVES experiments is that the forger is provided an extra signature encryption oracle $E$. Since $\hatSigma$ is StE, we can easily construct $\hatR$ by having it run $\R$ and forwarding queries to $E$ to the signing oracle $S$ of $\R$ and encrypting the result. Specifically, when $\hatR$ receives an $E$ oracle query $(m, \pkEnc)$ it makes a query $(m)$ to $S$ and receives $\sigma$. It then sets $\hatsigma \gets \Enc(\pkEnc, m)$ and returns $\hatsigma$ to the forger. This does not interfere with $\R$ at all so $\hatR$ is also a reduction from $\hardproblem$.
\end{proof}

\section{One-Time Verifiably Encrypted Signatures}
\label{otVES}
We introduce the \emph{one-time verifiably encrypted signature scheme} to abstract the functionality of the ``adaptor signature''\cite{poelstra-adaptor}. A one-time VES is a VES with an additional property: given the ciphertext and the decrypted signature, the decryption key is easily recoverable.
Obviously, this property makes it useless for the optimistic fair exchange of signatures with a trusted party envisioned for ordinary VES schemes, as the trusted adjudicator would leak their decryption key after its first use.
Despite this, the property turns out to be incredibly useful to layer-2 protocol designers as it allows them to force the release of a secret key whenever a party broadcasts a decrypted transaction signature.
We define by extending the original VES definition:

\begin{definition}[One-Time Verifiably Encrypted Signatures]
A One-Time Verifiably Encrypted Signature scheme (one-time VES) is a Verifiably Encrypted Signature scheme (\SIGNALG, \VESALG) with the following additional algorithms:
\begin{itemize}
    \item $\RecKey(\pkEnc, \hatsigma) \rightarrow \delta$: A deterministic recovery key extraction algorithm which extracts a recovery key $\delta$ from the ciphertext $\hatsigma$ and the public encryption key $\pkEnc$.
    \item $\Rec(\sigma,\rec) \rightarrow \skEnc$: A deterministic decryption key recovery algorithm which when given a decrypted signature $\sigma$ and the recovery key $\rec$ associated with the original ciphertext, returns the secret decryption key $\skEnc$.
\end{itemize}

\end{definition}

Technically, $\Rec$ takes a ``recovery key'' $\delta$ rather than the ciphertext $\hatsigma$ but they should usually be thought of as equivalent. The distinction only really becomes necessary in Section~\ref{semi-scriptless} when we construct a simple two party encrypted signing protocol where one party is not able to output the whole ciphertext but is able to output the recovery key.

To be considered secure, we require a one-time VES scheme to have the \emph{completeness}, \emph{validity} and \EUFCMAVES properties of an ordinary VES along with \emph{recoverability} which we define as follows.

\begin{definition}[Recoverability]

 A one-time VES scheme is recoverable if for all PPT algorithms $\adv$ the $\textsf{VES-Recover}$ experiment outputs 1 except with negligible probability over the coin tosses of $\adv$ and $\Setup$:

\begin{center}
    \fbox{%
          \procedure{$\textsf{VES-Recover}^{\adv}_{\Setup}$}{%
            \hatSigma \sample \Setup(1^k) \\
            (\pkSign,(\skEnc, \pkEnc), m,\hatsigma ) \sample \adv(\hatSigma) \\
            \delta \gets \hatSigma.\RecKey(\pkEnc, \hatsigma); \sigma \gets \hatSigma.\DecSig(\skEnc, \hatsigma) \\
            \pcreturn(\hatSigma.\textsf{valid}(\skEnc, \pkEnc) \land \hatSigma.\FullEncVer \land \hatSigma.\FullVer) \implies \hatSigma.\Rec(\sigma, \delta) = \skEnc
        }
    }

 \end{center}

\end{definition}

Note that we no longer have need of the \emph{opacity} property as defined for an ordinary VES scheme. Recall that the informal purpose of opacity is to ensure that an encrypted signature cannot be accessed without the decryption key. Recoverability makes this is trivial because if you are able to access the signature you can recover the decryption key anyway. In other words, obtaining a signature from a ciphertext without the decryption key is no easier than obtaining the decryption key just given the public encryption key (which is hopefully hard). Crucially, this also means that even the signer themselves cannot produce the signature from the ciphertext without the decryption key. This necessarily implies that one-time VES schemes only exist for probabilistic signature schemes where there is an exponential number of possible signatures under a public key for any message.

\subsection{Schnorr One-Time VES Scheme}
What we call the Schnorr one-time VES was introduced by Poelstra \cite{poelstra2017scriptless} which he termed an ``adaptor signature''\cite{poelstra-adaptor} with the encryption key being termed an ``auxiliary point''\cite{blind-tumbler} or sometimes just ``$T$''. A major benefit of our one-time VES concept is to be able to explain this useful idea with intuitive encryption/decryption semantics. It is typically described with a two-party signing protocol as this is where it is most useful. We describe the single singer scheme in Figure~\ref{fig:schnorr-ves} including its underlying Schnorr signature scheme. The Schnorr signature scheme was introduced by its namesake in \cite{Schnorr:1989:EIS:646754.705037} and our description resembles the key-prefixed scheme described in the Schnorr Bitcoin Improvement Proposal\cite{bip-schnorr} currently under consideration.

\begin{figure}[h]

    \centering
    \begin{mdframed}
    \begin{pchstack}[center]
    \procedure{$\KeyGen/\EncGen$}{
        x \sample \ZZ_q; X \gets g^{x} \\
        sk := (x,X); pk := X \\
        \pcreturn (sk,pk)
    }
    \pchspace
    \procedure{$\Sign(\skSign, m)$}{
        (x,X) := \skSign; \\
        r \sample \ZZ_q; R \gets g^r \\
        c := H(R || X || m) \\
        s \gets r + cx \\
        \pcreturn \sigma := (R,s) \\
    }

    \procedure{$\Verify(\pkSign,m,\sigma)$}{
        X := \pkSign; (R,s) := \sigma \\
        c := H(R || X || m) \\
        \pcreturn R = g^{s}X^{-c}
    }
    \pchspace
    \procedure{$\EncSign(\skSign,\pkEnc, m)$}{%
        (x,X) := \skSign; Y := \pkEnc  \\
        r \sample \ZZ_q; \hat{R} \gets{} g^r \\
        R \gets \hat{R}Y \\
         c := H(R || X || m) \\
        \hat{s} \gets r + cx \\
         \pcreturn \hat{\sigma} := (\hat{R},\hat{s}) \\
    }
    \end{pchstack}
    \begin{pchstack}[center]
    \procedure{$\EncVer(\pkSign,\pkEnc, m, \hatsigma)$}{%
        X := \pkSign; Y := \pkEnc \\
        (\hat{R},\hat{s}) := \hatsigma \\
        R \gets \hat{R}Y \\
        c := H(R || X || m) \\
        \pcreturn \hat{R} = g^{\hat{s}}X^{-c} \\
    }
    \pchspace
    \procedure{$\DecSig(\skEnc,\hatsigma)$}{
        (\hat{R},\hat{s}) := \hatsigma \\
        (y, Y) := \skEnc \\
        R \gets \hat{R}Y \\
        s \gets \hat{s} + y \\
        \pcreturn \sigma := (R,s)
    }
    \pchspace
    \procedure{$\RecKey(\pkEnc, \hatsigma)$}{
        (\hat{R},\hat{s}) := \hatsigma \\
        \pcreturn \rec := \hat{s} \\
    }
    \pchspace
    \procedure{$\Rec(\sigma, \rec)$}{
        (R,s) := \sigma \\
        \hat{s} := \rec \\
        y \gets  s - \hat{s} \\
        \pcreturn y
    }
    \end{pchstack}
    \end{mdframed}
    \caption{The algorithms of the Schnorr one-time VES scheme with a hash algorithm $H$}
    \label{fig:schnorr-ves}
\end{figure}

Since the $\EncSign$ algorithm is a simple tweak of the sign algorithm it is easy to get an intuition for the security of the scheme. Unsurprisingly, we find that the scheme is unconditionally valid and recoverable and is \EUFCMAVES secure. We now formally prove these properties.

\begin{lemma}
The Schnorr one-time VES is unconditionally valid and recoverable.
\end{lemma}

\begin{proof}
 Since $\EncVer(X,Y,m,(\hat{R},\hat{s})) = 1$ implies $ \hat{R} = g^{\hat{s}}X^{-c}$ where $c := H(\hat{R}Y || X || m)$, by the one-way homomorphism between $\ZZ_q$ and $\G$ we know that $\hatsigma$ encrypts some valid signature $(R,s) := (\hat{R}Y, \hat{s} + y)$ where $g^y = Y$ and is therefore valid because:
\[ \hat{R}Y = Yg^{\hat{s}}X^{-c} = g^{\hat{s} + y}X^{-c} \]
By the same token, the scheme is recoverable because $\Rec((\hat{R}Y, \hat{s} + y)), \hat{s})$ always returns the decryption key $y = s - \hat{s}$.
\end{proof}


\begin{theorem}
The Schnorr one-time VES is \EUFCMAVES secure.
\end{theorem}

\begin{proof}
  We transform the standard Schnorr reduction from the \DLOG problem to the \EUFCMA security of Schnorr signatures in the random oracle model by Pointcheval and Stern\cite{pointcheval2000security} into a \EUFCMAVES reduction by simulating the additional signature encryption oracle $E$.
  Note the original reduction was not did not key-prefixed but the same reduction can be applied to key-prefixed Schnorr. Our reduction $\RDL$ simulates $E$ by programming the random oracle $H$ in a similar way to how it usually simulates the signing oracle $S$ as shown below:

\begin{center}
  \fbox{%
%     \begin{pchstack}[center]
        \procedure{$\RDL(X)$}{
           \pccomment{Run the reduction from \cite{pointcheval2000security}} \\
           \text{...} \gets \F^{E,S}_{\EUFCMAVES}(X) \\
        }
        \pchspace
        \procedure{Simulate $S(m)$}{
            s,c \sample \ZZ_q \\
            R \gets g^sX^{-c} \\
            \pcif H(R || X || m) = \bot \pcthen \\
             \t H(R || X || m) := c \\
             \t \pcreturn (R,s) \\
            \pcelse \textbf{abort} \\
        }
        \pchspace
        \procedure{Simulate $E(\pkEnc, m)$}{
             Y := \pkEnc \\
             \hat{s},c \sample \ZZ_q \\
             \hat{R} \gets g^{\hat{s}}X^{-c}; R \gets \hat{R}Y \\
             \pcif H(R || X || m) = \bot \pcthen \\
             \t H(R || X || m) := c \\
             \t \pcreturn (\hat{R},\hat{s}) \\
             \pcelse \textbf{abort} \\
        }
%    \end{pchstack}
    }
  \end{center}

The fact that we can efficiently simulate $E$ without changing the internals of $\RDL$ completes the proof.
\end{proof}

\subsection{ECDSA One-Time VES Scheme}
\label{ecdsa-ot-ves-section}

\newcommand{\Pdleq}{\pcalgostyle{P}_{\textsf{DLEQ}}}
\newcommand{\Vdleq}{\pcalgostyle{V}_{\textsf{DLEQ}}}

In order circumvent the need for Schnorr signatures, which are not included in the Bitcoin protocol today, Moreno-Sanchez et al.\  developed an adaptor signature construction for the standard ECDSA signature scheme already used in Bitcoin\cite{ecdsa-scriptless-scripts}. It was later applied to achieve a payment channel construction with better privacy in \cite{cryptoeprint:2018:472} and an efficient tumbler in \cite{cryptoeprint:2019:589}. The scheme is built upon the two-party ECDSA protocol from \cite{Lindell2pECDSA}. We translate it into a single signer scheme in Figure~\ref{fig:ecdsa-adaptor}.

As the protocol is single signer it avoids all the complexities that come with two-party ECDSA protocols. It only requires requires a simple non-interactive zero knowledge proof of discrete logarithm equality, whose proving and verification algorithms we denote as $(\Pdleq,\Vdleq)$. When invoked as $\Pdleq((g, A),(h,B),w)$, it generates a proof of membership of the language:

\newcommand{\DLEQ}{\textsf{DLEQ}\xspace}
\[ L_{\DLEQ} = \{ (g, h, A, B) \in \G^4 \mid  \exists w \in \ZZ_q : A = g^w \land B = h^w \} \]

We instantiate this proof with the Fiat-Shamir transform applied to the Sigma protocol for the relation originally from \cite{dleq-proof}.

\newcommand{\Rx}{R_\texttt{x}}
\newcommand{\hatRx}{\hat{R}_\texttt{x}}
\newcommand{\xcoord}{f}

\begin{figure}[h]
    \centering
    \begin{mdframed}
    \begin{pchstack}[center]
    \procedure{$\KeyGen/\EncGen$}{
        x \sample \ZZ_q; X \gets g^{x} \\
        sk := (x,X); pk := X \\
        \pcreturn (sk,pk)
    }
    \pchspace

    \procedure{$\Sign(\skSign, m)$}{
        (x,X) := \skSign; \\
        r \sample \ZZ_q; R \gets g^r \\
        \Rx \gets \xcoord(R) \\
        s \gets r^{-1}(H(m) + \Rx{}x)\\
        \pcreturn \sigma := (\Rx,s) \\
    }

    \procedure{$\Verify(\pkSign,m,\sigma)$}{
        X := \pkSign; (\Rx,s) := \sigma \\
        R' \gets (g^{H(m)}X^{\Rx})^{s^{-1}} \\
        \pcreturn \xcoord(R') = \Rx \\
    }
    \pchspace
    \procedure{$\EncSign(\skSign,\pkEnc, m)$}{%
        (x,X) := \skSign; Y := \pkEnc  \\
        r \sample \ZZ_q; \hat{R} \gets{} g^r; R \gets Y^{r} \\
        \pi \sample \pcalgostyle{P}_{\DLEQ}((g, \hat{R}), (Y, R),r) \\
        \Rx \gets \xcoord(R) \\
        \hat{s} \gets r^{-1}(H(m) + \Rx{}x)\\
        \pcreturn \hat{\sigma} := (R, \hat{R},\hat{s}, \pi) \\
    }
    \end{pchstack}
    \begin{pchstack}[center]

    \procedure{$\EncVer(\pkSign,\pkEnc, m, \hatsigma)$}{%
        X := \pkSign;  Y := \pkEnc \\
        (R, \hat{R},\hat{s}, \pi) := \hatsigma \\
        \pcalgostyle{V}_{\DLEQ}((g, \hat{R}), (Y, R)), \pi) \stackrel{?}{=} 1\\
        \Rx \gets \xcoord(R) \\
        \pcreturn \hat{R} = (g^{H(m)}X^{\Rx})^{\hat{s}^{-1}} \\
    }
    \pchspace
    \procedure{$\DecSig(\skEnc,\hatsigma)$}{
        (R, \hat{R},\hat{s}, \pi) := \hatsigma \\
        (y, Y) := \skEnc \\
        s \gets \hat{s}y^{-1} \\
        \pcreturn \sigma := (\xcoord(R),s)
    }
    \pchspace
    \procedure{$\RecKey(\pkEnc, \hatsigma)$}{
        (R, \hat{R},\hat{s}, \pi) := \hatsigma \\
        Y := \pkEnc \\
        \pcreturn \rec := (Y, \hat{s})
    }
    \pchspace
    \procedure{$\Rec(\sigma, \rec)$}{
        (\Rx,s) := \sigma; (Y, \hat{s}) := \rec \\
        \tilde{y} \gets  s^{-1}\hat{s} \\
        y := \left\{\begin{array}{l}
                \tilde{y}  \hspace{1em} \pcif g^{\tilde{y}} = Y \pclb
                -\tilde{y} \hspace{0.33em} \pcif g^{\tilde{y}} = Y^{-1} \pclb
                \bot \hspace{1em} \textbf{otherwise}
                \end{array}
             \right. \\
        \pcreturn y
    }
    \end{pchstack}
    \end{mdframed}
    \caption{The algorithms of the ECDSA one-time VES scheme. $f: \G \rightarrow \ZZ_q$ converts a an elliptic curve point to its x-coordinate mod $q$.}
    \label{fig:ecdsa-adaptor}
\end{figure}

We now attempt to prove the scheme secure.

\begin{lemma}
The ECDSA one-time VES is valid and unconditionally recoverable.
\end{lemma}
\begin{proof}
If $\EncVer(X,Y,m,(R, \hat{R},\hat{s}, \pi)) = 1$ then $\hat{R} = (g^{H(m)}X^{\Rx})^{\hat{s}^{-1}}$ and $\hat{R}^{y} = R$ if $\pi$ is sound. Which means $\hat{R}^{y} = R = (g^{H(m)}X^{\Rx})^{\hat{s}^{-1}y}$. Therefore $\DecSig$ produces a valid signature $\sigma := (R, \hat{s}y^{-1})$ whenever $\hatsigma$ is valid except with the negligible probability that $\pi$ is unsound. If $\sigma$ is valid then $\Rec$ will always recover $\tilde{y} \gets s^{-1}\hat{s} = (\hat{s}y^{-1})^{-1}\hat{s}$, which is either equal to $y$ or $-y$ (due to $\Verify$ only checking the x-coordinate of $R$).
\end{proof}

Unfortunately, while trying to prove the scheme \EUFCMAVES secure we found a problem: the ciphertext surreptitiously leaks the Diffie-Hellman key for the signing and encryption key. $Y^x = X^y$ can be computed as $(R^{\hat{s}}Y^{-H(m)})^{\Rx^{-1}}$. This clearly violates the premise of \EUFCMAVES which is that nothing useful should be learned from the ciphertext, other than the signature (if it can be decrypted). Furthermore, it is not difficult to imagine a composability attack where an adversary, with an ElGamal encryption $(g^r, X^rm)$ of some message $m \in \G$ is able to decrypt it by requesting a signature encryption under $g^r$ from the signer, learning $X^r$ and thereby illegally learning $m$. We discuss the impact of this further after proving that the scheme cannot be \EUFCMAVES secure.

\begin{lemma}
\label{ecdsa-ves-not-secure}
There exists no \emph{key-preserving} \EUFCMAVES reduction for the ECDSA one-time VES scheme if the Computational Diffie-Hellman Problem (CDH) is hard.
\end{lemma}

\newcommand{\ECDSAVES}{\hatSigma_{\text{ECDSA}}}
\newcommand{\CDH}{\textsf{CDH}}
\newcommand{\Sim}{\mathcal{S}}

\begin{proof}

  Let $\CDH(X,Y)$ for $(X,Y) \sample \G^2$ denote an instance of the CDH problem with respect to the generator $g$ of the ECDSA one-time VES\@. We will prove our statement by solving $\CDH(X,Y)$ with only black-box access to a simulator $\Sim$ for the encryption oracle $E$ that must be provided to the forger in a key-preserving \EUFCMAVES reduction. This contradicts the existence of $\Sim$ and therefore no key-preserving \EUFCMAVES reduction scheme can exist if the CDH problem is hard. To solve $\CDH(X,Y)$ we run the simulator for $\Sim$ with $X$ as the signing key and then query it with an arbitrary message $m$: $(R, \hat{R}, \hat{s}, \pi) \sample \Sim(m,Y)$.

   First, note that $(\hat{R},Y,R)$ must be a valid Diffie-Hellman tuple if $\Sim$ properly simulates the an encrypted signing oracle. Even though $\Sim$ can simulate DLEQ proofs (by their zero knowledge property) for invalid tuples, this is not enough to simulate the view of a real forger. Regardless of validity of $\pi$, a forger can make a query to $E(Y',m')$ with an encryption key-pair it has generated itself $(y',Y')$ and check that $\hat{R}^{y'} = R$ in the response. If the check fails with non-negligible probability then $\Sim$ can be distinguished from the real oracle $E$ in the \EUFCMAVES experiment.

   Given $(\hat{R},Y,R)$ is a valid Diffie-Hellman tuple and $\hat{s} = r^{-1}(H(m) + \Rx{}x)$,  $R = Y^r$ and $X = g^x$ are true since $(R, \hat{R}, \hat{s}, \pi)$ must be a valid signature encryption, we can compute $\CDH(X,Y)$ as $(R^{\hat{s}}Y^{-H(m)})^{\Rx^{-1}}$ since:

\begin{align*}
    R^{\hat{s}} & = Y^{H(m) + \Rx{}x} &  \\
    R^{\hat{s}}Y^{-H(m)} & =  Y^{\Rx{}x} \\
    (R^{\hat{s}}Y^{-H(m)})^{\Rx^{-1}} & = Y^{x}
\end{align*}
\end{proof}

The fact that this scheme leaks a Diffie-Hellman key does not necessarily mean it is useless. None of the schemes presented in Section~\ref{exisitng-protocols} rely on the CDH problem being hard. Furthermore, on a Bitcoin like ledger, signing keys for transactions are usually generated randomly within the protocol and are not shared between executions, so learning a CDH tuple in one execution cannot help an adversary break the security of another. Thus, as long as the protocol designer does not rely on the CDH problem being hard within their protocol the ECDSA one-time VES is practically secure.

It remains to be shown that a CDH solution is the only extra information the adversary learns from the ciphertext. To prove this we make the CDH problem easy by giving the reduction access to a CDH oracle and show the scheme secure under this condition. We choose the \EUFCMA reduction to the \DLOG problem for ECDSA by Fersch et al.\cite{ecdsa-eufcma} in the \emph{bijective random oracle model} as our starting point. In this model, the conversation function $f$ which converts an elliptic curve point $R$ to its x-coordinate $\Rx$ is modelled as a bijective random oracle and signatures are simulated by programming it. We prove the following theorem in Appendix~\ref{proof-ecdsa-eufcma}.

\begin{theorem}
\label{claim-ecdsa-eufcma}
The reduction from the discrete logarithm problem to the EUFCMA security of ECDSA in the bijective random oracle model from \cite{ecdsa-eufcma} can be transformed into a $\EUFCMAVES$ reduction for the ECDSA one-time VES if the CDH problem is easy.
\end{theorem}

\section{Semi-Scriptless Protocols}
\label{semi-scriptless}

\newcommand{\TxFund}{\texttt{Tx}_{\textsf{fund}}}
\newcommand{\TxRefund}{\texttt{Tx}_{\textsf{refund}}}
\newcommand{\TxRedeem}{\texttt{Tx}_{\textsf{redeem}}}
\newcommand{\TxInput}{\texttt{Tx}_{\textsf{input}}}
\newcommand{\addrRedeem}{addr_{B}}
\newcommand{\addrRefund}{addr_{A}}
\newcommand{\TxGen}{\textsf{Tx}}
\newcommand{\refundSig}{\sigma_{\textsf{refund}}}
\newcommand{\redeemSig}{\sigma_{\textsf{redeem}}}
\newcommand{\redeemEncSig}{\hatsigma_{\textsf{redeem}}}

The essential function of a smart contract on a Bitcoin-like ledger is to lock coins in an output such that they can only be spent to certain parties under certain conditions. With a smart contract language like Bitcoin script, the conditions can be expressed in the language and enforced by the ledger's transaction validation rules. In the scriptless model, we can only constrain spending through time-locks and by setting a public key, for which the spender must provide a signature. Clearly in order to stop one party from arbitrarily spending the coins the corresponding private key cannot be exclusively known to one party. Thus we require the parties have a joint ownership of the public key and cooperatively use a multi-signature protocol to sign transactions spending from the joint output. Multi-signature protocols exist for ECDSA\cite{Lindell2pECDSA,hash-proof-ecdsa}, Schnorr\cite{musig}, BLS\cite{compact-blockchains-bls} and most prominent signature schemes.

To realise most of the scriptless protocols from Section~\ref{exisitng-protocols}, the multi-signature scheme also needs to admit a two-party one-time VES encrypted signing protocol to emulate $\EncSign$ on a joint signing key. It is relatively simple to build this on top of a Schnorr multi-signature scheme, but since Schnorr signatures have not been included in the Bitcoin protocol yet, this tool is out of reach for now. Both the two-party ECDSA schemes in \cite{Lindell2pECDSA,hash-proof-ecdsa} admit a two-party $\EncSign$ protocol as described in \cite{ecdsa-scriptless-scripts}. Unfortunately, these schemes are complex and rely additional exotic computational hardness assumptions. As a result, the consensus that came out of the 2018 Lightning Developer Summit was to postpone updating the lightning specification to include ``payment points'' until Schnorr becomes viable.\cite{zmn-2pecdsa}

We present a workaround that allows protocol designers to realise many of the benefits of scriptless protocols in Bitcoin as it is today. To do so, we relax the scriptless model slightly to what we call the ``semi-scriptless'' model where protocols are allowed to use a single $\OPCHECKMULTISIG$ script opcode but no others. $\OPCHECKMULTISIG$ acts as a naive ECDSA multi-signature scheme, where the public key for the scheme is the concatenation of each party's public keys and a valid signature is the concatenation of valid signatures under each public key. When locking coins with \OPCHECKMULTISIG, a set of public keys is specified along with how many of those keys must authorize any transaction spending from it. We will only use ``2-of-2'' outputs which require two signatures on two out of two of the specified public keys.

\begin{figure}[h]
    \centering
    \begin{mdframed}
    \begin{pchstack}[center]
    \procedure{$\textsf{2p-Sign}(pk := (pk_1,pk_2), m)$}{
     \textbf{P}_1(sk_1) \< \< \textbf{P}_2(sk_2) \\
     \sigma_1 \sample \Sign(sk_1,m) \< \< \\
     \< \sendmessageright*[0.4cm]{\sigma_1} \< \\
     \< \< \Verify(pk_1,m,\sigma_1) \stackrel{?}{=} 1 \\
     \< \< \sigma_2 \sample \Sign(sk_2, m) \\
     \< \< \pcreturn \sigma := (\sigma_1,\sigma_2) \\
    }
    % \end{pchstack}
    % \begin{pchstack}[center]
    \procedure{$\textsf{2p-EncSign}(pk := (pk_1, pk_2),pk_E,m)$}{%
        \textbf{P}_1(sk_1) \< \< \textbf{P}_2(sk_2) \\
        \hatsigma_1 \sample \EncSign(sk_1,pk_E,m) \< \< \\
        \rec \gets \RecKey(pk_E, \hatsigma_1) \< \< \\
        \< \sendmessageright*[0.4cm]{\hatsigma_1} \< \\
        \< \< \EncVer(pk_1,pk_E,m,\hatsigma_1) \stackrel{?}{=} 1 \\
        \< \< \sigma_2 \sample \Sign(sk_2, m) \\
        \< \< \hatsigma := (\hatsigma_1, \sigma_2) \\
        \pcreturn \rec  \< \< \pcreturn \hatsigma
    }
    \end{pchstack}
    \end{mdframed}
    \caption{The two-party signing and encrypted signing algorithms for an 2-of-2 \OPCHECKMULTISIG output.}
    \label{opcms-2p-ves}
\end{figure}

We can transform any existing scriptless protocol into a semi-scriptless protocol by locking funds to an \OPCHECKMULTISIG 2-of-2 on two distinct public keys and using the single signer ECDSA one-time VES from Section~\ref{ecdsa-ot-ves-section}. The simple two-party signing and encrypted signing protocols are presented in Figure~\ref{opcms-2p-ves}.

The downsides of semi-scriptless protocols are readily apparent. First, the transactions are larger because they require two public keys and two signatures to spend them (in addition the overhead that comes from using script). Secondly, it is easy to distinguish \OPCHECKMULTISIG outputs from a regular payment transactions (but not from other uses of \OPCHECKMULTISIG 2-of-2).

Having said this, semi-scriptless protocols are a practical alternative to two-party ECDSA to developers who wish to attempt to realise many of the benefits of scriptless protocols prior to the Schnorr upgrade. In general, semi-scriptless enjoy better confidentiality than their script based counterparts. Although script is used, \OPCHECKMULTISIG is not particular to any protocol making it at more confidential than protocols with a unique script structure. For the following protocols we note the following particular benefits:

\begin{itemize}
    \item \textbf{Payment Channels \cite{poon2016bitcoin}:} The typical hash lock can be replaced with a discrete logarithm based lock which enables the privacy benefits from \cite{cryptoeprint:2018:472} other conjectured improvements\cite{lightning-dev-scriptless-scripts}.
    \item \textbf{Atomic swaps \cite{scriptless-atomic-swap}:} The secret that releases funds from the escrow transactions never appears on the ledger, unlike the existing hash constructions which make it easy to associate assets changing hands as the contracts on the ledgers share the same hash.
    \item \textbf{Discreet Log Contracts \cite{dryja2017discreet}:} The protocol can be completed in two transactions rather than three.
\end{itemize}

\FloatBarrier
\bibliography{bib.bib}{}
\bibliographystyle{unsrt}

\appendix
\section{ Proof for Theorem \ref{claim-ecdsa-eufcma}}

\newcommand{\Ocdh}{\mathcal{O}_{\CDH}}
\newcommand{\betarange}{\mathbb{B}}
\newcommand{\Sdleq}{\pcalgostyle{S}_{\DLEQ}}

\emph{authors note: This proof is wrong. By giving the reduction access to the
  $\Ocdh$ oracle we implicitly make the discrete logarithm problem
  easy\cite{Kushwaha16} making the reduction from the discrete logarithm
  pointless. I am in the process of fixing the proof so that it no longer
  requires such a powerful oracle and can be reduced from the discrete logarithm
  problem with a static Diffie-Hellman oracle. Technically, this is slightly easier than the
  usual discrete logarithm problem but still secure in practice.\cite{SDHP}}

\label{proof-ecdsa-eufcma}
As we have proved, the ECDSA one-time VES is not \EUFCMAVES secure if the CDH problem is hard. We now wish to show that if the CDH problem were easy then it would satisfy \EUFCMAVES i.e.\ leak no useful information to a forger. Thus we give our reduction access to an $\Ocdh$ oracle which when queried with $\Ocdh(X,Y)$ returns $Z$ such that (X,Y,Z) is a Diffie-Hellman tuple with respect to $g$. Additionally, in the reduction we simulate the NIZK $\DLEQ$ proof $\pi$ with $\Sdleq$.

As our starting point, we take the \EUFCMA reduction for ECDSA by Fersch et al.\cite{ecdsa-eufcma} to the discrete logarithm problem. In this work, the conversion function $f:\G \rightarrow \ZZ_q$ that maps a group element to its x-coordinate mod $q$ is decomposed and idealised as an oracle. The forger must query this oracle to produce a valid forgery. During the reduction, this oracle is programmable. In more detail, $f$ is decomposed as $f = \psi \circ \Pi \circ \varphi$ where:

\begin{enumerate}
    \item $\varphi$ is an invertible 2-to-1 function mapping curve points to the domain of $\Pi$ reflecting the fact that every x-coordinate belongs to two possible group elements.
    \item $\Pi$ is the bijective random oracle that the reduction is able to program.
    \item $\psi$ is an invertible function that maps the range of $\Pi$ (denoted as $\betarange$)  to $\ZZ_q$.
\end{enumerate}

We sketch the simulation of the signature encryption oracle $E$ in this model below. Note that we leave out and simplify some important details for the sake of clarity and encourage the reader to review the original proof in \cite{ecdsa-eufcma} to get a full understanding of the reduction.


\begin{center}
    \fbox{
        \begin{pchstack}
         \procedure{$\RDL(X)$}{
            Q \gets \emptyset; \Pi \gets \emptyset  \\
            \pccomment{Run the reduction from \cite{ecdsa-eufcma}} \\
            \text{...} \gets \F^{E,S}_{\EUFCMAVES}(X) \\
        }
        \procedure{Simulate $S(m)$}{
            \beta \sample \betarange \\
            \pcif (\cdot, \beta) \in \Pi: \textbf{abort} \\
            \Rx{} \gets \psi(\beta) \\
            s \sample \ZZ_q \\
            R \gets (g^{H(m)}X^{\Rx})^{s^{-1}} \\
            \alpha \gets \varphi(R) \\
            \pcif (\alpha,\cdot) \in \Pi: \textbf{abort} \\
            \Pi \gets \Pi \cup \{ (\alpha, \beta) \} \\
            Q \gets Q \cup \{m\} \\
            \pcreturn (s, \Rx)
        }
        \pchspace
        \procedure{Simulate $E(Y, m)$}{
            \beta \sample \betarange \\
            \pcif (\cdot, \beta) \in \Pi: \textbf{abort} \\
            \Rx{} \gets \psi(\beta) \\
            \hat{s} \sample \ZZ_q \\
            \hat{R} \gets (g^{H(m)}X^{\Rx})^{\hat{s}^{-1}} \\
            R \gets \Ocdh(\hat{R}, Y) \\
            \pi \gets \Sdleq((g, \hat{R}),(Y,R)) \\
            \alpha \gets \varphi(R) \\
            \pcif (\alpha,\cdot) \in \Pi: \textbf{abort} \\
            \Pi \gets \Pi \cup \{ (\alpha, \beta) \} \\
            Q \gets Q \cup \{m\} \\
            \pcreturn (R, \hat{R}, \hat{s}, \pi) \\
        }
        \end{pchstack}
    }
\end{center}

The fact that we can simulate $E$ with access to $\Ocdh$ without modifying the internals of $\RDL$ completes the proof.

% \section{Semi-Scriptless Time-Lock Protocol}

% \begin{figure}[h]
%     \centering
%     \begin{mdframed}
%     \begin{center}
%         \pseudocode{%
%         \\
%         \textbf{Alice}(Y, \addrRefund, \TxInput) \< \< \textbf{Bob}(Y,\addrRedeem) \\[0.1 \baselineskip][\hline]
%         \< \< \\[0.5\baselineskip]
%         (sk_A,pk_A) \sample \KeyGen \< \< \\
%         \< \sendmessageright*{pk_A, \TxInput, \addrRefund} \< \\
%         \< \<  (sk_B,pk_B) \sample \KeyGen \\
%         \< \< script := \texttt{OP\_CMS-2of2}(pk_A,pk_B) \\
%         \< \< \TxFund \gets \TxGen(\TxInput, script) \\
%         \< \< \TxRefund \gets \TxGen(\TxFund, \addrRefund) \\
%         \< \< \refundSig^B \sample \Sign(sk_B, \TxRefund) \\
%         \< \sendmessageleft*{pk_B, \refundSig, \addrRedeem} \< \\
%         script := \texttt{OP\_CMS-2of2}(pk_A,pk_B) \\
%         \TxFund \gets \TxGen(\TxInput, script) \< \< \\
%         \TxRefund \gets \TxGen(\TxFund, \addrRefund) \< \< \\
%         \Verify(pk_B, \TxRefund, \refundSig^{B}) \stackrel{?}{=} 1 \\
%         \refundSig^{A} \sample \Sign(sk_A, \TxRefund) \\
%         \refundSig := (\refundSig^{A},\refundSig^{B}) \\
%         \TxRedeem \gets \TxGen(\TxFund, \addrRedeem) \< \< \\
%         \redeemEncSig^A \sample \EncSign(sk_A, Y, \TxRedeem) \\
%         \rec \gets \RecKey(Y, \redeemEncSig^A) \\
%         \< \sendmessageright*{\redeemEncSig^A} \< \\
%         \< \< \TxRedeem \gets \TxGen(\TxFund, \addrRedeem) \\
%         \< \< \EncVer(pk_A, Y, \TxRedeem, \redeemEncSig^A) \stackrel{?}{=} 1 \\
%         \< \< \redeemSig^B \sample \Sign(sk_B,\TxRedeem) \\
%         \< \< \redeemEncSig := (\redeemEncSig^A, \redeemSig^B) \\
%         \pcreturn \TxFund, (\TxRefund, \refundSig), (\TxRedeem, \rec) \< \< \pcreturn \TxFund, (\TxRedeem, \redeemEncSig) \\
%     }
%     \end{center}
%     \end{mdframed}
%     \caption{Caption}
%     \label{fig:my_label}
% \end{figure}

\end{document}






% \subsection{Opacity}

% The opacity property ensures that only those who have the decryption key can extract the signature from a VES ciphertext. The definition was not orthogonal to the unforgeability of the underlying signature scheme. The adversary did not have to necessarily decrypt the ciphertext to break opacity; simply forging a totally different signature on the same message as the encrypted signature was enough to win the game. Note that the BGLS scheme has deterministic signatures so this distinction was not important. We remedy both these issues in the our new definition:

% \newcommand{\VESopacity}{\textsf{VES-Opacity}^{\adv}_{\hatSigma}}
% \begin{definition}[Opacity]
% A VES scheme $\hatSigma$ is opaque if for every PPT algorithm $\adv$, with access to a signature encryption and decryption oracle $ED$, the $\textsf{VES-Opacity}^{\adv}_{\hatSigma}$ experiment outputs 1 with at most negligible probability over the coin tosses of the oracles, $\EncGen, \KeyGen, \EncSign$ and $\adv$. Specifically, for an adversary $\adv(\pkSign,\pkEnc,m,\hatsigma)$, $ED$ responds to requests of the form $(m', \pkEnc)$ if $m' \neq m$ with $(\sigma, \hatsigma)$ such that $\EncVer(\pkSign, \pkEnc, m', \hatsigma) = 1$ and $\sigma$ is the decryption of $\hatsigma$.
% \begin{center}
%     \fbox{
%         \procedure{$\VESopacity$}{%
%             \kSign \sample \KeyGen \\
%             \kEnc \sample \EncGen \\
%             \hatsigma \sample \EncSign(\pkSign, \pkEnc, m) \\
%             \sigma \sample \adv^{E,D}(\pkSign, \pkEnc, m, \hatsigma) \\
%             \pcreturn \sigma = \DecSig(\skEnc,\hatsigma) \\
%         }
%         \pchspace
%         \procedure{Oracle $\tilde{E}_{\pkSign,\pkEnc}(m')$}{
%              \pcreturn \EncSign(\skSign,\pkEnc,m')
%         }
%         \pchspace
%         \procedure{Oracle $\tilde{D}_{\pkEnc}$}{}

%     }
% \end{center}

% \end{definition}

% It is rather straightforward to see that for a StE VES, if the encryption algorithm is at least one-way then extracting the signature without the decryption key will be hard.  First, we recall the definition of \emph{one-way under chosen plain text attack} (\textsf{OW-CPA}) secure public key encryption.

% \begin{definition}[OW-CPA]
%  An public key encryption scheme $\Pi = (\EncGen, \Enc, \Dec)$ with message space $\mathcal{M}$ is \textsf{OW-CPA} if every PPT algorithm $\adv$ the $\textsf{OW-CPA}^{\adv}_{\Pi}$ experiment outputs 1 with at most negligible probability.
%  \begin{center}
%      \fbox{
%         \procedure{$\textsf{OW-CPA}^{\adv}_{\Pi}$}{
%             \kEnc \sample \EncGen \\
%             m \sample \mathcal{M} \\
%             c \sample \Enc(\pkEnc, m) \\
%             m' \sample \adv(\pkEnc, c) \\
%             \pcreturn m' = m \\
%         }
%      }
%  \end{center}
% \end{definition}


% \begin{theorem}
% Let $\hatSigma$ be StE VES scheme with associated public key encryption scheme $\Pi$ and let $\Sigma$ be its underlying signature scheme. If $\Sigma$ is \EUFCMA and $\Pi$ is \textsf{OW-CPA} then it is opaque.
% \end{theorem}

% \begin{proof}[Proof Sketch]
% The only ways for the adversary can output $\sigma = \DecSig(\skEnc, \hatsigma)$ and break the opacity of $\hatSigma$ in the $\VESopacity$ experiment is to (i) forge the signature or (ii) decrypt the ciphertext. Since $\Sigma$ is \EUFCMA and $\hatSigma$ is StE, it is also \EUFCMAVES which means it will succeed at (i) with negligible probability and since the encryption is \textsf{OW-CPA} it will succeed at (ii) with negligible probability.
% \end{proof}