> "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?
Some pre-processing SNARK constructions (particularly ones used by some ZCash scientists) are based on multi-round interactive proof systems which reduce to one round (depending on how you count) when you relax some requirements. Such relaxations include weakening the adversary from being computationally unbounded to polynomial time bounded, forcing the prover and verifier to use a specific set of functions, or restricting what kinds of statements can be proven. Oded's work on efficient interactive proofs contributed to this effort. It is partially this efficiency that helps SNARKs actually be "succinct" and quick to verify.
You should check out some of the citations to Oded's work in https://eprint.iacr.org/2012/718.pdf (which is co-authored by Alessandro Chiesa of ZCash) and see for yourself.
"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"
The hackathon that they mention in the post (Mhacks) put up an application process and enforced a 50/50 gender ratio. In the weeks leading up to the event, I overheard many defeated conversations from fellow CS students over anxiety of getting rejected from this hackathon because they were male. The females didn't share the same anxiety, but it definitely made them feel down that they wouldn't be able to participate with their male friends who were rejected/waitlisted. Overall, the fact that things ended up this way made everyone feel very awkward, guilty, and discouraged. Hopefully its success makes up for the hidden fractures that will be felt by our student body for quite a while after.
Mhacks lists the 50/50 gender divide on their site followed by the reasoning: "because it’s about time for a little change in the tech world"
Disclosure: I am a CS-Eng student at this university. I did not plan to attend or care about this hackathon.
People reading this write-up should keep in mind that the author uses the term "complexity class" incorrectly. When the author says this, they actually mean "worst case runtime". It never dives into space complexity, which is yet another complexity measure for evaluating the performance of these operations. In some spots they completely abuse big O notation to make it do things it is not supposed to. For example:
"O(==) is the complexity class for checking whether two values in the list are =="
This stuff needs to be fixed since it is only going to lead to later confusion (and embarrassment).
A complexity class is a set of problems that tend to be similar in resource requirements. O(f(n)), more or less, means asymptotically bounded from above by c*f(n) for some constant, c, as n -> inf. It is a general way to represent the asymptotic growth rate of functions and is NOT married to the concept of complexity classes.
For those who are interested, Berkeley has publicly available lecture notes for their Randomness & Computation course. They go over some randomized algorithms as well as the mathematical tools necessary to analyze them. Just a heads up, the content is fairly theoretical.
The actual decision problem statement for TSP is "Does there exist a tour of less than length L".
It is easy to prove if such a tour exists: simply give me tour. I can sum up the lengths and check that the sum < L. Finding such a tour is the computationally hard part in the worst of cases.
I heavily suspect this claim is wrong due to some amateurish mistakes. In particular, I believe the author is confusing the concepts of "checking" a solution and "searching" for one. At some points in the paper, their use of the word "detecting" (an ESS) is equivalent to "checking", but the logic of the argument (very simple, might I add) seems to equivocate it to "searching for" an ESS. The distinction between these two tasks is exactly the distinction between P and NP. So I'm inclined to blame this on lack of reading comprehension on the author's part when piecing together information from other works.
Assuming that the author wasn't inconsistent in the meaning of the term "detection", then they are probably claiming that there is some sort of polynomial time reduction taking place between recognizing a solution to an ESS problem (coNP-complete) and recognizing a strict local maximum in a quadratic program (NP-hard according to the author). I don't see this explicitly done in the paper and doubt what they have yields one even if I had more of the context. Unfortunately, I wasn't able to evaluate all of the citations since they are behind paywalls. I wish there was enough information in the actual paper to determine this.
I get the gist of what you are saying and agree with some of it. I still think the article isn't sufficient, at all, for even an elementary introduction to anything. It's incredibly incomplete. An introductory cs course is going to present asymptotic complexity analysis (written using Landau notation) as one of the TOOLS for thinking about the efficiency of code. It will hopefully not just hop to big O without setting up the context. The author can fix this by just reworking the preface. It needs to answer the question: "why are we doing this and how will this accomplish anything?"
If you fail to frame the context and the semantics well enough, you'll end up with people running around saying that an algorithm is "big O of blah." AGH
The introduction to the concept is articulated by the following comparison:
'We want to measure code efficiency. Big O notation describes this. Here are some examples.'
vs.
'We want to measure code efficiency. We can do this by thinking about its usage of resources (complexity). for example, total run time and memory usage. One of the ways to compare the efficiencies of algorithms is to compare their asymptotic behaviors. We can express this using big O notation. Here are some examples.'
-----
The author talks about how big O notation is awesome because you can drop the constants. It is not explained why this is awesome or useful. Interestingly, it later says that sometimes it isn't good because the constants sometimes matter. What is the reader supposed to understand here?
There's no followup as to what to think about after you determine the "big O" of an algorithm. Either he forgot to write this or figured that it was obvious at that point. Considering that he didn't sufficiently explain the concept's motivation either, I don't see how an uneducated reader will get a clear picture.
I'll ignore discussion as to what counts as a step, what "n" is, or how it doesn't necessarily reflect on the real world. I still feel like this article focuses on the wrong thing. It's equivocating Landau notation (Big O) with complexity/efficiency, but never explains what complexity is. It then proceeds to link this to the efficiency of code under certain circumstances. While this work gives a couple of examples as to how to determine the "big O" of simple algorithms, it ignores its meaning and context. This is a huge mistake.
First off, big O notation wasn't created with complexity theory or algorithms in mind. If I recall correctly, it has its roots in complex analysis. The notation was later borrowed as computational complexity was formalized. What happened is that people needed a way to describe the hardness or "logical sophistication" of problems and tasks. Looking into the asymptotic behavior of a complexity measure was just one means that they used. There are plenty of other ways to do this. The article reads like big O exists for the purpose of complexity analysis of algorithms. I doubt the author intended this, but they should be a bit more careful.
Time and space aren't the only resources of interest. Sometimes you need to quantify how much information you have or how much entropy there is. If you want to understand "what is basically happening", this is something you should pay attention to. Are we handling more information than we have to? What do we need and not need? Circuit sizes, sophistication of proofs, setups of databases, and the complexity of communications/protocols also play a role.
Even ignoring all this, the article is missing an elementary half of the picture: the structure of the input. It's not just about code and its design. Data structures matter, too. How information is organized, how it is encoded, and how it can be manipulated (computed on) makes an absolute huge difference. Are things sorted or unsorted? What kind of list or tree structure is your code working with? From what I understand, this is the whole point of a significant chunk of the interview questions candidates are presented with. It's ridiculous to omit this when introducing algorithmic complexity.
The author claims that Big O notation is an "awesome, not-boring kind of math where you get to wave your hands through the details and just focus on what's basically happening". They are hand waving not just the math, but also hand waving (and ignoring) most of the context as well. It doesn't even directly explain why big O notation models code efficiency in a fruitful way. It just mentions run time and memory usage superficially. In my opinion, this needs to be significantly revised or rewritten.
I can see how it can be read that way, though you should also to look at this from his perspective (or at least my guess as to a possible perspective).
The internet (and the field) is flooded with nonsense papers that don't respect the hard work of others. A lot of them really do come from these "common novice mistakes". The authors are taking very superficial views of complexity theory and physics against the advice of researchers in those fields. This particular one hasn't, but a lot of them have incredibly bad and egotistical attitudes. I think researchers see this as incredibly insulting, ignorant, and a severe lack of humility. People aren't showing enough respect and care to this field.
This wouldn't be such a problem if it didn't happen more often than not. On top of that, these poor findings end up swarming around the media and dilute the field. Look, Aaronson is a well known guy who has spent a lot of time trying to point out and explain these mistakes. Though people, including pseudo-scientists, completely ignore him. They even start fights with him. He and others get spammed with this stuff weekly if not daily. For him, I bet it's simply too much to ignore.
I think you would have to be assuming that the far-advanced civilization's simulator has the same complexity as the models of computation we can construct. I think that's a huge leap to make. We might not be able to model something due to issues with, let's say, Turing decidability. Unlike us, the advanced civilization's might be able to because their constructable models of computation are strictly more powerful.