32 Post Quantum Crypto for Dummies private key since publishing the other value from her private key would reveal all private information to the public, Bob could no longer distinguish whether Alice or somebody else signed subsequent messages. Another obvious drawback of this basic scheme is the extremely limited length of the messages. More elaborate hash-based signature schemes allow to perform more than one signature by using tree structures (see Figure 3.3) and an arbitrary message length by using hash chains. The total amount of possible signatures is typically limited and specified by a parameter for the scheme; in general, the signature size increases if more signatures for the same public key are required. Hash-based signature schemes are considered very mature and have very reliable security estimates. The hash-based signature scheme XMSS 16 is currently in the standardization process by the IETF for use in Internet protocols 17. A potential disadvantage of XMSS is its statefulness: In order to avoid re-usage of private key material, a state needs to be maintained that marks what parts of the private key already have been used and which parts are still available. For some applications, this might introduce additional cost. Also backup strategies might cause problems for state-based schemes because it is not secure to fall back to an old key state in case of data loss. There are hash-based signature schemes that avoid maintaining a key state. A recent example is SPHINCS 9. The price of stateless schemes compared to stateful schemes are larger signature sizes. The size of the public key for both stateless and stateful schemes is relatively small, typically about 64 bytes. The signature size of stateful schemes is in the range of 2–3 kB, the signature size of stateless schemes is about 40 kB. Multivariate Cryptography Multivariate cryptography is based on the hardness of the MQ-problem. Solving multivariate quadratic systems of equations over finite fields is NP-hard: As opposed to linear systems, there is no efficient algorithm for solving random multivariate polynomial systems. Figure 3.4 shows an example for a small multivariate polynomial system. The hardness of solving a specific system depends on the size of the underlying finite field, the number of variables, and the degree of the system. Nevertheless, if the number of equations and variables is sufficiently large, even systems of quadratic equations over ��2 (degree two, smallest finite field) are hard to solve.
PQC_for_Dummies
To see the actual publication please follow the link above