\newcommand{\etalchar}[1]{$^{#1}$}
 \newcommand{\noop}[1]{}
\begin{thebibliography}{FGUO{\etalchar{+}}13}

\bibitem[AB09]{arora2009computational}
Sanjeev Arora e Boaz Barak.
\newblock {\em Computational complexity: a modern approach}.
\newblock Cambridge University Press, 2009.

\bibitem[ABB{\etalchar{+}}15]{augot16initial}
Daniel Augot, Lejla Batina, Daniel~J Bernstein, Joppe Bos, Johannes Buchmann,
  Wouter Castryck, O~Dunkelmann, Tim G{\"u}neysu, Shay Gueron, Andreas
  H{\"u}lsing et~al.
\newblock Initial recommendations of long-term secure post-quantum systems.
\newblock {\em URL: https://pqcrypto. eu. org/docs/initial-recommendations.
  pdf. Citations in this document}, 16, 2015.

\bibitem[AKS04]{agrawal2004primes}
Manindra Agrawal, Neeraj Kayal e Nitin Saxena.
\newblock Primes is in p.
\newblock {\em Annals of mathematics}, p\'{a}ginas 781--793, 2004.

\bibitem[BBD09]{bernstein2009post}
Daniel~J Bernstein, Johannes Buchmann e Erik Dahmen.
\newblock {\em Post-quantum cryptography}.
\newblock Springer Science \& Business Media, 2009.

\bibitem[BCGO09]{berger2009reducing}
Thierry~P Berger, Pierre-Louis Cayrel, Philippe Gaborit e Ayoub Otmani.
\newblock Reducing key length of the {{McEliece}} cryptosystem.
\newblock Em {\em Progress in Cryptology--AFRICACRYPT 2009}, p\'{a}ginas
  77--97. Springer, 2009.

\bibitem[BCS13]{bernstein2013mcbits}
Daniel~J Bernstein, Tung Chou e Peter Schwabe.
\newblock {McBits}: fast constant-time code-based cryptography.
\newblock Em {\em International Workshop on Cryptographic Hardware and Embedded
  Systems}, p\'{a}ginas 250--272. Springer, 2013.

\bibitem[BDPR98]{bellare1998relations}
Mihir Bellare, Anand Desai, David Pointcheval e Phillip Rogaway.
\newblock Relations among notions of security for public-key encryption
  schemes.
\newblock Em {\em Advances in Cryptology—CRYPTO'98}, p\'{a}ginas 26--45.
  Springer, 1998.

\bibitem[Ber73]{berlekamp1973goppa}
Elwyn~R Berlekamp.
\newblock Goppa codes.
\newblock {\em Information Theory, IEEE Transactions on}, 19(5):590--592, 1973.

\bibitem[BLP08]{bernstein2008attacking}
Daniel~J Bernstein, Tanja Lange e Christiane Peters.
\newblock Attacking and defending the {McEliece} cryptosystem.
\newblock Em {\em Post-Quantum Cryptography}, p\'{a}ginas 31--46. Springer,
  2008.

\bibitem[BMVT78]{berlekamp1978inherent}
Elwyn~R Berlekamp, Robert~J {McEliece} e Henk~CA Van~Tilborg.
\newblock On the inherent intractability of certain coding problems.
\newblock {\em IEEE Transactions on Information Theory}, 24(3):384--386, 1978.

\bibitem[BR93]{bellare1993random}
Mihir Bellare e Phillip Rogaway.
\newblock Random oracles are practical: A paradigm for designing efficient
  protocols.
\newblock Em {\em Proceedings of the 1st ACM conference on Computer and
  communications security}, p\'{a}ginas 62--73. ACM, 1993.

\bibitem[BSC16]{baldi2016soft}
Marco Baldi, Paolo Santini e Franco Chiaraluce.
\newblock Soft {McEliece}: {MDPC} code-based {McEliece} cryptosystems with very
  compact keys through real-valued intentional errors.
\newblock p\'{a}ginas 795--799, 2016.

\bibitem[BT{\etalchar{+}}06]{bogdanov2006average}
Andrej Bogdanov, Luca Trevisan et~al.
\newblock Average-case complexity.
\newblock {\em Foundations and Trends{\textregistered} in Theoretical Computer
  Science}, 2(1):1--106, 2006.

\bibitem[CCJ{\etalchar{+}}16]{chen2016report}
Lily Chen, Lily Chen, Stephen Jordan, Yi-Kai Liu, Dustin Moody, Rene Peralta,
  Ray Perlner e Daniel Smith-Tone.
\newblock {\em Report on post-quantum cryptography}.
\newblock US Department of Commerce, National Institute of Standards and
  Technology, 2016.

\bibitem[CFS01]{courtois2001achieve}
Nicolas~T Courtois, Matthieu Finiasz e Nicolas Sendrier.
\newblock How to achieve a {McEliece}-based digital signature scheme.
\newblock Em {\em International Conference on the Theory and Application of
  Cryptology and Information Security}, p\'{a}ginas 157--174. Springer, 2001.

\bibitem[Cho16]{chou2016qcbits}
Tung Chou.
\newblock {QcBits}: constant-time small-key code-based cryptography.
\newblock Em {\em International Conference on Cryptographic Hardware and
  Embedded Systems}, p\'{a}ginas 280--300. Springer, 2016.

\bibitem[Cor64]{corr1964statistical}
F~Corr.
\newblock A statistical evaluation of error detection cyclic codes for data
  transmission.
\newblock {\em IEEE Transactions on Communications Systems}, 12(2):211--216,
  1964.

\bibitem[DDN03]{dolev2003nonmalleable}
Danny Dolev, Cynthia Dwork e Moni Naor.
\newblock Nonmalleable cryptography.
\newblock {\em SIAM review}, 45(4):727--784, 2003.

\bibitem[DES77]{Des77dataencryption}
DES.
\newblock Data encryption standard.
\newblock Em {\em In FIPS PUB 46, Federal Information Processing Standards
  Publication}, p\'{a}ginas 46--2, 1977.

\bibitem[DH76]{diffie1976new}
Whitfield Diffie e Martin Hellman.
\newblock New directions in cryptography.
\newblock {\em IEEE transactions on Information Theory}, 22(6):644--654, 1976.

\bibitem[DR13]{daemen2013design}
Joan Daemen e Vincent Rijmen.
\newblock {\em The design of Rijndael: AES-the advanced encryption standard}.
\newblock Springer Science \& Business Media, 2013.

\bibitem[FGUO{\etalchar{+}}13]{faugere2013distinguisher}
Jean-Charles Faugere, Val{\'e}rie Gauthier-Umana, Ayoub Otmani, Ludovic Perret
  e Jean-Pierre Tillich.
\newblock A distinguisher for high-rate {McEliece} cryptosystems.
\newblock {\em IEEE Transactions on Information Theory}, 59(10):6830--6844,
  2013.

\bibitem[FHS{\etalchar{+}}17]{fabvsivc2017reaction}
Tom{\'a}{\v{s}} Fab{\v{s}}i{\v{c}}, Viliam Hromada, Paul Stankovski, Pavol
  Zajac, Qian Guo e Thomas Johansson.
\newblock A reaction attack on the {QC-LDPC McEliece} cryptosystem.
\newblock Em {\em International Workshop on Post-Quantum Cryptography},
  p\'{a}ginas 51--68. Springer, 2017.

\bibitem[FO99]{fujisaki1999secure}
Eiichiro Fujisaki e Tatsuaki Okamoto.
\newblock Secure integration of asymmetric and symmetric encryption schemes.
\newblock Em {\em Annual International Cryptology Conference}, p\'{a}ginas
  537--554. Springer, 1999.

\bibitem[FOP{\etalchar{+}}16]{faugere2016structural}
Jean-Charles Faugere, Ayoub Otmani, Ludovic Perret, Fr{\'e}d{\'e}ric
  De~Portzamparc e Jean-Pierre Tillich.
\newblock Structural cryptanalysis of {McEliece} schemes with compact keys.
\newblock {\em Designs, Codes and Cryptography}, 79(1):87--112, 2016.

\bibitem[FOPT10]{faugere2010algebraic}
Jean-Charles Faugere, Ayoub Otmani, Ludovic Perret e Jean-Pierre Tillich.
\newblock Algebraic cryptanalysis of {McEliece} variants with compact keys.
\newblock Em {\em Advances in Cryptology--Eurocrypt 2010}, p\'{a}ginas
  279--298. Springer, 2010.

\bibitem[FS09]{finiasz2009security}
Matthieu Finiasz e Nicolas Sendrier.
\newblock Security bounds for the design of code-based cryptosystems.
\newblock Em {\em Asiacrypt}, volume 5912, p\'{a}ginas 88--105. Springer, 2009.

\bibitem[Gab05]{gaborit2005shorter}
Philippe Gaborit.
\newblock Shorter keys for code based cryptography.
\newblock Em {\em Proceedings of the 2005 International Workshop on Coding and
  Cryptography (WCC 2005)}, p\'{a}ginas 81--91, 2005.

\bibitem[Gal62]{gallager1962low}
Robert Gallager.
\newblock Low-density parity-check codes.
\newblock {\em IRE Transactions on information theory}, 8(1):21--28, 1962.

\bibitem[Gal12]{galbraith2012mathematics}
Steven~D Galbraith.
\newblock {\em Mathematics of public key cryptography}.
\newblock Cambridge University Press, 2012.

\bibitem[GHR95]{greenlaw1995limits}
Raymond Greenlaw, H~James Hoover e Walter~L Ruzzo.
\newblock {\em Limits to parallel computation: P-completeness theory}.
\newblock Oxford University Press on Demand, 1995.

\bibitem[GJ16]{guo2016p}
Qian Guo e Thomas Johansson.
\newblock A p-ary {MDPC} scheme.
\newblock Em {\em Information Theory (ISIT), 2016 IEEE International Symposium
  on}, p\'{a}ginas 1356--1360. IEEE, 2016.

\bibitem[GJS16]{guo2016key}
Qian Guo, Thomas Johansson e Paul Stankovski.
\newblock A key recovery attack on {MDPC} with {CCA} security using decoding
  errors.
\newblock Em {\em 22nd Annual International Conference on the Theory and
  Applications of Cryptology and Information Security (ASIACRYPT)}, 2016.

\bibitem[GM84]{goldwasser1984probabilistic}
Shafi Goldwasser e Silvio Micali.
\newblock Probabilistic encryption.
\newblock {\em Journal of computer and system sciences}, 28(2):270--299, 1984.

\bibitem[Gop70]{goppa1970new}
Valerii~Denisovich Goppa.
\newblock A new class of linear correcting codes.
\newblock {\em Problemy Peredachi Informatsii}, 6(3):24--30, 1970.

\bibitem[Gro96]{grover1996fast}
Lov~K Grover.
\newblock A fast quantum mechanical algorithm for database search.
\newblock Em {\em Proceedings of the twenty-eighth annual ACM symposium on
  Theory of computing}, p\'{a}ginas 212--219. ACM, 1996.

\bibitem[Guo16]{Guo2016Youtube}
Qian Guo.
\newblock Guo's presentation at {Asiacrypt}.
\newblock \url{https://youtu.be/tKvDdGLJLZc?t=1006}, 2016.

\bibitem[HGS99]{hall1999reaction}
Chris Hall, Ian Goldberg e Bruce Schneier.
\newblock Reaction attacks against several public-key cryptosystem.
\newblock Em {\em International Conference on Information and Communications
  Security}, p\'{a}ginas 2--12. Springer, 1999.

\bibitem[HP10]{huffman2010fundamentals}
W~Cary Huffman e Vera Pless.
\newblock {\em Fundamentals of error-correcting codes}.
\newblock Cambridge university press, 2010.

\bibitem[HPS98]{hoffstein1998ntru}
Jeffrey Hoffstein, Jill Pipher e Joseph~H Silverman.
\newblock Ntru: A ring-based public key cryptosystem.
\newblock Em {\em International Algorithmic Number Theory Symposium},
  p\'{a}ginas 267--288. Springer, 1998.

\bibitem[HVMG13]{heyse2013smaller}
Stefan Heyse, Ingo Von~Maurich e Tim G{\"u}neysu.
\newblock Smaller keys for code-based cryptography: {QC-{MDPC}} {McEliece}
  implementations on embedded devices.
\newblock Em {\em Cryptographic Hardware and Embedded Systems-CHES 2013},
  p\'{a}ginas 273--292. Springer, 2013.

\bibitem[Imp95]{impagliazzo1995personal}
Russell Impagliazzo.
\newblock A personal view of average-case complexity.
\newblock Em {\em Structure in Complexity Theory Conference, 1995., Proceedings
  of Tenth Annual IEEE}, p\'{a}ginas 134--147. IEEE, 1995.

\bibitem[KI01]{kobara2001semantically}
Kazukuni Kobara e Hideki Imai.
\newblock Semantically secure {McEliece} public-key cryptosystems-conversions
  for {McEliece} {PKC}.
\newblock Em {\em International Workshop on Public Key Cryptography},
  p\'{a}ginas 19--35. Springer, 2001.

\bibitem[LB88]{lee1988observation}
Pil~Joong Lee e Ernest~F Brickell.
\newblock An observation on the security of mceliece's public-key cryptosystem.
\newblock Em {\em Eurocrypt}, volume~88, p\'{a}ginas 275--280. Springer, 1988.

\bibitem[Lev68]{levy1968weight}
J~Levy.
\newblock A weight distribution bound for linear codes.
\newblock {\em IEEE Transactions on Information Theory}, 14(3):487--490, 1968.

\bibitem[Mac99]{mackay1999good}
David~JC MacKay.
\newblock Good error-correcting codes based on very sparse matrices.
\newblock {\em IEEE transactions on Information Theory}, 45(2):399--431, 1999.

\bibitem[{Mar}12]{M4RI}
{Martin Albrecht and Gregory Bard}.
\newblock {\em {The M4RI Library -- Version 20121224}}.
\newblock {The M4RI~Team}, 2012.

\bibitem[MB09]{misoczki2009compact}
Rafael Misoczki e Paulo~SLM Barreto.
\newblock Compact {McEliece} keys from goppa codes.
\newblock Em {\em Selected Areas in Cryptography}, p\'{a}ginas 376--392.
  Springer, 2009.

\bibitem[{McE}78]{mceliece1978}
R.~J. {McEliece}.
\newblock A public-key cryptosystem based on algebraic coding theory.
\newblock {\em Deep Space Network Progress Report}, 44:114--116, 1978.

\bibitem[Mil86]{miller1986ecc}
V.S. Miller.
\newblock Use of elliptic curves in cryptography.
\newblock {\em Advances in Cryptology (CRYPTO85)}, p\'{a}ginas 417--426, 1986.

\bibitem[MOG15]{maurich2015implementing}
Ingo~Von Maurich, Tobias Oder e Tim G{\"u}neysu.
\newblock Implementing {QC-{MDPC}} {McEliece} encryption.
\newblock {\em ACM Transactions on Embedded Computing Systems (TECS)},
  14(3):44, 2015.

\bibitem[MTSB13]{misoczki2013mdpc}
Rafael Misoczki, Jean-Pierre Tillich, Nicolas Sendrier e Paulo~SLM Barreto.
\newblock {MDPC}-{McEliece}: New {McEliece} variants from moderate density
  parity-check codes.
\newblock Em {\em Information Theory Proceedings (ISIT), 2013 IEEE
  International Symposium on}, p\'{a}ginas 2069--2073. IEEE, 2013.

\bibitem[MVOV96]{menezes1996handbook}
Alfred~J Menezes, Paul~C Van~Oorschot e Scott~A Vanstone.
\newblock {\em Handbook of applied cryptography}.
\newblock CRC press, 1996.

\bibitem[Nie86]{niederreiter1986knapsack}
Harald Niederreiter.
\newblock Knapsack-type cryptosystems and algebraic coding theory, problems of
  control and information theory 15, 159--166.
\newblock {\em Citations in this document}, 1(6), 1986.

\bibitem[NY90]{naor1990public}
Moni Naor e Moti Yung.
\newblock Public-key cryptosystems provably secure against chosen ciphertext
  attacks.
\newblock Em {\em Proceedings of the twenty-second annual ACM symposium on
  Theory of computing}, p\'{a}ginas 427--437. ACM, 1990.

\bibitem[OS09]{overbeck2009code}
Raphael Overbeck e Nicolas Sendrier.
\newblock Code-based cryptography.
\newblock Em {\em Post-quantum cryptography}, p\'{a}ginas 95--145. Springer,
  2009.

\bibitem[OTD10]{otmani2010cryptanalysis}
Ayoub Otmani, Jean-Pierre Tillich e L{\'e}onard Dallot.
\newblock Cryptanalysis of two {McEliece} cryptosystems based on quasi-cyclic
  codes.
\newblock {\em Mathematics in Computer Science}, 3(2):129--140, 2010.

\bibitem[Pat75]{patterson1975algebraic}
Nicholas~J Patterson.
\newblock The algebraic decoding of goppa codes.
\newblock {\em Information Theory, IEEE Transactions on}, 21(2):203--207, 1975.

\bibitem[Poi00]{pointcheval2000chosen}
David Pointcheval.
\newblock Chosen-ciphertext security for any one-way cryptosystem.
\newblock Em {\em International Workshop on Public Key Cryptography},
  p\'{a}ginas 129--146. Springer, 2000.

\bibitem[Pra62]{prange1962use}
Eugene Prange.
\newblock The use of information sets in decoding cyclic codes.
\newblock {\em IRE Transactions on Information Theory}, 8(5):5--9, 1962.

\bibitem[PT17]{paiva2018improving}
Thales~Bandiera Paiva e Routo Terada.
\newblock Improving the efficiency of a reaction attack on the {QC-MDPC}
  {McEliece} (submetido em outubro de 2017).
\newblock {\em IEICE Transactions on Fundamentals of Electronics,
  Communications and Computer Sciences}, 2017.

\bibitem[Rei85]{reif1985depth}
John~H Reif.
\newblock Depth-first search is inherently sequential.
\newblock {\em Information Processing Letters}, 20(5):229--234, 1985.

\bibitem[RHHM17]{rossi2017side}
M{\'e}lissa Rossi, Mike Hamburg, Michael Hutter e Mark~E Marson.
\newblock A side-channel assisted cryptanalytic attack against {QcBits}.
\newblock Em {\em International Conference on Cryptographic Hardware and
  Embedded Systems}, p\'{a}ginas 3--23. Springer, 2017.

\bibitem[RK87]{rao1987parallel}
V~Nageshwara Rao e Vipin Kumar.
\newblock Parallel depth first search. part i. implementation.
\newblock {\em International Journal of Parallel Programming}, 16(6):479--499,
  1987.

\bibitem[RL09]{ryan2009channel}
William Ryan e Shu Lin.
\newblock {\em Channel codes: classical and modern}.
\newblock Cambridge University Press, 2009.

\bibitem[RS91]{rackoff1991non}
Charles Rackoff e Daniel~R Simon.
\newblock Non-interactive zero-knowledge proof of knowledge and chosen
  ciphertext attack.
\newblock Em {\em Annual International Cryptology Conference}, p\'{a}ginas
  433--444. Springer, 1991.

\bibitem[RS94]{reinefeld1994work}
Alexander Reinefeld e Volker Schnecke.
\newblock Work-load balancing in highly parallel depth-first search.
\newblock Em {\em Scalable High-Performance Computing Conference, 1994.,
  Proceedings of the}, p\'{a}ginas 773--780. IEEE, 1994.

\bibitem[RSA78]{rsa1978rsa}
R.~L. Rivest, A.~Shamir e L.~M. Adleman.
\newblock A method for obtaining digital signatures and public-key
  cryptosystems.
\newblock {\em Communications of the ACM}, 21(2):120--126, 1978.

\bibitem[Sha48]{shannon1948mathematical}
Claude~E Shannon.
\newblock A mathematical theory of communication.
\newblock {\em Bell System Technical Journal}, 27:379--423, 1948.

\bibitem[Sho97]{shor1997poly}
P.W. Shor.
\newblock Polynomial time algorithms for prime factorization and discrete
  logarithms on a quantum computer.
\newblock {\em SIAM Journal on Computing}, 26(5):1481--1509, 1997.

\bibitem[SMR00]{shokrollahi2000using}
Amin Shokrollahi, Chris Monico e Joachim Rosenthal.
\newblock Using low density parity check codes in the {McEliece} cryptosystem.
\newblock Em {\em IEEE International Symposium on Information Theory (ISIT
  2000)}, p\'{a}gina 215, 2000.

\bibitem[SS11]{stehle2011making}
Damien Stehl{\'e} e Ron Steinfeld.
\newblock Making ntru as secure as worst-case problems over ideal lattices.
\newblock Em {\em Annual International Conference on the Theory and
  Applications of Cryptographic Techniques}, p\'{a}ginas 27--47. Springer,
  2011.

\bibitem[Ste88]{stern1988method}
Jacques Stern.
\newblock A method for finding codewords of small weight.
\newblock Em {\em International Colloquium on Coding Theory and Applications},
  p\'{a}ginas 106--113. Springer, 1988.

\bibitem[Wei08]{weisstein2008q}
Eric~W Weisstein.
\newblock q-{Pochhammer} symbol.
\newblock 2008.

\end{thebibliography}
