mdxn

The author grew up in Michigan (although somewhat closer to southeast MI).

> "unaware that in nearby Ohio," Clearly this was written by a coastal or someone who needs a lesson in geography. Vulcan, Michigan, and for that matter most of the Upper Peninsula is closer to 3 other states including Iowa than it is to ANY part of Ohio.

Can you explain why this is relevant? It seems of little consequence to me in the context that it is written.

As someone who lived in Michigan for 20+ years (I am aware where Vulcan, MI is), Ohio seems "nearby" enough given the reason the author would use that language in the article.

Lattice based cryptography can actually be made pretty accessible and can be taught to highschoolers and fresh undergraduates (I have done this with students at my job) as long as you give them a couple of math tools they may not have: matrix transforms, Gaussian distribution, vector dot product, and the one time pad. While this is a longish list, none of the topics are particularly hard and are accessible. I'll take a crack at an explanation (with schoolbook Regev-like LWE) and you can let me know how I did. It is better with pictures and probably can be shaped over the years, but I do think that people can adapt this explanation to turn it into something as easy, if not easier, than RSA.

1. Start with a random (secret) n-dimensional vector, s, that lives on a lattice (a square grid like pattern). This is your (small) secret key.

2. Hit that vector with a randomly generated matrix A (written As for multiplying matrix A with vector s), which basically just scales, skews, rotates, and projects that lattice into m-dimensional space (we want m to be much bigger than n). For those in the know, the new vector, As, is almost a "psuedorandom", "random looking", or hard to predict value. This is a way of taking your small key and turning it into a large key.

Intuition: Note that each component of As is basically an individual dot product. On a simple level, you can think of the dot product as a generalization of XOR, parity, or something that creates a checkerboard pattern using that lattice. This basically creates a high dimensional grid (lattice) with many colors that alternate. The end goal is to get some samples of these colors and reconstruct what the grid pattern looks like. If you have tried to learn a checkerboard (XOR, parity) pattern with a linear classifier, you know that this is hard. Here, we are generalizing this concept into something even harder.

3. Add (Discrete) Gaussian noise to As to get As + e. This is just adding "small" random noise to each of the components. You do this is to turn the almost "random looking" large key into an actually "random looking" large key.

Intuition: The reason for doing this is that if you have A and y where As = y, you can solve for s using Gaussian elimination. This is equivalent to the process that gradeschoolers use to solve systems of equations with multiple variables (where they subtract one row from another or solve then substitute variables).

Turns out that Gaussian elimination and other algorithms suck bad at getting the right answer if you have noise or small sources of error. The process gets thrown off wildly and gets no where close to s. The situation is so bad that even quantum computers are assumed to not be able to do it. This is what makes your large key resistant to being reverse engineered by powerful computers.

4. Use your As + e as a one time pad. To encrypt a message m, your ciphertext is the pair A and As + e + m. To decrypt, someone takes the key, s, computes As, then subtracts that off. This leaves you with m + e.

5. Decryption in (4) is bad because the small error, e, is leftover. This makes the process noisy and makes you lose a little information when you encrypt or decrypt. You fix this by using a noise correction encoding that makes the e go away.

Your new ciphertext is (A, As + e + encode(m))

EDIT: Note that to make this actually secure you need to pick good parameters for your lattices and your noise distributions. If your error is too small, it wont fool attacks and is easy to solve. If your error is too large you cant decrypt. The problem is easy unless you are in high enough dimensions (for instance, LWE is easy in 2 dimensions, which is what we use to visualize things).

Encryption keys do not have to give "all or nothing" access to encrypted material. With homomorphic encryption and related primitives, you can shape things in a much more finer grained manner and only expose carefully crafted partial information. This can accomplish what you are hoping for with your threshold cryptography example without relying on some sort of combined trust built from multiple authorized parties.

For instance, with functional encryption, you are able to distribute or derive keys that have a very specific functional purpose and leaks no other information. Basically it allows you to derive a "function key" that basically computes f(x) for you given an encryption of x. As long as the crypto is strong, no other information about x is exposed (only info about f(x) is revealed).

With the right system architecture, this would allow the government to perform a very specific, pre-defined query to check for illegal content without exposing any additional information about the encrypted data.

Another approach you could use is based on zero-knowledge proofs and verifiable computation. Essentially a government could come along and ask you to provide a proof that your encrypted data does not contain malicious content. Given a program that can check for what they are looking for, you can provide them a zero-knowledge proof that convinces them that you correctly ran their provided algorithm on the suspect data and that the algorithm did not identify any malicious content. In this process, no other bits of information are exposed or handed to the government other than the data is not malicious.

This is a misapplication of that principle and runs the risk of turning into the toxic gatekeeping that I know first hand has kept many talented people out of the academic cryptography community. The authors of this work implement their system using existing proof of concept zkSNARK libraries that have been developed by researchers studying this area for roughly a decade or more. They are not rolling their own crypto and are guided by top notch cryptography researchers at MIT (albeit in a course setting).

Even supposing that there is a dangerous time to experiment with application with proof of concept work, this really isn't the case for zero-knowledge proof (or more specifically, zk-SNARK) systems right now. I have been in this field for many years and the chief complaint that I have heard many researchers have is that the tooling exists, yet people are not making heavy usage of it outside of ZCash. This, thankfully, has become less true within the last year or two. This work, even if it is written by students, is nice to see given this reality and can give researchers trying to optimize these development tools necessary feedback to improve them.

To put this into a larger research context, keep in mind that various funding agencies have probably spent at least $1 billion on FHE, ZKP, and similar novel crypto research in the last decade. Off the top of my head, this includes DARPA, ONR, NSF, and many more. The biggest barrier this area currently faces is fine tuning these tools to be performant and accessible to non-research level security engineers and developers. This includes determining which applications this technology may be useful for and where, if applied, it is surprisingly not useful. This is why there are continuing (multi-million $) programs to directly target these problems (DARPA SIEVE and IARPA HECTOR for example). This work by MIT students is, at least on the surface, a potentially useful datapoint that we can use to inform our decisions going forward (I personally would like to know more about their development experience using the tools).

> This is not a peer-reviewed research paper. It seems to be a project report likely done by undergraduates. The paper is full of typos and it is not clear what the specific novelty of the proposal is (if there is any).

This is not a constructive comment.

The URL suggests this is a final(?) project paper for MIT's 6.857: Computer and Network Security course. The paper seems appropriate in style and length for this kind of setting.

There is definitely a difference. The problem with the vast majority of "Turing-completeness in X" claims on HN is that they are just logically complete Boolean circuits that are overgeneralized (infinitely tessellated or scaled) for free and cannot handle arbitrarily large inputs. They can only handle constant sized input lengths. To handle an arbitrary input, the circuit has to be resynthesized and created to handle that particular case length. This ends up being a massive leap in computational complexity from constant-time to decidable.

Some of these claims are even wrong since the posters don't bother analyzing whether their suggested generalization technique (e.g. infinite tiling) actually do let you topologically embed every gate and batch of wires into any Boolean circuit you want. This is quite common in 2D side scrollers where you have constant y-height and infinite x length. It just is not possible to communicate all the information you need for a computation from one side of the map to the other. This was the case with Minecraft prior to bidirectional flying machines. You could actually prove that any finite sized "machine" could not communicate an arbitrary distance away (think arbitrarily long Turing tapes) without losing some part of it going off in the distance forever. Hence it was not "Turing-equivalent" unless you used command blocks or gave some overly general infinite tiling capabilities.

Actual descriptions of Turing machines are finite in size/length. These "Turing-equivalent" candidates that keep popping up are not when laid out. This makes it pretty easy to run into uncomputability situations when you try to feed the machines a description of itself and compute some property (like a number = 2x its length). A typical Turing machine would have no problem handling this, though a Boolean circuit would.

The average GPA of millionaires alone is obviously not enough information to make the conclusions that this video is making. An average GPA of 2.9 is not far off from the average college GPA of regular students, anyways (for, let's say, the ones that graduate). For all we know (from just this statistic), college GPA could be completely independent from who is a millionaire and who is not. We really need information about the shape of the distributions in order to really compare these two groups. For instance, we would, at least, need to know that valedictorians (for the sake of simplicity, just people with 4.0s) have a lower likelihood of becoming millionaires than other groups. The average alone does not help us enough here.

I have a few questions for the people who are really more knowledgeable about the topic:

Is there really a lower incidence of high GPA graduates (3.8-4.0s) becoming millionaires than those closer to the average? Is this distribution tighter around the mean or are there clusters in certain bands of GPAs?

Withdrawn already

"The paper has been withdrawn due to a mistake in the last line of the proof--it does not hold for n=0. Thanks to Terry Tao for pointing out this crucial gap"