pbsd

8 ms·

31.
by pbsd 2y ago
This is the Rao-Sandelius shuffle [1]. [1] https://doi.org/10.1145/3009909
32.
by pbsd 2y ago
An alternative, more arithmetic, argument: - x is 2^b*k for some odd k < 2^(n-b) - -x is 2^n - 2^b*k = 2^b*(2^(n-b)-k) - k is odd by definition, and (2^(n-b)-k) + k = 0 (mod 2^(n-b)). This means that the LSB must be 1 in both operands, w
33.
by pbsd 2y ago
No, you're thinking of PS{R,L}LQ.
34.
by pbsd 2y ago
The 128-bit wide shifts PS{L,R}LDQ only have byte granularity. They're a special case of a byte shuffle.
35.
by pbsd 2y ago
Actually it wasn't Knuth; only the 1997 3rd edition contains the lagged Fibonacci name. The first instance of the name I can find is Marsaglia-Tsay in 1985 [1] (and possibly Marsaglia's 1984 "A current view of random number g
36.
by pbsd 2y ago
The name itself might be due to Knuth; they were initially known as additive generators in other early literature.
37.
by pbsd 2y ago
Go 1's math/rand would more accurately be called an additive lagged Fibonacci generator. The first publication of it is due to Green, Smith, and Klem [1]. [1] https://doi.org/10.1145/320998.321006
38.
by pbsd 2y ago
Brilliant. Can be further simplified to 0x10880 & (0x2240 << i).
39.
by pbsd 2y ago
The overlong lookup can also be written without a memory lookup as 0x10000U >> ((0x1531U >> (i*5)) & 31); On most current x86 chips this has a latency of 3 cycles -- LEA+SHR+SHR -- which is better than an L1 cache h
40.
by pbsd 2y ago
This bias testing is essentially ruling out candidates with very high probability truncated differentials of Hamming weight 1. In a cryptographic primitive you want to rule out _all_ high-probability differentials, which requires different
41.
by pbsd 2y ago
The best asymptotic bound is somewhere between n^(1/8sqrt(e) + eps) and n^(1/6.568sqrt(e) + eps), per [1]. [1] https://doi.org/10.1007/BFb0030409
42.
by pbsd 2y ago
You only need to try the _prime_ bases up to 2 log^2(n). So the total number of bases here would be 79060.
43.
by pbsd 2y ago
Keccak (and other ciphers only using bit rotation and bitwise ops) can use bit interleaving to avoid slow 64-bit rotations on 32-bit hardware, by replacing 1 64-bit rotation by 2 independent 32-bit rotations on the interleaved words [1, §2.
44.
by pbsd 2y ago
Personally I think https://crypto.stackexchange.com/a/86548 is a better answer. It turns the LCG state recovery into a hidden number-like problem, and works out the solution that way. It is easy to go from there to (EC
45.
by pbsd 2y ago
SVP is NP-hard for approximation factors much smaller than this algorithm reaches. This algorithm solves approximation factors of at best O(n^4.5), but NP-hardness is only shown for approximation factors well below n^(1/2). See Figure
46.
by pbsd 3y ago
It's not quite forgotten. It kind of lives on in the pseudo-dot product Wegman-Carter authenticators like UMAC. See Section 3 of [1] for context. [1] https://cr.yp.to/antiforgery/pema-20071022.pdf
47.
by pbsd 3y ago
The LWE problem is one level of abstraction away from the fundamental lattice problems it reduces to. It is somewhat analogous to the Diffie-Hellman problem that many constructions reduce to, which itself is related to the lower-level discr
48.
by pbsd 3y ago
A different way to get a result like this is to observe that the nth Fibonacci number is obtainable as the coefficient of x in x^n mod (x^2-x-1) via the usual matrix exponentiation argument, apply Kronecker substitution, and compute pow(b,
49.
by pbsd 3y ago
x=0 is the last solution to be hit the way I wrote it.
50.
by pbsd 3y ago
A simple way to do the latter is for(u64 x = -m & m; ;x = (x - m) & m) { const u64 r = x ^ m; for(u64 t = -x & x; ; t = (t - x) & x) { const u64 z = r | t; // Use (x,z) if(t == 0) brea
51.
by pbsd 3y ago
While there is more confidence now on the security of SHA-2, or rather the lack of transference of the SHA-1 approach to SHA-2, this was not the case in 2005-2006 when NIST decided to hold the SHA-3 competition. See for example the report o
52.
by pbsd 3y ago
Suppose you wanted to find a root of f(x) = x^3 - a mod N. If there is a root smaller than N^(1/3), this reduces to simply computing the integer cube root of a, since there is no wrap-around. But imagine if the problem is slightly chan
53.
by pbsd 3y ago
extern templates are a C++11 feature. export templates are the removed C++98 feature.
54.
by pbsd 3y ago
FWIW, there are two NTRUs: the original one, which had no djb involvement, and NTRU Prime, which does.
55.
by pbsd 3y ago
This is generally known as "freestanding" in the C/C++ world -- https://en.cppreference.com/w/cpp/freestanding
56.
by pbsd 3y ago
With appropriate padding to ensure each s is in its own separate input block, that is called "envelope" or "sandwich" MAC, and its security can be reduced to the compression function's security using mostly the same
57.
by pbsd 4y ago
"This" as in finding the next combination. Gosper's trick does.
58.
by pbsd 4y ago
That appears to be a direct C++ translation of item 175 from HAKMEM [1]. This does not require a division and can be done much faster, see section 1.24 of [2]. [1] http://www.inwap.com/pdp10/hbaker/hakmem/hack
59.
by pbsd 4y ago
The first one is already explained, a^b + 2*(a&b) is computing the sum and carry in parallel, and then adding them up. The second formula is more elaborate, and makes heavy use of the above identity: 2*(a|b)-(a^b) = 2*((a&am
60.
by pbsd 4y ago
Yeah, I was wrong. Mixed up the signed and unsigned cases.

More ›