I was struggling to wrap my head around how federated social media works until I realized that email has basically been doing the same thing for 30 years. Different email servers are like instances of a federated network. You can send emails to people from within a single server or you can send emails to people on any other mail server. Your email address is a username followed by an ‘@’ and the server address, just like on Lemmy. Email is a decentralized service I’ve been using the whole time!
Encryption was illegal back in those days, especially for export. Google “crypto wars”.
Furthermore it was quite computationally expensive. Modern CPUs have special instructions to work with AES and other algorithms, but back then it had to be done with individual instructions and with slow clock speeds.