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?

I think what you are claiming here is misleading.

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.

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"

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.

Here's a link to Zcash's first blog post on their official site:

https://z.cash/blog/helloworld.html

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.

http://www.cs.berkeley.edu/~sinclair/cs271/f11.html

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.

This is overly general. And we need to make a distinction between actual physics (laws of Nature) and our theoretical models of such.

Yes. Our theoretical models of the laws of physics are usually formal and axiomatic systems of logic (basically mathematics).

Yes. We understand and describe it using mathematical constructions we know of.

However, the laws of Nature do govern what kinds of models of computation are realizable (theoretically and physically). Limits on computability influence the design and sophistication of logic and mathematics. A good model of computation that we choose for this is some variant of a Turing machine. If this is true for our brains as well, then there is a limit on how sophisticated and powerful mathematics can be from our perspectives. In other words, the laws of Nature are dictating how good of a system of mathematics we come up with can be from a logical standpoint.

HN is not your personal editorial or blog. (Note: at the time of writing, his comment was the only one present). Also, I'm going to ignore how cliche the 'Americans are sheep and should wake up' attitude is.

That said, I don't see how anyone could possibly have the expectation that the NSA hand over state secrets just because an upset foreigner asks for it. Doing so would blatantly contradict their entire mission and purpose. Americans would (and should) be more concerned if they complied.

I guess you could object to the NSA's mission as a whole, though then it doesn't become specific to the mood of Merkel or other nations.

Back in highschool, I wrote an Uno clone for a final project in Java. I ended up encountering a similar issue for when I was defining constructors for Card objects. At some point, I had to cast null as an Object to rid of some ambiguity. Still pretty embarrassed about it.

There are a lot of things here that I take issue with. Some things I find relatively insulting. I wrote up a list, but I'd rather you spend your time answering the following challenge:

Describe to me any particular infinite process which does not derive or presume the existence of an actual infinity (e.g. an infinitely large set). You may also want to specify the details of your model for an infinite process to prove that your example isn't circular.

---------------

I promise that I will not simply quantify over all the results of the process and call it an infinite set.

You may use time as part of the definition of your process, but you may not prematurely assume that there is an infinite process for enumerating timesteps. If you did, the example would run the risk of being circular. If you can construct it, then you can use it.

Likewise, you may include a finite number of atoms, but you can't sweep any actual infinite objects underneath them.

This database includes emails that were simply listed in these data breaches. Newer Adobe account emails were put in as entries in the database, but their associated password/hint data was not. There were quite a large number of these in the leaked db, including some of mine. I had to download the whole thing and search to realize that the only information revealed/stored was the email address.

What you are talking about is actually the difference between two different notions of infinity: actual and potential. I think you identify these, but do not quite separate them as much as I believe you should.

Potential infinity aligns with the explanation you provide in the second paragraph. It refers to the process of arbitrarily unbounded enumeration (having the potential to count to any arbitrary number). This is equivalent to the capabilities of a Turing Machine. Aristotle's argument is that the human mind (Turing Machine) is restricted to computing decidable problems and cannot compute undecidable ones. The whole point of the application of Cantor's diagonalization argument is to demonstrate this limitation.

Cantor rather argues that assuming the Axiom of Infinity does not necessarily lead to a contradiction (unless you assume the opposite of course). The assumption simply states that some infinitely large set exists, in particular, the natural numbers. It does not have to physically exist, but we certainly can theoretically associate a finite characterization to it. You should look into Kolmogorov complexity for this. Note that this is NOT at all the same thing as "counting to infinity".

A lot of people will counterargue that infinity is just a concept, but I feel as if they miss part of the point. A similar argument would lead to the conclusion that pi does not exist and neither does the number, 2. The only difference is that we apply the concept of two-ness to discrete objects we can compute with. We do have recursive descriptions (programs) that can describe a countable infinity (aleph null) or even pi. We might as well use these descriptions as placeholders for the actual thing. While we cannot contain the base 10 encoding of pi, we have another encoding of it of finite length (the program). Who is to say that a base 10 encoding of numbers is a better proof of existence than one written in C++?

You might have more success with arguing against the existence of undefinable numbers. These do not have a description of finite length and are definitely numbers that we cannot conceptualize with our current assumed limitations.

Can you be more specific about the nature of the logic you are using when concluding that a "completed infinity" is a self-contradiction? Are you sure that you aren't naively equivocating abstract notions of infinity with cardinal numbers?

In your set of positive even numbers example, you are only showing that a specific enumeration scheme does not generate the set of even numbers. A diagonalization argument requires that you show that no such enumeration scheme can exist (not just a particular chosen one). In the typical proof of diagonalization, it does not presuppose any particular scheme of listing the numbers. It just assumes that some arbitrary one exists, then derives a contradiction.

For your binary tree construction, a trancedental real number can be represented by a path of infinite length down the tree. Your argument is that since a breadth first traversal will eventualy exhaust that whole path, that the real number described by it will have been encountered. There are two ways to interpret what you are doing wrong:

- If we are indexing/pairing these nodes by time steps (an index), your construction is using a countably infinite time step to express the numbers described by an entire path (which defeats the point of being countable).

- For countable sets, you have to give me an index of finite size. If I give you a real number, you need to return a natural number (or equivalent) that indicates where it is. To test this, give me the index of pi in your claimed "countable" enumeration. The reason you wont be able to somewhat follows from Cantor's diagonalization scheme.

You might want to do some Googling before spending the time to write up an entire blog post about it (god forbid posting it to HN). The mistake you made is very common and has been discussed to death. You would have caught it.

The answer is no. My standard mainly focuses on preventing the player from making choices after the "machine" executes. Choices here include instructions for the player from the spec about how to handle certain situations. As the author describes it, we would want the entire execution of the machine to act autonomously without choices. I guess it may be permissible to let the player choose not to act, but the idea is to not sneak any of the machines logic to the player.

As for whether or not the current cards suffice, I can't say much (I don't care about Magic tbh). It just speculation as far as I can tell. I was not presuming that new cards are necessary. I just considered it for the sake of the hypothetical.

Interesting links. Thank you.

I didn't know there were that many infinite loops in Magic (I don't happen to play it). Could you link something describing the hilarious confetti combo?

I must have not been clear and concise. I apologize for this. I was discussing the scenario where we introduce a set of cards that allow for an arbitrary number of triggers without human involvement. We clearly need to implement a way of handling nested loops, branching, and recursive calls. So the set of cards facilitating this need to either need to do this completely by themselves or construct the behavior given the state of the playing field. I did not assume we can do what is described in the paper (the site) because I have no reason to think the new cards must function in a way that is compatible with their setup. This is why I am interested in the possibility of implicit and bounded recursion.

The fuel comment was just relevant to implementing an infinite loop in a real game. If our supposed 100% autonomous system (with the new cards as mentioned above) relied on an additional resource (such as burning through cards each "tick"), then this wouldn't work in real life but would work if we generalized the size of the deck or available cards. This is not supposed to be a characteristic of Turing Machines in general (or at all). It was just a precaution for attempting to translate an instance of the generalized case to real life.