Monthly Archives: January 2012

Watermarking molecules

This post was chosen as an Editor's Selection for ResearchBlogging.orgI’ve posted twice about Anonymous hacking into Stratfor — and, more generally, their hacktivism has been making bigger and bigger waves.  CNN recently ran a fairly positive story on the support hacktivists are providing the Occupy movement.  Many of these hacktivists are quite active on Twitter and elsewhere.  However, from the perspective of both international and corporate espionage, the “quiet” hacks are the worst: someone makes off with information and the victim never knows.  As security expert Kevin Mandia told the New York Times:

The hacks that do the most damage don’t have Twitter feeds.

Another security expert, Jeremy Falkenrath, in an interview on Bloomberg News (at about 7:00 into the video), discussed, quite matter-of-factly, the hacker-for-hire market that companies in the chemical industry deploy against one another to learn trade secrets.  With this as the backdrop, I’d like to discuss one of the main open questions of cheminformatics: Is secure encryption of molecules possible?  For example, it would be nice if a company could encrypt a molecule, but then allow some third party to run in silico tests with it, having access to the molecule’s properties but not the structure itself.

Encryption of molecules

Part of the reason for the traditional closed-data policies of pharmaceutical companies is the total absence of any way to encrypt chemical structural information.  This has been recognized as an open problem for many years, the American Chemical Society held a special meeting in 2005 about it, a summary of which appeared in Nature.  While there were presenters at that meeting who felt molecular encryption was possible, and others who felt it was impossible, the practical reality as we enter 2012 is that, so far, the voices in favor of “impossible” have been correct.  Almost no new theoretical literature has been produced since 2005, and the industry appears no nearer a practical solution than it was in, say, 1975.

I recently had an idea to expand upon a proposal by Eggers et al. in 2001, to watermark in silico representations of molecules.  My idea, however, is going nowhere — just like all other attempts so far to implement chemical watermarking.  At least I can get a blog entry out of my failure though!  I hope readers of this page find my little attempt entertaining or informative.

Acknowledgement: The material in this post is based on conversations I have had with cheminformaticians Rajarshi Guha and Jörg Kurt Wegner.

Continue reading


Ian Stewart’s Mathematics of Life

This post is based on a book review I recently wrote on The Mathematics of Life, by Ian Stewart. A final version of the review will appear in a future issue of SIGACT News.  Please feel free to download a pdf version of the full preprint, or just read an abbreviated version of it here, in blog format.


Ian Stewart is one of the premier popularizers of mathematics.  He has written over twenty books about math for lay audiences.  He has also co-authored science fiction, and books on the science of science fiction (three books on “the science of discworld”).  In his newest effort, The Mathematics of Life, Stewart focuses his talents on the mathematics of biology, and the result is superb.  In an easy, flowing read, with dozens of diagrams and scholarly footnotes — but without a single formula — he introduces the reader to a wide range of interactions between mathematicians and biologists.  I heartily recommend this book.
Continue reading

My own information was just compromised in the Zappos hack

In an unfortunate coincidence, as a thematic followup to my previous post on hacking, a “throwaway” email I use, and partial credit card information of mine, has just been compromised in the recent hack of  Infosec Island has a good blog post about this data breach,  and I was one of 24 million Zappos customers who received the email quoted in that blog post.

I’ve deleted my credit card information from Zappos, and from one other online retailer I use.  To be honest, I’m not sure who else might have my sensitive information — and I bet I’m not alone in that.  I’m not sure what precautions I will take in the future when shopping online, but I plan never to save my credit card information again.

Stay safe, everyone.

Password analysis from the Stratfor hack

I will return to blogging about theoretical computer science and algorithm-related mathematics next week, but I wanted to take a few minutes today to mention a rare research opportunity that has arisen as a result of the hack of the private global intelligence company Stratfor.  This opportunity is the list of 860,000 (MD5 hashed) passwords to accounts of people in journalism, government contracting, the military, etc. — in short, people who “should” know how to create and maintain strong passwords.  Most of the MD5 hashes have now been cracked, and preliminary analysis indicates that even people who “know what they are doing” use weak passwords.

Stratfor, by the way, finally has their website back online, with a Hacking News section, in which they tell their side of the story.  (They verify that they stored credit card information in cleartext, as Anonymous had claimed, and they state that they were working with the FBI on an investigation into a hack of their systems before the hack went public on Christmas Eve.)  About a week ago, the hackers released a zine which includes a press release about the Stratfor hack and two others, and a log of the hacks themselves.

Continue reading

Polygon rectangulation wrap up

Tying up loose ends from my three posts in December about rectangulation of orthogonal polygons.

  1. Derrick Stolee requested in a comment a resolution of the computational complexity of the 3D version of the problem of decomposing a shape into the minimum number of rectangles.  I found a reference that proves the problem is NP-complete, by directly reducing the problem to a variant of 3SAT.  The diagrams of the gadgets used are pretty cool — the gadgets look like children’s toys used to build 3D structures.  Rectangular partition is polynomial in two dimensions but NP-complete in three, by Victor J. Dielissen and Anne Kaldewaij, Information Processing Letters, April 1991.
  2. The survey Polygon Decomposition by J. Mark Keil (1996) has much more information on exact algorithms for rectangulation, triangulation, and problems I did not mention at all, like covering.
  3. There is an extensive literature on approximation algorithms for finding a minimum-length rectangulation of an orthogonal polygon with holes.  (The problem is NP-complete even for the case where the polygon is a rectangle and its interior holes are points.)  I can recommend the survey Minimum Edge-Length Rectangular Partitions, by Gonzalez and Zheng (in Handbook of Approximation Algorithms and Metaheuristics, 2007).

Victor J. Dielissen, & Anne Kaldewaij (1991). Rectangular partition is polynomial in two dimensions but NP-complete in three Information Processing Letters, 38 (1), 1-6 : 10.1016/0020-0190(91)90207-X