The existence of true one-way functions depends on Kolmogorov complexity | Hacker News Reader

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

quantamagazine.org

439 pointstheafh198 comments

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

[2]: https://eccc.weizmann.ac.il//eccc-reports/2006/TR06-046/inde...

> 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.

So you could refer to Levin's complete OWF as "one-way-function-inversion-complete"? And, since one-way functions are, by construction, the hardest to invert, it's function-inversion-complete?

Edit: Wait, I guess the second part wouldn't follow, because OWFs only include functions that are easy in the forward direction, so they don't necessarily cover functions that are hard in both directions.

And one-way functions are not necessarily the hardest to invert. They are, in some sense, "hard enough", at least as hard as certain threshold (speaking informally).

What I meant was, the set of OWFs includes the upper bound on inversion difficulty (for functions easy in the forward direction) -- that is, you cannot remove a function from the set of OWFs by making it harder to invert (while preserving forward-direction-easiness).

> There's Levin's complete one way function [1; Section 4.3].

I think the article also mentions this:

> But his construction was “very artificial,” said Eric Allender, a computer scientist at Rutgers University. It is “not something anybody would have studied for any reason other than to get a result like that.”

But as a layman to cryptography I don't get what is the significant difference between this finding and Levin's. Is there anyone who can explain this to someone with an undergraduate level of mathematical backgrounds?

> But as a layman to cryptography I don't get what is the significant difference between this finding and Levin's. Is there anyone who can explain this to someone with an undergraduate level of mathematical backgrounds?

Here's a massive simplification. Let's say you tell me "Here's a conjecture: since multiplying 2x3 is hard, multiplying any combination of two numbers from 1-5 is hard. I can't prove that it is hard, but if all of them are hard, then my cryptography works!"

Levin's complete function approach : "Here's a function that's at least as hard as any given combination of two numbers: (1x2) + (1x2) + (1x3) + (1x4) + (1x5) + (2x3) + (2x4)... [and so on]. If that turns out to be easy, than your conjecture is wrong!"

The article states that there is a novel and surprising connection: "Proving the difficulty of multiplying any random combination of numbers under 5 is equivalent to solving this seemingly unrelated (and as yet unsolved) problem in geometry."

The two approaches are pretty different and have very different ramifications. While in a lot of cases, the approach of "here's an equivalent problem" doesn't actually help, in some cases it turns out that the equivalent problem is easier to solve. Or that the connection between the two opens up completely new approaches to solutions - or even applications of the math involved. Sometimes just the proof itself causes new connections! Often it takes considerable time before the impacts show themselves.

> I think the article also mentions this

My bad, I didn't read the article carefully enough.

> I don't get what is the significant difference between this finding and Levin's.

I think it's generally very important to find connections between distant and seemingly unrelated fields. And it's even better to express two seemingly separate fields in the same terms. Because then there's a lot of potential to cross apply the techniques which were developed in those fields. You can see the linked result not only as a formal construction of a problem with certain properties, but also as a link between two distant fields and as one of the many steps needed to maybe one day show that those fields are the same thing. One of my theoretician friends likes to say that solutions in mathematics are valuable because of the "moral" they have, i.e. the possibilities and lessons they demonstrate, not because they formally satisfy some conditions.

Think of Physics, Chemistry and Biology. Centuries ago they were completely separate fields. A growing plant and a lightning bolt were completely different concepts which seemed to be operated by their own distinct laws and have nothing to do with each other. But as the Science progressed, people learned about the elemental particles and could see now that lightning bolt and a plant are not separate concepts, but only manifestations of the same laws and processes on lower levels. Now Physics, Chemistry and Biology are not completely distinct domains (Richard Feynman would argue that the latter two are sub-fields of Physics) and techniques and findings from one can be sometimes converted to the others.

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?

Yes, I realized I made some rushed conclusions there.

No worries. The rest of your comment was very informative!

Has this paper actually found anything meaningful or just engaged in sophistry? So instead of using a Turing machine to compute the Kolmogorov complexity where you face the halting problem and uncomputability, they use a time-bounded Turing machine to compute the time-bounded Kolmogorov complexity where you face the hardness of one-way functions.

Yes, constructing a one-way function out of a computation of Kolmogorov complexity is interesting, but frankly it would appear that it is the possible existence of one-way functions (i.e. hard computations) that is more fundamental, just like the uncomputability of the halting problem is more fundamental, not the wrapper that is Kolmogorov complexity.

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

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?

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)

2 would be the wrong answer here, because K-complexity includes the definition of sha256 itself.

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

Which four functions?

00,01,10,11

That would depend heavily on the encoding used for your turning machine.

You probably mean a Dervish turning machine, with a halting problem?

That article was incredibly good, especially the digression on determinism with Einstein, Born and Pauli.

I feel like synchronicity just boils down to the pigeonhole principle.

> Chaitin's theorem

That's already mentioned in the original article.

> 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 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)

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.

"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.

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?

> 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.

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.

> 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.

Recall that in the CCA experiment, the decryption oracle uses the same key as the message in your challenge ciphertext.

Is it really an OTP if you have an oracle that uses the same key? By definition of OTP, such an oracle should not exist, right?

It’s an oracle, we allow it to exist for the experiment.

Then it’s not an oracle of OTP, but an oracle of a single-key XOR.

If an encryption scheme cannot have an oracle by definition, then it automatically passes all tests which requires the attacker to access an oracle.

Just like my wooden pencil is not vulnerable to stack overflow attacks.

Any encryption scheme may have an oracle by definition of oracle. You’re (possibly intentionally) changing the situation by refusing to allow OTP to be an actual encryption scheme.

Here is a blog post that summarizes some facts about Vernan’s OTP as it is defined in cryptography: https://wiki.soimort.org/crypto/one-time-pad/

Regardless, this is a silly discussion with nothing to be gained by me.

Well, my bad to have wasted your time with a silly discussion, then. I find it neither silly nor gain-less. I'm sorry that you feel differently.

I meant that it’s all pretty trivial business, focusing on the technicalities of what oracle is used in what security experiment.

Although if you were previously unfamiliar with the definitions at play I apologize for calling an informative discussion gain-less.

The important part being that what makes a one time pad secure from this attack is that it is in fact, one time. If you re-use your keystream, well, it's not a one time pad.

That's not true. OTPs are vulnerable to adaptive chosen-ciphertext attacks, and don't satisfy IND-CCA2. This means the malleability allows learning the contents of the ciphertext.

Recall that IND-CCA2 says "given encryption and decryption oracles, can the adversary figure out the contents of a challenge ciphertext".

In the OTP case, the adversary proceeds as follows. Upon receiving the challenge ciphertext c = b xor r, where r is a random bit, it computes c' = 1 xor c = (1 xor b) xor r. It then asks for a decryption b' of c'. If b' = 1, then the adversary knows that 1 = 1 xor b => b = 0. If b' = 0, then adversary knows that 0 = 1 xor b => b = 1. So it learns the value of b without breaking the security of the OTP.

This assumes that the same random bit r is used to encrypt c' and c, but there's no way for the challenger to force different bits.

I think that is a bit of a stretch, as an OTP isn't maybe a "scheme" in the sense of IND-CCA2 and the attacker cannot force an encryption to happen by design.

Let's assume a game where Alice and Bob are two military generals using One-Time Pads to encrypt a message and Mallory wants to confuse them.

  Alice -> Encrypt("RETREAT", Pad[128:7])

You intercept this message and you're not sure if it means "RETREAT" or "ADVANCE". But contextually, you know it's one of the two, and you want to sew confusion.

  Mallory -> XOR(Ciphertext, XOR("RETREAT", "ADVANCE")) -> Bob

And then Bob reads this message as the opposite of what Alice sent.

  Bob -> Decrypt(Cipher2, Pad[128:7])

Thus, the lack of ciphertext integrity allowed Mallory to gain an advantage in her goal as an attacker to sew confusion between two generals. If Alice advances, Bob retreats, and vice versa.

It doesn't really matter, to this security game, if you learn anything about the key from the malleability. You chose the ciphertext, and thus you succeeded in dividing their military force.

Yes, but it also means you knew a lot about the clear text to do this.

I don't think that there is dispute that malleability is an issue in OTPs. What is also not in dispute is that the message itself is secure against decryption absent other knowledge.

The point that is made (and in other posts) is that on its own, OTP isn't enough in most situations - and I agree with that.

> The point that is made (and in other posts) is that on its own, OTP isn't enough in most situations - and I agree with that.

Yes, and that's all I'm saying here.

I deal with real-world cryptography. I'm not a theoretical or academic cryptographer. If someone deployed an OTP in a system I'm responsible for, I'd escalate until they use an AEAD instead.

Couldn't Alice just repeat the plaintext many times (number agreed in advance when she shared the OTP), split it into bits, label each bit with a sequence number, shuffle all the labelled bits, then encrypt?

Then Bob can decrypt, split the message into labelled bits, and sort by sequence number. If any any of the repetitions of the message differ then it was tampered with.

At that point you might as well use a MAC.

You have to trust a hash function to do that, which doesn't seem likely if you require a one time pad.

A variation on this would be: For each bit of the message take the next bit from the pad. If the bit is 0 then take a second bit from the pad and send it, then take a third bit, XOR it with the message, and send that. If the first bit is 1 then swap the order: take a second bit from the pad, XOR it with the message, and send that, then take a third bit from the pad and send it verbatim. The first bit is not transmitted. For decryption you do the same in reverse, checking that the verbatim pad bits match your copy of the pad.

This requires three times as much pad as regular OTP for the same plaintext, and the ciphertext is also twice as large, but it doesn't depend on any hash functions, all bits remain independent, and an attacker has no way to know which half of the ciphertext makes up the message. Any N-bit change in the ciphertext will have a ((2*N)-1)/(2*N) chance of being detected on the receiving side (50% for one bit, 75% for two bits, …).

Of course, if you are willing to trust message authentication codes something like OTP(pad1, message + MAC(pad2, message)) will be more efficient and has a higher chance of detecting tampering, especially for smaller numbers of bits.

Hm... wouldn't the dead simple pattern of "RRRRREEEEETTTTTRRRRREEEEEAAAAATTTTT" in the message defeat the attempt to sow confusion?

To be clear-- the parties agree ahead of time that each message will consist of repeating each desired letter in the message N times (before encrypting). If there's a letter that doesn't repeat N times in the received message then the message isn't authentic.

Surely a cryptographer could figure out the math to make N large enough that the probability of defeating the authentication is practically equivalent to guessing the message itself.

Hm... I guess if the attacker knows N=5 they could just send truncated text.

Is there really no dead simple authentication scheme that is as easy to understand as OTP, which can be used with OTP?

Edit: clarification

Would you be a bit better off if N is to be inferred from the decrypted text, and Alice rolls a die to pick it?

I'm just surprised that there isn't some bog standard authentication puzzle piece that goes with learning OTPs.

This doesn't work if the attacker knows the repeating pattern is going to be used, and if they know it's going to be either "ADVANCE" or "RETREAT" then it seems likely they will also know about the repeating pattern.

They can still invert the meaning by XORing the cyphertext with XOR("RRRRREEEEETTTTTRRRRREEEEEAAAAATTTTT","AAAAADDDDDVVVVVAAAAANNNNNCCCCCEEEEE").

Thanks, I just realized that in my comment below. See additional question there...

If you combine that with a one-time-signature, and add the overall sha256 to the end of the message, will that be secure against such manipulation?

Something like

    Encrypt("RETREAT" + sha256("RETREAT" + SignaturePad[128:7]), KeyPad[128:7])

It’s not even IND-CCA1 secure. You only need one access to the decryption oracle to determine the key before the challenge ciphertext. Just encrypt all 0 bits.

Yes, OTPs are vulnerable if you do the one thing that you're not supposed to do with a OTP, namely reuse the bits.

The question for OTPs is whether there is an encryption or decryption oracle for a given OTP, not whether OTPs are vulnerable to such oracles.

OTPs are vulnerable if you do the one thing that you're not supposed to do with a OTP, namely reuse the bits.

YES. "One time" means "ONE TIME". Use once and destroy. The one time pad must be random, generated by a true random process. Not pseudorandom. Not generated by an algorithm. Not generated from a shorter key. Not reused. Not generated by humans hammering on typewriters (see Venona).

One time keys are used for some crucial point to point links. Embassy to foreign ministry, higher military headquarters to high command, or spy to HQ.

> One time keys are used for some crucial point to point links. Embassy to foreign ministry, higher military headquarters to high command, or spy to HQ.

I am very skeptical this actually used in practice anywhere. The one-time pad is prone to side-channel attacks, since sharing the secret key(s) is such a nightmare. Putting people on planes flying around the globe with bags full of keys or having long lists of keys lying around is a security nightmare. Using an asymmetric encryption scheme is in practice a lot safer.

Declassified NSA documents describe some of the systems.[1] Early systems used paper tapes for the key. One of the features was a tape slitter, so the tape could only be used one time before it was cut in half. Systems with floppy disks have been advertised. Mils Electronik sold one time key systems from the 1950s until 2017.[2] Early systems used paper tape, later systems were electronic and stored the keying material on PCMCIA cards.

[1] https://www.nsa.gov/portals/75/documents/news-features/decla...

[2] https://cryptomuseum.com/manuf/mils/index.htm

The point is that with OTP in the IND-CCA2 game you can force the challenger to reuse keys

And this translates to any real world scenario too.

If your scenario involves reusing keys then what you are breaking is not a one-time pad.

You're showing that if you implement something vaguely similar to OTP, but lacking the one element that makes OTP secure, it fails the IND-CCA2 game. Which is really pretty obvious when you think about it since OTP minus the critical "one time" element is just repeated XOR with a fixed key, which is barely stronger than ROT-13.

I understand "the point" - the problem is that said "point" isn't gospel/unquestionable.

Forcing a challenger to reuse keys is not possible in every real-world scenario. Or rather, there are real-world scenarios where keys aren't/can't be reused. An evaluation criteria that assumes/requires otherwise is broken.

If we're going to allow any game, then every encryption system is broken in my game, which requires that the keys and method be made available to the challenger.

I guess what I’m trying to say is that the length issues with OTP mean that it can’t be used in any scenario that requires even a weak form of non-malleability. Maybe you could try to do something with universal hashes, but it’s unclear.

You only end up with length issues if you don't use a big enough pad.

Just use a one-time pad that is uncountably infinite in length and require messages to be at most countably infinite in length. Sure you burn infinite bits on each message, but you'll never run out or reuse bits in the pad.

How do you get both sides to have the same infinite random pad?

I thought the whole problem with one time pads was that they had to be distributed to the other side physically and thus were always finite.

Sarcasm...

> How do you get both sides to have the same infinite random pad?

With Quantum Key Distribution both sides have access to identical streams of random bits not available to anyone else.

Without invoking quantum mechanics, you can just treat the portion of the pad you have on hand as a prefix of an infinitely long pad which is being delivered incrementally. If you run out of pad bits you just pause and wait for someone to hand-deliver a new set of identical storage devices to both parties with the next segment of the pad. This is the same principle behind treating physical computers as "Turing complete" when a Turing machine is technically defined to include an infinitely-long tape—you can always extend the system with more storage as needed.

Malleable or not is a function property that doesn't make sense for OTPs. The problem is that while a OTP's outputs are determined by its inputs, a OTP's inputs are always different.

That said, a one time pads are non-malleable if you don't reuse the bits (and the bits are truly random). If you do reuse the bits, it's not a one time pad.

That said, there are no length issues with a One Time Pad.

Or rather, the length issue with one-time-pads is that you can't reuse pad bits, not just within a given message but across all messages that ever use that pad, hence the name ONE TIME Pad.

One time pads are necessarily as large as the data to be encrypted. (You might be able to get away with some fraction of the total number of "to encrypt" bits, but you can't reuse them.) Schemes which reuse "encryption bits" do not have that limit and are much smaller.

One issue wrt malleability is whether/how one can recognize that a cyphertext or a plaintext is "valid".

If you just xor with a OTP (which means that every cryptotext is valid) and every plaintext is valid, the receiver can't look at the cyphertext or the plaintext and recognize whether a MITM modified the message.

However, the same is true of any crypto system where every cryptotext and plaintext is valid.

However, if there's some way to recognize/distinguish valid plaintext, OTPs are non-malleable.

> It then asks for a decryption b' of c'.

If you can do that, why not just ask this "oracle" for a decryption b of c, i.e. to decrypt the original ciphertext? Either way you're basically asking for a copy of the pad since you can trivially derive that from any plaintext/ciphertext pair. The idea that anyone would just give you the decryption of an arbitrary message of your choosing using their supposedly secure one-time pad is a bit bizarre. You've already broken the security rules of the OTP well before you get to the point of calculating b from b'.

It is vulnerable to chosen cipher text attacks.

Give me a one time pad cipher text c of length n and a decryption oracle Dec(). Then the key k = Dec(0^n) and I can easily tell you that the message is c xor k.

Assuming you have the Decryption oracle is the same as assuming you have the key in your example, so you are just saying a OTP is vulnerable if you have the key. This is true for any encryption scheme that I can think of.

This is not generally true. You can easily imagine a cryptosystem where having a decryption Oracle does not give the key.

The fact that it is so easy to get the key given a decryption oracle for OTP just tells us that it’s really easy to show that it’s not CCA secure. The definition of CCA secure allows a decryption oracle with the same key as the challenge ciphertext.

Being a one-time pad makes it irrelevant if you get the key. So it’s CCA secure because you never reuse the pad. You’ve gathered no useful information, ie you’ve only gathered noise that has no use.

It is not CCA secure because an adversary with access to a decryption oracle may get the key that was used to encrypt a challenge ciphertext via the method I’ve described.

In the CCA experiment, the oracle uses the same key as the challenge ciphertext.

But the OTP is still secure against that attack because the “key” is never reused. It is literally just noise, no useful information whatsoever.

It isn’t secure against the attack because the oracle uses the same key.

The oracle is a tool used to formalize our definition. You’re right that the fact that OTP isn’t CCA secure doesn’t matter in practice because the key is only used for one message so such an oracle doesn’t generally exist.

No, Dec(0^n) would give you a unique keystream never used before or since. That is the whole point of the >>one-time<< pad.

No, in the CCA experiment the Dec() oracle uses the same key.

Even if you make this assumption it still wouldn't be a successful attack because OTP makes no security claims if the key is re-used. If there's no security claim there's nothing to attack to begin with.

It would still be a successful attack for the purposes of the definition of CCA secure.

In the CCA experiment, an attacker is given access to a decryption oracle that has used the same key as the challenge message.

The definition of CCA is then simply incompatible with the definition of an OTP. Making the question wether OTP is vulnerable to CCA meaningless.

That’s not true at all.

You can make an oracle for whatever you want. That’s why it’s an oracle.

It absolutely is true.

I can declare that my "brazzy attack" involves an oracle that for any given cipher text gives me the key it was encrypted with. Wow, all modern ciphers are vulnerable to it, the only thing that resists it is keeping the algorithm secret!

Just because you can think of something doesn't mean it makes sense.

I’m not sure what point you were trying to make. I think you accidentally made the opposite point. Indeed your definition would imply that all modern ciphers are not Brazzy-secure. I’m not sure why this matters to you.

No one is saying that the fact that OTP cipher is not CCA secure is practically relevant.

But the fact of the matter is that a cryptosystem being CCA secure is defined as we discussed and the OTP cipher does not meet the requirements.

I think we're largely in agreement then, but I still believe that it makes more sense to say that the definitions of OTP and CCA are incompatible and therefore it's just meaningless to apply one to the other.

"The same key" in the context of OTP means the same pad… all the key material shared between the sender and recipient. However, every encryption with that pad must use a different part of the pad or it isn't OTP at all. Not reusing bits from the key material is the defining characteristic of the One-Time Pad.

The only reasonable formulation of IND-CPA, IND-CCA1, or IND-CCA2 for OTP involves the encryption and decryption oracles using a unique subset of the pad for each plaintext. That's part of the cryptosystem definition, much like the selection of unique, random nonce values. When put in those terms, the encryption and decryption oracles can only ever reveal the parts of the pad used to encrypt the adversaries' chosen plaintext, which doesn't provide any information which could be used to decrypt any other ciphertext, so OTP easily passes all three tests.

You’re mistaken. CCA has a formal definition that may not match with your expectation, but in the definition of CCA, the same key that is used to encrypt the challenge message is used for the decryption oracle.

Is there a point to arguing whether a system is CCA secure if the 'formal definition' uses the system in an explicitly wrong way?

Especially if there is a trivial modification of the 'formal definition' that better matches the intention and allows for results that apply to reality?

Of course there is the question of whether the modification is trivial, and whether the modification changes CCA meaningfully for other systems. But argue about that, whether a definition modification changes past results using that definition. Just stating 'that is not the formal definition' if the formal definition gets criticism and an alternative is suggested, is not really good-faith engagement with criticism.

Is there a point? Probably not. I’m just saying that as a matter of fact, OTP is not CCA secure.

It may be secure under whatever alternative notions you’re proposing, but they’re not standard.

The point is that CCA is not applicable to one time pad. All you're saying is that OTP is not secure if you know the key. It doesn't matter what terms you use to describe it. It just doesn't mean anything beyond that.

I wouldn't go so far as to say that IND-CPA/CCA1/CCA2 aren't applicable. The fundamental error l33t2328 is making lies in mistaking the part of the pad used to encrypt a particular plaintext with the entire "key" which must remain constant. That makes zero sense in the context of a one-time pad, and as you said if the rules are misinterpreted that way it just makes the IND tests meaningless for OTP. Even for other algorithms it's typical to have some element which must be unique for each plaintext (e.g. a nonce or initialization vector) for the system's security properties to hold. For OTP that varying component just happens to be the specific region of the pad used for the encryption. The entire pad is the key. This perfectly satisfies the requirements of the formal definition, as the pad is shared in advance and does not vary, while the portion to be used for a given plaintext is chosen during encryption and does not need to be kept secret.

> The fundamental error l33t2328 is making lies in mistaking the part of the pad used to encrypt a particular plaintext with the entire "key" which must remain constant.

This is no error. The distinction you are making is nonsense. Indeed, given the key k and a message m, the basic correctness requirement of a crypto-system demands that dec_k(enc_k(m)) = m.

How on earth is this decryption to be done under your assumption that only some part of the pad was used?

The entire pad is the key.

First, to get this out of the way, there is no meaningful sense in which OTP fails any of these IND-CPA/CCA1/CCA2 games. Depending on how you formulate the preconditions, either the games are simply not applicable to OTP and the result is nonsense, as any implementation which satisfied requirements for encryption and decryption oracles which reuse the same bits of the pad for multiple plaintexts would not be OTP, or OTP passes the tests with flying colors. Personally I don't think the former is worth discussing—as it amounts to an attacker already having a full copy of the pad—so I'll be limiting my response to the version that actually makes sense.

> the basic correctness requirement of a crypto-system demands that dec_k(enc_k(m)) = m

Indeed. For OTP you have a bitstream k which is the entire pad, large enough to provide one bit of pad for every bit of plaintext you might ever want to encrypt. enc_k(m) is defined as taking the next length(m) unused bits from the pad, which I'll call k[m], and calculating the ciphertext (c) as (k[m] XOR m, i) where i is the index of k[m] within the pad. (In some systems the starting index would be implicit but then you can't lose or reorder messages, which isn't really compatible with the concept of oracles.) These bits k[m] are then effectively destroyed in the sender's copy of the pad, never to be used again. dec_k(m) is exactly the same process, including the destruction of the used bits, but using the recipient's copy of the pad.

(Yes, this means enc_k and dec_k carry some extra implicit state and are not simply functions in (k × m) → c; this is a strict requirement to count as an implementation of OTP. If you aren't doing at least this much, especially including the part about never reusing bits from the pad on either the sending or receiving side, you don't have an OTP system.)

So dec_k(enc_k(m)) = m, but k[m] is different for each m—and knowing m and enc_k(m) tells you k[m] for that message, the one supplied by the attacker, but nothing about any other message. The attacker might as well be using their own distinct pad rather than the provided encryption & decryption oracles for all the good this does them.

> The entire pad is the key.

At least we agree on something. The key for which encryption & decryption oracles must be provided is indeed the entire pad, not just the part used for one particular message.

> there is no meaningful sense in which OTP fails any of these IND-CPA/CCA1/CCA2 games

That’s factually wrong. A CCA oracle can easily determine the key.

> enc_k(m) is defined as taking the next length(m) unused bits from the pad

No, it is not. It’s defined as m \xor k.

You are describing another cipher, but not Vernan’s OTP.

> Yes, this means enc_k and dec_k carry some extra implicit state and are not simply functions in (k × m) → c

Then you aren’t describing an encryption and decryption function. Those depend only on k and m.

Someone must be able to have the algorithm and the key and decrypt any message. Your “hidden state” cannot(and indeed should not) be a part of the algorithm as it violates the principle of kerckhoff.

Stepping out of the theoretical for a moment, your proposed scheme also makes no sense in reality. How am I to know what part of the pad you’re using if I’m in a bunker picking up your encrypted signal?

re edit 2: a fair number probably loaded the page a while ago and hadn't seen the edit. e.g. I sometimes open a dozen or so tabs at once and then wander through them through the day when I feel like it.

  > 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.

I think they're assuming space efficiency. The article dances around the issue a lot, but doesn't actually say that.

After all, you can convert any function to a time bounded one by writing down a table with the inputs and outputs.

It’s hardly narrow if it includes 99% of crypto in deployment.

They are talking about asymmetric encryption, which is what you always need when communicated with someone else. Symmetric encryptions like AES also work without one-way functions.

No, the security of AES assumes that AES is an one-way function. Otherwise, if AES is not one-way, one could decrypt it easily reversing the function. Symmetric encryption usually assumes the existence of one-way functions, but there are indeed some rare exceptions. The one-time pad is a construction with unconditional security and is secure even if one-way functions do not exist. Of course, it requires the assumption that each person will not reuse the key more than once. And without one-way functions, you also would never be able to exchange the keys securely using any computer network.

But you can reverse AES! You obviously need the secret key, but it's trivial to reverse the steps of encryption (it's actually a bit tricky to get all the steps correctly, but you can easily google how to do it, tons of example impelentations and lecture notes online).

There are a bunch of online tools that demonstrate it such as: https://www.devglan.com/online-tools/aes-encryption-decrypti...

Aes is a one-way function if you consider the key part of the arguments to the function.

One requirement for one way functions is to not easily find a preimage. With AES output you could decrypt it with a wrong key, get wrong plaintext, but they're still a valid input combination giving this same AES output

Different key = different function, so you have not inverted the original function and thus have not found a preimage.

Fair point!

I guess it's a one-way function given only the key as input with a fixed ciphertext.

Incidentally if you use AES in a AED mode (like AES gcm) then it would be a one-way function but that is more about the MAC.

Actually they aren't talking about asymmetric/public-key encryption, but rather "efficient" symmetric encryption (and related primitives) where the key size is (asymptotically) smaller than the plaintext size.

> 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.

The security of OTP is much more restricted than most cryptography books admit.

OTP's security can be proved in the following cases:

* the set of secrets (plaintexts) is finite,

* the set of secrets (plaintexts) is the uncountable sets of streams, say, N -> {0,1}.

What one is interested in for cryptography is if the set of secrets is a countable domain, say the a set of strings (e.g. {0,1}^*).

Bad news:

"[N]o perfect private-key encryption schemes, over the set of all strings, exist. Stated informally, this means that there is no way to perfectly encrypt all strings without revealing information about their length."

This quote is taken from the abstract of

Chor, B., Kushilevitz, E. Secret sharing over infinite domains. J. Cryptology 6, 87–95 (1993). https://doi.org/10.1007/BF02620136

> https://link.springer.com/article/10.1007/BF02620136 (website of paper)

> https://link.springer.com/content/pdf/10.1007/BF02620136.pdf (PDF)

Isn't leaking the length pretty harmless? You can make that leak arbitrarily small by adding randomized amounts of padding with various distributions as well, right?

> Isn't leaking the length pretty harmless?

Whether this is harmless or not is up to a debate. But it is a clear violation of the "information-theoretic security" property that (nearly) every textbook about cryptography mentions or proves for OTP.

Just to be clear: these proofs are correct, they just do not work when OTP is applied to a countable set of secrets - which is actually the situation that "everybody" is interested in.

Toomanysecrets.

I would argue that it is not harmless.

Let's say that you have a P2P application for sharing MP3s. There are many millions of MP3s, but if an attacker sees a download of a particular size, then they have a pretty good idea of which MP3 has been downloaded.

Well, can you tell me if you got accepted into a college based off the size of the letter you got?

Not if the college is deliberately trying to hide that information—they'll make the acceptance and rejection letters the same size.

Most systems have a finite limit to the sizes of the messages they can handle. (If nothing else there are practical limits to both the maximum transfer rate and the operators' patience.) It's inefficient, but you can pad all messages to that length regardless of the size of the plaintext.

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.

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

"...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?

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.

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.

No, that’s not true. Plenty of cryptography is asymptotic.

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.

Sure if you want to be pedantic. However even if you double the number of rounds, the number of operations required to brute force increases by only a factor of 2. Since the number of operations is likely to be a very large number already, such a change is insignificant and we can consider the brute force cost to be independent of the number of rounds which is usually a small integer.

The only difference between 1 and 2^128 is 128 small constant factors of 2.

Yes, that’s the difficult part that the research is tackling.

I believe, though I haven't done much with real complexity theory, that most feel P=BPP, and problems like the one you describe can be converted into more typical BPP problems. It's unproven, like most of the fun problems, but it's suspected.

Regardless, this definitely isn't a result with much to say about practical cryptography, and it wasn't trying to be one. Just another, very interesting link in a field with lots of "if pigs could fly" proofs.

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)

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

> 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

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.

The arms race already exists: hash sizes and standard key sizes have increased. Because Moore's Law already applies to classical computers: you effectively lose 1 bit of entropy / security every year.

I think that would be a bit every 2 years based on Moore's law after the 80's and actual progress has been slower than that for something like a decade now. There are looming fundamental physical limits.

Moore's law refers to hardware capacity and not speed. If you can't figure out how to completely parallelize your attack then that is important. And things are not getting significantly faster.

So a lot of stuff is likely to be safe indefinitely under current technological conditions. A complete breakthrough like quantum computing would be required. Makes it hard to predict things.

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.

(Also layperson, so this is based on my understanding of reading other people's material). Yes that is the case, our current one-ways, especially RSA, are considered broken by quantum computers and will be proper broken once more qubits are a reality. https://en.wikipedia.org/wiki/Shor%27s_algorithm

There are already efforts underway to replace it with something quantum safe. It's believed that lattice based cryptography will help us. https://en.wikipedia.org/wiki/Lattice-based_cryptography.

There will be updates required to a lot of infrastructure and digital assets to secure them. Some things will be simple updates, some will require moving to new wallets.

"if modern cryptography is broken": this statement has many interpretations.

In the context of the OP paper, approximately solving the t-bounded Kolmogorov complexity (in a precise technical sense described in that paper) is akin to breaking one-way functions.

A method to breaking one-way functions would in fact break all of the cryptographic schemes (enc, signatures, prgs, hashing, zero-knowledge, mpc, bitcoin...) that rely on computational assumptions that we know. There is then no hope for doing things like we do on the internet today.

A secondary interpretation relates to breaking a specific widespread cryptosystem like ECDSA or Ed25519 (which can both be broken with suitably large generic circuit quantum computers). In this context, maybe some important things break, but in principle, we can rebuild them using lattice-based schemes or something else.

Hashing would be generally be fine.

AES would still be totally okay.

I'm a layperson, but isn't hashing the quintessential one way function? (at least for industry software engineers).

/me also layman.

Hash functions are irreversible; a potentially-infinite number of inputs all map to the same output.

I think the one-way functions referred to are what used to be called trap-door functions. They're not irreversible, like hash functions; they're computationally hard to reverse, unless you happen to know the key to open the trap-door.

Even if you can’t get back to the original data you hashed, you’d still only need to pick an input length and then compute a single example that produced that hash to break all the cryptographic uses of hash functions like signatures and password storage though.

Exactly, it doesn't matter if Sqrt produces two possibilities, you gain root access by using either root, pun intended.

One-way functions are definitely not trap-door functions, they are a weaker assumption. But you can get all symmetric cryptography out of a one-way function; it doesn't have to be reversible.

For instance, you can use a hash function to encrypt, by XORing its output with a plaintext, using it as a stream cipher.

>Hash functions are irreversible; a potentially-infinite number of inputs all map to the same output.

I don't think that's pre-image resistance, or else extremely trivial "Hash functions" like

- Line up the input string into a matrix of n columns, XOR every column into a single bit, output the resulting n-bit hash.

Would be pre-image resistant, but it's obviously not. Given an n-bit hash I can trivially generate a message that hashes to it.

Generally, there are at least 3 notions of irreversiblity that might get confused:

- Non-bijectivity : That just means the set of images is smaller than the set of pre-images, so it's impossible (in general) to tell what input produced a given image. If F(x) == 1 for all x in X, it's impossible to tell which x was evaluated in order to get a 1. This is what you described, and it's - by itself - useless security-wise.

- One-way functions : Given x, its reasonably efficient to calculate y = F(x). But given y = F(x), it's prohibitively expensive to recover x = F^-1(y). The function is easy to compute in one direction, and practically impossible in the other. The inverse might very will exist, maybe even infinite inverses exist for every y, but you would need the computational resources of a thousand thousand universe working for a thousand thousand epoch to even get close to finding a single one.

- Trap-door functions : They are special one-way functions that have the property that : given a special piece of information about x or y (an inequality, a prime factor,....), x = F^-1(y) suddenly becomes much easier to compute, maybe even as easy as y = F(x).

The one way function (or trapdoor function) in a cryptography context still needs to be reversible given the decryption key so a hash won’t do.

As I mentioned in my reply to the sibling comment, a hash function is enough. For example, you could encrypt by feeding a key + block counter to a hash function and XORing the plaintext blocks with the output. The recipient with the same key can generate the same digests and XOR to decrypt.

That's not a proof, of course, it's just to give an intuition for how all symmetric cryptography can be constructed from a one-way function.

One way functions do not need to be reversible.

No and no.

If a hash function is not an one-way function, it cannot be collision-resistant.

And the security in AES assumes that it is an one-way function. Otherwise, anyone could decrypt reversing the function.

You have some slight misunderstanding.

AES does not need to be a one way function. It’s trivial to compute the preimage of a ciphertext. Just choose any key and decrypt it.

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.

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!

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)

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.

> 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?

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.

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.

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?

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

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

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

I think this is more like Impagliazzo's "Pessiland", where P!=NP but cryptography is still impossible.

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... All five worlds are still possible, given our current results. In both "Heuristica" and "Pessiland", P != NP but one-way-functions do not exist.

yeah if someone proved P != NP --> OWFs, that would be the seminal result of a generation of work in computer science theory.

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.

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.

It's not an approximation, it defines a variant version of the problem that makes sense in the context of practical computation.

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.

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.

> 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.

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

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

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).

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.

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.

K can be arbitrarily large though.

Yes, but still finite.

As in the above comment, the K constant actually bears on low-complexity strings, not high-complexity ones. It says low-complexity strings in any language are always reasonably low-complexity (within +K) in other languages, but since K can be arbitrarily large, the bound is totally loose and useless.

I think the key is that K is fixed per language, not per input. So if you have a sequence of inputs of complexity 1, 10, 100, 1000, 10000...in language L1, then in language L2, the complexities will be something like 1+K, 10+K, 100+K, 1000+K, 10000+K,.... In the limit of very-high-complexity-input (pick a random TB of data as your string) the language-specific constant is overwhelmed.

1+K, 10+K, ... are merely upper bounds on the Kolmogorov complexities in L2, but the actual complexities can be lower, by an arbitrary amount for some strings. Furthermore, what's considered complex in L1 and L2 can be very different, and although "most" strings would be complex in either language, they don't have to be the same subsets in L1 and L2.

What is the correlation between _ complexity and e.g. EVM/eWASM opcode [CPU,] costs?

https://news.ycombinator.com/item?id=28499001

> Smart contracts cost CPU usage with costed opcodes. eWASM (Ethereum WebAssembly) has costed opcodes for redundantly-executed smart contracts (that execute on n nodes of a shard) https://ewasm.readthedocs.io/en/mkdocs/determining_wasm_gas_...

> AFAIU, while there are DLTs that cost CPU, RAM, and Data storage between points in spacetime, none yet incentivize energy efficiency by varying costs depending upon whether the instructions execute on a FPGA, ASIC, CPU, GPU, TPU, or QPU?

Yes, in my view you are entirely right, Kolmogorov complexity says nothing about any complexity independent of language. The invariance theorem is true, but useless: https://forwardscattering.org/post/14

Hah, this is a very clever way of putting it. Will certainly use this thought experiment in the future! :)

This is known as the invariance theorem:

https://en.m.wikipedia.org/wiki/Kolmogorov_complexity#Invari...

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.

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

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:

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.

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

[1] https://en.wikipedia.org/wiki/Berry_paradox

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.

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.

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.

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

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.

I wish this explained it better

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

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.

TL;DR: Kolmogorov complexity.

Seems that the clickable title was changed

naming things?

cache invalidation?

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.

You would probably enjoy some of Dusko Pavlovic's work: https://arxiv.org/pdf/1109.5542.pdf

Thank you, at a glance it seems very interesting.

> #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 :)

Reply on news.ycombinator.com