Friday seminar: The foundations of PAC learning
Friday seminar: Lightweight, Realtime Solutions to the Privacy and Security Issues in the Internet of Vehicles (IoV)
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.
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
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.
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.
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.
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.
07.09.2022 - 06.09.2025Duration
Øyvind Ytrehus, Simula UiBProject manager
Øyvind YtrehusPrincipal scientist from Simula UiB
The Research Council of Norway (IKTPLUSS)Funding source
01.01.2021 - 01.01.2024Duration
Kjell Jørgen HoleProject manager
Kjell Jørgen HolePrincipal scientist from Simula UiB
The AI Risk project studies future tools with general AI, called tool AIs. Tool AIs based on the human neocortex answer difficult questions. The tools are the basis for different types of intelligent devices. There are risks associated with the tools themselves and the answers they provide. The goal is to design neocortex-based tool AIs without existential risk to humanity and then describe systems of tool-based devices providing answers with acceptable non-existential risk to users and other stakeholders.
The project’s first part is described in two published papers Tutorial on systems with antifragility to downtime and A thousand brains: toward biologically constrained AI. The second part studies the properties tool AIs need to eliminate existential risk and how to create tool-based antifragile systems with acceptable non-existential risk. The project’s third part explores other risks users face when using tool-based personal assistants.
01.01.2021 - 01.01.2024Duration
Kjell Jørgen HoleProject manager
Kjell Jørgen HolePrincipal scientist from Simula UiB
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 – 10th International Workshop, CBCrypto 2022, Trondheim, Norway, May 29–30, 2022, Revised Selected Papers. Springer.
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.
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.
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
- 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