International Business Machines Corporation

Don Coppersmith

Stephen Michael Matyas, Jr

Shai Halevi

Charanjit Singh Jutla

Nevenko Zunic

David R Safford

Rosario Gennaro

Mohammed Peyravian

Chai Wah Wu

Charles Philippe Tresser

Donald B Johnson

Luke James O'Connor

Phillip W Rogaway

Frederick Cole Mintzer

Richard Henry Guski

Minerva Ming-Yee Yeung

Claude Alexander Greengard

Raymond Craig Larson

Thomas Guthrie Zimmerman

Stephen M Matyas

Prabhakar Raghavan

Gary E Strait

John Cocke

Carl H Meyer

Adrian Eric Seigler

Se June Hong

Jonathan R Hosking

Samuel Monk Weber

Jonathan Oseas

Bruce P Kitchens

Bruno O Brachtl

Michael Schilling

Richard Fairbanks Arnold

Myrna M Hyden

Shaiy Pilpel

A computer system and method generates a random output stream of bits. The system comprises an initial evolving state produced from one or more initial keys, one or more round functions, and one or more mask tables. Each round function is part of a step in a sequence of steps. Each step applies the respective round function to a current evolving state to produce a respective new evolving state for processing by the next step in the sequence. The first step in the sequence starts b processing the initial evolving state. The mask tables are produced from one or more of the initial keys. Each of the mask tables has one or more masks. The masks are combined, in each respective step, with the respective new evolving state in a combination operation to create a respective step output. The random output stream bits is a concatenation of each of the respective step outputs. In one preferred embodiment, one or more of the masks in the mask tables are replaced by one or more replacement masks after a number of combination operations. The replacement masks not being linear combinations of prior masks. In an alternative embodiment, there are two or more mask tables produced from one or more of the initial keys. One or more of the masks from each table is combined, in each respective step, with the respective new evolving state in a combination operation to create a respective step output. There may or may not be replacement of the masks in this embodiment.

Efficient stream cipher system and method

A watermarking scheme is provided that allows the watermarked image to be authenticated by an authentication agent without revealing the human-readable content of the image. There is disclosed an approach that combines privacy control with watermarking and authentication mechanisms. The watermark can be made to be imperceptible to humans. Public key cryptography allows the authentication agent to authenticate without being able to watermark an image. Watermark information may also be encoded in a vector graphics image that includes at least one stroke defined by coordinate values of an ordered sequence of points. This may be obtained by providing watermark information as a bit sequence, identifying one or more redundant properties of the image, modifying the redundant properties based upon the bit sequence to generate a representation of the image and storing the representation of the image for subsequent use.

Secured signal modification and verification with privacy control

In order to verify the authenticity of manufactured goods, a smart tag is attached to the goods containing encrypted authentication information, such as a serial number, a description of the good's physical appearance or chemical decomposition, its color, or digital images of the good etc. The encryption procedure comprises public/private key encryption with zero-knowledge protocols. Zero knowledge protocols allow a smart tag to be authenticatable and yet be duplication resistant by allowing the verifying agent to convince him/herself that the smart tag is authentic without revealing its authentication information. The verification procedure can be done using a reader at a point of sale (POS) machine equipped with the appropriate public key and zero-knowledge protocols to decrypt the authentication information. A printed version of the serial number or other authentication information may be placed on the goods in human readable form to quickly verify the information electronically read from the smart tag. With the present invention, only the manufacturer can create such smart tags with the associated data thus making it virtually impossible to pass off a counterfeit good as authentic. In addition to authenticating counterfeit goods, the present invention can be used to detect authentic goods being sold in a parallel market.

System for protection of goods against counterfeiting

A method and apparatus for cryptographically transforming an input block into an output block. The input block has a first block size and is partitionable into a plurality of input subblocks having a second block size that is a submultiple of the first block size. To encrypt or decrypt, the input subblocks are passed through respective first substitution functions controlled by one or more keys to generate a first plurality of modified subblocks. The first plurality of modified subblocks are then passed through a mixing function to generate a second plurality of modified subblocks, each of which depends on each of the first plurality of modified subblocks. Finally, the second plurality of modified subblocks are passed through respective second substitution functions controlled by one or more keys to generate a plurality of output subblocks that are combinable into an output block.

Method and apparatus for cryptographically transforming an input block into an output block

A watermarking scheme which allows the watermarked image to be authenticated by an authentication agent without revealing the human-readable content of the image. There is disclosed an approach which combines privacy control with watermarking and authentication mechanisms. The watermark can be made to be imperceptible to humans. Public key cryptography allows the authentication agent to authenticate without being able to watermark an image.

A method and apparatus for an advanced symmetric key cipher for encryption and decryption, using a block cipher algorithm. Different block sizes and key sizes are supported, and a different sub-key is used in each round. Encryption is computed using a variable number of rounds of mixing, permutation, and key-dependent substitution. Decryption uses a variable number of rounds of key-dependent inverse substitution, inverse permutation and inverse mixing. The variable length sub-keys are data-independent, and can be precomputed.

Method and apparatus for advanced symmetric key block cipher with variable length key and block

A method and apparatus for an advanced byte-oriented symmetric key cipher for encryption and decryption, using a block cipher algorithm. Different block sizes and key sizes are supported, and a different sub-key is used in each round. Encryption is computed using a variable number of rounds of mixing, permutation, and key-dependent substitution. Decryption uses a variable number of rounds of key-dependent inverse substitution, inverse permutation, and inverse mixing. The variable length sub-keys are data-independent, and can be precomputed.

Method and apparatus for advanced byte-oriented symmetric key block cipher with variable length key and block

The present invention provides a technique, system, and computer program for a symmetric key block cipher. This cipher uses multiple stages with a modified Type-3 Feistel network, and a modified Unbalanced Type-1 Feistel network in an expansion box forward function. The cipher allows the block size, key size, number of rounds of expansion, and number of stages of ciphering to vary. The modified Type-3 cipher modifies the word used as input to the expansion box in certain rounds, to speed the diffusion properties of the ciphering. The modified Type-3 and Type-1 ciphers are interleaved, and provide excellent resistance to both linear and differential attacks. The variable-length subkeys and the S-box can be precomputed. A minimal amount of computer storage is required to implement this cipher, which can be implemented equally well in hardware or software (or some combination thereof).

Symmetric block cipher using multiple stages with modified type-1 and type-3 feistel networks

The present invention provides a technique, system, and computer program for a symmetric key block cipher. Variable block sizes and key sizes are supported, as well as a variable number of rounds. The cipher uses multiple stages of processing, where the stages have different structures and different subround functions, to provide excellent resistance to both linear and differential attacks. Feistel Type-3 networks are used, with different networks during different stages. The number of rounds may vary among stages. Subkeys are used in some, but not all, stages. The variable-length keys can be precomputed. A novel manner of using multiplication in a cipher is defined.

Method and apparatus for a symmetric block cipher using multiple stages

The present invention provides a technique, system, and computer program for a symmetric key block cipher. Variable block sizes and key sizes are supported, as well as a variable number of rounds. The cipher uses multiple stages of processing, where the stages have different structures and different subround functions, to provide excellent resistance to both linear and differential attacks. Feistel Type-1 and Type-3 are both used, each during different stages. The number of rounds may vary among stages. Subkeys are used in some, but not all, stages. The variable-length keys can be precomputed. A novel manner of using data-dependent rotation in a cipher is defined.

Method and apparatus for a symmetric block cipher using multiple stages with type-1 and type-3 feistel networks

A fast way for determining the best subset test for a nominal attribute in a decision tree. When a nominal attribute has n distinct values, the prior art requires computing the impurity functions on each of the 2.sup.n-1 -1 possible subset partitioning of the n values and finding the minimum case among them. This invention guarantees the minimum impurity test on the attribute by computing only (n-1) impurity function computations. This reduction of computational complexity makes it practically possible to find the true best tests for many real data mining application, where a binary decision tree is used as the classification model.

Method for finding a best test for a nominal attribute for generating a

A visible seal or label containing a serial number is placed in plain view on the product packaging. The visible label contains the serial number as well as a first public key encrypted version of the serial number. A second or hidden label inside of the package has thereon a second a second encrypted version of the serial number made using a second public key. The hidden label may be secured inside of the package out of sight or may be placed on the back of the visible label and therefore viewable through a transparent case when opened or visible when peeled off. The private keys are known only to the manufacturer. Using a corresponding public key provided by the manufacturer, the consumer, law enforcement agent, or customs inspector can verify that the encrypted version matches the serial number. An advantage to this method is that only the manufacturer can produce matching pairs. Moreover, using a point of sale machine equipped with the public key the sales clerk can authenticate the product in front of the consumer at point of purchase. Additionally, in the case of a CD or other digital medium, the hidden label may comprise a digital watermark of the encrypted serial number such that a consumer, law enforcement agency, or customs inspector can readily detect a counterfeit product.

A software-efficient pseudorandom function maps an index and an encryption key to a pseudorandom bit string useful for constructing a stream cipher. The method begins by preprocessing the encryption key into a table of pseudorandom values. The index and a set of values from the table is then used to generate a set of initial values for the registers. At least some of the register values are modified in part by taking a current value of a register and replacing the current value with a function of the current value and a value retrieved from the table, the latter value being determined by the values in one or more other registers. After modifying the register values in this fashion, the values are masked using other values from the table and the results then concatenated into the pseudorandom bit string. The modification step is repeated and a new masked function of the register values is then concatenated into the pseudorandom bit string. The modification and concatenation steps are repeated to continue growing the pseudorandom bit string until the string reaches some desired length.

Software-efficient pseudorandom function and the use thereof for

An apparatus and method are disclosed for encoding and transferring data from a transmitter to a receiver, using the human body as a transmission medium. The transmitter includes an electric field generator, a data encoder which operates by modulating the electric field, and electrodes to couple the electric field through the human body. The receiver includes electrodes, in physical contact with, or close proximity to, a part of the human body, for detecting an electric field carried through the body, and a demodulator for extracting the data from the modulated electric field. An authenticator, connected to the receiver, processes the encoded data and validates the authenticity of the transmission. The apparatus and method are used to identify and authorize a possessor of the transmitter. The possessor then has secure access to, and can obtain delivery of, goods and services such as the distribution of money, phone privileges, building access, and commodities. Encryption provides rapid transmission and authentication of the transmitter, and a plurality of similar transmitters, with minimum vulnerability to counterfeit. Signal processing and digital communication components accommodate variations in location and orientation of the transmitter and receiver, and provide transmitters with long life times and high reliability.

System and method for near-field human-body coupling for encrypted

A system for cryptographically transforming a sequence of input blocks of plaintext or ciphertext data into corresponding sequence of output blocks of data while providing enhanced protection against cryptographic attacks. Each input block is enciphered using a first key to generate a first encryption product, which is combined with a first secret masking value generated independently of the input blocks to generate a masked first encryption product. Each masked first encryption product is then enciphered using a second key to generate a second encryption product, which is combined with a second secret masking value generated independently of the input blocks to generate a masked second encryption product. Finally, each masked second encryption result is enciphered using a third key to generate an output block corresponding to the input block.

Growing community of inventors

Ossining, NY, United States of America

Don Coppersmith