Indistinguishability obfuscation (original) (raw)
En cryptologie, l'obfuscation indistinguable ou iO est un modèle de sécurité dans lequel on peut espérer prouver certaines propriétés cryptologiques. Ce modèle postule l'existence d'un algorithme efficace dont l'effet approximatif est de réécrire un programme informatique, de sorte qu'un adversaire ne parvienne pas à distinguer de manière fiable deux programmes ainsi réécrits, lorsque ces derniers sont assez similaires. L'existence postulée d'un tel algorithme, pour lequel plusieurs candidats sont aujourd'hui proposés, a des conséquences importantes en cryptologie et en sécurité informatique.
| Property | Value |
|---|---|
| dbo:abstract | In cryptography, indistinguishability obfuscation (abbreviated IO or iO) is a type of software obfuscation with the defining property that obfuscating any two programs that compute the same mathematical function results in programs that cannot be distinguished from each other. Informally, such obfuscation hides the implementation of a program while still allowing users to run it. Formally, IO satisfies the property that obfuscations of two circuits of the same size which implement the same function are computationally indistinguishable. Indistinguishability obfuscation has several interesting theoretical properties. Firstly, iO is the "best-possible" obfuscation (in the sense that any secret about a program that can be hidden by any obfuscator at all can also be hidden by iO). Secondly, iO can be used to construct nearly the entire gamut of cryptographic primitives, including both mundane ones such as public-key cryptography and more exotic ones such as deniable encryption and functional encryption (which are types of cryptography that no-one previously knew how to construct), but with the notable exception of collision-resistant hash function families. For this reason, it has been referred to as "crypto-complete". Lastly, unlike many other kinds of cryptography, indistinguishability obfuscation continues to exist even if P=NP (though it would have to be constructed differently in this case), though this does not necessarily imply that iO exists unconditionally. Though the idea of cryptographic software obfuscation has been around since 1996, indistinguishability obfuscation was first proposed by Barak et al. (2001), who proved that iO exists if P=NP is the case. For the P!=NP case (which is harder, but also more plausible), progress was slower: Garg et al. (2013) proposed a construction of iO based on a computational hardness assumption relating to multilinear maps, but this assumption was later disproven. A construction based on "well-founded assumptions" (hardness assumptions that have been well-studied by cryptographers, and thus widely assumed secure) had to wait until Jain, Lin, and Sahai (2020). (Even so, one of these assumptions used in the 2020 proposal is not secure against quantum computers.) Currently known indistinguishability obfuscation candidates are very far from being practical. As measured by a 2017 paper, even obfuscating the toy function which outputs the logical conjunction of its thirty-two Boolean data type inputs produces a program nearly a dozen gigabytes large. (en) En cryptologie, l'obfuscation indistinguable ou iO est un modèle de sécurité dans lequel on peut espérer prouver certaines propriétés cryptologiques. Ce modèle postule l'existence d'un algorithme efficace dont l'effet approximatif est de réécrire un programme informatique, de sorte qu'un adversaire ne parvienne pas à distinguer de manière fiable deux programmes ainsi réécrits, lorsque ces derniers sont assez similaires. L'existence postulée d'un tel algorithme, pour lequel plusieurs candidats sont aujourd'hui proposés, a des conséquences importantes en cryptologie et en sécurité informatique. (fr) 不可區分混淆（英語：Indistinguishability obfuscation，常作iO），是一種形式化定義了程式混淆的。白話地說，混淆隱藏了程式的內部實現，但用戶仍可運行它。 (zh) |
| dbo:wikiPageID | 59961754 (xsd:integer) |
| dbo:wikiPageLength | 20828 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1109611237 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Multilinear_map dbr:Toy_model dbr:Boolean_data_type dbr:Quantum_computing dbr:Pseudorandom_generator dbr:Computationally_indistinguishable dbr:Cryptography dbr:Oblivious_transfer dbr:One-way_function dbr:Russell_Impagliazzo dbr:One-way_functions dbr:NC_(complexity) dbr:Cryptographic_primitive dbr:Logical_conjunction dbr:Computational_hardness_assumption dbr:Deniable_encryption dbr:Zero-knowledge_proof dbr:Functional_encryption dbr:Key_exchange dbr:Parity_learning dbr:Probabilistic_polynomial-time dbr:Public-key_cryptography dbr:Hash_function dbr:Learning_with_errors dbr:Advanced_Encryption_Standard dbr:Amit_Sahai dbr:P=NP dbr:Digital_signature dbr:Fully_homomorphic_encryption dbr:Provable_security dbr:Adversary_(cryptography) dbr:Key_encapsulation dbr:Black-box_obfuscation dbc:Cryptographic_primitives dbc:Software_obfuscation dbr:Trapdoor_function dbr:Average-case_complexity dbr:Boolean_circuit dbr:Polynomial_hierarchy dbr:Injective_function dbr:Open-source_software dbr:Secret_sharing dbr:Turing_machine dbr:Gigabyte dbr:Non-interactive_zero-knowledge_proof dbr:PPAD_(complexity) dbr:XDH_assumption dbr:Trapdoor_permutation dbr:IND-CCA dbr:P_=_NP dbr:Quantum_computers dbr:Mathematical_function dbr:Software_obfuscation dbr:Witness_encryption |
| dbp:date | January 2022 (en) |
| dbp:reason | Has someone checked this for Jain et al. 's proposal yet, or any of the other more recent ones? ~Duckmather (en) |
| dbp:wikiPageUsesTemplate | dbt:Dubious dbt:Reflist dbt:Short_description dbt:Technical dbt:Update_inline dbt:Speculation_inline dbt:Synthesis_inline dbt:Broader |
| dcterms:subject | dbc:Cryptographic_primitives dbc:Software_obfuscation |
| rdfs:comment | En cryptologie, l'obfuscation indistinguable ou iO est un modèle de sécurité dans lequel on peut espérer prouver certaines propriétés cryptologiques. Ce modèle postule l'existence d'un algorithme efficace dont l'effet approximatif est de réécrire un programme informatique, de sorte qu'un adversaire ne parvienne pas à distinguer de manière fiable deux programmes ainsi réécrits, lorsque ces derniers sont assez similaires. L'existence postulée d'un tel algorithme, pour lequel plusieurs candidats sont aujourd'hui proposés, a des conséquences importantes en cryptologie et en sécurité informatique. (fr) 不可區分混淆（英語：Indistinguishability obfuscation，常作iO），是一種形式化定義了程式混淆的。白話地說，混淆隱藏了程式的內部實現，但用戶仍可運行它。 (zh) In cryptography, indistinguishability obfuscation (abbreviated IO or iO) is a type of software obfuscation with the defining property that obfuscating any two programs that compute the same mathematical function results in programs that cannot be distinguished from each other. Informally, such obfuscation hides the implementation of a program while still allowing users to run it. Formally, IO satisfies the property that obfuscations of two circuits of the same size which implement the same function are computationally indistinguishable. (en) |
| rdfs:label | Indistinguishability obfuscation (en) Obfuscation indistinguable (fr) 不可區分混淆 (zh) |
| owl:sameAs | wikidata:Indistinguishability obfuscation dbpedia-fr:Indistinguishability obfuscation dbpedia-zh:Indistinguishability obfuscation https://global.dbpedia.org/id/7rkvK |
| prov:wasDerivedFrom | wikipedia-en:Indistinguishability_obfuscation?oldid=1109611237&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Indistinguishability_obfuscation |
| is dbo:knownFor of | dbr:Amit_Sahai dbr:Shai_Halevi |
| is dbo:wikiPageDisambiguates of | dbr:Io dbr:Indistinguishability |
| is dbo:wikiPageWikiLink of | dbr:Encryption dbr:Index_of_cryptography_articles dbr:Io dbr:Obfuscation_(software) dbr:Computational_hardness_assumption dbr:Lattice-based_cryptography dbr:Amit_Sahai dbr:Shai_Halevi dbr:Black-box_obfuscation dbr:Indistinguishability dbr:Outline_of_cryptography |
| is foaf:primaryTopic of | wikipedia-en:Indistinguishability_obfuscation |