# Tag Info

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 ...

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 ...

5

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-...

3

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

3

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$ ...

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 ...

2

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 ...

1

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 ...

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

Existing definitions for functional encryption don't support "combining" ciphertexts in the way that you suggest. As far as doing more than just access control, two very recent papers (to appear next month at STOC 2013) achieve functional encryption for arbitrary functionalities: Attribute-Based Encryption for Circuits by Gorbunov, Vaikuntanathan, Wee ...

1

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 ...

1

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\}}$ ...

1

The previous answers skip an important fact. I think that a PE for all circuits and A FE for all circuits are equivalent in the sense that you can build the second from the first one (the opposite direction is trivial). A key for a circuit C with output size of $n$ bits can be implemented as $n$ PE keys in which the $i$-th key is relative to the circuit ...

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