Hello.

`I humbly say that I *might* have devised a provably secure cryptosystem`

`that actually *might* work in reality. It provides secure authentication`

`and possibly might be extended to something else. Sounds too good to be`

`true? Well, you're right. In reality it's a bit more complicated.`

`I'm risking again making fool of myself, but what the heck ;-) At least`

`I think it's something you all know, at least to some extent.`

`I have searched for some other provably secure schemas for`

`MACs/signatures/etc., they use many similar assumptions (e.g. random`

`oracle assumption, strong one-way hash function with uniform`

`distribution assumption) and some similar techniques.`

`In the system I can prove there *is* a random oracle (this is also not`

`so entirely true, but...you'll see).`

OK, the point:

`In complexity theory with random oracle, NP != P (cf. Shoup 1997: Lower`

`Bounds for Discrete Logarithms and related problems, Baker-Gill-Solovay`

`1975). The trick is based on this fact.`

`Keys in the cryptosystem are not *data*, but *programs*, i.e.`

`(partially) recursive functions. The trick is to simulate random oracle`

`by a program, each program is the key describing a random permutation on`

`some subset of natural numbers.`

`The cryptosystem is based on the following observation (extension of`

`halting problem):`

`Given a program L as an input that takes 1..n as input, L stops exactly`

`for one 1<=j <=n.`

`If we give this program to a DTM (deterministic Turing machine), no`

`finite algorithm can decide for all possible input programs L and`

`numbers n, for which j the input program L will stop in polynomial time.`

`In another words, no finite program can detect every virus (virus is`

`defined to be a self-replicating program) or check if other program will`

`draw prescribed picture for a given input, etc. in polynomial time.`

`So, the paper can be found here (alpha-draft, by no means complete, some`

`parts such as related work and references, acks are not complete):`

-- http://urtax.ms.mff.cuni.cz/~abyssal/PS.pdf --

`Be warned, it may be at least *partially* false, because I`

`*deliberately* left out one proof ("protecting the keyspace", though`

`it's security by obscurity). Well, hopefully there are no more serious`

`glitches ;-]`

`The system as whole is secure, but every single instance can be of`

`course broken by man (stealing the key, guessing the key,`

`cryptanalysis). Integer factorization problem, (generalized) discrete`

`logarithm problem are also elements of the system (it is a set).`

At least I hope you'll have some fun. OM --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]