Provably secure cryptosystem

[Ondrej Mikle]

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 majordomo at metzdowd.com