text:
# Mathematical Foundations of Modern Cryptography: Computational Complexity Perspective

## 1. Introduction

The mathematics of cryptography is driven by real world applications. The original and most basic application is the wish to communicate privately in the presence of an eavesdropper who is listening in. With the rise of computers as means of communication, abundant other application arise, ranging from verifying authenticity of data and access priveleges to enabling complex financial transactions over the internet involving several parties each with its own confidential information.

As a rule, in theoretical fields inspired by applications, there is always a subtle (and sometimes not so subtle) tension between those who do “theory” and those who “practice”. At times, the practitioner shruggs of the search for a provably good method, saying that in practice his method works and will perform much better when put to the test than anything for which a theorem could be proved. The theory of Cryptography is unusual in this respect. Without theorems that provably guarantee the security of a system, it is in a sense worthless, as there is no observable outcome of using a security system other than the guarantee that no one will be able to crack it.

In computational complexity based cryptography one takes feasible (or easy) to mean those computations that terminate in polynomial time and infeasible (or hard) those computations that do not111 We remark however that all security definitions (although not necessarily all security proofs) still make sense for a different meaning of ‘easy’ and ‘hard’. For example, one may take easy to mean linear time whereas hard to mean quadratic time. ). Achieving many tasks of cryptography relies on a gap between feasible algorithms used by the legitimate user versus the infeasibility faced by the adversary. On close examination then, it becomes apparent that a necessary condition for many modern cryptographic goals is that $`NPP`$ 222This is the celebrated unresolved NP vs. P problem posed by Karp, Cook and Levin in the early seventies. NP corresponds to those problems for which given a solution its correctness be verified in polynomial time whereas P corresponds to those problems for which a solution can be found in polynomial time., although it is not known to be a sufficient condition. A (likely) stronger necessary condition which is also sufficient for many tasks is the existence of one-way functions: those functions which are easy to compute but hard to invert with non-negligible probability of success taken over a polynomial time samplable distribution of inputs.

In 1976 when Diffie and Hellman came out with their paper “New Direction in Cryptography”  announcing that we are “on the brink of a revolution in cryptoghraphy” hopes were high that the resolution of the celebrate $`P`$ vs. $`NP`$ problem was close at hand and with it techniques to lower bound the number of steps required to break cryptosystems. That did not turn out to be the case. As of today, no non-linear lower bounds are known for any $`NP`$ complete problem333 NP-complete problems are the hardest problems for $`NP`$. Namely, if an NP complete problem can be solved in polynomial time and thus be in P, then all problems in NP are in P..

Instead, we follow a 2-step program when faced with a cryptographic task which can not be proved unconditionally (1) find the minimal assumptions necessary and sufficient for the task at hand. (2) design a cryptographic system for the task and prove its security if and only if the minimal assumptions hold. Proofs of security then are realy proofs of secure design. They take a form of a constructive reduction. For example, the existence of a one-way function has been shown a sufficient and necessary condition for “secure” digital signatures to exist. To prove this statement one must show how to convert any “break” of the digital signature scheme into an efficient algorithm to invert the underlying one-way function. Defining formally “secure” and “break” is an essential preliminary step in accomplishing this program.

These type of constructive reductions are a double edged sword. Say that system has been proved secure if and only if integer factorization is not in polynomial time. Then, either the system is breakable and then the reduction proof immediately yields a polynomial time integer factorization algorithm which will please the mathematicians to no end, or there exists no polynomial time integer factorization algorithms and we have found a superb cryptosystem with guaranteed security which will please the computer users to no end.

Curiously, whereas early hopes of complexity theory producing lower bounds have not materialized, cryptographic research has yielded many dividends to complexity theory. New research themes and paradigms, as well as techniques originating in cryptography, have made their way to the main stream of complexity theory. Well known techniques include random self-reducibility, hardness amplification, low degree polynomial representations of Boolean functions, and proofs by hybrid and simulation arguments. Well known examples of research themes include : interactive and probabilisticly checkable proofs and their application to show inapproximability of NP-hard algorithmic problems, the study of average versus worst case hardness of functions, and trading off hardness of computation for randomness to be used for derandomizing probabilistic complexity classes.

These examples seem, on a superficial level, quite different from each other. There are similarities however, in addition to the fact that they are investigated by a common community of researchers, who use a common collection of techniques. In all of the above, an “observer” is always present, success and failure are defined “relative to the observer”, and if the observer cannot “distinguish” between two probabilistic events, they are treated as identical. This is best illustrated by examples. (1) A probabilistically checkable proofs is defined to achieve soundness if the process of checking it errs with exponentially small probability (which is indistinguishable from zero). (2) A function is considered hard to compute if all observers fail to compute it with non negligible probability taken over a efficiently samplable input distribution. It is not considered “hard” enough if it is only hard to compute with respect to some worst case input never to be encountered by the observer. (3) A source outputting bits according to some distribution is defined as pseudorandom if no observer can distinguish it from a truly random source (informally viewed as an on going process of flipping a fair coin).

### 1.1. Cryptography and classical mathematics

Computational infeasibility, which by algorithmic standards is the enemy of progress, is actually the cryptographer’s best friend. When a computationally difficult problem comes along with some additional properties to be elaborated on in this article, it allows us to design methods which while achieving their intended functionality are “infeasible” to break. Luckily, such computationally intensive problems are abundant in mathematics. Famous examples include integer factorization, finding short vectors in an integer lattice, and elliptic curve logarithm problem. Viewed this way, cryptography is an external customer of number theory, algebra, and geometry. However, the complexity theory view point has not left these fields untouched, and often shed new light on old problems.

In particular, the history of cryptography and complexity theory is intertwined with the development of algorithmic number theory. This is most evident in the invention of faster tests for integer primality testing and integer factorization  whose quality is attested by complexity analysis rather than the earlier benchmarking of their performance. A beautiful account on the symbiotic relationship between number theory and complexity theory is given by Adleman  who prefaces his article by saying that “Though algorithmic number theory is one of man’s oldest intellectual pursuit, its current vitality is unrivaled in history. This is due in part to the injection of new ideas from computational complexity.”

### 1.2. Cryptography and information theory

In a companion paper to his famous paper on information theory, Shannon  introduced a rigorous theory of perfect secrecy based on information theory. The theory addresses adversary algorithms which have unlimited computational resources. Thus, all definitions of security, which we will refer to henceforth as information theoretic security, and proofs of possibility and impossibility are with respect to such adversary. Shannon proves that “perfectly secure encryption” can only exist if the size of secret information that legitimate parties exchange between them in person prior to remote transmission, is as large as the total entropy of secret messages they exchange remotely. Maurer  generalized these bounds to two-way communications. This limits the practice of encryption based on information theory a great deal. Even worse, the modern cryptographic tasks of public-key encryption, digital signatures, pseudo random number generation, and most two party protocols can be proved down right impossible information theoretically. To achieve those, we turn to adversaries who are limited computationally and aim at computational security with the cost of making computational assumptions or assumptions about the physical world.

Having said that, some cryptographic tasks can achieve full information theoretic security. A stellar example is of multi party computation. Efficient and information theoretic secure multi-party protocols are possible unconditionally tolerating less than half faults, if there are perfect private channels between each pair of honest users . Statistical zero-knowledge proofs are another example .

Perfect private channels between pairs of honest users can be implemented in several settings: (1) The noisy channel setting  (which is a generalization of the wire tal channel ) where the communication between users in the protocol as well as what the adversary taps is subject to noise). (2) A setting where the adversary’s memory (i.e. ability to store data) is limited . (3) The Quantum Channels setting where by quantum mechanics, it is impossible for the adversary to obtain full information on messages exchanged between honest users. Introducing new and reasonable such settings which enable information theoretic security is an important activity.

Moreover, often paradigms and construction introduced within the computational security framework can be and have been lifted out to achieve information theoretic security. The development of randomness extractors from pseudo random number generators can be done in this fashion .

We note that whereas the computational complexity notions of secrecy, knowledge, and pseudo-randomness are different than their information theoretic analogues, techniques of error recovery developed in information theory are extremely useful. Examples include the Haddamard error correcting codes which is used to exhibit hard core predicates in one-way functions , and various polynomial based error correcting codes which enable high fault tolerance in multi-party computation .

To sum up, the theory of cryptography has in the last 30 years turned into a rich field with its own rules, structure, and mathematical beauty which has helped to shape complexity theory. In the talk, I will attempt to lead you through a short summary of what I believe to have been a fascinating journey of modern cryptography. I apologize in advance for describing my own journey, at the expense of other points of view. I attach a list of references including several survey articles that contain full details and proofs .

In the rest of the article, I will briefly reflect on a few points which will make my lecture easier to follow.

## 2. Conventions and complexity theory terminology

We say that an algorithm is polynomial time if for all inputs $`x`$, the algorithm runs in time bounded by some polynomial in $`|x|`$ where the latter denotes the length of $`x`$ when represented as a binary string. A probabilistic algorithm is one that can make random choices, where without loss of generality each choice is among two and is taken with probability 1/2. We view these choices as the algorithm coin tosses. A probabilistic algorithm $`A`$ on input $`x`$ may have more than one possible output depending on the outcome of its coin tosses, and we will let $`A(x)`$ denote the probability distribution over all possible outputs. We say that a probabilistic algorithm is probabilistic polynomial time (PPT) if for any input $`x`$, the expectation of the running time taken over the all possible coin tosses is bounded by some polynomial in $`|x|`$, regardless of the outcome of the coin tosses.

In complexity theory, we often speak of language classes. A language is a subset of all binary strings. The class P is the set of languages such that there exists a polynomial time algorithm, which on every input $`x`$ can decide if $`x`$ is in the language or not. The class $`\mathrm{BPP}`$ are those languages whose membership can be decided by a probabilistic polynomial time algorithm which for every input, is incorrect with at most negligible probability taken over the coin tosses of the algorithm. The class NP is the class of languages accepted by polynomial time non-deterministic algorithm which may make non-deterministic choices at every point of computation. Another characterization of NP is as the class of languages that have short proofs of memberships. Formally, $`NP=\{L|`$ there exists polynomial time computable function $`f`$ and $`k>`$ 0, such that $`xL`$ iff there exists $`y`$ such that $`f(x,y)=1`$ and $`|y|<|x|^k\}`$.

In this article, we consider an ‘easy’ computation to be one which is carried out by a PPT algorithm. A function $`\nu :\text{N}\text{R}`$ is negligible if it vanishes faster than the inverse of any polynomial. All probabilities are defined with respect to finite probability spaces.

## 3. Indistinguishability

Indistinguishability of probability distributions is a central concept in modern cryptography. It was first introduced in the context of defining security of encryption systems by Goldwasser and Micali . Subsequently, it turned out to play a fundamental role in defining pseudo-randomness by Yao , and zero-knowledge proofs by Goldwasser, Micali, and Rackoff .

###### Definition 1

Let $`X=\{X_k\}_k`$, $`Y=\{Y_k\}`$ be two ensembles of probability distributions on $`\{0,1\}^k`$. We say that $`X`$ is computationally indistinguishable from $`Y`$ if $``$ probabilistic polynomial time algorithms $`A`$, $``$ $`c>0`$, $`k_0`$, s.t $`k>k_0`$,

$$|\underset{tX_k}{\mathrm{Pr}}(A(t)=1)\underset{tY_k}{\mathrm{Pr}}(A(t)=1)|<\frac{1}{k^c}.$$

The algorithm $`A`$ used in the above definition is called a polynomial time statistical test.

Namely, for sufficiently long strings, no probabilistic polynomial time algorithms can tell whether the string was sampled according to $`X`$ or according to $`Y`$. Note that such a definition cannot make sense for a single string, as it can be drawn from either distribution. Although we chose to focus on polynomial time indistinguishability, one could instead talk of distribution which are indistinguishable with respect to any other computational resource, in which case all the algorithms $`A`$ in the definition should be bounded by the relevant computational resource. This, has been quite useful when applied to space bounded computations .

Of particular interest are those probability distributions which are indistinguishable from the uniform distribution, focused on in , and are called pseudorandom distributions.

Let $`U=\{U_k\}`$ denote the uniform probability distribution on $`\{0,1\}^k`$. That is, for every $`\alpha \{0,1\}^k`$, $`\mathrm{Pr}_{xU_k}[x=\alpha ]=\frac{1}{2^k}`$.

###### Definition 2

We say that $`X=\{X_k\}_k`$ is pseudo random if it is computationally indistinguishable from $`U`$. That is, $``$ probabilistic polynomial time algorithms $`A`$, $``$ $`c>0`$ $`k_0`$, such that $`k>k_0`$,

$$|\underset{tX_k}{\mathrm{Pr}}[A(t)=1]\underset{tU_k}{\mathrm{Pr}}[A(t)=1]|<\frac{1}{k^c}.$$

If $`A`$ and $`c`$ such that the condition in definition $`2`$ is violated, we say that $`X_k`$ fails the statistical test $`A`$.

A simple but not very interesting example of two probability distributions which are computationally indistinguishable are two distributions which are statistically very close. For example, $`X=\{X_k\}`$ defined exactly as the uniform distribution over $`\{0,1\}^k`$ with two exceptions, $`0^k`$ appears with probability $`\frac{1}{2^{k+1}}`$ and $`1^k`$ appears with probability $`\frac{3}{2^{k+1}}`$. Then the uniform distribution and $`X`$ can not be distinguished by any algorithm (even one with no computational restrictions) as long as it is only given a polynomial size sample from one of the two distributions.

It is fair to ask as this point whether computationally indistinguishability is anything more than statistical closeness where the latter is formally defined as follows.

###### Definition 3

Two probability distributions $`X,Y`$ are statistically close if $`c>0`$, $`k_0`$ such that $`k>k_0`$,

$$\underset{t}{}|\mathrm{Pr}(tX_k)\underset{t}{}(tU_k)<\frac{1}{k^c}.$$

$`X`$ and $`Y`$ are far if they are not close.

Do there exist distributions which are statistically far apart and yet are computationally indistinguishable? Goldreich and Krawczyk  who pose the question note this to be the case by a counting argument. However their argument is non constructive. The works on secure encryption and pseudo random number generators  imply the existence of efficiently constructible pairs of distributions that are computationally indistinguishable but statistically far, under the existence of one-way functions. The use of assumptions is no accident.

###### Theorem 4

 The existence of one-way functions is equivalent to the existence of pairs of polynomial-time constructible distributions which are computationally indistinguishable and statistically far.

## 4. Building blocks

A central building block required for many tasks in cryptography is the existence of a one-way function. Let us discuss this basic primitive as well as a few others in some detail.

### 4.1. One-way functions

Informally, a one-way function is a function which is “easy” to compute but “hard” to invert. Any probabilistic polynomial time (PPT) algorithm attempting to invert the function on an element in its range, should succeed with no more than “negligible” probability, where the probability is taken over the elements in the domain of the function and the coin tosses of the PPT attempting the inversion. We often refer to an algorithm attempting to invert the function as an adversary algorithm.

###### Definition 5

A function $`f:\{0,1\}^{}\{0,1\}^{}`$ is one-way if:

1. Easy to Evaluate: there exists a PPT algorithm that on input $`x`$ output $`f(x)`$;
2. Hard to Invert: for all PPT algorithm $`A`$, for all $`c>0`$, there exists $`k_0`$ such that for all $`k>k_0`$,

$$\mathrm{Pr}\left[A(1^k,f(x))=z:f(x)=f(z)\right]\frac{1}{k^c}$$

where the probability is taken over $`x\{0,1\}^k`$ and the coin tosses of $`A`$.

Note Unless otherwise mentioned, the probabilities during this section are calculated uniformly over all coin tosses made by the algorithm in question.

A few remarks are in order. (1)The guarantee is probabilistic. The adversary has low probability of inverting the function where the probability distribution is taken over the inputs of length $`k`$ to the one-way function and the possible coin tosses of the adversary.

(2) The adversary is not asked to find $`x`$; that would be pretty near impossible. It is asked to find some inverse of $`f(x)`$. Naturally, if the function is 1-1 then the only inverse is $`x`$. We note that it is much easier to find candidate one-way functions without imposing further restrictions on its structure, but being 1-1 or at least regular (that is, the number of preimage of any image is about of the range), it results in easier and more efficient cryptographic constructions.

(3) One may consider a non-uniform version of the “Hard to invert” requirement, requiring the function to be hard to invert by all non-uniform polynomial size family of algorithms, rather than by all probabilistic polynomial time algorithms. The former extends probabilistic polynomial time algorithms to allow for each different input size, a different polynomial size algorithm.

(4) The definition is typical to definitions from computational complexity theory, which work with asymptotic complexity—what happens as the size of the problem becomes large. One-wayness is only asked to hold for large enough input lengths, as $`k`$ goes to infinity. Per this definition, it may be entirely feasible to invert $`f`$ on, say, 512 bit inputs. Thus such definitions are useful for studying things on a basic level, but need to be adapted to be directly relevant to practice.

(5) The above definition can be considerably weakened by replacing the second requirement of the function to require it to be hard to invert on some non-negligible fraction of its inputs (rather than all but non-negligible fraction of its inputs ). This relaxation to a weak one-way function is motivated by the following example. Consider the function $`f:𝐙\times 𝐙𝐙`$ where $`f(x,y)=xy`$. This function can be easily inverted on at least half of its outputs (namely, on the even integers) and thus is not a one-way function as defined above. Still, $`f`$ resists all efficient algorithms when $`x`$ and $`y`$ are primes of roughly the same length which is the case for a non-negligible fraction ($`\frac{1}{k^2}`$) of the $`k`$-bit composite integers. Thus according to our current state of knowledge of integer factorization, $`f`$ does satisfy the weaker requirement. Convertion between any weak one-way function to a one-way function have been shown using “hardness amplification” techniques which expand the size of the input by a polynomial factor . Using expanders, constant factor expansions (of the input size) construction of a one-way function from a weak one-way function is possible .

(6) To apply this definition to practice we must typically envisage not a single one-way function but a family of them, parameterized by a security parameter $`k`$. That is, for each value of the security parameter $`k`$, there is a family of functions, each defined over some finite domain and finite ranges. The existence of a single one-way function is equivalent to the existence of a collection of one-way functions.

###### Definition 6

A collection of one-way functions is a set $`F=\{f_i:D_iR_i\}_{iI}`$ where $`I`$ is an index set, and $`D_i`$ ($`R_i`$) are finite domain(range) for $`iI`$, satisfying the following conditions.

1. Selection in Collection: $``$ PPT algorithm $`S_1`$ that on input $`1^k`$ outputs an $`iI`$ where $`|i|=k`$.
2. Selection in Domain: $``$ PPT algorithm $`S_2`$ that on input $`iI`$ outputs $`xD_i`$
3. Easy to Evaluate: $``$ PPT algorithm $`Eval`$ such that for $`iI`$ and $`xD_i`$, $`Eval(i,x)=f_i(x)`$.
4. Hardness to Invert: $``$ PPT adversary algorithm $`A`$, $`c>0`$, $``$ $`k_0`$ such that $``$ $`k>k_0`$,

$$\mathrm{Pr}\left[A(1^k,i,f_i(x))=z:f(x)=f(z)\right]\frac{1}{k^c}$$

(the probability is taken over $`iS_1(1^k),xS_2(i)`$ and the coin tosses of $`A`$).

The hardness to invert condition can be made weaker by requiring only that $`c>0`$, such that $``$ PPT algorithm $`A`$, $``$ $`k_0`$ such that $``$ $`k>k_0`$. $`Prob[A(1^k,i,f_i(x))z`$, $`f(x)=f(z)]>\frac{1}{k^c}`$ (the probability taken over $`iS_1(1^k),xS_2(i)`$ and the coin tosses of $`A`$). We call collections which satisfy such weaker conditions, collection of weak one-way functions. Transformations exist via sampling algorithms between both types of collections.

Another useful and equivalent notion is of a one-way predicate, first introduced in . This is a Boolean function of great use in encryption and protocol design. A one-way predicate is equivalent to the existence of 0/1 problems, for which it is possible to uniformly select an instance for which the answer is 0 (or respectively 1), and yet for a (pre-selected) instance it is hard to compute with success probability greater than $`\frac{1}{2}`$ whether the answer is 0 or 1.

###### Definition 7

A one-way predicate is a Boolean function $`B:\{0,1\}^{}\{0,1\}`$ for which

1. Sampling is possible: $``$ PPT algorithm $`S`$ that on input $`v\{0,1\}`$ and $`1^k`$, outputs a random $`x`$ such that $`B(x)=v`$ and $`x\{0,1\}^k`$.
2. Guessing is hard: $`c>0`$, $``$ PPT algorithms $`A`$, $`k`$ sufficiently large, $`Prob[A(x)`$ $`=B(x)]\frac{1}{2}+\frac{1}{k^c}`$ (probability is taken over $`v\{0,1\},xS(1^k,v)`$, and the coin tosses of $`A`$).

Proving the equivalence between one-way predicates and one-way functions is easy in the forward direction, by viewing the sampling algorithm $`S`$ as a function over its coin tosses. To prove the reverse implication is quite involved. Toward this goal, the notion of a hard core predicate of a one-way function was introduced in . Jumping ahead, hard core predicate of one-way functions yield immediately one-way predicates.

#### 4.1.1. Hard-core predicates

The fact that $`f`$ is a one-way function obviously does not necessarily imply that $`f(x)`$ hides everything about $`x`$. It is easy to come up with constructions of universal one-way functions in which one of the bits of $`x`$ leaks from $`f(x)`$. Even if each bit of $`x`$ is well hidden by $`f(x)`$ then some function of all of the bits of $`x`$ can be easy to compute. For example, the least significant bit of $`x`$ is easy to compute from $`f_{p,g}(x)=g^xmodp`$ where $`p`$ is a prime and $`g`$ a generator for the cyclic group $`Z_p^{}`$, even though we know of no polynomial time algorithms to compute $`x`$ from $`f_{p,g}(x)`$. Similarily, it is easy of compute the Jacobi symbol of $`x`$ mod $`n`$ from the RSA function $`RSA_{n,e}(x)=x^emodn`$ where $`(e,\varphi (n))=1`$, even though the fastest algorithm to invert $`RSA_{n,e}`$ needs to factor integer $`n`$ first, which is not known to be a polynomial time computation.

Yet, clearly there are some bits of information about $`x`$ which cannot be computed from $`f(x)`$, given that $`x`$ in its entirety is hard to compute. The question is, which bits of $`x`$ are hard to compute, and how hard to compute are they. The answer is encouraging. For several functions $`f`$ for which no polynomial time inverting algorithm is known, we can identify particular bits of the pre-image of $`f`$ which can be proven (via a polynomial time reduction) to be as hard as to compute with probability significantly better than $`\frac{1}{2}`$, as it is to invert $`f`$ itself in polynomial time. Examples of these can be found in .

More generally, a hard-core predicate for $`f`$, is a Boolean predicate about $`x`$ which is efficiently computable given $`x`$, but is hard to compute from $`f(x)`$ with probability significantly better than $`\frac{1}{2}`$.

###### Definition 8

A hard-core predicate of a function $`f:\{0,1\}^{}\{0,1\}^{}`$ is a Boolean predicate $`B:\{0,1\}^{}\{0,1\}`$, such that

1. $`PPT`$ algorithm $`Eval,`$ such that $`xEval(x)=B(x)`$
2. $`\text{PPT algorithm}A,c>0,k_0,\text{s.t.}k>k_0`$ $`\mathrm{Pr}[A(f(x))=B(x)]<\frac{1}{2}+\frac{1}{k^c}.`$ The probability is taken over the random coin tosses of A, and random choices of $`x`$ of length $`k`$.

Yao proposed a construction of a hard-core predicate for any one-way function . A considerably simpler construction and proof general result is due to Goldreich and Levin .

###### Theorem 9

 Let $`f`$ be a length preserving one-way function. Define $`f^{}(xr)=f(x)r`$, where $`|x|=|r|=k`$, and $``$ is the concatenation function. Then

$$B(xr)=\mathrm{\Sigma }_{i=1}^kx_ir_i(mod2)$$

is a hard-core predicate for $`f^{}`$ (Notice that if $`f`$ is one-way then so is $`f^{}`$).

Interestingly, the proof of the theorem can be regarded as the first example of a polynomial time list decoding  algorithm. Essentially $`B(x,r)`$ may be viewed as the $`r`$th bit of a Haddamrd encoding of $`x`$. The proof of the theorem yields a polynomial time error decoding algorithm which returns a polynomial size list of candidates for $`x`$, as long as the encoding is subject to an error rate of less than $`\frac{1}{2}ϵ`$ where $`ϵ>\frac{1}{k^c}`$ for some constant $`c>0`$, $`k=|x|`$. The length of the list is $`O(\frac{1}{ϵ^2})`$.

### 4.2. Trapdoor functions

A trapdoor function $`f`$ is a one-way function with an extra property. There also exists a secret inverse function (the trapdoor) that allows its possessor to efficiently invert $`f`$ at any point in the domain of his choosing. It should be easy to compute $`f`$ on any point, but infeasible to invert $`f`$ with high probability without knowledge of the inverse function. Moreover, it should be easy to generate matched pairs of $`f`$’s and corresponding trapdoor.

###### Definition 10

A trapdoor function is a one-way function $`f:\{0,1\}^{}\{0,1\}^{}`$ such that there exists a polynomial $`p`$ and a probabilistic polynomial time algorithm $`I`$ such that for every $`k`$ there exists a $`t_k\{0,1\}^{}`$ such that $`|t_k|p(k)`$ and for all $`x\{0,1\}^k`$, $`I(f(x),t_k)=y`$ such that $`f(y)=f(x)`$.

Trapdoor functions are much harder to locate than one-way function, as they seem to require much more hidden structure. An important problem is to establish whether one implies the other. Recent results of  indicate this may not the case.

A trapdoor predicate is a one-way predicate with an extra trapdoor property: for every $`k`$, there must exist trapdoor information $`t_k`$ whose size is bounded by a polynomial in $`k`$ and whose knowledge enables the polynomial-time computation of $`B(x)`$, for all $`x\{0,1\}^k`$. Restating as a collection of trapdoor predicates we get.

###### Definition 11

Let $`I`$ be an index set and for $`iI`$, $`D_i`$ a finite domain. A collection of trapdoor is a set $`B=\{B_i:D_i\{0,1\}\}_{iI}`$ such that:

1. $``$ PPT algorithm $`S_1`$ which on input $`1^k`$ outputs $`(i,t_i)`$ where $`iI\{0,1\}^k`$, and $`|t_i|<poly(k)`$ ( $`t_i`$ is the trapdoor).
2. $``$ PPT algorithm $`S_2`$ which on input $`iI,v\{0,1\}`$ outputs $`xD_i`$ such that $`B_i(x)=v`$.
3. $``$ PPT algorithm $`S_3`$ which on input $`iI,xD_i,t_i`$ outputs $`B_i(x)`$.
4. $``$ PPT adversary algorithms $`A`$, $`c>0`$, $`k_0,k>k_0`$, $`Prob[A(i,x)=B_i(x)]\frac{1}{2}+\frac{1}{k^c}`$ (the probability taken over $`iS_1(1^k),v\{0,1\},xS_2(i,v)`$, and the coins of A).

The existence of a trapdoor predicate is equivalent to the existence of secure public-key encryption as we shall see in the next section. Trapdoor functions imply trapdoor predicates, but it is an open problem to show that they are equivalent.

###### Claim 12

If trapdoor functions exist then collection of trapdoor predicates exist.

### 4.3. Candidate examples of building blocks

It has been shown by a fairly straightforward diagonalization argument  how to construct a universal one-way function (i.e. a function which is one-way if any one-way function exists). Still this is very inefficient, and concrete proposals for one-way function are needed for any practical usage of cryptographic constructions which utilized one-way functions. Moreover, looking into the algebraic, combinatorial, and geometric structure of concrete proposals has lead to many insights about what could be true about general one-way functions. The revelation process seems almost always to start from proving properties about concrete examples to generalizing to proving properties on general one-way functions.

Interesting proposals for one-way functions, trapdoor functions, and trapdoor predicates have been based on hard computational problems from number theory, coding theory, algebraic geometry, and geometry of numbers. What makes a computational problem a “suitable” candidate? First, it should be put under extensive scrutiny by the relevant mathematical community. Second, the problem should be hard on the average and not only in the worst case. A big project in cryptography is the construction of cryptographic functions which are provably hard to break on the average under some worst-case computational complexity assumption. A central technique is to show that a problem is as hard for an average instance as it is for a worst case instance by random self reducibility . A problem $`P`$ is random self reducible if there exists a probabilistic polynomial time algorithm that maps any instance $`I`$ of $`P`$ to a collection of random instances of $`P`$ such that given solutions to the random instances, one can efficiently obtain a solution to the original instance. Variations would allow mapping any instance of $`P`$ to random instances of $`P^{}`$.444This technique was first observed and applied to the number theoretic problems of factoring, discrete log, testing quadratic residuosity, and the RSA function. In each of these problems, one could use the algebraic structure to show how to map a particular input uniformly and randomly to other inputs in such a way that the answer for the original input can be recovered from the answers for the targets of the random mapping. Showing that polynomials are randomly self reducible over finite fields was applied to the low-degree polynomial representations of Boolean functions, and has been a central and useful technique in probabilistically checkable proofs.

Perhaps the most interesting problem in cryptography today is to show (or rule out) that the existence of a one-way function is equivalent to the $`NPBPP`$.

For lack of space, we discuss in brief a few proposals.

#### 4.3.1. Discrete logarithm problem proposal

Let $`p`$ be a prime integer and $`g`$ a generator for the multiplicative cyclic group $`𝒵_p^{}=\{1y<p|(y,p)=1\}`$. The discrete log problem (DLP) is given $`p`$,$`g`$, and $`yZ_p^{}`$, compute the unique $`x`$ such that $`1xp1`$ and $`y=g^xmodp`$. The discrete log problem has been first suggested to be useful for key exchange over the public channel by Diffie and Hellman .

The function $`DL(p,g,x)=(p,g,g^xmodp)`$, and the corresponding collection of functions $`DL=\{DL_{p,g}:Z_{p1}Z_p^{},DL_{p,g}(x)=g^xmodp\}_{<p,g>I}`$ where $`I=\{<p,g>,p\text{ prime },g\text{ generator}\}`$ have served as proposals for a one-way function and a collection of one-way functions (respectively). On one hand, there exist efficient algorithms to select pairs of $`(p,g)`$ of a given length with uniform probability , and to perform modulo exponentiation. On the other hand, the fastest algorithms to solve the discrete log problem is the generalized number field sieve version of the index-calculus method which runs in expected time $`e^{((c+o(1))(\mathrm{log}p)^{\frac{1}{3}}(\mathrm{log}\mathrm{log}p)^{\frac{2}{3}})}`$ (see survey ). Moreover, for a fixed prime $`p`$, $`DL(p,g,g^xmodp)`$ can be shown as hard to invert on the average over the $`1xp1`$ and $`g`$ generators, as it is for every $`g`$ and $`x`$.

An important open problem is to prove that, without fixing first the prime $`p`$, solving the discrete log problem for an average instance $`(p,g,y)`$ is hard on the average as in the worst case.

In the mid-eighties an extension of the discrete logarithm problem over prime integers, to computing discrete logarithms over elliptic curves was suggested by Koblitz and V. Miller (see survey ). The attraction is that the fastest algorithms known for computing logarithms over elliptic curves are of complexity $`O(\sqrt{p})`$ for finite field $`F_p`$. The main concern is that they have not been around long enough to go under extensive scrutiny, and that the intersection between the mathematical community who can offer such scrutiny and the cryptographic community is not large.

#### 4.3.2. Shortest vector in integer lattices proposal

In a celebrated paper  Ajtai described a problem that is hard on the average if some well-known integer lattice problems are hard to approximate in the worst case, and demonstrated how this problem can be used to construct one-way functions. Previous worst case to average case reductions were applied to two parameter problems and the reduction was shown upon fixing one parameter (e.g. in the discrete logarithm problem random self reducibility was shown fixing the prime parameter), whereas the  reduction is the first which averages over all parameters.

Let $`V`$ be a set of $`n`$ linearly independent vectors $`V=\{v_1,\mathrm{},v_n,v_i\}`$. The integer lattice spanned by $`V`$ is the set of all possible linear combinations of the $`v_i`$’s with integer coefficients, namely $`L(V)\stackrel{\mathrm{def}}{=}\{_ia_iv_i:a_i\text{Z}\text{ for all }i\}`$. We call $`V`$ the basis of the lattice $`L(V)`$. We say that a set of vectors $`L^n`$ is a lattice if there is a basis $`V`$ such that $`L=L(V)`$.

Finding “short vectors” (i.e., vectors with small Euclidean norm) in lattices is a hard computational problem. There are no known efficient algorithms to find or even approximate - given an arbitrary basis of a lattice - either the shortest non-zero vector in the lattice, or another basis for the same lattice whose longest vector is as short as possible. Given an arbitrary basis $`B`$ of a lattice $`L`$ in $`\text{R}^n`$, the best algorithm to approximate (up to a polynomial factor in $`n`$) the length of the shortest vector in $`L`$ is the $`L^3`$ algorithm  which approximates these problems to within a ratio of $`2^{n/2}`$ in the worst case, and its improvement  to ratio $`(1+ϵ)^n`$ for any fixed $`ϵ>0`$.

Ajtai reduced the worst-case complexity of problem (W) which is closely related the length of the shortest vector and basis in a lattice, to the average-case complexity of problem (A) (version presented here is due to Goldreich, Goldwasser, and Halevi ).

* : Given an arbitrary basis $`B`$ of a lattice $`L`$, find a set of $`n`$ linearly independent lattice vectors, whose length is at most polynomially (in $`n`$) larger than the length of the smallest set of $`n`$ linearly independent lattice vectors. (The length of a set of vectors is the length of its longest vector.)
* : Let parameters $`n,m,q𝒩`$ be such that $`n\mathrm{log}q<m\frac{q}{2n^4}`$ and $`q=O(n^c)`$ for some constant $`c>0`$. Given a matrix $`M\text{Z}_q^{n\times m}`$, find a vector $`x\{1,0,1\}^m,x0`$ so that $`Mx0(modq)`$.

###### Theorem 13

 Suppose that it is possible to solve a uniformly selected instance of Problem (A) in expected $`T(n,m,q)`$-time, where the expectation is taken over the choice of the instance as well as the coin-tosses of the solving algorithm. Then it is possible to solve Problem (W) in expected $`poly(|I|)T(n,poly(n),poly(n))`$ time on every $`n`$-dimensional instance $`I`$, where the expectation is taken over the coin-tosses of the solving algorithm.

The construction of a candidate one-way function follows in a straight forward fashion. Let $`M`$ be a random $`k\times m`$ matrix $`M`$ with entries from $`\text{Z}_q`$, where $`m`$ and $`q`$ are chosen so that $`k\mathrm{log}q<m<\frac{q}{2k^4}`$ and $`q=O(k^c)`$ for some constant $`c>0`$ ($`k`$ here is the security parameter).

The one-way function candidate is then $`f(M,s)=(M,Msmodq=_is_iM_imodq)`$ where $`s=s_1s_2\mathrm{}s_m\{0,1\}^m`$ and $`M_i`$ is the $`i`$’th column of $`M`$. We note that this function is regular.

#### 4.3.3. Factoring integers proposal

Consider the function $`Squaring(n,x)=(n,x^2modn)`$ where $`n=pq`$ for $`p,qZ`$ prime numbers and $`xZ_n^{}`$, and the corresponding collection of functions $`Squaring=\{Squaring_n(x)=x^2modn:Z_n^{}Z_n^{},n=pq,p,q\text{ primes},|p|=|q|=k\}_k`$. This function is easy to compute without knowing the factorization of $`n`$, and is easy to invert given the factorization of $`n`$ (the trapdoor) using fast square root extraction algorithms modulo prime moduli  and the Chinese remainder theorem. Moreover, as the primes are abundant by the prime number theorem ($`\frac{1}{k}`$ for $`k`$-bit primes) and there exist probabilistic expected polynomial time algorithms for primality testing , it is easy to uniformly select $`n,p,q`$ of the right form.

In terms of hardness to invert, Rabin  has shown it as hard to invert as it is to factor $`n`$ as follows. Suppose there exists a factoring algorithm $`A`$. Choose $`rZ_n^{}`$ at random. Let $`y=A(r^2modn)`$. If $`yr`$ or $`nr`$, then let $`p=gcd(ry,n)`$, else choose another $`r`$ and repeat. Within expected 2 trials you should obtain $`p`$. The asymptotically proven fastest integer factorization algorithm to date is the number field sieve which runs in expected time $`e^{((c+o(1))(\mathrm{log}n)^{\frac{1}{3}}(\mathrm{log}\mathrm{log}n)^{\frac{2}{3}})}`$ . The hardest input to any factoring algorithms are integers $`n=pq`$ which are product of two primes of similar length. Finally, for a fixed $`n`$, $`Squaring(n,)`$ can be shown as hard to invert on the average over $`xZ_n^{}`$ as it is for any $`x`$. We remark, that integer factorization has been first proposed as a basis for a trapdoor function in the celebrated work of Rivest, Shamir and Adelman .

By choosing $`p`$ and $`q`$ to be both congruent to $`3mod4`$ and restricting the domain of $`Squaring_n`$ to the quadratic residues mod $`n`$, this collection of functions becomes a collection of permutations proposed by Williams , which are especially easy to work with in many cryptographic applications.

An open problem is to prove that the difficulty of factoring integers is as hard on the average as in the worst case. In our terminology an affirmative answer would mean that $`x^2modn`$ is as hard to invert on the average over $`n`$ and $`x`$, as it is for any $`n`$ and $`x`$.

#### 4.3.4. Quadratic residues vs. quadratic non residues proposal

Let $`nZ`$. Then we call $`yZ_n^{}`$ is a quadratic residue mod $`n`$ iff $`xZ_n^{}`$ such that $`yx^2modn`$. Let us restrict our attention to $`n=pq`$ where $`p=q=3mod4`$.

Selecting a random quadratic residue mod $`n`$ is easy by choosing $`rZ_n^{}`$ and computing $`r^2modn`$. Similarily, for such $`n`$, selecting a random quadratic non-residue is easy by choosing $`rZ_n^{}`$ and computing $`nr^2modn`$ (this is a quadratic non-residue by the property of the $`n`$’s chosen).

On the other hand, deciding whether $`x`$ is a quadratic residue modulo $`n`$ for $`n`$ composite (which is the case if and only if it is a quadratic residue modulo each of its prime factors), seems a hard computational problem. No algorithm is known other than first factoring $`n`$ and then deciding whether $`x`$ is a quadratic residue modulo all its prime factors. This is easy for a prime modulos by computing the Legendre symbol $`(\frac{x}{p})=x^{\frac{p1}{2}}modp`$ ($`=1`$ iff $`x`$ is a quadratic residue mod $`p`$). The Legendre symbol is generalizable to the Jacobi symbol for composite moduli $`(\frac{x}{n})=\mathrm{\Pi }_{p^\alpha |n}(\frac{x}{p})^\alpha `$ where $`n=\mathrm{\Pi }p^\alpha `$. The Jacobi symbol only provides partial answer to whether $`xmodn`$ is a quadratic residue or not. For $`xJ_n^{+1}=\{xZ_n^{},(\frac{x}{n})=1\}`$, it gives no information.

A proposal by Goldwasser and Micali  for a collection of trapdoor predicates follows.

$`QR=\{QR_n:J_n^{+1}\{0,1\}\}_{nI}`$ where $`I=\{n=pqp,q,\text{ primes},|p|=|q|\}`$,

$$QR_n(x)=\left\{\begin{array}{c}\text{0 if }x\text{ is a quadratic residue mod }n\hfill \\ \text{1 if }x\text{ is a quadratic non-residue mod }n\hfill \end{array}\right\}.$$

It can be proved that for every $`n`$ distinguishing between random quadratic residues and random quadratic non residues with Jacobi symbol +1, is as hard as solving the problem entirely in the worst case.

###### Theorem 14

 Let $`SI`$. If there exists a PPT algorithm which for every $`nS`$, can distinguish between quadratic residues and quadratic non-residues with non-negligible probability over $`\frac{1}{2}`$ (probability taken over the $`xZ_n^{}`$ and the coin tosses of the distinguishing algorithm), then there exist a PPT algorithm which for every $`nS`$ and every $`xZ_n^{}`$ decides whether $`x`$ is a quadratic residue mod $`n`$ with probability close to 1.

## 5. Encryption case study

As discussed in the introduction we would like to propose cryptographic schemes for which we can prove theorems guaranteeing the security of our proposals. This task includes a definition phase, construction phase and a reduction proof which is best illustrated with an example. We choose the example of encryption.

We will address here the simplest setting of a passive adversary who can tap the public communication channels between communicating parties. We will measure the running time of the encryption, decryption, and adversary algorithms as a function of a security parameter $`k`$ which is a parameter fixed at the time the cryptosystem is setup. We model the adversary as any probabilistic algorithm which runs in time bounded by some polynomial in $`k`$. Similarily, the encryption and decryption algorithms designed are probabilistic and run in polynomial time in $`k`$.

### 5.1. Encryption: definition phase

###### Definition 15

A public-key encryption scheme is a triple, $`(G,E,D)`$, of probabilistic polynomial-time algorithms satisfying the following conditions

1. key generation algorithm : On input $`1^k`$ (the security parameter) algorithm $`G`$, produces a pair $`(e,d)`$ where $`e`$ is called the public key, and $`d`$ the corresponding private key. (Notation: $`(e,d)G(1^k)`$.) We will also refer to the pair $`(e,d)`$ a pair of encryption/decryption keys.
2. An encryption algorithm: Algorithm $`E`$ takes as inputs encryption key $`e`$ from the range of $`G(1^k)`$ and string $`m\{0,1\}^k`$ called the message, and produces as output string $`c\{0,1\}^{}`$ called the ciphertext. (We use the notation $`cE(e,m)`$ or the shorthand $`cE_e(m)`$.) Note that as $`E`$ is probabilistic, it may produce many ciphertexts per message.
3. A decryption algorithm: Algorithm $`D`$ takes as input decryption key $`d`$ from the range of $`G(1^k)`$, and a ciphertext $`c`$ from the range of $`E(e,m)`$, and produces as output a string $`m^{}\{0,1\}^{}`$, such that for every pair $`(e,d)`$ in the range of $`G(1^k)`$, for every $`m`$, for every $`cE(e,m)`$, the $`prob(D(d,c)m^{})`$ is negligible.
4. Furthermore, this system is “secure” (see discussion below ).

A private-key encryption scheme is identically defined except that $`e=d`$. The security definition for private-key encryption and public-key encryption are different in one aspect only, in the latter $`e`$ is a public input available to the whereas in the former $`e`$ is a secret not available to the adversary.

#### 5.1.1. Defining security

Brain storming about what it means to be secure brings immediately to mind several desirable properties. Let us start with the the minimal requirement and build up.

First and foremost the private key should not be recoverable from seeing the public key. Secondly, with high probability for any message space, messages should not be entirely recovered from seeing their encrypted form and the public file. Thirdly, we may want that in fact no useful information can be computed about messages from their encrypted form. Fourthly, we do not want the adversary to be able to compute any useful facts about traffic of messages, such as recognize that two messages of identical content were sent, nor would we want her probability of successfully deciphering a message to increase if the time of delivery or relationship to previous encrypted messages were made known to her.

In short, it would be desirable for the encryption scheme to be the mathematical analogy of opaque envelopes containing a piece of paper on which the message is written. The envelopes should be such that all legal senders can fill it, but only the legal recipient can open it.

Two definitions of security attempting to capture the “opaque envelope” analogy have been proposed in the work of  and are in use today: computational indistinguishability and semantic security. The first definition is easy to work with whereas the second seems to be the natural extension of Shannon’s perfect secrecy definition to the computational world. They are equivalent to each other as shown by .

The first definition essentially requires that the the adversary cannot find a pair of messages $`m_0,m_1`$ for which the probability distributions over the corresponding ciphertexts is computationally distinguishable.

###### Definition 16

We say that a Public Key Cryptosystem $`(G,E,D)`$ is computationally indistinguishable if $``$ PPT algorithms $`F,A`$, and for $``$ constant $`c>0`$, $`k_0`$, $``$ $`k>k_0`$, $`m_0,m_1F(1^k)`$, $`|m_0|=|m_1|`$,

$`|\mathrm{Pr}[A(e,c)=1\text{ where }(e,d)G(1^k);cE(e,m_0)]`$
$`\mathrm{Pr}[A(e,c)=1(e,d)G(1^k);cE(e,m_1)]|<{\displaystyle \frac{1}{k^c}}.`$
Remarks about the definition

1. In the case of private-key cryptosystem, the definition changes slightly. The encryption key $`e`$ is not given to algorithm $`A`$.
2. Note that even if the adversary know that the messages being encrypted is one of two, he still cannot tell the distributions of ciphertext of one message apart from the other.
3. Any cryptosystem in which the encryption algorithm $`E`$ is deterministic immediately fails to pass this security requirement. (e.g given $`e,m_0,m_1`$ and $`c`$ it would be trivial to decide whether $`c=E(e,m_0)`$ or $`c=E(e,m_1)`$ as for each message the ciphertext is unique.)

The next definition is called Semantic Security. It may be viewed as a computational version of Shannon’s perfect secrecy definition. It requires that the adversary should not gain any computational advantage or partial information from having seen the ciphertext.

###### Definition 17

We say that an public key cryptosystem $`(G,E,D)`$ is semantically secure if $``$ PPT algorithm $`A`$ $``$ PPT algorithm $`B`$, s.t. $``$ PPT algorithm $`M`$, $``$ function $`h:M(1^k)\{0,1\}^{}`$, $`c>0`$, $`k_0`$, $`k>k_0`$, $`\mathrm{Pr}[A(e,|m|,c)=h(m)(e,d)G(1^k);mM(1^k);cE(e,m)]\mathrm{Pr}[B(e,|m|)=h(m)mM(1^k)]+\frac{1}{k^c}.`$

The algorithm $`M`$ corresponds to the message space from which messages are drawn, and the function $`h(m)`$ corresponds to information about message $`m`$ ( for example, $`h(m)=1`$ if $`m`$ has the letter ‘e’ in it).

###### Theorem 18

 A Public Key Cryptosystem is computationally indistinguishable if and only if it is semantically secure.

### 5.2. Encryption: construction phase

We turn now to showing how to actually build a public key encryption scheme which is polynomial time indistinguishable. The construction shown here is by Goldwasser and Micali . The key to the construction is to answer a simpler problem: how to securely encrypt single bits. Encrypting general messages would follow by viewing each message as a string of bits each encrypted independently.

Given a collection of trapdoor predicates B, we define a public key cryptosystem $`(G,E,D)_B`$ as follows:

###### Definition 19

A probabilistic encryption $`PE_B=(G,E,D)`$ based on trapdoor predicates $`B`$ is defined as:

1. Key generation algorithm G: On input $`1^k`$, G outputs $`(i,t_i)`$ where $`B_iB`$, $`i\{0,1\}^k`$ and $`t_i`$ is the trapdoor information. The public encryption key is $`i`$ and the private decryption key is $`t_i`$. (This is achieved by running the sampling algorithm $`S_1`$ from the def of B.)
2. Let $`m=m_1\mathrm{}m_n`$ where $`m_j\{0,1\}`$ be the message.

| $`E(i,m)`$ encrypts $`m`$ as follows: |
| --- |
|  | Choose $`x_j_RD_i`$ such that $`B_i(x_j)=m_j`$ for $`j=1,\mathrm{},n`$. |
|  | Output $`c=f_i(x_1)\mathrm{}f_i(x_n)`$. |
3. Let $`c=y_1\mathrm{}y_k`$ where $`y_iD_i`$ be the cyph ertext.

| $`D(t_i,c)`$ decrypts $`c`$ as follows: |
| --- |
|  | Compute $`m_j=B_i(y_j)`$ for $`j=1,\mathrm{},n`$. |
|  | Output $`m=m_1\mathrm{}m_n`$. |

It is clear that all of the above operations can be done in expected polynomial time from the definition of trapdoor predicates and that messages can indeed be sent this way.

Let us ignore for a minute the apparent inefficiency of this proposal in bandwidth expansion and computation (which has been addressed by Blum and Goldwasser in ) and talk about security. It follows essentially verbatim from the definition of trapdoor predicates that this system is polynomially time indistinguishable in the case the message is a single bit (i.e. $`n=1`$). Even though every bit individually is secure, it is possible in principle that some predicate computed on all the bits (e.g. their parity) is easily computable. Luckily, it is not the case.

We prove polynomial time indistinguishability using the hybrid argument. This method is a key proof technique in the theory of pseudo randomness and secure protocol design, in enabling to show how to convert a slight “edge” in solving a problem into a complete surrender of the problem.

As this is one of the most straight forward simplest examples of this technique we shall give it in full.

###### Theorem 20

 Probabilistic encryption $`PE_B=(G,E,D)`$ is semantically secure if and only if $`B`$ is a collection of trapdoor predicates.

Proof  Suppose that $`(G,E,D)`$ is not indistinguishably secure (i.e. not semantically secure). Then there is a $`c>0`$, a PPT $`A`$ and $`M`$ such that for infinitely many $`k`$, $`m_0,m_1M(1^k)`$ with $`|m_0|=|m_1|`$,

$`()`$ $`\mathrm{Pr}[A(i,c)=1\text{ where }(i,t_i)G(1^k);cE(i,m_0)]`$
$`\mathrm{Pr}[A(i,c)=1(i,t_i)G(1^k);cE(i,m_1)]{\displaystyle \frac{1}{k^c}},`$
where the probability is taken the choice of $`(i,t_i)`$, the coin tosses of $`A`$ and $`E`$.

Consider $`k`$ where (\*) holds. Wlog, assume that $`|m_0|=|m_1|=k`$ and that $`A`$ says $`0`$ more often when $`c`$ is an encryption of $`m_0`$ and $`1`$ more often when $`c`$ is an encryption of $`m_1`$.

Define distributions $`D_j=E(i,s_j)`$ for $`j=0,1,\mathrm{},k`$ where $`s_0=m_0,s_k=m_1`$ and $`s_j`$ differs from $`s_{j+1}`$ in precisely $`1`$ bit.

Let $`P_j=\mathrm{Pr}[A(i,c)=1|cD_j]`$.

Then $`P_kP_0\frac{1}{k^c}`$ and since $`_{j=0}^{k1}(P_{j+1}P_j)=P_kP_0`$, $`j`$ such that $`P_{j+1}P_j\frac{1}{k^{c+1}}`$.

Assume that $`s_j`$ and $`s_{j+1}`$ differ in the $`l^{\text{th}}`$ bit; that is, $`s_{j,l}s_{j+1,l}`$ or, equivalently, $`s_{j+1,l}=\overline{s_{j,l}}`$ where $`s_{j,u}`$ is the $`u`$-th bit of $`s_j`$.

Now, consider the following algorithm $`B`$ which takes input $`i,y`$ and outputs $`0`$ or $`1`$ as its guess to the value of the hard core predicate $`B_i(y)`$.

$`B`$ on input $`i,y`$:

1. Choose $`y_1,\mathrm{},y_k`$ such that $`B_i(y_r)=s_{j,r}`$ for $`r=1,\mathrm{},k`$ using $`S_1`$ from the definition of $`B`$.
2. Let $`c=y_1,\mathrm{},y,\mathrm{},y_k`$ where $`y`$ has replaced $`y_l`$ in the $`l^{\text{th}}`$ block.
3. If $`A(1^k,i,,m_0,m_1,c)=0`$ then output $`s_{j,l}`$.
If $`A(1^k,i,,m_0,m_1,c)=0`$ then output $`s_{j+1,l}=\overline{s}_{j,l}`$.

Note that $`cE(i,s_j)`$ if $`B_i(y)=s_{j,l}`$ and $`cE(i,s_{j+1})`$ if $`B_i(y)=s_{j+1,l}`$.

Thus, in step $`3`$ of algorithm $`B`$, outputting $`s_{j,l}`$ corresponds to $`A`$ predicting that $`c`$ is an encryption of $`s_j`$.

Claim $`\mathrm{Pr}[B(i,y)=B_i(y)]>\frac{1}{2}+\frac{1}{k^{c+1}}`$.

Proof

$`\mathrm{Pr}[B(i,f_i(y))=B_i(y)]`$ $`=`$ $`\mathrm{Pr}[A(i,c)=0|cE(i,s_j)]\mathrm{Pr}[cE(i,s_j)]`$
$`+\mathrm{Pr}[A(i,c)=1|cE(i,s_{j+1})]\mathrm{Pr}[cE(i,s_{j+1})]`$
$``$ $`(1P_j)({\displaystyle \frac{1}{2}})+(P_{j+1})({\displaystyle \frac{1}{2}})`$
$`=`$ $`{\displaystyle \frac{1}{2}}+{\displaystyle \frac{1}{2}}(P_{j+1}P_j)`$
$`>`$ $`{\displaystyle \frac{1}{2}}+{\displaystyle \frac{1}{k^{c+1}}}.`$
Thus, $`B`$ will predict $`B_i(y)`$ given $`i`$, $`y`$ with probability better than $`\frac{1}{2}+\frac{1}{k^{c+1}}`$. This contradicts the assumption that $`B_i`$ is a trapdoor predicate.

Hence, the probabilistic encryption $`PE=(G,E,D)`$ is indistinguishably secure.

### 5.3. Strengthening the adversary: non malleable security

The entire discussion so far has assumed that the adversary can listen to the cipher texts being exchanged over the insecure channel, read the public-file (in the case of public-key cryptography), generate encryptions of any message on his own (for the case of public-key encryption), and perform probabilistic polynomial time computation.

One may imagine a more powerful adversary who can intercept messages being transmitted from sender to receiver and either stop their delivery all together or alter them in some way. Even worse, suppose the adversary can after seeing a ciphertext, request a polynomial number of related ciphertexts to be decrypted for him. For definitions and constructions of encryption schemes secure against such adverdary see .

## 6. A constructive theory of pseudo randomness

A theory of randomness based on computability theory was developed by Kolmogorov, Solomonov and Chaitin . This theory applies to individual strings and defines the complexity of strings as the shortest program (running on a universal machine) that generates that string. A perfectly random string is the extreme case for which no shorter program than the length of the string itself can generate it. Inherintly, it is impossible to generate perfect random strings from shorter ones.

One of the surprising contributions of cryptographically motivated research in the early eighties, has been a theory of randomness computational complexity theory pioneered by Shamir  Blum and Micali , which makes it possible in principle to deterministically generate random strings from shorter ones. Not to mix notions, we will henceforth refer to this latter development as a theory of pseudo randomness, and the strings generated as pseudo random. In contrast, when we speak of choosing a truly random string of a fixed length over some alphabet, we refer to selecting it with uniform probability over all strings of the same length. In this section we shall only speak of binary alphabet. The notation $`x_R\{0,1\}^k`$ will thus be taken to mean that for every $`s\{0,1\}^k`$, the probability of $`x=s`$ is $`1/2^k`$.

Defining pseudo-random distributions is a special case of the definition of computational indistinguishability, which we encountered earlier in the context of secure encryption. A distribution over binary strings is called pseudo-random if it is computationally indistinguishable from the uniform distribution over all binary strings of the same length. The idea is that as long as we cannot tell apart samples from the uniform distribution from samples of a distribution $`X`$ in polynomial time , there is no difference between using either distributions that can be observed in polynomial time. In particular, any probabilistic algorithm, in which the internal coin flips of the algorithm are replaced by strings sampled from $`X`$, must not behave any different than it would using truly random coin flips. A counter example will yield a statistical test to distinguish between $`X`$ and the uniform distribution.

A deterministic polynomial time program which ’stretchs’ a short input string selected with uniform distribution (henceforth called the ‘seed’), to a polynomial long output string is called a pseudo random sequence generator. When such a construction is accompanied with a proof that the output string distribution is pseudo random we call the generator a strong pseudo random sequence generator (SPRSG).555 Again the choice of polynomial-time is arbitrary here, a strong pseudo random sequence generator can be defined to be a deterministic program which works in time $`T(n)`$ where $`n`$ is the seed length and is computationally indistinguishable with respect to algorithms which run in time $`T^{}(n)`$ for time functions $`T,T^{}`$.

In a culmination of a sequence of results by , Hastand, Impagliazzo, Levin and Luby showed that a necessary and sufficient condition for the existence of strong pseudo random sequence generators is the existence of one-way functions.

The link between one-way functions and pseudo randomness starts from the following observation. First, rephrase the fact that inverting one-way functions is difficult, by saying that the inverse of a one-way function is unpredictable. In particular, the hard-core of a one-way function is impossible to predict with any non-negligible probability greater than $`\frac{1}{2}`$. Second, show that impossibility to predict is the ultimate test for pseudo randomness. Namely, if a pseudo-random sequence generator has the property that it is difficult to predict the next bit from previous ones with probability significantly better than $`\frac{1}{2}`$ in time polynomial in the size of the seed, then it is impossible to distinguish in polynomial time between strings produced by the pseudo random sequence generators and truly random strings. This is proved by turning any statistical test that distinguishes in polynomial time pseudo random strings from random strings into polynomial time next bit predictor. This link is not conditional on the existence of one-way functions. In fact, in work by Nisan and Wigderson  they removed the requirement that the pseudo random sequence generator has to work in time which is as fast as the algorithm trying to distinguish the output sequences from truly random. Generators of this type are generally useless for cryptographic applications (as they can not be generated in feasible time) but are very useful for proving complexity theoretic results.

Strong pseudo random generators are useful for understanding the relation between deterministic algorithms and probablistic algorithms. The idea which was put forth by Yao  was to replace a single execution of a probablistic polynomial time algorithm $`A`$ with the majority output of all the executions of the same algorithm, where each execution uses instead of random coins the output of a strong pseudo random number generator on a different input seed. The cost of the latter deterministic procedure will be a factor of $`2^k^{}`$ longer where $`k^{}`$ is the seed length used to generate the pseudo random sequences necessary. The algorithm $`A`$ must behave “the same” when it uses truly random coins as when it uses coins which are pseudo-random, as otherwise it becomes a distinguisher between the uniform and pseudo-random distributions, an impossible task for a probabilistic polynomial time algorithm. Putting this together, we get : if one-way functions exist, then $`BPP_ϵDTIME(2^{k^ϵ})`$. This tradeoff between the hardness of inverting the one-way function, and randomness replacement, has been followed up with many papers in complexity theory each either relaxing the hardness assumption or tightening the relation between deterministic and probabilistic complexity classes.

Strong pseudo random generators are particularly useful for cryptography. Suppose you need a large supply of random strings for your cryptographic applications (e.g. the choice of secret keys, internal coin tosses of an encryption algorithm, etc.). If you use instead of truly random bits, pseudo random sequence generators which are weak (e.g. predictable), it may completely destroy the underlying cryptographic applications . In contrast, we can replace any use of truly random coins with strong pseudo random ones (assuming we have access to truly random coins for the seeds — which is an interesting discussion all by itself), without fear of compromising the security of the underlying application. Indeed, if as a result of such replacement the cryptographic application becomes insecure, then a way is found to distinguish outputs of SPRG from the uniform distribution. Many classical pseudo random number generators which are quite useful and effective for Monte Carlo simulations, have been shown not only weak but predictable in a strong sense which makes them typically unsuitable for cryptographic applications. For example, linear feedback shift registers  are well-known to be cryptographically insecure; one can solve for the feedback pattern given a small number of output bits, and similarily outputs of linear congruential generators . In  Kannan, Lenstra, and Lovasz use the $`L^3`$ algorithm to show that the binary expansion of any algebraic number $`y`$ (such as $`\sqrt{5}=10.001111000110111\mathrm{}`$) is insecure, since an adversary can identify $`y`$ exactly from a sufficient number of bits, and then extrapolate $`y`$’s expansion.

### 6.1. Pseudo random functions, permutations, and what else?

Similarily to defining pseudo random sequences one may ask what other random objects can be replaced with pseudo-random counter parts. Goldreich, Goldwasser and Micali  considered in this light random functions, which from a gold mind for applications. Pseudo random functions are defined to be for every size $`k`$ a subset of all functions from (and to) the binary strings of length $`k`$, which are polynomial time indistinguishable from truly random functions by any algorithm whose only access to the function is to query it on inputs of its choice. However, in contrast with a truly random function, a pseudo random function has a short description which if known enables efficient evaluation.

Let $`H_k=\{f:\{0,1\}^k\{0,1\}^k\}`$ then $`|H_k|=(2^k)^{2^k}`$. Let $`=_kH_k`$.

###### Definition 21

A polynomial time statistical test for functions is a polynomial time algorithm $`T^f`$ with access to a black box $`f`$ from which $`T`$ can request values of $`f(x)`$ for x of $`T`$’s choice. A collection of functions $`=_kF_k`$ where $`F_kH_k`$ passes the statistical test $`T`$ if $`Q𝐐[x],k_0,k>k_0|T(F_k)T(H_k)|<\frac{1}{Q(k)}`$ where $`T(F_k)=\mathrm{Pr}_{fF_k,\text{coins of T}}[T^f(1^k)=1]`$ and $`T(H_k)=\mathrm{Pr}_{fH_k,\text{coins of}T}[T^f(1^k)=1]`$.

###### Definition 22

A collection of functions $`=_kF_k`$ is a pseudo-random collection of functions if

1. (Indexing) For each k, there is a unique index $`i\{0,1\}^k`$ associated with each $`fF_k`$. The function $`fF_k`$ associated with index $`i`$ will be written $`f_i`$.
2. (Efficiency) There is a polynomial time function $`A`$ so that $`A(i,x)=f_i(x)`$.
3. (Pseudo-randomness) $``$ passes all polynomial time statistical tests for functions.

###### Theorem 23

 If there exist one-way functions, then there exist pseudo-random collections of functions.

An immediate application of pseudo random functions is the construction of semantically secure private key cryptosystem as follows. Let $`s`$ an index of a pseudo random function $`f_s`$ be the joint secret key of the sender Alice and the receiver Bob. Then to encrypt message $`m`$, Alice selects at random $`r\{0,1\}^k`$, and sets the cipher text $`c=(r,f_s(r)m)`$ where $``$ is the bit-wise exclusive-or of two strings. To decrypt $`c=(a,b)`$, Bob computes $`f_s(a)b`$.

Pseudo random functions have been used to derive negative results in computational learning theory by Valiant and Kearns . They show that any concept class (i.e. a set of Boolean functions) which contains a family of pseudo random functions cannot be efficiently learnable under the uniform distribution and with the help of membership queries. A learning algorithm is given oracle access to any function in the class and is required to output a description of a function which is close to the target function (being queried).

The work on natural proofs originated by Rudich and Razborov  use pseudo random functions to derive negative results on the possibility of proving good complexity lower bounds using a restricted class of circuit lower bound proofs referred to as natural. It is proved that natural (lower bound) proofs cannot be established for complexity classes containing a family of pseudo random functions.

An interesting question is to characterize which classes of random objects can be replaced by pseudo random objects. Luby and Rackoff  treated the case of pseudo random permutations and Naor and Reingold the case of permutations with cyclic structure . As any object can be abstracted as a restricted class of functions, the real question is what form of access to the function does the statistical test have. In the standard definition, the statistical test for functions can query the functions at values of its choice. This may not be necessarily the natural choice in every case. For example, if the function corresponds to the description of a random graph (e.g. $`f(u,v)=1`$ if and only if an edge is present between vertices $`u`$ and $`v`$).

Define the “ultimate” extension of a statistical test for functions on $`k`$ bit strings, to be given access to the entire truth table of the function (i.e. an exponential size input). The following observation is then straightforward.

###### Theorem 24

Let $`f:\{0,1\}^{}\{0,1\}^{}`$ be polynomial time computable function, for which the fastest inverting algorithm runs in time $`2^{n^ϵ}`$ for some $`ϵ>0`$. Then, there exist collections of pseudo random functions which pass all ultimate statistical tests for functions.

## 7. Interactive protocols, interactive proofs, and zero knowledge interactive proofs

Secure one-way communication is a special case of general interactive protocols. The most exciting developments in cryptography beyond public-key cryptography has been the development of interactive protocols, interactive proofs, and zero knowledge interactive proofs . 666In particular, the idea of multi-prover interactive proofs of Benor, Goldwasser, Kilian, and Wigderson  (which has become better known as probabilistic checkable proofs) has led to a rice body of NP-hardness results for approximation versions of optimization problems . Unfortunately, we have no space to cover these developments in this article. These topics have been surveyed extensively, and the interested reader may turn to .

A few final words. Generally speaking, an interactive protocol consists of two or more parties who cooperate and coordinate without a trusted “third” party to accomplish a common goal, referred to as the functionality of the protocol, while maintaining the secrecy of their private data. A functionality may be computing a simple deterministic function such as majority of the inputs of the communicating parties, or a more complicated probabilistic computation such as playing a non-cooperative game without a trusted referee.

In the case of more than two parties, the case of adversarial coalitions of participants who attempt to damage the functionality and break secrecy has been considered. Very powerful and surprising theorems about the ability of playing non-cooperative games without a trusted “third party” have been shown. A sample theorem of Benor, Goldwasser, and Wigderson shows that in the presence of an adversarial coalition containing less than a third of the parties, any probabilistic computation can be performed maintaining functionality and perfect information theoretic secrecy of the inputs, as long as each pair of parties can communicate in perfect secrecy . These results make extensive use of error correcting codes based on polynomials. The connection between these theorems and research in game theory and threory of auctions is well worth examining.


format: text

text:
# Phys. Rev. Lett., in press. Adsorption of Xe atoms on metal surfaces: New insights from first-principles calculations

\[

## Abstract

The adsorption of rare gases on metal surfaces serve as the paradigm of weak adsorption where it is typically assumed that the adsorbate occupies maximally coordinated hollow sites. Density-functional theory calculations using the full-potential linearized augmented plane wave method for Xe adatoms on Mg(0001), Al(111), Ti(0001), Cu(111), Pd(111), and Pt(111), show, however, that Xe prefers low-coordination on-top sites in all cases. We identify the importance of polarization and a site-dependent Pauli repulsion in actuating the site preference and the principle nature of the rare-gas atom–metal surface interaction. Copyright (2002) by The American Physical Society.

PACS numbers:68.35.Bs,68.35.Md,71.15.Ap

\]

The adsorption of rare-gas atoms on metal surfaces represent prototypical physical adsorption systems . Noting that these adatoms have closed shells, it is typically assumed that the adatom-substrate interaction is determined by an interplay of van der Waals attraction and Pauli repulsion, and that these adsorbates prefer maximally coordinated sites . However, the concept of the van der Waals interaction (dispersion forces) is valid for large distances where orbitals almost do not overlap, and at closer distances, near the equilibrium geometry of an adsorbate on a surface, the direct interaction of adsorbate and substrate orbitals can be significant. Thus, although the van der Waals tail is not described by state-of-the-art exchange-correlation functionals, the short-range attraction, as well as the Pauli repulsion, is treated properly. This appears to be valid in particular for the adsorption of heavier rare-gas atoms, but also for the scattering of He and Ne atoms at metal surfaces, the interatomic distances at the turning point are sufficiently small that density-functional theory (DFT) calculations provide the correct description .

With regard to the preferred adsorption site, about ten years ago it was argued that Xe on Pt(111) adsorbs in low-coordination on-top sites instead of the expected high-coordination hollow sites ; a quite surprising, not widely accepted, and certainly not understood suggestion. This assessment was based on He-atom diffraction data from the low-temperature ($`T60`$ K) uniaxially compressed phase of Xe on Pt(111) . Later, a spin-polarized low-energy electron diffraction (SP-LEED) study of Xe-adsorption “showed” that Xe atoms adsorb preferentially in hollow sites on Pt(111)  and Pd(111)  in the $`(\sqrt{3}\times \sqrt{3})R30^{}`$ structure (from now on labeled $`\sqrt{3}`$). These latter findings were subsequently contradicted by recent LEED studies, which reported that Xe in the $`\sqrt{3}`$ structure on Cu(111), Pd(111), and Pt(111) adsorbs in the on-top sites .

Thus, despite the conceived “simplicity” of these adsorption systems, even the most basic questions have not been answered satisfactorily: What is the adsorption site and why is it what it is? and what is the nature of the adsorbate-surface bond?

With respect to first-principles studies, the first good-quality calculation was performed by Müller , who studied Xe on Pt(111) using the cluster approach and the local-density approximation (LDA). It was concluded that the on-top site was energetically preferred over the hollow site by 30 meV. The interaction was described in terms of a hybridization of Xe $`5p`$ orbitals with metal $`d`$-states, with the on-top site affording the greater mixing and hence being the preferred adsorption site. Some questions about this work were raised (e.g. ): $`(i)`$ Besides the general concern about the validity of the cluster approach, such calculations may only relate to low coverages, and not to the case of Xe in the $`\sqrt{3}`$ adlayer, which is the only structure for which good experimental data exists. $`(ii)`$ It is also unclear why the top site affords the greater mixing. As it stands, this is more a statement than an explanation. $`(iii)`$ Because on-top site adsorption was also found for Xe on Cu(111), for which the $`d`$-band lies well below the Fermi level, a crucial role of substrate $`d`$-states seems unlikely . A recent work by Betancourt and Bird  find that Xe also prefers the on-top site in the $`\sqrt{3}`$ adlayer structure on Pt(111). And for an artificial $`c(2\times 2)`$-Xe/Ag(001) structure, Clarke et al.  reported a theoretical study which also favors the on-top site. However, neither Betancourt and Bird, nor Clarke et al. presented a consistent explanation for the on-top site preference. Finally, a recent study of the Xe/Cu(111) system using a ten-atom cluster model, has investigated the interface dipole and work-function, but the site preference was not addressed .

To determine the adsorption site preference of Xe adatoms on metal surfaces, to explain the site preference, and to provide an improved understanding of rare-gas adsorption on metal surfaces in general, we performed DFT calculations using the all-electron, full-potential linearized augmented plane wave (FP-LAPW) method  for Xe adatoms on the Mg(0001), Al(111), Ti(0001), Cu(111), Pd(111), and Pt(111) surfaces. We employed two different exchange-correlation functionals, namely, the LDA  and the generalized gradient approximation (GGA) . The surfaces are treated by the supercell approach using the repeated slab geometries (five- and six-layer thick slabs separated by a vacuum region of 18 Å). To determine the potential-energy surface (PES) of Xe on the metal surfaces we chose six sites on the fcc(111) surface: on-top, bridge, fcc, hcp, the midpoint between on-top and fcc, and the midpoint between on-top and hcp (see inset of Fig. 1). For each site the height of the Xe atom and the position of the topmost two substrate layers are fully relaxed.

Our calculations show: $`(i)`$ The on-top site is energetically favored for all studied systems in the $`\sqrt{3}`$ structure. $`(ii)`$ Calculations for low Xe coverage, $`\mathrm{\Theta }_{\mathrm{Xe}}`$ $`=`$ $`1/4`$ and $`1/9`$, show that also in these cases Xe atoms prefer the on-top site (e.g., for Xe/Pd(111) and Xe/Pt(111) the on-top site is favored over the fcc site by $`20.59`$ meV and $`57.87`$ meV, respectively, at $`\mathrm{\Theta }_{\mathrm{Xe}}`$ $`=`$ $`1/9`$ using the LDA). Thus, lateral Xe–Xe interactions are not responsible for the on-top Xe site preference. $`(iii)`$ Spin-orbit coupling corrections were included for the valence-states using the second variational method ; this yields a change in the energy difference between on-top and fcc sites of $``$ 2 meV, and the geometrical parameters are unchanged. $`(iv)`$ The energy difference between the on-top and fcc sites is smaller in the GGA than in the LDA (e.g., for Xe/Pd(111) the on-top site is favorable by $`13.48`$ meV (GGA) and $`51.22`$ meV (LDA), while for Xe/Pt(111) the on-top site is favorable by $`4.80`$ meV (GGA) and $`49.09`$ meV (LDA)). Furthermore, the GGA predicts a weaker adsorption energy than LDA (e.g., $`E_{\mathrm{ad}}^{\mathrm{Xe}/\mathrm{Pd}(111)}`$ $`=`$ $`76`$ meV (GGA) and $`453`$ meV (LDA), $`E_{\mathrm{ad}}^{\mathrm{Xe}/\mathrm{Pt}(111)}`$ $`=`$ $`82`$ meV (GGA) and $`367`$ meV (LDA)). However, both functionals gives the same qualitative picture for the interaction between Xe atoms and metal surfaces. In view of these four points we limit our discussion in the following to the LDA results, neglecting spin-orbit coupling corrections for the valence states, and discussing only the $`\sqrt{3}`$ structure. All our results, including convergence tests, will be presented in detail in a forthcoming publication .

Figures 1a and 1b show respectively the relative binding energy (with respect to the on-top site geometry) and the adsorption induced work-function change for Xe on Pt(111). It can be seen that the on-top site is energetically favorable and Xe adsorption induces a decrease in the work-function (which is greater for the on-top site), in agreement with experiment. The adsorption energy, the relative energy difference for Xe in the on-top and fcc sites, as well as the work-function change for all the systems are summarized in Tab. I, where it can be seen that this same behavior is exhibited. For the cases where there are experimental values of the adsorption energy with which to compare (Xe/Cu, Xe/Pd, and Xe/Pt), the agreement between theory and experiment is quite good.

In Tab. I we also list the important structural data. The DFT-LDA bond lengths are about 10% shorter than those obtained by LEED , but in view of the fact that the adsorption energy is weak in physisorption systems and our theory does not include vibrational contributions, the sign and size of the deviation is as expected. The difference in bondlengths, however, for the Xe/Cu, Xe/Pd, and Xe/Pt systems, for which comparison is possible, are in excellent agreement between theory and LEED analyses. There is one deviation between the calculations and LEED analyses and that is in the direction of displacement of the atom below the Xe atom. The experimental values lie however within the given error margins. Particularly interesting is that the vertical distance between the Xe adatom and the topmost metal layer is smaller for the on-top site as compared to the fcc site for all the studied cases (for Xe/Pd it is almost equal). This is in contrast to the calculations of Ref. , and in contrast to what might be intuitively expected. We will come back to this point below.

Figures 2a, 2b, and 2c show the local density of states (LDOS) for Xe on Pt(111) for three distances of Xe above the surface. It can be seen that there is a broadening of the Xe states as the Xe adatom approaches the surface, which leads to a partial occupation of the previously unoccupied Xe $`6s`$\- and $`5d`$-states (mainly $`5d_{\mathrm{z}^2}`$-state), and a partial depopulation of the Xe $`5p`$-states (mainly the Xe $`5p_\mathrm{z}`$-state). The same behavior in the LDOS is identified for Xe on all the studied metal surfaces. We note that in Ref. , occupation of the Xe-$`6s`$ resonance was attributed to being the origin of the Fermi level LDOS which renders Xe visible on Ni(110) in scanning tunneling microscopy experiments. This is consisent with the present results.

We now turn to consider the change in electron density due to adsorption, i.e., the difference between the density of the interacting system, $`n^{\mathrm{Xe}/\mathrm{Pt}}`$, and the sum of the densities of the clean surface, $`n^{\mathrm{Pt}}`$, and a free Xe layer, $`n^{\mathrm{Xe}}`$. We find that a polarization of the Xe atom sets in when it is already far from the surface, where the negative end of the dipole points towards the surface, i.e., the electron density is enhanced closer to the metal surface (see Fig. 3, upper left). This is due to the general property that the potential in front of a metal is attractive for electrons; specifically, the exchange-correlation potential is more attractive on the metal side of the Xe atom than on the vacuum side. At this large distance where the Xe dipole moment starts to build up, the electrostatic and covalent contributions are small, if present at all. This behavior is consistent with the pioneering works of Lang  and Antoniewicz . A corresponding polarization occurs in the surface, which can be described as the image of the Xe dipole. The build-up of these dipoles happens simultaneously (and continuously with decreasing distance from the surface) and are related to the partial population and depopulation of the Xe states (cf. Fig. 2). In Fig. 3, the work-function change and dipole moment is shown as a function of distance, Z. For all Z, the values for the on-top site are greater and the variation with distance is smooth and continuous. From the electron density difference distributions at the equilibrium positions (Z=Zeq) depletions of charge are seen at the Xe atom (mainly $`5p_\mathrm{z}`$) and at the metal atom closest to Xe, i.e., mainly in the Pt $`d_{\mathrm{z}^2}`$-states, while an increase occurs at the surface, between these regions of depletion. Similar results are found for all the other studied transition metal surfaces.

The differences in the LDOS and $`\mathrm{\Delta }n(𝐫)`$ distributions between on-top and hollow sites described above, show that the Pauli repulsion and the attractive interaction is not the same at each site. In order to investigate this aspect in more detail, we calculated the binding energy of Xe on the metal surfaces as a function of vertical distance. The results for Xe/Pt are shown in Fig. 4 (left). At all distances above the equilibrium position, the on-top site has lower energy. From these results, we obtain Xe vibrational frequencies of $`E_{\mathrm{vib}}`$ $`=`$ $`3.79`$ meV (on-top) and $`4.17`$ meV (fcc). Reported experimental values are 3.70 meV and 3.80 meV,  showing excellent agreement with the calculated (on-top) value.

In Fig. 4 (right), we decomposed the binding energy curves into a repulsive and attractive potential using a standard empirical formula: $`E(Z)=Aexp(BZ)C(ZZ_0)^3`$ , where $`Z_0`$ is the position of the image plane. We note that the two right-most DFT-LDA points in Fig. 4 (left) were not included in the fit since DFT results are most reliable near the minimum in the potential well. It can be seen quite clearly that the Pauli repulsion is different for the two sites and is weakest for the on-top site. We also used other expressions for the repulsive and attractive terms, and the conclusion was always the same. We furthermore decomposed the DFT-total energy into kinetic, Coulomb, and exchange-correlation energies. The results suggest that the repulsion due to the kinetic energy is smaller for Xe in the on-top site. We find the same behavior as exhibited in Fig. 4 for all the rare-gas atom–metal systems investigated.

The reason why, that for Xe at the on-top site, the Pauli repulsion is weaker, the equilibrium distance closer to the surface, and the dipole moment greater, is explained as follows: On analyzing the reactivity index of the clean Pt surface , we find that the electronic character at the on-top region is donor-like and at the hollow region it is acceptor like. Thus, for a negative charge, at not too close distance (or for a dipole with the negative end pointing toward the surface), the on-top region can easily screen this perturbation by transferring electron density from the on-top region (i.e., from $`d_{z^2}`$ and $`p_z`$ orbitals) to the interstitial region. Therefore, at intermediate distances the Xe atom becomes polarized more strongly at the on-top geometry, because the screening charge at the metal can build up more efficiently. This is why the dipole is greater. Similarily, at close distance, when wavefunctions start to overlap and Pauli repulsion sets in, the substrate can reduce this repulsion more efficiently at the on-top site by transferring $`d_{z^2}`$ and $`p_z`$ electrons to $`s`$-states. Hence Xe can get closer to the surface.

In summary, from DFT calculations we determined that Xe adatoms on the free-electron-like, early and late transition metals, as well as noble metals, Mg(0001), Al(111), Ti(0001), Cu(111), Pd(111), and Pt(111), prefer low coordination on-top sites. The qualitative results are the same for LDA and GGA functionals. We find that the dominant mechanisms at play in these systems are polarization and a site-dependent Pauli repulsion which is weaker for the on-top site, thus stabilizing on-top adsorption. Our recent investigations for the smaller rare-gas atoms, e.g., Ar and Kr on Pd(111) exhibit the same behavior and basic mechanisms, and we anticipate that the present findings may also be generally valid for other rare-gas/metal systems, thus presenting a new picture of rare-gas adsorption, where the on-top site is the rule rather than the exception.