SANGRIA

Secure distributed computAtioN - cryptoGRaphy, combinatorIcs and computer Algebra
ANR (2021-2025)

Research project funded by the french Agence Nationale de la Recherche (2021-2026). ANR-21-CE39-0006

Partners


  • École normale supérieure / DI-ENS
  • École polytechnique / LIX
  • Sorbonne Université / LIP6 and IMJ
  • Télécom Paris / LTCI
  • Université de Bordeaux / IMB
  • Université Grenoble Alpes / LJK
  • Université de Montpellier / LIRMM
  • Beginning and duration of the scientific project: October 2021 - 60 Months
  • Project coordinator: Damien Vergnaud


Project Summary


Cryptology is a crucial and ubiquitous component of cybersecurity. The development of information technology has brought great convenience to our lives but require cryptographic methods that go far beyond basic secure communication (i.e. confidentiality, integrity or authentication). The amount of sensitive data stored in digital form has grown tremendously and we now store and process them daily on nomad devices as well as in the cloud. This comes with many novel attack surfaces. Managing and protecting personal, financial or medical data is challenging and seems impossible for users with current tools.

Secure distributed computation has long stood in the realm of theoretical cryptography but it was known to have the potential to provide a disruptive change for practical security solutions. The concept was introduced by Yao in the 1980s and it allows mutually distrusting parties to run joint computations without disclosing any participant’s private inputs. New cryptographic tools have been invented in recent years (e.g. fully-homomorphic encryption, functional encryption, succinct proof systems...). These constructions have opened the door to applications that were previously believed unattainable in practice (e.g. Cloud Computing, Big Data, Blockchain or the Internet of Things). There is currently a strong interest in secure distributed computation from governments and security organisations (in particular the National Institute of Standards and Technology (NIST)), military, academia and industry. We are close to the stage where the secure distributed computation protocols can be applied to real-world security issues. We now list the main scientific challenges in the project.

The main scientific challenges are (1) to construct specific protocols that take into account practical constraints and prove them secure, (2) to implement them and to improve the efficiency of existing protocols significantly. The SANGRIA project (for Secure distributed computAtioN: cryptoGRaphy, combinatorIcs and computer Algebra) aims to undertake research in these two aspects while combining research from cryptography, combinatorics and computer algebra. It is expected to impact central problems in secure distributed computation, while enriching the general landscape of cryptography.

Publications


2025

  1. Efficient Succinct Zero-Knowledge Arguments in the CL Framework
    Agathe Beaugrand, Guilhem Castagnos, and Fabien Laguillaumie
    J. Cryptol. 38, 1, pp. 13 (2025).
    doi
  2. Compact Zero-Knowledge Arguments for Blum Integers
    Jules Maire, and Damien Vergnaud
    Theor. Comput. Sci. 1038, pp. 115155 (2025).
    open access doi

2024

  1. Fast interpolation and multiplication of unbalanced polynomials
    Pascal Giorgi, Bruno Grenet, Armelle Perret Cray, and Daniel S. Roche
    In Proceedings of the 2024 International Symposium on Symbolic and Algebraic Computation, ISSAC 2024, Raleigh, NC, USA, July 16-19, 2024 (Jonathan D. Hauenstein, Wen-shin Lee, and Shaoshi Chen, eds), ACM, pp. 437–446 (2024).
    doi
  2. Strassen’s algorithm is not optimally accurate
    Jean-Guillaume Dumas, Clément Pernet, and Alexandre Sedoglavic
    In Proceedings of the 2024 International Symposium on Symbolic and Algebraic Computation, ISSAC 2024, Raleigh, NC, USA, July 16-19, 2024 (Jonathan D. Hauenstein, Wen-shin Lee, and Shaoshi Chen, eds), ACM, pp. 254–263 (2024).
    doi
  3. Computational Differential Privacy for Encrypted Databases Supporting Linear Queries
    Ferran Alborch Escobar, Sébastien Canard, Fabien Laguillaumie, and Duong Hieu Phan
    Proc. Priv. Enhancing Technol. 2024, 4, pp. 583–604 (2024).
    doi
  4. Fast Secure Computations on Shared Polynomials and Applications to Private Set Operations
    Pascal Giorgi, Fabien Laguillaumie, Lucas Ottow, and Damien Vergnaud
    In 5th Conference on Information-Theoretic Cryptography, ITC 2024, August 14-16, 2024, Stanford, CA, USA (Divesh Aggarwal, ed), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, LIPIcs, vol. 304, pp. 11:1–11:24 (2024).
    doi
  5. An Improved Threshold Homomorphic Cryptosystem Based on Class Groups
    Lennart Braun, Guilhem Castagnos, Ivan Damgård, Fabien Laguillaumie, Kelsey Melissaris, Claudio Orlandi, and Ida Tucker
    In Security and Cryptography for Networks - 14th International Conference, SCN 2024, Amalfi, Italy, September 11-13, 2024, Proceedings, Part II (Clemente Galdi, and Duong Hieu Phan, eds), Springer, Lecture Notes in Computer Science, vol. 14974, pp. 24–46 (2024).
    doi
  6. Cryptographic Accumulators: New Definitions, Enhanced Security, and Delegatable Proofs
    Anaı̈s Barthoulot, Olivier Blazy, and Sébastien Canard
    In Progress in Cryptology - AFRICACRYPT 2024 - 15th International Conference on Cryptology in Africa, Douala, Cameroon, July 10-12, 2024, Proceedings (Serge Vaudenay, and Christophe Petit, eds), Springer, Lecture Notes in Computer Science, vol. 14861, pp. 94–119 (2024).
  7. Secure Multi-Party Linear Algebra with Perfect Correctness
    Jules Maire, and Damien Vergnaud
    IACR Commun. Cryptol. 1, 1, pp. 29 (2024).
    open access doi

2023

  1. VESPo: Verified Evaluation of Secret Polynomials (with application to dynamic proofs of retrievability)
    Jean-Guillaume Dumas, Aude Maignan, Clément Pernet, and Daniel S. Roche
    Proc. Priv. Enhancing Technol. 2023, 3, pp. 354–374 (2023).
    doi
  2. Simultaneous Rational Function Reconstruction with errors: Handling multiplicities and poles
    Eleonora Guerrini, Kamel Lairedj, Romain Lebreton, and Ilaria Zappatore
    J. Symb. Comput. 116, pp. 345–364 (2023).
    doi
  3. Commitments with Efficient Zero-Knowledge Arguments from Subset Sum Problems
    Jules Maire, and Damien Vergnaud
    In Computer Security - ESORICS 2023 - 28th European Symposium on Research in Computer Security, The Hague, The Netherlands, September 25-29, 2023, Proceedings, Part I (Gene Tsudik, Mauro Conti, Kaitai Liang, and Georgios Smaragdakis, eds), Springer, Lecture Notes in Computer Science, vol. 14344, pp. 189–208 (2023).
    open access doi
  4. Efficient Zero-Knowledge Arguments and Digital Signatures via Sharing Conversion in the Head
    Jules Maire, and Damien Vergnaud
    In Computer Security - ESORICS 2023 - 28th European Symposium on Research in Computer Security, The Hague, The Netherlands, September 25-29, 2023, Proceedings, Part I (Gene Tsudik, Mauro Conti, Kaitai Liang, and Georgios Smaragdakis, eds), Springer, Lecture Notes in Computer Science, vol. 14344, pp. 435–454 (2023).
    doi
  5. I Want to Ride My BICYCL : BICYCL Implements CryptographY in CLass Groups
    Cyril Bouvier, Guilhem Castagnos, Laurent Imbert, and Fabien Laguillaumie
    J. Cryptol. 36, 3, pp. 17 (2023).
    doi
  6. Pattern Matching in Encrypted Stream from Inner Product Encryption
    Elie Bouscatié, Guilhem Castagnos, and Olivier Sanders
    In Public-Key Cryptography - PKC 2023 - 26th IACR International Conference on Practice and Theory of Public-Key Cryptography, Atlanta, GA, USA, May 7-10, 2023, Proceedings, Part I (Alexandra Boldyreva, and Vladimir Kolesnikov, eds), Springer, Lecture Notes in Computer Science, vol. 13940, pp. 774–801 (2023).
    open access doi
  7. Bandwidth-efficient threshold EC-DSA revisited: Online/offline extensions, identifiable aborts proactive and adaptive security
    Guilhem Castagnos, Dario Catalano, Fabien Laguillaumie, Federico Savasta, and Ida Tucker
    Theor. Comput. Sci. 939, pp. 78–104 (2023).
    doi

2022

  1. Zero-Knowledge Protocols for the Subset Sum Problem from MPC-in-the-Head with Rejection
    Thibauld Feneuil, Jules Maire, Matthieu Rivain, and Damien Vergnaud
    In Advances in Cryptology - ASIACRYPT 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, December 5-9, 2022, Proceedings (Shweta Agrawal, and Dongdai Lin, eds), Springer, Lecture Notes in Computer Science, vol. to appear, (2022).
    open access
  2. A tighter proof for CCA secure inner product functional encryption: Genericity meets efficiency
    Guilhem Castagnos, Fabien Laguillaumie, and Ida Tucker
    Theor. Comput. Sci. 914, pp. 84-113 (2022).
    doi
  3. Threshold Linearly Homomorphic Encryption on Z/2kZ
    Guilhem Castagnos, Fabien Laguillaumie, and Ida Tucker
    In Advances in Cryptology - ASIACRYPT 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, December 5-9, 2022, Proceedings, Part II (Shweta Agrawal, and Dongdai Lin, eds), Springer, Lecture Notes in Computer Science, vol. 13792, pp. 99–129 (2022).
    doi



(pictures credit: upklyak / Freepik)