It is a long-standing open problem whether the Minimum Circuit Size Problem (MCSP) and related meta-complexity problems are NP-complete. Even for the rare cases where the NP-hardness of meta-complexity problems are known, we only know very weak hardness of approximation. In this talk, we discuss NP-hardness of approximating meta-complexity with nearly- optimal approximation gaps. Our key idea is to use *cryptographic constructions* in our reductions, where the security of the cryptographic construction implies the correctness of the reduction. Using this approach, we show: - Assuming subexponentially-secure indistinguishability obfuscation exists, we prove es- sentially optimal NP-hardness of approximating conditional time-bounded Kolmogorov complexity (Kt(x | y)) in the regime where t ≫ |y|. • Unconditionally, for any constant c > 1, the Minimum Oracle Circuit Size Problem (MOCSP) is NP-hard to approximate, where Yes instances have circuit complexity at most s, and No instances have circuit complexity at least s^c.