密碼學背景
密碼學關注各種不同類型的對象及其可以滿足的安全屬性。在複雜性理論(與信息理論相對)密碼學中，都會通過安全參數 λ 調節所有算法的運行時間，包括攻擊者，以及攻擊者的成功度量，稱為其"優勢"。典型的要求是所有算法（包括攻擊者）的運行時間在安全參數中是多項式 ，並且攻擊者的優勢是可忽略的 ，即漸進地小於 λ 中任何多項式的倒數。（可以對對手更加寬容，例如允許其運行時間和/或逆優勢在 λ 中是次指數的，允許其非均勻等。）在下文中，所有函數族都隱含地由 λ 索引，並且所有算法（包括攻擊者）都將 λ 作為輸入。

函數族與安全屬性
函數族是函數 ，對於某些鍵空間 K、域 X 和範圍 Y。稱其為族，因為它定義了函數集 ，其中鍵 。如果 ，即函數在某種程度上"壓縮"其輸入，則通常稱為哈希函數。以下是函數族的兩個常用安全屬性：

• 族 f 是單向的，如果對於隨機輸入"難以逆轉"。更準確地說，給定 和 ，其中 k,x 從規定的分佈中隨機選擇，難以找到任何原像 。
• 族 f 是抗碰撞的，如果對於隨機鍵難以找到碰撞。更準確地說，給定隨機 （從規定的分佈中選擇），難以找到不同的 使得
  

公鑰加密
非對稱(也稱為公鑰) 加密方案是具有以下接口的三種隨機化算法：

• 密鑰生成器，給定安全參數，輸出公鑰和私鑰。
• 加密算法，使用公鑰和消息（來自某些已知的有效消息集）並輸出密文。
• 解密算法，使用私鑰和密文，輸出消息或特殊的"失敗"符號。

如果生成密鑰對，然後使用公鑰加密有效消息，然後使用私鑰解密生成的密文，得到原始消息（可能除可忽略的概率外），則該方案被稱為正確的。
一個標準的安全概念，稱為語義安全[GM82]，或在選擇明文攻擊下的不可區分性（IND-CPA），非正式地保證加密對被動（竊聽）對手不透露任何關於加密消息的信息。形式上，定義考慮以下實驗，該實驗由一個 bit 為 的參數化:

1. 生成公鑰/私鑰對，並將公鑰給攻擊者，攻擊者必須回復兩個有效消息
   。（如果有效消息空間只是 {0,1}，則可以不失一般性地假設 。）
2. 使用公鑰加密 並將生成的"挑戰密文"給攻擊者。
3. 最後，攻擊者接受或拒絕。

如果攻擊者在 b=0 和 b=1 兩種情況下接受的概率僅相差可忽略的量，則加密方案被稱為語義（或 IND-CPA）安全的。即，兩種情況下接受的概率應僅相差可忽略的量。
一個更強的安全概念，稱為主動安全或更正式地，在選擇密文攻擊下的不可區分性（IND-CCA) ，通過給攻擊者訪問解密預言機來增強上述實驗，即攻擊者可以查詢任何密文（挑戰密文除外）的解密算法（使用私鑰）。（此限制當然是必要的，因為否則攻擊者可以請求解密挑戰密文從而學習 b 的值。）如果攻擊者難以區分b=0 和 b=1 兩種情況，則該方案被稱為主動（或 IND-CCA）安全的。

更豐富的加密形式
在過去幾年中，人們對具有額外有用特徵的加密系統的興趣日益增加。例如，同態加密允許不可信的工作者對加密數據執行有意義的計算，而不向工作者透露任何關於數據的信息。在這種情況下，基本語法和 IND-CPA 安全的概念保持完全相同，但有一個額外的算法用於對密文執行所需的同態計算。
另一個例子是基於身份的加密（IBE），其中任何字符串（例如用戶的電子郵件地址）都可以作為公鑰。這裡的模型略有不同：IBE 是具有以下接口的四種隨機化算法:

• 設置算法，給定安全參數，輸出"主"公鑰和私鑰對。
• 密鑰提取算法，使用主私鑰和身份字符串，輸出該特定身份的私鑰。
• 加密算法，使用主公鑰、身份字符串和有效消息，輸出密文。
• 解密算法，使用身份私鑰和密文，輸出消息（或失敗符號）。

正確性以預期的方式定義: 對於加密到特定身份字符串的密文，使用相應的私鑰(由密鑰提取算法生成)解密會返回原始消息。
非正式地，IBE 的語義安全通過修改標準 IND-CPA 實驗來建模以下屬性：即使許多用戶通過組合其私鑰進行合謀，他們仍然無法了解加密給另一個用戶的消息。更正式地，考慮以下實驗：攻擊者被給主公鑰，以及對密鑰提取算法（內置主私鑰）的預言機訪問，從而允許其獲取任何其選擇的身份的私鑰。在某個時刻，攻擊者產生兩個消息 和一個目標身份，該身份必須與其對密鑰提取預言機的所有查詢不同。然後攻擊者被給予一個加密 給目標身份的密文，並可以在接受或拒絕之前對其預言機進行進一步查詢。

[GM82] S. Goldwasser and S. Micali. Probabilistic encryption. J. Comput. Syst. Sci., 28(2):270–299,
1984. Preliminary version in STOC 1982.