38 ms·

The existence of true one-way functions depends on Kolmogorov complexity

439 points by theafh 5y ago

margalabargala 5y ago
I take issue with their proof/illustration showing that Kolmogorov complexity is incomputable; perhaps someone can help me explain better. Here's the passage in question: > There’s just one drawback to Kolmogorov complexity: It’s incomputable, meaning that there is no program that can calculate the complexity of every possible string. We know this because if there were such a program, we’d end up with a contradiction. > To see this, imagine we have a program that can compute Kolmogorov complexity for any string. Let’s call the program K. Now, let’s search for the smallest string of numbers — call it S — whose Kolmogorov complexity is double the length of K. To be concrete, we could imagine that K has 1 million characters, so we’re looking for a string S whose Kolmogorov complexity is 2 million (meaning that the shortest program that outputs S has 2 million characters). > With program K in our toolbox, calculating S is easy (though not necessarily quick): We can write a new program that we’ll call P. The program P essentially says, “Go through all strings in order, using program K to compute their Kolmogorov complexity, until you find the first one whose Kolmogorov complexity is 2 million.” We’ll need to use program K when building P, so altogether P will have slightly more than 1 million characters. But this program outputs S, and we defined S as a string whose shortest program has 2 million characters. There’s the contradiction. The way I understand it, the upper bound of the complexity of a given string is essentially len(string), since you can just print out the thing itself. So in the above example, the string S is at least 2 million characters long. Now, it describes program K as itself having complexity of only 1 million, but it takes numerous strings as input. It seems to me that if an arbitrary input is given to a program in a case where you're measuring the character length of something, the character length of your input should be included. So while program K has complexity 1 million inherently, program K in the state of processing string S has complexity of 3 million- the complexity of S plus the complexity of K. Thus the contradiction vanishes. What the author is doing is tantamount to trying to write the shortest program to print all of Lorem Ipsum, and their submission looks like this: c=`cat <<EOF import sys for line in sys.stdin: print(line) EOF` cat loremipsum.txt | python -c "$c" You don't get to claim a 100 character submission without also counting the contents of loremipsum.txt.
- shmageggy 5y ago
  I'm not really following the logic of your argument, but one correction to: > it describes program K as itself having complexity of only 1 million K has length 1M, not complexity 1M.
- kamkha 5y ago
  In their example, you're not giving S as an input to K — instead, you're using K to write another program P which iterates over all possible strings and returns the first whose complexity is some value ("2 million" in their example). That program P will certainly be longer than K (as it contains K), but not much longer — it's adding to K only the instructions needed to iterate over strings and define the threshold complexity ("2 million"). P will then produce that "2 million"-complexity output, but it didn't need any input and thus the complexity of its output is truly just the length of P (which is smaller than "2 million"). It eventually stumbles upon S by going through all possible strings, and didn't need S to be provided. The main idea of the proof is very similar to the interesting-number paradox [0] or the Berry paradox [1]. [0] https://en.wikipedia.org/wiki/Interesting_number_paradox https://en.wikipedia.org/wiki/Interesting_number_paradox [1] https://en.wikipedia.org/wiki/Berry_paradox https://en.wikipedia.org/wiki/Berry_paradox
  - margalabargala 5y ago
    Got it, this makes sense, and continues to make more sense the more I think about it. I appreciate you taking the time to break this down for me.
- klank 5y ago
  P+K does not include S, but can output any arbitrary S. That is the whole reason for introducing P, you need a way of getting K(S) into your program without "hard coding" it directly and thus including the complexity of S. So, if we assume K is computable, then both S and P+K can output S, however, for an arbitrarily large S, K(P+K) < K(S). This is the proof by contradiction. Specifically, the value K(S) is supposed to be the the shortest program that can output S, yet P+K, which can also output S, is shorter.
Ono-Sendai 5y ago
The existence of one-way functions is also equivalent to P != NP: https://forwardscattering.org/post/33 https://forwardscattering.org/post/33
- throwaway81523 5y ago
  I think this is more like Impagliazzo's "Pessiland", where P!=NP but cryptography is still impossible.
- isaacg 5y ago
  That's not exactly what the page you linked says. The existence of one-way functions implies P != NP, but the reverse is not known to be true. In particular, it's possible that P != NP, but also no one-way-functions exist. See Impagliazzo's Five Worlds for more: http://blog.computationalcomplexity.org/2004/06/impagliazzos-five-worlds.html?m=1 http://blog.computationalcomplexity.org/2004/06/impagliazzos... All five worlds are still possible, given our current results. In both "Heuristica" and "Pessiland", P != NP but one-way-functions do not exist.
  - Vervious 5y ago
    yeah if someone proved P != NP --> OWFs, that would be the seminal result of a generation of work in computer science theory.
- joe_the_user 5y ago
  I haven't looked at this blog post in detail but the claim seems unlikely. Broadly, P!=NP is about worst case scenarios and the existence of one-way functions is about average case scenarios. If a few paragraphs could prove a relationship between the two, it would be a remarkable result indeed.
awinter-py 5y ago
whew thank you for editing the title -- quanta always buries the lede
- paulpauper 5y ago
  yeah sucks how they do this. annoying. tell us the why, what, etc. I don't need a huge back story and biography. tell me why this finding matters, what it does.
gobengo 5y ago
I feel so lucky to have stumbled upon this book 10+ years ago, which introduced me to the topic of Kolmogorov Complexity, neural nets, and more. https://mitpress.mit.edu/books/what-thought https://mitpress.mit.edu/books/what-thought
paulpauper 5y ago
I wish this explained it better
_8j50 5y ago
Two points of opinion on this: 1) There is no true randomness 2) Absolute security is not necessary or useful #1, because of cause and effect, in other words if you are an absolute observer who knows the state of all matter and energy and can retain infinite information of that knowledge then by knowing cause and effect of all things nothing is random to you. So in a true sense it isn't possible, so 'true random' is relative to the ability of the observer to measure cause and effect. #2, Because security is securitu of something against some other threat. Outside of theory, no one will face an absolute threat that threatens everything. A threat with finite ability to do harm intends to do harm against specific and measurable resources by abusing a finite number of vulnerabilities. Threat x Vulnerability = Risk of harm In reality, this equation applies on a finite but large number of threats and attack vectors. Where humans exists, Threat will always be greater than 0. In the article's context, they seek to reduce vulnerability to 0 so risk multiplies to 0 but even looking at only crypto vulns, a one way function with 0 vulns still needs a key to reverse it and management if that key will also need to have 0 risk, otherwise the net risk is still not zero. If AES is replaced by a new provably unbreakable cipher, what will meaninguly change about risk assesment? I think the premise is you somehow can stop worrying about some non-specific threats. But if you specify your threat, for example as 1 and your reduce your vuln to 0.000001 then your risk of 0.000001 is negligible. Absolute 0 is not useful other than to help you feel better.
- jkhdigital 5y ago
  You would probably enjoy some of Dusko Pavlovic's work: https://arxiv.org/pdf/1109.5542.pdf https://arxiv.org/pdf/1109.5542.pdf
  - _8j50 5y ago
    Thank you, at a glance it seems very interesting.
- scaramanga 5y ago
  > #1, because of cause and effect, in other words if you are an absolute observer who knows the state of all matter and energy and can retain infinite information of that knowledge then by knowing cause and effect of all things nothing is random to you. So in a true sense it isn't possible, so 'true random' is relative to the ability of the observer to measure cause and effect. So you just need to assume you are the god of a different universe than the one we appear to be in, where there is no physical realism. That is definitely outside of my threat model :)
iaw 5y ago
Anyone have insight into what the overtly complex one-way function they proposed was?
mxkopy 5y ago
I love this. There is something eerie about concrete results in computation and math that makes it hard for me to sleep at night. It's like we're discovering the speed of light in a non-physical universe, placing limits and boundaries on logic itself. Though this is less of a boundary and more of a door, it's no less concrete.
ganzuul 5y ago
https://en.wikipedia.org/wiki/Ilya_Prigogine https://en.wikipedia.org/wiki/Ilya_Prigogine maybe presents an intuitive approach to this topic. "A dissipative structure is characterized by the spontaneous appearance of symmetry breaking (anisotropy) and the formation of complex, sometimes chaotic, structures where interacting particles exhibit long range correlations. Prigogine actually coined that term for his main research subject, for which he was awarded the Nobel Prize in Chemistry in 1977." - scihi.org/ilya-prigogine/ (XSS warning) If the particles are words, then the physics is sentence structure.
- ganzuul 5y ago
  > The End of Certainty: Time, Chaos, and the New Laws of Nature, Prigogine contends that determinism is no longer a viable scientific belief: "The more we know about our universe, the more difficult it becomes to believe in determinism." This is a major departure from the approach of Newton, Einstein and Schrödinger, all of whom expressed their theories in terms of deterministic equations. According to Prigogine, determinism loses its explanatory power in the face of irreversibility and instability. > Prigogine traces the dispute over determinism back to Darwin, whose attempt to explain individual variability according to evolving populations inspired Ludwig Boltzmann to explain the behavior of gases in terms of populations of particles rather than individual particles.[24] This led to the field of statistical mechanics and the realization that gases undergo irreversible processes. In deterministic physics, all processes are time-reversible, meaning that they can proceed backward as well as forward through time. As Prigogine explains, determinism is fundamentally a denial of the arrow of time. With no arrow of time, there is no longer a privileged moment known as the "present," which follows a determined "past" and precedes an undetermined "future." All of time is simply given, with the future as determined or as undetermined as the past. With irreversibility, the arrow of time is reintroduced to physics.
giorgioz 5y ago
What if all our existence is actually part of an algorithm to generate strings with very high Kolmogorov complexity?
- giorgioz 5y ago
  this is inspired by The Hitchhiker's Guide to the Galaxy where planet earth is part of a computer to calculate an answer to a question. And also the fact that Lavalamps are used to generated random private keys. So our universe could be a gigantic lavalamp to generate string with high Kolmogorov complexity.
some_furry 5y ago
If you want to read the actual paper from the researchers, the URL is https://arxiv.org/abs/2009.11514 https://arxiv.org/abs/2009.11514
- pishpash 5y ago
  "...their paper even provides a specific way to make one. The one-way function that they describe in their paper is too complicated to use..." So can someone briefly describe the construction?
frankus 5y ago
"If they do not, cryptographers have shown, then secure cryptography is impossible." It seems like they're using "secure cryptography" kind of narrowly, as AFAIK a one-time pad could still be secure without any kind of one-way function.
- some_furry 5y ago
  A one-time pad is malleable* and doesn't provide ciphertext integrity guarantees. If you want to add message authentication to a protocol, you still need something more than a one-time-pad. * EDIT: Correct verbage EDIT 2: Why are people continuing to downvote this after it was corrected?
  - Rexxar 5y ago
    > Why are people continuing to downvote this after it was corrected? Because they don't refresh comments every 30s and they see your comment from one hour ago.
  - orlp 5y ago
    > A one-time pad is vulnerable to chosen-ciphertext attacks No it isn't. A one-time pad in isolation is vulnerable to being malleable since it provides no authentication, but the data it carries is 100% unknowable.
    - some_furry 5y ago
      And that malleability can be exploited to send garbage messages in some contexts, which is vaguely classifiable as a "chosen-ciphertext attack" but I've edited my comment to be more precise in verbage.
      - orlp 5y ago
        > which is vaguely classifiable as a "chosen-ciphertext attack" Only if we interpret the jargon at face value as a layman. But is is jargon, with a specific meaning. A chosen-ciphertext attack isn't just any attack in which you send (modified) ciphertext to your victim, it specifically refers to breaking a cipher (by e.g. deriving the key) using the information gained from getting ciphertexts of your choice decrypted. The only information you can gain this way about a one-time-pad is a random keystream that will never be used again for anything.
Snitch-Thursday 5y ago
Based on the title, I read this article thinking I was going to read a 'master vulnerability' or weakness of some sort in all major crypto implementations. I was ready to say 'well actually - as long as you have perfect forward secrecy and maybe a double rachet you can make it virtually impossible to break the encryption at scale blah blah blah', like a good little armchair crypto parrot would. But instead, I learned a little something new about how cryptography studies work. Thank you HN!
atonalfreerider 5y ago
Layperson question: if modern cryptography is broken at some point in the future, would this also lead to the collapse of any cryptographic system that only depends on one-way functions? In other words, would the code-breaker be able to access any bitcoin wallet, de-anonymize any transaction? Is this risk built in to cryptocurrency? Edit: https://avs.scitation.org/doi/10.1116/5.0073075 https://avs.scitation.org/doi/10.1116/5.0073075 > Finally, we calculate the number of physical qubits required to break the 256-bit elliptic curve encryption of keys in the Bitcoin network within the small available time frame in which it would actually pose a threat to do so. It would require 317 × 10 ^ 6 physical qubits to break the encryption within one hour using the surface code, a code cycle time of 1 μs, a reaction time of 10 μs, and a physical gate error of 10−3. To instead break the encryption within one day, it would require 13 × 10 ^ 6 physical qubits
- Someone 5y ago
  Not necessarily. A mathematical proof that one-way functions do not exist need not say anything about non-one-way functions, so it need not say anything about how hard it is to invert what we now think might be one-way functions. But yes, the risk that we don’t know whether encryption is mathematically possible hangs above every use of cryptography, using hashes to verify that data didn’t get tampered with, etc.
- dibujante 5y ago
  Yes, I believe so, although millions of qubits are still many orders of magnitude away from the largest quantum computers currently in existence. If Moore's Law applies to quantum computers (big if) then it will take about 50 years for quantum computers to crack 256-bit encryption within a day. Maybe this will spark a cryptography arms race where keys just get larger for a while to postpone that day.
  - SAI_Peregrinus 5y ago
    There also seem to be some fundamental limits on computation in physical systems. The Landauer limit is a famous one. Even with quantum computers, you quickly start needing ridiculous amounts of energy, on the order of "build a dyson swarm". Any symmetric system with a 512-bit key will be secure against solar-system sized quantum computers for many human lifetimes.
abhv 5y ago
An even more tantalizing result by the prolific Rafael and Yanyi is the following paper [1] which discusses how to relate the existence of one-way functions to the assumption that BPP \neq EXP (two classes). If you spend the time understanding just the statement of their result in that paper, you get to an eerily small gap between "heuristic algorithms" for a version of the time-bounded K-complexity, and "errorless" versions of it. Their line of research has been even more inspiring than this very well-written quanta article suggests. [1] https://eprint.iacr.org/2021/535.pdf https://eprint.iacr.org/2021/535.pdf
- CaptainNegative 5y ago
  Many tight connections between the problem of (BPP vs superpolynomial-time complexity classes) and the existence of hard-on-average functions have been known for a long time -- at least since the Nisan-Wigderson construction was discovered in '94. What distinguishes this paper from the related results preceding it?
- deleted 5y ago
  [deleted]
- deleted 5y ago
  [deleted]
woliveirajr 5y ago
TL;DR: Kolmogorov complexity.
- woliveirajr 5y ago
  Seems that the clickable title was changed
praptak 5y ago
The notions of hardness for practical cryptography are a bit different than ones in complexity theory. One difference is obviously the asymptotics. Just because something is in P (generally considered "easy" in complexity theory) does not mean it is feasible to compute - maybe the complexity is N^256 or even N^2 but with a huge constant. OTOH even if we show that something is "harder than P", it does not mean it is infeasible to compute - strictly speaking P is only about deterministic complexity and worst case. So a problem where 99% instances are practically easy to compute can still be harder than P, yet too easy for crypto.
- Vervious 5y ago
  Just wanted to emphasize your point about "worst case hardness" -- even if 3SAT turns out to be hard (due to P != NP), it is only hard in the worst case (for a very small subset of all possible 3SAT problems). Most 3sat problem instances are (probably?) easy. In crypto, we need to sample "average case hard" problems, where on average, a random problem that we sample is hard. This is in contrast to, for instance, uniformly sampling from the set of all 3SAT instances, which gives an easy problem on average. A continuation of this line of research essentially looks at turning worst case hard problems into average case hard problems. Asymptotics are already way on the backburner since we are in theory world. (Note that a One way function is average case hard)
- zarzavat 5y ago
  Difficulty in cryptography is boolean. Is there an attack which has fewer steps than the brute force constant? If no? you’re good. If Yes? add more rounds, etc.
  - Ar-Curunir 5y ago
    No, that’s not true. Plenty of cryptography is asymptotic.
  - MauranKilom 5y ago
    By that specific notion, any hash where you can shave a hair of complexity off the first round (e.g. via SAT) is insecure, because it takes ever-so-slightly less effort to brute force it that way than pure brute force. Adding more rounds doesn't change that.
achenet 5y ago
Isn’t Kolmogorov Complexity hard to measure, because it depends on the language chosen?
- jkhdigital 5y ago
  All Turing-complete programming languages (i.e. the encoding used for the Turing machine's instructions) can be compiled into a "universal" language, and the length of the compiler is a constant. So the choice of language affects only a constant factor, and can be hand-waved away when speaking of asymptotic complexity.
- tromp 5y ago
  It's incomputable regardless of the language chosen. And two different languages only affect the Kolmogorov Complexity up to a constant (the maximum size of an interpreter for one language written in the other language).
- Zamicol 5y ago
  It doesn't depend on language. Kolmogorov Complexity is about information. It requires understanding the minimum amount of information needed to perform a task. And information is, naturally, measured in bits.
- tlb 5y ago
  The value of K for any language is within a constant of K for any other language. To convince yourself this is true, imagine constructing an interpreter for your preferred language in whatever language you are given. You can always prepend this (fixed-sized) interpreter to a program in your preferred language, adding a constant value to the complexity.
  - pishpash 5y ago
    K can be arbitrarily large though.
    - Ono-Sendai 5y ago
nullc 5y ago
Here is an enjoyable classic work connecting cryptography to complexity theory, in the abstract: https://stuff.mit.edu/afs/sipb/project/reading-group/past-readings/2009-06-08-five-worlds.pdf https://stuff.mit.edu/afs/sipb/project/reading-group/past-re...
gnull 5y ago
Identifying the connection between one-way functions and Kolmogorov complexity is truly impressive. But the article oversimplified a few things that may be misleading for someone. 1. One-way functions are not all cryptography. Some constructions may need stronger assumptions than one-way functions (we don't know yet if they do). So this problem is a “Master Problem” only for a subset of cryptography (symmetric encryption, pseudorandom generators, etc.). 2. This is not the first “Master Problem” to base one-way functions on. There's Levin's complete one way function [1; Section 4.3]. Breaking it is proven to be as hard as any other one-way function, in other words if there exist one-way functions then this is one of them. But Levin's construction is somewhat artificial (it combines many one-way function candidates to create the “master one-way function”) and is not as surprising since its techniques and formulation are similar to how the usual one-way functions are defined. The connection from the linked article, on the other hand, is very surprising and unusual; it connects one-way functions to a more distant field which (to me) seems to be operating with quite different concepts. It's also fun to know that similar “Master Problems” exist for other primitives too. For example, for public-key encryption there's a Complete Public Key cryptosystem [2]. Albeit this one is similar in spirit to Levin's construction (not as surprising IMO as the linked article), the complete cryptosystem is obtained by combining many other cryptosystems. [1]: https://arxiv.org/abs/cs/0012023 https://arxiv.org/abs/cs/0012023 [2]: https://eccc.weizmann.ac.il//eccc-reports/2006/TR06-046/index.html https://eccc.weizmann.ac.il//eccc-reports/2006/TR06-046/inde...
- eru 5y ago
  You say: > 1. One-way functions are not all cryptography. The article says: > Today, the internet protocols for tasks like transmitting credit card numbers and digital signatures depend on these functions. “Most of the crypto that is used in the real world is something that can be based on one-way functions,” said Yuval Ishai, a cryptographer at the Technion in Haifa, Israel. Looks like they alreadyd mentioned that?
  - gnull 5y ago
    Yes, I realized I made some rushed conclusions there.
knowsuchagency 5y ago
naming things?
- lucb1e 5y ago
  cache invalidation?
denton-scratch 5y ago
The bit I don't get: The time-bounded Kolmogorov complexity is an approximation. But it seems to be being used to prove that cryptography based on one-way functions is/isn't possible. It's not obvious to this grandstanding ignoramus that the approximation taints the proof; nor that it doesn't. I just prefer proofs that don't include approximations.
- pishpash 5y ago
  It's not an approximation, it defines a variant version of the problem that makes sense in the context of practical computation.
- derbOac 5y ago
  In another paper they imply that the time bound also effectively bounds the solvability of the one-way function. So, without the bound you say "can Kolmogorov complexity be calculated?", which implies "given infinite time can you solve this one-way function?" With the bound, it's saying "given this time limit to calculating Kolmogorov complexity, can the one-way function be solved within a directly related time limit?" The assumption is that practically speaking it doesn't matter if the one-way function can be solved in millions of eons, so a corresponding time bound is acceptable.
jtsiskin 5y ago
This makes sense, intuitively; if I gave you "8f434346648f6b96df89dda901c5176b10a6d83961dd3c1ac88b59b2dc327aa4" (sha256('hi')), and you quickly told me its K complexity was 2, I would become skeptical that sha256 was a one way function. (assuming of course you didn't brute force it)
- rogers18445 5y ago
  The correct analogy would be suppose I give you a block of an encrypted uncompressed image. And you return K(encryption_algo_with_key) + K(image_compression_algo_with_compressed_image)
- mxkopy 5y ago
  My intuition was this: Take a sequence of operations (AND, OR, NOT) and assign each unique term a prime, then multiply each term by some other prime raised to their respective position in the sequence. Call the result the 'output'. This kinda feels like running a program. Now, try and work out, for any given output, the sequence of minimum operations & their order that would get that output. Basically you factor, which is a common 'one-way' function from my understanding. P.S. I feel like the multiplied sequence of operations is a program, but then adding some input (encoded as a number) to that is closer to actually running the program. Then, for every output you have a unique program P with input 0 that gives you that output, but P isn't necessarily tied to the structure of the original program that generated that specific output.
- p1mrx 5y ago
  2 would be the wrong answer here, because K-complexity includes the definition of sha256 itself.
  - lisper 5y ago
    This is a very good point and very important to understand. K-complexity is measured in terms of how many bits you need to specify a Turing machine (under some encoding) that computes the function. There are therefore only four functions whose K-complexity is 2. An important ancillary result is Chaitin's theorem, which is that beyond a certain threshold (a few hundred bits) it is not possible to know the K-complexity of a function because if you did then you could solve the halting problem. See [1] for a simple proof. [1] https://flownet.com/ron/chaitin.html https://flownet.com/ron/chaitin.html
kevinwang 5y ago
The article doesn't mention the date, but it appears the result in question is from 2020 (based on the arxiv paper).
Xcelerate 5y ago
> suppose you’ve set your sights on a less lofty goal than calculating the exact time-bounded Kolmogorov complexity of every possible string — suppose you’re content to calculate it approximately, and just for most strings. If there’s an efficient way to do this, Liu and Pass showed, then true one-way functions cannot exist. In that case, all our candidate one-way functions would be instantly breakable, not just in theory but in practice. Wow, this discovery seems to have really deep implications for the limits of artificial general intelligence, but I don’t have quite enough background in the field to make a formal mathematical connection. At first glance, this seems to imply: cryptography or AIXItl, choose one. Anyone working in the field have more insight on this paper’s potential AGI implications?
- contravariant 5y ago
  Not sure why the intelligence being artificial is needed for these implications? Though I don't really follow you reasoning anyway, you would expect a general intelligence to be able to estimate the exact Kolmogorov complexity of nigh everything?
- pas 5y ago
  Isn't there other formulations of AGI that don't rely on Solomonoff induction (which relies on Kolgomorov complexity)? Furthermore humans are already general intelligences, and worst case it's possible to do whole brain emulation, and then optimize that.
  - ravi-delia 5y ago
    I'm much much more of a pure math than CS person, but I've stopped in on more than a few lectures. The impression I get is that Solomonoff Induction was already an upper bound. This just makes it a strict upper bound (assuming we believe one-way functions exist, which I think we do). It seems fairly intuitive that you wouldn't be able to even approach the peak in reasonable computational time, and I don't think most people working this angle disagreed.
torotonnato 5y ago
Tangential: Marcus Hutter's AIXI model popped in my head. The hardness of the time-bounded Kolmogorov complexity is also tied to the maximum intelligence of his universal AIXI agents. So, in an universe where one-way functions exist, the best agents can have privacy, but are rationally more limited than their cousins that live in a universe without OWFs. Makes sense? One property, two consequences. (I'm not talking about quantum cryptography, which I know even less than the usual one)
- ravi-delia 5y ago
  I think that seems basically logical, though I suspect there's a sort of peak of agency towards the middle of rationality. Like, if you had a planning oracle you wouldn't be an agent anymore, even if you were perfectly rational. That matches my intuitions, it seems like agentness is tied to complexity anyway.

439 points by theafh 5y ago

I take issue with their proof/illustration showing that Kolmogorov complexity is incomputable; perhaps someone can help me explain better. Here's the passage in question: > There’s just one drawback to Kolmogorov complexity: It’s incomputable, meaning that there is no program that can calculate the complexity of every possible string. We know this because if there were such a program, we’d end up with a contradiction. > To see this, imagine we have a program that can compute Kolmogorov complexity for any string. Let’s call the program K. Now, let’s search for the smallest string of numbers — call it S — whose Kolmogorov complexity is double the length of K. To be concrete, we could imagine that K has 1 million characters, so we’re looking for a string S whose Kolmogorov complexity is 2 million (meaning that the shortest program that outputs S has 2 million characters). > With program K in our toolbox, calculating S is easy (though not necessarily quick): We can write a new program that we’ll call P. The program P essentially says, “Go through all strings in order, using program K to compute their Kolmogorov complexity, until you find the first one whose Kolmogorov complexity is 2 million.” We’ll need to use program K when building P, so altogether P will have slightly more than 1 million characters. But this program outputs S, and we defined S as a string whose shortest program has 2 million characters. There’s the contradiction. The way I understand it, the upper bound of the complexity of a given string is essentially len(string), since you can just print out the thing itself. So in the above example, the string S is at least 2 million characters long. Now, it describes program K as itself having complexity of only 1 million, but it takes numerous strings as input. It seems to me that if an arbitrary input is given to a program in a case where you're measuring the character length of something, the character length of your input should be included. So while program K has complexity 1 million inherently, program K in the state of processing string S has complexity of 3 million- the complexity of S plus the complexity of K. Thus the contradiction vanishes. What the author is doing is tantamount to trying to write the shortest program to print all of Lorem Ipsum, and their submission looks like this: c=`cat <<EOF import sys for line in sys.stdin: print(line) EOF` cat loremipsum.txt | python -c "$c" You don't get to claim a 100 character submission without also counting the contents of loremipsum.txt.

shmageggy 5y ago
I'm not really following the logic of your argument, but one correction to: > it describes program K as itself having complexity of only 1 million K has length 1M, not complexity 1M.
kamkha 5y ago
In their example, you're not giving S as an input to K — instead, you're using K to write another program P which iterates over all possible strings and returns the first whose complexity is some value ("2 million" in their example). That program P will certainly be longer than K (as it contains K), but not much longer — it's adding to K only the instructions needed to iterate over strings and define the threshold complexity ("2 million"). P will then produce that "2 million"-complexity output, but it didn't need any input and thus the complexity of its output is truly just the length of P (which is smaller than "2 million"). It eventually stumbles upon S by going through all possible strings, and didn't need S to be provided. The main idea of the proof is very similar to the interesting-number paradox [0] or the Berry paradox [1]. [0] https://en.wikipedia.org/wiki/Interesting_number_paradox https://en.wikipedia.org/wiki/Interesting_number_paradox [1] https://en.wikipedia.org/wiki/Berry_paradox https://en.wikipedia.org/wiki/Berry_paradox
- margalabargala 5y ago
  Got it, this makes sense, and continues to make more sense the more I think about it. I appreciate you taking the time to break this down for me.
klank 5y ago
P+K does not include S, but can output any arbitrary S. That is the whole reason for introducing P, you need a way of getting K(S) into your program without "hard coding" it directly and thus including the complexity of S. So, if we assume K is computable, then both S and P+K can output S, however, for an arbitrarily large S, K(P+K) < K(S). This is the proof by contradiction. Specifically, the value K(S) is supposed to be the the shortest program that can output S, yet P+K, which can also output S, is shorter.

Ono-Sendai 5y ago

The existence of one-way functions is also equivalent to P != NP: https://forwardscattering.org/post/33 https://forwardscattering.org/post/33

throwaway81523 5y ago
I think this is more like Impagliazzo's "Pessiland", where P!=NP but cryptography is still impossible.
isaacg 5y ago
That's not exactly what the page you linked says. The existence of one-way functions implies P != NP, but the reverse is not known to be true. In particular, it's possible that P != NP, but also no one-way-functions exist. See Impagliazzo's Five Worlds for more: http://blog.computationalcomplexity.org/2004/06/impagliazzos-five-worlds.html?m=1 http://blog.computationalcomplexity.org/2004/06/impagliazzos... All five worlds are still possible, given our current results. In both "Heuristica" and "Pessiland", P != NP but one-way-functions do not exist.
- Vervious 5y ago
  yeah if someone proved P != NP --> OWFs, that would be the seminal result of a generation of work in computer science theory.
joe_the_user 5y ago
I haven't looked at this blog post in detail but the claim seems unlikely. Broadly, P!=NP is about worst case scenarios and the existence of one-way functions is about average case scenarios. If a few paragraphs could prove a relationship between the two, it would be a remarkable result indeed.

awinter-py 5y ago

whew thank you for editing the title -- quanta always buries the lede

paulpauper 5y ago
yeah sucks how they do this. annoying. tell us the why, what, etc. I don't need a huge back story and biography. tell me why this finding matters, what it does.

gobengo 5y ago

I feel so lucky to have stumbled upon this book 10+ years ago, which introduced me to the topic of Kolmogorov Complexity, neural nets, and more. https://mitpress.mit.edu/books/what-thought https://mitpress.mit.edu/books/what-thought

paulpauper 5y ago

I wish this explained it better

_8j50 5y ago

Two points of opinion on this: 1) There is no true randomness 2) Absolute security is not necessary or useful #1, because of cause and effect, in other words if you are an absolute observer who knows the state of all matter and energy and can retain infinite information of that knowledge then by knowing cause and effect of all things nothing is random to you. So in a true sense it isn't possible, so 'true random' is relative to the ability of the observer to measure cause and effect. #2, Because security is securitu of something against some other threat. Outside of theory, no one will face an absolute threat that threatens everything. A threat with finite ability to do harm intends to do harm against specific and measurable resources by abusing a finite number of vulnerabilities. Threat x Vulnerability = Risk of harm In reality, this equation applies on a finite but large number of threats and attack vectors. Where humans exists, Threat will always be greater than 0. In the article's context, they seek to reduce vulnerability to 0 so risk multiplies to 0 but even looking at only crypto vulns, a one way function with 0 vulns still needs a key to reverse it and management if that key will also need to have 0 risk, otherwise the net risk is still not zero. If AES is replaced by a new provably unbreakable cipher, what will meaninguly change about risk assesment? I think the premise is you somehow can stop worrying about some non-specific threats. But if you specify your threat, for example as 1 and your reduce your vuln to 0.000001 then your risk of 0.000001 is negligible. Absolute 0 is not useful other than to help you feel better.

jkhdigital 5y ago
You would probably enjoy some of Dusko Pavlovic's work: https://arxiv.org/pdf/1109.5542.pdf https://arxiv.org/pdf/1109.5542.pdf
- _8j50 5y ago
  Thank you, at a glance it seems very interesting.
scaramanga 5y ago
> #1, because of cause and effect, in other words if you are an absolute observer who knows the state of all matter and energy and can retain infinite information of that knowledge then by knowing cause and effect of all things nothing is random to you. So in a true sense it isn't possible, so 'true random' is relative to the ability of the observer to measure cause and effect. So you just need to assume you are the god of a different universe than the one we appear to be in, where there is no physical realism. That is definitely outside of my threat model :)

iaw 5y ago

Anyone have insight into what the overtly complex one-way function they proposed was?

mxkopy 5y ago

I love this. There is something eerie about concrete results in computation and math that makes it hard for me to sleep at night. It's like we're discovering the speed of light in a non-physical universe, placing limits and boundaries on logic itself. Though this is less of a boundary and more of a door, it's no less concrete.

ganzuul 5y ago

https://en.wikipedia.org/wiki/Ilya_Prigogine https://en.wikipedia.org/wiki/Ilya_Prigogine maybe presents an intuitive approach to this topic. "A dissipative structure is characterized by the spontaneous appearance of symmetry breaking (anisotropy) and the formation of complex, sometimes chaotic, structures where interacting particles exhibit long range correlations. Prigogine actually coined that term for his main research subject, for which he was awarded the Nobel Prize in Chemistry in 1977." - scihi.org/ilya-prigogine/ (XSS warning) If the particles are words, then the physics is sentence structure.

ganzuul 5y ago
> The End of Certainty: Time, Chaos, and the New Laws of Nature, Prigogine contends that determinism is no longer a viable scientific belief: "The more we know about our universe, the more difficult it becomes to believe in determinism." This is a major departure from the approach of Newton, Einstein and Schrödinger, all of whom expressed their theories in terms of deterministic equations. According to Prigogine, determinism loses its explanatory power in the face of irreversibility and instability. > Prigogine traces the dispute over determinism back to Darwin, whose attempt to explain individual variability according to evolving populations inspired Ludwig Boltzmann to explain the behavior of gases in terms of populations of particles rather than individual particles.[24] This led to the field of statistical mechanics and the realization that gases undergo irreversible processes. In deterministic physics, all processes are time-reversible, meaning that they can proceed backward as well as forward through time. As Prigogine explains, determinism is fundamentally a denial of the arrow of time. With no arrow of time, there is no longer a privileged moment known as the "present," which follows a determined "past" and precedes an undetermined "future." All of time is simply given, with the future as determined or as undetermined as the past. With irreversibility, the arrow of time is reintroduced to physics.

giorgioz 5y ago

What if all our existence is actually part of an algorithm to generate strings with very high Kolmogorov complexity?

giorgioz 5y ago
this is inspired by The Hitchhiker's Guide to the Galaxy where planet earth is part of a computer to calculate an answer to a question. And also the fact that Lavalamps are used to generated random private keys. So our universe could be a gigantic lavalamp to generate string with high Kolmogorov complexity.

some_furry 5y ago

If you want to read the actual paper from the researchers, the URL is https://arxiv.org/abs/2009.11514 https://arxiv.org/abs/2009.11514

pishpash 5y ago
"...their paper even provides a specific way to make one. The one-way function that they describe in their paper is too complicated to use..." So can someone briefly describe the construction?

frankus 5y ago

"If they do not, cryptographers have shown, then secure cryptography is impossible." It seems like they're using "secure cryptography" kind of narrowly, as AFAIK a one-time pad could still be secure without any kind of one-way function.

some_furry 5y ago
A one-time pad is malleable* and doesn't provide ciphertext integrity guarantees. If you want to add message authentication to a protocol, you still need something more than a one-time-pad. * EDIT: Correct verbage EDIT 2: Why are people continuing to downvote this after it was corrected?
- Rexxar 5y ago
  > Why are people continuing to downvote this after it was corrected? Because they don't refresh comments every 30s and they see your comment from one hour ago.
- orlp 5y ago
  > A one-time pad is vulnerable to chosen-ciphertext attacks No it isn't. A one-time pad in isolation is vulnerable to being malleable since it provides no authentication, but the data it carries is 100% unknowable.
  - some_furry 5y ago
    And that malleability can be exploited to send garbage messages in some contexts, which is vaguely classifiable as a "chosen-ciphertext attack" but I've edited my comment to be more precise in verbage.
    - orlp 5y ago
      > which is vaguely classifiable as a "chosen-ciphertext attack" Only if we interpret the jargon at face value as a layman. But is is jargon, with a specific meaning. A chosen-ciphertext attack isn't just any attack in which you send (modified) ciphertext to your victim, it specifically refers to breaking a cipher (by e.g. deriving the key) using the information gained from getting ciphertexts of your choice decrypted. The only information you can gain this way about a one-time-pad is a random keystream that will never be used again for anything.

Snitch-Thursday 5y ago

Based on the title, I read this article thinking I was going to read a 'master vulnerability' or weakness of some sort in all major crypto implementations. I was ready to say 'well actually - as long as you have perfect forward secrecy and maybe a double rachet you can make it virtually impossible to break the encryption at scale blah blah blah', like a good little armchair crypto parrot would. But instead, I learned a little something new about how cryptography studies work. Thank you HN!

atonalfreerider 5y ago

Layperson question: if modern cryptography is broken at some point in the future, would this also lead to the collapse of any cryptographic system that only depends on one-way functions? In other words, would the code-breaker be able to access any bitcoin wallet, de-anonymize any transaction? Is this risk built in to cryptocurrency? Edit: https://avs.scitation.org/doi/10.1116/5.0073075 https://avs.scitation.org/doi/10.1116/5.0073075 > Finally, we calculate the number of physical qubits required to break the 256-bit elliptic curve encryption of keys in the Bitcoin network within the small available time frame in which it would actually pose a threat to do so. It would require 317 × 10 ^ 6 physical qubits to break the encryption within one hour using the surface code, a code cycle time of 1 μs, a reaction time of 10 μs, and a physical gate error of 10−3. To instead break the encryption within one day, it would require 13 × 10 ^ 6 physical qubits

Someone 5y ago
Not necessarily. A mathematical proof that one-way functions do not exist need not say anything about non-one-way functions, so it need not say anything about how hard it is to invert what we now think might be one-way functions. But yes, the risk that we don’t know whether encryption is mathematically possible hangs above every use of cryptography, using hashes to verify that data didn’t get tampered with, etc.
dibujante 5y ago
Yes, I believe so, although millions of qubits are still many orders of magnitude away from the largest quantum computers currently in existence. If Moore's Law applies to quantum computers (big if) then it will take about 50 years for quantum computers to crack 256-bit encryption within a day. Maybe this will spark a cryptography arms race where keys just get larger for a while to postpone that day.
- SAI_Peregrinus 5y ago
  There also seem to be some fundamental limits on computation in physical systems. The Landauer limit is a famous one. Even with quantum computers, you quickly start needing ridiculous amounts of energy, on the order of "build a dyson swarm". Any symmetric system with a 512-bit key will be secure against solar-system sized quantum computers for many human lifetimes.

abhv 5y ago

An even more tantalizing result by the prolific Rafael and Yanyi is the following paper [1] which discusses how to relate the existence of one-way functions to the assumption that BPP \neq EXP (two classes). If you spend the time understanding just the statement of their result in that paper, you get to an eerily small gap between "heuristic algorithms" for a version of the time-bounded K-complexity, and "errorless" versions of it. Their line of research has been even more inspiring than this very well-written quanta article suggests. [1] https://eprint.iacr.org/2021/535.pdf https://eprint.iacr.org/2021/535.pdf

CaptainNegative 5y ago
Many tight connections between the problem of (BPP vs superpolynomial-time complexity classes) and the existence of hard-on-average functions have been known for a long time -- at least since the Nisan-Wigderson construction was discovered in '94. What distinguishes this paper from the related results preceding it?
deleted 5y ago
[deleted]
deleted 5y ago
[deleted]

woliveirajr 5y ago

TL;DR: Kolmogorov complexity.

woliveirajr 5y ago
Seems that the clickable title was changed

praptak 5y ago

The notions of hardness for practical cryptography are a bit different than ones in complexity theory. One difference is obviously the asymptotics. Just because something is in P (generally considered "easy" in complexity theory) does not mean it is feasible to compute - maybe the complexity is N^256 or even N^2 but with a huge constant. OTOH even if we show that something is "harder than P", it does not mean it is infeasible to compute - strictly speaking P is only about deterministic complexity and worst case. So a problem where 99% instances are practically easy to compute can still be harder than P, yet too easy for crypto.

Vervious 5y ago
Just wanted to emphasize your point about "worst case hardness" -- even if 3SAT turns out to be hard (due to P != NP), it is only hard in the worst case (for a very small subset of all possible 3SAT problems). Most 3sat problem instances are (probably?) easy. In crypto, we need to sample "average case hard" problems, where on average, a random problem that we sample is hard. This is in contrast to, for instance, uniformly sampling from the set of all 3SAT instances, which gives an easy problem on average. A continuation of this line of research essentially looks at turning worst case hard problems into average case hard problems. Asymptotics are already way on the backburner since we are in theory world. (Note that a One way function is average case hard)
zarzavat 5y ago
Difficulty in cryptography is boolean. Is there an attack which has fewer steps than the brute force constant? If no? you’re good. If Yes? add more rounds, etc.
- Ar-Curunir 5y ago
  No, that’s not true. Plenty of cryptography is asymptotic.
- MauranKilom 5y ago
  By that specific notion, any hash where you can shave a hair of complexity off the first round (e.g. via SAT) is insecure, because it takes ever-so-slightly less effort to brute force it that way than pure brute force. Adding more rounds doesn't change that.

achenet 5y ago

Isn’t Kolmogorov Complexity hard to measure, because it depends on the language chosen?

jkhdigital 5y ago
All Turing-complete programming languages (i.e. the encoding used for the Turing machine's instructions) can be compiled into a "universal" language, and the length of the compiler is a constant. So the choice of language affects only a constant factor, and can be hand-waved away when speaking of asymptotic complexity.
tromp 5y ago
It's incomputable regardless of the language chosen. And two different languages only affect the Kolmogorov Complexity up to a constant (the maximum size of an interpreter for one language written in the other language).
Zamicol 5y ago
It doesn't depend on language. Kolmogorov Complexity is about information. It requires understanding the minimum amount of information needed to perform a task. And information is, naturally, measured in bits.
tlb 5y ago
The value of K for any language is within a constant of K for any other language. To convince yourself this is true, imagine constructing an interpreter for your preferred language in whatever language you are given. You can always prepend this (fixed-sized) interpreter to a program in your preferred language, adding a constant value to the complexity.
- pishpash 5y ago
  K can be arbitrarily large though.
  - Ono-Sendai 5y ago

nullc 5y ago

Here is an enjoyable classic work connecting cryptography to complexity theory, in the abstract: https://stuff.mit.edu/afs/sipb/project/reading-group/past-readings/2009-06-08-five-worlds.pdf https://stuff.mit.edu/afs/sipb/project/reading-group/past-re...

gnull 5y ago

Identifying the connection between one-way functions and Kolmogorov complexity is truly impressive. But the article oversimplified a few things that may be misleading for someone. 1. One-way functions are not all cryptography. Some constructions may need stronger assumptions than one-way functions (we don't know yet if they do). So this problem is a “Master Problem” only for a subset of cryptography (symmetric encryption, pseudorandom generators, etc.). 2. This is not the first “Master Problem” to base one-way functions on. There's Levin's complete one way function [1; Section 4.3]. Breaking it is proven to be as hard as any other one-way function, in other words if there exist one-way functions then this is one of them. But Levin's construction is somewhat artificial (it combines many one-way function candidates to create the “master one-way function”) and is not as surprising since its techniques and formulation are similar to how the usual one-way functions are defined. The connection from the linked article, on the other hand, is very surprising and unusual; it connects one-way functions to a more distant field which (to me) seems to be operating with quite different concepts. It's also fun to know that similar “Master Problems” exist for other primitives too. For example, for public-key encryption there's a Complete Public Key cryptosystem [2]. Albeit this one is similar in spirit to Levin's construction (not as surprising IMO as the linked article), the complete cryptosystem is obtained by combining many other cryptosystems. [1]: https://arxiv.org/abs/cs/0012023 https://arxiv.org/abs/cs/0012023 [2]: https://eccc.weizmann.ac.il//eccc-reports/2006/TR06-046/index.html https://eccc.weizmann.ac.il//eccc-reports/2006/TR06-046/inde...

eru 5y ago
You say: > 1. One-way functions are not all cryptography. The article says: > Today, the internet protocols for tasks like transmitting credit card numbers and digital signatures depend on these functions. “Most of the crypto that is used in the real world is something that can be based on one-way functions,” said Yuval Ishai, a cryptographer at the Technion in Haifa, Israel. Looks like they alreadyd mentioned that?
- gnull 5y ago
  Yes, I realized I made some rushed conclusions there.

knowsuchagency 5y ago

naming things?

lucb1e 5y ago
cache invalidation?

denton-scratch 5y ago

The bit I don't get: The time-bounded Kolmogorov complexity is an approximation. But it seems to be being used to prove that cryptography based on one-way functions is/isn't possible. It's not obvious to this grandstanding ignoramus that the approximation taints the proof; nor that it doesn't. I just prefer proofs that don't include approximations.

pishpash 5y ago
It's not an approximation, it defines a variant version of the problem that makes sense in the context of practical computation.
derbOac 5y ago
In another paper they imply that the time bound also effectively bounds the solvability of the one-way function. So, without the bound you say "can Kolmogorov complexity be calculated?", which implies "given infinite time can you solve this one-way function?" With the bound, it's saying "given this time limit to calculating Kolmogorov complexity, can the one-way function be solved within a directly related time limit?" The assumption is that practically speaking it doesn't matter if the one-way function can be solved in millions of eons, so a corresponding time bound is acceptable.

jtsiskin 5y ago

This makes sense, intuitively; if I gave you "8f434346648f6b96df89dda901c5176b10a6d83961dd3c1ac88b59b2dc327aa4" (sha256('hi')), and you quickly told me its K complexity was 2, I would become skeptical that sha256 was a one way function. (assuming of course you didn't brute force it)

rogers18445 5y ago
The correct analogy would be suppose I give you a block of an encrypted uncompressed image. And you return K(encryption_algo_with_key) + K(image_compression_algo_with_compressed_image)
mxkopy 5y ago
My intuition was this: Take a sequence of operations (AND, OR, NOT) and assign each unique term a prime, then multiply each term by some other prime raised to their respective position in the sequence. Call the result the 'output'. This kinda feels like running a program. Now, try and work out, for any given output, the sequence of minimum operations & their order that would get that output. Basically you factor, which is a common 'one-way' function from my understanding. P.S. I feel like the multiplied sequence of operations is a program, but then adding some input (encoded as a number) to that is closer to actually running the program. Then, for every output you have a unique program P with input 0 that gives you that output, but P isn't necessarily tied to the structure of the original program that generated that specific output.
p1mrx 5y ago
2 would be the wrong answer here, because K-complexity includes the definition of sha256 itself.
- lisper 5y ago
  This is a very good point and very important to understand. K-complexity is measured in terms of how many bits you need to specify a Turing machine (under some encoding) that computes the function. There are therefore only four functions whose K-complexity is 2. An important ancillary result is Chaitin's theorem, which is that beyond a certain threshold (a few hundred bits) it is not possible to know the K-complexity of a function because if you did then you could solve the halting problem. See [1] for a simple proof. [1] https://flownet.com/ron/chaitin.html https://flownet.com/ron/chaitin.html

kevinwang 5y ago

The article doesn't mention the date, but it appears the result in question is from 2020 (based on the arxiv paper).

Xcelerate 5y ago

> suppose you’ve set your sights on a less lofty goal than calculating the exact time-bounded Kolmogorov complexity of every possible string — suppose you’re content to calculate it approximately, and just for most strings. If there’s an efficient way to do this, Liu and Pass showed, then true one-way functions cannot exist. In that case, all our candidate one-way functions would be instantly breakable, not just in theory but in practice. Wow, this discovery seems to have really deep implications for the limits of artificial general intelligence, but I don’t have quite enough background in the field to make a formal mathematical connection. At first glance, this seems to imply: cryptography or AIXItl, choose one. Anyone working in the field have more insight on this paper’s potential AGI implications?

contravariant 5y ago
Not sure why the intelligence being artificial is needed for these implications? Though I don't really follow you reasoning anyway, you would expect a general intelligence to be able to estimate the exact Kolmogorov complexity of nigh everything?
pas 5y ago
Isn't there other formulations of AGI that don't rely on Solomonoff induction (which relies on Kolgomorov complexity)? Furthermore humans are already general intelligences, and worst case it's possible to do whole brain emulation, and then optimize that.
- ravi-delia 5y ago
  I'm much much more of a pure math than CS person, but I've stopped in on more than a few lectures. The impression I get is that Solomonoff Induction was already an upper bound. This just makes it a strict upper bound (assuming we believe one-way functions exist, which I think we do). It seems fairly intuitive that you wouldn't be able to even approach the peak in reasonable computational time, and I don't think most people working this angle disagreed.

torotonnato 5y ago

Tangential: Marcus Hutter's AIXI model popped in my head. The hardness of the time-bounded Kolmogorov complexity is also tied to the maximum intelligence of his universal AIXI agents. So, in an universe where one-way functions exist, the best agents can have privacy, but are rationally more limited than their cousins that live in a universe without OWFs. Makes sense? One property, two consequences. (I'm not talking about quantum cryptography, which I know even less than the usual one)

ravi-delia 5y ago
I think that seems basically logical, though I suspect there's a sort of peak of agency towards the middle of rationality. Like, if you had a planning oracle you wouldn't be an agent anymore, even if you were perfectly rational. That matches my intuitions, it seems like agentness is tied to complexity anyway.