\def\hs{\hspace{0.4 cm}}

\documentclass{beamer}

\usetheme{Warsaw}
\usecolortheme{beaver}
\setbeamertemplate{footline}[page number]
\beamertemplatenavigationsymbolsempty

\title{Threshold Signatures, Accountability and More}
\author{Andrew Poelstra}
\institute{\texttt{schnorr@wpsoftware.net}}
\date{March 11, 2019}

\usepackage{amsfonts,amsmath,latexsym,color,epsfig,graphicx,multirow,rotating}
\usepackage{anyfontsize}

\begin{document}
\frame{ \frametitle{}
\begin{center}
{\small NIST Threshold Cryptography Workshop, March 12, 2019}~\\~\\~\\~\\
{\color{darkred} \Large Multisignatures and Threshold Signatures\\in a Bitcoin Context}\\~\\~\\
Andrew Poelstra\\
{\tiny Director of Research, Blockstream}
\end{center} }

\newcommand{\G}{{\color{black}G}}
\newcommand{\wG}{{\color{white}G}}
\newcommand{\mui}{{\color{blue}\mu_i}}
\newcommand{\wmui}{{\color{white}\mu_i}}
\newcommand{\m}{{\color{blue}m}}
\newcommand{\x}{{\color{red}x}}
\renewcommand{\t}{{\color{red}t}}
\renewcommand{\k}{{\color{red}k}}
\renewcommand{\P}{{\color{blue}P}}
\newcommand{\R}{{\color{blue}R}}
\newcommand{\Rz}{{\color{purple}R^0}}
\renewcommand{\c}{{\color{purple}c}}
\newcommand{\T}{{\color{blue}T}}
\newcommand{\s}{{\color{blue}s}}
\newcommand{\e}{{\color{blue}e}}

\newcommand{\gm}[1]{{\color{red}\gamma_{#1}}}
\newcommand{\poly}[1]{{\color{red}p_{#1}}}
\newcommand{\share}[2]{{\color{red}\zeta_{#1,#2}}}
\newcommand{\boxthing}{{\color{red}\left[\vdots\qquad\vdots\right]_j}}

\frame
{
  \frametitle{Bitcoin}
  \begin{itemize}
  \item Bitcoin is a cryptocurrency denominated in \emph{unspent transaction outputs} (UTXOs)
      labelled by a value and (script) public key.\\~\\
  \item Transactions destroy UTXOs and create new UTXOs with equivalent value and
      different public keys.\\~\\
  \item Transactions are serialized onto a \emph{blockchain} which defines a canonical history.
  \end{itemize}
}
\frame
{
  \frametitle{Bitcoin}
  \begin{itemize}
  \item Bitcoin users generate a lot of keys; must store and recognize these.\\~\\
  \item Loss or theft of a key is not recoverable.\\~\\
  \item Keys are typically not uniform random; are related in detectable ways.\\~\\
  \item Diverse hardware: PCs, tiny devices, cell phones, virtual machines. Allergic
     to randomness.
  \end{itemize}
}

\frame
{
  \frametitle{Schnorr Signatures}
  \begin{center}
  \begin{align*}
      \P &= \x\G\\
\\
      \R &= \k\G\\
      \e &= H(\P, \R, \m) \\
      \s &= \k + \e\x
  \end{align*}
  Notice $\P$ in the hash function.
  \end{center}
}

\frame
{
  \frametitle{Schnorr Signatures}
  \begin{itemize}
  \item Consider ``BIP32'' keys $P$ and $P'$, where $P' = P + \gamma\G$ for some non-secret $\gamma$.
  \item Used to make key generation and backup more tractable.
  \end{itemize}
  \begin{center}
  \begin{align*}
      \R &= \k\G\\
      \e &= H(\R, \m) \\
      \s &= \k + \e\x  \\
         &\to \k + \e\x + \e\gamma
  \end{align*}
  \end{center}
}

\frame
{
  \frametitle{Sign-to-Contract}
  \begin{itemize}
  \item Consider the ``sign-to-contract'' construction which overloads a signature
  as a signature on another, auxiliary message.
  \item Used for timestamping, wallet audit logging, and anti-covert-sidechannel resistance.
  \end{itemize}
  \begin{center}
  \begin{align*}
      \P &= \x\G\\
\\
      \Rz &= \k\G\\
      \R &= \Rz + H(\Rz\|\c)\G\\
      \e &= H(\P, \R, \m) \\
      \s &= (\k + H(\Rz\|\c)) + \e\x
  \end{align*}
  \end{center}
}

\frame
{
  \frametitle{Sign-to-Contract Replay Attack}
Now suppose $\k = H(\x\|m)$, as in RFC6979.
  \begin{center}
  \begin{align*}
      \s &= (\k + H(\Rz\|\c)) + \e\x\\
      -~\s' &= (\k + H(\Rz\|\c')) + \e'\x\\
\hline\\
      \s - \s' &= H(\Rz\|\c) - H(\Rz\|\c') + (\e - \e')\x
  \end{align*}
  \end{center}~\\
So we'd better have $\k = H(\x\|m\|\c)$!
}

\frame
{
  \frametitle{Interlude: Randomness}
  \begin{itemize}
  \item If $\k$ deviates from uniform by any amount, given enough signatures
     lattice techniques can be used to extract secret keys. (In practice at
     least a couple bits of bias are needed.)\\~\\
  \item A malicious manufacturer could insert such bias in a way that only the
     attacker could detect the deviation.\\~\\
  \item No way to prove that deterministic randomness was used (general zkps?
     Hard on typical signing hardware.)
  \end{itemize}
}

\frame
{
  \frametitle{Sign-to-Contract as an Anti-Nonce-Sidechannel Measure}
  \begin{itemize}
  \item If the hardware device knows $\c$ before producing $\Rz$ it can grind $\k$
      so that $(k + H(\Rz\|\c))$ has detectable bias.\\~\\
  \item If it doesn't know $\c$ how can it prevent replay attacks?\\~\\
  \item Send hardware device $H(\c)$ and receive $\Rz$ before giving it $\c$.\\~\\
  \item Then $\k = H(\x\|m\|H(\c))$.
  \end{itemize}
}



\frame
{
  \frametitle{Multisignatures}
  \begin{itemize}
  \item Bitcoin people use ``multisignature'' in a funny way.\\~\\
  \item Includes thresholds (or arbitrary monotone functions of individuals' keys).\\~\\
  \item Do \emph{not} expect or want verifiers to see the original keys, for efficiency
      and privacy.
  \end{itemize}
}

\frame
{
  \frametitle{Multisignatures}
  \begin{itemize}
  \item Plain public-key model.\\~\\
  \item May be chosen (from the set of available keys) adversarially and adaptively.\\~\\
  \item Keys controlled by inflexible offline signing hardware.\\~\\
  \item No good place to store KOSK proofs. No keygen authorities.\\~\\
  \item Keys may encode semantics (e.g. Taproot, pay-to-contract) where KOSK is insufficient for security!
  \end{itemize}
}

\frame
{
  \frametitle{Multisignatures}
  \begin{itemize}
  \item Consider Schnorr multisignatures with combined keys of the form
      $\P = \sum \P_i$.\\~\\
  \item Vulnerable to rogue-key attacks where one participant cancels others' keys.\\~\\
  \item Bitcoin's \emph{Taproot} uses keys of the form $\P = \P' + H(\P'\|\c)\G$ which
      admits a new form of rogue-key attack.\\~\\
  \item KOSK cannot protect against the latter!
  \end{itemize}
}

\frame
{
  \frametitle{Multisignatures}
  \begin{itemize}
  \item Derandomization of the form $\k = H(\x\|\c)$ no longer works.\\~\\
  \item In a multi-round protocol need to consider replay attacks, parallel attacks,
      VM forking, etc.\\~\\
  \item General ZKPs can save us here. More R\&D needed.
  \end{itemize}
}

\frame
{
  \frametitle{Threshold Signatures and Accountability}
  \begin{itemize}
  \item Accountability: ability to prove which specific set of signers
      contributed to a threshold signature.\\~\\
  \item Constant-size non-accountable signatures. Log-sized accountable signatures.\\~\\
  \item Can we close this gap?
  \end{itemize}
}

\frame
{
    \frametitle{~}
    \begin{center}
    Thank you.
    ~\\~\\~\\
    Andrew Poelstra\\
    \texttt{apoelstra@blockstream.com}
    \end{center}
}

\end{document}