Security First Corporation

Other

University of California

Phillip Rogaway

Mihir M Bellare

Rick L Orsini

Mark S O'Hare

Till Stegers

Benjamin J Morris

A secure data parser is provided that may be integrated into any suitable system for securely storing and communicating data. The secure data parser parses data and then splits the data into multiple portions that are stored or communicated distinctly. Encryption of the original data, the portions of data, or both may be employed for additional security. The secure data parser may be used to protect data in motion by splitting original data into portions of data, that may be communicated using multiple communications paths. A keyed information dispersal algorithm (keyed IDA) may also be used. The key for the keyed IDA may additionally be protected by an external workgroup key, resulting in a multi-factor secret sharing scheme.

Systems and methods for securing data using multi-factor or keyed dispersal

A robust computational secret sharing scheme that provides for the efficient distribution and subsequent recovery of a private data is disclosed. A cryptographic key may be randomly generated and then shared using a secret sharing algorithm to generate a collection of key shares. The private data may be encrypted using the key, resulting in a ciphertext. The ciphertext may then be broken into ciphertext fragments using an Information Dispersal Algorithm. Each key share and a corresponding ciphertext. Fragment are provided as input to a committal method of a probabilistic commitment scheme, resulting in a committal value and a decommittal value. The share for the robust computational secret sharing scheme may be obtained by combining the key share, the ciphertext fragment, the decommittal value, and the vector of committal values.

Systems and methods for distributing and securing data

A robust computational secret sharing scheme that provides for the efficient distribution and subsequent recovery of a private data is disclosed. A cryptographic key may be randomly generated and then shared using a secret sharing algorithm to generate a collection of key shares. The private data may be encrypted using the key, resulting in a ciphertext. The ciphertext may then be broken into ciphertext fragments using an Information Dispersal Algorithm. Each key share and a corresponding ciphertext fragment are provided as input to a committal method of a probabilistic commitment scheme, resulting in a committal value and a decommittal value. The share for the robust computational secret sharing scheme may be obtained by combining the key share, the ciphertext fragment, the decommittal value, and the vector of committal values.

Conventional block ciphers that traffic in 128-bit block sizes are ill-suited for operating in small domains like credit card numbers. Some embodiments relate to techniques for constructing and speeding up practical and provably secure schemes for deterministically enciphering data from a small domain like credit card numbers using a conventional block cipher or other pseudorandom function.

Method and system for accelerating the deterministic enciphering of data in a small domain

A shared-key encryption scheme that uses identically keyed block-cipher calls, low additional overhead, supports the encryption of arbitrary-length strings, produces a minimal-length-ciphertext, and is fully parallelizable. In one embodiment, 'OCB', a key shared between communicating parties is mapped to a key variant using the block cipher. The key variant is mapped into a sequence of basis offsets using shifts and conditional xors. To encrypt a message using a nonce, a nonce-dependent base offset is formed, and then a sequence of offsets is constructed by starting with the base offset and then xoring, for each offset, an appropriate basis offset. The message is partitioned into message blocks of the same length as the block length of the block cipher, along with a message fragment that may be shorter. Each message block is combined with a corresponding offset, enciphered, and then combined again with the offset, yielding a ciphertext block. The message fragment is xored with an appropriately computed pad to give a ciphertext fragment. A checksum is formed using the message blocks, the message fragment, and the pad. The checksum is combined with an offset and enciphered to yield a tag. The encrypted message includes the ciphertext blocks, the ciphertext fragment, and the tag.

Method and apparatus for facilitating efficient authenticated encryption

A block-cipher based encryption scheme providing both privacy and authenticity that encrypts an arbitrary-length message into a minimal-length ciphertext. In one embodiment, 'OCB', a message is encrypted using a nonce by partitioning it into 128-bit message blocks and a possibly shorter message fragment. A sequence of offsets is computed from the nonce and block cipher using shifts and conditional xors. Each message block is xored with an offset, enciphered, and xored with the offset, yielding a ciphertext block. The length of the message fragment is encoded, xored with an offset, enciphered to give a pad, truncated, and xored with the message fragment to give a ciphertext fragment. A checksum is formed by xoring the message blocks, the padded ciphertext fragment, and the pad. It is xored with an offset and enciphered to yield a tag. The ciphertext is the ciphertext blocks, the ciphertext fragment, and the tag.

An RSA-based signing scheme that combines essentially optimal efficiency with attractive security properties. One preferred signing routine requires one RSA decryption plus some hashing, verifications requires one RSA encryption plus some hashing, and the size of the signature preferably is the size of the modulus. Given an ideal underlying hash function, the scheme is not only provably secure, but has security tightly related to the security of RSA. An alternative embodiment maintains all of the above features and, in addition, provides message recovery. The techniques can be extended to provide schemes for Rabin-based signatures or signatures using other trapdoor functions.

Growing community of inventors

Davis, CA, United States of America

Phillip Rogaway