Ntt Docomo, Inc.

Microsoft Technology Licensing, LLC

Alice Silverberg

Craig B Gentry

Mark Steven Manasse

Chandramohan Amyangot Thekkath

High throughput in data computations and processing is maintained while minimizing latency. A binary tree architecture is provided in which two trees are used simultaneously, and initiation of the trees is staggered to allow for optimal use of bandwidth. These techniques are desirable for erasure codes and other computations where the addition operator is commutative. Additionally, a ternary tree architecture may be used, in which three trees co-exist on the same set of nodes to maintain high throughput while further improving latency.

Erasure coding and group computations using rooted binary and ternary trees

A signature {Sig, {Q}} is generated on a message M by a signer Ein a hierarchical system including the entities E, E, . . . , E, each entity E(i&#x3e;0) being a child of E. Here where: each Sis a secret key of E; each sis a secret of S; Pis a public function of M; each Pis a public function of the ID's of all entities Esuch that 1&#x2266;j&#x2266;i; each Q=sPwhere Pis public. The verifier confirms that where: the product &#x3a0;&#xea;(Q,P) is taken over all integers i in a proper subset of the integers from 1 to t inclusive; &#xea; is a bilinear non-degenerate mapping; V can be &#xea;(Q,P) where iis predefined (e.g. 1), or V can be another expression is a verifier is part of the hierarchical system.

Hierarchical identity-based encryption and signature schemes

Nodal pattern configuration is described, including generating successive values at a source node, processing the successive values using a plurality of intermediate nodes, sending the processed values from a node in the plurality of intermediate nodes to a destination node, and configuring the plurality of intermediate nodes such that each node of the plurality of intermediate nodes, concurrently performs at least two actions. Also, nodal pattern configuration includes generating a series of data blocks at a source node, processing data blocks from the series of data blocks using a plurality of intermediate nodes in data communication with the source node, each node of the plurality of intermediate nodes being configured to concurrently perform at least two operations, and sending processed data blocks from the plurality of intermediate nodes to a destination node, the destination node being in data communication with the plurality of intermediate nodes.

Nodal pattern configuration

Methods are provided for encoding and decoding a digital message between a sender and a recipient in a system including a plurality of private key generators ('PKGs'). The PKGs include at least a root PKG and n lower-level PKG in the hierarchy between the root PKG and the recipient. A root key generation secret is selected and is known only to the root PKG. A root key generation parameter is generated based on the root key generation secret. A lower-level key generation secret is selected for each of the n lower-level PKGs, wherein each lower-level key generation secret is known only to its associated lower-level PKG. A lower-level key generation parameter also is generated for each of the n lower-level PKGs using at least the lower-level key generation secret for its associated lower-level private key generator. The message is encoded to form a ciphertext using at least the root key generation parameter and recipient identity information associated with the recipient. A recipient private key is generated such that the recipient private key is related to at least the root key generation secret, one or more of the n lower-level key generation secrets, and the recipient identity information. The ciphertext is decoded to recover the message using at least the recipient private key.

A method and system are provided for determining a shared secret between two entities in a cryptosystem. A first random secret is selected that is known to the first entity and unknown to the second entity. A first intermediate shared secret component is determined using the first random secret and a system parameter. The first intermediate shared secret component is communicated to the second entity. A second random secret is selected that is known to the second entity, but unknown to the first entity. A second intermediate shared secret component is determined using the second random secret and the system parameter. The second intermediate shared secret component is communicated to the first entity. It is confirmed that both the first entity and the second entity know a non-interactive shared secret. An interactive shared secret is determined using the first random secret, the second random secret, and the system parameter.

Growing community of inventors

Columbus, OH, United States of America

Alice Silverberg