Recent zbMATH articles in MSC 68Q12https://www.zbmath.org/atom/cc/68Q122021-04-16T16:22:00+00:00WerkzeugAlgorithms for quantum branching programs based on fingerprinting.https://www.zbmath.org/1456.680542021-04-16T16:22:00+00:00"Ablayev, Farid"https://www.zbmath.org/authors/?q=ai:ablaev.farid-m"Vasiliev, Alexander"https://www.zbmath.org/authors/?q=ai:vasiliev.alexander-valeryevichSummary: In the paper we develop a method for constructing quantum algorithms for computing Boolean functions by quantum ordered read-once branching programs (quantum OBDDs). Our method is based on fingerprinting technique and representation of Boolean functions by their characteristic polynomials. We use circuit notation for branching programs for desired algorithms presentation. For several known functions our approach provides optimal QOBDDs. Namely we consider such functions as \(\mathrm{MOD}_m\), \(\mathrm{EQ}_n\), \(\mathrm{Palindrome}_n\), and \(\mathrm{PERM}_n\) (testing whether given Boolean matrix is the Permutation Matrix). We also propose a generalization of our method and apply it to the Boolean variant of the Hidden Subgroup Problem.
For the entire collection see [Zbl 1392.68013].Quantum cryptanalysis in the RAM model: claw-finding attacks on SIKE.https://www.zbmath.org/1456.940902021-04-16T16:22:00+00:00"Jaques, Samuel"https://www.zbmath.org/authors/?q=ai:jaques.samuel"Schanck, John M."https://www.zbmath.org/authors/?q=ai:schanck.john-mSummary: We introduce models of computation that enable direct comparisons between classical and quantum algorithms. Incorporating previous work on quantum computation and error correction, we justify the use of the gate-count and depth-times-width cost metrics for quantum circuits. We demonstrate the relevance of these models to cryptanalysis by revisiting, and increasing, the security estimates for the supersingular isogeny Diffie-Hellman (SIDH) and supersingular isogeny key encapsulation (SIKE) schemes. Our models, analyses, and physical justifications have applications to a number of memory intensive quantum algorithms.
For the entire collection see [Zbl 1428.94004].Physical consequences of \(P \neq\) NP and the density matrix renormalization group annealing conjecture.https://www.zbmath.org/1456.823832021-04-16T16:22:00+00:00"Rodríguez-Laguna, Javier"https://www.zbmath.org/authors/?q=ai:rodriguez-laguna.javier"Santalla, Silvia N."https://www.zbmath.org/authors/?q=ai:santalla.silvia-nQuantum logic gates from Dirac quasiparticles.https://www.zbmath.org/1456.811482021-04-16T16:22:00+00:00"Marino, E. C."https://www.zbmath.org/authors/?q=ai:marino.eduardo-c"Brozeguini, J. C."https://www.zbmath.org/authors/?q=ai:brozeguini.j-cDeterministic quantum annealing expectation-maximization algorithm.https://www.zbmath.org/1456.681592021-04-16T16:22:00+00:00"Miyahara, Hideyuki"https://www.zbmath.org/authors/?q=ai:miyahara.hideyuki"Tsumura, Koji"https://www.zbmath.org/authors/?q=ai:tsumura.koji"Sughiyama, Yuki"https://www.zbmath.org/authors/?q=ai:sughiyama.yukiGeneralized approach for analysing quantum key distribution experiments.https://www.zbmath.org/1456.940982021-04-16T16:22:00+00:00"Maitra, Arpita"https://www.zbmath.org/authors/?q=ai:maitra.arpita"Das, Suvra Sekhar"https://www.zbmath.org/authors/?q=ai:das.suvra-sekharSummary: In this initiative, a generalized approach towards step by step synthesis of quantum key distribution (QKD) experiments is presented. Schematic diagram of the optical setup of any QKD protocol is easily available in the literature whereas step by step synthesis of the circuit needs further attention. For practical implementation, this understanding is necessary. In the current effort, we describe a disciplined methodology to synthesize the optical experimental setup of QKD protocols. This approach can be extended towards any optical experiment. The beam splitter and phase retarders are described in terms of annihilation and creation operators. We represent the polarization of photon in the Fock state basis. We consider two QKD protocols; Passive BB84 with coherent light [\textit{M. Curty} et al., `` Passive preparation of BB84 signal states with coherent light'', Prog. Inform. 8, 57--63 (2011; \url{doi:10.2201/NiiPi.2011.8.7})] and Reference Frame Independent 6-4 QKD (RFI-QKD) [\textit{R. Tannous} et al., ``Demonstration of a 6 state-4 state reference frame independent channel for quantum key distribution'', Preprint, \url{arXiv:1905.09197}) to test the methodology. We observe that this disciplined methodology can successfully describe the experiments. This can be exploited to build a convenient synthesis tool for modelling any optical arrangement for security analysis.
For the entire collection see [Zbl 1428.94012].Quantum attacks against type-1 generalized Feistel ciphers and applications to CAST-256.https://www.zbmath.org/1456.941012021-04-16T16:22:00+00:00"Ni, Boyu"https://www.zbmath.org/authors/?q=ai:ni.boyu"Ito, Gembu"https://www.zbmath.org/authors/?q=ai:ito.gembu"Dong, Xiaoyang"https://www.zbmath.org/authors/?q=ai:dong.xiaoyang"Iwata, Tetsu"https://www.zbmath.org/authors/?q=ai:iwata.tetsuSummary: Generalized Feistel schemes (GFSs) are important components of symmetric ciphers, which have been extensively studied in the classical setting. However, detailed security evaluations of GFS in the quantum setting still remain to be explored.
In this paper, we give improved polynomial-time quantum distinguishers on Type-1 GFS in quantum chosen-plaintext attack (qCPA) setting and quantum chosen-ciphertext attack (qCCA) setting. In qCPA setting, we give a new quantum polynomial-time distinguisher on \((3d-3)\)-round Type-1 GFS with branches \(d\ge 3\), which gains \((d-2)\) more rounds than the previous distinguishers. This leads us to obtain a better key-recovery attack with reduced time complexities by a factor of \(2^{\frac{(d-2)n}{2}}\), where n is the bit length of the branch. We also show a quantum distinguishing attack against \((d^2-d+1)\)-round version in qCCA setting, and this gives a key-recovery attack with much lower time complexity.
In addition, based on a 14-round quantum distinguisher, we give quantum key-recovery attacks on round-reduced CAST-256 block cipher. For the 256-bit key version, we could attack up to 20-round CAST-256 in time \(2^{111}\), which is faster than the quantum brute-force attack by a factor of \(2^{17}\). For the 128-bit key version, we could attack 17 rounds in time \(2^{55.5}\), while the best previous classical or quantum attacks are no more than 16 rounds.
For the entire collection see [Zbl 1428.94012].Efficient quantum algorithms related to autocorrelation spectrum.https://www.zbmath.org/1456.940482021-04-16T16:22:00+00:00"Bera, Debajyoti"https://www.zbmath.org/authors/?q=ai:bera.debajyoti"Maitra, Subhamoy"https://www.zbmath.org/authors/?q=ai:maitra.subhamoy"Tharrmashastha, Sapv"https://www.zbmath.org/authors/?q=ai:tharrmashastha.sapvSummary: In this paper, we propose efficient probabilistic algorithms for several problems regarding the autocorrelation spectrum. First, we present a quantum algorithm that samples from the Walsh spectrum of any derivative of \(f()\). Informally, the autocorrelation coefficient of a Boolean function \(f()\) at some point a measures the average correlation among the values \(f(x)\) and \(f(x\oplus a)\). The derivative of a Boolean function is an extension of autocorrelation to correlation among multiple values of \(f()\). The Walsh spectrum is well-studied primarily due to its connection to the quantum circuit for the Deutsch-Jozsa problem. We extend the idea to ``higher-order Deutsch-Jozsa'' quantum algorithm to obtain points corresponding to large absolute values in the Walsh spectrum of a certain derivative of \(f()\). Further, we design an algorithm to sample the input points according to squares of the autocorrelation coefficients. Finally we provide a different set of algorithms for estimating the square of a particular coefficient or cumulative sum of their squares.
For the entire collection see [Zbl 1428.94012].Quantum algorithms for the approximate \(k\)-list problem and their application to lattice sieving.https://www.zbmath.org/1456.940932021-04-16T16:22:00+00:00"Kirshanova, Elena"https://www.zbmath.org/authors/?q=ai:kirshanova.elena"Mårtensson, Erik"https://www.zbmath.org/authors/?q=ai:martensson.erik"Postlethwaite, Eamonn W."https://www.zbmath.org/authors/?q=ai:postlethwaite.eamonn-w"Moulik, Subhayan Roy"https://www.zbmath.org/authors/?q=ai:moulik.subhayan-roySummary: The Shortest Vector problem (SVP) is one of the mathematical foundations of lattice based cryptography. Lattice sieve algorithms are amongst the foremost methods of solving SVP. The asymptotically fastest known classical and quantum sieves solve SVP in a \(d\)-dimensional lattice in \(2^{\mathsf{c}d+o(d)}\) time steps with \(2^{\mathsf{c}^\prime d+o(d)}\) memory for constants \(c, c^\prime\). In this work, we give various quantum sieving algorithms that trade computational steps for memory.
We first give a quantum analogue of the classical \(k\)-Sieve algorithm [\textit{G. Herold} et al., Lect. Notes Comput. Sci. 10769, 407--436 (2018; Zbl 1439.94033)] in the quantum random access memory (QRAM) model, achieving an algorithm that heuristically solves SVP in \(2^{0.2989d+o(d)}\) time steps using \(2^{0.1395d+o(d)}\) memory. This should be compared to the state-of-the-art algorithm [\textit{T. Laarhoven} [Search problems in cryptography. Eindhoven University of Technology (PhD Thesis) (2015)] which, in the same model, solves SVP in \(2^{0.2653d+o(d)}\) time steps and memory. In the QRAM model these algorithms can be implemented using \(\mathrm{poly}(d)\) width quantum circuits. Secondly, we frame the \(k\)-Sieve as the problem of \(k\)-clique listing in a graph and apply quantum \(k\)-clique finding techniques to the \(k\)-Sieve.
Finally, we explore the large quantum memory regime by adapting parallel quantum search [\textit{R. Beals} et al., Proc. R. Soc. Lond., Ser. A, Math. Phys. Eng. Sci. 469, No. 2153, Article ID 20120686, 20 p. (2013; Zbl 1371.81074)] to the 2-Sieve, and give an analysis in the quantum circuit model. We show how to solve SVP in \(2^{0.1037d+o(d)}\) time steps using \(2^{0.2075d+o(d)}\) quantum memory.
For the entire collection see [Zbl 1428.94008].Quantum attacks without superposition queries: the offline Simon's algorithm.https://www.zbmath.org/1456.940522021-04-16T16:22:00+00:00"Bonnetain, Xavier"https://www.zbmath.org/authors/?q=ai:bonnetain.xavier"Hosoyamada, Akinori"https://www.zbmath.org/authors/?q=ai:hosoyamada.akinori"Naya-Plasencia, María"https://www.zbmath.org/authors/?q=ai:naya-plasencia.maria"Sasaki, Yu"https://www.zbmath.org/authors/?q=ai:sasaki.yu"Schrottenloher, André"https://www.zbmath.org/authors/?q=ai:schrottenloher.andreSummary: In symmetric cryptanalysis, the model of superposition queries has led to surprising results, with many constructions being broken in polynomial time thanks to Simon's period-finding algorithm. But the practical implications of these attacks remain blurry. In contrast, the results obtained so far for a quantum adversary making classical queries only are less impressive.
In this paper, we introduce a new quantum algorithm which uses Simon's subroutines in a novel way. We manage to leverage the algebraic structure of cryptosystems in the context of a quantum attacker limited to classical queries and offline quantum computations. We obtain improved quantum-time/classical-data tradeoffs with respect to the current literature, while using only as much hardware requirements (quantum and classical) as a standard exhaustive search with Grover's algorithm. In particular, we are able to break the Even-Mansour construction in quantum time \(\tilde{O}(2^{n/3})\), with \(O(2^{n/3})\) classical queries and \(O(n^2)\) qubits only. In addition, we improve some previous superposition attacks by reducing the data complexity from exponential to polynomial, with the same time complexity.
Our approach can be seen in two complementary ways: reusing superposition queries during the iteration of a search using Grover's algorithm, or alternatively, removing the memory requirement in some quantum attacks based on a collision search, thanks to their algebraic structure.
We provide a list of cryptographic applications, including the Even-Mansour construction, the FX construction, some Sponge authenticated modes of encryption, and many more.
For the entire collection see [Zbl 1428.94008].Quantum algorithms for testing Boolean functions.https://www.zbmath.org/1456.680552021-04-16T16:22:00+00:00"Floess, Dominik F."https://www.zbmath.org/authors/?q=ai:floess.dominik-f"Andersson, Erika"https://www.zbmath.org/authors/?q=ai:andersson.erika"Hillery, Mark"https://www.zbmath.org/authors/?q=ai:hillery.markSummary: We discuss quantum algorithms, based on the Bernstein-Vazirani algorithm, for finding which variables a Boolean function depends on. There are \(2^n\) possible linear Boolean functions of \(n\) variables; given a linear Boolean function, the Bernstein-Vazirani quantum algorithm can deterministically identify which one of these Boolean functions we are given using just one single function query. The same quantum algorithm can also be used to learn which input variables other types of Boolean functions depend on, with a success probability that depends on the form of the Boolean function that is tested, but does not depend on the total number of input variables. We also outline a procedure to futher amplify the success probability, based on another quantum algorithm, the Grover search.
For the entire collection see [Zbl 1445.68010].