TLS is the most important protocol for securing web communication today. Authenticating servers on the internet relies on PKI, and the number of public key certificates issued yearly
by certificate authorities (CA) are now in the billions. Most of the public keys attested by these certificates are 2048-bit RSA keys. The security of RSA is based on the hardness of factoring N = pq where N is public and p and q are two secret big primes. With so many keys generated for certificates each year it is important that all CAs use cryptographically strong random number generators when selecting their prime numbers. If the same prime is used in two different RSA keys it is easy to factor both by computing their greatest common divisor (GCD).  Experiments on computing the GCDs of all pairs from a large set of RSA keys have been done before. In 2012, two teams of researchers independently harvested approximately 6 million certificates with RSA keys each, and ran GCD on all pairs. One finding was that around 0.5% of the RSA keys could be factored this way, mostly due to faulty random number generators. The same experiment was repeated in 2016, this time collecting 81 million keys. The result was that 0.4% of the RSA keys could be factored via GCD. Finally, in 2019 approximately 75 million certificates with RSA keys were collected from the internet and almost 0.6% of them were factored by taking GCD of all pairs. According
to the authors this is due to IoT devices with poor random generators. The authors compare this to a set of 100 million RSA keys collected from the Certificate Transparency (CT) logs, where they could only factor 5 keys.

We have redone the GCD factoring experiment using 159 million certificates from the CT log Argon from 2021, and report on our findings. To our knowledge, this is the largest
experiment of this type done so far.

In this paper we propose Fasta, a stream cipher design optimised for implementation over popular fully homomorphic encryption schemes. A number of symmetric encryption ciphers have been recently proposed for FHE applications, e.g. the block cipher LowMC, and the stream ciphers Rasta (and variants), FLIP and Kreyvium. The main design criterion employed in these ciphers has typically been to minimise the multiplicative complexity of the algorithm. However, other aspects affecting their efficient evaluation over common FHE libraries are often overlooked, compromising their real-world performance. Whilst Fasta may also be considered as a variant of Rasta, it has its parameters and linear layer especially chosen to allow efficient implementation over the BGV scheme, particularly as implemented in the HElib library. This results in a speedup by a factor of 25 compared to the most efficient publicly available implementation of Rasta.  Fasta’s target is BGV, as implemented in HElib. However the design ideas introduced in the cipher could also be potentially employed to achieve improvements in the homomorphic evaluation in other popular FHE schemes/libraries. We do consider such alternatives in this paper (e.g. BFV and BGVrns, as implemented in SEAL and PALISADE), but argue that, unlike BGVin HElib, it is more challenging to make use of their parallelism in a Rasta-like stream cipher design.

Fully homomorphic encryption (FHE) is a powerful tool in cryptography that allows one to perform arbitrary computations on encrypted material without having to decrypt it first. There are numerous FHE schemes, all of which are expanded from somewhat homomorphic encryption (SHE) schemes, and some of which are considered viable in practice. However, while these FHE schemes are semantically (IND-CPA) secure, the question of their IND-CCA1 security is much less studied, and we therefore provide an overview of the IND-CCA1 security of all acknowledged FHE schemes in this paper. To give this overview, we group SHE schemes into broad categories based on their similarities and underlying hardness problems. For each category, we show that the SHE schemes are susceptible to either known adaptive key recovery attacks, a natural extension of known attacks, or our proposed attacks. Finally, we discuss the known techniques to achieve IND-CCA1 secure FHE and SHE schemes. We conclude that none of the proposed schemes are IND-CCA1 secure, and that the known general constructions all have their shortcomings.

EFLASH is a multivariate public-key encryption scheme proposed by Cartor and Smith-Tone at SAC 2018. In this paper we investigate the hardness of solving the particular equation systems arising from EFLASH, and show that the solving degree for these types of systems is much lower than estimated by the authors. We show that a Gröbner basis algorithm will produce degree fall polynomials at a low degree for EFLASH systems. In particular we are able to accurately predict the number of these polynomials occurring at step degrees 3 and 4 in our attacks. We performed several experiments using the computer algebra system MAGMA, which indicate that the solving degree is at most one higher than the one where degree fall polynomials occur; moreover, our experiments show that whenever the predicted number of degree fall polynomials is positive, it is exact. Our conclusion is that EFLASH does not offer the level of security claimed by the designers. In particular, we estimate that the EFLASH version with 80-bit security parameters offers at most 69 bits of security.

We initiate the study of self-dual codes over GF(4) whose corresponding graphs have fixed rankwidth. We show that by combining the structural properties of rankwidth 1 graphs, the classification of corresponding codes becomes significantly faster.
We give a new algorithm for computing weight enumerators using Binary Decision Diagrams (BDD), which has similar complexity to brute force O(2^k) but has the benefit that we automatically get complexity O(2^min{k,n−k}) (for k > n/2) without needing to consider the dual code.
We show that the minimum distance of a code is at least 3 if and only if the corresponding graph does not contain any pendant vertex or any twin-pairs. We also give an algorithm for computing an approximate minimum distance in codes corresponding to general graphs.

We introduce a new technique for doing the key recovery part of an integral or higher order differential attack. This technique speeds up the key recovery phase significantly and can be applied to any block cipher with small S-boxes. We show several properties of this technique, then apply it to PRINCE and report on the improvements in complexity from earlier integral and higher order differential attacks on this cipher. Our attacks on 4 and 6 rounds were the fastest and the winner of PRINCE Challenge's last round in the category of chosen plaintext attack.

Many modern ciphers have a substitution-permutation (SP) network as a main component. This design is well researched in relation to Advanced Encryption Standard (AES). One of the ways to improve the security of cryptographic primitives is the use of additional nonlinear layers. However, this replacement may not have any effect against particular cryptanalytic attacks. In this paper we use algebraic attacks to analyze an SP network with addition modulo 2^n as the key mixing layer. In particular, we show how to reduce the number of intermediate variables in round functions based on SP networks. We also apply the proposed method to the GOST 28147-89 block cipher that allows us to break reduced 8- and 14-round versions with complexity at most 2^{155} and 2^{215.4}, respectively.

In this paper we describe an approach for solving complex multivariate equation systems related to algebraic cryptanalysis. The work uses the newly introduced Compressed Right Hand Sides (CRHS) representation, where equations are represented using Binary Decision Diagrams (BDD). The paper introduces a new technique for manipulating a BDD, similar to swapping variables in the well-known sifting-method. Using this technique we develop a new solving method for CRHS equation systems. The new algorithm is successfully tested on systems representing reduced variants of Trivium.

We study a new representation of non-linear multivariate equations for algebraic cryptanalysis. Using a combination of multiple right hand side equations and binary decision diagrams, our new representation allows a very efficient conjunction of a large number of separate equations. We apply our new technique to the stream cipher Trivium and variants of Trivium reduced in size. By merging all equations into one single constraint, manageable in size and processing time, we get a representation of the Trivium cipher as one single equation.

This paper shows how to carry out a quantitative risk assessment, describing how each step in the process is carried out. We use the grade management system at the University of Bergen as a case study, evaluating the risk of wrong grades ending up in the university grade database.

Several suggested Internet-based electronic voting systems provide the voters with receipts to prove that their votes were counted. Unfortunately, these receipts strengthen an adversary’s ability to coerce voters. This paper proposes a technique for generating receipts which gives voters a high degree of certainty their votes were counted, but without helping a coercer.

We describe the background of the Zodiac killer’s cipher, and present a strategy for how to attack the unsolved Z340 cipher. We present evidence that there is a high degree of non-randomness in the sequence of ciphertext symbols in this cipher, suggesting it has been constructed in a systematic way. Next, we use this information to design a tool for solving the Zodiac ciphers. Using this tool we are able to re-solve the known Z408 cipher.

LEX is a stream cipher that progressed to Phase 3 of the eSTREAM stream cipher project. In this paper, we show that the security of LEX against algebraic attacks relies on a small equation system not being solvable faster than exhaustive search. We use the byte leakage in LEX to construct a system of 21 equations in 17 variables. This is very close to the require- ment for an efficient attack, i.e. a system containing 16 variables. The system requires only 36 bytes of keystream, which is very low.

A new method for solving algebraic equation systems common in cryptanalysis is proposed. Our method differs from the others in that the equations are not represented as multivariate polynomials, but as a system of Multiple Right Hand Sides linear equations. The method was tested on scaled versions of the AES. The results overcome significantly what was previously achieved with Gröbner Basis related algorithms.

It is well known that replacing the irreducible polynomial used in the AES one can produce 240 dual ciphers. In this paper we present 9120 other representations of GF(28), producing more ciphers dual to the AES. We also show that if the matrix used in the S-box of Rijndael is linear over a larger field than GF(2), this would have implications for the XSL attack.

IDEA is a 64-bit block cipher with a 128-bit key designed by J. Massey and X. Lai. At FSE 2002 a slightly modified version called IDEA-X was attacked using multiplicative differentials. In this paper we present a less modified version of IDEA we call IDEA-X/2, and an attack on this cipher. This attack also works on IDEA-X, and improves on the attack presented at FSE 2002.

Recently it was shown (by J. Patarin) how to distinguish a general five-round Feistel network from a random permutation using O(23n/2) chosen plaintexts or O(27n/4) known plaintexts. The present authors report improvement of these results and a distinguisher is presented which uses roughly 2n chosen plaintexts or roughly 23n/2 known plaintexts.