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
-
Efficient Succinct Zero-Knowledge Arguments in the CL Framework
J. Cryptol. 38, 1, pp. 13 (2025).
doi -
Compact Zero-Knowledge Arguments for Blum Integers
Theor. Comput. Sci. 1038, pp. 115155 (2025).
open access doi
2024
-
Fast interpolation and multiplication of unbalanced polynomials
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 -
Strassen’s algorithm is not optimally accurate
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 -
Computational Differential Privacy for Encrypted Databases Supporting Linear Queries
Proc. Priv. Enhancing Technol. 2024, 4, pp. 583–604 (2024).
doi -
Fast Secure Computations on Shared Polynomials and Applications to Private Set Operations
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 -
An Improved Threshold Homomorphic Cryptosystem Based on Class Groups
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 -
Cryptographic Accumulators: New Definitions, Enhanced Security, and Delegatable Proofs
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). -
Secure Multi-Party Linear Algebra with Perfect Correctness
IACR Commun. Cryptol. 1, 1, pp. 29 (2024).
open access doi
2023
-
VESPo: Verified Evaluation of Secret Polynomials (with application to dynamic proofs of retrievability)
Proc. Priv. Enhancing Technol. 2023, 3, pp. 354–374 (2023).
doi -
Simultaneous Rational Function Reconstruction with errors: Handling multiplicities and poles
J. Symb. Comput. 116, pp. 345–364 (2023).
doi -
Commitments with Efficient Zero-Knowledge Arguments from Subset Sum Problems
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 -
Efficient Zero-Knowledge Arguments and Digital Signatures via Sharing Conversion in the Head
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 -
I Want to Ride My BICYCL : BICYCL Implements CryptographY in CLass Groups
J. Cryptol. 36, 3, pp. 17 (2023).
doi -
Pattern Matching in Encrypted Stream from Inner Product Encryption
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 -
Bandwidth-efficient threshold EC-DSA revisited: Online/offline extensions, identifiable aborts proactive and adaptive security
Theor. Comput. Sci. 939, pp. 78–104 (2023).
doi
2022
-
Zero-Knowledge Protocols for the Subset Sum Problem from MPC-in-the-Head with Rejection
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 -
A tighter proof for CCA secure inner product functional encryption: Genericity meets efficiency
Theor. Comput. Sci. 914, pp. 84-113 (2022).
doi -
Threshold Linearly Homomorphic Encryption on Z/2kZ
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