A better way to publically demonstrate ground-breaking compression algorithms without risking reverse-engineering.
Posted by Sachin Garg on 29th June 2005 | Permanent Link
A comp.compression post by someone called Goldy (Kyle) brings foward an interesting method for publically demonstrating any new compression algorithms without risking reverse engineering.
The previously accepted method used two physically seperate computers with compression done on one, decompression done on other and data tranferred b/w the two using media like floppy/cd. It required the inventor and evaluator to be present in same physical room, the computers to be provided by evaluator (to rule out previous tampering) and then be destroyed or given to inventor (to rule out possibility of reverse engineering).
New method is much more efficient and can work online, and is thus better suited for public demonstration.
Here it is…
Step 1) Allow the public to download a “decompressor” program. The decompressor should not make any network connections of any kind.
Step 2) Allow the public to upload a file to a server to be compressed.
Step 3) The server compresses the file and generates a compressed file on server which can be downloaded and given to decompressor program. (All submitted files for testing can be made accessible to the public on this web page, so everyone can see what everyone else has submitted to be tested, and check it themselves, but this part is not necessary)
Step 4) Run the decompressor program on the downloaded compressed file get the output file. Preferrably on a different computer which has no traces of original file.
Step 5) Transfer both files (Original and the one generated by decompressor) on same computer and compare the two files with DIFF or something similar to see if they match.
As the compressor never leaves the hands of original inventor, he can relax that it cant be reverse engineered
Although this method was presented in context of randam data compressors (uh!) it can ofcourse be used for evaluating or demonstrating any research breakthrough in data-compression.
Update: As many compression algorithms can be reverse engineered (atleast to a large extent) even if only decompressor is available, this method is restricted to only those cases where inventor feels that he can safely release the decompressor.
June 29th, 2005 at 11:40 am
“As the compressor never leaves the hands of original inventor, he can relax that it cant be reverse engineered.” I disagree — some methods, like LZ78, *can* be deduced by looking at the decompressor, since the decompressor build the dictionary as it goes.
June 30th, 2005 at 12:55 am
I am sorry to deeply disagree also with the statement regarding that this method does not allow reversing engineering. In lossless compression, once that you have managed to know the decompression algorithm, have an input data (the compressed file) and and output data (the original file) it is very hard to imagine a compression algorithm that could not be reconstructed, at least to an engineering level where you can get the main ideas behind and generate your own compressor.
Lossless compression, at least for the efficient algorithms, can mostly be seen as a highly sophisticated state machine, where you jump from state to state according to the input data, generating at the same time the shortest output possible. Reversely, the decompression algorithm have to replicate the same state machine, but now travelling in the other way around.
June 30th, 2005 at 8:59 am
Hmmm… I agree that in many cases algorithm can be reverse engineered from the decompressor, at least to a large extent.
As you might have noticed from the comp.compression thread, the method was posted by the inventor, so it was assumed that the inventor was willing to give away the decompressor.
Thus, I never gave too much thought on inventor’s perspective. But as a perspective evaluator, I was satisfied by the method.
I have made some changes to the text in news item, please point out any other shortcomings in it.
If you feel that I should remove this news item, I will.
July 14th, 2005 at 4:31 am
Please keep this post.
I did the original post on comp.compression.
I never mentioned anything about reverse engineering the decompressor, as that was not the question being asked.
Yes, you could very easly reverse engineer a decompressor, but would you still want to if you got the compressor for free? ;)