Name: Foundations of Cryptography
ISBN: 9780511721656

Foundations of Cryptography

Cryptography is concerned with the conceptualization, definition and construction of computing systems that address security concerns. The design of cryptographic systems must be based on firm foundations. Foundations of Cryptography presents a rigorous and systematic treatment of foundational issues, defining cryptographic tasks and solving cryptographic problems. The emphasis is on the clarification of fundamental concepts and on demonstrating the feasibility of solving several central cryptographic problems, as opposed to describing ad-hoc approaches. This second volume contains a thorough treatment of three basic applications: Encryption, Signatures, and General Cryptographic Protocols. It builds on the previous volume, which provided a treatment of one-way functions, pseudorandomness, and zero-knowledge proofs. It is suitable for use in a graduate course on cryptography and as a reference book for experts. The author assumes basic familiarity with the design and analysis of algorithms; some knowledge of complexity theory and probability is also useful.

What Hacker News says

sweisMay 2022

Oded Goldreich's "Foundations of Cryptography" books are the rigorous, theoretical oriented books used in many grad-level crypto courses: https://www.wisdom.weizmann.ac.il/~oded/foc-book.html

Neil Koblitz has "A Course in Number Theory and Cryptography", which I haven't read, but is often used: https://www.amazon.com/Course-Number-Cryptography-Graduate-M...

Also, Boneh and Shoup is good and mentioned in other comments: https://toc.cryptobook.us/

thread

xtajvJun 2020

tl;dr:

To learn about some cryptography fundamentals:

* Read Katz & Lindell's Introduction to Modern Cryptography

* If you're missing math background, read Timothy Gowers' blog

* Supplement: Take Jonathan Katz' and Dan Boneh's MOOCS (links in post)

To get to the point where you can "design/analyze crypto protocols" (and maybe know what you're doing):

* Read Oded Goldreich's Foundations of Cryptography (Volumes 1&2)

* Try to have quasi-intelligent conversations with real cryptographers (advice for this in blog post)

* Get a PhD somewhere with a good crypto program

edit: formatting

thread

throwawaymathApr 2019

I've given a few textbook suggestions for almost all of the topics you requested, in a preferred order for learning them. But before you look at that list, consider the following:

I would strongly, strongly advise against trying to learn proof-based mathematics from a textbook (almost all of the math here will be proof-based). The absolute best way to learn mathematics is to have an experienced and competent instructor tailor their pedagogy to you. Failing that, an experienced instructor who is "just okay" but who can e.g. review and critique your work is better than a textbook.

Learning math is very unlike learning programming. It's a counterintuitive idea, but the information density of math textbooks (whether they're well or poorly written) is generally so high that you can't absorb the material unless you read only a few pages per day. Not only that, but it's usually not the case that a single textbook has the ideal level of exposition for your needs - for example, you don't have linear algebra on here despite it being a prerequisite for basically everything else. Some textbooks treat this subject in a highly theoretical manner, while others treat it at a very applied/computational level. Which suits your needs more? Have you studied it at all?

If you're actually serious about this, you need to proceed at a slow pace (2 - 5 pages per day) and complete as many exercises as possible. If the exercises are computationally focused you can do fewer, but you should aim to solve as many of the proof-based problems as possible.

If you go at a rate which will actually allow you to absorb the material, doing this "properly" will take you years. With dedication and not much talent I'd expect it to take as long as an undergraduate degree. With dedication and a lot of talent I could see this being accomplished in two, maybe three years. Once again, I strongly, strongly suggest finding a mentor or instructor.

In any case, here is a list of the textbooks most mathematicians will consider to be very good:

1. Calculus

Calculus, by Spivak

This gives you a rigorous treatment of calculus, which hopefully you have some familiarity with. After this you can move on to real analysis.

2. Real Analysis

Principles of Mathematical Analysis, by Rudin

You might be ready for this after Spivak's Calculus, but it can be rough. If you can't reproduce a proof of irrationality after reading through the first few pages, work through Tao's Analysis I first.

3. Topology

Topology, by Munkres is the absolute gold standard. You should be comfortable with calculus (and hopefully analysis) before tackling this.

4. Linear Algebra

Linear Algebra Done Right, by Axler

This is a thorough introduction to the subject at a theoretical level, with a focus on finite-dimensional vector spaces over fields R and C.

You should also work through either Linear Algebra by Friedberg, Insel, Spence or Linear Algebra by Hoffman & Kunze for the treatment of more advanced/specialized material and, in particular, determinants (which are notably de-emphasized by Axler).

Noam Elkies uses Axler for Harvard's Math 55 and has written up notes and remarks for his students; be sure to read them: http://www.math.harvard.edu/~elkies/M55a.16/index.html

5. Abstract Algebra (Groups, Rings, etc)

Abstract Algebra by Dummit & Foote is the usual reference text for a first course. It's pretty good. If it's too advanced for you, try Pinter's A Book of Abstract Algebra. For a very challenging (but comprehensive) approach to the subject, try Lange's Algebra.

6. Category Theory

Once you have abstract algebra under your belt, a good introduction to category theory is given by Aluffi's Algebra: Chapter 0. I would suggest not trying to dive into this prior to at least encountering fields, groups and rings because it's good to have both the traditional and modern (read: categorical) contexts.

Also try Category Theory in Context, by Riehl.

7. Complex Analysis

Complex Analysis, by Ahlfors. This is an excellent and concise text. You can theoretically approach this before real analysis, but I wouldn't recommend that. Also try Complex Variables, by Churchill & Brown.

8. Differential Geometry

Calculus on Manifolds by Spivak. You will want to have a thorough understanding of analysis and linear algebra before approaching this material.

9. Measure Theory

This is very advanced material in an analysis sequence; don't jump to this unless you've thoroughly worked through analysis first.

I would recommend Stein & Shakarchi's Real Analysis: Measure Theory, Integration and Hilbert Spaces.

10. Probability Theory

A really rigorous treatment of probability is measure theoretic, but even if you haven't worked with measures before you'll need (real) analysis and linear algebra. Tackle those first.

Feller's Introduction to Probability Theory is usually a good first course. If you don't like that, try Ross. For truly advanced probability theory, work through Shiryaev or Kallenberg.

The other things you've asked for are a little under-specified or outside my wheelhouse (in particular, I don't think chaos theory is still emphasized as a field distinct from dynamical systems). You should probably add ordinary and partial differential equations to your list before some of these more specialized topics.

1. Numerical Analysis

Numerical Linear Algebra, by Trefethen & Bau. This is the best all-around introduction. Once you've worked through this, try moving on to Matrix Computations by Golub & van Loan. The latter is much more of a reference text.

2. Cryptography

You haven't specified what you're looking for here, but given the mathematical bent of your question I'd recommend Goldreich's Foundations of Cryptography (two volumes). Be forewarned: cryptography is a subfield of complexity theory. You should have a strong understanding of complexity theory before embarking on Goldreich's Foundations.

If you really want to challenge yourself theoretically, work through Galbraith's Mathematics of Public Key Cryptography. The most up to date version is available for free: https://www.math.auckland.ac.nz/~sgal018/crypto-book/crypto-...

On the other hand, if you're looking for a more implementation-focused text on cryptography, try Menezes' Handbook of Applied Cryptography.

3. Optimization

This is extremely broad. There's linear programming, mixed integer programming, nonlinear optimization, stochastic optimization...I can't recommend textbooks targeted at everything here.

For a good start to the subject of optimization and constraints in general, work through Boyd & Vanderberghe's Convex Optimization. There are additional exercises available from the authors here: https://web.stanford.edu/%7Eboyd/cvxbook/bv_cvxbook_extra_ex...

thread

robertkJul 2018

Why is it a marketing fraud? As a mathematician, I can see the solution of a fully public permissionless DLT as long as (1) there is a PKI — not too hard to accomplish, (2) the generation time of ZKPs and SMPC can cross below the network latency threshold — to which I can say that I know researchers in the space and even a simple run rate calculations indicates this will be feasible soon...

I wonder whether your stance would update if you were to read Foundations of Cryptography by Oded Goldreich?

thread

betterunixDec 2013

If you want a more "theoretical" look at the theory, Introduction to Modern Cryptography by Jon Katz and Yehuda Lindell is a great book. Also good (but my copy had many printing errors) is Foundations of Cryptography by Oded Goldreich.

thread

ReidZBDec 2013

Yes! This is exactly what I was going to post. The article's recommendation to read Applied Cryptography and the HAC to "learn the theoretical background" left me dejected, since neither is particularly that great in the area of theoretical underpinnings. (The HAC is a reference book, for Chrissake!) Both are great books in their own right, but they're not what I'd recommend for the theoretical background.

Katz and Lindell's Introduction, on the other hand, is absolutely fantastic for the task (this was its design goal...). It introduces theoretical cryptography from the bottom-up and uses it to motivate the various primitives and constructions from the applied realm. It's really a great mix. The book has become my go-to recommendation for those who are serious about cryptography but have had relatively little exposure to it. It also doesn't assume the reader is an expert in all things computer science, which is nice.

Goldreich's Foundations of Cryptography is more of a treatise on theoretical cryptography... it goes much deeper and starts out assuming the reader is pretty familiar with concepts from theoretical computer science and probability theory. The optional sections of Katz and Lindell's work end up being the opening chapters of the first volume --- and they're not optional. Block ciphers aren't even treated until the second book. It's a seriously theoretical series, which makes it great in its own right, but I would postpone reading it until well-after Katz and Lindell's book. (And a book on computational complexity, at minimum, for those not familiar with it.)

thread