it feels incredibly trippy to be reading about quantum physicists (an evil science) using group theory (a lovely beautiful field misused by the horrors) to do just their normal average everyday sort of evil as opposed to the horrors
18
Replies
6
Boosts
This comment is unavailable — it may have been deleted or is not visible to you.
This comment is unavailable — it may have been deleted or is not visible to you.
This comment is unavailable — it may have been deleted or is not visible to you.
This comment is unavailable — it may have been deleted or is not visible to you.
This comment is unavailable — it may have been deleted or is not visible to you.
This comment is unavailable — it may have been deleted or is not visible to you.
This comment is unavailable — it may have been deleted or is not visible to you.
This comment is unavailable — it may have been deleted or is not visible to you.
This comment is unavailable — it may have been deleted or is not visible to you.
This comment is unavailable — it may have been deleted or is not visible to you.
https://dl.acm.org/doi/pdf/10.1145/321328.321337?download=true
Unrecognizable Sets of Numbers (1966)
and he literally cites our boy rabin too
The technique described in this note enables one to show that certain sets cannot be recognized by finite state automata
GOD FUCKING DAMN IT IS THAT WHY AUTOMATA THEORY SUCKS TOO
We consider here only the binary representation, so as to avoid pompous statements, but the same results can be obtained for any radix by changing all 2’s to r’s in the sequel. We warn readers not to confuse the statement that the primes written in binary form are not a regular set with the trivial statement that the set of strings of prime length is not regular.
this is just the discrete log problem?????
If
a_nis of odd length,2k+1, it has the forma_n = b_n 2^{k+1] + d 2^k + b_n, wheredis0or1.
this also gives the q = 2p + 1 relation??? this is also an actual analysis of the appropriateness of discrete log as a CSPRNG???
@hipsterelectron I mean... the whole CS base curriculum kinda sucks. to me, one main reason is that we do "CS" rather than "informatics" in the first place.
@promovicz well i recently learned that all of the people i hate who literally without exaggeration work for the israeli genocide apparatus (chomsky working for MIT means he is very much included, MIT is the problem) were all central to the development of "formal languages" as a field. it makes perfect sense how i was able to develop completely novel work without any prior expertise
@promovicz i fervently believe there was a concerted effort to deskill and disengage academic study in operating system development (worldwide!!!) after the late 90s and most certainly to do the same for cryptography and other forms of mathematics since well before then (it began around the late 70s but really took shape in the 80s with ECC created soon after RSA, because modular exponentiation alone was in act too powerful and easy to understand). but i'm actually more concerned about basic symmetric cryptography. NIST limiting AES to 128-bit block size while varying key size was an incredibly dirty trick and they knew it
@promovicz and of course this means parsing must be denigrated and discarded as a field of investigation or research, which means compilers and programming languages pass that on to their users, and it means vulnerabilities, everywhere, because parsing is definitionally the system's boundary with external input.
@promovicz there's very much a reason the turing machine employs a tape, and it's because it was expected to recieve input, and process it, and produce output, and this was supposed to go to the user. and mark rabin (who called dibs on formal languages, and cryptography earlier) would strike the first gruesome and contemptuous blow against the turing machine, with extreme prejudice
@hipsterelectron i would love to know the reason for TM construction "with tapes", or good modern arguments for the choice, because i've been wondering.
for my own models, i'm undecided whether input/output memory should be separate, or just seen as the same memory with different constraints on the in/out side.
@promovicz it's the simplest general model. the framing that a turing machine's purpose is to transform the tape is completely fucked. that's not the point at all. the point is that you have mutable state, some of which you can set aside, and other sections that can grow freely. the restrictive nature of the single tape works specifically for problems that work like implicit graph traversals. you can and should add on whatever else you want. a stack or two is always a good idea (although two stacks is really more useful for things that do parse strings)
@promovicz the problem comes when you start handwaving away logarithmic factors for larger machines and processes. in many cases you may have a problem that you can verify won't grow in memory past a certain amount: modular exponentiation in the forward direction is an example where the turing machine makes it excessively simple to make strong claims about runtime, particularly since bignum arithmetic conforms so naturally to the tape that moves one at a time.
you should not be feeling like the turing machine constrains you. make a better model if it works. you can do that too. the turing undecidability paper was to prove undecidability exists, similarly to how modular exponentiation is almost a kind of joke to demonstrate one-way functions (mostly) exist (i need to do more group theory to maintain safety everywhere).
hellman claims the choice of q = 2p + 1 is specifically to trade off between exponential computation and exponential memory. i haven't found a good proof for this yet, but the idea deeply compels me. you can make the enemy dance for you. they can't touch you.
@hipsterelectron yes - i don't feel constrained by the Turing model at all, because we have a reasonable understanding of its equivalences (imo). my open question on "programs as transforms" has its origins in information theory, and the idea that programs don't necessarily answer/solve specific problems (which is a traditional premise i'm poking at).
@promovicz i promise i'm not hating on you personally but i absolutely fucking hate the word information theory it just makes me too pissed off to use about my own work anymore. reading this paper about how much simpler kolmogorov's model had been for decades with painstaking work to piece together the pieces bell labs shit out was so important to me https://projecteuclid.org/ebooks/berkeley-symposium-on-mathematical-statistics-and-probability/Proceedings-of-the-Fourth-Berkeley-Symposium-on-Mathematical-Statistics-and/chapter/Mathematical-Problems-in-the-Shannon-Theory-of-Optimal-Coding-of/bsmsp/1200512168.pdf
@promovicz the complexity basis behind secure modular exponentation can be viewed from a computational perspective and a data and memory perspective. both of these are necessary at once for crypto, e.g.:
a^x = b (mod q)- [represented as a bitstring, therefore as
[0, 2^{k}]], wherek = floor(log_2 q) - 1, - hellman said you can actually perform
floor(log_a k)squaring operations here (for reallog_a), not justfloor(log_a q), and such squaring becomes faster here because you can make it a bit shift. the state you keep track of here is just the remaining squares!
so this was half of it. this is the computational view. now we bring in what i call the dataflow view.
for example:
- if
a < sqrt(q), do we "lose" some information here? what is divulged? what abouta < cubert(q)? [i saw these two roots in succession in in a number theory textbook yesterday somehwere]
but immediately we then must break out some level of group theory, because typically while q - 1 is a generator of F_q, the other cycles are smaller (and if not a cycle, they may branch out elsewhere). which produces a much less random sequence than then used in solution. and the group theoretical approach gives us ridiculously more power to analyze these and essentially to mitigate them, because it can make statements about the size of possible generating groups at the start
i still can't say yet what exactly made hellman concerned enough to write that second paper on q = 2p + 1. to me, this is largely still mediated through the smaller groups, but i can't say much about those yet.
consider another example, from "symmetric" crypto (although i absolutely hate that term as its because by definition it's literally not symmetric
i don't fully know what any of the SHAs does and BLAKE3 is even worse as it is literal djbware. here's a question i posed earlier: how much "information" (which i may deem the integral of "data) is being ignored in these cases:
- read each byte at a time, left to right (the standard)
- reading in blocks, and proceeding always left to right
- unrestricted: taking advantage of not just that the end of the message is later than all the earlier tokens, but also the same kind of local information that something like AES with a counter mode like AES-GCM achieve. at the same time!
@promovicz i have a really terrible symmetric algorithm based upon the final point, and as you may have [intuituted it works by squaring or something, in fact, without workiing too hard by spliting it halfway, and following the point of some .
there's a curious connection.! in the forward [heroic] direction, modular expentiation, we wanted to force our adversity to perform some maximum form of work which coulld not be replaced or amortized. of course you know of the CSPRNG use case for discrete log -- i am now working to understand and determine the subcyclic behavior so that we achieve both computational and informational unguessability.
now consider an insecure system: you could break e.g. the key scheduler for the AES-encoded message. but (speakiung abstractly here) you cannot invert the transformation uniquely at all without the key for my half-assed cipher, because it mixes and modifies data across the entire length of the message, and the message is also a cyclic group if you go both directions, outwards from the center! and i fully believe this is in fact capable of (if certainly not now) the precise unconditional security that claude shannon was so stumped on.
you could also establish the cross-influence upon the key and the message and determine more specific bounds, according to a model of computation and (if you're careful) an "oracle" or "game" experiment with bounded security failures.
dataflow serves as a kind of "conservation of energy"-like principle for me to design safe systems. one reason i despise the "probabilistic turing machine" is because it directly makes excuses and cheats auditors of the author's clever notation. but for discrete log, there is a fundamentally serial computation required to factor the largest subgroup of q - 1. and that is in fact how you can achieve security. and the turing machine happens to represent that alright in many cases
@hipsterelectron i don't do cryptog actively at the moment because "stress avoidance" - but i do think these are worthy angles. it's sad that this is a loaded subject.
@hipsterelectron I am an evil scientist muahhahahaha
@jackielovescompchem32 you can do evil science without being evil. but you can also be evil without being bad
@jackielovescompchem32 i like lenstra's and schoof's papers a lot even if they specifically focus on factoring methods and the hellman paper where he advises the use of a prime q = 2p + 1 was also doing some evil math but it was necessary to demonstrate the good math
@jackielovescompchem32 i wonder whether/how slight deviations from periodic standing waves might manifest in quasiperiodic or intermittently high-period behavior. i suppose that would largely agree with the periodic-as-discrete view by e.g. briefly introducing the next largest prime factor
