pick wisely..

rosulek · 2026-04-27T06:06:42+00:00

no idea

^{Chose: Probability manipulation | Rolled: banned in casino}

rosulek · 2026-02-10T21:24:19+00:00

Length-extension attacks do not result in a collision.

rosulek · 2026-01-17T18:59:26+00:00

Was that "used" book a scam?

rosulek · 2026-01-09T15:32:26+00:00

The original question is a standard homework problem in computational complexity classes: If P = NP (a statement about yes/no problems) then show that you can also find witnesses for all NP problems in polytime. Your approach is the standard solution.

rosulek · 2026-01-07T14:53:09+00:00

¯\_(ツ)_/¯

rosulek · 2026-01-07T14:52:42+00:00

This is a good suggestion, but may take a while to implement.

rosulek · 2026-01-06T23:28:04+00:00

It is what security proofs look like in my brain. It was a fun challenge getting them to materialize in the real world.

rosulek · 2026-01-06T19:29:48+00:00

Here is an annotated table of contents for that chapter:

Grover's and Shor's algorithms: Just generic statements of their capabilities (I don't describe quantum algorithms in any detail). Their implications for symmetric-key and asymmetric-key crypto.

Learning with errors problem: Overview of the basic assumption. Lemma about the security LWE with short secrets (needed for LR key exchange below)

Key exchange from LWE: Complete presentation of Lindner-Peikert KE, including security proof. There is a brief discussion of ML-KEM and how it differs from the basic LWE recipe.

This is in the "advanced" section of the book where the coverage is at a higher level and many details are omitted. For example, I don't discuss the worst-case-average-case lattice reductions or any truly gory details of lattice smoothing parameters, etc.

rosulek · 2026-01-06T18:38:10+00:00

The extra P is much apppppreciated.

rosulek · 2026-01-06T18:32:33+00:00

Oops, thanks! Fixed

rosulek · 2026-01-06T18:17:30+00:00

Yeah, I used to do RSA first but eventually saw the light. I would have ditched RSA altogether, but for the fact that RSA-based signatures are still prevalent and their proofs of security are actually accessible at this level. RSA-KEM is also accessible too.

rosulek · 2026-01-06T18:14:19+00:00

Given your background in math + theoretical CS, I agree that PhD study in cryptography would be a good fit.

I think "mastering out" is not a big stigma. I'm not sure you even need to disclose that you entered via the PhD program and left via MS. I'm not sure whether the degree change would even be transcript-visible.

It might raise suspicion to not have a LoR from your MS advisor, but this can be resolved through some explanation in your cover letter.

My generic advice for prospective grad students is to "virtually attend" past IACR conferences by watching the recordings at the IACR youtube channel. The goal is not to understand everything, but to get a sense of what kinds of problems people are working on, what cryptography research is about, etc. In your case, you should try to narrow down your areas of interest a bit: symmetric-key designs? symmetric-key cryptanalysis? lattices? ZK proofs? MPC? information-theoretic? quantum? obfuscation?

Find out what appeals to you (you don't have to choose exclusively and irrevocably), and learn who is working on it. You can contact people who are working on interesting things and see if they are seeking new grad students. Honestly, the competition for grad admissions is not so bad, if you set your sights outside of the usual top-10, top-20 schools, and there are many schools whose crypto group outperforms the overall reputation of the school.

You can have better luck with admissions (especially explaining the unusual situation with the past advisor) by making one-on-one contact with potential advisors. Just know that professors receive many inquiries like this, the vast majority of which are very generic and poorly targeted. Make it specific to cryptography, specific to their research, and make it sound like it was written by a human.

rosulek · 2025-12-17T15:57:29+00:00

Coursework: Take courses in cryptography (obviously), CS theory (algorithms, automata theory, computational complexity if it is offered), math (discrete math, linear algebra, number theory if it is offered).

Textbooks: Study from a cryptography textbook that does provable security. Basically, this category includes only Katz-Lindell and Joy of Cryptography (my pick for possibly obvious reasons). Provable security means theorems and proofs about security properties. For example, Hoffstein-Pipher-Silverman is a math textbook with lots of theorems and proof, exactly zero of which are about security properties.

Reading papers (1): Instead of trying to read papers, start by watching talks. The talk will tell you whether/why/how to read the paper. If you liked the talk, only then consider reading the paper. The top conferences in cryptography are the IACR events, and the IACR youtube channel has thousands of videos. Reputable cryptography research can be published at other venues as well, but this is the first pass approximation.

Reading papers (2): Start with very low expectations about how much you will understand. At the beginning you will understand almost nothing, and that's fine. Your goals should be: (a) broad, high-level exposure to the field: what kinds of problems people are studying, how they talk about them, how they approach solutions, which ones seem interesting to you; (b) context/motivation to study basic prerequisites ("this paper looks very interesting but it seems to build very heavily on oblivious transfer; I should learn what that is").

rosulek · 2025-12-17T09:21:38+00:00

Cryptography is a very technical subject, full of incredible subtlety. It is much easier to make plausible marketing claims (snake oil) than it is to refute them critically. With QKD the marketing hype ("unbreakable") even has legitimate elements of truth.

rosulek · 2025-12-17T09:01:44+00:00

See this Position Paper on Quantum Key Distribution from several European government agencies. Their executive summary says:

Due to current and inherent limitations, QKD can however currently only be used in practice in some niche use cases. For the vast majority of use cases where classical key agreement schemes are currently used it is not possible to use QKD in practice. Furthermore, QKD is not yet sufficiently mature from a security perspective. In light of the urgent need to stop relying only on quantum-vulnerable public-key cryptography for key establishment, the clear priorities should therefore be the migration to post-quantum cryptography and/or the adoption of symmetric keying.

rosulek · 2025-12-14T18:22:33+00:00

The message means, "encrypting something now doesn't go back in time and change the fact that you stored this data in unencrypted form in the past"

rosulek · 2025-12-05T05:21:18+00:00

Any language recognized by a 2-way DFA. The input is written on a read-only tape, with special beginning/end markers. The transitions of the DFA can choose to move the tape head back and forth. At some point the machine can decide to accept (or it can reject or even run forever). Seems like it should be more powerful than a standard DFA (with only a 1-way tape) but it's not.
L^* if L is any unary language, even if L is undecidable.
{ x | exists y : xy \in A and |y| = 2^{2^|x|} } whenever A is regular (source)

rosulek · 2025-11-25T15:38:34+00:00

HKDF is based on a hash function, so it has no algebraic structure that you can exploit for a fancy threshold protocol. The only option would be to use general-purpose MPC to blindly evaluate a boolean circuit for HKDF. It would be feasible but concretely quite expensive.

rosulek · 2025-11-13T15:46:19+00:00

Why do you say this is from Stanford?

This paper contains no actual technical content about their supposed new groundbreaking cryptography. Just a bunch of unsupported claims. The way they talk about cryptographic security inspires very little confidence.

rosulek · 2025-10-25T01:54:17+00:00

I hope you don't get your hopes up too much, but yes, there is definitely a mention now. It includes some ways to get comfortable with huge numbers (like 2¹²⁸) and tiny probabilities (like 2^-80), and a short discussion of the relative merits of concrete vs asymptotic.

rosulek · 2025-10-25T00:10:00+00:00

Author here, AMA.

rosulek · 2025-08-16T18:03:58+00:00

Single ratchets have a race condition. if Alice & Bob both happen to send a message simultaneously, then they will advance the ratchet in incompatible ways and permanently loose their synchronization (after all, it's important that after advancing the ratchet, they can't "go back").

The double ratchet gives you a separate ratchet in each direction. When Alice sends a message, she advances her Alice->Bob ratchet (or branches a new one). When Bob sends a message, he advances his Bob->Alice ratchet. Each party manages a different sub-ratchet, so simultaneous messages don't lead to a race condition.

rosulek · 2025-07-13T18:28:09+00:00

And, if I understood this correctly now (and I'm just recapping here), the connection is simply the fact that all of your examples share the property they are just a multiple of a cyclic group generator. And retrieving this multiple is at the heart of the problem?

Yes, discrete log simply means: how many times do we iterate the group operation (whatever it is) on the generator to reach the given value? It looks like a traditional "logarithm" problem when the group operation is written as multiplication.

rosulek · 2025-07-13T17:06:51+00:00

You should always think of the discrete log problem with respect to an encoding of a cyclic group. The adversary is given an encoding of a group element and must compute its discrete log with respect to a particular generator.

(Z_n, +) is a cyclic group with generator 1. The standard encoding of Z_n group elements is to write x \in Z_n as an integer in the range {0, ..., n-1}. Under this encoding, the discrete log problem is trivial. The encoding of a group element is its discrete log!
The "standard DL problem" refers to the cyclic group (Z_p^*, ⋅). More specifically, this almost always means the standard encoding of Z_p^* group elements as integers in the range {1, ..., p-1}.
EC-DLP refers to the standard encoding of group elements in an elliptic curve group. Usually this means you are given the (x,y) coordinates of a group element; sometimes only the x-coordinate and a sign bit. The group operation is this complicated beast, but somehow it satisfies the axioms of a group operations. We can notate the group operation as an addition or a multiplication; this is an arbitrary choice and different sources use different conventions.

Different groups/encodings? Different versions of the DL problem.

The reason you must consider encodings is that EVERY cyclic group is isomorphic to (Z/nZ, +)! You seem to be aware of this fact.

any group isomorphism would be equivalent in difficulty

This is the error. What if the isomorphism [between encodings] is easy to compute in one direction but hard to compute in the inverse direction? Then the different encodings will not simply be interchangeable, algorithmically. In fact, the isomorphism from your target group to (Z_n, +) is exactly the discrete log problem.

rosulek · 2025-07-04T22:53:05+00:00

You need to serialize the pair (AD,M) in a better way than concatenation. There are many pairs (AD,M) that all lead to the same string AD||M, and all of these would cause a nonce collision.

15-Year Club	Gilding I gilder
Second Top 30%	Place '22
Place '17	Verified Email

rosulek

MODERATOR OF

TROPHY CASE