u/DoWhile

Anyone remember Mario teaches typing? Mavis Beacon is cool and all, but Mario was my guy.

Soundness bugs are hard to come by "accidentally" for a human

You haven't seen my Lean/Easycrypt code then!

Matching upper and lower bounds!

The letter "y"

My salary has always outpaced my investments (S&P and chill since 2005, picked up some Bogleheads advice along the way and added some amount of international/bonds), so it's unfair to say I solely made money from the market. My investments survived 2008, survived COVID, I hope to survive whatever comes next. That's the thing nobody is saying: earning more salary is the bigger make/break. If you want $10M by age XX (by the time you're XX years old, $10M will be worth a lot less due to inflation), you'll end up finding out that you still have to EARN a good chunk of it, even if your stocks outperform the market.

I chose this topic because I’d like to start my career in cryptography or cybersecurity

Cryptography: this is IMO a scientific endeavor, so getting a PhD is usually the route there. If you just want to implement things, I would consider that more software engineering rather than cryptography per se.

Cybersecurity: This is a broad field, and a lot of it comes to getting the right training. Standards, configurations, etc. are more important than building blocks.

If you want a future working, say, at a cryptography research lab, they do need software engineers, but Merkle Trees aren't going to tickle my fancy.

What kind of university are you going to? Is it a top-ranked research university? Technical university? State-school?

We threw a bigger computer at it. Unlike in the past where a bigger computer was just "more horsepower", this is like tying a fleet of cars together and having them all pull. The engineering effort of managing this fleet is non-trivial, and you can ask AI to kindly write it for you.

You still need to have a gazillion GPU-hours though. Guess which kinds of companies have tons of those lying around.

I have my own take on this. This is one of those things you gotta just do a bunch of times before you get a feel for it.

When I first got into it, it reminded me of integration by parts: sometimes you have to "know" the leap of faith before it happens.

If your proofs background is weak, you should take a complexity theory course that goes into poly-time reductions, it has the same flavor.

And is there a good argument that the harvest-now problem was already lost before 2024, so we should stop pretending the 2029 dates fix it?

The best time to plant a tree was 20 years ago. The second best time is... in 2029 I guess.

Good artists copy, great artists steal... even greater artists steal from the workshop they're submitting to.

You know how they say memories are not "real" in the sense that the mind re-generates a lot of what happens in memories? Maybe theirs is so messed up that they "remembered" writing it themselves, like this: https://i.imgur.com/VrgyDwC.jpeg

Protocols can exist at different levels of abstraction.

The fully generic term you're looking for is key agreement or key exchange. There are many ways to instantiate key exchange, some of which are insecure today, some of which will be made insecure with quantum computers, and some of which are still secure against quantum computers.

The fundamental parts of cryptography is usually taught at a theoretical level. One-way functions, collision-resistant hashing, key agreement, secret-key encryption, public-key encryption, etc. all are interrelated and none of them really are at risk. Unless some horrible shit happens like P=NP or BQP=NP.

Are we moving into a fundamentally different era or an era that is the same but with different parts? It always confuses me

Same, with different parts (a bit more different than normal). If you were taught cryptography thinking that RSA is the only way to do public-key encryption or signatures, or DH is the only way to do key exchange, you'd be in for a rude awakening. But if you learned cryptography from a theory viewpoint, this is still mostly business as usual. I'm actually glad PQC is picking up, because it motivates people into thinking about cryptography from a more grounded, fundamental frame of reference rather than learning individual algorithms.

Why not just read the standard + original papers?

Standard: https://csrc.nist.gov/pubs/fips/203/final

Original: https://eprint.iacr.org/2017/634

Standard: https://csrc.nist.gov/pubs/fips/204/final

Original: https://eprint.iacr.org/2017/633

Standard: https://csrc.nist.gov/pubs/fips/205/final

Original: https://eprint.iacr.org/2019/1086

It's a great mobster heist movie, once you get past the sesbian lex

Right? My step 1 would be: go online and feed my Neopets.

We've come a long way from the controversy being computers used to brute force search! Ironically, it was Gemini that caught some minor bugs in their implementation, so in some sense it was computers beating their own controversy.

The main point of the paper is still cool though, computers or not: nlogn time 4coloring!

Here my dumb-ass is thinking the cat was fighting the AC unit.

"Everything in moderation, including moderation." - Oscar Wilde

Navier-Stokes was claimed to be resolved, but how it was done is currently undergoing drama. I have a biased opinion on this, so I'll keep my mouth shut and leave it as an exercise to the reader to seek out the story and discover out how they feel about it.

You're right, c and w both would need to be part of the "there exists" statement as part of the witness rather than in the clear.

As for the cropping, depending on how much you want to hide (crop size, dimensions, location), you may want to look at a recent paper that uses tiles for compressing size: https://eprint.iacr.org/2024/1074

Another way you can do it, especially if you need to hide the crop size, is to treat cropping as adding black rectangles to your image. This then becomes a zk-redaction problem, and papers such as https://eprint.iacr.org/2020/1579 might do the trick!

In Dan Boneh's world, the verifier has a hash/commitment of the original uncropped image, and the plaintext of the cropped version, and has to verify a ZK proof that there exists an uncropped version such that (1) it hashes to the hash, and (2) it crops to the cropped version.

Instead of Boneh's (hash of original) + (plaintext of cropped) + ZK proof, you want to have an (encryption of the original) + (encryption of cropped) + ZK proof.

If we let o denote the original picture, and c denote the cropped picture, let w be the secret window coordinates that you use to crop, h be the commitment of the original, e1 be your encrypted original, and e2 be your encrypted cropped version, then Dan Boneh's proof looks like "There exists some randomness r such that Hash(r,o)==h && Crop(w,o)==c", and your proof looks like "There exists some key k and randomnesses r1 and r2, such that Enc(k,r1,o) == e1 && Enc(k,r2,c)==e2 && Crop(w,o)==c". This is pretty easily expressible in modern ZK languages.

This is a partial answer of what you're asking for: https://medium.com/@boneh/using-zk-proofs-to-fight-disinformation-17e7d57fe52f

This is on authenticated images, not encrypted images, but the ZK proof would be similar. You don't need FHE for this, just ZK, assuming the person doing the encryption is also the person doing the cropping. If you need another person to crop for you, then FHE-like stuff is needed.

He got outslopped

I would love for this to have more details. New advances in problem partitioning? Slight improvements to GNFS? Implementation hacks? Anything!

Right now, all I'm seeing is: Man with access to thousands of CPU/GPU-hours solves problem requiring thousands of CPU/GPU-hours. *shocked pikachu face*

I grew up loving so many shows on PBS. Thank you for the work you do!

When you cannot explain a saying, tie a goat around the saying and explain the goat.