Cryptography Reference
In-Depth Information
Then, we mention the size of the signature. In the original scheme [22], r is a
“small” number. However, at a viewpoint of provable security, we estimate that
the length of the random salt r is required at least log( q s ( q H + q s ))-bits. This is
about 90-bits.
5 Extension for HFEV Signature Scheme
The HFEV function is presented by Kipnis et al. [16] and is generated from the
combination of HFE and UOV. The HFEV function uses a variant of the map
F HFE such that it has additional vinegar variables, and its coecients b i and c
are a first degree function and a quadratic function on the vinegar variables,
respectively. Signatures of this scheme are not uniformly distributed, because of
the same reason both of the UOV and of the HFE signature schemes.
By combining the approaches for UOV in Section 4.1 and for HFE in Sec-
tion 4.2, the HFEV signature scheme can be also modified. In short, the modified
signing algorithm first fixes a set of vinegar variables and then computes a preim-
age by the same way to the modified HFE scheme in Section 4.2. Assuming
that the HFEV function generator is secure, we can also prove the EUF-CMA
of the modified scheme as Theorem 2. Due to the combination of the approaches
for HFE and UOV, the signatures are also uniformly distributed. The details of
the modified HFEV scheme is described in Appendix B.
6 Conclusions
We analyzed distribution of signatures of the UOV and the HFE signature
schemes, and suggested that it might be dicult to sample from the distri-
bution without knowledge of trapdoor. It implies that a usual security proof
of FDH-like schemes cannot directly apply to that of the UOV and the HFE
schemes. Moreover, we showed that the UOV and the HFE signature schemes
can be simply modified into ones achieving the EUF-CMA without changing the
underlying trapdoor functions.
References
1. Bellare, M., Rogaway, P.: Random Oracles are Practical: A Paradigm for Design-
ing Ecient Protocols. In: ACM Conference on Computer and Communications
Security, pp. 62-73 (1993)
2. Bellare, M., Rogaway, P.: The Exact Security of Digital Signatures - How to Sign
with RSA and Rabin. In: Maurer [21], pp. 399-416
3. Bernstein, D.J., Buchmann, J., Dahmen, E.: Post-Quantum Cryptography.
Springer, Heidelberg (2009)
4. Bogdanov, A., Eisenbarth, T., Rupp, A., Wolf, C.: Time-Area Optimized Public-
Key Engines: Cryptosystems as Replacement for Elliptic Curves? In: Oswald, E., Ro-
hatgi, P. (eds.) CHES 2008. LNCS, vol. 5154, pp. 45-61. Springer, Heidelberg (2008)
5. Braeken, A., Wolf, C., Preneel, B.: A Study of the Security of Unbalanced Oil and
Vinegar Signature Schemes. In: Menezes, A. (ed.) CT-RSA 2005. LNCS, vol. 3376,
pp. 29-43. Springer, Heidelberg (2005)
 
Search WWH ::




Custom Search