in DH 1976:

It appears, however, that choosing the {a_i} uniformly from {0, 1, 2, ..., 2^(n-1)} results in a hard problem with probability one as n -> infinity.

that's five different separate notations to refer to the n-vector a_i, and the type of a_i is only inferred by implication to be integers. so that's fucked, whatever.

["a_i" sounds like a cute "AI" joke. interesting that there are large high-dimensional matrices involved]

anyway, they tried this cryptosystem with merkle in 1978:

Merkle, Hellman 1978: Hiding Information and Signatures in Trapdoor Knapsacks

so it sucks, and hellman would have known it sucked. this is the method [1] they cited:

Horowitz, Sahni 1974: Computing Partitions with Applications to the Knapsack Problem

it's important to understand this is specifically describing the VERY SPECIFIC GROUP-THEORETICAL METHOD WITH SUNZI'S THEOREM TO BREAK A DISCRETE LOG CRYPTOSYSTEM!

eight years after this obviously fucked cryptosystem from merkle and hellman, our hero adi shamir investigates the situation:

Adi Shamir, 1982: A POLYNOMIAL TIME ALGORITHM FOR BREAKING THE BASIC MERKLE-HELLMAN CRYPTOSYSTEM

obviously, because the lattice system of hellman and merkle is not using a hard problem, but solving one, and then pretending they're doing real crypto. the "cryptanalysis" is obvious

FIFTEEN YEARS LATER, cynthia dwork, later turing awardee, introduces a "post-quantum" cryptosystem:

Dwork, 1997: A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence

[the URL says 1996, but the title says 1997. the page with all versions is at https://eccc.weizmann.ac.il/report/1996/065/]

[and you'll want to OCR this by hand, because the pdf text layer has an encoding firefox can't interpret]

To our knowledge this is the first public key cryptosystem with the property that to break a random instance is as hard as to solve the worst-case instance of the problem on which the system is based.

if that's true, then diffie-hellman wouldn't be safe either, because even "random" exponents x would produce recognizably simpler solutions a^x (mod p). we will move on, though, to its actual security claim:

Find the shortest nonzero vector in an n dimensional lattice L where the shortest vector v is unique in the sense that any other vector whose length is at most a constant power of n times the length of v, is parallel to v.

you may notice there is no private key involved in this problem. that is because there is no information being protected here. the user is being made to solve the precise combinatorial problem that attacks the discrete log problem.

Decryption of a ciphertext x is performed using the private key to determine the distance of x to the nearest hidden hyperplane. If this distance is sufficiently small, then x is decrypted as zero; otherwise x is decrypted as one. There is a small (but polynomial) probability of an error in decryption: an encryption of one may be decrypted as zero.

so you perform a huge amount of repeated matrix multiplications in order to extract exactly one bit, which may have polynomial error.

let's continue to:

Appendix 1: Lattice-Based Cryptography

again, recall dwork received the turing award for "differential privacy". we continue:

In a recent paper, a positive result on the hardness of computing the most significant bits of a Diffie-Hellman secret key was obtained by rounding in lattices using basis reduction [5].

what is [5]? it is, in fact, at first glance, directly explaining how to use discrete log as a CSPRNG:

D. Boneh and R. Venkatesan, 1996: Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes

the answer to this one is curious. in both the downloadable single article as well as my separate copy of the CRYPTO 1996 proceedings, this paper declares:

An interesting point is that breaking modified the Diffie-Hellman scheme modulo a composite is as hard as factoring integers. We leave the details for the final version of the paper.

there is no final version of the paper, in either copy. but don't fret!

The modified scheme modulo a composite still retains the property that the most significant bit of the secret is as hard to compute as the entire secret.

this was not proven! however, in my copy of the CRYPTO 1996 proceedings, they describe:

The results in [GL] allow us up to k = epsilon * log s(n) where, s(n) is a lower bound on the time for inverting F on all but a negligible fraction of non-zero instances.

this isn't supposed to be correct. the next sentence is what matters:

Since the security of DLP is sub exponential, Ic will be at most sub linear.

this is false

Current rounds of standards advocate hashing g^(ab) with a collision resistant hash function (e.g. MD6, SHA).

the purpose of a CSPRNG is to use complexity theory to produce an algorithmically unpredictable sequence. ron rivest's backdoored hash functions do not achieve this.

finally, we cover [GL]:

[GL] 0. Goldreich, L.A. Levin. Hard core bits based on any one way function. In Proc. ACM Symp. on Theory of Computing 1989.

this does not exist and has never existed. see https://dl.acm.org/doi/proceedings/10.1145/73007 for the full listing, which provides https://dl.acm.org/doi/10.1145/73007.73010

anyway, it cites this guy andrew yao a lot, whose entire thing is about factoring discrete log parameter sets and uploads a massive technical report on every subproblem of it