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

\documentclass{beamer}

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

\title{Fragile Nonce Selection and ZKPs as a Solution}
\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}
{
{\color{darkred} \Large Fragile Nonce Selection and\\~\\\Huge ZKPs as a Solution}~\\~\\~\\
\small 2nd ZKProof Workshop, 2019}~\\~\\
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{Schnorr Signatures}
  \begin{center}
  \begin{align*}
      \P &= \x\G\\
\\
      \k &\gets \$\\
      \R &= \k\G\\
      \e &= H(\P, \R, \m) \\
      \s &= \k + \e\x
  \end{align*}
  In practice ``$\$$'' is by far the most difficult part of this protocol.
  (see Breitner and Heninger, 2019)
  \end{center}
}

\frame
{
  \frametitle{Schnorr Signatures}
  \begin{itemize}
  \item Standard solution: use RFC6979: $k = H(x\|m)$.\\~\\
  \item Not verifiable.\\~\\
  \item Use a ZKP? Better hope your host doesn't leak the ZKP.\\~\\
  \item \ldots and if you trust the host, just use sign-to-contract.
  \end{itemize}
}

\frame
{
  \frametitle{Schnorr Signatures}
  \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*}
      \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{Multisignatures}
  \begin{itemize}
  \item Consider Schnorr multisignatures with combined keys of the form
      $\P = \sum \mu_i \P_i$ (MuSig).\\~\\
  \item Participant $i$ creates partial signatures with secret key $\mu_i\x_i$.\\~\\
  \item But the challenge $e=H(\P,\R,\m)$ will have contributions from all
     participants. $\R$ could change without $\P$ or $\m$ changing.\\~\\
  \item Replay attacks, parallel attacks, VM forking, etc.\\~\\
  \item So RFC6969 is out. Back to physical randomness?
  \end{itemize}
}

\frame
{
  \frametitle{Multisignatures}
  \begin{itemize}
  \item Suppose instead each party used RFC6979 (or a moral equivalent)
     but provide a ZKP that they produced their nonce deterministically.\\~\\
  \item What's a ``moral equivalent''? A PRF but verifiable. Like a VRF. But not.\\~\\
  \item Upcoming research (Ruffing, Seurin, Wuille 2020)
  \end{itemize}
}

\frame
{
  \frametitle{Multisignatures}
  In general, ZKPs of deterministic PRNG operation can\\~\\
  \begin{itemize}
  \item Turn randomized signatures into unique ones (sooorta. Ignore the ZKP's randomness).\\~\\
  \item Prevent replay attacks.\\~\\
  \item Eliminate the need for broadcast channels?
  \end{itemize}
}

\frame
{
  \frametitle{Threshold Signatures}
  \begin{itemize}
  \item Consider now \emph{threshold} Schnorr signatures (Stinson \& Strobl 2001)\\~\\
  \item Here each participant $i$ shards his key $\x_i$ into shards $\x_i^j$ from
    which $x_i$ can be reconstructed by Lagrange interpolation (Pedersen 1991, GJKR 1999)\\~\\
  \item During signing, participant $i$ similarly shards his nonce $\k_i$.\\~\\
  \item Final signature is assembled by interpolating partial signatures.
  \end{itemize}
}

\frame
{
  \frametitle{Threshold Signatures}
  \begin{itemize}
  \item Requires potentially many rounds; accusations and defenses\\~\\
  \item Could simplify accusation process using zk-PoKs rather than GJKR'99 protocol,
     using PVSS (Stadler '96) (maybe.)\\~\\
  \item Or we could just avoid secret-sharing at signing time, still having potentially many rounds\\~\\
  \item No matter what, we \textbf{need a broadcast channel.}
  \end{itemize}
}

\frame
{
  \frametitle{Threshold Signatures}
  \begin{itemize}
  \item \textbf{Alternately}, suppose each participant produces her interpolation polynomial
      using deterministic randomness.\\~\\
  \item Does PVSS where the public coefficients are accompanied by a ZKP that
      they were formed deterministically.\\~\\
  \item Now a participating signer's entire transcript must be unique.\\~\\
  \item No replays; no physical randomness; fixed
      number of rounds.\\~\\
  \item And it appears our broadcast channel can be replaced with a set-reconciliation phase.
  \end{itemize}
}

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

\end{document}