International Business Machines Corporation

Other

Miklos Ajtai

Randal Chilton Burns

Ronald Fagin

Larry Joseph Stockmeyer

A public key cryptosystem utilizes a hard lattice with O(n log n) random bits for security. The system comprises a public-key cryptosystem whose hardness assumption is a clearly stated mathematical problem with a long history and comprises a short key, reaching a balance between the favorable properties of the hardness assumption and the key size. This balance has not been achieved by previously known public-key cryptosystems. The improved efficiency of the present system is achieved by reducing the size of the public key from O(nlog n) to O(n log n). The improved security of the system is achieved by reducing the security to the hardness of a clearly stated computational problem, the dipohantine approximation problem of Dirichlet.

Public key cryptosystem and associated method utilizing a hard lattice with O(n log n) random bits for security

A method and a system are presented for generating differentially compressed output from binary sources. Given two versions of the same file as input streams, a compact encoding of one of the input streams is generated, by representing it as a set of changes with respect to the other input stream. Algorithms for differencing files requiring time linear in the size of the input and a constant amount of space for execution are presented. In addition, advanced techniques for improving existing differencing algorithms are developed and applied to previous methods. These techniques allow algorithms to increase their efficiency without a loss of compression and to accept arbitrarily large inputs without sacrificing correctness or degrading the compression data rate. The differential compression methods provide a computationally efficient compression technique for applications that generate versioned data.

System and method for differential compression of data from a plurality of binary sources

A compact mechanical toy is provided. The toy is a multi-sided game including multiple sides and a plurality of moveable pieces. The toy includes a first part including one side having a cavity shaped to fit any one of the plurality moveable pieces at one time. The toy further includes a second part rotatably coupled to the first part, the second part including a complex cavity in each of the multiple sides, the complex cavity shaped to fit each of the plurality of moveable pieces in a certain order. The object of the game is to move each of the plurality of pieces from a first side in the second part to a second side in the second part.

Towers of hanoi game

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.

Growing community of inventors

Los Gatos, CA, United States of America

Miklos Ajtai