Discussion
learning about kyber from wikipedia https://en.wikipedia.org/wiki/ML-KEM
Compared to competing PQ methods, it has typical advantages of lattice-based methods, e.g. in regard to runtime as well as the size of the ciphertexts and the key material.[6]
"advantages of lattice-based methods" they are famously the slowest and biggest but go off i guess
replacing the extremely efficient, non-quantum-safe ECDH key exchange using Curve25519 was found to increase runtime by a factor of about 2.3 (1.5–7), an estimated 2.3-fold (1.4–3.1) increase in energy consumption, and have about 70 times (48–92) more data overhead.[11]
i love when they make the data actively adversarial. "70 times (48-92)" lmao
wait this is so funny so hashing-based PRNGs like......aren't really cryptographically secure i think
so most of the runtime of this method is hashing and now i wonder if it's really all a con. i doubt it
like if it's truly just "use SHA-3 a lot" i think that would be funny
i am reading the "lattice crypto is real u guise" paper. it is an IBM paper, in every sense of the word https://dl.acm.org/doi/epdf/10.1145/237814.237838
Consequently the theorem (and Remark 1) implies that if at least one of the three worst-case problems have no polynomial time probabilistic solutions then f is a one-way function.
"have no polynomial time probabilistic solutions" is very strange to read. is that literally just implying quantum computing is probabilistic polynomial time because lol lmao
love that it's like oh it's ok there are three of them for more safety
Sketch of the proof. We prove the theorem for therandom variable A’ instead of A. The fact that their distribution is exponentially close to each other is not proved in this paper but can be found in [Ajt].
you can't be serious. looking up that reference reveals:
[Ajt] M. Ajtai, “Generating Hard Instances of Lattice Problems” Electronic Colloquium on Computational Complexity, 1996. TR96-007, http:// www. eccc.uni-trier.de/eccc/
do i type in the http:// link
jesus fucking christ mastodon why do you linkify anything beginning with www
holy fucking shit dude. you can't search for that paper online cause it has the same name as this paper. the provided link doesn't work and it now redirects to israel not germany
Now we apply our probabilistic algorithm A, whose existence was assumed,
ridiculous paper
oh the A part is ok
In fact we give a random problem: find a short vector in a certain class of random Iattices (whose elements can be generated together with a short vector in them), whose solution in the mentioned sense would imply the solution of a group of related “famous” problems in the worst case.
It has been realized a long time ago that a possible solution would be to find a set of randomly generated problems and show that if there is an algorithm which finds a solution of a random instance with a positive probability, then there is also an algorithm which solves one of the famous unsolved problems in the worst case.
i'm not sure if this is wrong but it's incredibly misleading:
i think it may be correct technically but no IBM paper is ever just correct. that place is just not a source of truth
anyway now they've rolled this out during wartime very cool
oh wait lmao mihir bellare completely validated my hypothesis https://cseweb.ucsd.edu/~mihir/papers/inchash.pdf
The problem is you need to store the entire tree, meaning all the intermediate hash values.
bet?????????
To date the only incremental hash function was proposed by [BGG1], based on work of [CHP].
ok ok ok ok ok ok ok ok ok
This function is based on discrete exponentiation in a group of prime order. It uses one modular exponentiation per message block to hash the message.
YEAH!!!!!!!!!!!!!!!!!
oh lmao i did not realize i was describing incremental hashing this whole time. ok cool so i am atm equivalent to mihir bellare in 1996
It turns out that even putting incrementality aside, functions resulting from our paradigm have attractive features, such as parallelizability.
jack nicholson zoom in jpg
What we want is to store only the final hash value and be able to increment given only this.
sorry this is just a ridiculous, absurd requirement when describing filesystem integrity???? when someone modifies your hard drive where did it happen??? it's literally C * log^2 n space i think???? i don't think it's that much???? nobody else is doing the memory analysis???
also this paper does the WORST FUCKING SHIT THAT I HATE and puts an incredibly lengthy appendix after the citations
now they're like oh yeah chaum invented discrete log signatures and the last time anyone mentioned chaum it was to thank him for inventing the mixnet which he did not invent nor even describe
but it's even worse this time because it's the same shit as lattice crypto where the paper is an "extended abstract" and the real one is named the same and impossible to find
The cryptographic assumption, needed for the security of the recipients, is that we have an infinite sequence of groups G_p of known prime orders p, where one can perform the group operations and choose random elements efficiently, but the discrete logarithm is hard.
that is not an assumption i will make?????
mihir bellare just talking out of his ass now https://cseweb.ucsd.edu/~mihir/papers/inc1.pdf
Some care must be taken in formalizing this since the update algorithm receives the entire nb-bit message as input and in a standard Turing machine model could not even read the relevant part in poly(k, b) time. Thus we assume a RAM type computation model and in the formal definition allow the update time to depend on log n.
that's not a footnote-type comment but it's in the tiniest possible text? i have never heard of "the security parameter k" before in my life??? i have also never heard of anyone assuming a RAM type model before either
jfc
We pin-point an ideal incremental scheme for collision-free hashing which is based on the hardness
of the discrete logarithm in groups of prime order.
there are definitely other hardnesses it works for?
Hashing an n-block message (each block k bits long) to a k bit string takes n exponentiations, while updating takes two exponentiations; these exponentiations are modulo a O(k)-bit prime.
that is a lot of exponentations? also isn't it going to be commutative?
Note the hash functions we discuss here are ones of public description. That is, the description of the function is provided to the adversary trying to find collisions. This is unlike the hash functions used in applications like finger-printing, where the description of the function is not available to
the collision-finder!
none of this makes sense?????
In keeping with the philosophy of an adaptive chosen message attack [13], we must allow the adversary to obtain examples of signatures under the update algorithm.
i don't think adaptive chosen message attacks are about philosophy?
it's also not called that. it's adaptive chosen plaintext or ciphertext
Incrementality is fundamentally a practical concern because it is a measure of efficiency.
bullshit meter off the charts
Clearly, an (ideal) incremental scheme is a win over a standard one as message sizes get larger. The practical concern is what is the cross-over point: if incrementality only helps for messages longer than I am ever likely to get, I am not inclined to use the incremental scheme.
"i will not use the more efficient scheme because i sometimes might not get the benefit"
Install bonfire.cafe
Get the full app experience
