16

Complexity leveraging is a type of reduction where the "reduction algorithm" runs in a complexity class that is greater than the adversary. For example, one may construct a simulator that runs in time $n^{\log n}$ although the adversary is only polynomial time. When considering the simulation paradigm, this is not very satisfactory. For example, in zero ...


12

Are the results as ground breaking as the article suggests? This result will prove to be a very important one for theoretical crypto. The analogy to fully homomorphic encryption (mentioned above by Samuel) is useful, since that is another well-known result that was hugely groundbreaking from a theoretical point of view, but even years later the ...


9

Wanted to add some to Mikero's answer. There are three main contributions of the research A proposed indistinguishability obfuscation for NC1 circuits where the security is based on the so called Multilinear Jigsaw Puzzles (a simplified variant of multilinear maps). Pair the contribution in 1 with Fully Homomorphic Encryption and you get ...


8

Program Obfuscation is a method to scramble the program code such that it becomes unintelligible but preserves the program's functionality. The notion of indistinguishability obfuscation was proposed in [BGI+01]. Actually they first consider another notion which is called virtual black box obfuscation (VBB Obfuscation). However, they showed that VBB ...


7

For an easy to grasp explanation, you can have a look at the talk Obfuscation I at the Cryptography Bootcamp by Amit Sahai. Here's a link to youtube. In this context he also explains matrix branching programs, which are also used in the construction of indistuingishability obfuscation. He starts explaining them at the minute 40. In short: You're given $2k$ ...


7

Some general categories that come to mind: Same functionalities from less extreme assumptions; in particular, from falsifiable ones. For example, the FE for Turing machines in GKPVZ requires SNARKs and extractable witness encryption, both of require less plausible "knowledge-type assumptions." See Gentry/Wichs Or taking the above further: Succinct-...


6

PE is a subclass of FE. This (from the other answer) is correct. Also, from my understanding, your analogy is correct. PE returns the plaintext if the predicate evaluates to true. FE, on the other hand, returns a function of the plaintext. We can say that PE is a subclass of FE, since we can use FE to implement PE. Just use the identity function. Your ...


4

I think you are confusing functional encryption and homomorphic encryption. In a functional encryption scheme, using a secret key for some function $f$ on a ciphertext $c$ which is an encryption of $m$ allows you to get $f(m)$ in clear. In an homomorphic encryption scheme, you can run some operation on ciphertexts, and get an encryption of the result, for ...


4

A toy example would be this simple map with $\mathbb{G} = \mathbb{Z}/5$ to $\mathbb{G}_T = \mathbb{Z}^*/11$, as follows: $$e(x,y) = 3^{xy} \bmod 11$$ It's easy to verify that both equations hold (except that $e(0,0) = 1$; that's actually a necessary consequence of the first equation, and so I'll consider that an acceptable exception). Of course, even if ...


4

PE is a subclass of FE. A description can be found on page 256 of the book “Theory of Cryptography: 8th Theory of Cryptography Conference, TCC 2011”. The related paper is available in PDF format via eprint.iacr.org: Functional Encryption: Definitions and Challenges Dan Boneh, Amit Sahai, Brent Waters


4

From InfoSec SE This Security.SE answer should be read before the answer posted here. The following block quote and FPS example are taken from the answer linked. Functional encryption is about providing a computable circuit (obfuscated with IO) which receives as input encrypted versions of some value x, and returns F(x) for some function F, without ...


3

There are ways to prevent Bob from having complete control over the randomness pool. You could use some form of verified randomness, where your function $f$ checks that the random string is signed before executing. This would work using, for instance, the NIST randomness beacon. You could also contain within $f$ a PRNG, so Bob does not need to provide all ...


3

This condition is here just because it is the one that appears in the proof. Usually, decryption will output $\bot$ if some relation is not satisfied. However, there is a non zero probability that the relation is satisfied even when it is not supposed to (it can be some weird case where the secret key is all zeros for example). In practice, this doesn'...


3

My understanding of this is as follows: Monotonic access structure: if $\mathbb{A}$ is a set of attributes satisfying an access structure $T$, then any $\mathbb{A}'$ such that $\mathbb{A} \subset \mathbb{A}'$ also satisfies $T$. For example, consider $T = A \cap B$, then both $\mathbb{A}=\{A,B\}$ and $\mathbb{A}'=\{A,B,C\}$ satisfy $T$. Non-monotonic ...


2

Simply speaking, if any superset of the set satisfying the access structure satisfies the access structure, we call the structure monotonic. Let $\{1,2,...,n\}$ be a set of indices. An access structure is a collection $\mathbb{A}$ of non-empty subsets of $\{1,2,3,...,n\}$. We say a collection (or an access structure) $\mathbb{A} \subseteq 2^{\{1,2,...,n\}}$ ...


2

Indistinguishability Obfuscation (iO) is a quite powerful tool, but its implications alone are really hard to tackle - as so often, the combination of different primitives enables us to do new and exciting things. But before going into details, I am not sure if this is clear to you: If you can use an algorithm $A$ (in your question that would be compact ...


2

Witness encryption is essentially the same thing as hash proof systems (what some people call “smooth projective hash functions”), so we know quite a few examples. The best-known one is probably the Cramer-Shoup SPHF, which can be seen as a witness encryption scheme with respect to the NP language of Diffie-Hellman pairs. Precisely, we have a cyclic group $...


2

One obvious example would be the factorization problem, with the Rabin encryption system. One way of stating the factorization decision problem is: given $x, M$, does there exist integers $y, z$ such that $1 < y < x$ and $yz = M$? The witness would be the values $y, z$. If we constrain the values of $M$ to be Rabin modulii (product of two prime ...


2

If key revocation is a requirement, that is, if Alice no longer works for BigCorp, her keys no longer is able to decrypt email to BigCorp, then it either becomes impractical or easy. That is, you will need to do one of two things: Either you need to update the master public key when Alice leaves. This is likely to be impractical. You require Alice to work ...


2

Actually, what you asked is not unusual, even more, it is always true. Since $Eval(f, Enc(dA)) = Enc(f(dA))$ and $Eval(f, Enc(dU)) = Enc(f(dU))$, if $Eval(f, Enc(dA)) = Eval(f, Enc(dU))$, then $ Enc(f(dA)) = Enc(f(dU))$. Now, if you use the decryption algorithm in both sides, you get $f(dA) = f(dU)$. The same argument applies if we use $Enc(f)$ instead ...


1

I will talk about HE here, since I am not much aware of FE. If you look at Somewhat Homomorphic Encryption schemes, say Lauter et al's scheme in "Can Homomorphic Encryption be Practical", you will find that the cipertext, e-X in you case, has 2 components, one of which depends on the message and the second does not depend on the message (A here). Now, let ...


1

The fact that you want an inverse function means hashing is not appropriate, as hashes are by definition not invertible due to the requirement of preimage resistance. What you're looking for is homomorphic encryption. What operations you need to perform will determine what scheme you need to use. There is fully homomorphic encryption, which allows you to ...


1

Potential Solution? Using Functional encryption, a trusted authority with a master secret key ($msk$) and public key ($pk$) would generate a "functional decryption" key ($sk$) from a participant's policy ($k$). Each participants would be provided the $pk$ and relative $sk$, where $sk$ is bound to the participant's public identity via a signed document. For ...


1

I think this is a very huge question. IO has been proved that it is a very strong tool in cryptography in constructing various cryptographic primitives, such as two-round secure computation, deniable encryption, universal samplers and so on. Also, researchers are still exploring its applications. I think currently the more intriguing problem is how to build ...


1

Attribute-Based Encryption schemes (ABE) are definitionally a sub-category of FE. Furthermore, non-monotonic ABEs (NM-ABE) can encode decisions from $NC^1$, so yes, there are FE-schemes that are restricted to $NC^1$. There are both ciphertext-policy ABEs (CP-ABE), key-policy ABEs (KP-ABE) and mixtures of them (dual-policy, or DP-ABEs), so it is possible to ...


1

No, there is none (as far as is currently known). From Ben Lynn's doctoral thesis on the subject: There is only one known mathematical setting where desirable pairings exist: hyperelliptic curves.


1

If you can live with security against passive adversaries here is how you could do that: Denote the inputs of Alice and Bob $x$ and $y$ respectively. Bob generates public- and private-key for the FHE scheme. He sends the public key to Alice a long with an encryption of his input. Alice encrypts her own input and computes an encryption of $g(x,y)$ using the ...


1

It depends on what you are interested in, when building your expression. If you want to optimize for speed and/or expression size, then the problem is hard, and no good solution is known. You can either try to enumerate all expressions, looking for a match with your table (this is exponential in the size of the expression, so it becomes prohibitive real fast)...


1

It is not true that the functional encryption acts as access control on data since you don't control access on data once you know the key but you know the result of a function applied on data. For instance if the function is find the minimum then you can learn the minimum coefficient of a vector encrypted appropriately. If your function is the decryption ...


Only top voted, non community-wiki answers of a minimum length are eligible