Symmetric cryptography is finding new uses due of the emergence of novel and more complex computing environments, many of which are based on sophisticated Zero-Knowledge (ZK) and Multi-Party Computation (MPC) protocols. These new uses often call for dedicated symmetric algorithm designs, typically natively described over large finite fields of odd characteristic (rather than in binary fields). The COSINUS Associate Team will combine the expertises at COSMIQ-Inria and Simula UiB, to research and devise novel design and cryptanalytic techniques for this new breed of symmetric cryptography.
Trial lecture: Kolmogorov complexity and cryptography
PhD Defence: Reent Schlegel
Research
Our research departments cover a range of problems within cryptography and information theory. Have a closer look below at our focus areas and which researchers are working within the different areas.
Cryptography department
Many secure systems are built upon the assumption that the cryptographic primitives used as building blocks can not be broken. Researchers at Simula UiB study the hardness of underlying mathematical problems that cryptographic schemes are based on. This work builds confidence in the assumption that these cryptographic building blocks deliver the promised security. In particular, we do research in the following areas:
- Post-quantum secure algorithms for encryption and digital signatures based on RLWE/MLWE and the connected SVP problem in lattices
- Analysis of symmetric ciphers and their representations as instances of the MQ problem or other types of non-linear equation systems
- FHE schemes – cryptanalysis and their usefulness in practice

Håvard Raddum

Carlos Cid
Many cryptographic security guarantees treat cryptographic primitives as black-boxes: an adversary trying to break it can play with the inputs and outputs, but not peek inside. In reality, these primitives will have to be implemented on some device that lives in the physical world and hence can be observed by an adversary. For instance, a device’s power consumption or EM emanation provides leakage that an adversary can exploit by mounting a side-channel attack. As a rule of thumb, unprotected implementations will be vulnerable to side-channel analysis, the main question is how vulnerable. Understanding this vulnerability also helps to protect an implementation by means of countermeasures. Our research concentrates on creating a solid scientific basis from which engineering progress in creating secure solutions can be made.

Martijn Stam
A cryptographic protocol is a protocol between two or more parties that is built upon usually existent cryptographic primitives and guarantees security against malicious participants. Cryptographic protocols are used to secure a variety of activities, starting from privacy-preserving data mining and machine learning and ending with electronic voting. A currently very active and important area of research is developing secure cryptographic protocols for cryptocurrencies and blockchain. An important keyword here is zk-SNARK (zero-knowledge succinct non-interactive argument of knowledge). A zero-knowledge proof system enables one participant (the prover) to prove to another one (the verifier) that it followed the prescribed protocol without leaking any side information. A zk-SNARK is an efficient zero-knowledge proof where the communication and the verifier’s computation are minimal. Zk-SNARKs have multibillion dollar applications in cryptocurrencies.
We are studying cryptographic protocols in general and zero-knowledge proof systems and zk-SNARKs in particular. We are both interested in the theoretical underpinnings of cryptographic protocols and their practical applications. We are interested both in attaining good security (minimal cryptographic assumptions) and maximal practical efficacy — and the tradeoffs between these two aspects. On top of zk-SNARKs, we have recently performed work on electronic voting, functional encryption, private information retrieval, and various underlying cryptographic primitives like functional commitment schemes.

Helger Lipmaa
Information Theory department
We consider privacy- and security-preserving technologies in retrieving information and distributed learning. In the first topic of private information retrieval (PIR), the goal is to allow a user to access an arbitrary message stored in a set of databases without revealing any information about the identity of the requested message to each database. Researchers at Simula UiB work on extensions of the original PIR problem and for allowing for the retrieval of more general function evaluations, so-called private computation.
In distributed learning, we focus on a paradigm named federated learning (FL), which trains an algorithm across multiple devices without exchanging the training data directly, thus limiting the privacy leakage and reducing the communication load. FL has been used in real-world applications, e.g., for medical data, text predictions on mobile devices, or by Apple to personalize Siri. We work on designing efficient schemes to mitigate the effect of straggling devices while minimizing the leakage of users’ private data, including efficient coded secure aggregation schemes.

Eirik Rosnes

Hsuan-Yin Lin
We work on the design of efficient and reliable storage and computing systems using coding theory. In distributed storage systems where data is encoded and stored over a set of distributed storage nodes, the aim is to add redundancy in an efficient manner such that no data is lost in case of storage node failures, and such that failed nodes can be efficiently repaired. Modern distributed platforms like Facebook’s Hadoop storage system and Microsoft Azure rely on such efficient methods for repairing node failures. Error correction of data storage in deoxyribonucleic acid (DNA) has recently gained much attention after several successful experiments that demonstrated the viability of using synthetic DNA as a reliable medium for data storage. Researchers at Simula UiB are currently looking into designing efficient coding solutions for this emerging storage technology.
Distributed computing systems have emerged as one of the most effective ways of solving increasingly complex computational problems, such as those in large-scale machine learning and data analytics. In coding for distributed computing, redundancy is added to the computation to mitigate the effect of straggling servers and reduce the amount of intra-server communication. In distributed computing over the edge (so-called edge computing), computations are offloaded to the edge of the network instead of being carried out in a data center in order to reduce the overall computational latency. Low-latency applications, like autonomous driving and virtual reality, will likely require efficient solutions for edge computing. At Simula UiB, we work on developing efficient methods to mitigate the effect of straggling nodes in edge computing systems.

Eirik Rosnes

Hsuan-Yin Lin
Projects
01.06.2023 - 31.05.2025
DurationCarlos Cid, Simula UiB, and Léo Perrin, Inria Paris
Project managerCarlos Cid
Principal scientist from Simula UiBInria Associate Team Program
Funding source07.09.2022 - 06.09.2025
DurationØyvind Ytrehus, Simula UiB
Project managerØyvind Ytrehus
Principal scientist from Simula UiBThe Research Council of Norway (IKTPLUSS)
Funding sourceqsIo2: Quantum safe cryptography
07.09.2022 - 06.09.2025
DurationØyvind Ytrehus, Simula UiB
Project managerØyvind Ytrehus
Principal scientist from Simula UiBThe Research Council of Norway (IKTPLUSS)
Funding sourcePublications
Martin Brain, Carlos Cid, Rachel Player and Wrenna Robson. “Verifying Classic McEliece: examining the role of formal methods in post-quantum cryptography standardisation”. Code-Based Cryptography. CBCrypto 2022. Lecture Notes in Computer Science, vol 13839. Springer, Cham. https://doi.org/10.1007/978-3-031-29689-5_2
Helger Lipmaa, Janno Siim and Michal Zajac. 2022. “Counting Vampires: From Univariate Sumcheck to Updatable ZK-SNARK”. In Shweta Agrawal and Dongdai Lin, editors, Asiacrypt 2022, Lecture Notes in Computer Science, Taipei, Taiwan, December 5-9, Springer, Cham.
Prastudy Fauzi, Martha Norberg Hovd and Håvard Raddum. 2022. “On the IND-CCA1 Security of FHE Schemes” Cryptography 6, no. 1: 13. https://doi.org/10.3390/cryptography6010013
Behzad Abdolmaleki, Hamidreza Khoshakhlagh and Helger Lipmaa. Smooth Zero-Knowledge Hash Functions. In Avishek Adhikari, Bart Preneel and Ralf Kusters, editors, Indocrypt 2021, volume ? of Lecture Notes in Computer Science, pages ?–?, Jaipur, India, December 12–15, 2021. Springer, Cham.
Helger Lipmaa and Kateryna Pavlyk. Gentry-Wichs Is Tight: A Falsifiable Non-Adaptively Sound SNARG. In Huaxiong Wang and Mehdi Tibouchi, editors, Asiacrypt 2021, volume 13092 of Lecture Notes in Computer Science, pages 34–64, Singapore, Singapore, December 5–9, 2021. Springer, Cham. 10.1007/978-3-030-92078-4_2.
Alessandro Melloni, Martijn Stam and Øyvind Ytrehus (2022). On Evaluating Anonymity of Onion Routing. In: AlTawy, R., Hülsing, A. (eds) Selected Areas in Cryptography. SAC 2021. Lecture Notes in Computer Science, vol 13203. Springer, Cham. https://doi.org/10.1007/978-3-030-99277-4_1
Prastudy Fauzi, Helger Lipmaa, Janno Siim, Michal Zajac and Arne Tobias Ødegaard. Verifiably-Extractable OWFs and Their Applications to Subversion Zero-Knowledge. In Huaxiong Wang and Mehdi Tibouchi, editors, Asiacrypt 2021, volume 13093 of Lecture Notes in Computer Science, pages 618–649, Singapore, Singapore, December 5–9, 2021. Springer, Cham. 10.1007/978-3-030-92068-5_21.
Geoffroy Couteau, Helger Lipmaa, Roberto Parisella and Arne Tobias Ødegaard. Efficient NIZKs for Algebraic Sets. In Huaxiong Wang and Mehdi Tibouchi, editors, Asiacrypt 2021, volume 13092 of Lecture Notes in Computer Science, pages 128–158, Singapore, Singapore, December 5–9, 2021. Springer, Cham. 10.1007/978-3-030-92078-4_5.
Behzad Abdolmaleki, Helger Lipmaa, Janno Siim and Michal Zajac. “On Subversion-Resistant SNARKs”. Journal of Cryptology 34, 17 (2021). https://doi.org/10.1007/s00145-021-09379-y
Toomas Krips and Helger Lipmaa. More Efficient Shuffle Argument from Unique Factorization. In Kenny Paterson, editor, CT-RSA 2021, volume 12704 of Lecture Notes in Computer Science, pages 252–275, San Francisco, CA, USA, May 17–21, 2021. Springer, Cham. 10.1007/978-3-030-75539-3_11.
Prastudy Fauzi, Martha Norberg Hovd and Håvard Raddum. 2021. “A Practical Adaptive Key Recovery Attack on the LGM (GSW-like) Cryptosystem.” In Post-Quantum Cryptography, Seoul, South Korea, July 2021, 483-498. Springer, Cham. https://doi.org/10.1007/978-3-030-81293-5_25
Kjell Jørgen Hole. “Tutorial on systems with antifragility to downtime”, Computing, 2021, 10.1007/s00607-020-00895-6
- A. Aggelakis, P. Fauzi, G. Korfiatis, P. Louridas, F. Mergoupis-Anagnou, J. Siim and M. Zając, “A Non-Interactive Shuffle Argument With Low Trust Assumptions”, in Topics in Cryptology – CT-RSA 2020 – The Cryptographers’ Track at the RSA Conference 2020, San Francisco, CA, USA, February 24-28th, 2020.
Martha Norberg Hovd and Martijn Stam. 2020. “Vetted Encryption”. In Progress in Cryptology – INDOCRYPT 2020, Bangalore, India, December 2020, 488-507. Springer, Cham. https://doi.org/10.1007/978-3-030-65277-7_22
- B. Greve, Ø. Ytrehus, H. Raddum and G. Fløystad, “Solving non-linear Boolean equation systems by variable elimination», Applicable Algebra in Engineering, Communication and Computing, 2019, https://doi.org/10.1007/s00200-019-00399-7
- M. Albrecht, C. Cid, L. Grassi, D. Khovratovich, R. Lüftenegger, C. Rechberger and M. Schofnegger,
“Algebraic Cryptanalysis of STARK-Friendly Designs: Application to MARVELlous and MiMC”,
in Proc. 25th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2019), Kobe, Japan, December 8-12, 2019
- S.Kumar, A. Graell i Amat, I. Andriyanova, F. Brännström and E. Rosnes, “Code constructions for distributed storage with low repair bandwidth and low repair complexity”, in IEEE Transactions on Communications
- Hovd, Martha Norberg. 2018. “A successful subfield lattice attack on a fully homomorphic encryption scheme”. In Proceedings of the 11th Norwegian Information Security Conference, Longyearbyen, Norway, September 2018, 1-15. Open Journal Systems, Bibsys. https://ia.cr/2021/1626