Re: New result in predicate encryption: disjunction support

2008-05-06 Thread 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 [EMAIL PROTECTED]


Re: New result in predicate encryption: disjunction support

2008-05-06 Thread 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 [EMAIL PROTECTED]


Re: New result in predicate encryption: disjunction support

2008-05-05 Thread Ariel Waissbein
[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

Ivan Krsti? wrote:
> This is fairly interesting: AFAIK the first generalization of predicate
> encryption to support disjunctions. I find the result mostly interesting
> mathematically, since I expect we won't be seeing predicate encryption
> in widespread use anytime soon due to complexity and regulatory
> concerns. --IK
> 
> 
> 
> "Predicate Encryption Supporting Disjunctions, Polynomial Equations, and
> Inner Products"
> Jonathan Katz and Amit Sahai and Brent Waters
> 
> Preprint: 
> 
> Abstract: Predicate encryption is a new paradigm generalizing, among
> other things, identity-based encryption. In a predicate encryption
> scheme, secret keys correspond to predicates and ciphertexts are
> associated with attributes; the secret key SK_f corresponding to the
> predicate f can be used to decrypt a ciphertext associated with
> attribute I if and only if f(I)=1. Constructions of such schemes are
> currently known for relatively few classes of predicates.
> We construct such a scheme for predicates corresponding to the
> evaluation of inner products over N (for some large integer N). This, in
> turn, enables constructions in which predicates correspond to the
> evaluation of disjunctions, polynomials, CNF/DNF formulae, or threshold
> predicates (among others). Besides serving as what we feel is a
> significant step forward in the theory of predicate encryption, our
> results lead to a number of applications that are interesting in their
> own right.
> 
> -- 
> Ivan Krsti? <[EMAIL PROTECTED]> | http://radian.org
> 
> -
> The Cryptography Mailing List
> Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
> 

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]


RE: New result in predicate encryption: disjunction support

2008-05-05 Thread Scott Guthery
[Moderator's Note: Top posting is discouraged. --Perry]


What I meant was that the crypogram decrypted with a correct f(I)=1 key
yields the encrypted message "Meet you at Starbucks at noon 0"
whereas decryption with a wrong, f(I)=0, key yields "Let's go down to Taco
Bell at midnight".  Padding with 0's doesn't help.

Cheers, Scott 

-Original Message-
From: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED] On Behalf Of Jonathan Katz
Sent: Sunday, May 04, 2008 1:20 PM
To: cryptography@metzdowd.com
Subject: RE: New result in predicate encryption: disjunction support

On Sun, 4 May 2008, Scott Guthery wrote:

> One useful application of the Katz/Sahai/Waters work is a counter to 
> traffic analysis.  One can send the same message to everyone but 
> ensure that only a defined subset can read the message by proper key 
> management.  What is less clear is how to ensure that decrytion with 
> the wrong key doesn't yield an understandable (and actionable) message.

This is actually pretty easy to do by, e.g., padding all valid messages with
sufficiently-many 0s. Decryption with an incorrect key will result in
something "random" that is unlikely to end with the requisite number of 0s
(and so will be discarded).
-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]


RE: New result in predicate encryption: disjunction support

2008-05-04 Thread Jonathan Katz

On Sun, 4 May 2008, Scott Guthery wrote:


One useful application of the Katz/Sahai/Waters work is a counter to traffic
analysis.  One can send the same message to everyone but ensure that only a
defined subset can read the message by proper key management.  What is less
clear is how to ensure that decrytion with the wrong key doesn't yield an
understandable (and actionable) message.


This is actually pretty easy to do by, e.g., padding all valid messages 
with sufficiently-many 0s. Decryption with an incorrect key will result in 
something "random" that is unlikely to end with the requisite number of 0s 
(and so will be discarded).


-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]


RE: New result in predicate encryption: disjunction support

2008-05-04 Thread Scott Guthery
A group member asked me to elaborate on:

> - No knowledge of which groups can be successfully authenticated is 
> known to the verifier

What this tries to say is that the verifier doesn't need to have a list of
all authenticable groups nor can the verifier draw any conclusions about
other authenticable groups based on authenticating one group.

One useful application of the Katz/Sahai/Waters work is a counter to traffic
analysis.  One can send the same message to everyone but ensure that only a
defined subset can read the message by proper key management.  What is less
clear is how to ensure that decrytion with the wrong key doesn't yield an
understandable (and actionable) message.

Cheers, Scott

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]


Re: New result in predicate encryption: disjunction support

2008-05-04 Thread Ben Laurie

Scott Guthery wrote:
Those interested in predicate encryption might also enjoy 

Group Authentication Using The Naccache-Stern Public-Key Cryptosystem 


http://arxiv.org/abs/cs/0307059

which takes a different approach and handles negation.

A group authentication protocol authenticates pre-defined groups of
individuals such that: 
- No individual is identified 
- No knowledge of which groups can be successfully authenticated is known to
the verifier 


I don't understand this one, could you say it again with more words?

- No sensitive data is exposed 
The paper presents a group authentication protocol based on splitting the

private keys of the Naccache-Stern public-key cryptosystem in such a way
that the Boolean expression defining the authenticable groups is implicit in
the split

Shamelessly, Scott

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]





--
http://www.apache-ssl.org/ben.html   http://www.links.org/

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]


RE: New result in predicate encryption: disjunction support

2008-05-03 Thread Scott Guthery
Those interested in predicate encryption might also enjoy 

Group Authentication Using The Naccache-Stern Public-Key Cryptosystem 

http://arxiv.org/abs/cs/0307059

which takes a different approach and handles negation.

A group authentication protocol authenticates pre-defined groups of
individuals such that: 
- No individual is identified 
- No knowledge of which groups can be successfully authenticated is known to
the verifier 
- No sensitive data is exposed 
The paper presents a group authentication protocol based on splitting the
private keys of the Naccache-Stern public-key cryptosystem in such a way
that the Boolean expression defining the authenticable groups is implicit in
the split

Shamelessly, Scott

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]


New result in predicate encryption: disjunction support

2008-05-03 Thread Ivan Krstić
This is fairly interesting: AFAIK the first generalization of  
predicate encryption to support disjunctions. I find the result mostly  
interesting mathematically, since I expect we won't be seeing  
predicate encryption in widespread use anytime soon due to complexity  
and regulatory concerns. --IK




"Predicate Encryption Supporting Disjunctions, Polynomial Equations,  
and Inner Products"

Jonathan Katz and Amit Sahai and Brent Waters

Preprint: 

Abstract: Predicate encryption is a new paradigm generalizing, among  
other things, identity-based encryption. In a predicate encryption  
scheme, secret keys correspond to predicates and ciphertexts are  
associated with attributes; the secret key SK_f corresponding to the  
predicate f can be used to decrypt a ciphertext associated with  
attribute I if and only if f(I)=1. Constructions of such schemes are  
currently known for relatively few classes of predicates.
We construct such a scheme for predicates corresponding to the  
evaluation of inner products over N (for some large integer N). This,  
in turn, enables constructions in which predicates correspond to the  
evaluation of disjunctions, polynomials, CNF/DNF formulae, or  
threshold predicates (among others). Besides serving as what we feel  
is a significant step forward in the theory of predicate encryption,  
our results lead to a number of applications that are interesting in  
their own right.


--
Ivan Krstić <[EMAIL PROTECTED]> | http://radian.org

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]