Cryptologic assumption

The main underlying cryptologic assumption is therefore that factoring large integers is infeasible. Concrete versions have later been called the factoring assumption (see Section 8.4).. To this day, it has remained one of the two most important assumptions to base asymmetric cryptologic schemes on. 

Anyway, one should be very carefiil with new cryptologic assumptions Nowadays, the only criterion for their trustworthiness is how intensively they have been examined. Thus, roughly speaking, among those schemes that have not been broken, the oldest ones are most recommendable for practical use. 

There are concrete cryptologic assumptions, such as the factoring assumption, and more general abstract ones, such as a one-way function exists . 

Ever since the invention of digital signature schemes, it had been accepted that signers can only be secure in the computational sense and on cryptologic assumptions (see [DiHe76] and Section 2.3). One purpose of this work is to show that this need not be so, and to present several alternatives, in particular fail-stop signature schemes. 

Moreover, the fail-stop property will only be used with two specific degrees of security low is on a cryptologic assumption and high information-theoretically . In principle, other combinations are also possible, for instance that low needs an upper bound on the number of attackers and high means that more attackers are tolerated. 

The main variations are in the number of risk bearers and how the risk bearers participate in initialization, and in the number of recipients and the consequences on testing signatures. Furthermore, the existing schemes vary in the message space, the cryptologic assumption that the correctness of broken relies on, and in efficiency. 

The situation with messages spaces, cryptologic assumptions, and efficiency is similar to that with fail-stop signature schemes. 

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. 

Note that this argument is more about liberty and psychology than about computer science One might say that the security for the bank is so important that any cryptologic assumption that a bank can trust ought to be trustworthy enough for anybody else, too. First, however, there is the undefined word can Why should someone else be convinced that an assumption can be trasted just because a bank does trust it And why should they even be forced to trust... 

The bank is the party that can stop the system. Hence there is a kind of external fail-stop property if the bank is the only party whose security is based on a cryptologic assumption If anyone breaks the assumption, the only party that can... 

Regarding two different acceptable signatures on the same message (and for the same public key) as a proof that the scheme has been broken is sound because it was assumed that the signer herself can compute only one acceptable signature, unless she breaks the cryptologic assumption. 

A scheme that does not need tree authentication is presented in [Pfit94]. This leads to very short signatures, but it has computational disadvantages. Furthermore, it relies on stronger cryptologic assumptions than the other schemes. 

Note that only dual security has been achieved, and not a fail-stop property The court s entity cannot distinguish the situation where an attacker shows a random number s, claiming it were an invisible signature, and the signer disavows s , from the situation where the cryptologic assumption has been broken. Hence the court s result is acc = FALSE in both cases, never acc = broken . 

The properties of the following two constructions were already mentioned in Section 6.1.2, Number of Risk Bearers and Complexity of Initialization and Cryptologic Assumptions and Efficiency . Both constructions are general, i.e., they can be applied to arbitrary schemes. More efficient constructions are possible in special cases see Section 7.5.2, Special Versions , and Remark 9.16. (It is not even necessary that schemes with many risk bearers are constructed from schemes with one risk bearer at all, although all existing constructions are.)... 

The main addition in the newer references is a property called fairness. Roughly, it means that if the protocol is stopped, the attackers and the honest participants have approximately the same amount of information about what the result would have been. This property is not needed in the present application. Furthermore, the newer references do not have the property called special protection for the signer below. Hence [ChDG88] is used in the following. It may, however, be possible to add that property to newer protocols and thus to obtain protocols relying on weaker cryptologic assumptions. 

The Jacobi symbol is interesting because it can be computed efficiently for any pair of numbers, by use of the so-called law of quadratic reciprocity. Actually, one would often be more interested in deciding quadratic residuosity, but no probabilistic polynomial-time algorithm for that is known, unless the prime factors of n are additional inputs. (A cryptologic assumption that deciding quadratic residuosity is infeasible has been used several times in the literature, e.g., in the... 

The chapter concentrates on efficient schemes where a whole message block is signed at once. Constructions with bit-by-bit signing are not presented they were all mentioned in Section 6.1.2, Cryptologic Assumptions and Efficiency . 

This is a slightly simplified comparison, because k is not directly comparable between schemes relying on different cryptologic assumption. However, the two schemes just mentioned do rely on the same assumption, and it was shown in Section 9.5 that with choices of security parameters that seem reasonable at present, the secret keys in the constructions based on the factoring assumption are longer. 

---