Ye Yuan
0%

The Basic of Cryptography

Posted on Edited on

The Basic of Cryptography

Shannon ciphers and perfect security

Definition of a Shannon cipher

The basic mechanism for encrypting a message using a shared secret key is called a cipher (or encryption scheme). In this section, we introduce a slightly simplified notion of a cipher, which we call a Shannon cipher.

A Shannon cipher is a pair of functions.

  • The function (the encryption function) takes as input a key and a message (also called a plaintext), and produces as output a ciphertext . That is,

and we say that is the encryption of under .

  • The function (the decryption function) takes as input a key and a ciphertext , and produces a message . That is,

and we say that is the decryption of under .

  • We require that decryption "undoes" encryption; that is, the cipher must satisfy the following correctness property: for all keys and all messages , we have

To be slightly more formal, let us assume that is the set of all keys (the key space), $ is the set of all messages (the message space), and that is the set of all ciphertexts (the ciphertext space). With this notation, we can write:

Also, we shall say that is defined over .

Perfect security

The mathematical notion of perfect security.

Definition (perfect security). Let be a Shannon cipher defined over . Consider a probabilistic experiment in which the random variable is uniformly distributed over . If for all , and all , we have

then we say that is a perfectly secure Shannon cipher.

Theorem. Let be a Shannon cipher defined over . The following are equivalent:

  • is perfectly secure.
  • For every , there exists an integer (possibly depending on ) such that for all , we have

  • If the random variable is uniformly distributed over , then each of the random variables , for , has the same distribution.

Another expaination of perfect security (or information-theoretic secure): means that the cipertext conveys no information about the content of the plaintext.[2]

  • In effect this means that, no matter how much ciphertext you have, it does not convey anything about what the plaintext and key were.
  • When used correctly, the One Time Pad (OTP) is information-theoretic secure, which means it cannot be broken with cryptanalysis.

The bad news

keys must be at least as long as messages. As a result, it is almost impossible to use perfectly secure ciphers in practice.

Therem (Shannon's theorem). Let be a Shannon cipher defined over . If is perfectly secure, then .

Computational ciphers and semantic security

The only way around Shannon’s theorem is to relax our security requirements. The way we shall do this is to consider not all possible adversaries, but only computationally feasible adversaries, that is, “real world” adversaries that must perform their calculations on real computers using a reasonable amount of time and memory. This will lead to a weaker definition of security called semantic security.

Definition of a computational cipher

A computational cipher is a pair of efficient algorithms, and . The encryption function is allowed to be a probabilistic algorithm, such as: .

Definition of semantic security

For all predicates on the ciphertext space, and all message , we have

where is a random variable uniformly distributed over the key space . Instead of insisting that these probabilities are equal, we shall only require that they are very close; that is,

for some very small, or negligible, value of .

To precisely formulte the definition of semantic security, we shall describe an attack game played between two parties, a challenger and an adversary. In general, the challenger follows a very simple, fixed protocol. However, an adversary may follow an arbitrary (but still efficient) protocol.

Attack Game (semantic security). For a given cipher , defined over , and for a given adversary , we define two experiments, Experiment and Experiment . For , we define

Experiment b:

  • The adversary computes , of the same length, and sends them to the challenger.
  • The challenger computes , and sends to the adversary.
  • The adversary outputs a bit .

For , let be the event that outputs in Experiment . We define 's semantic security advantage with respect to as

Definition (semantic security). A cipher is semantically secure if for all efficient adversaries , the value is negligible.

Connections to weaker notions of security

The probability of random guessing for an adversary is probability .

Attack Game (message recovery). For a given cipher , defined over , and for a given adversary , the attack game proceeds as follows:

  • The challenger computes , and sends to the adversary.
  • The adversary outputs a message .

Let be the event that . We say that wins the game in this case, and we define 's message recovery advantage with respect to as

Definition (security against message recovery). A cipher is secure against message recovery if for all efficient adversaries , the value is negligible.

Theorem. Let be a cipher defined over . If is semantically secure then is secure against message recovery.

Mathematical details

Negligible, super-poly, and poly-bounded functions

Intuitively, a negligible function is one that not only tends to zero as , but does so faster than the inverse of any polynomial.

Definition of negligible: A function is called negligible if for all there exists such that for all integers , we have .

Theorem: A function is negligible if and only if for all , we have

Definition of super-poly: A function is called super-poly if is negligible.

Definition of poly-bounded: A function is called poly-bounded, if there exists such that for all integers , we have .

Computational ciphers: the formalities

In mathematical model, we associate with families of key, message, and ciphertext spaces, indexed by

  • a security parameter, which is a positive integer, and is denoted by , and
  • a system parameter, which is a bit string, and is denoted by .

Steam ciphers

Pseudo-random generators

The one-time pad, keys, messages and ciphertexts are all -bit strings. We want to instead use a short, -bit "seed" as the encryption key. The string is stretched using algorithm that maps -bit string s to -bit strings. Thus, the key space for this modified one-time pad is , while the message and ciphertext spaces are . For and , encryption and decryption are defined as follows:

This modified one-time pad is called a stream cipher, and the function is called a pseudo-random generator.

Definition of a pseudo-random generator

  • A pseudo-random generator, or PRG for short, is an efficient, deterministic algorithm that, given as input a seed , computes an output .
  • The seed comes from a finite seed space and the output belongs to a finite output space .
  • Typically, and are sets of bit strings of some prescribed length.
  • We say that is a PRG defined over .

Protocols

Identification (ID) protocols. The identification problem involves two parties, a prover and a verifier.

  • The prover has a secret key that it uses to convince the verifier of its identity.
  • The verifier has a corresponding verification key that it uses to confirm the prover's claim.

Interactive protocols: definitions

Definition: An identification protocol is a triple .

  • is a probabilistic, key generation algorithm, that takes no input, and outputs a pair , where is called the verification key and is called the secret key.
  • is an interactive protocol algorithm called the prover, which takes as input a secret key , as output by .
  • an interactive protocal algorithm called the verifier, which takes as input a verfication key , as output by , and which outputs or .

Protocals[3] : A cryptographic protocol is a complete description of everything that is needed in order to implement a cryptographic procedure.

  • The term is not entirely precise, but it generally refers to the way in which one or more cryptogrpahic algorithms are to be implemented and coordinated with one another.

Formal Definition of Turing Machine [4]

Following Hopcroft & Ullman (1979, p.148), a (one-tape) Turing machine can be formally defined as a -tuple where

  • is a finite, non-empty set of ;
  • is the (the only symbol allowed to occur on the tape infinitely often at any step during the computation);
  • is the set of , that is, the set of symbols allowed to appear in the initial tape contents;
  • is a finite, non-empty set of ;
  • is the ;
  • is the set of or . The initial tape contents is said to be accepted by if it eventually halts in a state from .
  • is a partial function called , where is left shift, is right shift. If is not defined on the current state and the current tape symbol, then the machine halts; intuitively, the transition function specifies the next state transited from the current state, which symbol to overwrite the current symbol pointed by the head, and the next head movement.

Abstract Machine

In computer science, an abstract machine is a theoretical model that allows for a detailed and precise analysis of how a computer system functions. It is similar to a mathematical function in that it receives inputs and produces outputs based on predefined rules.

Black Box

In science, computing, and engineering, a black box is a system which can be viewed in terms of its inputs and outputs, without any knowledge of its internal workings. Its implementation is "opaque" (black). The term can be used to refer to many inner workings, such as those of a transistor, an engine, an algorithm, the human brain, or an institution or government.

Oracle Machine

In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to solve certain problems in a single operation.

Random Oracle

In cryptography, a random oracle is an oracle (a theoretical black box) that responds to every unique with a (truly) random response chosen uniformly from its output domain. If a query is repeated, it responds the same way every time that query is submitted.

Stated differently, a random oracle is a mathematical function chosen uniformly at random, that is, a function mapping each possible query to a (fixed) random response from its output domain.

References

[1] A Graduate Course in Applied Cryptography, Version 0.6, Dan Boneh and Victor Shoup.

[2] https://crypto.stackexchange.com/questions/3896/simply-put-what-does-perfect-secrecy-mean

[3] An Introduction to Mathematical Cryptography, Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. Springer, 2008.

[4] https://en.wikipedia.org/wiki/Turing_machine#Formal_definition