  This paper studies the limitations of the generic approaches to solving
cryptographic problems in classical and quantum settings in various models.
  - In the classical generic group model (GGM), we find simple alternative
proofs for the lower bounds of variants of the discrete logarithm (DL) problem:
the multiple-instance DL and one-more DL problems (and their mixture). We also
re-prove the unknown-order GGM lower bounds, such as the order finding, root
extraction, and repeated squaring.
  - In the quantum generic group model (QGGM), we study the complexity of
variants of the discrete logarithm. We prove the logarithm DL lower bound in
the QGGM even for the composite order setting. We also prove an asymptotically
tight lower bound for the multiple-instance DL problem. Both results resolve
the open problems suggested in a recent work by Hhan, Yamakawa, and Yun.
  - In the quantum generic ring model we newly suggested, we give the
logarithmic lower bound for the order-finding algorithms, an important step for
Shor's algorithm. We also give a logarithmic lower bound for a certain generic
factoring algorithm outputting relatively small integers, which includes a
modified version of Regev's algorithm.
  - Finally, we prove a lower bound for the basic index calculus method for
solving the DL problem in a new idealized group model regarding smooth numbers.
  The quantum lower bounds in both models allow certain (different) types of
classical preprocessing. All of the proofs are significantly simpler than the
previous proofs and are through a single tool, the so-called compression lemma,
along with linear algebra tools. Our use of this lemma may be of independent
interest.
