[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Complete analysis of Simon’s quantum algorithm with additional collisions

  • Published:
Quantum Information Processing Aims and scope Submit manuscript

Abstract

Simon’s algorithm, an exponential speedup quantum algorithm for recovering period, has been widely applied to symmetric cryptography. At Crypto 2016, Kaplan et al. showed the effect of additional collisions on the success probability of Simon’s algorithm, which led to a better analysis of previous applications. In this paper, we provide several new results of Simon’s algorithm. Firstly, we present the composing form of additional collisions and reveal the exact relationship between additional collisions and measurement outcomes for the first time. Specifically, all probabilities of observed measurements are completely depended on the number of additional collisions. Our findings shed new light on how to estimate the success probability of Simon’s algorithm with additional collisions and point out somewhere unreasonable in the work by Kaplan et al. Finally, we give the trade-off between the success probability and the number of runs of the subroutine afresh. For a random function, 4n repetitions of subroutine will ensure the success probability exponentially close to 1.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Anand, M.V., Targhi, E.E., Tabia, G.N., Takagi, T.: Post-Quantum Security of the CBC, CFB, OFB, CTR, and XTS Modes of Operation, Post-quantum Cryptography 2016, vol. 9606, p. 44. Springer, Cham (2016)

  2. Boneh D., Zhandry M.: Secure signatures and chosen ciphertext security in a quantum computing world. In: Advances in Cryptology—CRYPTO 2013, vol. 8043, p. 361. Springer, Berlin (2013)

  3. Bernstein, D.J.: Introduction to post-quantum cryptography, Post-quantum cryptography, pp. 1–14. Springer, Berlin (2009)

  4. Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26, 1484 (1997)

    Article  MathSciNet  Google Scholar 

  5. Takagi, T., Peyrin, T.: Advances in Cryptology—ASIACRYPT 2017. Springer, Cham (2017)

    Book  Google Scholar 

  6. NIST: Post-Quantum Cryptography, https://csrc.nist.gov/Projects/Post-Quantum-Cryptography. (2017). Accessed 08 Jan 2019

  7. Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, vol. 212. ACM (1996)

  8. Boneh, D., Dagdelen, O., Fischlin, M., Lehmann, A., Schaffner, C., Zhandry, M.: Random oracles in a quantum world. In: Advances in Cryptology—ASIACRYPT 2011, vol. 41. Springer, Cham (2017)

  9. Boneh, D., Zhandry, M.: Quantum-secure message authentication codes. In: Advances in Cryptology—EUROCRYPT 2013, vol. 592. Springer, Berlin (2013)

  10. Damgard I., Funder J., Nielsen J. B., Salvail L.: Superposition attacks on cryptographic protocols. In: ICITS 2013, vol. 142 (2013)

  11. Kuwakado, H., Morii, M.: Quantum distinguisher between the 3-round Feistel cipher and the random permutation. Int. Symp. Inf. Theory Appl. 41, 2682 (2010)

    Google Scholar 

  12. Kuwakado, H., Morii, M.: Security on the quantum-type Even–Mansour cipher. In: International Symposium Information Theory and its Applications. vol. 312 (2012)

  13. Simon, D.R.: On the power of quantum computation. SIAM J. Comput. 1474, 26 (1997)

    MathSciNet  Google Scholar 

  14. Kaplan, M., Leurent, G., Leverrier, A., Naya-Plasencia, M.: Breaking symmetric cryptosystems using quantum period finding. In: Advances in Cryptology—CRYPTO 2016, vol. 207. Springer, Berlin (2016)

  15. Alagic, G., Russell, A.: Quantum-secure symmetric-key cryptography based on hidden shifts. In: Advances in Cryptology—EUROCRYPT 2017, vol. 65. Springer, Berlin (2015)

  16. Leander, G., May, A.: Grover meets simon—quantumly attacking the FX-construction. In: Advances in Cryptology—ASIACRYPT 2017, vol. 161. Springer, Cham (2017)

  17. Santoli, T., Christian, S.: Using Simon’s algorithm to attack symmetric-key cryptographic primitives. Quantum Inf. Comput. 17, 65 (2017)

    MathSciNet  Google Scholar 

  18. Dong, X., Wang, X.: Quantum key-recovery attack on Feistel structures. SCI. CHINA Inf. Sci. 61, 240 (2018)

    Google Scholar 

  19. Shi, T.R., Jin, C.H., Guan, J.: Collision attacks against AEZ-PRF for authenticated encryption AEZ. China Commun. 15, 46 (2018)

    Article  Google Scholar 

Download references

Acknowledgements

This work was supported by National Natural Science Foundation of China (Grant Nos. 61572516, 61602514, 61802437 and 61802438).

Author information

Authors and Affiliations

  1. PLA SSF Information and Engineering University, No. 62, Science Avenue, Zhengzhou, People’s Republic of China

    Tai-Rong Shi, Chen-Hui Jin, Bin Hu, Jie Guan, Jing-Yi Cui & Sen-Peng Wang

Authors
  1. Tai-Rong Shi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Chen-Hui Jin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Bin Hu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Jie Guan
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Jing-Yi Cui
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Sen-Peng Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tai-Rong Shi.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendices

The proof of Theorem 2

For an arbitrary f(z) that \(|{{\varOmega }_{z}}|=2m\), we classify u into \({{2}^{m}}\) categories by the orthogonal relationship with t in \({{\varOmega }_{z}}\). Denoting them as \({{u}^{j}}(0\le j\le {{2}^{m}}-1)\), we have

$$\begin{aligned} p[{{u}^{j}}\text { is observed}]&=p[u\text { is observed,}u\in {{u}^{j}}]\times |{{u}^{j}}| \end{aligned}$$
(13)
$$\begin{aligned}&=\frac{|{{u}^{j}}|}{{{2}^{n-2}} (|{{\varOmega }_{z}}|+2)}{{\left( 1+\sum \limits _{t\in \varOmega _{z}^{0}}{{{(-1)}^{{{u}^{j}}\cdot t}}}\right) }^{2}} \end{aligned}$$
(14)

where \(|{{u}^{j}}|=\frac{{{2}^{n-1}}}{{{2}^{m}}}\) and \(p[u\text { is observed,}u\in {{u}^{j}}]\) is from Eq. (4). If \(t\in {{\varOmega }_{z}}\), the probability of \(u\cdot t=0\) is

$$\begin{aligned} p\left[ u\cdot t=0|t\in {{\varOmega }_{z}} \right]&=\sum \limits _{j=0}^{{{2}^{m}}-1}{p[{{u}^{j}}\text { is observed}]\times p[{{u}^{j}}\cdot t=0|t\in {{\varOmega }_{z}}]} \end{aligned}$$
(15)
$$\begin{aligned}&=\sum \limits _{j=0}^{{{2}^{m}}-1}\frac{|{{u}^{j}}|}{{{2}^{n-2}}(|{{\varOmega }_{z}}|+2)}{{\left( 1+\sum \limits _{t\in \varOmega _{z}^{0}}{{{(-1)}^{{{u}^{j}}\cdot t}}}\right) }^{2}}\nonumber \\&\quad \times \frac{\#\{t:{{u}^{j}}\cdot t=0,t\in {{\varOmega }_{z}}\}}{|{{\varOmega }_{z}}|} \end{aligned}$$
(16)
$$\begin{aligned}&{=}\frac{1}{{{2}^{m}}(m+1)m}\sum \limits _{j=0}^{{{2}^{m}}-1}{{(2\times \#\{t:{{u}^{j}}\cdot t=0,t\in \varOmega _{z}^{0}\}{-}(m{-}1))}^{2}} \nonumber \\&\quad \times \#\{t:{{u}^{j}}\cdot t=0,t\in \varOmega _{z}^{0}\} \end{aligned}$$
(17)

where

$$\begin{aligned} \sum \limits _{t\in \varOmega _{z}^{0}}{{{(-1)}^{{{u}^{j}}\cdot t}}}&=\#\{t:{{u}^{j}}\cdot t=0,t\in \varOmega _{z}^{0}\}-\#\{t:{{u}^{j}}\cdot t=1,t\in \varOmega _{z}^{0}\} \end{aligned}$$
(18)
$$\begin{aligned}&=2\times \#\{t:{{u}^{j}}\cdot t=0,t\in \varOmega _{z}^{0}\}-m \end{aligned}$$
(19)

and \(\#\{t:{{u}^{j}}\cdot t=0,t\in {{\varOmega }_{z}}\}=2\times \#\{t:{{u}^{j}}\cdot t=0,t\in \varOmega _{z}^{0}\}\).

If \(t\in {{\varPhi }_{z}}\), the probability of \(ut=0\) is

$$\begin{aligned} p\left[ u\cdot t=0|t\in {{\varPhi }_{z}} \right]&=\sum \limits _{j=0}^{{{2}^{m}}-1}{p[{{u}^{j}}\text { is observed}]\times p[{{u}^{j}}\cdot t=0|t\in {{\varPhi }_{z}}]} \end{aligned}$$
(20)
$$\begin{aligned}&=\sum \limits _{j=0}^{{{2}^{m}}-1}{p[{{u}^{j}}\text { is observed}]\times \frac{\#\{t:{{u}^{j}}\cdot t=0,t\in {{\varPhi }_{z}}\}}{|{{\varPhi }_{z}}|}} \end{aligned}$$
(21)
$$\begin{aligned}&=\sum \limits _{j=0}^{{{2}^{m}}-1}p[{{u}^{j}}\text { is observed}] \nonumber \\&\quad \times \frac{{{2}^{n-1}}-1-\#\{t:{{u}^{j}}\cdot t=0,t\in {{\varOmega }_{z}}\}}{{{2}^{n}}-|{{\varOmega }_{z}}|} \end{aligned}$$
(22)

Since

$$\begin{aligned} \frac{{{2}^{n-1}}-1-2m}{{{2}^{n}}-2m}\le \frac{{{2}^{n-1}}-1-\#\{t:{{u}^{j}}\cdot t=0,t\in {{\varOmega }_{z}}\}}{{{2}^{n}}-2m}\le \frac{{{2}^{n-1}}-1}{{{2}^{n}}-2m} \end{aligned}$$

When m is small,

$$\begin{aligned} \frac{{{2}^{n-1}}-1-\#\{t:{{u}^{j}}\cdot t=0,t\in {{\varOmega }_{z}}\}}{{{2}^{n}}-2m}\approx \frac{1}{2} \end{aligned}$$

Hence,

$$\begin{aligned} p\left[ u\cdot t=0|t\in {{\varPhi }_{z}} \right] \approx \frac{1}{2}\sum \limits _{j}{p[{{u}^{j}}\text { is observed}]}=\frac{1}{2} \end{aligned}$$

.

The probability distribution \({{u}_{2}}t\) when \(\left| {{\varOmega }_{z}} \right| =4\)

For \(({{u}_{2}},f({{z}_{2}}))\) that \(\varOmega _{{{z}_{2}}}^{0}=\{{{t}_{0}},{{t}_{1}}\}\). We can classify the measurement outcomes \({{u}_{2}}\) into \({{2}^{2}}\) categories by the orthogonal relationship with \(\{{{t}_{0}},{{t}_{1}}\}\). Denoting them as \(u_{2}^{j}(0\le j\le 3)\), then we have combined Tables 7 and 8, and the total probability distribution of \({{u}_{2}}t\) is shown as:

$$\begin{aligned}&p\left[ {{u}_{2}}\cdot t=0|t\in {{\varOmega }_{{{z}_{2}}}} \right] =\sum \limits _{j}{p[u_{2}^{j}\text { is observed}]\times p[u_{2}^{j}\cdot t=0|t\in {{\varOmega }_{{{z}_{2}}}}]} \end{aligned}$$
(23)
$$\begin{aligned}&=\frac{3}{4}\times 1+\frac{1}{12}\times \frac{1}{2}\times 2+\frac{1}{12}\times 0 \end{aligned}$$
(24)
$$\begin{aligned}&=\frac{5}{6} \nonumber \\&p\left[ {{u}_{2}}\cdot t=0|t\in {{\varPhi }_{{{z}_{2}}}} \right] =\sum \limits _{j}{p[u_{2}^{j}\text { is observed}]\times p[u_{2}^{j}\cdot t=0|t\in {{\varPhi }_{{{z}_{2}}}}]}\approx \frac{1}{2} \end{aligned}$$
(25)
Table 7 The probability of being observed in different \(u_{2}^{j}\) when \(|{{\varOmega }_{{{z}_{2}}}}|=4\)
Full size table
Table 8 The distribution of \(u_{2}^{j}\cdot t\) when \(|{{\varOmega }_{{{z}_{2}}}}|=4\)
Full size table

Thus,

$$\begin{aligned} \underset{t\in {{\{0,1\}}^{n}}\backslash \{0,s\}}{\mathop {\max }}\,p[{{u}_{2}}\cdot t=0]=\underset{t\in \{{{\varOmega }_{{{z}_{2}}}},{{\varPhi }_{{{z}_{2}}}}\}}{\mathop {\max }}\,p[{{u}_{2}}\cdot t=0]=p[{{u}_{2}}\cdot t=0|t\in {{\varOmega }_{{{z}_{2}}}}]=\frac{5}{6}. \end{aligned}$$

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Shi, TR., Jin, CH., Hu, B. et al. Complete analysis of Simon’s quantum algorithm with additional collisions. Quantum Inf Process 18, 334 (2019). https://doi.org/10.1007/s11128-019-2444-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s11128-019-2444-x

Keywords

Search

Navigation