【难解任务】
在计算复杂性理论下，密码学通常把那些不能由概率多项式时间模型完成的任务视为难解任务（Intractable Tasks）。也就是说，如果一个攻击任务不能被任何概率多项式时间模型有效完成，那么它就可以作为密码学安全性的基础
这里之所以使用概率多项式时间敌手模型，是因为密码学中的敌手通常被允许使用随机性。例如，敌手在进行攻击加密方案、伪造数字签名等任务时，都可以采用随机化攻击策略。因此，密码学中的高效敌手通常不是确定性多项式时间模型，而是概率多项式时间模型
然而，密码学中关心的许多敌手任务，例如攻破加密方案、伪造数字签名等，具有一个重要特点：一旦找到了一个候选解，它是否有效通常很容易验证。因此，这类任务可以由非确定性多项式时间模型完成，即密码学中的许多攻击问题与 NP 类问题密切相关
【复杂性前提】
由于密码学中的攻击任务通常可被有效验证，如果所有 NP 问题都能够被概率多项式时间模型有效解决，那么这些攻击任务也可能被高效完成。在这种情况下，基于计算困难性的密码学就失去了意义。因此，计算复杂性秘密学真正有意义的前提是：
这个条件的含义是：并不是所有可以被有效验证的问题，都可以被概率多项式时间模型有效求解。换句话说，至少存在某些 NP 问题，即使允许随机性，也仍然无法高效解决
这个前提比单纯的 $\mathcal{P} \neq \mathcal{NP}$ 更适合密码学语境。因为密码学中的敌手通常不是确定性算法，而是允许使用随机性的概率算法。因此，密码学关心的不只是确定性多项式时间算法是否足够强，而是概率多项式时间算法是否也无法完成攻击任务
【难解性假设】
如果上述复杂性前提不成立，那么计算复杂性密码学并不是逻辑上不成立，而是没有实际意义。原因在于，密码学中的很多结论都具有如下形式：
也就是说，如果某个难解性假设（Intractability Assumption）成立，那么某个有用的密码学结论成立
这种条件命题即使在前提错误时，也可能在形式逻辑上保持成立。但是，如果难解性假设本身是错误的，那么由它推出的密码学结论就缺乏实际价值
因此，问题不在于这些定理是否在逻辑上有效，而在于它们是否建立在可信的难解性假设之上。若难解性假设不可信，那么相应的密码学构造虽然仍然是形式化的数学结论，但对真实安全性没有意义
在很多情况下，一个有用的密码学结论并不是完全独立于难解性假设的。相反，密码学结论本身往往会反过来蕴含某种难解性假设，或者至少蕴含该假设的某种较弱形式。也就是说，许多密码学原语的存在本身就意味着某些计算问题必须是困难的，否则这些问题如果能被概率多项式时间模型高效解决，那么相应的密码学原语就会被攻破
因此，在计算复杂性理论下，通常不能期望完全不依赖任何难解性假设，就直接证明某些有用的密码学结论
【敌手模型的选择】
一般情况下，密码学中的敌手被建模为概率多项式时间模型，直观来说，其是一个运行时间受多项式限制、并允许使用随机性的攻击算法。因此，密码学中的难解性假设通常针对概率多项式时间模型提出
不过在少数情况下，仅考虑概率多项式时间模型还不够，还需要考虑更强的非均匀多项式时间模型，其允许敌手针对不同输入长度获得不同的多项式长度建议信息
相应地，针对非均匀多项式时间模型的难解性假设也更强。如果一个任务对于非均匀多项式时间模型都是困难的，那么它对于普通概率多项式时间机器当然也是困难的
不过，除非确实必要，否则应优先使用概率多项式时间模型，原因是概率多项式时间模型通过归约能够得到相应的非均匀多项式时间模型，但反过来并不一定成立
因此，用概率多项式时间模型表述的结论在理论上更强，也更值得优先采用
【平均情形复杂性】
密码学所需要的难解性假设，不能只停留在最坏情形复杂性（Worst-Case Complexity）上。例如，仅仅假设某个问题在最坏情况下很难，并不能直接保证一个密码方案是安全的
原因在于，密码学方案必须在实际使用中的大多数情形下都难以攻破。如果一个方案只是存在某些特殊实例很难被攻破，而在大量普通实例上容易被攻破，那么这个方案没有实际安全意义
因此，密码学真正需要的是平均情形复杂性（Average-Case Complexity）意义下的难解性。也就是说，敌手不仅不能在某些最困难的实例上成功，而且在典型实例或多数实例上也不能有效成功
目前复杂性理论还无法证明：
如果能够证明这样的结论，将是计算复杂性理论中的重大突破。正因为目前无法从最坏情形难解性推出平均情形难解性，所以密码学中的难解性假设必须直接针对平均情形复杂性提出
