less_less

13 ms·

31.
by less_less 1y ago
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 i
32.
by less_less 1y ago
Oh yeah, factoring the polynomial is also a good idea. For a long enough list that ought to be better than AFFT too.
33.
by less_less 1y ago
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_
34.
by less_less 1y ago
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
35.
by less_less 1y ago
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 er
36.
by less_less 1y ago
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 t
37.
by less_less 1y ago
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
38.
by less_less 1y ago
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.
39.
by less_less 1y ago
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,
40.
by less_less 1y ago
> 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
41.
by less_less 2y ago
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.
42.
by less_less 2y ago
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
43.
by less_less 2y ago
Ah. I didn't mean to introduce a "necessary" constraint at all, but my wording wasn't the best.
44.
by less_less 2y ago
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
45.
by less_less 2y ago
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 cr
46.
by less_less 2y ago
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 pro
47.
by less_less 2y ago
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
48.
by less_less 2y ago
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
49.
by less_less 2y ago
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 migh
50.
by less_less 2y ago
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
51.
by less_less 2y ago
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 int
52.
by less_less 2y ago
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.
53.
by less_less 2y ago
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&#x2
54.
by less_less 2y ago
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 th
55.
by less_less 2y ago
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 br
56.
by less_less 2y ago
> 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 s
57.
by less_less 2y ago
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 (
58.
by less_less 2y ago
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 i
59.
by less_less 2y ago
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 c
60.
by less_less 2y ago
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 ai

More ›