672 karma · joined July 4, 2021
The context is the US mobile drivers licenses and the forthcoming digital identity documents in the EU. The government gives you an electronic document stored in your device, and now the problem is, why would you ever want to give a copy of your document to a third party. This code solves the problem via zero-knowledge presentations of the document. This is real stuff already integrated in Google Wallet, not vaporware. See also the paper linked from GitHub. Ignore the marketing in TFA.
The identity document (e.g. driver's license) is granted by an issuer (e.g. department of motor vehicles) and stored in the user's device only. Google is not part of this flow and the document is not sent to Google or stored by Google. In fact, one major technical problem is how to make sure that the document cannot be used without having possession of the phone. To this end, the document is associated with the phone's secure element (think of a hardware yubikey already present in the phone itself) and cannot be used without the secure element.
Think of the document as a dictionary { "name": "foo", "address": "bar" ... }, although the reality is more complicated. One standard for these documents is ISO/IEC 18013-5, but other possibilities exist.
The proof itself proves the truth of a certain predicate on the document. The predicate is something like "The document parses correctly, it is bound to the device's secure element, and it contains zip_code = 012345".
The phone generates the proof at presentation time in about 1s. Another major technical difficulty is that past attempts at solving this problem required prover time of tens of seconds. Our proofs have the property that no entity, including a future quantum computer, can learn anything from the proof other than the predicate is true. See https://eprint.iacr.org/2024/2010 for the gory details. The specific predicate being proved is in Algorithm 10.
When you say "interactive" you probably mean "at presentation time", as opposed to "in advance". We generate a fresh proof at presentation time and not in advance. Be aware that the ZKP literature uses "interactive" in a different sense, in which the verifier keeps posing multiple challenges to the prover until the verifier is satisfied that the proof is correct. Our system is derived from an "interactive" protocol in this technical sense, and transformed into a "non-interactive" prover via a general transformation called "Fiat-Shamir". The net effect is that the verifier asks "tell me your age and nothing else", the prover sends one message with the proof, and that's it.
1) elliptic-curve cryptography cares about 256-bit multiplication (and perhaps 384 or 521 bits for the truly paranoid). Is your algorithm better than alternatives in that regime?
2) cryptography/ZK cares about multiplication mod p, and not about multiplication per se. Of course you can perform the multiplication and then reduce mod p, but other techniques exist (e.g. Montgomery multiplication) that interleave the multiplication and the reduction for better performance. It is hard to combine Montgomery and Karatsuba. Can your technique be combined with Montgomery?
3) ZK also cares about binary fields GF(2^k). Does your technique work in those fields?
The first case is where you have a N-dimensional vector space where all dimensions have the same units. The standard example would be the Newtonian 3D space. Depending on what you are trying to do, you can view it as a collection of coordinate-free abstract vectors, as a triple (x, y, z) of real numbers, or as an array X[i] of three coordinates in a given basis. In this case I would agree that X[0], X[1], X[2] is better than (x, y, z), the order matters, and you can define the Jacobian is a 2D array that represents a certain abstract derivative in a given coordinate system. I would argue that the formalism of Sussman and Wisdom (which they got from Spivak) is totally adequate to this case, and perhaps even the best possible.
The second case is the one of the Lagrangian that parent mentioned, where L is a function of the triple (t, x, v). You could pretend that (t, x, v) form a vector space, but this definition won't get you far. I would regard (t, x, v) = t * (1, 0, 0) + x * (0, 1, 0) + v * (0, 0, 1) as meaningless because it is adding time, space, and velocity. You cannot really do rotations or general linear transformations in this space. You can define a Jacobian matrix if you want, but now all entries in the matrix have different physical units. In this case I would say the fact that v is the third element of the tuple is irrelevant, and that the tuple is better regarded as a map from symbolic names "t", "x", and "v" to real numbers. I would argue that the Spivak formalism is inadequate in this case, and it seems that many physicists on this thread think the same for essentially the same reason.
This difference is kind of analogous to double X[3]; vs struct { double t; double x; double v; }; From one point of view they are the same, but in practice they have totally different meanings.
But I do agree with your main point that the order of arguments is irrelevant, and it is a mistake to make it a first-class citizen of the notation.
(Disclaimer: googler, I have nothing to do with this research.)
I had a semi-sophisticated device consisting of a lightweight plastic cylinder that could move up and down when filled with gas, and a way to know the volume with accuracy (single-digit milliliter error out of five liters). I had a tank of pure CO2 and an air intake, coupled with valves that let me fill the cylinder with any desired mixture of CO2 and air. I wrote an automatic program that created a calibration curve in various proportions (100ppm CO2, 200ppm CO2, ..., up to 5000ppm) and collected the sensor value.
The results of this procedure made no sense, because the sensor reading collected during the calibration, e.g. at 1000ppm, was totally different from the sensor reading in response to a 1000ppm concentration created outside the calibration loop. After several days of investigation, it turned out that the problem was that I was using tubes of some carbon-based plastic material. Somehow the CO2 mixes with the plastic and is slowly released afterwards, altering the mixture. Everything worked fine after I replaced the tubes with silicon-based silicone tubes.
Human exhaust breath contains about 5000ppm CO2, so this device is decent for measuring humans. It's less decent to measure atmospheric CO2.
Edit: looking at the datasheet, the device claims +-30ppm and 3% of reading, which I interpret as "whichever is greater". Thus, the device would be +-30ppm up to 1000ppm, and 3% of the reading above 1000ppm.
If I were you, I would send an email to Knuth reporting the error. You may receive a reward check from Knuth himself, which will give you eternal bragging rights.
I couldn't confirm the DR SVD part, but the PROF SVD story appears to be real: https://www.mathworks.com/company/newsletters/articles/profe...
I have read a few opinions of the Supreme Court over the years. I have no specific background in law, and I am not even a native English speaker, but I have found them uniformly accessible to a layman. They use a dozen or so boilerplate latin expressions that you need to get used to, but they are otherwise fairly readable.
The leaked text by Mr. Alito is a masterpiece of English prose and scholarship, in my opinion. In 90 pages or so, it explains the history of the issue and the legal theories that common-law judges have advanced since the 14th century. It analyzes the arguments in favor and against Roe and Wade. It also summarizes the legal handling of the issue in various US states.
Irrespective of whether or not you agree with the conclusion, these opinions are one of the few pieces of contemporary literature worth reading. I myself am looking forward to the final form of this text (should the Court decide to uphold it) as well as all the dissenting opinions, which I expect to be of similarly high caliber.
Assume you import $1 of goods, which are consumed. Then the GDP reflects $1 consumption (either private or government) minus $1 imports, for a net zero.
The goods may not be consumed immediately, in which case GDP counts $1 inventories minus $1 imports, still net zero.
The thing to remember is that GDP is domestic product, so anything produced abroad is irrelevant.
h <- e means (h OR (NOT E)), which is the usual meaning of implication (either the consequent is true or the antecedent is false)
So p(h <- e GIVEN e) = p((h OR (NOT e)) GIVEN e) = p(h GIVEN e) since NOT e is false given that e is true.
Let me try again. I think that Deutsch is saying that h is the proposition "smoker implies cancer", and e is a specific instance of a person where the hypothesis holds (either a nonsmoker or a smoker with cancer). He is talking about e being instances of h, so h must be a higher order proposition about instances.
But now h can be decomposed as we said into a logically necessary part (h|e) and a part (h|~e) that may be true or false depending upon which universe you live in. By the argument above, finding more instances of the theory should decrease our belief in the (h|~e) part. Since h|~e is the same as e->h, gathering more e should decrease our faith that the evidence validates the hypothesis.
Presumably Deutsch is saying that the logically necessary part is sort of trivial (a mere theorem) whereas (h|~e) has actual physical content, so why do we believe that the evidence increases our confidence in the physical portion of the hypothesis?
By the way, I got all this math from the unapproachable paper, which is not that unapproachable if one looks at the math alone. Like you, I am trying to figure out how this math applies to the real world.
For all h and e, you can always write (using C bitwise operations to denote logic) h = (h | ~e) & (h | e). The second factor (h | e) is the part which logically follows from the evidence, that is, it is true in all universes in which e is true. The first factor is the part that is not logically implied by the evidence, that is, there are universes where it is raining in London and yet h is false because London is not in England.
Now the real question: somebody tells you that it is raining in London, so your credence in e goes up. What happens to the probability of (h | ~e)? It should go down, because as e becomes "more true", ~e becomes "more false", and thus (h | ~e) becomes more false in the sense that there are fewer worlds where (h | ~e) is true.
But (h | ~e) is the same as "e implies h", which is your empirical theory. So your belief in the theory should go down as you gather more evidence. Another way to say it is that, as the evidence becomes stronger, the part logically implied by e becomes more likely, and whatever remains (h | ~e) becomes a smaller set of possibilities, so it is less likely.
Note that your belief in (h | ~e) goes down, but your belief in h goes up. I think Deutsch's criticism is that people confuse the two, and they think that evidence increases the credence in the theory instead of the hypothesis.
There are three concepts involved: an evidence "e", for example "I extracted 1 black ball"; a hypothesis "h", for example "the urn does not contain only white balls"; a theory "h <- e" that, by means of logic or otherwise, deduces the hypothesis from the evidence. Your (qsort) theory is that if you see a black ball then the hypothesis is correct.
Everybody, including you, me, and Deutsch, agree that if the probability of the evidence goes up, then the probability of the hypothesis goes up as well.
What Deutsch and Popper/Miller are also saying, however, is that if the probability of the evidence goes up then the probability of the theory goes down (proof in the paper).
I need to study the paper more carefully, because I am not 100% sure that it is strictly correct (there are many factors that would transform a < into <= if they were 1, and I suspect that some are), but I believe the weaker statement that if the evidence goes up the probability of the theory does not go up at all.
In any case, this conclusion is consistent with what all scientists have believed forever: the only way to increase confidence in a theory is to try to break it. Or at least they believed this until fact checkers and censorship came along and threw the baby away with the bathwater.
If you take the position that calculus is the concept of limit and all its consequences, then things like exp() and log() are calculus and it's hard to get anything done in CS without those. In this view, saying that quicksort is O(n log n) is a statement of calculus.
If you say that calculus is derivatives and integrals, then I'd say that calculus is not that important in a digital world, and that discrete math is much more useful. However, discrete math is harder than calculus, but you can use calculus as an approximation to the discrete answer (i.e., compute the integral if you don't know how to compute a sum, or use a derivative to approximate a difference). Ironically, this is the opposite of the old attitude that the continuous answer was the true one and the discrete answer was a poor man's approximation to the true one.
One old convention, mostly originating with radio-frequency connectors, is that the gender of the connector is the gender of its innermost contact. Thus, the plug of the common 2.5" and 2.1" connector of power supplies is technically female because the inner contact is a hole. The socket on the appliance has a pin in the middle and is technically male. When you try to buy one, half the time the part is labelled as male and the other half it is labelled as female.
But there is no problem bad enough that cannot be made worse by government. Years ago some US regulator didn't like the fact that people were plugging big radio antennas into wifi equipment, so they invented the "reverse-polarity" connector. What used to be a "SMA male" connector with a pin in the middle now is a "RP SMA male" connector with a hole in the middle. Here is a random link with a picture: http://cablesondemandblog.com/wordpress1/2014/05/05/reverse_... If you order this kind of connectors, now you have a 25% chance of getting what you need. One RP SMA male and a SMA female will mate together but not propagate any signals.
Some commenters on this thread think that they are too unimportant for AWS to harass them after they leave. The issue is not how important the employee is, but how dangerous a competitor the next employer is from the perspective of AWS. If AWS wants to slow down the competitor, they will use all legal means available to them.
The last thing you want to do is tell investors that you lost money investing the cash that they gave you. For example, US treasury inflation-protected securities maturing on 4/2023 pay CPI inflation minus 3%. Say you buy these securities thinking that it is a good idea to protect yourself against unexpected inflation, and then inflation moderates down to 0% in the next year. How are you going to explain to your investors that you lost 3% of their money?
Beware that, in the 2008 crisis, even some money-market funds lost money. The US money market funds have since been regulated so that they won't lose money in the same way, but I am sure more ways exist. Stay in government bills, insured bank deposits, and money-market funds that invest in government securities only. The extra 0.01% yield is not worth the risk.
The trust of your investors is more precious than the cash they gave you. If in 12-18 months things look good you won't have a problem raising more cash.