% This template has been tested with LLNCS DOCUMENT CLASS -- version 2.20 (24-JUN-2015)

%"runningheads" enables:
%  - page number on page 2 onwards
%  - title/authors on even/odd pages
%This is good for other readers to enable proper archiving among other papers and pointing to content.
%Even if the title page states the title, when printed and stored in a folder, when blindly
%opening the folder, one could hit not the title page, but an arbitrary page.
%Therefore, it is good to have title printed on the pages, too.
\documentclass[runningheads,a4paper]{llncs}

%cmap has to be loaded before any font package (such as cfr-lm)
\usepackage{cmap}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{graphicx}

%Even though `american`, `english` and `USenglish` are synonyms for babel package (according to https://tex.stackexchange.com/questions/12775/babel-english-american-usenglish), the llncs document class is prepared to avoid the overriding of certain names (such as "Abstract." -> "Abstract" or "Fig." -> "Figure") when using `english`, but not when using the other 2.
%english has to go last to set it as default language
\usepackage[ngerman,english]{babel}
%Hint by http://tex.stackexchange.com/a/321066/9075 -> enable "= as dashes
\addto\extrasenglish{\languageshorthands{ngerman}\useshorthands{"}}

%better font, similar to the default springer font
%cfr-lm is preferred over lmodern. Reasoning at http://tex.stackexchange.com/a/247543/9075
\usepackage[%
  rm={oldstyle=false,proportional=true},%
  sf={oldstyle=false,proportional=true},%
  tt={oldstyle=false,proportional=true,variable=true},%
  qt=false%
]{cfr-lm}
%
%if more space is needed, exchange cfr-lm by mathptmx
%\usepackage{mathptmx}

%Sorts the citations in the brackets
%It also allows \cite{refa, refb}. Otherwise, the document does not compile.
%  Error message: "White space in argument"
\usepackage{cite}

%% If you need packages for other papers,
%% START COPYING HERE
%% COPY ALSO cmap and fontenc from lines 10 to 12

%extended enumerate, such as \begin{compactenum}
\usepackage{paralist}

%put figures inside a text
%\usepackage{picins}
%use
%\piccaptioninside
%\piccaption{...}
%\parpic[r]{\includegraphics ...}
%Text...

%for easy quotations: \enquote{text}
\usepackage{csquotes}

%enable margin kerning
\usepackage{microtype}

%tweak \url{...}
\usepackage{url}
%\urlstyle{same}
%improve wrapping of URLs - hint by http://tex.stackexchange.com/a/10419/9075
\makeatletter
\g@addto@macro{\UrlBreaks}{\UrlOrds}
\makeatother
%nicer // - solution by http://tex.stackexchange.com/a/98470/9075
%DO NOT ACTIVATE -> prevents line breaks
%\makeatletter
%\def\Url@twoslashes{\mathchar`\/\@ifnextchar/{\kern-.2em}{}}
%\g@addto@macro\UrlSpecials{\do\/{\Url@twoslashes}}
%\makeatother

%diagonal lines in a table - http://tex.stackexchange.com/questions/17745/diagonal-lines-in-table-cell
%slashbox is not available in texlive (due to licensing) and also gives bad results. This, we use diagbox
%\usepackage{diagbox}

%required for pdfcomment later
\usepackage{xcolor}

%enable nice comments
%this also loads hyperref
\usepackage{pdfcomment}
%enable hyperref without colors and without bookmarks
\hypersetup{hidelinks,
   colorlinks=true,
   allcolors=black,
   pdfstartview=Fit,
   breaklinks=true}
%enables correct jumping to figures when referencing
\usepackage[all]{hypcap}

\usepackage[ruled, linesnumbered, noend]{algorithm2e}
\newlength\mylen\newcommand\myinput[1]{%
  \settowidth\mylen{\KwData{}}%
  \setlength\hangindent{\mylen}%
  \hspace*{\mylen}#1\\}

\usepackage{amsfonts,mathtools}
\usepackage{amssymb}
\let\oldemptyset\emptyset
\let\emptyset\varnothing

\newcommand{\commentontext}[2]{\colorbox{yellow!60}{#1}\pdfcomment[color={0.234 0.867 0.211},hoffset=-6pt,voffset=10pt,opacity=0.5]{#2}}
\newcommand{\commentatside}[1]{\pdfcomment[color={0.045 0.278 0.643},icon=Note]{#1}}

%compatibality with packages todo, easy-todo, todonotes
\newcommand{\todo}[1]{\commentatside{#1}}
%compatiblity with package fixmetodonotes
\newcommand{\TODO}[1]{\commentatside{#1}}

%enable \cref{...} and \Cref{...} instead of \ref: Type of reference included in the link
\usepackage[capitalise,nameinlink]{cleveref}
%Nice formats for \cref
\crefname{section}{Sect.}{Sect.}
\Crefname{section}{Section}{Sections}


\usepackage{xspace}
\usepackage{booktabs}
\usepackage{mathtools}
\usepackage{tikz}
\usetikzlibrary{chains,shapes.geometric,shapes.arrows,fit}
\usetikzlibrary{decorations.pathreplacing,quotes}

\usepackage{subfig}

%\newcommand{\eg}{e.\,g.\xspace}
%\newcommand{\ie}{i.\,e.\xspace}
\newcommand{\eg}{e.\,g.,\ }
\newcommand{\ie}{i.\,e.,\ }

%introduce \powerset - hint by http://matheplanet.com/matheplanet/nuke/html/viewtopic.php?topic=136492&post_id=997377
\DeclareFontFamily{U}{MnSymbolC}{}
\DeclareSymbolFont{MnSyC}{U}{MnSymbolC}{m}{n}
\DeclareFontShape{U}{MnSymbolC}{m}{n}{
    <-6>  MnSymbolC5
   <6-7>  MnSymbolC6
   <7-8>  MnSymbolC7
   <8-9>  MnSymbolC8
   <9-10> MnSymbolC9
  <10-12> MnSymbolC10
  <12->   MnSymbolC12%
}{}
\DeclareMathSymbol{\powerset}{\mathord}{MnSyC}{180}

% correct bad hyphenation here
\hyphenation{op-tical net-works semi-conduc-tor}

%% END COPYING HERE

\input macros


\begin{document}

\title{A Timing Attack on the HQC \\ Encryption Scheme\thanks{T. B. Paiva is supported by CAPES. R. Terada is supported
by CNPq grant number 442014/2014-7.}}


%If Title is too long, use \titlerunning
%\titlerunning{Short Title}

%Single institute
\author{Thales Bandiera Paiva \and Routo Terada}
%If there are too many authors, use \authorrunning
%\authorrunning{First Author et al.}
\institute{Universidade de São Paulo \\ \email{\{tpaiva, rt\}@ime.usp.br}}

%Multiple insitutes
%Currently disabled
%
% \iffalse
% %Multiple institutes are typeset as follows:
% \author{Firstname Lastname\inst{1} \and Firstname Lastname\inst{2} }
% %If there are too many authors, use \authorrunning
% %\authorrunning{First Author et al.}

% \institute{
% Insitute 1\\
% \email{...}\and
% Insitute 2\\
% \email{...}
% }
% \fi

\maketitle


\begin{abstract}

The HQC public-key encryption scheme is a promising code-based submission to
NIST's post-quantum cryptography standardization process.
The scheme is based on the decisional decoding problem for random
quasi-cyclic codes.
One problem of the HQC's reference implementation submitted to NIST in the
first round of the standardization process is that it is not constant-time.
In particular, the decryption time depends on the number of errors decoded
by a BCH decoder.
We use this to present the first timing attack against HQC.
The attack is practical, requiring the attacker to record the
decryption time of around 400 million ciphertexts for a
set of HQC parameters corresponding to 128 bits of security.
This makes the use of constant-time decoders mandatory for the scheme to
be considered secure.


\end{abstract}
\begin{keywords}
HQC, post-quantum cryptography, timing attack, BCH decoder
\end{keywords}

% \showthe\font
\input intro
\input prelim
\input hqc
\input attack
\input analysis
\input expresults
\input countermeasures
\input conclusion

\section*{Acknowledgments}


This study was financed in part by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Brasil (CAPES) - Finance Code 001.
This research is part of the INCT of the Future Internet for Smart Cities funded by CNPq proc. 465446/2014-0, Coordenação de Aperfeiçoamento de Pessoal de Nível Superior – Brasil (CAPES) – Finance Code 001, FAPESP proc. 14/50937-1, and FAPESP proc. 15/24485-9.

\bibliographystyle{splncs04}
\bibliography{biblio}

\end{document}
