New result in predicate encryption: disjunction support

[Jonathan Katz]

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.

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