Ajtai Lattice Patent

[John Young <jya@pipeline.com>]

30 April 1998, Micropatent:

Cryptosystem employing worst-case difficult-to solve lattice 
problem (Assignee -- International Business Machines 
Corporation)

Abstract: A cryptosystem and cryptographic method are 
provided for performing tasks such as encoding/decoding, 
signing messages, and verifying identity. The system and 
method employ a problem which is difficult to solve in the 
worst case. Because of the worst-case nature of the 
problem employed, a system and method according to the 
invention has advantageous level of security, In a class of 
preferred embodiments, the difficult problem is one of the 
recognized difficult problems associated with the mathematical 
theory of lattices. These problems include finding short 
vectors and sets of basis vectors from a lattice. Cryptographic 
protocols are performed, using these problems. 

Ex Claim Text: A cryptographic communications system A 
comprising: a communications channel; means for generating 
a public key and a corresponding private key based on an 
instance of a problem, the problem being difficult to solve in 
the worst case, the instance of the problem  being difficult to 
solve, commensurate with the difficulty of the  worst-case 
solution of the problem; and means for performing a 
cryptographic communication protocol, employing the public 
and private keys generated by the means for generating, with 
another cryptographic communications system B over the 
communications channel. 

Patent Number: 5737425 

Issue Date: 1998 04 07 

Inventor(s): Ajtai, Miklos

If you would like to purchase a copy of this patent, please call 
MicroPatent at 800-648-6787.