Study Group: Signature Schemes from Standard Assumptions

The latest study group, on signature schemes from standard assumptions, was given by Florian Böhl, who is currently visiting Bristol. He discussed three schemes from the (bilinear) Computational Diffie-Hellman assumption: the scheme by Waters from Eurocrypt '05, the scheme by Hohenberger and Waters from Eurocrypt '09 and finally a new scheme which is to appear at Eurocrypt '13. Theoretically, Digital Signature schemes are a weaker primitive than Public Key Encryption, as signatures are equivalent to one-way functions whereas PKE requires something stronger. On the other hand, it seems much more difficult to construct practical signature schemes as opposed to PKE schemes. The most efficient known signature schemes rely on "strong" assumptions, where the adversary only needs to break one instance of the system out of many possible instances. The schemes that Florian discussed are based on simpler assumptions, such as the standard (bilinear) Computational Diffie-Hellman assumption and the standard RSA assumption.

The security notions for signature schemes are slightly different than those of encryption schemes. Consider message indistinguishability of encryption schemes, where the adversary chooses two messages, gets the encryption of one of them and has to guess which message was encrypted. However, for signatures, the adversary sends in several messages and receives accompanying signatures. Finally, he needs to output a valid signature of a new message of his choosing. The only restraint on this message is that it was not queried before by the adversary, which means he has many options in choosing his challenge.

An important notion of security for digital signatures is Existential Unforgeability under Chosen Message Attack, which can be non-adaptive (EUF-naCMA) or adaptive (EUF-CMA). In the non-adaptive case, the adversary chooses q messages and sends them to the challenger. He then receives the public parameters and valid signatures for these q messages and has to output a fresh message with a valid signature for this message. In the adaptive case, the adversary receives the public parameters at the start and can adaptively query q messages one by one, receiving a valid signature every time. As in the non-adaptive case, he needs to output a fresh message with a valid signature.

It is possible to turn a non-adaptively secure scheme into an adaptively secure scheme using something known as a Chameleon Hash Function. A Chameleon Hash Function (CHF) is a special hash function that has a trapdoor which allows you to find collisions. Specifically, it takes a message and some randomness as input and if you are given a new message, the trapdoor allows you to find new randomness such that the CH of the first message and the first randomness is the same as that of the second message and second randomness. By signing the CH with the non-adaptive scheme, the challenger can generate signatures for q random CH's and then find the appropriate randomness for each of the adaptive queries of the adversary. The randomness must also be published as part of the signature to allow verification. An adversary breaking the new scheme must either break the collision-resistance of the CHF or give a forgery for the non-adaptive scheme.

At Eurocrypt '05, Waters presented an Identity-Based Encryption scheme with a security reduction to the decisional Bilinear Diffie-Hellman assumption. It is possible to construct a signature scheme from this Identity-Based Encryption scheme using a generic conversion (due to Boneh and Franklin). An IBE scheme is an encryption scheme where the public key is someone's identity (such as their email address for example) and a master secret key can be used to derive secret keys for each identity. To turn this into a signature scheme, one can view the message to be signed as an 'identity' and then give the associated secret key as the signature of the message. To verify the signature of a message, the verifier can encrypt a random value with the message (the public key in the IBE scheme) and then decrypt it using the signature (the associated secret key for this identity). The security of this signature scheme is equivalent to the security of the underlying IBE scheme, which is decisional BDH in Waters' scheme. However, Waters shows that it is possible to use the bilinear map to verify signatures deterministically, which results in a signature scheme with a security reduction to the weaker Computational Diffie-Hellman assumption.

It turns out that this scheme implicitly contains a Programmable Hash Function, a concept later formalized by Kiltz and Hofheinz (Crypto '08), which will be the topic of a study group in the near future. The PHF proposed by Waters has some adaptive properties and hence the scheme does not require the use of a CHF to be adaptively secure. However, this particular PHF is unfortunately not very efficient and therefore the resulting signature scheme is also not very efficient. In the scheme by Hohenberger and Waters from Crypto '09, they instead use a slightly weaker notion which is due to Boneh and Boyen, from their selectively-secure signature scheme. The security of the resulting scheme is based on the RSA assumption and the scheme is stateful, in the sense that the signer must maintain a state that counts the number of signatures issued. Hohenberger and Waters state that they believe that the statefulness of the scheme can be removed and that their scheme is a step towards realizing stateless signature schemes.

Consequently, the new paper that was discussed at the study group, which is to appear at Eurocrypt '13, will show how to convert such stateful schemes to efficient stateless schemes. They use a CHF and a 'weakly programmable hash function' as in the scheme by Hohenberger and Waters. In their work, they provide new and more efficient schemes, based on the RSA, bilinear CDH and SIS assumptions.