[tahoe-dev] GSoC : 100 Year Cryptography

[Lalit Bharat]

Hello Everyone,

In this mail I would like to discuss the possible digital signature
algorithms to be used in the 100 year cryptography project.

With the invention of Quantum computers(15-20 years approx.), we shall have
to worry about only Public Key Crypto System and not much for hash functions
or the symmetric Key Systems. As the later two(hash & symmetric Systems)
being perfectly secure systems are not based on some hard problem.

In normal cryptosystems(e.g. based on prime factorisation-RSA), solving a
cryptosystem generally boils down to the fact of solving an 'average' case
hard problem(i.e. if the adversary wins then this implies he has solved the
'average' case hard problem in polynomial time). But in case of lattice
based  crypto systems, this means solving the 'worst' case hard problem.
Hence making it further more secure. Also in the operations in lattice
cryptography are quite faster as compared to those systems used publicly.
Hence, in these systems we may increase the size of the security parameter
without much increase in the computational cost.

Now, even before the invention of practical quantum computers there are
algorithms for quantum computers(quantum computers don't work on the
principles of the normal Turing Machine) to solve the factorisation problem
and discrete log problem(DLP) in polynomial time as showed by Shor in the
paper - "Polynomial-Time Algorithms for Prime Factorization and Discrete
Logarithms on a Quantum Computer"(http://arxiv.org/abs/quant-ph/9508027v2)
Hence, today's crypto systems would not be able to withstand the quantum
computers. As of today, there is no quantum algorithm to solve Lattice based
hard problems.

Lattice based signature algorithms already exist. One of them is the
NTRUSign(Digital Signatures Using the NTRU Lattice @
http://securityinnovation.com/cryptolab/pdf/NTRUSign_RSA.pdf).

So, I would suggest in adding a Lattice based algorithm to the Signature
algorithm.

Lastly I would like to point out to the following fact, which might increase
the security of a signature scheme in general(nothing realted to Tahoe)
In long term data storage systems if storage is not a concern (while signing
some data) then I propose that a the hash function should be removed while
using digital signatures as in case there is a flaw in the hash function
then it will not make the Digital Signature vulnerable. Thus, in this case
the signature will be equivalent to the size of the message.

Further, Nils Durner, asked me to add some of my previous inter country
experiences, in this mail, as cultural differences matter while working.
I have not worked outside India physically, but I was accepted for an
internship with a professor in Canada(but couldn't go due to VISA issues).
But I interacted with the professor regularly, then.
I also have an online Russian friend and we get well together.
As such India in itself is quite varied and have been to every corner of
India.
Further, I have done an internship at Oracle Financial Services Software
from where I have some experience of the corporate world. At this internship
I was appointed to scan for various vulnerabilities in the intranet
applications.
I have done internship in Cryptography(theoretical, basically), and worked
on Proxy Digital signatures. Hence I have an in depth knowledge on Public
Key Crpypto Systems, in general.

Thank You

-- 
Lalit Bharat
IT BHU
Varanasi
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://allmydata.org/pipermail/tahoe-dev/attachments/20100420/e975131f/attachment.htm