Method and apparatus for cryptographically secure algebraic key establishment protocols based on monoids
AssigneeArithmetica, Inc.
InventorsIRIS ANSHEL, MICHAEL M. ANSHEL, DORIAN GOLDFELD
Life of this patent
Estimating the term…
Abstract
The present invention is a method and apparatus for providing cryptographically secure algebraic key establishment protocols that use monoids and groups possessing certain algorithmic properties. Special fast algorithms associated with certain monoids and groups are used to optimize both key agreement and key transport protocols. The cryptographic security of the algorithms is based on the difficulty of solving the conjugacy problem in groups and other known hard algebraic problems. Braid groups and their associated algorithms are the basis for highly rapid key agreement and key transport protocols which employ modest computational resources.
Claims34
An encryption system comprising:
- a monoid key establishment apparatus responsive to an input monoid, a private element, and a combined input monoid list;
- a combinatorial action unit connected to said monoid key establishment apparatus responsive to an input message and having an encrypted output.
A key agreement system comprising:
- a combinatorial group modulator using a private element to act on a group of elements associated with a remote system to generate a local combination;
- a combinatorial multiplier responsive to a multiplier input and a remotely generated combination wherein said multiplier input is related to said private element;
- and
- a key extractor responsive to said private element and an output of said combinatorial multiplier.
An encryption method comprising the steps of:
- transforming an input monoid, a private element, and a combined input monoid list into a monoid key wherein said transforming is based on the word problem for monoids;
- combinatorially acting on said monoid key and an input message to create an encrypted output.
A method for establishing a key comprising the steps of:
- transforming a private element and a group of elements associated with a remote system into a local combination based on a combinatorial relationship;
- combinatorially multiplying a multiplier input and a remotely generated combination wherein said multiplier input is related to said private element;
- and
- extracting a key from said private element and the result of the step of combinatorially multiplying.
Dependencies are inferred from the claim text.