%% v2.2 [2016/03/25]
\documentclass[paper]{ieice}
%\documentclass[invited]{ieice}
%\documentclass[position]{ieice}
%\documentclass[survey]{ieice}
%\documentclass[invitedsurvey]{ieice}
%\documentclass[review]{ieice}
%\documentclass[tutorial]{ieice}
%\documentclass[letter]{ieice}
%\documentclass[brief]{ieice}
%\usepackage[dvips]{graphicx}
\usepackage[pdftex]{graphicx,xcolor}% for pdflatex
%\usepackage[dvipdfmx]{graphicx,xcolor}% for platex or uplatex
% \usepackage{lmodern}
\usepackage[fleqn]{amsmath}
% \usepackage{amsfonts}
% \RequirePackage[OT1]{fontenc}

\usepackage{newtxtext}
\usepackage[varg]{newtxmath}


%% <local definitions>
\def\ClassFile{\texttt{ieice.cls}}
\newcommand{\PS}{{\scshape Post\-Script}}
\newcommand{\AmSLaTeX}{%
 $\mathcal A$\lower.4ex\hbox{$\!\mathcal M\!$}$\mathcal S$-\LaTeX}
\def\BibTeX{{\rmfamily B\kern-.05em
 \textsc{i\kern-.025em b}\kern-.08em
  T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}}
\hyphenation{man-u-script}
\makeatletter
\def\tmpcite#1{\@ifundefined{b@#1}{\textbf{?}}{\csname b@#1\endcsname}}%
\makeatother
%% </local definitions>

% ---- LNCS tips begin ---- %

%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}

% ---- LNCS tips end ---- %

\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,fit}

%\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


\field{A}
% \vol{??}
% \no{1}
%\SpecialIssue{}
\title[Improving the efficiency of a reaction attack on the QC-MDPC McEliece]
      {Improving the efficiency of a reaction attack on the QC-MDPC McEliece}
% \titlenote{This paper was presented at ...}
\authorlist{%
 \authorentry{Thales Bandiera~Paiva}{n}{labelA}\MembershipNumber{}
 \authorentry{Routo Terada}{m}{labelB}\MembershipNumber{1111111}
}
\affiliate[labelB]{T. Bandiera~Paiva is with the Dept. of
Computer Science, Universidade de São
Paulo, São Paulo State,
Brazil e-mail:tpaiva@ime.usp.br, supported by CAPES grant number 00.889.834/0001-08.}

\affiliate[labelA]{R. Terada is with the Dept. of
Computer Science, Universidade de São
Paulo, São Paulo State, Brazil e-mail: rt@ime.usp.br,
supported by FAPESP grant number 2015/01587-0, CNPq grant number
442014/2014-7.}

\received{0000}{00}{00}
\revised{0000}{00}{00}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}

\newtheorem{definition}[theorem]{Definition}

\newenvironment{proof}[1][Proof]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}

\newcommand{\qed}{\nobreak \ifvmode \relax \else
      \ifdim\lastskip<1.5em \hskip-\lastskip
      \hskip1.5em plus0em minus0.5em \fi \nobreak
      \vrule height0.75em width0.5em depth0.25em\fi}

\begin{document}
%\linenumbers
%%\linenumberdisplaymath
%%\realpagewiselinenumbers
%%\runninglinenumbers
%%\pagewiselinenumbers
\maketitle

\begin{summary}

The QC-MDPC McEliece scheme was considered one of the most
promising public key encryption schemes for efficient post quantum secure
encryption. As a variant of the McEliece scheme, it is based on the
syndrome decoding problem, which is a hard problem from Coding Theory.
Its key sizes are competitive with the ones of the widely used
RSA cryptosystem, and it came with an apparently strong security reduction.
For three years, the scheme has not suffered major threats, until the end of 2016,
at the Asiacrypt, when Guo, Johansson, and Stankovski presented a
reaction attack on the QC-MDPC that exploits one aspect that was not considered
in the security reduction: the probability of a decoding failure to occur
is lower when the secret key and the error used for encryption share certain properties.
Recording the decoding failures, the attacker obtains information about the
secret key and then use the information gathered to reconstruct the key.
Guo et al. presented an algorithm for key reconstruction
for which we can point two weaknesses.
The first one is that it cannot deal with partial information about the
secret key, resulting in the
attacker having to send a large number of decoding challenges. The second one
is that it does not scale well for higher security levels.
To improve the attack, we propose a key reconstruction algorithm that
runs faster than Guo's et al. algorithm using around 20\% less
interaction with the secret key holder,
for parameters suggested for 80 bits of security.
It also has a lower asymptotic
complexity which makes it scale much better for higher security parameters.
The algorithm can be parallelized straightforwardly, which is not the case
for the one by Guo et al..

\end{summary}
\begin{keywords}
QC-MDPC McEliece, post-quantum cryptography, reaction attack
\end{keywords}

% \showthe\font
\input intro
\input prelim
\input mdpc
\input idea
\input complexity
\input expresults
\input conclusion

\section*{Acknowledgments}
The simulations were performed using the High Performance Computing resources
provided by the Technology Superintendence of Universidade de São Paulo.

\bibliographystyle{ieicetr}% bib style
\bibliography{biblio}% your bib database

\profile*{Thales Bandiera~Paiva}{MSc student at the Department of Computer
Science, Universidade de São Paulo, Brazil, received his bachelor's degree
in Computer Science from Universidade de São Paulo in 2015.}
\label{profile}

\profile*{Routo Terada}{Professor at the Department of Computer
Science, Universidade de São Paulo, Brazil, MSc
in Applied Math from Universidade de São Paulo and PhD in
Computer Science from University of Wisconsin-Madison, USA.}

\end{document}



