Authenticated ID-based cryptosystem with no key escrow

A system for encoding and decoding a digital message communicated between a first entity and a second entity, wherein the first entity and the second entity both know a non-interactive shared secret, comprising:

• a first memory associated with the first entity, the first memory operable to store at least a first random secret that independent of the non-interactive shared secret and is not known to the second entity, a system parameter that is independent of the non-interactive shared secret, a first intermediate shared secret component, a second intermediate shared secret component, an interactive shared secret, and a symmetric key;
• a second memory associated with the second entity, the second memory operable to store at least a second random secret that is independent of the non-interactive shared secret and not known to the first entity, the system parameter, the first intermediate shared secret component, the second intermediate shared secret component, the interactive shared secret, and the symmetric key;
• a first processor associated with the first entity, the first processor operable to select the first random secret, to determine the first intermediate shared secret component using the first random secret and the system parameter, such that the first intermediate shared secret component is independent of the non-interactive shared secret to communicate the first intermediate shared secret component to the second entity, to receive the second intermediate shared secret component from the second entity, to determine the interactive shared secret using the first random secret and the second intermediate shared secret component, to determine the symmetric key using the interactive shared secret and the non-interactive shared secret, to encode the message using the symmetric key, and to communicate the encoded message to the second entity;
• and
• a second processor associated with the second entity, the second processor operable to select the second random secret, to determine the second intermediate shared secret component using the second random secret and the system parameter, to communicate the second intermediate shared secret component to the first entity, to receive the first intermediate shared secret component from the first entity, to determine the interactive shared secret using the second random secret and the first intermediate shared secret component, such that the first intermediate shared secret component is independent of the non-interactive shared secret to determine the symmetric key using the interactive shared secret and the non-interactive shared secret, to receive the encoded message from the first entity;
• and to decode the encoded message using the symmetric key.