Shevtsov O. Models and methods of postquantum lattice based and code based digital signatures

The thesis provides research of mathematical models and computational methods of digital signature in polynomial quotient-rings and code based signatures. For these signature schemes security estimates against existing methods of cryptographic analysis are scrutinized, and as a result there is also developed recommendations for practical implementation for post-quantum period. In the dissertation, a hybrid adversary model of existential forgery is proposed, which consider both classical and quantum cryptanalysis methods implementation. Under an assumption that adversary acts with a combination of heuristic classical and quantum computer routines, we consider strong unforgeable security model of signatures, which presumes that even legal signer can't create another valid signature for one given message. We show with experimental results that such unforgeability is unattainable for certain primitives of lattice based signatures. Also a digital signature threat model is proposed. It utilize the methods of security reductions for post-quantum environment, to classify threats by the additional complexity of cryptanalysis in comparison with a more general cryptanalysis problem. Experimental researches of digital signatures properties in polynomials quotient-ring as well as code based schemes have been carried out, and resistance to existing methods of cryptographic analysis has been estimated. In particular, an attack model against signature in the polynomial quotient-rings with enhanced parameters and additional protection by perturbation techniques was developed. This model allows to derive a lower complexity of the counterfeit compared to a brute force. Also, another approach of creating malleable signature was obtained, which gives new numerical estimates of breaking bijection between signatures and messages for relevant key sizes. This can invoke to several messages belonging to one signature derived by private key owner. New security estimates of forgery are obtained. First it has been shown that mathematical model of lattices was the reason of forgery. Finally it implies that current mathematical model of trapdoor function can't engender signature model with needed properties. Also new attack against Melchor NTRUSign signature is proposed. And new evidences that Fiat-Shamir paradigm can't provide security under flows of lattice trapdoor function have been achieved. A new attack against code based digital signature is proposed. It exploits an addition operation of arbitrary code word of the applied block code, and changes Hamming weight of signature vector. In thesis also elaborated new countermeasures against this attack as well as auxiliary conditions for verification procedure. The thesis provides research of mathematical models and computational methods of digital signature in polynomial quotient-rings and code based signatures. For these signature schemes security estimates against existing methods of cryptographic analysis are scrutinized, and as a result there is also developed recommendations for practical implementation for post-quantum period.