The complexity of public-key cryptography. (English) Zbl 1512.94062
Lindell, Yehuda (ed.), Tutorials on the foundations of cryptography. Dedicated to Oded Goldreich. Cham: Springer. Inf. Secur. Cryptogr., 45-77 (2017).
Summary: We survey the computational foundations for public-key cryptography. We discuss the computational assumptions that have been used as bases for publickey encryption schemes, and the types of evidence we have for the veracity of these assumptions.
For the entire collection see [Zbl 1411.94003].
For the entire collection see [Zbl 1411.94003].
MSC:
| 94A60 | Cryptography |
Keywords:
block cipher; quantum algorithm; discrete logarithm; stream cipher; discrete logarithm problemReferences:
| [1] | Cryptography today: Memorandum on Suite B Cryptography, 2015. Retrievedon2/29/16fromhttps://www.nsa.gov/ia/programs/ suiteb_cryptography/ |
| [2] | D. Achlioptas and A. Coja-Oghlan. Algorithmic barriers from phase transitions. In49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, pages 793-802, 2008. |
| [3] | L. M. Adleman, J. DeMarrais, and M. A. Huang. A subexponential algorithm for discrete logarithms over hyperelliptic curves of large genus overGF(q). Theoretical Computer Science, 226(1-2):7-18, 1999. · Zbl 1007.11080 |
| [4] | D. Aharonov and O. Regev. Lattice problems inNP∩coNP.J. ACM, 52(5):749-765, 2005. Preliminary version in FOCS 2004. · Zbl 1286.68218 |
| [5] | M. Ajtai. Generating hard instances of lattice problems (extended abstract). InTwenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 99-108, 1996. · Zbl 0921.11071 |
| [6] | M. Ajtai and C. Dwork. A public-key cryptosystem with worst-case/averagecase equivalence. InProceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, pages 284-293, 1997. · Zbl 0962.68055 |
| [7] | M. Alekhnovich. More on average case vs approximation complexity.Computational Complexity, 20(4):755-786, 2011. Published posthumously. Preliminary version in FOCS ’03. · Zbl 1242.68109 |
| [8] | B. Applebaum. Pseudorandom generators with long stretch and low locality from random local one-way functions. InProceedings of the 44th Symposium on Theory of Computing Conference, STOC, pages 805-816, 2012. · Zbl 1286.65007 |
| [9] | B. Applebaum. The cryptographic hardness of random local functions - survey.IACR Cryptology ePrint Archive, 2015:165, 2015. · Zbl 1315.94049 |
| [10] | B. Applebaum, B. Barak, and A. Wigderson. Public-key cryptography from different assumptions. InProceedings of the 42nd ACM Symposium on Theory of Computing, STOC, pages 171-180, 2010. · Zbl 1293.94052 |
| [11] | G. Asharov and G. Segev. Limits on the power of indistinguishability obfuscation and functional encryption. InFoundations of Computer Science (FOCS), pages 191-209, 2015. · Zbl 1356.94048 |
| [12] | B. Barak. Structure vs. combinatorics in computational complexity.Bulletin of the European Association for Theoretical Computer Science, 112, 2014. Survey, also posted on Windows on Theory blog. · Zbl 1409.68132 |
| [13] | B. Barak. Hopes, fears, and software obfuscation.Commun. ACM, 59(3):88- 96, 2016. |
| [14] | B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. P. Vadhan, and K. Yang. On the (im)possibility of obfuscating programs.J. ACM, 59(2):6, 2012. · Zbl 1281.68118 |
| [15] | B. Barak, G. Kindler, and D. Steurer. On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction. InInnovations in Theoretical Computer Science, ITCS ’13, pages 197-214, 2013. · Zbl 1361.68104 |
| [16] | B. Barak and M. Mahmoody-Ghidary. Lower bounds on signatures from symmetric primitives. In48th Annual IEEE Symposium on Foundations of Computer Science (FOCS, pages 680-688, 2007. |
| [17] | B. Barak and M. Mahmoody-Ghidary.Merkle puzzles are optimal - an O(n2)-query attack on any key exchange from a random oracle. InAdvances in Cryptology - CRYPTO 2009, Springer (LNCS 5677), pages 374-390, 2009. · Zbl 1252.94046 |
| [18] | B. Barak and D. Steurer. Sum-of-squares proofs and the quest toward optimal algorithms, 2014. · Zbl 1373.68253 |
| [19] | E. Ben-Sasson, I. Ben-Tov, I. Damgård, Y. Ishai, and N. Ron-Zewi. On public key encryption from noisy codewords. InPublic-Key Cryptography - PKC 2016, Springer pages 417-446, 2016. · Zbl 1395.94267 |
| [20] | D. J. Bernstein. The Salsa20 family of stream ciphers. InNew stream cipher designs, Springer, pages 84-97, 2008. |
| [21] | G. Bertoni, J. Daemen, M. Peeters, and G. Van Assche. The Keccak SHA-3 submission.Submission to NIST (Round 3), 6(7):16, 2011. |
| [22] | J.-F. Biasse, D. Jao, and A. Sankar. A quantum algorithm for computing isogenies between supersingular elliptic curves. InProgress in Cryptology- INDOCRYPT 2014, pages 428-442. Springer, 2014. · Zbl 1337.94024 |
| [23] | E. Biham, Y. J. Goren, and Y. Ishai. Basing weak public-key cryptography on strong one-way functions. InTheory of Cryptography, Fifth Theory of Cryptography Conference, TCC 2008, pages 55-72, 2008. · Zbl 1162.94339 |
| [24] | A. Blum, M. L. Furst, M. J. Kearns, and R. J. Lipton. Cryptographic primitives based on hard learning problems. InAdvances in Cryptology - CRYPTO ’93, pages 278-291, 1993. · Zbl 0870.94021 |
| [25] | A. Blum, A. Kalai, and H. Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model.J. ACM, 50(4):506-519, 2003. Preliminary version in STOC ’00. · Zbl 1325.68114 |
| [26] | A. Bogdanov and Y. Qiao. On the security of Goldreich’s one-way function. Computational Complexity, 21(1):83-127, 2012. · Zbl 1280.68092 |
| [27] | B. Bollob´as and P. Erd¨os. Cliques in random graphs. InMathematical Proceedings of the Cambridge Philosophical Society, volume 80, pages 419- 427. Cambridge Univ. Press, 1976. · Zbl 0344.05155 |
| [28] | Z. Brakerski, A. Langlois, C. Peikert, O. Regev, and D. Stehl´e. Classical hardness of learning with errors. InProceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pages 575-584. ACM, 2013. · Zbl 1293.68159 |
| [29] | Z. Brakerski and V. Vaikuntanathan. Efficient fully homomorphic encryption from (standard) LWE. InIEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS, pages 97-106, 2011. · Zbl 1292.94038 |
| [30] | J. Buresh-Oppenheim. On the TFNP complexity of factoring, 2006. |
| [31] | D. Cash, D. Hofheinz, E. Kiltz, and C. Peikert. Bonsai trees, or how to delegate a lattice basis.J. Cryptology, 25(4):601-639, 2012. · Zbl 1277.94017 |
| [32] | L. Chen, S. Jordan, Y.-K. Liu, D. Moody, R. Peralta, R. Perlner, and D. Smith-Tone.Report on post-quantum cryptography.National Institute of Standards and Technology Internal Report, 8105, 2016.Available onhttp://csrc.nist.gov/publications/drafts/ nistir-8105/nistir_8105_draft.pdf. |
| [33] | A. Childs, D. Jao, and V. Soukharev. Constructing elliptic curve isogenies in quantum subexponential time.Journal of Mathematical Cryptology, 8(1):1- 29, 2014. · Zbl 1283.81046 |
| [34] | J. Cook, O. Etesami, R. Miller, and L. Trevisan. Goldreich’s one-way function candidate and myopic backtracking algorithms. InTheory of Cryptography, pages 521-538. Springer, 2009. · Zbl 1213.94092 |
| [35] | D. Coppersmith, A. M. Odlzyko, and R. Schroeppel. Discrete logarithms in GF(p).Algorithmica, 1(1-4):1-15, 1986. · Zbl 0631.12010 |
| [36] | N. T. Courtois, M. Daum, and P. Felke. On the security of HFE, HFEv- and Quartz. InPublic Key CryptographyPKC 2003, pages 337-350. Springer, 2003. · Zbl 1033.94518 |
| [37] | J. M. Couveignes.Hard homogeneous spaces.IACR Cryptology ePrint Archive, 2006:291, 2006. |
| [38] | R. Cramer, L. Ducas, C. Peikert, and O. Regev. Recovering short generators of principal ideals in cyclotomic rings.IACR Cryptology ePrint Archive, 2015:313, 2015. · Zbl 1371.94630 |
| [39] | J. Daemen and V. Rijmen.The design of Rijndael: AES-the advanced encryption standard. Springer Science & Business Media, 2013. · Zbl 1065.94005 |
| [40] | W. Diffie and M. E. Hellman. Multiuser cryptographic techniques. InProceedings of the June 7-10, 1976, National Computer Conference and Exposition, pages 109-112. ACM, 1976. |
| [41] | W. Diffie and M. E. Hellman. New directions in cryptography.IEEE Transactions on Information Theory, 22(6):644-654, 1976. · Zbl 0435.94018 |
| [42] | J. H. Ellis. The history of non-secret encryption.Cryptologia, 23(3):267- 273, 1999. |
| [43] | U. Feige, J. H. Kim, and E. Ofek. Witnesses for non-satisfiability of dense random 3CNF formulas. In47th Annual IEEE Symposium on Foundations of Computer Science (FOCS, pages 497-508, 2006. |
| [44] | E. Friedgut.Sharp thresholds of graph properties, and thek-SAT problem.Journal of the American Mathematical Society, 12(4):1017-1054, 1999. With an appendix by Jean Bourgain. · Zbl 0932.05084 |
| [45] | S. Garg, C. Gentry, S. Halevi, M. Raykova, A. Sahai, and B. Waters. Candidate indistinguishability obfuscation and functional encryption for all circuits. InFOCS, pages 40-49, 2013. · Zbl 1348.94048 |
| [46] | S. Garg, O. Pandey, A. Srinivasan, and M. Zhandry.Breaking the sub-exponential barrier in Obfustopia.IACR Cryptology ePrint Archive, 2016:102, 2016. · Zbl 1394.94932 |
| [47] | C. Gentry. Fully homomorphic encryption using ideal lattices. InSTOC, pages 169-178, 2009. · Zbl 1304.94059 |
| [48] | O. Goldreich.Lessons from Kant: On knowledge, morality, and beauty.Essay available onhttp://www.wisdom.weizmann.ac.il/ ˜oded/on-kant.html |
| [49] | O. Goldreich.On cryptographic assumptions.Short note available on http://www.wisdom.weizmann.ac.il/˜oded/on-assumptions.html |
| [50] | O. Goldreich. On intellectual and instrumental values in science. Essay available on http://www.wisdom.weizmann.ac.il/˜oded/on-values.html |
| [51] | O. Goldreich.On post-modern cryptography.Short note available on http://www.wisdom.weizmann.ac.il/˜oded/on-pmc.html,revised on 2012. |
| [52] | O. Goldreich.On quantum computing.Essay available on http://www.wisdom.weizmann.ac.il/˜oded/on-qc.html · Zbl 1291.05195 |
| [53] | O.Goldreich.Onscientificevaluationanditsrelationto understanding,imagination,andtaste.Essayavailableon http://www.wisdom.weizmann.ac.il/˜oded/on-taste.html |
| [54] | O. Goldreich. On the philosophical basis of computational theories. Essay available on http://www.wisdom.weizmann.ac.il/˜oded/on-qc3.html |
| [55] | O. Goldreich.The Foundations of Cryptography - Volume 1, Basic Techniques. Cambridge University Press, 2001. · Zbl 1007.94016 |
| [56] | O. Goldreich.The Foundations of Cryptography - Volume 2, Basic Applications. Cambridge University Press, 2004. · Zbl 1068.94011 |
| [57] | O. Goldreich. Candidate one-way functions based on expander graphs. In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation - In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman, pages 76-87. 2011. Original version published as ECCC TR00-090 in 2000. · Zbl 1306.94056 |
| [58] | O. Goldreich, S. Goldwasser, and S. Halevi. Public-key cryptosystems from lattice reduction problems. InAdvances in Cryptology - CRYPTO ’97, 17th Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 1997, Proceedings, pages 112-131, 1997. · Zbl 0889.94011 |
| [59] | O. Goldreich, S. Goldwasser, and S. Micali. How to construct random functions.J. ACM, 33(4):792-807, 1986. · Zbl 0596.65002 |
| [60] | O. Goldreich, H. Krawczyk, and M. Luby. On the existence of pseudorandom generators.SIAM J. Comput., 22(6):1163-1175, 1993. Preliminary versions in CRYPTO ’88 and FOCS ’88. · Zbl 0795.94011 |
| [61] | O. Goldreich and E. Kushilevitz. A perfect zero-knowledge proof system for a problem equivalent to the discrete logarithm.J. Cryptology, 6(2):97-116, 1993. · Zbl 0783.68039 |
| [62] | O. Goldreich and L. A. Levin. A hard-core predicate for all one-way functions. InProceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 25-32, 1989. |
| [63] | O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game or a completeness theorem for protocols with honest majority. InProceedings of the 19th Annual ACM Symposium on Theory of Computing, pages 218-229, 1987. |
| [64] | S. Goldwasser and S. Micali. Probabilistic encryption and how to play mental poker keeping secret all partial information. InProceedings of the 14th Annual ACM Symposium on Theory of Computing, pages 365-377, 1982. |
| [65] | W. Gowers. An almost m-wise independent random permutation of the cube. Combinatorics, Probability and Computing, 5(02):119-130, 1996. · Zbl 0865.60056 |
| [66] | G. R. Grimmett and C. J. McDiarmid. On colouring random graphs. InMathematical Proceedings of the Cambridge Philosophical Society, volume 77, pages 313-324. Cambridge Univ Press, 1975. · Zbl 0297.05112 |
| [67] | J. Håstad, R. Impagliazzo, L. A. Levin, and M. Luby. A pseudorandom generator from any one-way function.SIAM J. Comput., 28(4):1364-1396, 1999. Preliminary versions in STOC ’89 and STOC ’90. · Zbl 0940.68048 |
| [68] | J. Hoffstein, J. Pipher, and J. H. Silverman. Ntru: A ring-based public key cryptosystem. InAlgorithmic number theory, pages 267-288. Springer, 1998. · Zbl 1067.94538 |
| [69] | S. Hoory, N. Linial, and A. Wigderson. Expander graphs and their applications.Bulletin of the American Mathematical Society, 43(4):439-561, 2006. · Zbl 1147.68608 |
| [70] | S. Hoory, A. Magen, S. Myers, and C. Rackoff. Simple permutations mix well.Theor. Comput. Sci., 348(2-3):251-261, 2005. · Zbl 1081.68063 |
| [71] | N. Howgrave-Graham. Approximate integer common divisors. InCryptography and Lattices, International Conference, CaLC 2001, pages 51-66, 2001. · Zbl 1006.94528 |
| [72] | R. Impagliazzo. A personal view of average-case complexity. InProceedings of the Tenth Annual Structure in Complexity Theory Conference, pages 134- 147, 1995. |
| [73] | R. Impagliazzo and M. Luby. One-way functions are essential for complexity based cryptography (extended abstract). In30th Annual Symposium on Foundations of Computer Science, pages 230-235, 1989. |
| [74] | R. Impagliazzo and S. Rudich. Limits on the provable consequences of oneway permutations. InProceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 44-61, 1989. |
| [75] | D. Itsykson. Lower bound on average-case complexity of inversion of Goldreich’s function by drunken backtracking algorithms. InComputer Science- Theory and Applications, pages 204-215. Springer, 2010. · Zbl 1285.68056 |
| [76] | M. Jerrum. Large cliques elude the Metropolis process.Random Structures &Algorithms, 3(4):347-359, 1992. · Zbl 0754.60018 |
| [77] | A. Joux and C. Pierrot. Technical history of discrete logarithms in small characteristic finite fields - the road from subexponential to quasi-polynomial complexity.Des. Codes Cryptography, 78(1):73-85, 2016. · Zbl 1364.11165 |
| [78] | A. Juels and M. Peinado. Hiding cliques for cryptographic security.Des. Codes Cryptography, 20(3):269-280, 2000. · Zbl 0965.94015 |
| [79] | R. M. Karp. The probabilistic analysis of some combinatorial search algorithms.Algorithms and complexity: New directions and recent results, 1:19, 1976. · Zbl 0368.68035 |
| [80] | A. Kipnis and A. Shamir. Cryptanalysis of the HFE public key cryptosystem by relinearization. InAdvances in Cryptology - CRYPTO ’99, Springer, pages 19-30, 1999. · Zbl 0940.94012 |
| [81] | N. Koblitz.Elliptic curve cryptosystems.Mathematics of computation, 48(177):203-209, 1987. · Zbl 0622.94015 |
| [82] | L. Kucera. Expected complexity of graph partitioning problems.Discrete Applied Mathematics, 57(2-3):193-212, 1995. · Zbl 0830.68101 |
| [83] | G. Kuperberg. A subexponential-time quantum algorithm for the dihedral hidden subgroup problem.SIAM J. Comput., 35(1):170-188, 2005. · Zbl 1084.81019 |
| [84] | A. K. Lenstra, H. W. Lenstra Jr, M. S. Manasse, and J. M. Pollard. The number field sieve. InProceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, pages 564-572. ACM, 1990. |
| [85] | L. A. Levin. Average case complete problems.SIAM J. Comput., 15(1):285- 286, 1986. · Zbl 0589.68032 |
| [86] | V. Lyubashevsky. The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem. InProceedings of the 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems APPROX 2005, and 9th International Workshop on Randomization and Computation RANDOM 2005, pages 378-389, 2005. · Zbl 1142.68399 |
| [87] | T. Matsumoto and H. Imai. Public quadratic polynominal-tuples for efficient signature-verification and message-encryption. InAdvances in Cryptology EUROCRYPT ’88, Springer, pages 419-453, 1988. · Zbl 0655.94013 |
| [88] | R. McEliece. A public-key cryptosystem based on algebraic coding theory. Deep Space Network Progress Report, 44:114-116, 1978. |
| [89] | N. Megiddo and C. H. Papadimitriou. On total functions, existence theorems and computational complexity.Theor. Comput. Sci., 81(2):317-324, 1991. · Zbl 0731.68036 |
| [90] | R. C. Merkle. Secure communications over insecure channels.Commun. ACM, 21(4):294-299, 1978. Originally submitted in August 1975. · Zbl 1342.94085 |
| [91] | R. C. Merkle and M. E. Hellman. Hiding information and signatures in trapdoor knapsacks.IEEE Transactions on Information Theory, 24(5):525-530, 1978. · Zbl 1487.94132 |
| [92] | E. Miles, A. Sahai, and M. Zhandry. Annihilation attacks for multilinear maps: Cryptanalysis of indistinguishability obfuscation over GGH13. Cryptology ePrint Archive, Report 2016/147, 2016. · Zbl 1391.94782 |
| [93] | E. Miles and E. Viola. Substitution-permutation networks, pseudorandom functions, and natural proofs. InAdvances in Cryptology - CRYPTO 2012, Springer, pages 68-85, 2012. · Zbl 1294.94065 |
| [94] | V. S. Miller. Use of elliptic curves in cryptography. InAdvances in Cryptology - CRYPTO’85, Springer, pages 417-426, 1985. · Zbl 0589.94005 |
| [95] | A. D. Myasnikov and A. Ushakov. Length based attack and braid groups: cryptanalysis of anshel-anshel-goldfeld key exchange protocol. InPublic Key Cryptography-PKC 2007, Springer, pages 76-88, 2007. · Zbl 1127.94017 |
| [96] | M. Naor. Bit commitment using pseudorandomness.J. Cryptology, 4(2):151- 158, 1991. Preliminary version in CRYPTO ’89. · Zbl 0731.68033 |
| [97] | M. Naor and M. Yung. Universal one-way hash functions and their cryptographic applications. InProceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 33-43, 1989. |
| [98] | NIST. Secure hash standard, 2002. Federal Information Processing Standard Publication 180-2. US Department of Commerce, National Institute of Standards and Technology (NIST). |
| [99] | R. O’Donnell and D. Witmer. Goldreich’s PRG: evidence for near-optimal polynomial stretch. InIEEE 29th Conference on Computational Complexity, CCC, pages 1-12, 2014. |
| [100] | R. Ostrovsky and A. Wigderson. One-way fuctions are essential for nontrivial zero-knowledge. InISTCS, pages 3-17, 1993. |
| [101] | J. Patarin. Hidden fields equations (HFE) and isomorphisms of polynomials (IP): Two new families of asymmetric algorithms. InAdvances in Cryptology - EUROCRYPT96, Springer, pages 33-48, 1996. · Zbl 1301.94125 |
| [102] | C. Peikert. Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. InProceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, pages 333-342, 2009. · Zbl 1304.94079 |
| [103] | C. Peikert. A decade of lattice cryptography. Cryptology ePrint Archive, Report 2015/939, 2015.http://eprint.iacr.org/. · Zbl 1391.94788 |
| [104] | C. Peikert.How (not) to instantiate ring-LWE, 2016.Unpublished manuscript; available atweb.eecs.umich.edu/˜cpeikert/pubs/ instantiate-rlwe.pdf. · Zbl 1421.94066 |
| [105] | C. Peikert and B. Waters. Lossy trapdoor functions and their applications. SIAM Journal on Computing, 40(6):1803-1844, 2011. · Zbl 1236.94063 |
| [106] | M. O. Rabin. Digitalized signatures and public-key functions as intractable as factorization. MIT technical report, 1979. |
| [107] | O. Regev. New lattice based cryptographic constructions. InProceedings of the 35th Annual ACM Symposium on Theory of Computing, pages 407-416, 2003. · Zbl 1192.94105 |
| [108] | O. Regev. Quantum computation and lattice problems.SIAM J. Comput., 33(3):738-760, 2004. · Zbl 1057.81012 |
| [109] | O. Regev. On lattices, learning with errors, random linear codes, and cryptography.J. ACM, 56(6), 2009. Preliminary version in STOC 2005. · Zbl 1192.94106 |
| [110] | R. L. Rivest, A. Shamir, and L. M. Adleman. A method for obtaining digital signatures and public-key cryptosystems.Commun. ACM, 21(2):120-126, 1978. · Zbl 0368.94005 |
| [111] | J. Rompel. One-way functions are necessary and sufficient for secure signatures. InProceedings of the 22nd Annual ACM Symposium on Theory of Computing, pages 387-394, 1990. |
| [112] | A. Rostovtsev and A. Stolbunov. Public-key cryptosystem based on isogenies.IACR Cryptology ePrint Archive, 2006:145, 2006. |
| [113] | A. Sahai and B. Waters. How to use indistinguishability obfuscation: deniable encryption, and more. InSymposium on Theory of Computing, STOC, pages 475-484, 2014. · Zbl 1315.94102 |
| [114] | A. Shamir. A polynomial time algorithm for breaking the basic MerkleHellman cryptosystem. InAdvances in Cryptology - CRYPTO’83, Springer, pages 279-288, 1983. · Zbl 0543.94010 |
| [115] | P. W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer.SIAM J. Comput., 26(5):1484-1509, 1997. Preliminary version in FOCS ’94. · Zbl 1005.11065 |
| [116] | A. Tarantola.Inverse problem theory and methods for model parameter estimation. SIAM, 2005. · Zbl 1074.65013 |
| [117] | M. van Dijk, C. Gentry, S. Halevi, and V. Vaikuntanathan. Fully homomorphic encryption over the integers. InAdvances in Cryptology - EUROCRYPT 2010, pages 24-43, 2010. · Zbl 1279.94130 |
| [118] | A. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
