I am just writing down some random ideas came to my mind regarding computer technologies. They may not be well thought-through, but hopefully they can inspire some sparkles.
Digital publishing has been a hot cake. Novels, papers and all sorts of documents are being sold online, but with one pitfall, the danger of being duplicated. One counter measurement is to apply cryptographic methods and only those authorized parties may read it, e.g., PDF enables a two level (owner and user) password protection. But this is apparently not sufficient: one user can simply pass the user password along with the PDF to another. Additional measurements such as online authorization or hardware/OS environment lock-in commonly adopted in various DRM (Digital Rights Management) schemes have to come into play, and which, regarless of their effectiveness, have all done one thing so far in common, i.e., degenerate the legitimate user’s user experience.
Ok then. But can one make the password so valuable that the user will not pass it along with the document?
Something as valuable as the password to one’s principal email account, ebay auction account, or even online banking account. But then, such items are so valuable that one wouldn’t reveal it to the document provider, and even if one does, the document provider has no way to verify whether the password submitted is indeed the same valuable one.
Symmetric encryption isn’t enough.
Ok then, how about the private key of one’s personal digital signature? It is probably something he/she would never want to reveal to others. But then, a document has to be specifically encrypted for each one of its readers using their respective public keys, which sounds impractical if we consider how easy it is to send email to multiple parties, where the message body stays unchanged and everyone just receive the exact same copy.
Ok then, how about using a (symmetric) secret key to encrypt the body for all, and only encrypt the secret key differently for each individual readers? No, it doesn’t work because once the secret key is revealed, there is no more secret as in the original problem.
So my question is, is there a way to encrypt a message once and for multiple parties so that each of them has to use and only use his/her own secret to decrypt it?
To make it more fun, is the following possible?
Mi = D(Si, E(M, P1, . . . Pn)) = W(M, Pi)
where Pi / Si are the pair of public/private keys, D, E, W are the decryption, encryption, and watermark functions. Though Mi and M are different, they convey the same meaning for the purpose of communication. By watermarking, I mean that Mi (or its slightly modified variant) can be verified against Pi so that one can trace a leaked Mi (or its variant) back to Pi.
Many have observed that if one tries to zip an already compressed file, the size will get a bit larger rather than decrease further. So one conclusion is that an already compressed file is very hard to be further compressed, and the extra increment in size is probably due to the overhead of the algorithm used. This leads to a question: is there a best algorithm of taking a piece of data and get it to its smallest form in terms of size?
It depends. Compression is tightly associated to the interpretation of the compressed data, or in other words, the data must be associated with a program that interprets it. So it is more appropriate to talk about self-extracting zip executable rather than the compressed data alone. For example, let’s take the sequence of Pi, 1 billion digits after the decimal point, and compress this sequence using a general tool like Zip. The result will be significantly larger than a computer program that computes Pi to an arbitrary precision. Though the latter isn’t a general purpose compression algorithm, it nevertheless represents a compressed form of the information about a piece of data, which is Pi in this case.
So the question should be changed. Is it possible to represent an arbitrary piece of data at the shortest size as a program of a fixed instruction set that would output the data?
As informed by a friend, this problem is known as Kolmogorov complexity. There exists no best compression for a given string encoded as a program that extracts it.
There exists implicit parallelism in almost every program. Computations with no dependency on each other can be executed concurrently. A good example of a massively parallel system is the electronic circuit on a computer mother board, where millions of Logic gates operate at the same time, and yet collectively they perform meaningful computations.
Let’s consider a system that takes a program source code as input and produces a circuit map of logic gates equivalent to the program in functionality and at the same time exploits implicit parallelism to its best concurrency level. Is such a system possible?
It soon reveals that the parallelism of a program execution depends on the inputs. So perhaps a static analysis on the program source code isn’t going to give the best solution of maximized concurrency. Or perhaps, there exists no best solution?
But after all, exploiting implicit parallelism is a fun topic, especially when asynchronous circuit is considered. I kind of feel that the clocked execution of logic gate was largely due to the ease of formulating computations around the model, but not because it is the best way to do it.
Let’s just imagine, someday somebody comes out with a system proposed above, maybe not an optimum solution, but it tries hard enough so that the efficiency of computation is greatly improved due to increased concurrency. What if one feeds an X86 execution core as a source program to such a system, will the output outperform all Pentium chips by Intel? Will it outperform all humanly possible solutions coming out of conventional chip design??