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

\documentclass{beamer}

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

\title{Secure Signatures: Harder Than You Think}
\author{Andrew Poelstra}
\institute{\texttt{schnorr@wpsoftware.net}}
\date{March 9, 2019}

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

\begin{document}
\frame{ \frametitle{}
\begin{center}
{\small MIT Bitcoin Expo, March 9, 2019}~\\~\\~\\~\\
{\color{darkred}
\Huge Secure Signatures:\\{\small~\\}
\huge Harder Than You Think\\}~\\~\\~\\
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{Secure Signatures}
  \begin{center}
  \begin{align*}
      \P &= \x\G\\
\\
      \R &= \k\G\\
      \e &= H(\P, \R, \m) \\
      \s\wG &= \k\wG + \e\x\wG
  \end{align*}
$(\s, \R)$ is the signature.
  \end{center}
}
\frame
{
  \frametitle{Secure Signatures}
  \begin{center}
  \begin{align*}
      \P &= \x\G\\
\\
      \R &= \k\G\\
      \e &= H(\P, \R, \m) \\
      \s\G &= \k\G + \e\x\G
  \end{align*}
$(\s, \R)$ is the signature.
  \end{center}
}
\frame
{
  \frametitle{Secure Signatures}
  What makes a signature ``secure''?\\~\\
  \begin{itemize}
  \item If nobody (i.e. no probablistic poly-time algorithm) can extract the secret key from signatures?\\~\\
  \item If nobody can sign a given message without the secret key?\\~\\
  \item If nobody can sign \emph{any} message?\\~\\
  \item What if they're allowed to request signatures on other messages?
  \item The same message?\\~\\
  \item What if they can change the key? Choose it freely?
  \end{itemize}
}
\frame
{
  \frametitle{Secure Signatures}
  \begin{itemize}
  \item Also, does $\k$ \emph{really} have to be uniformly random?\\~\\
  \item Yes. But we can get away with setting $\k=H(\x\|m)$. Why?\\~\\
  \item How about $\x$?
  \end{itemize}
}

\frame
{
  \frametitle{Sign-to-Contract}
  \begin{center}
  \begin{align*}
      \P &= \x\G\\
\\
      \Rz &= \k\G\\
      \R &= \Rz + H(\Rz\|\c)\G\\
      \e &= H(\P, \R, \m) \\
      \s\wG &= (\k + H(\Rz\|\c))\wG + \e\x\wG
  \end{align*}
  \end{center}
}
\frame
{
  \frametitle{Sign-to-Contract}
  \begin{center}
  \begin{align*}
      \P &= \x\G\\
\\
      \Rz &= \k\G\\
      \R &= \Rz + H(\Rz\|\c)\G\\
      \e &= H(\P, \R, \m) \\
      \s\G &= (\k + H(\Rz\|\c))\G + \e\x\G
  \end{align*}
  \end{center}
}

\frame
{
  \frametitle{Sign-to-Contract Replay Attack}
Suppose $\k = H(\x\|m)$.
  \begin{center}
  \begin{align*}
      \s &= (\k + H(\Rz\|\c)) + \e\x\\
      -~\s &= (\k + H(\Rz\|\c')) + \e'\x\\
\hline\\
      0 &= 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{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{center}
  \begin{align*}
      \P_i &= \x_i\G\\
      \P &= \sum \P_i\\
\\
      \R_i &= \k_i\G
  \end{align*}
(exchange $\R_i$'s)
  \begin{align*}
      \R &= \sum \R_i\\
      \e &= H(\P, \R, \m) \\
      \s_i\wG &= \k_i\wG + \e\x_i\wG
  \end{align*}
(exchange $\s_i$'s)
  \begin{align*}
      \s\wG &= \sum \k_i\wG + \sum \e\x_i\wG
  \end{align*}
  \end{center}
}
\frame
{
  \frametitle{Multisignatures}
  \begin{center}
  \begin{align*}
      \P_i &= \x_i\G\\
      \P &= \sum \P_i\\
\\
      \R_i &= \k_i\G
  \end{align*}
(exchange $\R_i$'s)
  \begin{align*}
      \R &= \sum \R_i\\
      \e &= H(\P, \R, \m) \\
      \s_i\G &= \k_i\G + \e\x_i\G
  \end{align*}
(exchange $\s_i$'s)
  \begin{align*}
      \s\G &= \sum \k_i\G + \sum\e\x_i\G
  \end{align*}
  \end{center}
}
\frame
{
  \frametitle{Multisignatures}
  What does it mean for a \emph{multisignature} to be secure?
  \begin{itemize}
  \item Now the attacker can be a signer? Freely choose the key?\\~\\
  \item How about \emph{all} the signers? All but one?\\~\\
  \item Start multiple signing sessions in parallel?
  \end{itemize}
}

\frame
{
  \frametitle{Multisignatures}
  \begin{itemize}
  \item In fact the just-described scheme is insecure in multiple ways.\\~\\
  \item Rogue-key attacks; if $\P=\sum \P_i$ then a bad signer can choose the whole key.\\~\\
  \item So set $\P=\sum \mu_i\P_i$ where $\mu_i$ is ``random''. (Hash $\P_i$? Or \emph{all} the $\P_i$'s?)\\~\\
  \item Parallel attack: grind $\R$'s until you get a lot of $\e$'s that sum to each other.\\~\\
  \item So add an extra round where everyone precommits to $\R_i$, preventing any individual from grinding $\R$.
  \end{itemize}
}

\frame
{
    \frametitle{~}
    \begin{center}
    Thank you.
    ~\\~\\~\\
    Andrew Poelstra\\
    \texttt{clauspschnorr@wpsoftware.net}
    \end{center}
}

\end{document}