Sarah Bordage

I am a member of the project-team GRACE, working under the supervision of Daniel Augot and co-advised by Alain Couvreur.

My research topic relates to succinct proofs of computational integrity based on error-correcting codes.

I am particularly interested in the transparent and post-quantum flavour of zero-knowledge proof systems for computational integrity, which relies heavily on efficient proximity tests to algebraic codes.

Main interests: probabilistically checkable proofs, interactive proof systems, zero-knowledge proofs, computational complexity, algebraic techniques and locality in coding theory.

Contact: First.Last [at] {inria.fr, lix.polytechnique.fr}

Office 2039, Bâtiment Alan Turing
Campus de l'Ecole Polytechnique
91120 Palaiseau Cedex - France

I am not a pirat.

* This action benefits from the support of the Chair "Blockchain & B2B Platforms", led by l’X – Ecole Polytechnique and the Fondation de l’Ecole Polytechnique, sponsored by Capgemini.


Research

"How can we ever trust results computed by a third-party without recomputing them?"

Verifiable computing (VC) schemes enable a weak client to oursource an heavy computation to an untrusted and powerful server. To convince the client that the computation has been run correctly, the server provides along with the result a proof of computational integrity. This proof is expected to be both short and easy to verify. By verifying this proof, the weak client is able to verify the correctness of the returned result, without having to run the calculation again.

The problem of securely delegating computations has immediate real-world applications, since outsourcing large computational tasks to a remote server is quite common today, e.g. in cloud computing. A less well-known problem solved by some special VC schemes is that raised by cryptocurrencies and blockchains. For instance, in pricacy-preserving cryptocurrencies such as Zcash, it is required to verify the validity of transactions according to the network’s consensus rules without revealing what the transactions are. In this context, the issue is addressed by zero-knowledge proofs for generic computations.

In the past few years, proofs-based verifiable computation has gained increasing attention not only from the theoretical computer science community, but also from people directly interested in real-world applications and deployed implementations.

Preprints

  • Interactive Oracle Proofs of Proximity to Algebraic Geometry Codes
    with Jade Nardi [Submitted]

    ECCC ArXiv

Publications


Talks

  • June 17, 2021

    Efficient proofs of computational integrity from code-based IOPs
    at Groupe de travail Codes et Cryptographie, Inria de Paris [slides]

  • May 20, 2021

    Introduction to Zero-Knowledge Proofs
    at Blockchain & B2B Platforms Working Group, Ecole Polytechnique [slides]

  • December 8 & 15, 2020

    Efficient proofs of computational integrity from code-based IOPs
    at Groupe de travail GRACE, Inria Saclay & LIX

  • November 19, 2020

    IOP of Proximity to Algebraic Geometry Codes (Joint talk with Jade Nardi)
    at StarkWare Industries [slides]

  • November 6, 2020

    Proofs of Proximity for Tensored Reed-Solomon codes and Reed-Muller codes
    at Journées Codage et Cryptographie, virtual conference

  • March 3, 2020

    How to verify a proof without reading it, and applications to verifiable computing
    at Grace young seminar


Teaching at Ecole Polytechnique

Advanced Cryptology

INF568 - Tutorials
2018-19, 2019-20, 2020-21

Algorithms for Data Analysis in C++

INF442 - Tutorials
2018-19, 2019-20

Les bases de la programmation et de l'algorithmique

INF411 - Tutorials & INF411T - Tutoring
2020-21

Supervision

CSE303: 3rd year Bachelor Computer Science Project
2020-21

Miscealleneous

Past internships

  • Multiparty computation protocols secure against covert adversaries at Inria Saclay, France

    April - August 2018, supervised by Daniel Augot and Matthieu Rambaud

  • Assessment of password cracking software and hardware at Cyberens Technologies & Services

    June - August 2017

Fete de la science at Inria Saclay

October 10-11, 2019
Volunteer

Grace Young Seminar

Co-organizer


Education

Master degree in Cryptology and Cybersecurity

University of Bordeaux, France
2016 - 2018

Bachelor degree in Pure Mathematics

University of Nantes, France
2013 - 2016