Trial lecture: Kolmogorov complexity and cryptography

05.05.2023
, 2:00 pm
All events

Simula UiB advances the science of cryptography and information theory

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
Working on this:

Håvard Raddum

Chief Research Scientist and Section Leader Cryptography

Carlos Cid

Director at Simula UiB

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.

Working on this:

Martijn Stam

Chief Research Scientist

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.

Working on this:

Helger Lipmaa

Chief Research Scientist

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.

Working on this:

Eirik Rosnes

Chief Research Scientist and Section Leader Information Theory

Hsuan-Yin Lin

Research Scientist

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.

Working on this:

Eirik Rosnes

Chief Research Scientist and Section Leader Information Theory

Hsuan-Yin Lin

Research Scientist

Projects

01.06.2023 - 31.05.2025
Duration
Carlos Cid, Simula UiB, and Léo Perrin, Inria Paris
Project manager
Carlos Cid
Principal scientist from Simula UiB
Inria Associate Team Program
Funding source

COSINUS — Collaboration On Secrecy to Investigate New USes

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
Duration
Carlos Cid, Simula UiB, and Léo Perrin, Inria Paris
Project manager
Carlos Cid
Principal scientist from Simula UiB
Inria Associate Team Program
Funding source
07.09.2022 - 06.09.2025
Duration
Øyvind Ytrehus, Simula UiB
Project manager
Øyvind Ytrehus
Principal scientist from Simula UiB
The Research Council of Norway (IKTPLUSS)
Funding source

qsIo2: Quantum safe cryptography

If in the future a large enough quantum computer can be constructed, it will break cryptographic primitives and protocols in current use, with devastating consequences for users worldwide. The project’s goal is to study and analyse cryptographic primitives and protocols that resist attacks by classical and quantum computers. This project is a continuation of the project qsIoT – Quantum safe cryptography for the Internet of Things.
07.09.2022 - 06.09.2025
Duration
Øyvind Ytrehus, Simula UiB
Project manager
Øyvind Ytrehus
Principal scientist from Simula UiB
The Research Council of Norway (IKTPLUSS)
Funding source
See all projects

Publications

•

Maiara F. Bollauf, Hsuan-Yin Lin, and Øyvind Ytrehus. 2023. “Formally Unimodular Packings for the Gaussian Wiretap Channel” to appear in IEEE Transactions on Information Theory.

•

Lorenzo Grassi, Irati Manterola Ayala, Martha Norberg Hovd, Morten Øygarden, Håvard Raddum and Qingju Wang. “Cryptanalysis of Symmetric Primitives over Rings and a Key Recovery Attack on Rubato.” Crypto 2023. Annual International Cryptology Conference. Springer, Cham.

•

Lorenzo Grassi, Morten Øygarden, Markus Schofnegger and Roman Walch. “From Farfalle to Megafono via Ciminion: The PRF Hydra for MPC Applications.” Eurocrypt 2023. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Cham

•

Pierre Briaud and Morten Øygarden. “A New Algebraic Approach to the Regular Syndrome Decoding Problem and Implications for PCG Constructions.” Eurocrypt 2023. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Cham.

•

Palma Rud Persson, Maiara Francine Bollauf, Hsuan-Yin Lin and Øyvind Ytrehus “On the Secrecy Gain of Isodual Lattices from Tail-Biting Convolutional Codes” in Proc. Int. Symp. Topics Coding, Brest, France, Sep. 2023.

•

Issam Maarouf, Gianluigi Liva, Eirik Rosnes, and Alexandre Graell i Amat “Finite blocklength performance bound for the DNA storage channel” in Proc. 12th Int. Symp. Topics Coding (ISTC), Brest, France, Sep. 2023.

•

Matteo Campanelli, Chaya Ganesh, Hamidreza Khoshakhlagh and Janno Siim, “Impossibilities in Succinct Arguments: Black-box Extraction and More” to appear in Africacrypt 2023.

•

David Hayes, David Ros, and Øyvind Ytrehus, “Proxy Path Scheduling and Erasure Reconstruction for Low Delay mmWave Communication,” to appear in IEEE Communications Letters.

•

Wrya K. Kadir, Hsuan-Yin Lin, and Eirik Rosnes, “Efficient interpolation-based decoding of Reed-Solomon codes,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Taipei, Taiwan, Jun. 2023.

•

Sarah A. Obead, Hsuan-Yin Lin, and Eirik Rosnes, “Single-server pliable private information retrieval with side information,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Taipei, Taiwan, Jun. 2023.

•

Yauhen Yakimenka, Chung-Wei Weng, Hsuan-Yin Lin, Eirik Rosnes, and Joerg Kliewer, “Differentially-private collaborative online personalized mean estimation,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Taipei, Taiwan, Jun. 2023.

•

Issam Maarouf, Eirik Rosnes, and Alexandre Graell i Amat. Apr. 2023. “Achievable information rates and concatenated codes for the DNA nanopore sequencing channel” in Proc. IEEE Inf. Theory Workshop (ITW), Saint-Malo, France.

•

Lorenz Welter, Issam Maarouf, Andreas Lenz, Antonia Wachter-Zeh, Eirik Rosnes, and Alexandre Graell i Amat. Apr. 2023. “Index-based concatenated codes for the multi-draw DNA storage channel’’ in Proc. IEEE Inf. Theory Workshop (ITW). Saint-Malo, France.

•

Maiara Francine Bollauf, Hsuan-Yin Lin and Øyvind Ytrehus, “Construction and Secrecy Gain of Formally Unimodular Lattices in Odd Dimensions” in Proc. IEEE Inf. Theory Workshop, Saint-Malo, France, April 2023.

•

Reent Schlegel, Siddhartha Kumar, Eirik Rosnes, and Alexandre Graell I Amat “CodedPaddedFL and CodedSecAgg: Straggler mitigation and secure aggregation in federated learning” in IEEE Transactions on Communications, vol. 71, no. 4, pp. 2013-2027, April 2023, doi: 10.1109/TCOMM.2023.3244243

•

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

•

Albin Severinson, Eirik Rosnes, Salim El Rouayheb, and Alexandre Graell i Amat “DSAG: A mixed synchronous-asynchronous iterative method for straggler-resilient learning” in IEEE Transactions on Communications, vol. 71, no. 2, pp. 808-822, Feb. 2023, doi: 10.1109/TCOMM.2022.3227286.

•

Chung-Wei Weng, Yauhen Yakimenka, Hsuan-Yin Lin, Eirik Rosnes and Jorg Kliewer. 2022. “Generative Adversarial User Privacy In Lossy Single-Server Information Retrieval”. IEEE Transactions On Information Forensics And Security 17: 3495-3510. doi:10.1109/tifs.2022.3203320.

•

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.

•

Issam Maarouf, Andreas Lenz, Lorenz Welter, Antonia Wachter-Zeh, Eirik Rosnes, and Alexandre Graell i Amat. 2022. “Concatenated Codes for Multiple Reads of a DNA Sequence,” in IEEE Transactions on Information Theory, vol. 69, no. 2, pp. 910-927, Feb. 2023, doi: 10.1109/TIT.2022.3206527.

•

Vinay A. Vaishampayan and Maiara F. Bollauf. 2022.  “Interactive Nearest Lattice Point Search in a Distributed Setting: Two Dimensions” IEEE Transactions on Communications 70, 8 (August 2022): 5128 – 5139

•

Yauhen Yakimenka, Chung-Wei Weng, Hsuan-Yin Lin, Eirik Rosnes and Joerg Kliewer. 2022. ”Straggler-resilient differentially-private decentralized learning” in Proc. IEEE Inf. Theory Workshop, Mumbai, India, Nov.

•

Carlos Cid, Lorenzo Grassi, Aldo Gunsing, Reinhard Lüftenegger, Christian Rechberger and Markus Schofnegger. 2022. “Influence of the Linear Layer on the Algebraic Degree in SP-Networks.” IACR Transactions on Symmetric Cryptology, Vol 2022 (1): 110-137.

•

Chaya Ganesh, Hamidreza Khoshakhlagh and Roberto Parisella. 2022. “NIWI and New Notions of Extraction for Algebraic Languages” to appear at SCN’22.

•

Reent Schlegel, Siddhartha Kumar, Eirik Rosnes and Alexandre Graell i Amat. 2022.”Straggler-resilient secure aggregation for federated learning,” in Proc. Eur. Signal Process. Conf. (EUSIPCO), Belgrade, Serbia, Aug./Sep.

•

Joakim Algrøy, Ángela Isabel Barbero and Øyvind Ytrehus. 2022. “Determining the Equivocation in Coded Transmission Over a Noisy Channel,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Espoo, Finland, Jun./Jul.

•

Maiara F. Bollauf, Hsuan-Yin Lin and Øyvind Ytrehus. 2022. “On the Secrecy Gain of Formally Unimodular Construction A4 Lattices,”  IEEE Int. Symp. Inf. Theory (ISIT’22), Espoo, Finland, June 26-July 1: 3239-3244.

•

Marvin Xhemrishi, Alexandre Graell i Amat, Eirik Rosnes and Antonia Wachter-Zeh. 2022. “Computational code-based privacy in coded federated learning,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Espoo, Finland, Jun./Jul.

•

Sarah A. Obead, Hsuan-Yin Lin, Eirik Rosnes and Joerg Kliewer. 2022.  “Private polynomial function computation for noncolluding coded databases,” IEEE Trans. Inf. Forensics Secur.:1800-1813

•

Siddhartha Kumar, Reent Schlegel, Eirik Rosnes and Alexandre Graell i Amat. 2022. “Coding for straggler mitigation in federated learning,” in Proc. IEEE Int. Conf. Commun. (ICC), Seoul, South Korea, May.

•

Sarah Obead, Hsuan-Yin Lin, Eirik Rosnes and Joerg Kliewer. 2022. “Private linear computation for noncolluding coded databases,” IEEE J. Sel. Areas. Commun. Issue 40, volume 3: 847-861. 

•

Yauhen Yakimenka, Hsuan-Yin Lin, Eirik Rosnes and Joerg Kliewer. 2022. “Optimal rate-distortion-leakage tradeoff for single-server information retrieval,” IEEE J. Sel. Areas. Commun. 40, no.3: 832-846

•

Reent Schlegel, Siddhartha Kumar, Eirik Rosnes and Alexandre Graell i Amat. 2022. “Privacy-preserving coded mobile edge computing for low-latency distributed inference,”  IEEE J. Sel. Areas. Commun. 40, no.3: 788-799

•

Maiara F. Bollauf, Hsuan-Yin Lin and Øyvind Ytrehus. 2022. “The Secrecy Gain of Formally Unimodular Lattices on the Gaussian Wiretap Channel,” in Proc. 2022 International Zurich Seminar on Information and Communication (IZS’22), Zurich, Switzerland, Mar. 02–04, pp. 69–73.

•
Helger Lipmaa. 2022. “A Unified Framework for Non-Universal SNARKs”. In G. Hanaoka, J. Shikata and Y. Watanabe (editors), Public-Key Cryptography – PKC 2022, volume 13177 of Lecture Notes in Computer Science, pages 553–583, Yokohama, Japan, March 7–11. Springer, Cham
•

Carlos Cid, John Petter Indrøy and Håvard Raddum. 2022. “FASTA — a stream cipher for fast FHE evaluation.” Topics in Cryptology – CT-RSA 2022. LNCS 13161, Springer, Cham.: 451-483

•

Hsuan-Yin Lin, Siddhartha Kumar, Eirik Rosnes, Alexandre Graell i Amat and Eitan Yaakobi. 2022. “Multi-server weakly-private information retrieval.” IEEE Transactions on Information Theory, 68(2): 1197-1219

•

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

•

Kjell Jørgen Hole and Subutai Ahmad. “A thousand brains: toward biologically constrained AI.” SN Applied Sciences, vol.3, article 743, 2021.

•

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.

•

Maiara F. Bollauf, Vinay A. Vaishampayan and Sueli I. R. Costa. “On Communication for Distributed Babai Point Computation.” IEEE Transactions on Information Theory 67, 10 (October 2021): 6408 – 6424.

•

Bjørn Møller Greve, Øyvind Ytrehus, Håvard Raddum, and Gunnar Fløysand. “Solving non-linear Boolean equation systems by variable elimination.” Appl. Algebra Eng. Commun. Comput. 32(1): 3-47 (2021)

•

Prastudy Fauzi, Helger Lipmaa, Zairo Pindado, and Janno Siim. “Somewhere Statistically Binding Commitment Schemes with Applications.” In FC 2021: Financial Cryptography and Data Security, Grenada, March 1–5, 2021.

•

Andreas Lenz, Issam Maarouf, Lorenz Welter, Antonia Wachter-Zeh, Eirik Rosnes, and Alexandre Graell i Amat, “Concatenated codes for recovery from multiple reads of DNA sequences” in Proc. IEEE Inf. Theory Workshop (ITW), Riva del Garda, Italy, April 2021

•

Christof Beierle, Patrick Derbez, Gregor Leander, Gaëtan Leurent, Håvard Raddum, Yann Rotella, David Rupprecht and Lukas Stennes. “Cryptanalysis of the GPRS Encryption Algorithms GEA-1 and GEA-2” Eurocrypt 2021.

•

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.

•

Morten Øygarden, Patrick Felke and Håvard Raddum. “Analysis of Multivariate Encryption Schemes: Application to Dob.” In Public-Key Cryptography – PKC 2021

•

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

•

Morten Øygarden, Daniel Smith-Tone and Javier Verbel. “On the Effect of Projection on Rank Attacks in Multivariate Cryptography.” In PQCrypto: International Conference on Post-Quantum Cryptography, 2021.

•

Yauhen Yakimenka, Hsuan-Yin Lin, Eirik Rosnes and Joerg Kliewer. “Optimal rate-distortion-leakage tradeoff for single-server information retrieval,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Melbourne, Victoria, Australia, Jul. 2021 (virtual)

•

Albin Severinson, Eirik Rosnes, and Alexandre Graell i Amat. “Improving age-of-information in distributed vehicle tracking,” in Proc. XXXIV General Assembly Scientific Symposium (GASS) International Union Radio Science, Rome, Italy, Aug./Sep. 2021. (Invited)

•

Maiara F. Bollauf and Øyvind Ytrehus, “Tiling of Constellations” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Melbourne, Victoria, Australia, Jul. 2021 (virtual)

•

Anton Frigård, Siddhartha Kumar, Eirik Rosnes and Alexandre Graell i Amat. “Low-latency distributed inference at the network edge using rateless codes” in Proc. 17th Int. Symp. Wireless Commun. Systems (ISWCS), Berlin, Germany, Sep. 2021 (Invited)

•
  • Hsuan-Yin Lin, Siddhartha Kumar, Eirik Rosnes, Alexandre Graell i Amat and Eitan Yaakobi. “The capacity of single-server weakly-private information retrieval” in IEEE Journal on Selected Areas in Information Theory 2 (1), 415-427. 2021.
•
  • Jesper Pedersen, Alexandre Graell i Amat, Jasper Goseling, Fredrik Brännström, Iryna Andriyanova and Eirik Rosnes. “Dynamic Coded Caching in Wireless Networks,” in IEEE Transactions on Communications, vol. 69, no. 4, pp. 2138-2147, April 2021, doi: 10.1109/TCOMM.2020.3047621.
•

H.-Y. Lin, S. Kumar, E. Rosnes, A. Graell i Amat, and E. Yaakobi, “The capacity of single-server weakly-private information retrieval” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Los Angles, CA, USA, Jun. 2020.

•

H.-Y. Lin, P.-N. Chen, Y.S. Han, and P.K. Varshney, “Minimum Byzantine Effort for Blinding Distributed Detection in Wireless Sensor Networks” IEEE Transactions on Signal Processing, vol. 68, pp. 647–661, 2020.

•

E. Rosnes and M. Helmling, “Adaptive Linear Programming Decoding of Nonbinary Linear Codes Over Prime Fields” in IEEE Transactions on Information Theory, vol. 66, no. 3, pp. 1281-1317, March 2020.

•

Y. Yakimenka and E. Rosnes, “Failure Analysis of the Interval-Passing Algorithm for Compressed Sensing” in IEEE Transactions on Information Theory, vol. 66, no. 4, pp. 2466-2486, April 2020.

•
  • D. Yuan, H.-Y. Lin, J. Widmer, M. Hollick, “Optimal and Approximation Algorithms for Joint Routing and Scheduling in Millimeter-Wave Cellular Networks” IEEE/ACM Transactions on Networking, vol. 28, no. 5, pp. 2188–2202, October 2020.
•

N. Costes and M. Stam. “Redundant Code-based Masking Revisited”. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2021 (1), 426-450.

•

M. Øygarden, P. Felke, H. Raddum and C. Cid, “Cryptanalysis of the Multivariate Encryption Scheme EFLASH”. Topics in Cryptology – CT-RSA 2020, Lecture Notes in Computer Science 12006, pp. 85-105, February 24-28th, 2020.

•
  • 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.
•
  • Y. Yakimenka, H.-Y. Lin, and E. Rosnes, “On the Capacity of Private Monomial Computation” in Proc. International Zurich Seminar on Information and Communication, Zurich, Switzerland, Feb. 26-28, 2020.
•
  • B. Abdolmaleki, H. Lipmaa, J. Siim, M. Zając (2020) “On QA-NIZK in the BPK Model”. In: Kiayias A., Kohlweiss M., Wallden P., Zikas V. (eds) Public-Key Cryptography – PKC 2020. Lecture Notes in Computer Science, vol 12110. Springer, Cham. PKC 2020.
•
  • H. Lipmaa. “Key-and-Argument-Updatable QA-NIZKs”. In Clemente Galdi and Vladimir Kolesnikov, editors, SCN 2020, volume 12238 of Lecture Notes in Computer Science, Amalfi, Italy, September 14-16, 2020.
•
  • R. Schlegel, S. Kumar, E. Rosnes, and A. Graell i Amat, “Private edge computing for linear inference based on secret sharing» in Proc. IEEE Int. Conf. Commun. (GLOBECOM), Taipei, Taiwan, Dec. 2020.
•
  • M. Ciampi, R. Parisella, and D. Venturi, “On Adaptive Security of Delayed-Input Sigma-Protocols and Fiat-Shamir NIZKs” at SCN 2020, Lecture Notes in Computer Science, Amalfi, Italy, September 14-16, 2020.
•
  • H. Lipmaa and K. Pavlyk. “Succinct Functional Commitment for a Large Class of Arithmetic Circuits”, Asiacrypt 2020
•
  • M. Eichlseder, L. Grassi, R. Lüftenegger, M. Øygarden, C. Rechberger, M. Schofnegger and Q. Wang, “An Algebraic Attack on Ciphers with Low-Degree Round Functions: Application to Full MiMC”.  Advances in Cryptology – ASIACRYPT December 7-11, 2020.
•
  • J.P. Indrøy, N. Costes and H. Raddum.”Boolean Polynomials, BDDs and CRHS Equations – Connecting the Dots with CryptaPath”, to be presented at Selected Areas in Cryptography (SAC) 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

•

C.-W. Weng, Y. Yakimenka, H.-Y. Lin, E. Rosnes, and J. Kliewer, “Generative adversarial user privacy in lossy single-server information retrieval”. NeurIPS Workshop on Privacy Preserving Machine Learning – PRIML and PPML Joint Edition, Vancouver, Canada, Dec. 11, 2020

•
  • M. Kumar, H. Raddum and S. Varadharajan, “Reducing Lattice Enumeration Search Trees”, Infocommunications Journal, Volume XI, Issue 4, pp. 8-16, 2019
•

Y. Yakimenka and E. Rosnes, “Failure analysis of the interval-passing algorithm for compressed sensing” IEEE Trans. Inf. Theory

•

E. Rosnes and M. Helmling, “Adaptive linear programming decoding of nonbinary linear codes over prime fields” IEEE Trans. Inf. Theory

•
  • S. Kumar, H.-Y. Lin, E. Rosnes, and A. Graell i Amat, “Achieving maximum distance separable private information retrieval capacity with linear codes” IEEE Trans. Inf. Theory, vol. 65, issue 7, 2019, p. 4243-4273
•
  • S.Kumar, A. Graell i Amat, E.Rosnes, and L.Senigagliesi, “Private information retrieval from a cellular network with caching at the edge” to appear in IEEE Trans. Commun
•
  • K.J. Hole and C. Otterstad, ”Software systems with antifragility to downtime” IEEE Computer, vol. 52, nr. 2, 2019, p. 23-31
•
  • K.J. Hole, “Dominating software systems” IEEE Software, vol. 36, no. 4, 2019, p. 81–87
•
  • K.J. Hole, and S. Ahmad, “Biologically driven AI” IEEE Computer, vol.52, no. 8, 2019, p. 72–75
•
  • 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
•
  • P. Fauzi, S. Meiklejohn, R. Mercer, and C. Orlandi, “Quisquis: A New Design for Anonymous Cryptocurrencies”, in Proc. 25th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2019), Kobe, Japan, December 8-12, 2019
•
  • A. Severinson, E. Rosnes, and A. Graell i Amat, “Coded distributed tracking” in Proc. IEEE Global Communications Conference (GLOBECOM), Waikoloa, HI, USA, Dec. 2019
•
  • S. A. Obead, H.-Y. Lin, E. Rosnes, and J. Kliewer, “On the capacity of private nonlinear computation for replicated databases” in Proc. IEEE Inf. Theory Workshop (ITW), Visby, Sweden, Aug. 2019
•
  • H.-Y. Lin, S. Kumar, E. Rosnes, and A. Graell i Amat, “Improved private information retrieval for coded storage from code decomposition” in Proc. IEEE Inf. Theory Workshop (ITW), Visby, Sweden, Aug. 2019
•
  • S. A. Obead, H.-Y. Lin, E. Rosnes, and J. Kliewer, “Private polynomial computation for noncolluding coded databases” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Paris, France, July 2019
•
  • H.-Y. Lin, S. Kumar, E. Rosnes, A. Graell i Amat, and E. Yaakobi, “Weakly-private information retrieval” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Paris, France, July 2019
•
  • S. Kumar, A. Graell i Amat, and E. Rosnes, “Private information retrieval in wireless coded caching” in Proc. 20th IEEE Int. Workshop Signal Processing Advances Wireless Commun. (SPAWC), Cannes, France, July 2019
•
  • M.Kumar, S. Varadharajan and H. Raddum, “Graphs and Self-dual additive codes over GF(4)”, in Proc. The Eleventh International Workshop on Coding and Cryptography, WCC, Saint-Jacut-de-la-Mer, France, March 31-April 5, 2019
•
  • Á. Barbero and Ø. Ytrehus, “Rate (n-1)/n systematic memory maximum distance separable convolutional codes” appear in IEEE Transactions on Information Theory, special issue in memory of Solomon W. Golomb, 2018
•
  • E. Rosnes and A. Graell i Amat, “Asymptotic analysis and spatial coupling of counter braids” IEEE Transactions on Information Theory, vol.64, issue 11, 2018, 7242-7263
•
  • C.-Y Wei, H.-Y. Lin, P.-N. Chen, Y.S. Han, and P.K. Varshney, “Target localization using sensor location knowledge in wireless sensor networks” appear in IEEE Wireless Communications Letters
•
  • H.-Y. Lin, S.M. Moser, P.N. Chen, “Weak flip codes and their optimality on the binary erasure channel” appear in IEEE Transactions on Information Theory
•
  • H. Raddum and S. Varadharajan, “Factorization using binary decision diagrams” Cryptography and Communications, Volume 11, Issue 1, pp. 1-18, 2018
•
  • H. Raddum and P. Zajac, “MRHS solver based on linear algebra and exhaustive search”, Journal of Mathematical Cryptology, Volume 12, Issue 3, pp. 143 – 157
•
  • 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
•
  • A. Severinson, A. Graell i Amat and E. Rosnes “Block-diagonal and LT codes for distributed computing with straggling servers” IEEE Transactions on Communications, vol. 67, issue 3, 2019, pp. 1739-1753
•
  • I. E. Bocharova, B. D. Kudryashov, V. Skachek, E. Rosnes and Ø. Ytrehus, ”LDPC Codes Over the BEC: Bounds and Decoding Algorithms” appear in IEEE Transactions on Communications
•
  • H.-Y. Lin and E. Rosnes, “Lengthening and extending binary private information retrieval codes” in Proc. International Zurich Seminar on Information and Communication, Zurich, Switzerland, Feb. 21–23, 2018
•
  • D. Yuan, H.-Y. Lin, J. Widmer, and M. Hollick, “Optimal joint routing and scheduling in millimeter-wave cellular networks” in Proc. 2018 IEEE International Conference on Computer Communications (INFOCOM’18), April 15–19, 2018
•
  • H.-Y. Lin, S.M. Moser, and P.-N. Chen, “The r-wise Hamming distance and its operational interpretation for block codes” in Proc. 52th Annual Conference on Information Sciences and Systems (CISS’18), Princeton University, Princeton, NJ, USA, Mar. 21–23, 2018
•
  • H.-Y. Lin, S. Kumar, E. Rosnes, and A. Graell i Amat, “An MDS-PIR capacity-achieving protocol for distributed storage using non-MDS linear codes” in Proc. IEEE International Symposium on Information Theory (ISIT 2018), Vail, CO, June 17–22, 2018
•
  • C. Boyd, G.T. Davies, K. Gjøsteen, H. Raddum, and M. Toorani, “Definitions for plaintext-existence hiding in cloud storage” in Proc. 13th International Conference on Availability, Reliability, and Security (ARES’18), University of Hamburg, Germany, Aug. 27–30, 2018
•
  • C. Boyd, G.T. Davies, K. Gjøsteen, H. Raddum, and M. Toorani, “Security notions for cloud storage and deduplication” in Proc. 12th International Conference on Provable Security (ProvSec’18), Jeju, Korea, Oct 25-28, 2018
•
  • S.A. Obead, H.-Y. Lin, E. Rosnes, and J. Kliewer, “Capacity of private linear computation for coded databases” in Proc. 56th Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL, USA, Oct. 2–5, 2018
•
  • H.-Y. Lin, S.M. Moser, and P.N. Chen, “Connections between the error probability and the r-wise Hamming distances” in Proc. International Symposium on Information Theory and Its Applications (ISITA), Oct. 28-31, 2018
•
  • H.-Y. Lin, S. Kumar, E. Rosnes, A. Graell i Amat, “Asymmetry helps: Improved private information retrieval protocols for distributed storage”, in Proc. IEEE Information Theory Workshop (ITW), Guangzhou, China, Nov. 2018
•
  • S. Kumar, H.-Y. Lin, E. Rosnes, A. Graell i Amat, “Local reconstruction codes: A class of MDS-PIR capacity-achieving codes”, in Proc. IEEE Information Theory Workshop (ITW), Guangzhou, China, Nov. 2018.
•
  • S. Chen, B. M. Kurkoski, and E. Rosnes, “Construction D’ lattices from quasi-cyclic low-density parity-check codes” in Proc. Int. Symp. Turbo Codes & Iterative Inf. Processing (ISTC), Hong Kong, China, Dec. 3–7, 2018.
•
  • 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
•
  • A. Severinson, A. Graell i Amat, E. Rosnes, Francisco Lázaro, and Gianluigi Liva “A Droplet Approach Based on Raptor Codes for Distributed Computing With Straggling Servers” in Proc. IEEE Int. Symposium on Turbo Codes & Iterative Inf. Processing, Hong Kong, Dec. 3–7, 2018.
•
  • Ø. Ytrehus,”Coding techniques for communication with low power devices over inductively coupled channels” invited talk at the Workshop on Coding and Cryptography, Munich, April 10–11, 2018
•
  • F. Armknecht, C. Boyd, G.T. Davies, K. Gjøsteen, and M. Toorani, “Side channels in deduplication: trade-offs between leakage and efficiency”, presented at the ACM Asia Conference on Computer and Communications Security (ASIACCS’17), Abu Dhabi, UAE, April 2–6, 2017
•
  • S. Kumar, E. Rosnes, and A. Graell i Amat, “Private information retrieval in distributed storage systems using an arbitrary linear code” in Proc. IEEE International Symposium on Information Theory (ISIT), Aachen, Germany, June 2017
•
  • D.G.M. Mitchell and E. Rosnes, “Edge spreading design of high rate array-based SC-LDPC codes” in Proc. IEEE International Symposium on Information Theory (ISIT), Aachen, Germany, June 2017
•
  • C.W. Otterstad, “On the effectiveness of non-readable executable memory against BROP” International Conference on Applications and Technologies in Information Security (ATIS 2017), Auckland, New Zealand, July 6–7, 2017
•
  • T. Yarygina, “Restful is not secure” International Conference on Applications and Technologies in Information Security (ATIS 2017), Auckland, New Zealand, July 6–7, 2017
•
  • H. Raddum and S. Varadharajan, “Representing integer multiplication using binary decision diagrams” Workshop on Mathematical Methods for Cryptography (MMC), Lofoten, Svolvær, Norway, Sept. 4–8, 2017
•
  • B. Greve, H. Raddum, G. Fløystad, and Ø. Ytrehus, “Eliminating variables in boolean equation systems” 2nd International Workshop on Boolean Functions and their Applications(BFA), July 3–8, 2017
•
  • B. Greve, H. Raddum, and Ø. Ytrehus, “Re-linearization and elimination of variables in boolean equation systems” Workshop on Mathematical Methods for Cryptography (MMC), Lofoten, Svolvær, Norway, Sept. 4–8, 2017
•
  • A. Severinson, A. Graell i Amat, and E. Rosnes, “Block-diagonal coding for distributed computing with straggling servers” in Proc. IEEE Inf. Theory Workshop, Kaohsiung, Taiwan, Nov. 6–10, 2017
•
  • C. Otterstad and T. Yarygina, “Low-level exploitation mitigation by diverse microservices” European Conference on Service-Oriented and Cloud Computing (ESOCC), Oslo, Norway, Sept- 27–29, 2017
•
  • Ø. Ytrehus, ”Optimum MDS convolutional codes over GF(2^m) and their relation to the trace function” invited talk at the workshop on Mathematical Methods for Cryptography(MMC), Svolvær, Norway, Sept. 4–8, 2017 (joint work with Á. Barbero)
•
  • K.J. Hole, “Building trust in e-government services” IEEE Computer, vol. 49, no. 1, 2016, p. 66–74
•
  • M. Toorani, “Cryptanalysis of a robust key agreement based on public key authentication” Journal of Security and Communication Networks, vol.9, no.1, 2016, p. 19–26
•
  • O. Lysne, K.J. Hole, C.W. Otterstad, Ø. Ytrehus, R. Aarseth, and J. Tellnes, “Vendor malware: detection limits and mitigation” IEEE Computer, vol. 49, no. 8, 2016, p. 62–69
•
  • M. Toorani, “Security analysis of the IEEE 802.15.6 standard” International Journal of Communication Systems, vol. 29, no. 17, 2016, p. 2471–2489
•
  • S. Kumar, E. Rosnes, and A. Graell i Amat, “Secure repairable fountain codes” IEEE Communications Letters, vol. 20, no. 8, 2016, p. 1491–1494
•
  • E. Rosnes and M. Helmling, “On adaptive linear programming decoding of linear codes over GF(8)” in Proc. Inf. Theory Appl. (ITA), La Jolla, CA, USA, Jan.-Feb. 2016
•
  • S. Rasoolzadeh and H. Raddum, “Cryptanalysis of PRINCE with minimal data” AfricaCrypt 2016, Lecture Notes in Computer Science vol. 9646, Springer Verlag, 2016, 109–126
•
  • S. Rasoolzadeh and H. Raddum, “Cryptanalysis of 6-round PRINCE using 2 known plaintexts” presented at ArcticCrypt 2016, Longyearbyen, Svalbard, Norway, July 17–22, 2016
•
  • E. Rosnes and M. Helmling, “Constructing valid convex hull inequalities for single parity-check codes over prime fields” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Barcelona, Spain, July 10–15, 2016
•
  • D.N.K. Jayakody and E. Rosnes, “Spatially-coupled LDPC coding in threshold-based lossy forwarding scheme” in Proc. IEEE 84th Veh. Tech. Conf. (VTC), Montréal, Canada, Sept. 2016
•
  • I.E. Bocharova, B.D. Kudryashov, E. Rosnes, V. Skachek, and Ø. Ytrehus, “Wrap-around sliding-window near-ML decoding of binary LDPC codes over the BEC” 9th International Symposium on Turbo Codes and Iterative Information Processing (ISTC), Brest, France, Sept. 5–9, 2016
•
  • E. Rosnes and M. Helmling, “On adaptive linear programming decoding of nonbinary linear codes over prime fields” in Proc. 9th Int. Symp. Turbo Codes & Iterative Inf. Processing, Brest, France, Sept. 2016
•
  • S. Rasoolzadeh and H. Raddum, “Improved multi-dimensional meet-in-the-middle cryptanalysis of KATAN” Tatra Mountains Mathematical Publication, Volume 67, 2016, pp. 149–167
•
  • S. Rasoolzadeh, “An improved truncated differential cryptanalysis of KLEIN” Central European Conference on Cryptography, Piestany, Slovakia, June 22–24, 2016
•
  • S. Rasoolzadeh and H. Raddum, “Faster key recovery attack on round-reduced PRINCE”  LightSec 2016, Lecture Notes in Computer Science 10098, pp. 3-17, 2016
•
  • Y. Yakimenka and E. Rosnes, “On failing sets of the interval-passing algorithm for compressed sensing” in Proc. 54th Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL, USA, Sept. 27–30, 2016
•
  • C.W. Otterstad, “On trends in low-level exploitation” NISK 2016, Bergen, Norway, November 29–30, 2016
•
  • M. Toorani, “Cryptanalysis of a new protocol of wide use for e-mail with perfect forward secrecy” Journal of Security and Communication Networks, vol.8, no.4, 2015, p. 694–701
•
  • O. Kazymyrov, R. Oliynykov, H. Raddum, “Influence of addition modulo 2n on algebraic attacks”, Cryptography and Communications, vol. 8, no. 2, p. 277–289
•
  • K.J. Hole, “Diversity Reduces the Impact of Malware” IEEE Security & Privacy, vol. 13, no. 3, 2015, p. 48–54
•
  • K.J. Hole, “Toward anti-fragility: a malware-halting technique” IEEE Security & Privacy, vol. 13, no. 4, 2015, p. 40–46
•
  • M. Toorani, “Cryptanalysis of two PAKE protocols for body area networks and smart environments” International Journal of Network Security, vol.17, no.5, 2015, p. 629–636
•
  • M. Toorani, “Cryptanalysis of a protocol from FC’10 (Poster Abstract)” Financial Cryptography and Data Security, LNCS 8975, Springer, 2015
•
  • M. Toorani, “On vulnerabilities of the security association in the IEEE 802.15.6 standard” Financial Cryptography and Data Security, LNCS 8976, Springer, 2015, 245–260
•
  • M. Toorani, “On continuous after-the-fact leakage-resilient key exchange” in Proc. 2nd Workshop on Cryptography and Security in Computing Systems (CS2’15)
•
  • C.W. Otterstad, “A brief evaluation of Intel®MPX” in Proc. 9th Annual IEEE InternationalSystems Conference (SysCon), Vancouver, BC, April, 2015
•
  • S. Kumar, A. Graell i Amat, I. Andriyanova, and F. Brännström, “A family of erasure correcting codes with low repair bandwidth and low repair complexity” in Proc. IEEE Global Telecommun. Conf. (GLOBECOM), San Diego, CA, USA, Dec. 2015
•
  • H. Raddum, “Algebraic Analysis of the Simon Block Cipher Family” LatinCrypt 2015, Lecture Notes in Computer Science, vol. 9230, 157–169, Springer, 2015
•
  • H. Raddum and O. Kazymyrov, “Algebraic attacks using binary decision diagrams” BalkanCryptSec 2014, Lecture Notes in Computer Science, vol. 9024, Springer, 2015
•
  • E. Rosnes and A. Graell i Amat, “Analysis of spatially-coupled counter braids” in Proc. IEEE Inf. Theory Workshop (ITW), Jeju, Korea, Oct. 2015, 133–137
•
  • E. Rosnes, “On the minimum distance of array-based spatially coupled low-density parity-check codes” IEEE International Symposium on Information Theory, 2015
•
  • E. Rosnes and M. Helmling, “On adaptive linear programming decoding of ternary linear codes” IEEE Information Theory Workshop, 2015
•
  • Á. Barbero and Ø. Ytrehus, “Network coding for cyclic networks” Mathematical Coding Theory in Multimedia Streaming, Banff, Canada, 2015
•

Á. Barbero and Ø. Ytrehus, “A coding-based approach to robust shortest-path routing” 4th Int. Castle Meeting on Coding Theory and its Applications, 2015