Monika Trimoska


I am currently a postdoc at the University of Picardie Jules Verne and a member of the GOC group. Formerly, I was a PhD student working in MIS Laboratory, under the supervision of Gilles Dequen and Sorina Ionica.

My primary research interest is investigating the use of SAT solvers in cryptographic attacks on public-key cryptosystems. During my thesis, I was focused on the index calculus attack on elliptic curves defined over prime-degree extension fields in characteristic 2. Currently, I am working on the MQ problem as part of the ANR project POSTCRYPTUM.

Research interests keywords

algebraic cryptanalysis; public-key cryptography; elliptic curve discrete logarithm problem; index calculus; logical cryptanalysis (SAT); authentication; combinatorics; multivariate quadratic polynomial problem; computational supersingular isogeny problem;


PhD defense - 14th January 2021

Combinatorics in Algebraic and Logical Cryptanalysis

[manuscript][slides][video]

CV

Contact

monika [dot] trimoska [at] u-picardie [dot] fr

Education and qualifications


Qualification for a position as an assistant professor at a French University (Qualifié aux fonctions de maître de conférences),
by the French National Council of Universities
Section: Computer Science (27)
February 2021

PhD in Cryptography
University of Picardie Jules Verne, France
October 2017 – January 2021

Master’s Degree in Information Systems and Network Security
University of Picardie Jules Verne, France
September 2015 – August 2017

Licence (BSc equivalent) in Computer Science
University of Picardie Jules Verne, France
September 2012 – August 2015

Research


Publications

Journal papers

Time-Memory Analysis for Parallel Collision Search Algorithms,
with Sorina Ionica and Gilles Dequen
TCHES, Volume 2021, Issue 2
[link][slides][video]

Book chapters

HappyKidz: Privacy Preserving Phone Usage Tracking,
with Benjamin M. Case and Marcella Hastings and Siam Hussain
Protecting Privacy through Homomorphic Encryption
[link](to appear in October 2021)

International Conferences

Logical cryptanalysis with WDSat,
with Gilles Dequen and Sorina Ionica
SAT 2021
[author's version][slides][video]

Parity (XOR) Reasoning for the Index Calculus Attack,
with Sorina Ionica and Gilles Dequen
CP 2020
[author's version][slides][video]

A SAT - Based Approach for Index Calculus on Binary Elliptic Curves,
with Sorina Ionica and Gilles Dequen
Africacrypt 2020
[author's version][slides]

Artifacts

Parallel Collision Search implementation,
with Sorina Ionica and Gilles Dequen
TCHES 2021
[link]

Preprints

A Simple Deterministic Algorithm for Systems of Quadratic Polynomials over $\mathbb{F}_2$,
with Charles Bouillaguet and Claire Delaplace
[link][implementation by C. Bouillaguet]

Talks

CHES 2021
Time-Memory Analysis for Parallel Collision Search Algorithms, at the annual Conference on Cryptographic Hardware and Embedded Systems [pre-recording][live session]
13 September 2021 online

AGC2T
A SAT-based approach for index calculus on binary elliptic curves, at the Arithmetic, Geometry, Cryptography and Coding Theory Conference [slides][video]
1 June 2021 online (CIRM, Marseille Luminy, France)

Caramba Seminar
Cryptanalyse logique du problème du logarithme discret sur courbes elliptiques, at Séminaire de l'équipe Caramba (Inria Nancy) [slides]
12 March 2021 online (INRIA Nancy)

ATI Seminar
Calcul d'index pour des courbes elliptiques définies sur des extensions de corps finis, at Séminaire Arithmétique et Théorie de l’Information [slides]
18 February 2021 online (Université Aix-Maseille)

CP 2020
Parity (XOR) Reasoning for the Index Calculus Attack, at the 26th International Conference on Principles and Practice of Constraint Programming [slides][video]
9 September 2020 online (Louvain-la-Neuve, Belgium)

IMACC 2019
A SAT-based approach for index calculus on binary elliptic curves, at the 17th IMA International Conference on Cryptography and Coding [slides]
17 December 2019 St Anne’s College, University of Oxford, Oxford, UK

MSR Seminar
A SAT-based approach for index calculus on binary elliptic curves, at a seminar at the Microsoft Reasearch Lab [slides]
5 December 2019 Microsoft Research, Redmond, Washington, USA

Private AI Bootcamp
HappyKidz: Privacy Preserving Phone Usage Tracking, at Private AI Bootcamp Competition 2019 [video]
4 December 2019 Microsoft, Redmond, Washington, USA

JJCMIS 2019
Analyse de la difficulté des Cryptosystèmes à l’Aide du Problème du Transversal Minimum, at Journée des Jeunes Chercheurs du MIS 2019 [slides]
5 July 2019 Amiens, France

GT BAC
A SAT-based approach for index calculus on binary elliptic curves, at Groupe de Travail "Butte aux Cailles" [slides]
16 May 2019 l'ENST (Télécom ParisTech), Paris, France

JC2 2018
Time-Memory Trade-offs for Parallel Collision Search Algorithms, at Journées Codage & Cryptographie 2018 [slides]
11 October 2018 Centre Paul-Langevin – CAES du CNRS, Aussois, France

JJCMIS 2018
Cryptanalyse logique du problème du logarithme discret, at Journée des Jeunes Chercheurs du MIS 2018 [slides]
29 May 2018 Amiens, France

JRES 2017
A propos d'un schéma d'authentification OTP, at Journées Réseaux de l’Enseignement et de la Recherche 2017 [video]
15 November 2017 Nantes, France

JJCMIS 2017
Protocole d’authentification CrypTonAuth, at Journée des Jeunes Chercheurs du MIS 2017 [slides]
30 May 2017 Amiens, France

Other outreach materials

Diffie-Hellman key exchange with colors
Presented at a laboratory visit for students who have participated in the Alkindi cryptography competition.

Time-Memory Trade-offs for PCS Algorithms - poster in French

Le protocole d’authentification CrypTonAuth
Newsletter of MIS Laboratory, September 2017

Software

WDSat
A SAT solver dedicated to solving instances derived from a Weil descent.
[github]

PCS - Published as TCHES 2021 Artifact
Implementation of a Parallel Collision Search algorithm for solving the ECDLP.
[github]

Weil descent
A Weil descent implementation for binary elliptic curves over prime-degree extension fields.
[github]

CrypTonAuth
A C library for implementing the CrypTonAuth authentication method, prepared for ANSSI standardisation.
[proprietary]

CrypTonID
A C library for implementing the CrypTonID hashed data retrieval technology , prepared for ANSSI standardisation.
[proprietary]

Prizes and distinctions

I was part of the winning team of the Private AI Bootcamp organised by Microsoft Research (December 2019, Seattle, US).

Teaching


Courses

Object-oriented programming 2 and Reactive programming
Third year - lectures, tutorials and laboratory work (cours, TD, TP).

Advanced algorithms
Second year - tutorials and laboratory work (TD, TP).

C programming
Second year - laboratory work (TP).

Elements of formal logic and mathematical reasoning
First year - tutorials (TD).

Algorithms and programming
First year - tutorials and laboratory work (TD, TP).

Propositional logic
First year - tutorials and laboratory work (TD, TP).

Introduction to databases
First year - tutorials and laboratory work (TD, TP).

Introduction to programming
First year - tutorials and laboratory work (TD, TP).

Internet and web
First year - tutorials and laboratory work (TD, TP).

Mentoring

Master's Internship
I co-supervised, with Sorina Ionica, a student in their second year of Master's studies on the topic of computing multiple elliptic curve discrete logarithms using the Parallel collision search algorithm by van Oorschot and Wiener.

Undergraduate internship
I co-supervised, with Gilles Dequen, a student in their third year of Undergraduate studies in CS. The student was working on a commercial presentation (website, explanatory animations) of the CrypTonAuth authentication technology and on storage solutions.

Miscellaneous


  • I am a member of the Artifact Review Committee of CHES 2022.
  • I am/was an external reviewer for Crypto 2019, SAT 2021 and Latincrypt 2021.
  • I was a student member of the Research Committee of the University of Picardie Jules Verne from April 2018 to March 2020.
  • I was part of the Organising Committee of the Journée des Jeunes Chercheurs du MIS 2019 (Young Researchers of MIS Day 2019).
  • I was involved in the organisation of the JFPC/JIAF 2018 event (National Constraint Programming Days in France / National Artificial Intelligence Days in France).
  • I animated, with Sorina Ionica, a laboratory visit for primary school students who have participated in the Alkindi cryptography competition.

Other interests

When I'm not thinking about crypto problems, you can find me at the circus. I had practiced contemporary ballet for 11 years and am currently practicing aerial arts: aerial hoop, pole, trapeze & working towards getting strong enough for straps.

Icon credit (CC)