In cryptography

Cryptography

Cryptography is the practice and study of techniques for secure communication in the presence of third parties...

, an interpolation attack is a type of cryptanalytic attack

Cryptanalysis

Cryptanalysis is the study of methods for obtaining the meaning of encrypted information, without access to the secret information that is normally required to do so. Typically, this involves knowing how the system works and finding a secret key...

 against block cipher

Block cipher

In cryptography, a block cipher is a symmetric key cipher operating on fixed-length groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take a 128-bit block of plaintext as input, and output a corresponding 128-bit block of ciphertext...

s.

In the attack, an algebraic function is used to represent an S-box. This may be a simple quadratic

Quadratic function

A quadratic function, in mathematics, is a polynomial function of the formf=ax^2+bx+c,\quad a \ne 0.The graph of a quadratic function is a parabola whose axis of symmetry is parallel to the y-axis....

, or a polynomial

Polynomial

In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...

 or rational function

Rational function

In mathematics, a rational function is any function which can be written as the ratio of two polynomial functions. Neither the coefficients of the polynomials nor the values taken by the function are necessarily rational.-Definitions:...

 over a Galois field. Its coefficients can be determined by standard Lagrange interpolation techniques, using known plaintexts

Known-plaintext attack

The known-plaintext attack is an attack model for cryptanalysis where the attacker has samples of both the plaintext , and its encrypted version . These can be used to reveal further secret information such as secret keys and code books...

 as data points. Alternatively, chosen plaintexts

Chosen-plaintext attack

A chosen-plaintext attack is an attack model for cryptanalysis which presumes that the attacker has the capability to choose arbitrary plaintexts to be encrypted and obtain the corresponding ciphertexts. The goal of the attack is to gain some further information which reduces the security of the...

 can be used to simplify the equations and optimize the attack.

Thomas Jakobsen

Thomas Jakobsen

Thomas Jakobsen is a mathematician, cryptographer, and computer programmer, formerly anassistant professor at the Technical University of Denmark and head of research anddevelopment at IO Interactive...

 introduced a probabilistic

Randomized algorithm

A randomized algorithm is an algorithm which employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random bits...

 version of the interpolation attack using Madhu Sudan

Madhu Sudan

Madhu Sudan is an Indian computer scientist, professor of computer science at the Massachusetts Institute of Technology and a member of MIT Computer Science and Artificial Intelligence Laboratory.-Career:...

's algorithm for improved decoding of Reed-Solomon codes. This attack can work even when an algebraic relationship between plaintexts and ciphertexts holds for only a fraction of values.