less_less

As I understand the paper, the point is that Fiat-Shamir does *not* give a correct proof of the program's output.

They gave a (maliciously constructed) program whose outputs are pairs (a,b) where certainly a != b (instead the program is constructed such that a = b+1 always). But you can get the corresponding Fiat-Shamir protocol to accept the statement "I know a secret x such that Program(x) = (0,0)", which is clearly a false statement.

Oh yeah, factoring the polynomial is also a good idea. For a long enough list that ought to be better than AFFT too.

Adding to some other comments in the thread: finding missing or extra numbers is closely related to error-correcting codes, especially binary linear codes. In an error-correcting code, you have a string of bits or symbols, with symbol x_i appearing at position i. You choose the code so that valid sequences have a certain mathematical property, and then if one or a few symbols are corrupted, then you can use that property to correct the errors. The property is typically that a certain linear function called the "syndrome" is zero, meaning that sum(x_i * G_i) = 0 where each G_i is some strategically chosen vector, particular to the code. The math for how to correct is particular to the chosen G_i, and it's a really interesting field of study.

In a typical error-correcting code usage, you have an encoder which takes your message, and adds some extra symbols at the end which are calculated so that the syndrome is zero. Then when receiving your message, the receiver calculates the syndrome and if it's not zero, they know that at least one error has occurred. By using the code's decoding algorithm, they can figure out the fewest (and thus hopefully most likely) number of changes which would result in that error syndrome, and use this information to (hopefully) correct the transmission error.

For the missing numbers problem, you can set x_i to "how many times does the number i appear?". Then since the syndrome is sum(x_i * G_i), you can compute the syndrome on an unordered list of the i's. You are expecting the syndrome to be the same as the syndrome of full set 1...n, so when it is not, you can figure out which few x_i's are wrong that would lead to the syndrome you observed. You have an advantage because you know how many numbers are missing, but it's only a slight one.

The author's solution is called the Hamming code: you set F(i) = i, and you do the additions by xoring. Using error-correcting codes generalize to more missing numbers as well, including using xor, but the math becomes more complicated: you would want to use a fancier code such as a BCH or Goppa code. These also use xor, but in more complicated ways.

If you imagine a polynomial L(z) that's zero at all the missing numbers, you can expand the coefficients out. For example, with 2 missing numbers (x,y), you have:

   L(z) = z^2 - (x+y)z + xy.

You already have x+y, but what's xy? You can compute it as ((x+y)^2 - (x^2 + y^2))/2. This technique generalizes to higher powers, though I forget the exact details: basically you can generate the coefficients of L from the sums of powers with a recurrence.

Then you solve for the roots of L, either using your finite field's variant of the quadratic formula, or e.g. just by trying everything in the field.

* But wait, this doesn't actually work! *

Over fields of small characteristic, such as F_2^m, you need to modify the approach and use different powers. For example, in the equations above, I divided by 2. But over F_2^m in the example shown above, you cannot divide by 2, since 2=0. In fact, you cannot solve for (x,y) at all with only x+y and x^2 + y^2, because

  (x+y)^2   =   x^2 + y^2 + 2xy   =   x^2 + y^2 + 0xy (since 2=0)   =   x^2 + y^2

So having that second polynomial gives you no new information. So you need to use other powers such as cubes (a BCH code), or some other technique (e.g. a Goppa code). My sibling comment to yours describes the BCH case.

This will depend on the field, and for F_2^m you want odd powers: sum(x), sum(x^3), sum(x^5) etc. Using sum(x^2) won't help because squaring over F_2^m is a field homomorphism, meaning that sum(x^2) = sum(x)^2.

This is also how BCH error-correction codes work (see https://en.wikipedia.org/wiki/BCH_code): a valid BCH codeword has sum(x^i where bit x is set in the codeword) = 0 for t odd powers i=1,3,5, ... Then if some bits get flipped, you will get a "syndrome" s_i := sum(x^i where bit x was flipped) for those odd powers. Solving from the syndrome to get the indices of the flipped bits is the same problem as here.

The general decoding algorithm is a bit involved, as you can see in the Wikipedia article, but it's not horribly difficult:

  • First, extend the syndrome: it gives sum(x^i) for odd i, but you can compute the even powers s_2i = s_i^2.

  • The syndrome is a sequence of field values s_i, but we can imagine it as a "syndrome polynomial" S(z) := sum(s_i z^i).  This is only a conceptual step, not a computational one.

  • We will find a polynomial L(z) which is zero at all errors z=x and nowhere else.  This L is called a "locator" polynomial.  It turns out (can be checked with some algebra) that L(z) satisfies a "key equation" where certain terms of L(z) * S(z) are zero.  The key equation is (almost) linear: solve it with linear algebra (takes cubic time in the number of errors), or solve it faster with the Berlekamp-Massey algorithm (quadratic time instead, maybe subquadratic if you're fancy).

  • Find the roots of L(z).  There are tricks for this if its degree is low.  If the degree is high then you usually just iterate over the field.  This takes O(#errors * size of domain) time.  It can be sped up by a constant factor using Chien's search algorithm, or by a logarithmic factor using an FFT or AFFT.

You can of course use a different error-correcting code if you prefer (e.g. binary Goppa codes).

Edit: bullets are hard.

Further edit just to note: the "^" in the above text refers to powers over the finite field, not the xor operator.

The data-dependent prefetcher is a cool feature, though you do have to be careful with side-channel issues, so some of them can disable it with the Data-Independent Timing bit or similar.

At this point I'm kinda expecting CPU vendors to stop putting as many Spectre mitigations in the main core, and just have a small crypto core with full-fat arithmetic, less hardware for memory access, less speculation, and careful side-channel hardening. You still have to block Meltdown and other large vulnerabilities on the main cores, but if someone wants to protect elliptic curves from weird attacks? Try to set the DIT bit, trap into the OS, and get sent to the hardened core.

Neat, but if you're using this in cryptographic code (one of the main consumers of bignums), keep in mind that secret data reaching branches is usually a side-channel risk. Sure, it's only 1 time in 2^64 on random data, but if you're depending on that, then you have to consider whether an attacker can choose data that will make it happen more often.

If you can substitute a cmov without control flow then it's probably safer, e.g. c1 |= c0 & seq(s1,-1) or so, so long as you can make sure the compiler won't turn it into a branch.

It does add a data dependency though ...

If you want to use Bloom filters for compression, you might want to consider binary fuse filters, ribbon filters or similar which avoid the 1/ln(2) leading factor in space usage.

The theory of elliptic curves goes amazingly deep. Scratching the surface slightly more, to fill in the article's "ignore the labels like 2P":

Intersecting the curve with lines the way the author does is, perhaps shockingly, a commutative group operation, known as point addition. You define this operation by saying that the three points A,B,C on a line sum to zero: that is A+B+C=0 or in other words, A+B = -C. Reflecting across the curve's line of symmetry is negation (there's an alternative definition that extends to curves without reflection symmetry). Combining the two defines an operation A+B which adds two points on the curve and gives a third one: draw the line from A to B, intersect it with the curve to find a point -A-B (using the same type of formula given in this article) and then reflect it to get A+B. This addition operation obviously commutes (meaning, the line between A and B is the same as the line between B and A), but surprisingly it also associates and you get a group operation.

(For math olympiad nerds out there: so the union of a conic and a line is also a bivariate cubic equation. You can carry out the same "addition" operation there. Again the operation clearly commutes. But it also associates! This is basically Pascal's theorem.)

The theory of elliptic curves is also the basis of elliptic curve cryptography. In that case, instead of the curve being over the reals, all the calculations are done mod some prime p, which destroys structure based on continuity and prevents the numbers from becoming too large. There are a bunch of subtleties here but the key is that you can still straightforwardly compute addition in this context, with basically the same formulas. Then from addition you can get n*A, both for small integers n (eg 5*A = A+A+A+A+A) but also for large n (e.g. 2*A = A+A; 66*A = 2*2*2*2*2*2*A + 2*A). This "scalar multiplication" operation is a one-way operation for appropriately chosen curves: it's easy to calculate n*A from (n,A), but as far as we know it is hard to calculate n from (A,n*A) ... at least if you can't build a large quantum computer.

This gives you mix of easy operations (eg, addition and scalar multiplication) plus problems believed to be hard, which is a great starting point to build cryptography. There are a lot of important technical details, though fewer than with the new lattice schemes.

(Further comment on the olympiad thing: so you can do this with conic+line too, extending from addition to multiplication and using the same formulas mod p. But it's not as good: it's not hard to find a projection that sends the line to infinity and the conic to the unit circle or similar, and then the group operation becomes equivalent to multiplying the points' coordinates as complex numbers or similar. If the group operation is equivalent to multiplication, then scalarmul becomes equivalent to exponentiation, which ends up being in Fp or Fp^2 depending on some Legendre symbol or other. Exponentiation is still potentially secure: it's basically classical Diffie-Hellman. However, more attacks are known on exponentiation in Fp or Fp^2: the attacks don't outright break it but you need p to be much bigger.)

Edit: unescaped stars make italics.

> Human-read numbers are big endian and dates should be big endian to maintain that consistency.

... in English, anyway. A lot of languages are little-endian both for dates and for at least 2-digit numbers, if not larger numbers.

(Just in case your post isn't a joke.)

It tells the shell utility that any remaining arguments are not options, but instead files or whatever the script might process. You know, in case someone makes a file called -rf.

True, but also the work can be reduced significantly with better tooling, which is still being developed but has improved markedly over the past decade. Eg SMT solvers that can output proofs, or tactics in Coq or Lean.

I'm hoping that this will be a big application of AI actually. If an AI can be built do to this simple but very tedious work, and your verification tool is capable of catching any errors it makes, then you've covered up a major flaw of formal verification (its tediousness) and of AI (its tendency to output bullshit).

Ah. I didn't mean to introduce a "necessary" constraint at all, but my wording wasn't the best.

OK, I'm sorry for the touchy response. But I still don't understand your point.

Breaking a hash is a prototypical NP problem (ok maybe FNP). SAT is the prototypical NP-hard problem.

I was just trying to explain that using SAT to attack hashes is therefore unsurprising, and does not in any way imply that breaking hashes is NP-complete, the way that it would if the reduction went in the other direction.

Surely the same logic would make sense for another class M, if you had a problem "M-HASH" that's clearly in M, and an M-hard problem "M-SAT" to reduce it to? There might be other problems that you could also reduce to M-SAT, but mentioning that it solves all of M is what's relevant if M-HASH is in M.

Yeah, SVP is NP-complete for certain parameters. But lattice cryptography uses other parameters where SVP might not be NP-complete. Also lattice crypto is usually based some other lattice problem like LWE, MLWE, MLWR, SIVP etc.

Lattice crypto is going to be broadly deployed because it hopefully can resist quantum attack, unlike ECDLP and factoring.

What?

Being in NP doesn't exclude being in P. Every problem in P is also in NP.

The definition of "NP-complete" is "in NP, and also NP-hard". The definition of "NP-hard" is that you can reduce any NP problem to it using a poly-time mapping reduction (also known as a Karp reduction). So yes, SAT being NP-complete does mean that you can reduce any NP problem to SAT, using a poly-time mapping reduction.

Breaking a hash (e.g. collision finding) is in NP, because you can easily check a proposed solution. Well, with an obvious quibble: P and NP are about asymptotic complexity, but most hash functions are fixed-size. Also if you're looking at complexity theory you might want to talk about targeted collision finding, or first or second preimage resistance, but same deal there. But anyway, supposing you choose a keyed hash that does scale so that you can talk about its asymptotic complexity at all, and has a poly-time cost to evaluate it, breaking that hash would be in NP. Therefore it can be reduced to SAT using a poly-time mapping reduction.

Breaking hash functions is in NP, but isn't expected to be NP-complete, meaning that you can't easily encode eg a SAT problem into a hash function, such that breaking the hash solves the SAT problem.

You can do the reverse (encode the hash into a SAT problem), but that's possible for any NP problem, because SAT is NP-complete.

Suppose that p-1 has no large prime factors, eg suppose p-1 divides 10000!, then you can factor N by calculating something like x = random() ^ (10000!) % N. Then x will be 1 mod p (or rarely 0, if x was) but probably not mod q unless q has the same property. Then gcd(x-1,N) = p, and you've factored N. A similar trick works with Lucas sequences if p+1 has no large prime factors. So instead of attacking your key with a very expensive algorithm that doesn't care about special properties of p,q, they might gamble that your key is weak and try a cheaper algorithm first. So folks would avoid keys where p+1 or p-1 was "smooth" in this way.

However, we don't care much about this attack anymore for two reasons. One is that N must now be big enough to resist attack by the Number Field Sieve (and not just the Quadratic Sieve). At least if there are only two primes in the RSA key, this means that p,q must be big enough for these attacks to be very unlikely to work. But just as importantly, it turns out that you can do the above attack with exponentiation on a random elliptic curve instead of regular exponentiation / Lucas sequences. This is how most math libraries implement factor(). It's slightly slower but since the random elliptic curve will have a random order instead of exactly p+1 or p-1, it is equally likely to work with any p,q of a given size, regardless of special properties they might have.

In other words, an attacker can re-randomize how weak or strong a key is by using elliptic curves. So there's not much point in avoiding ones that look weak at first glance.

Yeah that's right, there are no known cryptosystems whose security is based on the difficulty of solving an NP-hard problem. It's not known even in theory whether P != NP implies that one-way functions exist: for example, it might be that all NP problems are easy on average, or that there are problems that are hard on average but that you can't sample the problems and their solution at the same time.

(And this is even with the simplification that polytime = practical and not-polytime = infeasible.)

This is a really cool result, and I'm looking forward to reading Part 3.

My view on the ROM is that cryptographic proofs (the ones we are able to actually do) always rule out only some attacks but not out others. A standard model (non-ROM) proof will still be under some assumption about lattices or elliptic curves or AES or whatever, will be valid only under a certain model of the attacker's capabilities and goals, and will often have tightness issues (where the parameters or probability of success on the "proved" system will be worse than with the assumption). Even a tight unconditional proof (such as for the one-time pad) assumes a certain model of the attacker's goals and capabilities.

The ROM is another axis of this: a ROM proof rules out attacks that treat the hash function as a random oracle. Since hash functions are designed to have as few non-ROM properties as possible, and since most real attacks on cryptosystems either break the hash or treat it as a random oracle, ruling out those attacks can usually give you some confidence. But if your cryptosystem is itself making use of non-ROM properties of the hash, then it gives you a lot less confidence, and that's the situation of this new KRS result.

It's not really "of course", and I don't think we have such a theorem in general. But in this case, I believe the fact that it's not an integer follows from the same theorem that says it's very close to an integer. See eg https://math.stackexchange.com/questions/4544/why-is-e-pi-sq...

Basically e^(sqrt(163)*pi) is the leading term in a Laurent series for an integer, and the other (non-integer) terms are really small but not zero.

ECC is pretty closely related to the study of prime numbers. It might not be built directly on the difficulty of factoring, but the theory of how to construct curves, how to use them, what's expected to be secure etc goes pretty deep.

When the data is read-only, sparse linear filters get up to an O(ln 2)-factor smaller storage space at the cost of slower construction and inability to add items on the fly. These include xor-sat filters, xor/xor+ filters, smashed/bumped ribbon filters, frayed ribbon filters, binary fuse filters, probably a few other options.

The basic idea is that instead of table[hash1(x)] & table[hash2(x)] & ..., you calculate table[hash1(x)] ^ table[hash2(x)] ^ ... basically substituting XOR instead of AND. To construct the table, you need to solve a big system of linear equations. The various filter types change the parameters (mostly load factor of the filter) and indexing function (turning the hash into something where the bits you look up have correlated positions) in order to make structured equations that are easier to solve.

Unsolvable would mean that no proof exists, and no disproof exists, in whatever axiom system (eg ZF). While in some cases you can hack around this by proving eg "no proof and no disproof exist in ZF, if ZF is consistent", IIUC that's not always possible. It's like asking "when will AI be strong enough that it can always decide correctly whether a given computer program halts?"

Then again, it's fairly likely that P=?NP is decidable but we just don't have any idea how to prove it. In that case the question is more or less "what's the time horizon until AI is vastly better than humans at formal math?", to which the answer is certainly "we don't know, there may be obstacles, just wait and see".

Geez like pretty much everything. See eg https://slate.com/culture/2014/12/the-imitation-game-fact-vs...

Enigma was originally broken by a team of Polish cryptanalysts, who invented both a paper method to break it (Zygalski sheets) and the machine shown in movie (Rejewski's bomba). Turing later worked on a team to improve the bomba, which was a significant achievement but he didn't invent or spearhead the whole thing.

All this "don't use a machine to do a man's job" was bullshit invented for the movie, as were like half the other conflicts. Everyone involved knew that breaking Enigma was important, and they were already using a machine to do it, but after the Nazis changed their use of Enigma, the Brits needed mathematical insights to improve the speed of their machine.

The main characters in the film did exist and had some of the personality traits shown, but mostly didn't interact they way that the film showed. Turing was openly gay. Cairncross (the spy) didn't work with Turing. The codebreakers didn't choose which intercepted information to use and how, etc.

> DJB is high profile enough that all of his stuff gets a lot of cryptanalysis from experts. This isn't a rando proposing a scheme that no one can follow, and no one can be bothered to review. He consistently designs cryptographic systems which perform better and are less error prone to implement than systems designed by committees of people.

So in my opinion, NTRU Prime is a good cryptosystem. But it's not particularly better than Kyber: each has small advantages and disadvantages, and both got a ton of expert review (Kyber even more than NTRU Prime), and they will probably stand or fall together depending on improvements in lattice cryptanalysis.

I also don't think Kyber suffers from design-by-committee. There are a zillion small choices to make in these lattice schemes, and while some choices are definitely wrong, both the NTRU Prime and Kyber teams made reasonable ones. The same goes for SABER and regular NTRU.

SLH-DSA aka SPHINCS+ is the most conservative choice (i.e. they are all secure against currently-known attacks, but SLH-DSA is less likely to be broken later), but it is slow (at least several milliseconds to sign) and produces large sigs (>= 7.8kB). This means that it may not be suitable for all applications.

Dilithium is faster but less conservative, harder to implement securely, and produces medium sigs.

FALCON is even harder to implement securely, faster to verify and produces smaller sigs, though still much larger than classical systems. IMHO this choice was questionable, in that its advantages overlap too heavily with Dilithium to be worth another standard, but NIST apparently felt otherwise.

DJB's signature proposal is SPHINCS+, which is standardized in FIPS 205 as SLH-DSA. NTRUPrime is a KEM, so it doesn't really compete with FALCON.

Personally I think that FALCON is brilliant, but it is very difficult to securely implement or even precisely define, due to heavy use of floating-point arithmetic in the signing routine. I don't want to put words in DJB's mouth, but if you share his concern for ease of secure implementation, ease of auditing and side-channel protection, then you may prefer SPHINCS+ or, if the performance of SPHINCS+ is not acceptable in your workload, possibly Dilithium.

Of course, if signature size is make-or-break, then of the choices currently slated for standardization, FALCON has the smallest signatures. But it is possible that the new signature onramp will change that in a few years -- if you can be confident in the security of whatever is chosen within so short a time.

Of course you'd want to put those terms in the employment contract, not just a verbal promise. Surely you wouldn't get exactly the same protection as in another country with a completely different legal system, but at least you could get part of it.

And yeah, they could terminate the contract, but they would still be bound by its terms that say how they can do that, with how much notice, for what reasons, and how much they will owe you.

If you're just talking about basic encryption achieving no properties other than security against passive attack, then just nesting is probably fine. But in more complex systems, things end up being fairly subtle, so cryptographers aim for very specific security properties for the building blocks, and then try to combine these in a way that can be proved secure, at least in some attack model. This reduces the likelihood of a complex attack like the TLS triple handshake attack, where the protocol looks fine intuitively but can be broken by some weird pattern of forwarding messages between multiple parties.

So for example, nesting does not preserve IND-CCA security ("indistinguishability under chosen ciphertext attack"). Suppose you set ciphertext = outer_encrypt(outer_key, inner_encrypt(inner_key, data)). If the outer encryption system is broken, then an attacker can strip the outer layer and re-encrypt it. This will result in a different ciphertext, because if either layer is aiming for IND-CCA security, the encryption is necessarily randomized. Being able to modify ciphertexts in this way violates the IND-CCA-security goal. Then if another part of the system is designed assuming that the cipher is IND-CCA-secure, then its security is now at risk.

The attack surface is even broader if the system supports multiple combinations of ciphers, where an attacker might strip off one cipher layer and replace it with a different one.