### Re: New result in predicate encryption: disjunction support

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=ContentModaction=itemid=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

[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=ContentModaction=itemid=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: http://eprint.iacr.org/2007/404 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]

### WEP's dead-er: The Final Nail in WEP’s Coff in

IMHO, an interesting read: tapir.cs.ucl.ac.uk/bittau-wep.pdf The Final Nail in WEP’s Coffin Bittau, A. Handley, M. Lackey, J. University College London; This paper appears in: Security and Privacy, 2006 IEEE Symposium on Publication Date: 21-24 May 2006 On page(s): 386- 400 Authors present an attack that allows you to send arbitrary data on a WEP network after having eavesdropped a single data packet!! Next, communicate with every host in the router's LAN. And finally decrypt packets in real-time. Ariel -- Ariel Waissbein CORE SECURITY TECHNOLOGIES http://www.coresecurity.com/corelabs - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

### Re: Solving systems of multivariate polynomials modulo 2^32

Hi Danilo, Maybe you should use some other function in Mathematica. Symbolic solving polynomial equations is a very difficult task (e.g., doubly-exponential worst case time complexity). But in this case it shouldn't take that much time. Let me notice that Z_{2^32} is not the same as F_{2^32} the field of 2^32 elements. I presume that you mean the former, which is not a field! If you mean the latter, then you are using the wrong domain specification in Reduce. If you meant the field of 2^32 elements, then you should check how to specify this in Mathematica. For option Z_{2^32} you could try to solve the system (with elimination) over the rationals, and once you eliminated variables look at everything in the integers (multiplying by the LCM of the denominators) and then simply take modulo 2^32 over all the solutions! If the system of 3 polynomials in 3 variables is generic-enough it should have only finite solutions. If you want to continue using Mathematica, you can try your luck with functions such as Solve or GroebnerBasis. There exist alternatives to Groebner basis which I prefer personally, such as the Kronecker solver (http://www.math.uvsq.fr/~lecerf/software/kronecker/) which comes as a Magma package. I hope this helps. Cheers, Ariel Danilo Gligoroski wrote: Hi, In order to solve a system of 3 polynomials of order 3 with 3 variables x1, x2 and x3 in the set Z_{2^32} and coeficients also in Z_{2^32} I used the Mathematica 5.1 function Reduce[...,{x1,x2,x3},Modulus-2^32]. It is giving the solutions but it is not very fast. I wanted to programe a procedure in C in order to get more speed in the computation. I was trying to figure out what algorithms are used in the Reduce function of Mathematica (reading Wolfram web pages) but I couldn't find any specific information for the algorithms they are using for solving multivariate polynomials modulo 2^32. I found several papers that are dealing with solving univariate or multivariate polynomials in finite fields such as: 1. Lauder : http://www.maths.ox.ac.uk/~lauder/papers/LauderManyVarSept16.pdf 2. van de Woestijne : http://www.math.leidenuniv.nl/~cvdwoest/maths/ober.pdf and http://www.math.leidenuniv.nl/~cvdwoest/maths/issac2005.pdf 3. Barreto and Voloch: http://www.ma.utexas.edu/users/voloch/Preprints/roots.pdf 4. Ding, Gower and Schmidt: http://eprint.iacr.org/2006/038.pdf but the algorithms there are for soving polynomials over finite fields GF(p) or GF(p^n) which is different than just solving polynomials (univariate or multivariate) modulo 2^32. I will appreciate any hint or coment. Regards, Danilo Gligoroski - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] -- Ariel Waissbein RESEARCHER CORE SECURITY TECHNOLOGIES Tel./Fax: (54-11) 5556-2673 Humboldt 1967, 2do piso Capital Federal, Argentina http://www.coresecurity.com/corelabs - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

### Re: [IP] more on Can you be compelled to give a password?

Hi, Please notice that a second distress password becomes useless if the would-be user of this password has access to the binaries (that is, the encrypted data), e.g., because he will copy them before inserting the password and might even try to reverse-engineer the decryption software before typing anything. So I'm not sure what is the setting here. Cheers, Ariel Ed Gerck wrote: List, the Subject says it all. This might be of interest here, for comments. The answer is definitely NO even for the naive user, just requiring the tech-savvy for set up. Several examples are possible. John Smith can set two passwords, one for normal use and the other when in distress. The distress password may simply announce that the data is expired or, more creatively, also make the data unreadable. John Smith can also set two passwords, one of them unknown to him but known to a third-party (that John S does not have to trust) that is subject to a different jurisdiction /or rules /or is in another place. John Smith may comply with any demand to disclose his password but such a demand may not be effective for the third-party. John Smith can have the data, encrypted with a key controlled by his password, sitting on some Internet server somewhere. John S never carries the data and anyone finding the data does not know to whom it belongs to. John Smith can also use keys with short expiration dates in order to circumvent by delay tactics any demand to reveal their passwords, during which time the password expires. Of course, this is not really a safe heaven for criminals because criminal activity is often detected and evidenced by its outside effects, including tracing. Cheers, Ed Gerck - 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: MD5 trick

Hi Vlastimil and group, Gera Richarte has done some interesting work with executable files that have the same MD5 hash. Take a look at http://www.coresecurity.com/corelabs/projects/research_topics.php to see his talk at PacSec `05 and Two executable files with the same MD5 hash, crc32, checksum32 and checksum16. Regards, Ariel vlastimil.klima wrote: The trick could be shortly expressed as follows: Give me three files and I will give you another three with the same MD5 hash -- Ariel Waissbein RESEARCHER CORE SECURITY TECHNOLOGIES http://www.coresecurity.com/corelabs - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

### Re: solving, simplification and factorization of boolean equations

Dear Travis, simplification can be reduced to elimination, which is indeed intractable in the general case (for real-sized problems). (I am assuming that you need to simplify a big system; however if you only want to simplify a small SBox, then brute forcing might do.). The standard citation on itnractability is [E. Mayr and A. Meyer. The complexity of the word problem for commutative semigroups. Adv. in Math., 46:305–329, 1982.] or Philippon et al.'s article. A more comprehensive approach can be found in [D. Castro, M. Giusti, J. Heintz, G. Matera, L.M. Pardo. The hardness of polynomial equation solving. Found. Comput. Math. 3 (2003).]; see also the citations in their Intro). The intractability of elimination is well known at least since Grete Hermann (http://en.wikipedia.org/wiki/Grete_Hermann), and most probably since the end of the 19th century. In my opinion simplification is a means and not an end, and indeed a very intractable mean. On the other hand, form your email I gather that your end is to solve these equations. In polynomial equation solving, special cases are what counts. There is a lot of debate on what are good options for elimination, today there are different approaches presenting families of algorithms that are efficient on certain problem instances. Briefly I would classify the options as: 1-rewriting techniques (ie Groebner bases), 2-path-following techniques (e.g., [L. Blum, F. Cucker, M. Shub, S. Smale, Complexity and Real Computation, Springer, New York Berlin Heidelberg, 1998.], [B. Huber, B. Sturmfels, A polyhedral method for solving sparse polynomial systems, Mathematics of Computation 64 (112) (1995).]), 3-numeric techniques (e.g., [W. Rheinboldt, Methods for solving systems of nonlinear equations, vol. 70 of CBMS-NSF Regional Conf. Series in Appl. Math., SIAM, Philadelphia, 1998.), 4-an algorithms family based on flat deformations (e.g., [M. Giusti, K. Haegele, J. Heintz, J.E. Morais, J.L. Monta~na, L.M. Pardo, Lower bounds for Diophantine approximation, J. Pure Appl. Algebra 117,118 (1997)] and its predecessors; see http://tera.medicis.polytechnique.fr) There are also many ad hoc constructions (e.g., in crypto) that can be used on very specific problems. I think this is all. I might be unwittingly omitting some other option. Im sorry if I am. I can only speak for the latter technique (4), in which I have contributed; in fact, together with other coauthors we will be releasing a paper which attacks the problem of polynomial equation solving as applied to public-key schemes based on polynomial equations. I have not analyzed block ciphers, which yeild higher degree equations (as compared to the quadratic equations of typical public-key schemes). I hope that this helps, and feel free to mail me on any other questions. Best, Ariel Travis H. wrote: Does anyone have any references on how one would go about creating manipulating the boolean equations that govern symmetric ciphers? I know that most of the time ciphers describe an algorithm, often using tables (S-boxes and E-tables) in lieu of providing equations, and I'm wondering how one goes about generating the equations for each bit of the output. One thing I've always been curious about is the minimum amount of work (in terms of a primitive boolean gate such as NAND) necessary to compute the output values. Could there be tables derived from equations so cleverly arranged that brute forcing is very simple once you know the original equations, but their exact structure is not evident from the tables themselves? Once you have some equations, how would you go about simplifying them? I suspect that finding the simplest form is probably NP-hard, but I'm not certain and don't quite know where to start reading on the subject. -- http://www.lightconsulting.com/~travis/ -- We already have enough fast, insecure systems. -- Schneier Ferguson GPG fingerprint: 50A1 15C5 A9DE 23B9 ED98 C93E 38E9 204A 94C2 641B - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] -- I was scared. Petrified. Because (x) hearing voices isn't like catching a cold, you can't get rid of it with lemmon tea (y) it's inside, it is not some naevus, an epidermal blemish you can cover up or cauterise (z) I had no control over it. It was there of its own volition, just stopped in and (zz) I was going bananas. -Tibor Fischer ``The Thought Gang Ariel Waissbein RESEARCHER CORE SECURITY TECHNOLOGIES http://www.coresecurity.com/corelabs - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]

### Re: Cryptography Research wants piracy speed bump on HD DVDs

Is there really that much space for marking? Any substantial number of marked bits will become obvious in the output stream, no? Is the watermarking system robust? Is it public? And how long ago has it been published? If they are only modifying some bits (in the standard representation), then one might probably be able to alter them. Also notice, that this may harm the quality of the image. Intuitively, one is expected to have a low quality of image if lots of bits are used for watermarking, and a low security if a few bits are used for watermarking. Regarding blacklists, where are they stored? If they are included in every new DVD, then one doesn't need to buy a new DVD but simply simulate an ID (which is not in the blacklist) for the DVD. So this opens another place where designers may screw up. Another attack is to attempt to delete this blacklist from the DVD. In another respect, closed p2p communities that exchange movies through secure channels would never get into this revocations lists. So here is another inconvenience for this DRM scheme. Regards and (almost) merry christmas, Ariel - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]