Security parameter

Theorem 12 Let Abe a Subset-Cover revocation algorithm where the key assignment satisfies the key-indistinguishability property (Definition 9) and where E and F satisfy the above requirements. Then A is secure in the sense of Definition 11 with security parameter (5 < ei - - 2mw e2 + wsf), where w is the total number of subsets in the scheme and m is the maximum size of a cover. 

As mentioned in Section 2.3, the length of the instances of cryptologic problems is determined by so-called security parameters. Such parameters are represented in unary representation whenever they are input to an algorithm. For this, T denotes the unary representation of k e N. ... 

For a function /with integer inputs and integer outputs, an algorithm is said to compute/in unary iff it is a normal algorithm (i.e., not restricted to unary representation in its own computations) that expects each input in unary and computes the result in unary. For instance, if / has two inputs k and algorithm computes l / > ) from ( 1 1 °). This notation is used for transformations of security parameters. 

Related decisions are where one represents security parameters (see Section 5.2.4, Initialization ), how active attacks on honest users are modeled (Section 5.4.2), and the formalization of availability of service (Section 5.2.7). 

More parameters I considered including the security parameters in the inputs to initialization. This would enable individual users to control their own security, and one could use different security parameters in different initializations in the same... 

At present, however, the security parameters are regarded as internal details of the systems and represented in the initial states of each entity. The prevailing argument was The goal is to define general notions like a scheme Scheme fulfils a requirement Req computationally in the parameter k where both Scheme and Req are variables. This means that a sequence of systems Sys derived from Scheme fulfils a sequence of requirements Reqi. If k is a distinguished part of the entities, it is easy to define Sys/ formally. If k were an input parameter, it would formally be a parameter of the honest users and not of the system. This is not too bad, because a formal representation of honest users is needed anyway. However, one has to be able to talk about an honest user with parameter k, as far as a certain requirement is concerned. This seems difficult if k is one of many parameters and there can be different k s in different initializations. 

If the security parameters were included, they could collectively be called par, with a domain Pars, because they have no special meaning in a pure service specification. Anyway, it may be usefirl to include such a parameter par on whose value at least the minimal requirements do not depend, to provide for extensions of initialization necessitated by additional transactions. For the same reason as with the message bound N, all the users participating in initialization would have to input the same value par, and effectiveness of initialization would be guaranteed whenever they do this. This extension is omitted for brevity in the following. 

Finally, one could use a special operator, such as SOON, which is to be interpreted in dependence on the security parameters or one could use two different models of time inside the system and at the interface, so that the relation between these two notions is what depends on the parameters. 

A system is an instantiation of a scheme with certain system parameters. These are the sets of identities, Id, Id, Mq, as mentioned in Section 5.2.5, and additional security parameters. Given a scheme and the system parameters, the instantiation is... 

Suitable classes of very small functions are those where the probability decreases superpolynomially or exponentially in one of the security parameters, say k. However, one must take care with the remaining system parameters. In the order of increasing security, one can leave them constant while k tends to infinity, or let them grow at most polynomially with k, or universally quantify over them after the quantifier over k. Moreover, some requirements may only be fulfilled if more than one security parameter tends to infinity. Examples can be seen in later chapters. 

Computational security. For computational security, the quantifier over the attacker strategies is restricted toAe PPA n Attacker class(Scheme, Req), where PPA denotes the class of probabilistic polynomial-time interactive algorithms. In this case, one can at most allow other system parameters to grow polynomially with the security parameters under consideration, and one usually requires superpolynomially small error probabilities only. 

Each existing scheme is based on a construction for signing one message block. However, the block size usually depends on a security parameter hence these subprotocols are not signature schemes for a certain given message space in the sense of Chapter 5 (cf. Section 9.1). 

The bank is the stronger partner in several ways. It can select the signature schemes and security parameters and thus provide for its own security. Moreover, it can inform itself about how trustworthy the cryptologic assumption is, both initially and while the scheme is in use, whereas many clients will already be deterred by the name of a factoring or discrete-logarithm assumption. 

Security parameters. As some requirements on a fail-stop signature scheme have to be fulfilled information-theoretically and others only computationally, it is natural to consider two security parameters. They are called a and k, where a measures the information-theoretic security and k the computational security. The primary role of cr is that the error probability in the fail-back requirement of the signer on disputes decreases exponentially with a. In other words, a determines the probability that the signer is cheated with unprovable forgeries. The primary role of k is to ensure the correctness of broken , i.e., the larger k is, the harder it should be to compute valid proofs of forgeries (and thus forgeries in the first place). 

As usual, the security parameters are represented in unary when they are inputs to algorithms. 

As a two-party protocol does not need identities internally, the only input parameters of A and B are the security parameters and the message bound. When the parameters k, a, and N are clear from the context, they are abbreviated as... 

Neither the public key nor the security parameters are inputs to sign, although they are known to the entity. This is without loss of generality If these values are needed for signing, they can be included in skjemp. Similarly, the security parameters will not be inputs wherever pk is, because they can be included in pk. However, they will be inputs to all attacker algorithms, because otherwise, they would have to be included in pk. 

PB,pati o dKeys) < 2, where [Pg.176]

As unforgeability will be a consequence of the security for both the signer and the risk bearers, both security parameters, k and CT, may have to tend to infinity. The definition of the precise relation between them corresponds to the following theorem it can be generalized. 

The definition assumes that one party has to generate a value K (usually some sort of key — in the present application the prekey) with a certain probability distribution Corr (for correct ) and needs a generation algorithm gen for this task, and another party wants to be convinced that K is an element of a set Good. The first party is called the prover, the second party the verifier. More precisely, both the distribution and the set are parametrized with security parameters, and there is a precondition that all values generated with the correct distribution are elements of Good. 

Two security parameters have been used here. Usually, there is only one (or even none — then the security is measured as a function of the length of the input K exclusively), and strictly exponential decrease of the error probability in the soundness is not required. In the present application, however, it is needed. Anyway, most existing zero-knowledge proof schemes are repetitions of one basic round, and the error probability decreases exponentially with the number of rounds. Hence the number of such rounds would be a linear function of a. 

One could generalize this aspect further by using new security parameters for the zero-knowledge proof scheme, instead of the indices to the family of distributions. However, one must then be careful with the relation between these parameters when they all tend to infinity. 

Moreover, it does not seem to be required anywhere else that the verifier and the observer need time pol)momial in the security parameters only, because it is unusual to regard K as a. value that may be internal to a larger system, as it is needed here. 

AllFam = (Allj f j fj is a family of sets, called the family of all acceptable prekeys, and all jest decides membership in this family in time polynomial in the security parameters alone. Hence all jest is an algorithm... 

The outputs of gertg are written (prek, aux). The first output, prefe, is called a prekey the second output, aux, is only needed to convince the signer s entity of the correctness of prek in the zero-knowledge proof. Note that the inputs to geng are only the two security parameters par = ( 1 , 1 ), and not the message bound N. 

Moreover, standard ordinary digital signature schemes have only one security parameter. This can be realized by choosing k= a. Finally, the algorithms prove and verify are not needed they are simply omitted in the construction. 

A probabilistic polynomial-time algorithm gen, the group-generation algorithm, that, on input 1 with k e IN (the security parameter), outputs a prime q and a value desc (representing the description of a group Hq desc of order q). 

A function len N N, called the length function (denoting the length of the hash values in terms of the security parameter), and a polynomial-time algorithm that computes len in unary. 

---