The goal of this project is to develop “certifiable” Secure Multi-Party Computation (SMPC) protocols that ensure that data points consumed by the protocol are derived from accredited sources. SMPC protocols in current use for, e.g., sharing information between competing entities, do not usually verify that the private data input to the protocol is legitimate. The collaborative laboratory will tackle this problem by fundamentally reworking security models for such protocols, and analysing how developments in anonymous credentials and zero-knowledge proofs (ZKPs) can be used to export trust to privacy-preserving computations.
Privacy preserving technologies
PhD defence: Nicolas Costes
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
Cryptographic algorithms are fundamental building blocks that provides security in information systems. The security of these algorithms rely on various mathematical problems that are believed to be hard to solve, as well as the assumption that no weaknesses have been inadvertently introduced in their particular designs. To gain confidence in the cryptography we all use today it is therefore important to closely study proposed algorithms, searching for security flaws and possible ways they can be attacked.
The evolution of information systems has brought a demand for cryptographic algorithms with particular features. New designs aiming to accommodate these demands are therefore regularly being proposed, bringing a need for independent analysis. Current focus areas of our research are design and analysis of:
- Algorithms that are designed to be secure against attacks using quantum computers
- Encryption algorithms using secret keys that are designed to be used in protocols for doing multiparty computation, zero-knowledge proofs, or fully homomorphic encryption
- Fully homomorphic encryption schemes, and their usefulness in practice
Håvard Raddum
Carlos Cid
Martha Norberg Hovd
Morten Øygarden
Pierre Briaud
Irati Manterola Ayala
Atharva Phanse
Mohamed Abdelmonem
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
Håvard Raddum
Øyvind Ytrehus
Sigurd Jordal
Stian Husum
The recent popularity of blockchains has significantly increased the demand for cryptographic protocols with advanced features. Of particular interest are zero-knowledge proofs. These allow to prove mathematical statements without leaking any private information. For instance, one might want to prove that an encrypted transaction is valid without revealing the transaction or to prove knowledge of a secret key without leaking it.
Unfortunately, many zero-knowledge proofs have either impractical efficiency or poorly understood security assumptions. Our research at Simula UiB focuses on constructing zero-knowledge proofs, which finds a good balance between those two.
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
Øyvind Ytrehus
We study the finite-length analysis and the practical performance of quantum information and computation. While most theoretical results in quantum information and computation are developed assuming that quantum resources are unlimited, we are interested in what can be achieved with limited quantum resources in the current realistic, noisy intermediate quantum era. Quantum computers with 300-1000 qubits may allow us to perform classical tasks beyond the capabilities of today’s modern non-quantum digital devices. However, noise in quantum gates is known to be unavoidable, and this intrinsic fact limits the size of quantum circuits that can be reliably executed. We aim to develop efficient and reliable quantum information and computation systems using the principle of quantum error correction. This guarantees the robustness of noisy intermediate scale quantum systems to perform information processing tasks. Researchers at Simula UiB are currently investigating efficient and reliable quantum coding solutions for communicating either classical or quantum information over quantum communication systems with finite quantum resources.
Hsuan-Yin Lin
Eirik Rosnes
Olai Åsmundson Mostad
Tamás Havas
We investigate developing practical and efficient information-theoretically secure and reliable communication schemes against eavesdropping attacks using information theory and coding techniques. Information-theoretic secure communication is based on the principle of physical layer security (PLS), which uses only the physical layer resources of the communicating parties and provides information-theoretically unbreakable security. PLS has been recognized as an attractive technique for securing confidential data in Beyond 5G (B5G) and 6G wireless communication systems. Unfortunately, existing PLS coding solutions cannot meet the stringent latency and reliability requirements for short-packet communication since most previous works on PLS only provide impractical solutions for secure communication schemes under the assumption that an arbitrarily large coding block length can be used. We are currently designing finite-length lattice and polar code-based security coding schemes to ensure ultra-reliable and low-latency communication between the authorized parties while preventing an adversarial eavesdropper from learning the transmitted messages.
Hsuan-Yin Lin
Øyvind Ytrehus
Maiara Bollauf
Projects
01.01.2024 - 31.12.2024
DurationCarlos Cid (Simula UiB) and Alex Davidson (Universidade NOVA de Lisboa)
Project managerEEA Grants
Funding source01.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 sourceCOSINUS — Collaboration On Secrecy to Investigate New USes (Active project)
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.
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 sourcePublications
Augustin Bariant, Aurélien Boeuf, Axel Lemoine, Irati Manterola Ayala, Morten Øygarden, Léo Perrin, and Håvard Raddum. “The Algebraic Freelunch: Efficient Gröbner Basis Attacks Against Arithmetization-Oriented Primitives”. Accepted at Advances in Cryptology – CRYPTO 2024. https://eprint.iacr.org/2024/347
Garms, Lydia, Taofiq K. Paraïso, Neil Hanley, Ayesha Khalid, Ciara Rafferty, James Grant, James Newman, Andrew J. Shields, Carlos Cid, and Maire O’Neill. “Experimental Integration of Quantum Key Distribution and Post‐Quantum Cryptography in a Hybrid Quantum‐Safe Cryptosystem.” Advanced Quantum Technologies (2023): 2300304.
Fukang Liu, Mohammad Mahzoun, Morten Øygarden, and Willi Meier. “Algebraic Attacks on RAIN and AIM Using Equivalent Representations”. IACR Transactions on Symmetric Cryptology, 2023(4) (pp. 166-186). Presented at FSE 2024. https://doi.org/10.46586/tosc.v2023.i4.166-186
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, 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