Cryptographic primitives

Indistinguishability obfuscation

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. (Wikipedia).

Video thumbnail

Indistinguishability obfuscation from...to jumping pigs - Nir Bitansky

Indistinguishability obfuscation has turned out to be an outstanding notion with strong implications not only to cryptography, but also other areas such as complexity theory, and differential privacy. Nevertheless, our understanding of how to construct indistinguishability obfuscators is s

From playlist Mathematics

Video thumbnail

Indistinguishability Obfuscation from Well-Founded Assumptions - Huijia (Rachel) Lin

Computer Science/Discrete Mathematics Seminar I Topic: Indistinguishability Obfuscation from Well-Founded Assumptions Speaker: Huijia (Rachel) Lin Affiliation: University of Washington Date: November 16, 2020 For more video please visit http://video.ias.edu

From playlist Mathematics

Video thumbnail

Toy Ind3 - Part 02 - Indeterminacy Diagrams

This is terminology introduced to clarify the part of what goes on in IUT3. This isn't really in the body and Mochizuki may view this as implicit. We give an abstract definition of what an indeterminacy diagram is. We will apply this to the Log-Kummer correspondence. Errata: *The maps g

From playlist Toy Ind3

Video thumbnail

Linear Inequalities in Two Variables

http://mathispower4u.wordpress.com/

From playlist Linear and Absolute Value Inequalities

Video thumbnail

CERIAS Security: Obfuscated Databases: Definitions and Constructions 4/6

Clip 4/6 Speaker: Vitaly Shmatikov · University of Texas at Austin I will present some new definitions and constructions for privacy in large databases. In contrast to conventional privacy mechanisms that aim to prevent any access to individual records, our techniques are designed to

From playlist The CERIAS Security Seminars 2005 (1)

Video thumbnail

On the cryptographic hardness of finding a Nash equilibrium - Nir Bitansky

The computational complexity of finding Nash Equilibria in games has received much attention over the past two decades due to its theoretical and philosophical significance. This talk will be centered around the connection between this problem and cryptography. Mostly, I will discuss a res

From playlist Mathematics

Video thumbnail

C21 The annihilator approach

Another, perhaps better, method of solving for a higher-order, linear, nonhomogeneous differential equation with constant coefficients. In essence, some form of differentiation is performed on both sides of the equation, annihilating the right-hand side (to zero), so as to change it into

From playlist Differential Equations

Video thumbnail

CERIAS Security: Obfuscated Databases: Definitions and Constructions 3/6

Clip 3/6 Speaker: Vitaly Shmatikov · University of Texas at Austin I will present some new definitions and constructions for privacy in large databases. In contrast to conventional privacy mechanisms that aim to prevent any access to individual records, our techniques are designed to

From playlist The CERIAS Security Seminars 2005 (1)

Video thumbnail

Method of Undetermined Coefficients

We demonstrate how to solve 2nd order, linear, inhomogeneous differential equations with the Method of Undetermined Coefficients.

From playlist Mathematical Physics I Uploads

Video thumbnail

CERIAS Security: Obfuscated Databases: Definitions and Constructions 1/6

Clip 1/6 Speaker: Vitaly Shmatikov · University of Texas at Austin I will present some new definitions and constructions for privacy in large databases. In contrast to conventional privacy mechanisms that aim to prevent any access to individual records, our techniques are designed to

From playlist The CERIAS Security Seminars 2005 (1)

Video thumbnail

CERIAS Security: Obfuscated Databases: Definitions and Constructions 5/6

Clip 5/6 Speaker: Vitaly Shmatikov · University of Texas at Austin I will present some new definitions and constructions for privacy in large databases. In contrast to conventional privacy mechanisms that aim to prevent any access to individual records, our techniques are designed to

From playlist The CERIAS Security Seminars 2005 (1)

Video thumbnail

Solving Equations Using Multiplication or Division

This video is about Solving Equations with Multiplication and Division

From playlist Equations and Inequalities

Video thumbnail

Bitcoin Q&A: Will Governments Let Privacy Coins Exist?

On the benefits and challenges with upcoming privacy improvements to Bitcoin. What do you think about Snowden's comments on privacy in Bitcoin and open public blockchains? What are unspent transaction outputs (UTXOs)? Can you re-anonymise UTXOs from KYC exchanges like Coinbase, by particip

From playlist Privacy and Surveillance

Video thumbnail

CERIAS Security: Obfuscated Databases: Definitions and Constructions 2/6

Clip 2/6 Speaker: Vitaly Shmatikov · University of Texas at Austin I will present some new definitions and constructions for privacy in large databases. In contrast to conventional privacy mechanisms that aim to prevent any access to individual records, our techniques are designed to

From playlist The CERIAS Security Seminars 2005 (1)

Video thumbnail

Linear regression (5): Bias and variance

Inductive bias; variance; relationship to over- & under-fitting

From playlist cs273a

Video thumbnail

CERIAS Security: Obfuscated Databases: Definitions and Constructions 6/6

Clip 6/6 Speaker: Vitaly Shmatikov · University of Texas at Austin I will present some new definitions and constructions for privacy in large databases. In contrast to conventional privacy mechanisms that aim to prevent any access to individual records, our techniques are designed to

From playlist The CERIAS Security Seminars 2005 (1)

Video thumbnail

The Difference Between a Linear Equation and Linear Inequality (Two Variables)

This video explains the difference between a linear equation and linear inequality in two variables.

From playlist Solving Linear Inequalities in Two Variables

Video thumbnail

Brucon 2009: A new web attack vector: Script Fragmentation 1/6

Clip 1/6 Speaker: Stephan Chenette Abstract: This presentation will introduce a new web-based attack vector which utilizes client-side scripting to fragment malicious web content. This involves distributing web exploits in a asynchronous manner to evade signature detection. Similar

From playlist Brucon 2009

Related pages

Secret sharing | Multilinear map | Computational hardness assumption | Average-case complexity | Non-interactive zero-knowledge proof | Boolean circuit | Zero-knowledge proof | PPAD (complexity) | Key exchange | Trapdoor function | Oblivious transfer | Boolean data type | Learning with errors | Toy model | Pseudorandom generator | Injective function | Cryptography | Cryptographic primitive | NC (complexity) | One-way function | Hash function | Provable security | Polynomial hierarchy | Public-key cryptography | Functional encryption | Gigabyte | Turing machine | Deniable encryption | Black-box obfuscation | Digital signature | Logical conjunction | Adversary (cryptography) | XDH assumption | Advanced Encryption Standard | Quantum computing