[HN Gopher] The existence of true one-way functions depends on K...
___________________________________________________________________
The existence of true one-way functions depends on Kolmogorov
complexity
Author : theafh
Score : 209 points
Date : 2022-04-06 17:01 UTC (5 hours ago)
(HTM) web link (www.quantamagazine.org)
(TXT) w3m dump (www.quantamagazine.org)
| woliveirajr wrote:
| TL;DR: Kolmogorov complexity.
| torotonnato wrote:
| 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)
| abhv wrote:
| 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
| [deleted]
| [deleted]
| frankus wrote:
| "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.
| _fizz_buzz_ wrote:
| 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.
| some_furry wrote:
| 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_?
| orlp wrote:
| > 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.
| Ar-Curunir wrote:
| 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.
| nybble41 wrote:
| > 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'.
| l33t2328 wrote:
| 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.
| [deleted]
| anamax wrote:
| 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.
| Ar-Curunir wrote:
| 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.
| nybble41 wrote:
| 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.
| Animats wrote:
| _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.
| RandomLensman wrote:
| 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.
| some_furry wrote:
| 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.
| jancsika wrote:
| 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.
| jancsika wrote:
| 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
| mrob wrote:
| 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").
| jancsika wrote:
| Thanks, I just realized that in my comment below. See
| additional question there...
| mrob wrote:
| 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.
| powersnail wrote:
| 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])
| RandomLensman wrote:
| 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.
| some_furry wrote:
| > 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.
| some_furry wrote:
| 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 wrote:
| > 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.
| [deleted]
| buildbot wrote:
| 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.
| l33t2328 wrote:
| Recall that in the CCA experiment, the decryption oracle
| uses the same key as the message in your challenge
| ciphertext.
| powersnail wrote:
| 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?
| l33t2328 wrote:
| 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.
| orlp wrote:
| 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.
| l33t2328 wrote:
| No, in the CCA experiment the Dec() oracle uses the same
| key.
| orlp wrote:
| 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.
| nybble41 wrote:
| "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.
| kickling wrote:
| 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.
| [deleted]
| Groxx wrote:
| 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.
| q-big wrote:
| > 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)
| Ar-Curunir wrote:
| It's hardly narrow if it includes 99% of crypto in deployment.
| hedora wrote:
| 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.
| gnull wrote:
| 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...
| user677 wrote:
| summerlight wrote:
| > 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?
| SilasX wrote:
| > 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.
| praptak wrote:
| 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.
| zarzavat wrote:
| 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.
| MauranKilom wrote:
| 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.
| zarzavat wrote:
| 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.
| naniwaduni wrote:
| The only difference between 1 and 2^128 is 128 small
| constant factors of 2.
| Ar-Curunir wrote:
| No, that's not true. Plenty of cryptography is asymptotic.
| Ar-Curunir wrote:
| Yes, that's the difficult part that the research is tackling.
| achenet wrote:
| Isn't Kolmogorov Complexity hard to measure, because it depends
| on the language chosen?
| tromp wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| K can be arbitrarily large though.
| dvt wrote:
| Yes, but still finite.
| pishpash wrote:
| 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.
| isotropy wrote:
| 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.
| pishpash wrote:
| 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.
| dvt wrote:
| Hah, this is a very clever way of putting it. Will certainly
| use this thought experiment in the future! :)
| Xcelerate wrote:
| This is known as the invariance theorem:
|
| https://en.m.wikipedia.org/wiki/Kolmogorov_complexity#Invari.
| ..
| knowsuchagency wrote:
| naming things?
| lucb1e wrote:
| cache invalidation?
| denton-scratch wrote:
| 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 wrote:
| It's not an approximation, it defines a variant version of the
| problem that makes sense in the context of practical
| computation.
| Xcelerate wrote:
| > 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?
| pas wrote:
| 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.
| nullc wrote:
| 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...
| kevinwang wrote:
| The article doesn't mention the date, but it appears the result
| in question is from 2020 (based on the arxiv paper).
| jtsiskin wrote:
| This makes sense, intuitively; if I gave you "8f434346648f6b96df8
| 9dda901c5176b10a6d83961dd3c1ac88b59b2dc327aa4" (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)
| p1mrx wrote:
| 2 would be the wrong answer here, because K-complexity includes
| the definition of sha256 itself.
| atonalfreerider wrote:
| 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 x 10
| ^ 6 physical qubits to break the encryption within one hour using
| the surface code, a code cycle time of 1 ms, a reaction time of
| 10 ms, and a physical gate error of 10-3. To instead break the
| encryption within one day, it would require 13 x 10 ^ 6 physical
| qubits
| politelemon wrote:
| (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.
| abhv wrote:
| "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.
| l33t2328 wrote:
| Hashing would be generally be fine.
|
| AES would still be totally okay.
| mdoms wrote:
| I'm a layperson, but isn't hashing the quintessential one
| way function? (at least for industry software engineers).
| drexlspivey wrote:
| 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.
| denton-scratch wrote:
| /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.
| mindwok wrote:
| 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.
| dibujante wrote:
| 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.
| macksd wrote:
| 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.
| upofadown wrote:
| 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.
| Snitch-Thursday wrote:
| 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!
| some_furry wrote:
| If you want to read the actual paper from the researchers, the
| URL is https://arxiv.org/abs/2009.11514
| pishpash wrote:
| "...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?
___________________________________________________________________
(page generated 2022-04-06 23:00 UTC)