Security, Scalability and Privacy in Applied Cryptography

In the modern digital world, cryptography finds its place in countless applications. However, as we increasingly use technology to perform potentially sensitive tasks, our actions and private data attract, more than ever, the interest of ill-intentioned actors.
Due to the possible privacy implications of cryptographic flaws, new primitives’ designs need to undergo rigorous security analysis and extensive cryptanalysis to foster confidence in their adoption. At the same time, implementations of cryptographic protocols should scale on a global level and be efficiently deployable on users’ most common devices to widen the range of their applications.
This dissertation will address the security, scalability and privacy of cryptosystems by presenting new designs and cryptanalytic results regarding blockchain cryptographic primitives and public-key schemes based on elliptic curves. In Part I, I will present the works I have done in regards to accumulator schemes. More precisely, in Chapter 2, I cryptanalyze Au et al. Dynamic Universal Accumulator, by showing some attacks which can completely take over the authority who manages the accumulator. In Chapter 3, I propose a design for an efficient and secure accumulator-based authentication mechanism, which is scalable, privacy-friendly, lightweight on the users’ side, and suitable to be implemented on the blockchain.
In Part II, I will report some cryptanalytical results on primitives employed or considered for adoption in top blockchain-based cryptocurrencies. In particular, in Chapter 4, I describe how the zero-knowledge proof system and the commitment scheme adopted by the privacy-friendly cryptocurrency Zcash, contain multiple subliminal channels which can be exploited to embed several bytes of tagging information in users’ private transactions. In Chapter 5, instead, I report the cryptanalysis of the Legendre PRF, employed in a new consensus mechanism considered for adoption by the blockchain-based platform Ethereum, and attacks for further generalizations of this pseudo-random function, such as the Higher-Degree Legendre PRF, the Jacobi Symbol PRF, and the Power-Residue PRF.
Lastly, in Part III, I present my line of research on public-key primitives based on elliptic curves. In Chapter 6, I will describe a backdooring procedure for primes so that whenever they appear as divisors of a large integer, the latter can be efficiently factored. This technique, based on elliptic curves Complex Multiplication theory, enables to eventually generate non-vulnerable certifiable semiprimes with unknown factorization in a multi-party computation setting, with no need to run a statistical semiprimality test common to other protocols. In Chapter 7, instead, I will report some attack optimizations and specific implementation design choices that allow breaking a reduced-parameters instance, proposed by Microsoft, of SIKE, a post-quantum key-encapsulation mechanism based on isogenies between supersingular elliptic curves.