03210nas a2200253 4500008004100000245010000041210006900141260001200210520236500222100001902587700002702606700001702633700001802650700001602668700001702684700001602701700001702717700001802734700001802752700001702770700002102787700002302808856012502831 2020 eng d00aStatus Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process0 aStatus Report on the Second Round of the NIST PostQuantum Crypto c07/20203 a

The National Institute of Standards and Technology is in the process of selecting one or more public-key cryptographic algorithms through a public, competition-like process. The new public-key cryptography standards will specify one or more additional digital signatures, public-key encryption, and key-establishment algorithms to augment Federal Information Processing Standard (FIPS) 186-4, Digital Signature Standard (DSS), as well as NIST Special Publication (SP) 800-56A Revision 3, Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography, and SP 800-56B Revision 2, Recommendation for Pair-Wise Key Establishment Using Integer Factorization Cryptography. It is intended that these algorithms will be capable of protecting sensitive information well into the foreseeable future, including after the advent of quantum computers.

The NIST Post-Quantum Cryptography Standardization Process began in 2017 with 69 candidate algorithms that met both the minimum acceptance criteria and submission requirements. The first round lasted until January 2019, during which candidate algorithms were evaluated based on their security, performance, and other characteristics. NIST selected 26 algorithms to advance to the second round for more analysis. This report describes the evaluation and selection process, based on public feedback and internal review, of the second-round candidates. The report summarizes the 26 second-round candidate algorithms and identifies those selected to move forward to the third round of the competition. The third-round finalist public-key encryption and key-establishment algorithms are Classic McEliece, CRYSTALS-KYBER, NTRU, and SABER. The third-round finalists for digital signatures are CRYSTALS-DILITHIUM, FALCON, and Rainbow. These finalists will be considered for standardization at the end of the third round. In addition, eight alternate candidate algorithms will also advance to the third round: BIKE, FrodoKEM, HQC, NTRU Prime, SIKE, GeMSS, Picnic, and SPHINCS+. These additional candidates are still being considered for standardization, although this is unlikely to occur at the end of the third round. NIST hopes that the announcement of these finalists and additional candidates will serve to focus the cryptographic community’s attention during the next round.

1 aAlagic, Gorjan1 aAlperin-Sheriff, Jacob1 aApon, Daniel1 aCooper, David1 aDang, Quynh1 aKelsey, John1 aLiu, Yi-Kai1 aMiller, Carl1 aMoody, Dustin1 aPeralta, Rene1 aPerlner, Ray1 aRobinson, Angela1 aSmith-Tone, Daniel uhttps://www.quics.umd.edu/publications/status-report-second-round-nist-post-quantum-cryptography-standardization-process02754nas a2200229 4500008004100000245009900041210006900140520205300209100001902262700002402281700001302305700001502318700001302333700001702346700001402363700001602377700001602393700001702409700001902426700001602445856006302461 2019 eng d00aStatus Report on the First Round of the NIST Post-Quantum Cryptography Standardization Process0 aStatus Report on the First Round of the NIST PostQuantum Cryptog3 a

The National Institute of Standards and Technology is in the process of selecting one or more
public-key cryptographic algorithms through a public competition-like process. The new publickey cryptography standards will specify one or more additional digital signature, public-key
encryption, and key-establishment algorithms to augment FIPS 186-4, Digital Signature Standard
(DSS), as well as special publications SP 800-56A Revision 2, Recommendation for Pair-Wise
Key Establishment Schemes Using Discrete Logarithm Cryptography, and SP 800-56B,
Recommendation for Pair-Wise Key-Establishment Schemes Using Integer Factorization. It is
intended that these algorithms will be capable of protecting sensitive information well into the
foreseeable future, including after the advent of quantum computers.
In November 2017, 82 candidate algorithms were submitted to NIST for consideration. Among
these, 69 met both the minimum acceptance criteria and our submission requirements, and were
accepted as First-Round Candidates on Dec. 20, 2017, marking the beginning of the First Round
of the NIST Post-Quantum Cryptography Standardization Process. This report describes the
evaluation criteria and selection process, based on public feedback and internal review of the
first-round candidates, and summarizes the 26 candidate algorithms announced on January 30,
2019 for moving forward to the second round of the competition. The 17 Second-Round
Candidate public-key encryption and key-establishment algorithms are BIKE, Classic McEliece,
CRYSTALS-KYBER, FrodoKEM, HQC, LAC, LEDAcrypt (merger of LEDAkem/LEDApkc),
NewHope, NTRU (merger of NTRUEncrypt/NTRU-HRSS-KEM), NTRU Prime, NTS-KEM,
ROLLO (merger of LAKE/LOCKER/Ouroboros-R), Round5 (merger of Hila5/Round2), RQC,
SABER, SIKE, and Three Bears. The 9 Second-Round Candidates for digital signatures are
CRYSTALS-DILITHIUM, FALCON, GeMSS, LUOV, MQDSS, Picnic, qTESLA, Rainbow,
and SPHINCS+.

1 aAlagic, Gorjan1 aAlperin-Sheriff, J.1 aApon, D.1 aCooper, D.1 aDang, Q.1 aMiller, Carl1 aMoody, D.1 aPeralta, R.1 aPerlner, R.1 aRobinson, A.1 aSmith-Tone, D.1 aLiu, Yi-Kai uhttps://nvlpubs.nist.gov/nistpubs/ir/2019/NIST.IR.8240.pdf01811nas a2200145 4500008004100000245009400041210006900135260001500204520133900219100001901558700001601577700001601593700001901609856003701628 2017 eng d00aSuper-polynomial and exponential improvements for quantum-enhanced reinforcement learning0 aSuperpolynomial and exponential improvements for quantumenhanced c2017/12/123 a

Recent work on quantum machine learning has demonstrated that quantum computers can offer dramatic improvements over classical devices for data mining, prediction and classification. However, less is known about the advantages using quantum computers may bring in the more general setting of reinforcement learning, where learning is achieved via interaction with a task environment that provides occasional rewards. Reinforcement learning can incorporate data-analysis-oriented learning settings as special cases, but also includes more complex situations where, e.g., reinforcing feedback is delayed. In a few recent works, Grover-type amplification has been utilized to construct quantum agents that achieve up-to-quadratic improvements in learning efficiency. These encouraging results have left open the key question of whether super-polynomial improvements in learning times are possible for genuine reinforcement learning problems, that is problems that go beyond the other more restricted learning paradigms. In this work, we provide a family of such genuine reinforcement learning tasks. We construct quantum-enhanced learners which learn super-polynomially, and even exponentially faster than any classical reinforcement learning model, and we discuss the potential impact our results may have on future technologies.

1 aDunjko, Vedran1 aLiu, Yi-Kai1 aWu, Xingyao1 aTaylor, J., M. uhttps://arxiv.org/abs/1710.1116001619nas a2200133 4500008004100000245007600041210006900117260001500186300001000201490001200211520120900223100001601432856003701448 2014 eng d00aSingle-shot security for one-time memories in the isolated qubits model0 aSingleshot security for onetime memories in the isolated qubits  c2014/02/01 a19-360 vPart II3 a One-time memories (OTM's) are simple, tamper-resistant cryptographic devices, which can be used to implement sophisticated functionalities such as one-time programs. Can one construct OTM's whose security follows from some physical principle? This is not possible in a fully-classical world, or in a fully-quantum world, but there is evidence that OTM's can be built using "isolated qubits" -- qubits that cannot be entangled, but can be accessed using adaptive sequences of single-qubit measurements. Here we present new constructions for OTM's using isolated qubits, which improve on previous work in several respects: they achieve a stronger "single-shot" security guarantee, which is stated in terms of the (smoothed) min-entropy; they are proven secure against adversaries who can perform arbitrary local operations and classical communication (LOCC); and they are efficiently implementable. These results use Wiesner's idea of conjugate coding, combined with error-correcting codes that approach the capacity of the q-ary symmetric channel, and a high-order entropic uncertainty relation, which was originally developed for cryptography in the bounded quantum storage model. 1 aLiu, Yi-Kai uhttp://arxiv.org/abs/1402.0049v201932nas a2200169 4500008004100000245005700041210005500098260001500153300001200168520144400180100002701624700002101651700001601672700002101688700001601709856003701725 2012 eng d00aA Spectral Algorithm for Latent Dirichlet Allocation0 aSpectral Algorithm for Latent Dirichlet Allocation c2012/04/30 a193-2143 a The problem of topic modeling can be seen as a generalization of the clustering problem, in that it posits that observations are generated due to multiple latent factors (e.g., the words in each document are generated as a mixture of several active topics, as opposed to just one). This increased representational power comes at the cost of a more challenging unsupervised learning problem of estimating the topic probability vectors (the distributions over words for each topic), when only the words are observed and the corresponding topics are hidden. We provide a simple and efficient learning procedure that is guaranteed to recover the parameters for a wide class of mixture models, including the popular latent Dirichlet allocation (LDA) model. For LDA, the procedure correctly recovers both the topic probability vectors and the prior over the topics, using only trigram statistics (i.e., third order moments, which may be estimated with documents containing just three words). The method, termed Excess Correlation Analysis (ECA), is based on a spectral decomposition of low order moments (third and fourth order) via two singular value decompositions (SVDs). Moreover, the algorithm is scalable since the SVD operations are carried out on $k\times k$ matrices, where $k$ is the number of latent factors (e.g. the number of topics), rather than in the $d$-dimensional observed space (typically $d \gg k$). 1 aAnandkumar, Animashree1 aFoster, Dean, P.1 aHsu, Daniel1 aKakade, Sham, M.1 aLiu, Yi-Kai uhttp://arxiv.org/abs/1204.6703v4