Document Open Access Logo

Hardness of KT Characterizes Parallel Cryptography

Authors Hanlin Ren , Rahul Santhanam

PDF
Thumbnail PDF

File

LIPIcs.CCC.2021.35.pdf
  • Filesize: 1.32 MB
  • 58 pages

Document Identifiers

Author Details

Hanlin Ren
  • Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, China
Rahul Santhanam
  • University of Oxford, UK

Acknowledgements

The first author is grateful to Lijie Chen, Mahdi Cheraghchi, and Yanyi Liu for helpful discussions. The second author thanks Yuval Ishai for a useful e-mail discussion. We would like to thank anonymous CCC reviewers for helpful comments that improve the presentation of this paper.

Cite As Get BibTex

Hanlin Ren and Rahul Santhanam. Hardness of KT Characterizes Parallel Cryptography. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 35:1-35:58, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.CCC.2021.35

Abstract

A recent breakthrough of Liu and Pass (FOCS'20) shows that one-way functions exist if and only if the (polynomial-)time-bounded Kolmogorov complexity, K^t, is bounded-error hard on average to compute. In this paper, we strengthen this result and extend it to other complexity measures:  
- We show, perhaps surprisingly, that the KT complexity is bounded-error average-case hard if and only if there exist one-way functions in constant parallel time (i.e. NC⁰). This result crucially relies on the idea of randomized encodings. Previously, a seminal work of Applebaum, Ishai, and Kushilevitz (FOCS'04; SICOMP'06) used the same idea to show that NC⁰-computable one-way functions exist if and only if logspace-computable one-way functions exist.
- Inspired by the above result, we present randomized average-case reductions among the NC¹-versions and logspace-versions of K^t complexity, and the KT complexity. Our reductions preserve both bounded-error average-case hardness and zero-error average-case hardness. To the best of our knowledge, this is the first reduction between the KT complexity and a variant of K^t complexity.
- We prove tight connections between the hardness of K^t complexity and the hardness of (the hardest) one-way functions. In analogy with the Exponential-Time Hypothesis and its variants, we define and motivate the Perebor Hypotheses for complexity measures such as K^t and KT. We show that a Strong Perebor Hypothesis for K^t implies the existence of (weak) one-way functions of near-optimal hardness 2^{n-o(n)}. To the best of our knowledge, this is the first construction of one-way functions of near-optimal hardness based on a natural complexity assumption about a search problem.
- We show that a Weak Perebor Hypothesis for MCSP implies the existence of one-way functions, and establish a partial converse. This is the first unconditional construction of one-way functions from the hardness of MCSP over a natural distribution.
- Finally, we study the average-case hardness of MKtP. We show that it characterizes cryptographic pseudorandomness in one natural regime of parameters, and complexity-theoretic pseudorandomness in another natural regime.

Subject Classification

ACM Subject Classification
  • Theory of computation → Cryptographic primitives
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Circuit complexity
Keywords
  • one-way function
  • meta-complexity
  • KT complexity
  • parallel cryptography
  • randomized encodings

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Miklós Ajtai. Generating hard instances of lattice problems (extended abstract). In \stoc28th, pages 99-108, 1996. URL: https://doi.org/10.1145/237814.237838.
  2. Adi Akavia, Oded Goldreich, Shafi Goldwasser, and Dana Moshkovitz. On basing one-way functions on NP-hardness. In \stoc38th, pages 701-710, 2006. URL: https://doi.org/10.1145/1132516.1132614.
  3. Eric Allender. When worlds collide: Derandomization, lower bounds, and Kolmogorov complexity. In \proc 21st Foundations of Software Technology and Theoretical Computer Science (FSTTCS), volume 2245 of Lecture Notes in Computer Science, pages 1-15, 2001. URL: https://doi.org/10.1007/3-540-45294-X_1.
  4. Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, and Detlef Ronneburger. Power from random strings. \siamj, 35(6):1467-1493, 2006. URL: https://doi.org/10.1137/050628994.
  5. Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, and Ilya Volkovich. One-way functions and a conditional variant of \MKTP. \eccc, 2021. URL: https://eccc.weizmann.ac.il/report/2021/009/.
  6. Eric Allender and Shuichi Hirahara. New insights on the (non-)hardness of circuit minimization and related problems. \toct, 11(4):27:1-27:27, 2019. URL: https://doi.org/10.1145/3349616.
  7. Noga Alon, Jehoshua Bruck, Joseph Naor, Moni Naor, and Ron M. Roth. Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs. \toit, 38(2):509-516, 1992. URL: https://doi.org/10.1109/18.119713.
  8. Benny Applebaum. Cryptography in Constant Parallel Time. Information Security and Cryptography. Springer, 2014. URL: https://doi.org/10.1007/978-3-642-17367-7.
  9. Benny Applebaum. Cryptographic hardness of random local functions - survey. Computational Complexity, 25(3):667-722, 2016. Google Scholar
  10. Benny Applebaum. Exponentially-hard Gap-CSP and local PRG via local hardcore functions. In \focs58th, pages 836-847, 2017. URL: https://doi.org/10.1109/FOCS.2017.82.
  11. Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. Cryptography in \NC⁰. \siamj, 36(4):845-888, 2006. URL: https://doi.org/10.1137/S0097539705446950.
  12. Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009. Google Scholar
  13. László Babai, Lance Fortnow, Noam Nisan, and Avi Wigderson. \BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computatioanl Complexity, 3:307-318, 1993. URL: https://doi.org/10.1007/BF01275486.
  14. Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, and Ke Yang. On the (im)possibility of obfuscating programs. \jacm, 59(2):6:1-6:48, 2012. URL: https://doi.org/10.1145/2160158.2160159.
  15. Joshua Baron, Yuval Ishai, and Rafail Ostrovsky. On linear-size pseudorandom generators and hardcore functions. \tcs, 554:50-63, 2014. URL: https://doi.org/10.1016/j.tcs.2014.06.013.
  16. Eli Biham, Yaron J. Goren, and Yuval Ishai. Basing weak public-key cryptography on strong one-way functions. In \tcc5th, volume 4948 of Lecture Notes in Computer Science, pages 55-72, 2008. URL: https://doi.org/10.1007/978-3-540-78524-8_4.
  17. Andrej Bogdanov and Luca Trevisan. On worst-case to average-case reductions for NP problems. \siamj, 36(4):1119-1159, 2006. URL: https://doi.org/10.1137/S0097539705446974.
  18. J. L. Bordewijk. Inter-reciprocity applied to electrical networks. Applied Scientific Research, Section A, pages 1-74, 1957. URL: https://doi.org/10.1007/BF02410413.
  19. Samuel R. Buss. The Boolean formula value problem is in \ALOGTIME. In \stoc19th, pages 123-131, 1987. URL: https://doi.org/10.1145/28395.28409.
  20. Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. The complexity of satisfiability of small depth circuits. In Parameterized and Exact Computation, 4th International Workshop, (IWPEC) 2009, volume 5917 of Lecture Notes in Computer Science, pages 75-85. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-11269-0_6.
  21. Ran Canetti, Yevgeniy Dodis, Shai Halevi, Eyal Kushilevitz, and Amit Sahai. Exposure-resilient functions and all-or-nothing transforms. In Advances in Cryptology - EUROCRYPT 2000, International Conference on the Theory and Application of Cryptographic Techniques, volume 1807 of Lecture Notes in Computer Science, pages 453-469, 2000. URL: https://doi.org/10.1007/3-540-45539-6_33.
  22. Lijie Chen, Ce Jin, and R. Ryan Williams. Hardness magnification for all sparse NP languages. In \focs60th, pages 1240-1255, 2019. URL: https://doi.org/10.1109/FOCS.2019.00077.
  23. Lijie Chen and Hanlin Ren. Strong average-case lower bounds from non-trivial derandomization. In \stoc52nd, pages 1327-1334, 2020. URL: https://doi.org/10.1145/3357713.3384279.
  24. Benny Chor, Oded Goldreich, Johan Håstad, Joel Friedman, Steven Rudich, and Roman Smolensky. The bit extraction problem or t-resilient functions (preliminary version). In \focs26th, pages 396-407, 1985. URL: https://doi.org/10.1109/SFCS.1985.55.
  25. Whitfield Diffie and Martin E. Hellman. New directions in cryptography. \toit, 22(6):644-654, 1976. URL: https://doi.org/10.1109/TIT.1976.1055638.
  26. Bill Fefferman, Ronen Shaltiel, Christopher Umans, and Emanuele Viola. On beating the hybrid argument. Theory of Computing, 9:809-843, 2013. URL: https://doi.org/10.4086/toc.2013.v009a026.
  27. Amos Fiat and Moni Naor. Rigorous time/space trade-offs for inverting functions. \siamj, 29(3):790-803, 1999. URL: https://doi.org/10.1137/S0097539795280512.
  28. Gudmund Skovbjerg Frandsen and Peter Bro Miltersen. Reviewing bounds on the circuit size of the hardest functions. \ipl, 95(2):354-357, 2005. URL: https://doi.org/10.1016/j.ipl.2005.03.009.
  29. Ofer Gabber and Zvi Galil. Explicit constructions of linear-sized superconcentrators. \jcss, 22(3):407-420, 1981. URL: https://doi.org/10.1016/0022-0000(81)90040-4.
  30. Oded Goldreich. The Foundations of Cryptography - Volume 1: Basic Techniques. Cambridge University Press, 2001. URL: https://doi.org/10.1017/CBO9780511546891.
  31. Oded Goldreich, Russell Impagliazzo, Leonid A. Levin, Ramarathnam Venkatesan, and David Zuckerman. Security preserving amplification of hardness. In \focs31st, pages 318-326, 1990. URL: https://doi.org/10.1109/FSCS.1990.89550.
  32. Oded Goldreich and Leonid A. Levin. A hard-core predicate for all one-way functions. In \stoc21st, pages 25-32, 1989. URL: https://doi.org/10.1145/73007.73010.
  33. Shafi Goldwasser, Dan Gutfreund, Alexander Healy, Tali Kaufman, and Guy N. Rothblum. Verifying and decoding in constant depth. In \stoc39th, pages 440-449, 2007. URL: https://doi.org/10.1145/1250790.1250855.
  34. Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, and Avishay Tal. \AC⁰[p] lower bounds against \MCSP via the coin problem. In \icalp46th, volume 132 of LIPIcs, pages 66:1-66:15, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.66.
  35. Venkatesan Guruswami and Piotr Indyk. Expander-based constructions of efficiently decodable codes. In \focs42nd, pages 658-667, 2001. URL: https://doi.org/10.1109/SFCS.2001.959942.
  36. Venkatesan Guruswami, Christopher Umans, and Salil P. Vadhan. Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. \jacm, 56(4):20:1-20:34, 2009. URL: https://doi.org/10.1145/1538902.1538904.
  37. Iftach Haitner, Omer Reingold, and Salil P. Vadhan. Efficiency improvements in constructing pseudorandom generators from one-way functions. \siamj, 42(3):1405-1430, 2013. URL: https://doi.org/10.1137/100814421.
  38. Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby. A pseudorandom generator from any one-way function. \siamj, 28(4):1364-1396, 1999. URL: https://doi.org/10.1137/S0097539793244708.
  39. Martin E. Hellman. A cryptanalytic time-memory trade-off. \toit, 26(4):401-406, 1980. URL: https://doi.org/10.1109/TIT.1980.1056220.
  40. Shuichi Hirahara. Non-black-box worst-case to average-case reductions within NP. In \focs59th, pages 247-258, 2018. URL: https://doi.org/10.1109/FOCS.2018.00032.
  41. Shuichi Hirahara. Characterizing average-case complexity of \PH by worst-case meta-complexity. In \focs61st, pages 50-60, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00014.
  42. Shuichi Hirahara. Unexpected hardness results for Kolmogorov complexity under uniform reductions. In \stoc52nd, pages 1038-1051, 2020. URL: https://doi.org/10.1145/3357713.3384251.
  43. Shuichi Hirahara and Rahul Santhanam. On the average-case complexity of \MCSP and its variants. In çc32nd, volume 79 of LIPIcs, pages 7:1-7:20, 2017. URL: https://doi.org/10.4230/LIPIcs.CCC.2017.7.
  44. Thomas Holenstein, Ueli M. Maurer, and Johan Sjödin. Complete classification of bilinear hard-core functions. In ŗypto24th, volume 3152 of Lecture Notes in Computer Science, pages 73-91. Springer, 2004. URL: https://doi.org/10.1007/978-3-540-28628-8_5.
  45. Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, pages 439-561, 2006. URL: https://doi.org/10.1090/S0273-0979-06-01126-8.
  46. Rahul Ilango. Connecting perebor conjectures: Towards a search to decision reduction for minimizing formulas. In çc35th, volume 169 of LIPIcs, pages 31:1-31:35, 2020. URL: https://doi.org/10.4230/LIPIcs.CCC.2020.31.
  47. Rahul Ilango. Constant depth formula and partial function versions of \MCSP are hard. In \focs61st, pages 424-433, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00047.
  48. Rahul Ilango, Bruno Loff, and Igor Carboni Oliveira. NP-hardness of circuit minimization for multi-output functions. In çc35th, volume 169 of LIPIcs, pages 22:1-22:36, 2020. URL: https://doi.org/10.4230/LIPIcs.CCC.2020.22.
  49. Russell Impagliazzo. Hard-core distributions for somewhat hard problems. In \focs36th, pages 538-545, 1995. URL: https://doi.org/10.1109/SFCS.1995.492584.
  50. Russell Impagliazzo. A personal view of average-case complexity. In \sct10th, pages 134-147, 1995. URL: https://doi.org/10.1109/SCT.1995.514853.
  51. Russell Impagliazzo and Leonid A. Levin. No better ways to generate hard NP instances than picking uniformly at random. In \focs31st, pages 812-821, 1990. URL: https://doi.org/10.1109/FSCS.1990.89604.
  52. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. \jcss, 62(2):367-375, 2001. URL: https://doi.org/10.1006/jcss.2000.1727.
  53. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? \jcss, 63(4):512-530, 2001. URL: https://doi.org/10.1006/jcss.2001.1774.
  54. Yuval Ishai and Eyal Kushilevitz. Randomizing polynomials: A new representation with applications to round-efficient secure computation. In \focs41st, pages 294-304, 2000. URL: https://doi.org/10.1109/SFCS.2000.892118.
  55. Yuval Ishai and Eyal Kushilevitz. Perfect constant-round secure computation via perfect randomizing polynomials. In \icalp29th, pages 244-256, 2002. URL: https://doi.org/10.1007/3-540-45465-9_22.
  56. Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai. Cryptography with constant computational overhead. In \stoc40th, pages 433-442, 2008. URL: https://doi.org/10.1145/1374376.1374438.
  57. Stasys Jukna. Boolean Function Complexity - Advances and Frontiers, volume 27 of Algorithms and combinatorics. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-24508-4.
  58. Valentine Kabanets and Jin-Yi Cai. Circuit minimization problem. In \stoc32nd, pages 73-79, 2000. URL: https://doi.org/10.1145/335305.335314.
  59. Ker-I Ko. On the complexity of learning minimum time-bounded Turing machines. \siamj, 20(5):962-986, 1991. URL: https://doi.org/10.1137/0220059.
  60. Leonid A. Levin. Randomness conservation inequalities; information and independence in mathematical theories. Information and Control, 61(1):15-37, 1984. URL: https://doi.org/10.1016/S0019-9958(84)80060-1.
  61. Leonid A. Levin. The tale of one-way functions. Problems of Information Transmission, 39(1):92-103, 2003. Google Scholar
  62. Yanyi Liu and Rafael Pass. On one-way functions and Kolmogorov complexity. In \focs61st, pages 1243-1254, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00118.
  63. Yanyi Liu and Rafael Pass. On the possibility of basing cryptography on \EXP \ne \BPP. \eccc, 28:56, 2021. URL: https://eccc.weizmann.ac.il/report/2021/056.
  64. G. A. Margulis. Explicit constructions of concentrators. Probl. Peredachi Inf., pages 71-80, 1973. Google Scholar
  65. Dylan M. McKay, Cody D. Murray, and R. Ryan Williams. Weak lower bounds on resource-bounded compression imply strong separations of complexity classes. In \stoc51st, pages 1215-1225, 2019. URL: https://doi.org/10.1145/3313276.3316396.
  66. Cody D. Murray and R. Ryan Williams. On the (non) NP-hardness of computing circuit complexity. \tocj, 13(1):1-22, 2017. URL: https://doi.org/10.4086/toc.2017.v013a004.
  67. Mikito Nanashima. On basing auxiliary-input cryptography on NP-hardness via nonadaptive black-box reductions. In \itcs12th, volume 185 of LIPIcs, pages 29:1-29:15, 2021. URL: https://doi.org/10.4230/LIPIcs.ITCS.2021.29.
  68. Noam Nisan. Extracting randomness: How and why. A survey. In çcieee11th, pages 44-58, 1996. URL: https://doi.org/10.1109/CCC.1996.507667.
  69. Noam Nisan and Avi Wigderson. Hardness vs randomness. \jcss, 49(2):149-167, 1994. URL: https://doi.org/10.1016/S0022-0000(05)80043-1.
  70. Noam Nisan and David Zuckerman. More deterministic simulation in logspace. In \stoc25th, pages 235-244, 1993. URL: https://doi.org/10.1145/167088.167162.
  71. Igor Carboni Oliveira, Ján Pich, and Rahul Santhanam. Hardness magnification near state-of-the-art lower bounds. In çc34th, volume 137 of LIPIcs, pages 27:1-27:29, 2019. URL: https://doi.org/10.4230/LIPIcs.CCC.2019.27.
  72. Igor Carboni Oliveira and Rahul Santhanam. Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness. In çc32nd, volume 79 of LIPIcs, pages 18:1-18:49, 2017. URL: https://doi.org/10.4230/LIPIcs.CCC.2017.18.
  73. Igor Carboni Oliveira and Rahul Santhanam. Hardness magnification for natural problems. In \focs59th, pages 65-76, 2018. URL: https://doi.org/10.1109/FOCS.2018.00016.
  74. Alexander A. Razborov and Steven Rudich. Natural proofs. \jcss, 55(1):24-35, 1997. URL: https://doi.org/10.1006/jcss.1997.1494.
  75. Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120-126, 1978. URL: https://doi.org/10.1145/359340.359342.
  76. Rahul Santhanam. Pseudorandomness and the minimum circuit size problem. In \itcs11th, volume 151 of LIPIcs, pages 68:1-68:26, 2020. URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.68.
  77. Claude E. Shannon. The synthesis of two-terminal switching circuits. Bell System technical journal, 28(1):59-98, 1949. URL: https://doi.org/10.1002/j.1538-7305.1949.tb03624.x.
  78. Daniel A. Spielman. Linear-time encodable and decodable error-correcting codes. \toit, 42(6):1723-1731, 1996. URL: https://doi.org/10.1109/18.556668.
  79. Amnon Ta-Shma and David Zuckerman. Extractor codes. \toit, 50(12):3015-3025, 2004. URL: https://doi.org/10.1109/TIT.2004.838377.
  80. Roei Tell. Quantified derandomization of linear threshold circuits. In \stoc50th, pages 855-865, 2018. URL: https://doi.org/10.1145/3188745.3188822.
  81. Boris A. Trakhtenbrot. A survey of Russian approaches to perebor (brute-force searches) algorithms. IEEE Annals of the History of Computing, 6(4):384-400, 1984. URL: https://doi.org/10.1109/MAHC.1984.10036.
  82. Luca Trevisan. Extractors and pseudorandom generators. \jacm, 48(4):860-879, 2001. URL: https://doi.org/10.1145/502090.502099.
  83. D. Uhlig. On the synthesis of self-correcting schemes from functional elements with a small number of reliable elements. Mathematical notes of the Academy of Sciences of the USSR, 15:558-562, 1974. URL: https://doi.org/10.1007/BF01152835.
  84. D. Uhlig. Zur parallelberechnung boolescher funktionen. TR Ing.hochsch. Mittweida, 1984. Google Scholar
  85. Salil P. Vadhan. Pseudorandomness. Foundations and Trends in Theoretical Computer Science, 7(1-3):1-336, 2012. URL: https://doi.org/10.1561/0400000010.
  86. Salil P. Vadhan and Colin Jia Zheng. A uniform min-max theorem with applications in cryptography. In ŗypto33rd, volume 8042 of Lecture Notes in Computer Science, pages 93-110, 2013. URL: https://doi.org/10.1007/978-3-642-40041-4_6.
  87. Hoeteck Wee. Finding Pessiland. In \tcc3rd, volume 3876 of Lecture Notes in Computer Science, pages 429-442, 2006. URL: https://doi.org/10.1007/11681878_22.
  88. Ingo Wegener. The complexity of Boolean functions. Wiley-Teubner, 1987. URL: http://ls2-www.cs.uni-dortmund.de/monographs/bluebook/.
  89. Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. \tcs, 348(2-3):357-365, 2005. URL: https://doi.org/10.1016/j.tcs.2005.09.023.
  90. Ryan Williams. Improving exhaustive search implies superpolynomial lower bounds. \siamj, 42(3):1218-1244, 2013. URL: https://doi.org/10.1137/10080703X.
  91. Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In \proc of the ICM, volume 3, pages 3431-3472, 2018. Google Scholar
  92. Andrew Chi-Chih Yao. Theory and applications of trapdoor functions (extended abstract). In \focs23rd, pages 80-91, 1982. URL: https://doi.org/10.1109/SFCS.1982.45.
  93. Yu Yu, Xiangxue Li, and Jian Weng. Pseudorandom generators from regular one-way functions: New constructions with improved parameters. \tcs, 569:58-69, 2015. URL: https://doi.org/10.1016/j.tcs.2014.12.013.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact