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.

[2] Ariel Futoransky, Emiliano Kargieman, Carlos Sarraute, Ariel
Waissbein. Foundations and applications for secure triggers. ACM TISSEC,
Vol 9(1) (February 2006).


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 [EMAIL PROTECTED]

Reply via email to