不可區分混淆
![]() | 此條目包含過多行話或專業術語,可能需要簡化或提出進一步解釋。 (2021年8月1日) |
不可區分混淆(英語:Indistinguishability obfuscation,常作iO[1]:1),是一種形式化定義了程式混淆的密碼原語。白話地說,混淆隱藏了程式的內部實現,但用戶仍可運行它。[2]
候選構造
最早基於具體困難性假設,可證安全的候選構造在2013年提出。該假設和多線性映射有關,但後來該假設被推翻了。[3][4]
一系列後續工作試圖將iO基於更標準的假設。賈殷(Jain)、林和薩海於2020年出版的研究將iO建基於XDH假設、LWE假設和LPN假設。[4][1]此外,該構造還需要NC0實現的超線性延展的偽隨機數生成器。[1]直至2006,即使只考慮亞線性延展的NC0偽隨機數生成器,其存在性一直是未解問題。[5]
可能應用場合
若不可區分混淆器存在,它們可用於海量的密碼學構造裡。[2][4]具體地說,不可區分混淆器可用於以下的場合:
- 公鑰密碼學(以及其IND-CCA—安全版本)[6]
- 短數字簽名[6]
- IND-CCA—安全的密鑰封裝方案[6]
- 完美零知識的非交互零知識證明和簡賅的非交互論證(即證明方計算能力有限的證明)[6]
- 常數輪交互並行的零知識協議[1]
- 有限多項式次數的多重線性映射 (密碼學)[1]
- 單射陷門函數[6]
- 全同態加密[1]
- 見證加密[1]
- 任何單調NP語言的秘密分享[1]
- 半誠實不經意傳輸[6]
- 抵賴加密(不論是發送者抵賴還是完全抵賴)[6][1]
- 多方,非交互密鑰交換[1]
- 適應性安全簡賅的亂碼(Garbled)RAM[1]
- RAM模型任意程式的不可區分混淆[1]
- 關係難尋(Correlation intractible)函數[1]
- 屬性加密[1]
- PPAD困難性。[1]
不過,iO不是萬能的:例如,甚至在假設陷門排列的情況下,都無法通過黑盒構造由iO構造出抗撞的密碼雜湊函數,除非允許指數級的安全性損失[7]。
參見
- 黑箱混淆,一種更強,但一般情況下不可能實現的混淆形式。
參考文獻
- ^ 1.00 1.01 1.02 1.03 1.04 1.05 1.06 1.07 1.08 1.09 1.10 1.11 1.12 1.13 1.14 Jain, Aayush; Lin, Huijia; Sahai, Amit. Indistinguishability Obfuscation from Well-Founded Assumptions. 2020 [2021-08-15]. arXiv:2008.09317
. (原始內容存檔於2022-03-03).
- ^ 2.0 2.1 Klarreich, Erica. Cryptography Breakthrough Could Make Software Unhackable. Quanta Magazine. 2014-02-03 [2021-08-15]. (原始內容存檔於2022-04-14).
- ^ Sanjam Garg; Craig Gentry; Shai Halevi; Mariana Raykova; Amit Sahai; Brent Waters. Candidate Indistinguishability Obfuscation and Functional Encryption for all Circuits. FOCS 2013 (IEEE). 2013: 40–49. ISBN 978-0-7695-5135-7. doi:10.1109/FOCS.2013.13.
- ^ 4.0 4.1 4.2 Klarreich, Erica. Computer Scientists Achieve 'Crown Jewel' of Cryptography. Quanta Magazine. 2020-10-10 [2021-08-15]. (原始內容存檔於2022-05-07).
- ^ Applebaum, B; Ishai, Y; Kushilevitz, E. Cryptography in NC0 (PDF). SIAM Journal on Computing. 2006, 36 (4): 845–888 [2021-08-15]. doi:10.1137/S0097539705446950. (原始內容 (PDF)存檔於2021-11-30).
- ^ 6.0 6.1 6.2 6.3 6.4 6.5 6.6 Sahai, Amit; Waters, Brent. How to Use Indistinguishability Obfuscation: Deniable Encryption, and More. 2013 [2021-08-15]. (原始內容存檔於2022-02-03).
- ^ Asharov, Gilad; Segev, Gil. Limits on the Power of Indistinguishability Obfuscation and Functional Encryption. 2015 [2021-08-15]. (原始內容存檔於2022-01-21).