New result in predicate encryption: disjunction support

[Ariel Waissbein]

Jonathan Katz wrote:
> On Mon, 5 May 2008, Ariel Waissbein wrote:
> 
>> [Moderator's note: Again, top posting is discouraged, and not editing
>> quoted material is also discouraged. --Perry]
>>
>> Hi list,
>>
>> Interesting. Great work! I had been looking *generic* predicate
>> encryption for some time. Encryption over specific predicates is much
>> older. Malware (e.g., virus) and software protection schemes have been
>> using some sort of "predicate encryption" or "trigger" for over two
>> decades in order to obfuscate code. For example, an old virus used to
>> scan hard drives looking for a BBS configuration files in a similar
>> manner and some software protection schemes have encrypted pieces of
>> code that are decrypted only if some integrity checks (predicates) over
>> other pieces of the program are passed.
>>
>> Triggers/predicates are very promising. Yet, they are only useful in
>> certain applications, since eavesdropping one decryption is enough to
>> recover the keys and plaintext.
>>
>> I co-authored a paper were we used this same concept in a software
>> protection application ([1]) and later we formalized this concept, that
>> we called secure triggers, in a paper eventually publised at TISSEC
>> ([2]). We were only able to construct triggers for very specific
>> predicate families, e.g.,
>>  - p(x)=1 iff x=I for some I in {0,1}^k
>>  - q(x,y,z,...)=1 iff x=I_1, y=I_2, z=I_3,...; and finally
>>  - r(x)=1 iff x_{j_1}=b_1,...,x_{j_k}=b_k for some b_1,...,b_k in {0,1}
>>    and indexes i_1,...,i_k (|x|>=k).
>> While these predicates do not cover arbitrary large possibilities, they
>> are implemented by efficient algorithms and require assuming only the
>> existence of IND-CPA secure symmetric ciphers. In [2] we came up with
>> more applications other than sofprot;)
>>
>> [1] Diego Bendersky, Ariel Futoransky, Luciano Notarfrancesco, Carlos
>> Sarraute and Ariel Waissbein. "Advanced Software Protection Now". Core
>> Security Technologies Tech report.
>> http://www.coresecurity.com/index.php5?module=ContentMod&action=item&id=491
>>
>>
>> [2] Ariel Futoransky, Emiliano Kargieman, Carlos Sarraute, Ariel
>> Waissbein. Foundations and applications for secure triggers. ACM TISSEC,
>> Vol 9(1) (February 2006).
>>
>> Cheers,
>> Ariel
> 
> Predicate encryption sounds very different from the work you are
> referencing above. (In particular, as we discuss in the paper, predicate
> encryption for equality tests is essentially identity-based encryption.)
> I refer you to the Introduction and Definition 2.1 of our paper, which
> should give a pretty good high-level overview.
> 

Hi Jonathan,

and thanks for taking your time to answer. I had already read the
Introduction and had a quick --i admit-- read over the paper before
posting to the list. I think that the main difference are the
applications we are looking at (and I know Sahai's earlier work in
obfuscation). Take a look at the first three sentences of our article:

> Fix a bitstring, that we regard as a secret. Let be given a family of predicates, and
> secretly draw a predicate from this family according to a known distribution. Think
> of predicates as functions with range in {true, false}. We consider algorithms that
> return the secret if their input evaluates to true on the chosen predicate, else they
> return nothing.

Of course, the main difference is that one must hold SK (and f) in order
to decrypt messages according to the predicate encryption scheme. Note
that if the adversary is given the algorithm i\mapsto SK_{f_i} then
predicate encryption turns out to be similar to generic secure triggers.
However, we didn't cover predicates evaluating inner product so that's
what caught my interest, why I want to analyze how your work applies to
other problems (and why I think that the schemes are similar).

Cheers,
Ariel

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com