Computational Independence in the Design of Cryptographic Protocols

When an adversary aims to break or fabricate a cryptographic object with some unknown parameter it tries to collect/learn associated data from past or concurrent events. Such a learning effort can be neutralized if statistically independent observations are only available for the adversary. Though such clear-cut approach cannot be implemented in general, it can serve as a starting step for feasible (simplified) design and analysis of security protocols. Cost efficient realizations unavoidably introduce statistical dependence within and between protocol instances. Fortunately security guarantees remain intact in a computational environment even in such circumstances if at least some form “computational independence” can be attained.

Four types of independence relations between random variables will be considered: unpredictability (UP), computational independence (CI), statistical independence (SI) and functional independence (FI). Keeping statistical independence between instances of primitives and instances of protocols is a clear-cut approach for guaranteeing protection against harmful interactions in concurrent and multi-execution environment. However protection provided by statistical level of independence costs a lot, therefore several times it is used only as a tool in the beginning step of the analysis for reduction of the complexity of the analysis. Changing from SI to cost efficient computational independence brings into the picture the notion of CI, UP and FI. Our definitions for notions of CI, UP and FI will be introduced in the paper. UP essentially prevents attacks against correctness and privacy carried out via fabrication of valid cryptographic blocks and exploration of private data, respectively. CI as its name indicates provides the same independence guaranties under complexity constraint as SI does in unconditional case.

Our main technical result claims equivalence between unpredictability and computational independence for general non-binary random variables. This result can also be considered as an extension of the analogous classic result on pseudorandom generators, the equivalence of pseudo-randomness and unpredictability for ensembles of binary random variables. In our case uniformity of the underlying distributions also plays crucial role as we show that for general distributions such equivalence does not stand.

We explore useful relationships between independence notions under study:

In general CI is stronger property than UP, as the former implies the latter. We show separation result for notions CI and SI. We define CI of protocol instances and show relationships between the CI of protocol messages and the CI of corresponding protocol instances. Notion of functional independence (FI) provides the bridge to security notion by universal composability on one side and CI of protocol instances on the other side.

We are not aware of publication which mentions the notion of CI in the field of protocol analysis.

We underline that UP is a constructive property which can be directly associated to standard security properties of primitives. Our main example is that UP provides the bridge to EU-CMA standard-security of primitives as the latter is an important example for the weak version of the UP property. In this sense, we give a unified approach to the role of independence in the analysis and design of provably secure protocols.

Several examples help deeper understanding and serve as illustration for our notions and arguments.

The structure of the paper is the following. Section 2 presents the related works. In Section 3 we analyze the relationship between notions CI and SI as well as between CI and UP. Here we show that CI is stronger property than UP, in general, but under “plausible” assumption the two notions become equivalent. Section 4 presents several important applications for computational independence (CI), discussing both cryptographic primitives and protocols. Here we also show the relationship to the Universal Composition framework. In Section 5 we draw conclusions. In Appendix we give our notions for strong and weak unpredictability (UP), illustrated with several examples.

• II.    Related Works

A computational version of statistical independence appeared first in the classic paper of Yao [21] under notions of “effective conditional entropy” and “effective mutual information”. The aim was to define a computational counterpart of Shannon’s perfectly secure encryption.    The    notion    of    computational indistinguishability of two probability distributions (equivalently two random variables) is fundamental in the classic theory of standard secure cryptographic primitives. Interestingly  similar indistinguishability notion for independence/dependence of random variables has not been introduced until recently. Indeed, the only reference we found to it is rather fresh [8] (compared to the time of publication of [21]). The author of [8] after coining the name CI returned to Yao’s application for encryption security in [21]. In our paper we will use CI in different context both theoretically and practically. We embed this notion into the set of related notions mentioned above. Furthermore our application environment for CI is much wider than that of [8] as our aimed application environment is the design and analysis of provably secure protocols, in particular universally composable protocols [4], [5]. Such a setting where many protocol instances may run concurrently under adversarial coordination is obviously the richest one for potential dependence problems. Understandably, our examination is inherently related to Canetti’s universal composition framework [4], [5]. This framework has strong theoretical foundation and the corresponding analysis and design techniques have had wide application in the last decade [1-3], [6-7], [9-20]. Notions UP, CI and SI are defined for random variables, while notion FI is inherently related to the notion of UC-security of protocols.

• III.    Computational Independence

“Natural” definition of computational independence of two random variables is their computational indistinguishability (CI) from a pair of statistically independent random variables. One of the main points in this work is to underline the crucial role of CI in the design and analysis of cryptographic protocols.

Definition 1 (computational independence):

Computational indistinguishability of independence (computational independence, CI) means computational indistinguishability of a pair V1=(m1,m2) of random variables from a pair of random variables V =(M ,M ) , where M and M are statistically independent.

In the game of CI a distinguishing algorithm Z gets a sample v=(v ,v ) which is a realization of V or V₂ chosen by coin flipping result с . Algorithm Z successfully distinguishes V and V if P(Z(v)= c ) >  1/2+ e /2 for non-negligible e . If none of PPT algorithms is successful in the above game we say that random variables m and m are independent by CI.

For simplicity of presentation we consider the case when random variables m and M similarly random variables m and M have the same probability distribution (p.d.). Let the former be denoted by H(x) the latter by G(y) . In other words the marginal distributions of the two dimensional random vectors V and V are equal. We also introduce conditional probability distribution (c.p.d.) F(y|x)=P(m =y|m =x) . The main result of this chapter claims equivalence between CI and UP, where our main assumption will be that p.d-s G(y) and F(y|x) are computationally indistinguishable from uniform (for illustration see Fig. 1).

Fig.1. Assumption of Uniform Distributions

First we separate notions SI and CI.

Property 1: Random variables m and m are CI independent if 2 = sup_xVar(F(y|x), G(y)) is negligible, where mapping Var(.,.) stands for the statistical distance.

Proof : Using the definitions of CI and of statistical distance we get

P (Z(v1, v2) = с) = Ex [ j P (Z(x, y) = с | x) dF(y | x)]

y

= E x [ j P ( Z ( x , y ) = c | x ) dG ( y )] + ^y

E x [ j P ( Z ( x , y ) = с | x ) d ( F ( y | x ) - G ( y ))] ^y

< a + E_x [ J | dF ( y | x ) - dG ( y ) |] <  1/2 + 2 Я

y where a =P (Z (M1, M2) =c) =1/2.

In this chapter we examine the relationship between unpredictability (UP) and CI (our definition for UP is placed in the Appendix). First we separate these two notions by their strength.

Property 2: Set D of distinguishing algorithms in CI game is strictly larger than set P of predictors (F algorithms in Definition 5 in the Appendix).

Proof: | P | c | D | : predictor (F, 8 ) can be used to generate a distinguisher d: d(v)=1 if F(v₁)= 8 (v₂) , otherwise d(v)=0 . Note the number of

k kk          k21

V^1 ^ V 2 mappings (set P) is 2 2 while the number кд + k2

к + к      _Т,1                                T²

of V ^{1 2} ^ V mappings (set D) is 2      , where

|v₁|=k₁, |v₂|=k₂ and 8 is the identity mapping.

The next example illustrates the intuitive meaning of notion CI.

Example 1: Consider two instances I and I of a protocol where the only cryptographic primitive is EU-CMA secure digital signature, furthermore the instances use a common signature key. EU-CMA security prevents successful prediction of signatures in instance I from signatures in instance I and as digital signatures are the only cryptographic mappings, instance I is unpredictable from instance I and vice versa. In spite of this (weak) unpredictability, the two instances are not computationally independent, which were the case if I and I would use (statistically) independent signature keys. Indeed, a distinguishing algorithm being aware of the public verification algorithm could easily distinguish the case of a common key from the one with independent keys.

Consider now the case when instead of digital signature primitive message authentication (MAC) primitive is used. The question remains the same: can we distinguish the cases when a common key and when independent keys are used in the instances. Now there is no publicly available (efficient) verification algorithm. Assume PRF-CPA secure symmetric key encryption algorithm generates CBC-MAC with full block-length. Furthermore, we observe sets of MACs S 1 ={(m 11 , MAC k (m 11 )) ,..., (m 1n , MAC k m 1n ))} and

S2={(m21, MACk (m21)) ,..., (m2n, MACk m2n))} from instance I1 and I2 , respectively, where the messages are different with overwhelming probability. Clearly, if we used random function for encryption we were not able to decide about corresponding keys if k =k or not. Consequently this remains the case also for pseudorandom encryption, which implies that we identified an example for CI which is separated from SI.

Property 2 suggests that computational independence is strictly stronger than unpredictability, in general. In this chapter we show a condition under which UP implies CI. A restriction will be imposed on the corresponding distributions ( F ( y|x ) , G ( y ) ) . We also show an argument that in the general case of distributions CI is strictly stronger than UP.

For simplicity of notations first we will consider the case of identity mapping δ. The extension to the general case of δ is given subsequently.

Let the domain of random variable m₁ and m₂ be denoted by X and Y, respectively. Let H_Fx={y: F(y|x)>0} , i.e. set H_Fx c Y denotes the support of c.p.d. F ( y|x ) . Similarly H_G denotes the support of p.d. G. Obviously H_Fx c H_G c Y for all x.

Assumption 1: Assume that

• a)    c.p.d. F(y|x)=P(m = y|m =x) and p.d.

G(y)= P(m =y) are computationally indistinguishable from uniform distribution, respectively,

• b)    ratio | H | / | H | is non-negligible except for negligible set of x values.

Comments follow to Assumption 1:

to a): It is implicit in this assumption that p.d. G(y) can efficiently be sampled. Indeed, variable m2 is a protocol message or part of it, output of a known efficient mapping of constants and efficiently samplable random variables (typically coin flipping sequences).

to b) This assumption is a technical consequence of the standard definition of algorithmic indistinguishability of p.d-s, where the success of a distinguishing algorithm Z is equivalent to its non-negligible gain. When we want to inherit this gain by a predictor Z’ built on Z we need this assumption.

• Theorem 1:    Under Assumption 1 unpredictability (UP) implies computational independence (CI).

Note this claim resembles the classic theorem on the completeness of the next-bit test: “An ensemble of sequences of binary random variables is pseudorandom if and only if it is non-predictable.” Here pseudorandomness means computational indistinguishability of an efficiently generated series of binary random variables from a series of statistically independent uniformly distributed binary variables (in short from a coin flipping sequence). Prediction means prediction of the next bit within the series from the previous bits. In contrast we consider the algorithmic independence of non-binary random variables which may have different distributions, in general.

Proof of Theorem 1 : Assume the existence of a binary algorithm Z such that it is able to distinguish the pair of random variables from a pair with independent elements. (Z outputs 1 when it decides to V₁). We construct an algorithm Z’ such that it is able to predict with non-negligible probability. Algorithms have access to pub_inf which will not be explicit in the formulation below for simplicity of notations. According to Assumption 1/a we are allowed to use (genuine) uniform p.d-s for F(y|x) and G(y) in the calculations below.

The predictor is successful if its output random variable      has      distribution      computationally indistinguishable from F (y|x) (which by our assumption is uniform over H ). Consider the following prediction algorithm:

Algorithm 1:

• 1.    Z’ gets sample x as input from X.

• 2.    Z’ choses sample y*: y* ^ r H G .

• 3.    Z’ runs Z with input (x, y*) :

if Z(x,y*)=1then Z’ outputs y*, otherwise Z’ outputs y': y ^ _r H G .

Let P denote the probability of event E that the output of Z’ falls into set H_F,x . Note that as y* and y’ are uniformly random over H_G , furthermore H_{F x} c H_G , therefore distribution of the output of Z’ conditioned on event E is uniform. It remains to prove that P is non-negligible. According to Algorithm 1

P s = P ( { Z ( X , y *) = 1} П { y * G H F , , } )

• + P ({Z (X, y *) = 0} n {y' G Hf ,X})

For the first term on the RHS of (1) we get

P ( {Z (X, y *) = 1} | {y * G H x } ) P ( y * G h ) > pq, ,x                            ,xx

| H |

Qx = P ( y * G HF, X ) =

,

Similar lower bound can

be obtained for the second term in (1)

P ( Z (x , y *) = 0 ) P ( y' G HF,X) > p 2 qx, and this leads to lower bound

^Ps >  q_X ⁽ p 1 + p ₂) >  q_X ⁽¹ + e ) = q_X + q_Xe

If distinguisher Z is not available then Ps=qx.

Therefore if q is non-negligible then predictor Z’ has non-negligible gain q_x e .

• Theorem 2:    In the general case of distributions over pair of random variables V =(m ,m ) unpredictability does not imply computational independence.

Proof : Consider the best algorithm Z* for distinguishing V and V . Algorithm Z* decides on V over subset of samples S={z: P_Vi(z) > PV₂(z), z g XxY} . Note Z* is insensitive to the relative magnitude (ratio P_V (z)/P_V (z) or difference P_V (z) - P_V (z) ) of probabilities. In other words Z* carries no information about those relative values. Recall the task for predictor Z’ is to output sample y with p.d. F(y|x) . When we would like to generate a successful prediction algorithm Z’ by reducing the task of prediction to a successful distinguishing algorithm Z*, in the general case of distributions we would fail. Indeed, as Z* is insensitive in the above mentioned meaning we cannot expect that the output of Z’ will have the wanted distribution. Note that the assumed uniformity properties of distributions in Theorem 1 are immune to this insensitivity property. Furthermore, though the best distinguisher Z* is not polynomial in general, the above argument remains valid for our purposes in cases of distributions with polynomial size of support.

• A. Extension to general mapping δ and to more than two variables

Recall the examination in the previous chapter refers to the special case when δ is the identity mapping (i.e. we would like to predicate the whole “block” of m2 ). However according to Definition 5 for unpredictability of m from m we require that no part of m can be predicted and in general the same must be true for any efficient, deterministic binary mapping of m .

Property 3:  Computational independence implies unpredictability.

Proof : By contradiction assume there exists an efficient, deterministic binary mapping 5 of m₂ such that ^ (m₂)is successfully predictable from m with prediction algorithm Z ₅ . Distinguisher algorithm Z’ in the computational independence game gets input v=(vi,v₂) and runs algorithm Z ₅ with input v_t . Algorithm Z’ outputs 1 (i.e. decides that pair (m₁,m₂) is its input) if Z ₅ predicates v₂ successfully.

The extension of Assumption 1 and Theorem 1 to general mapping 5 is straightforward.

Lemma 1: Assumption 1 implies Assumption 1’ for the general case of 5 , where

Assumption 1’ : Collect polynomial many random samples from distribution G(y) into set W and generate set W'={ δ (y) : y ∈ W } . We assume that probability

P( δ (m2) ∈ W' | m =x) is non-negligible possibly except for a negligible set of x values.

Proof :  Note, that event {m ∈ W} on condition

{m =x} implies event  {δ(m2) ∈ W' } on the same condition for arbitrary x.

The proof of Theorem 1 can be repeated with changing distribution G(y) to the distribution of random variable δ (m ) (in Algorithm 1).

Definition 1 of CI is given for pairs of random variables. The extension to joint independence of several random variables is straightforward: we consider the computational indistinguishability of a vector of the corresponding vector of random variables V =(m ,...,m ) from vector V =(M ,...,M ) where coordinate variables M ,...,M are jointly statistically independent.

Example 2: For pseudorandom primitives CI property is straightforward by their definition. Essentially these definitions directly provide CI property (which in turn implies unpredictability). Recall in those definitions uniformity of the underlying random variables is part of the definition (or implicit in them). Pseudorandom security for primitives is the strongest guarantee within computational framework. In contrast for less strong definitions like EU-CMA, semantic security or nonmalleability the definition is unpredictability-oriented and as shown above we arrive to CI properties under restrictions on (or better to say by specifying) underlying p.d-s.

• IV.    Applications

In this section we present several applications for the notion of computational independence both in the field of secure cryptographic primitives and protocols. Our main goal is to protect a protocol instance from the adversary attacking in a concurrent environment. The point is that the target instance should be computationally independent from all other instances running in the same environment. Such independence can be established via proper unpredictability properties at the level of applied cryptographic primitives. CI level of independence can be achieved based on equivalence between UP and CI properties like the one stated in Theorem 1.

• A.    CI and the cryptographic primitives

The main observation in this sub-section is that by our definition of UP the EU-CMA standard-security property of primitives becomes an example for the weak version of the UP property. Subsequently, further important examples will also be shown for unpredictability.

EU-CMA security

Consider a standard secure cryptographic primitive given by mapping f(k,u) , where argument k and u corresponds to key and message, respectively. The adversary has oracle access to algorithm f(K,.) with unknown key K and is tasked with forging output f(K,u) for a new message u:

EU-CMA security guaranties that the adversary will not be successful if for any poly size set {f(K,u1),...,f(K,uN)} requested for arbitrarily chosen message set U={u ,...,u } , variable m =f(K,u) is unpredictable from m1 = (f(K,u1),...,f(K,uN)) for any u such that u ≠ u , i=1,...,n .

Note EU-CMA security for a primitive f is an example for (weak) unpredictability: we require (weak) unpredictability for any pair of random variables (m , m ) , where random variable m is learned via accessing the corresponding oracle and m is an output of f for a fresh input.

For example when the adversary wishes to fabricate a valid digital signature or authentication code without knowing the corresponding secret key, m 1 corresponds to signatures (MAC values) obtained from the oracle for messages sent in the requests, m will be the signature (MAC value) for a new message m’.

Obviously, if protocol instances running concurrently use an EU-CMA secure primitive f as a common primitive (i.e. with the same secret key X) then prediction-based attack against a target instance can be neutralized if different instances are coordinated in choosing inputs to f from disjoint subsets. Recall a corresponding technique is used in implementation of the JUC approach [5], where concurrent instances of the same protocol have a common module implementing primitive f.

In the more general GUC approach [7], the target instance and any other instances have access to a common public (global) variable. In this case coordination over the input space cannot be established in general (think on the case when one of the protocols is controlled by an adversary). With respect to predictability in GUC scenario the two extreme cases are the following:

In the first case anybody can code with a public algorithm but only one party can decode (e.g. public key encryption). Predictability is obvious and cannot be eliminated, therefore in this case we have to change from globally predictable instances to locally statistically independent ones (e.g. independent encryption keys per instance).

In the other case of primitives an honest party can access the secret key but anybody can verify with a public algorithm. For such primitives (weak) UP can be maintained by requiring EU-CMA-security. The known example is the digital signature. When a party controlling a signature key is a party in different instances of even different protocols he is able to ensure coordination of signatures issued by himself in spite of global (i.e. multiprotocol and multi-instance) use of the same instance of signature primitive. It seems plausible that digital signature is the only primitive which provides global (weak) UP capability.

Semantically secure encryption

As we already mentioned, formulation of Definition 5 has resemblance to the standard definition of semantic security of public key encryption with the following cast of roles: random variables m and m correspond to a ciphertext and corresponding cleartext, respectively, where mapping δ models the partial information on the clear-text.

Non-malleable encryption

It is an example for (weak) unpredictability. The cast of roles is the following: m =(c,M) where c is a ciphertext for message u, M is the data collected, and furthermore m₂ is a ciphertext for message u’ such that u and u’ are in relation R (R can be thought as included into pub_inf ).

Pseudorandom primitives

Standard secure pseudorandom primitives are PRG-, PRF- or PRP-based. Such primitives, in principle, can be used for key stream generation, encryption, digital signature or MAC. These are clear examples for unpredictability. For instance, by definition a PRP-secure symmetric key block encryption is computationally indistinguishable from random permutation, which implies that different messages are encrypted, essentially, into statistically independent ciphertexts chosen from the total space of ciphertexts (here “essentially” means that until we use an instance of the encryptor for at most polynomial number of messages the restriction by invertibility requirement is negligible).

• B.    CI of protocol instances

An instance is the concatenation of its component protocol messages. Let this random variable be denoted by I(v ,...,v ) where v ,...,v are the random state variables of the protocol. Shortly we will refer to random variable I as the transcript of the instance. UP, CI, SI type of independence of instance can be considered between protocol messages or parts of them or between transcripts of different instances.

First we recall the natural definition for the statistical independence of protocol instances.

Definition 2 (SI of protocol instances): Protocol instances are statistically independent (SI) if their transcripts are statistically independent.

Property 4: Protocol instances are statistically independent iff their random state variables are statistically independent.

Property 5: SI between pairs of messages of different protocol instances does not imply SI of the instances (in general).

Proof : Consider two instances I and I . Let instance I consist of two messages U and V and instance I of a single message W, where U, V, W are binary random variables with equal length. Let U and W be independent, furthermore V=U+W (mod 2). In this example messages of I are (pairwise) independent from the message of I butI and I are dependent.

According to Property 4 protocol instances become statistically dependent if some of their random state variables are statistically dependent. In the set of random state variables we find local coin flipping sequences and variables dependent between different instances. The most characteristic and practically most interesting dependence is caused by subroutines shared by different instances (for example, a common signature module). In this case dependence means that some state variables are equal. The task is that in spite of statistical dependence CI should be maintained between instances.

Definition 3 (CI for protocol instances): Protocol instances are computationally independent if their transcripts are computationally independent.

Property 6: SI of protocol instances implies CI of the instances.

Proof: Straightforward.

Property 7: CI between pairs of protocol messages of different protocol instances does not imply CI of the instances (in general).

Proof: The proof of Property 5 can be repeated. Indeed U and W as well as V(=U+W) and W are (pairwise) CI (as they are (pairwise) SI), however U+V (=W) and W are clearly not CI.

When we want to change from costly SI instances to less costly but statistically dependent ones we have to ensure their CI property. The corresponding base composition rule is the following:

Composition of CI variables: Assume a series of random variables X(z) = X (z ),...,X (z ) are computationally indistinguishable from series Y=Y ,...,Y , where X (z ) is an efficient random mapping of random variable z_i, i=1,...,n . Assume furthermore that series of random variables z=z ,...,z are computationally indistinguishable from series w=w ,...,w . It is not hard to see by standard reduction technique) that X(w)=X₁(w₁),...,X_n (w_n) will also be computationally indistinguishable from Y. If Y is a series of SI instances then X(z) is a series CI instances. Similarly if z is a series of SI instances then w is a series CI instances of random variables. This way by the above rule we embed a series of CI variables into a series if CI variables.

This rule of composition fits naturally to the following scenario. Let X stand for a series of different instances from a protocol, where X (z ) corresponds to the transcript of the i-th instance. Let z and w correspond to the output of a cryptographic primitive by the ideal functionality and by realization, respectively. Series Y is the ideal realization with statistically independent states per protocol instance. In such scenario X(w) is the realization of Y with computationally independent realized instances where those instances use computationally independent outputs of the cryptographic primitive.

Composition of CI protocol instances: Composability of instances of protocols means that if we know/prove that a single instance of a protocol (the stand alone case) securely implements the task then the same is true for arbitrary many concurrent instances of the protocol. The main technical tool for proving such statement is the standard hybrid argument which assumes statistically independent instances. This is the way also in the Canetti’s UC framework where the composition theorem [4] is proved for the generalized scenario where concurrent composition is carried out at the level of subroutines of a main protocol (in the hybrid protocol model). This is the first step of design and analysis. In the second step we change to less costly realization with computationally only independent instances.

In a typical example while in the ideal case cryptographic keys are independent (fresh) in different instances running between the same set of parties, in real implementation it is typical that the same keys are used in different instances of the same protocol. This way (statistical) dependence arises among such protocol instances induced by the (statistical) dependence of instances of primitives. However by careful selection and use of those primitives the protocol instances may remain computationally independent and the security guaranties remain intact. “Carefulness” means the unpredictability property for the primitives. This way though statistical dependence arises between instances it will not be of help for an adversary looking for harmful interactions between the instances if the implementation guarantees computational independence.

Intuitively, computational independence of the target instance and all other instances is equivalent to the requirement that even with adaptive access to concurrent instances the task of breaking the target instance remains hard for the adversary. An adversary is successful against a protocol realization if it is able to break privacy or correctness guaranties. In case of computationally dependent concurrent instances the adversary tries to exploit this dependence. Our point here is that this intuition is grounded as by definition a set of protocol instances with (mutually) computational independence property is equivalent to an “associated” set with (mutually) statistically independent elements. Here “associated” means replacing statistically dependent state variables with independent ones. In other words the standard hybrid argument can directly be applied to concurrent protocol instances with CI property. This means that composition of statistically dependent but computationally independent instances is a one step action.

• C.    Dependence models in UC

Three dependence models are defined in UC between concurrent protocol instances which are base UC [4], JUC (Joint-state UC) [5] and GUC (Global-state UC) [7].

In base UC in the real system the target instance has no common state variable with any other instances. In base UC statistical independence of concurrent instances is the result of the so-called “subroutine respecting”, the statistical independence of inputs to different instances as well as the statistical independence of local random variables at different instances. Property of “subroutine respecting” means that different instances do not communicate with each other (directly or via a common module). The result is that in this base model different instances cannot have any dependent state variable (at any step of their run). It follows that the target instance is statistically independent (SI) from all other instances in the environment. Computational independence (CI) provides the same independence guaranties under complexity constraint as SI in unconditional case. For example protocol instances can securely be composed parallel in case of CI as in case of SI.

In JUC the target instance and instances from the same protocol share a common variable which implies their statistical dependence [5]. Computational independence of such instances can be ensured under UP assumptions on the applied primitives. Functional independence (FI) is straightforward link to the UC analysis of protocols. Instead of random variables like in case of UP, CI and SI it is defined for functioning protocol instances, where a need for independence guarantee arises both for outputs an also for the series of protocol messages. Accordingly FI is related both to (UC-) secure emulation and also to harmful interactions between concurrently running instances.

In GUC the target instance and any other instances have access to a common globally accessible variable [7]. In this case computational independence is much harder to establish.

• D.    Functional independence of protocol instances

Protocols can be considered as complex primitives, with special feature that they are executed via the interaction of at least two parties and therefore details of the computation of protocol outputs can also be seen and can potentially be attacked by an adversary. Accordingly both the series of protocol messages and the input/output messages has to be included into a random variable which represents the run of an instance of the protocol. Recall such a random variable corresponds to the information seen by the distinguishing environment at the global interface in the UC system model with dummy adversary [4]. We defined the UP, CI and SI type of independence of instances as the independence of their transcripts where the aim is reduction of the complexity of the analysis to that of a single instance. The second step is the realization with CI only instances. By the complex notion of functional independence (FI) we want to cover this two step approach by one notion.

The base scenario is the following: consider two sets of concurrent instances S1={I ,...,I } , S2={J ,...,J } , where in set S the instances are in SI relationship, while in set S they are statistically dependent. The interface between S ( S ) and the distinguisher corresponds to the standard global interface of the UC framework, where the instances of the sets are bunched into one virtual instance S(1) (S(2)) the same way as by the multi-session extension in Joint State UC approach (informally, it is a parallel-to-serial converter followed by its inverse, a serial-to-parallel one on the level of input/output packets to/from instances).

Definition 4 (FI for protocol instances): Sets S1 and S2 of protocol instances are functionally independent if multi-session extensions   S(2)  is computationally indistinguishable from extension   S(1)   by the distinguishing environment at the global interface.

Obviously functional independence is more comprehensive property than CI, in general. Indeed, a protocol containing a protocol message “A→B: Output secret_key” might have been implemented with concurrent CI instances it will not provide FI, when S1 is a set of ideal instances.

Property 8: Definition 4 of functional independence for sets S and S of instances of a protocol reduces to

• a)    stand-alone analysis of secure realization if elements of S and S are SI instances of the corresponding ideal protocol and instances of a realization with statistically dependent state variables, respectively,

• b)    Computational independence if elements of S and S are instances of a realization with statistically independent and dependent state variables, respectively.

Example 3: Consider the special case when only one type of primitives is used by the protocol. In such cases CI between protocol instances of the given protocol can be reduced to the CI between instances of the primitives.

Assume a protocol which uses a single type of cryptographic primitive, a digital signature primitive. Furthermore consider the common state scenario, i.e. different instances of the protocol share a common signature key, therefore they become statistically dependent.

In the first step the elements in S1 and S2 are (statistically independent) instances of the corresponding ideal protocol and SI instances of the protocol (via statistically independent signature keys), respectively. This first step is equivalent to the stand alone analysis, which is the test for UC secure emulation of the ideal functionality. As it is well known EU-CMA secure signature primitive is sufficient for reaching base UC security [4] (of course only if the hybrid protocol which is hybrid in ideal signature primitive is secure, e.g. it does not contain “catastrophic” protocol message like “A→B: Output secret_key”).

In the second step S '=S and S'contains instances with common signature key. The distinguisher is successful if it can exploit the statistical dependence between digital signatures in different instances within set S'. Intuitively, the only way for such success is prediction of digital signature with non-negligible probability. Here we can use once again the EU-CMA property to foil such prediction attack.

Note EU-CMA is the general security requirement in case of instance dependence caused by shared subroutines. Indeed, two security measures have to be taken in case of shared subroutines. First disjoint (sub)spaces of inputs to the common module has to be maintained by different subroutines to avoid trivial adversarial interactions. Secondly successful forging has to be prevented. As we saw in Section 3 UP property induced by EU-CMA implies also CI according to Theorem 1.

• V.    Conclusions

Unpredictability (UP, Definition 5) guaranties prevent attacks against correctness and privacy carried out via fabrication of valid cryptographic blocks and exploration of private data, respectively. Unpredictability-based standard secure primitives support achievement of computational independence (CI, Definition 1) within and between protocol instances via equivalence result in Theorem 1. Obvious fact that statistical independence (SI) of protocol instances provides the strongest guarantee against interaction attacks. By the equivalence of CI to statistical independence (SI) within an environment of efficient algorithms we arrive to a chain of equivalence relations between independence properties (UP ≈ CI ≈ SI) which provides the unified fundament for equivalently secure but cost efficient realizations. Computational uniformity of the corresponding distributions is crucial assumption in UP ≈ CI claim.