Microsoft Technology Licensing, LLC

Peter L Montgomery

Kristin E Lauter

Ramarathnam R Venkatesan

Anne Kirsten Eisentraeger

David Jao

Victor V Boyko

John R Douceur

Edmund Bernard Nightingale

Ismail Cem Paya

Niels Thomas Ferguson

Jeremy Eric Elson

Dan Boneh

Stuart Schechter

Michael Naehrig

Adam Back

Daniel Bakalars Shumow

S Ramesh Raju

David Y Jao

A Metadata server described herein is configured to generate a metadata table optimized for data durability and recovery. In generating the metadata table, the metadata server associates each possible combination of servers with one of the indices of the table, thereby ensuring that each server participates in recovery in the event of a server failure. In addition, the metadata server may also associate one or more additional servers with each index to provide added data durability. Upon generating the metadata table, the metadata server provides the metadata table to clients or servers. Alternatively, the metadata server may provide rules and parameters to clients to enable those clients to identify servers storing data items. The clients may use these parameters and an index as inputs to the rules to determine the identities of servers storing or designated to store data items corresponding to the index.

Data layout for recovery and durability

A method described herein includes acts of executing a cryptographic function over input data utilizing a processor on a computing device and generating a data packet that indicates how the cryptographic function interacts with hardware of the computing device, wherein the hardware of the computing device comprises the processor. The method also includes acts of analyzing the data packet, and generating an indication of security of the cryptographic function with respect to at least one side channel attack based at least in part upon the analyzing of the data packet.

Side channel attack analysis

One or more techniques and/or systems are disclosed that provide for determining mathematical pairings for a curve for use in cryptography. A plurality of inversions used for determining the mathematical pairings for the curve are aggregated (e.g., into a single inversion in respective levels of a binary tree representation of elements of the computation). The mathematical pairings for the curve are determined in affine coordinates from a binary representation of a scalar read from right to left using the aggregated plurality of inversions.

Determination of pairings on a curve using aggregated inversions

Executable instructions designed to provide faster cryptographic processing, fixed-timing memory access, and dedicated memory usage are implementable on an x86 CPU utilizing XMM registers. The instructions can be utilized to implement cryptographic processing in accordance with the Advanced Encryption Standard (AES). To encrypt, a single instruction performs nonlinear transformation, rotation, and linear transformation. Another single instruction used during encryption performs nonlinear transformation and rotation. New instructions also are implemented to perform decryption. The instructions implemented to perform decryption perform the mathematical inverse functions of their counterparts used for encryption.

Cryptographic processing

Methods and apparati are provided for use in cryptographically processing information based on elliptic and other like curves. The methods and apparati allow pairings, such as, for example, Weil pairings, Tate Pairings, Squared Weil pairings, Squared Tate pairings, and/or other like pairings to be determined based on algorithms that utilize a parabola. The methods and apparati represent an improvement over conventional algorithms since they tend to me more computationally efficient.

Weil and Tate pairing techniques using parabolas

A technology generally related to large-scale computations employed in the fields of cryptography and data security system employing a new and improved variant of the Karatsuba multiplication approach. The variant of the Karatsuba multiplication approach being utilized to minimize the number of coefficient multiplications needed to multiple two polynomials of degree four.

Five-term karatsuba-variant calculator

A cryptosystem has a secret based on an order of a group of points on a Jacobian of a curve. In certain embodiments, the cryptosystem is used to generate a product identifier corresponding to a particular product. The product identifier is generated by initially receiving a value associated with a copy (or copies) of a product. The received value is padded using a recognizable pattern, and the padded value is converted to a number represented by a particular number of bits. The number is then converted to an element of the Jacobian of the curve, and the element is then raised to a particular power. The result of raising the element to the particular power is then compressed and output as the product identifier. Subsequently, the encryption process can be reversed and the decrypted value used to indicate validity and/or authenticity of the product identifier.

Cryptosystem based on a Jacobian of a curve

Methods and apparati are provided for use in determining 'Squared Weil pairings' and/or 'Squared Tate Pairing' based on an elliptic curve, for example, and which are then used to support cryptographic processing of selected information. Significant improvements are provided in computing efficiency over the conventional implementation of the Weil and Tate pairings. The resulting Squared Weil and/or Tate pairings can be substituted for conventional Weil or Tate pairings in a variety of applications.

Squared Weil and Tate pairing techniques for use with elliptic curves

Techniques are described that facilitate cryptographic operations, such as data encryption, signing and others, encryption using a computerized method for multiplying a scalar by a point. In one implementation, a set of random integers is selected, wherein the set comprises at least one integer selected randomly. A string is configured, based in part on the set of random integers. Output in the form of a product of the scalar and the point is then calculated, based on the string.

Randomized sparse formats for efficient and secure computation on elliptic curves

Techniques are described for generating and validating signatures. In an implementation, a method includes generating a signature by utilizing a plurality of isogenies included on a private key and incorporating the signature and a public key on a product, in which the public key is configured to validate the signature.

Systems and methods for generation and validation of isogeny-based signatures

In at least one implementation, described herein, P and Q, . . . , Qare public points on an elliptic curve over a finite field, but the ratios of Qto P are private. Those ratios are the components (&#x3b1;, . . . , &#x3b1;) of a private key, where Q=&#x3b1;P. This implementation generates short digital ciphers (i.e., signatures), at least in part, by mapping a message M to a point T on the elliptic curve and then scaling that point T based upon the private key &#x3b1; to get S. At least one other implementation, described herein, verifies those ciphers by comparing pairing values of two pairs, where one pair is the public point P and the scaled point S and another pair is public Q and the point T. This implementation tests whether log(Q)/log(P)=log(S)/log(T), without computing any elliptic curve discrete logarithm directly.

Cryptographic pairing-based short signature generation and verification

Systems and methods for providing signatures are described. In an implementation, a system includes a backend configured to generate a plurality of incomplete signatures using an offline portion of an online/offline signature algorithm, storage configured to store the plurality of incomplete signatures and a front end configured to process a plurality of messages using the plurality of incomplete signatures to form a plurality of digital signatures such that each of the messages has a corresponding one of the digital signatures.

Systems and methods for providing signatures

An architecture and methodology for implementing Montgomery multiplication on a computer system that supports SIMD instructions is described.

Utilizing SIMD instructions within montgomery multiplication

An implementation of a digital signature technique, described herein, generates, and another implementation of a digital signature technique, also described herein, validates, a hidden plaintext or ciphertext message wherein one or more portions of that message have another ciphertext message implicitly embedded therein. In other implementations, two or more portions of that message have another ciphertext message implicitly embedded therein. This abstract itself is not intended to limit the scope of this patent. The scope of the present invention is pointed out in the appending claims.

Generation and validation of short digital signatures with implicit message embedding

A cryptosystem based on a Jacobian of a hyperelliptic curve is being used. Various methods and apparati are provided for generating a compressed data format that identifies one or more points&#x2014;on the Jacobian of the hyperelliptic curve, and for subsequently decompressing the compressed format data.

Growing community of inventors

Bellevue, WA, United States of America

Peter L Montgomery