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]
