Strict Standards: Declaration of APCBagOStuff::delete() should be compatible with BagOStuff::delete($key, $time = 0) in /usr/share/mediawiki1.7/includes/BagOStuff.php on line 499
Basic Primitives - Wiki

Basic Primitives

From Wiki

Jump to: navigation, search

ONE-WAY FUNCTION: one-way function

Definition: A function f from a domain to a codomain is said to be one-way if it is easy to compute forwards, but given an element in the codomain it is hard to find a preimage; i.e. an element in the domain which maps to the given element in the codomain.

Use in cryptography: A one-way function can be thought of as a basic hash construction, or a form of encryption (which may not be decryptable). Thus one-way functions are used in constructing almost all the different types of crytographic schemes.

TRAPDOOR ONE-WAY FUNCTION: trapdoor one-way function

Definition: A function f is said to be a trapdoor one way function if on its own it is a one way function. But there is some secret piece of information, called the trapdoor, which enables an entity to efficiently invert the function on any element in the codomain.

Use in cryptography: Trapdoor one-way functions are used to construct public key encryption schemes. The function being the public key, and the trapdoor being the secret key.

(TRAPDOOR) ONE-WAY PERMUTATION: (trapdoor) one-way permutation

Definition: A permutation p on a set X is a bijective function from X to itself. A (trapdoor) one-way permutation is a permutation that is also a (trapdoor) one-way function.

Use in cryptography: A trapdoor one-way permutation is an abstraction of encryption. The permutation property ensures that decryption is possible with the trapdoor (key).

PSEUDO-RANDOM FUNCTION: pseudo-random function

Definition: A random function from a domain X to a codomain Y is a function sampled uniformly at random from the space F(X,Y) of all functions from X to Y. (This sampling is well-defined if both X and Y are finite, in which case | F(X,Y) | = | Y | | X | ). A random function has the property that whenever it is called on a fresh input, the output is uniformly random in Y and independent of previous input/output pairs. This can be used to efficiently simulate random functions.

A pesudo-random function or PRF is a function that is computationally indistinguishable from a random function, that is no efficient adversary can win a distinguishing game between the PRF and a true random function. (No single, fixed function can be a PRF but one can imagine a (keyed) collection of functions such that a random and hidden choice of key yields a PRF.)

Use in cryptography: PRFs are used as building blocks in abstractions of various constructions, for example block ciphers (e.g. a Feistel Network) or a hash function.

A PRF whose domain is larger than its codomain is sometimes known as a compression function (not to be confused with the notion of compressing files, or "zipping"), especially in the context of hash functions; a PRF whose domain is smaller than its codomain is sometimes known as a pseudorandom generator.

PSEUDO-RANDOM GENERATOR: pseudo-random generator

Definition: A pseudo-random generator or PRG is a pseudo-random function whose codomain is larger than its domain. Usually, the domain is taken as X = {0,1}n and the codomain as Y = {0,1}m for some values of n,m where n < m.

Use in cryptography: A PRG is an abstraction of a cryptographically strong random number generator. Starting from a short and secret seed, it can generate an arbitrarily long secret keystream that can be used, for example, in a stream cipher.

PSEUDO-RANDOM PERMUTATION: pseudo-random permutation

Definition: A pseudo-random permutation or PRP is a pseudo-random function that is also a permutation.

Use in cryptography: A PRP is an abstraction of a block cipher (for example DES or AES), being a permutation it can be inverted i.e. one can decrypt.

CLAW FREE PERMUTATIONs: claw free permutations

Definition: A family of set of permutations S_{\mathcal{I}}=\{S_i\}_{i \in \mathcal{I}} for a set of indexes \mathcal{I} (where S_i = \{f_0,\ldots,f_{r-1} \} is a set of permutations having the same domain), is a family of sets of claw free permutations if the following conditions are satisfied:

  • Efficient Generator: there exists an efficient algorithm that randomly picks a set Si with parameter r, from the family S_{ \mathcal{I} }.
  • Efficient Sampling: there exists an efficient sampling algorithm that on input i outputs a random instance of the domain of f_0  \in S_i
  • Efficient Evaluation: there exists an efficient evaluating algorithm that on input i,x, for all f_j \in S_i with j=0,\ldots,r-1, computes fj(x) where x is the output of the sampling algorithm.
  • Claw Free: it is hard for any efficient algorithm to find a "claw", i.e. two values x1,x2 of the domain such that fk(x1) = fj(x2) for all k\neq j with k,j \in \{0,\ldots,r-1\}, for i,Si sampled by the generator algorithm and f_k,f_j\in S_i.

Use in cryptography: Claw free permutations imply CRHFs [DO87].


  • [DO87] I. Damgard: Collision Free Hash Functions and Public Key Signature Schemes. In Proc. of EUROCRYPT, pages 203-216, 1987.

RANDOM ORACLE: random oracle

Defintion: A random oracle (RO) is a random function from the domain X = {0,1} * of all bitstrings into a codomain Y of fixed size.

Use in cryptography: A random oracle is an abstraction of a hash function (e.g. MD5, SHA). Random oracles are mainly used to transform interactive zero-knowledge protocols into non-interactive ones using the so-called Fiat-Shamir transformation.

CRHFs: collision resistant hash functions

Definition: A family of functions H_{\mathcal{I}}=\{h_i:\{0,1\}^* \rightarrow \{0,1\}^n\}_{i \in \mathcal{I}} for a set of indexes \mathcal{I}, is a family of collision resistant hash functions (CRHFs) if the following conditions are satisfied:

  • Efficient Generator: there exists an efficient algorithm that randomly picks a function hi from the family H_{\mathcal{I}} .
  • Compression: the domain of the hash function is always larger than 2n, i.e the size of the co-domain.
  • Efficient Evaluation: there exists an efficient evaluating algorithm that on input i,x computes hi(x).
  • Collision resistance: it is hard for any efficient algorithm to find two values of the domain x1,x2 such that x_1\neq x_2 and hi(x1) = hi(x2), for a randomly chosen i \in \mathcal{I}.

Algorithms: In practice, an implementation of CRHFs is SHA1. Although so far no collision has been found, several attacks reduced its security. SHA-2 and SHA-3 have been proposed as more secure alternatives.

Use in cryptography: CRHFs are widely used as a preprocessing step in many cryptographic primitives, i.e. typically a message is first hashed, then the cryptographic operation is applied on the hash of the original message. Due to the collision resistance property the shrinking of the message's size does not degrade the security of the cryptographic operation itself. Digital signatures are an example: the "hash-and-sign" paradigm requires the signature to be computed on the hash of the message instead of the message itself. Another important application is verification of files integrity. One can detect changes that have been made to a file by comparing the hash computed before, and after, the transmission of it to another entity (or before storing the file in a remote database and after the file have been retrieved). Both applications rely on the fact that finding a collision is infeasible, indeed if one can efficiently find a collision for two messages, than one can have two different messages with the same signature (breaking the unforgeability of the signature scheme) , or two distinct files having the same hash (compromising the security of the user of the database). write my essay References:

  • I. Damgard: Collision Free Hash Functions and Public Key Signature Schemes. In Proc. of EUROCRYPT, pages 203-216, 1987.

MPC: secure multi-party computation

Definition: Consider a function \mathcal{F}(\{0,1\}^*)^n\rightarrow (\{0,1\}^*)^n. Consider n parties P_1,\ldots,P_n with secret inputs respectively x_1,\ldots,x_n. The goal of each party Pi is to evaluate the function on the inputs x_1,\ldots,x_n receiving the i-th output without revealing its own input to the other parties. A multi-party protocol executed by P_1,\ldots,P_n securely implements a functionality \mathcal{F} if the following conditions hold:

  1. Completeness: if all parties P_1,\ldots,P_n honestly follow the protocol then they obtain as output the correct computation of \mathcal{F} on x_1,\ldots,x_n.
  2. Input/Output Privacy: any party behaving dishonestly in the protocol does not gain any information about the private inputs/outputs of the other parties (except the information that can be inferred by the output of the protocol and the own private input).

In the following we define what is a dishonest behavior and how to prove that a protocol securely implements a functionality \mathcal{F}.

Dishonest Behavior/Security notions: The dishonest behavior of the parties models the possible real-world attacks from adversarial machines. According to how much power is given to the adversary (corrupting honest machines, controlling schedule of/mauling the messages over the network, controlling the activation of the protocols) different security notions are defined. In the following we classify the dishonest behavior and therefore the security notions starting from the weakest one (that considers a very restricted real-world adversary) to the strongest one (that gives to the adversary full control over the network and the machines executing the protocol).

  • Honest-But-Curious Adversary: The dishonest party must follow the protocol but can arbitrarily analyze the protocol transcript off-line in order to infer some additional information.
  • Malicious Adversary: The dishonest party can arbitrarily deviate from the protocol and corrupt (i.e. obtain the entire state).
    • Adaptive/Static Corruption: Adaptive adversaries are allowed to decide the parties to corrupt during the protocol execution therefore depending upon the transcript and the state of the parties corrupted so far. Static adversaries instead corrupt the parties before the protocol execution starts.
    • Parallel/Concurrent Composability: One can require that the security of the protocol holds even when a dishonest party executes several instances of the same protocol (resp. different protocols) concurrently or in parallel. In this case we say that the protocol securely realizes a functionality under parallel/concurrent (resp. general concurrent) composition.
  • Computationally Bounded/Unbounded Adversary: According to the computational capability of the real-world adversary each notion of security shown above is denoted as computational or unconditional. The computational setting assumes that the running time of the dishonest party is bounded by a polynomial. Unconditional setting puts no restriction on the running time of the adversary, i.e. it can be exponential.

Proving that a protocol satisfies a security notion - Ideal world/Real World paradigm: Input/Output Privacy is formally proved using the ideal/real world paradigm. Consider an ideal world in which there exists a trusted third party (TTP) who computes the functionality \mathcal{F}. In this world parties do not communicate with each other but they send their inputs to the TTP and receive the output of \mathcal{F}. Since the TTP is trusted in this world the privacy of the parties' inputs is guaranteed by definition. In order to prove Input/Output privacy it is required to show that whatever a dishonest party (the dishonest behavior depends of the security notion that one wants to prove) can infer about the inputs/outputs of the honest parties by exploiting the protocol execution in the real world, it can be inferred also by an adversary (called simulator) playing in the ideal world and interacting only with the TTP.

Use in cryptography: secure two-party computation is the abstraction of many fundamental cryptographic primitives as commitment, zero knowledge, secret sharing, oblivious transfer used to implement any functionality.


  • O. Goldreich, S. Micali, and A. Wigderson. 1987. How to play ANY mental game. In Proceedings of the nineteenth annual ACM symposium on Theory of computing (STOC '87), Alfred V. Aho (Ed.). ACM, New York, NY, USA, 218-229.
  • M. Ben-Or, S. Goldwasser, and A. Wigderson. 1988. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In Proceedings of the twentieth annual ACM symposium on Theory of computing (STOC '88). ACM, New York, NY, USA, 1-10.
  • A. Chi-Chih Yao: Protocols for Secure Computations (Extended Abstract) FOCS 1982: 160-164.

OT: oblivious transfer

Definition: oblivious transfer (OT) is a two-party functionality in which one party, called Sender, hands two strings s0,s1 an the other party, called Receiver, hands a secret bit b \in \{0,1\}. The functionality allows the transfer of the string sb to the Receiver while the Sender gets no output. A two party protocol (Sender, Receiver) implements the OT functionality if the following conditions are satisfied:

  1. Completeness: if Sender and Receiver honestly follow the protocol then the Receiver correctly obtains sb.
  2. Sender Privacy: any dishonest Receiver gets only sb and no information about s1 − b.
  3. Receiver Privacy: any dishonest Sender is oblivious on the string that has been transferred.

The dishonest behavior of the adversary (Sender or Receiver) follows the definition provided in the multi-party computation primitive.

Algorithms: An efficient implementation based on the DDH Assumption can be found in [NP01].

Use in cryptography: OT functionality is complete for secure multi-party computation.


  • M. Rabin. How to Exchange Secrets by Oblivious Transfer. Tech. Memo TR-81, Aiken Computation Laboratory, Harvard University, 1981.
  • [NP01] M. Naor and B. Pinkas. Efficient oblivious transfer protocols. In Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms (SODA) 2001.
  • [EGL85] S. Even, O. Goldreich, A. Lempel. A Randomized Protocol for Signing Contracts. Commun. ACM (CACM) 1985.

COM: commitment scheme

Definition: A commitment scheme is a two-party (Committer, Receiver) two-stage (commitment phase, decommitment phase) protocol that enables the Committer to bind himself to a value while keeping the value hidden to the Receiver. The value is revealed in the decommitment phase. More in details, in the commitment phase the Committer interacts with the Receiver to commit to a secret message m. The output of this phase is a transcript. In the decommitment phase, the Committer reveals m providing all the information that allow the Receiver to check that the value is consistent with the transcript obtained in the commitment phase. Finally the Receiver outputs either the opened value m or \perp. A two-party protocol (Committer, Receiver) is a commitment scheme if the following conditions hold:

  1. Completeness: for all messages m, if Committer and Receiver are honest then at the end of the decommitment phase Receiver always outputs the message committed in the commitment phase by the Committer.
  2. Hiding: for all dishonest Receiver, for all pair of messages m0,m1 chosen by Receiver, given a transcript of the commitment phase for one of message mb, for a randomly chosen b \in \{0,1\}, Receiver cannot tell if the transcript hides m0 or m1 with probability better than 1 / 2.
  3. Binding: for all dishonest Committer, after the commitment phase, there is only one value that can be accepted by Receiver in the decommitment phase.

A commitment scheme is non-interactive if the commitment and the decommitment phases consist of only one message from Committer to Receiver. A commitment scheme is statistically hiding (resp. binding) if the hiding (resp. binding) holds even against an unbounded Receiver (resp. Committer).

Algorithms: Non-Interactive Statistically Binding Commitments on any One-Way Permutation are shown in [GL89]. A 2-Round Statistically Binding Commitment Scheme

ZK: zero knowledge

Definition: A zero knowledge protocol for an NP language L is a two-party protocol played by a Prover P and a Verifier V having as common input a string x (P has as secret input a witness w s.t. the NP relation \mathcal{R}_L(x,w) is satisfied) in which P wants to convince V that x \in L such that the following conditions hold:

  1. Soundness. If x \notin L then any P should not be able to convince V that x is indeed in L.
  2. Zero Knowledge. If x \in L then after the protocol execution any V should not have more information about x than the information it had before the protocol execution, except the fact that x is actually in L. In other words, V does not learn anything new interacting with the prover that she could not have computed by herself. This concept is modeled by requiring that for any dishonest verifier there exists an efficient machine called simulator, that on input only x and without the witness is able to produce a protocol transcript that is indistinguishable with the transcript obtained by V interacting with P.

When the soundness holds even for unbounded dishonest provers we say that the protocol is a zero-knowledge proof system. If soundness holds only for bounded dishonest provers that the protocol is a zero-knowledge argument system. Finally a protocol is computational/statistical/perfect zero knowledge, if the transcript produced by the simulator is computationally/statistically/perfectly indistinguishable from the transcript that a malicious Verifier obtains interacting with the Prover.

Use in cryptography: zero knowledge protocols are building blocks of many two/multi-party protocols.


  • S Goldwasser, S Micali, and C Rackoff. 1985. The knowledge complexity of interactive proof-systems. In Proceedings of the seventeenth annual ACM symposium on Theory of computing (STOC '85).

Personal tools