Chris Brzuska
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Chris Brzuska has a total of 55 co-authors. Here are the top co-authors by number of shared publications:
Geoffroy Couteau
CNRS, IRIF, Université de Paris, Paris, France
3 shared publications- Geoffroy Couteau
Université Paris Cité, CNRS, IRIF
2 shared publications - Ivy K. Y. Woo
Aalto University
2 shared publications - Markulf Kohlweiss
University of Edinburgh and Input Output
2 shared publications - Akin Ünal
ISTA
1 shared publication - Aleksi Kalsta
VTT Technical Research Centre of Finland
1 shared publication
Latest Publications
- Open Access
- 5 June 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Programming Languages and Systems
- Vol. 48 (2) , 1-64
Project Everest: Perspectives from Developing Industrial-Grade High-Assurance Software
Project Everest began at Microsoft Research in 2016, aiming to spur research in program verification to produce industrial-grade software. In collaboration with INRIA and Carnegie Mellon University, Project Everest’s goal was to produce drop-in verified replacements of secure communications software used in the HTTPS ecosystem, including TLS, the underlying cryptography, and related subprotocols. Now, almost a decade later, we reflect on the project, sharing both its successes and failures, and look ahead to the next decade of program verification research.
- 5 June 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Programming Languages and Systems
- Vol. 48 (2) , 1-64
Open AccessProject Everest: Perspectives from Developing Industrial-Grade High-Assurance Software
Project Everest began at Microsoft Research in 2016, aiming to spur research in program verification to produce industrial-grade software. In collaboration with INRIA and Carnegie Mellon University, Project Everest’s goal was to produce drop-in verified replacements of secure communications software used in the HTTPS ecosystem, including TLS, the underlying cryptography, and related subprotocols. Now, almost a decade later, we reflect on the project, sharing both its successes and failures, and look ahead to the next decade of program verification research.
- 24 May 2026
- Published by Springer Nature
- p. 162-197
Threshold Public-Key Encryption: Definitions, Relations, and CPA-to-CCA Transforms
- 24 May 2026
- Published by Springer Nature
- p. 162-197
Threshold Public-Key Encryption: Definitions, Relations, and CPA-to-CCA Transforms
- 22 May 2026
- Published by Springer Nature
- p. 510-543
Simple Attacks Against (Extended) Fiat-Shamir
- Open Access
- 17 August 2025
- Published by Springer Nature
- p. 628-662
Succinct PPRFs via Memory-Tight Reductions
- 17 August 2025
- Published by Springer Nature
- p. 628-662
Open AccessSuccinct PPRFs via Memory-Tight Reductions
- Open Access
- 8 April 2025
- Published by International Association for Cryptologic Research in IACR Communications in Cryptology
- Vol. 2 (1)
Relations Among New CCA Security Notions for Approximate FHE
In a recent Eurocrypt'24 paper, Manulis and Nguyen have proposed a new CCA security notion, vCCA, and associated construction blueprints to leverage both CPA-secure and correct FHE beyond the CCA1 security barrier. However, because their approach is only valid under the correctness assumption, it leaves a large part of the FHE spectrum uncovered, as many FHE schemes used in practice turn out to be approximate and, as such, do not satisfy the correctness assumption. In this paper, we improve their work by defining and investigating a variant of their security notion which is suitable for a more general case where approximate FHE are included. As the passive security of approximate FHE schemes is more appropriately captured by CPAD rather than CPA security, we start from the former notion to define our vCCAD new security notion. Although we show that vCCA and vCCAD are equivalent when the correctness assumption holds, we establish that vCCAD security is strictly stronger than vCCA security in the general case. In doing so, we interestingly establish several new separation results between variants of CPAD security of increasing strength. This allows us to clarify the relationship between vCCA security and CPAD security, and to reveal that the security notions landscape is much simpler for correct FHE than when approximate ones are included — in which case, for example, we establish that multiple challenges security notions are strictly stronger than single-challenge ones for both CPAD and vCCAD security. Lastly, we also give concrete construction blueprints, showing how to leverage some of the blueprints proposed by Manulis and Nguyen to achieve vCCAD security. As a result, vCCAD security is the strongest CCA security notion known so far to be achievable by both correct and approximate FHE schemes.
- 8 April 2025
- Published by International Association for Cryptologic Research in IACR Communications in Cryptology
- Vol. 2 (1)
Open AccessRelations Among New CCA Security Notions for Approximate FHE
In a recent Eurocrypt'24 paper, Manulis and Nguyen have proposed a new CCA security notion, vCCA, and associated construction blueprints to leverage both CPA-secure and correct FHE beyond the CCA1 security barrier. However, because their approach is only valid under the correctness assumption, it leaves a large part of the FHE spectrum uncovered, as many FHE schemes used in practice turn out to be approximate and, as such, do not satisfy the correctness assumption. In this paper, we improve their work by defining and investigating a variant of their security notion which is suitable for a more general case where approximate FHE are included. As the passive security of approximate FHE schemes is more appropriately captured by CPAD rather than CPA security, we start from the former notion to define our vCCAD new security notion. Although we show that vCCA and vCCAD are equivalent when the correctness assumption holds, we establish that vCCAD security is strictly stronger than vCCA security in the general case. In doing so, we interestingly establish several new separation results between variants of CPAD security of increasing strength. This allows us to clarify the relationship between vCCA security and CPAD security, and to reveal that the security notions landscape is much simpler for correct FHE than when approximate ones are included — in which case, for example, we establish that multiple challenges security notions are strictly stronger than single-challenge ones for both CPAD and vCCAD security. Lastly, we also give concrete construction blueprints, showing how to leverage some of the blueprints proposed by Manulis and Nguyen to achieve vCCAD security. As a result, vCCAD security is the strongest CCA security notion known so far to be achievable by both correct and approximate FHE schemes.
- 13 December 2024
- Published by Springer Nature
- p. 418-449
Evasive LWE Assumptions: Definitions, Classes, and Counterexamples
- 13 December 2024
- Published by Springer Nature
- p. 418-449
Evasive LWE Assumptions: Definitions, Classes, and Counterexamples
- Open Access
- 4 December 2024
- Published by Springer Nature in Journal of Cryptology
- Vol. 38 (1) , 1-70
On Building Fine-Grained One-Way Functions from Strong Average-Case Hardness
Constructing one-way functions from average-case hardness is a long-standing open problem. A positive result would exclude Pessiland (Impagliazzo ’95) and establish a highly desirable win–win situation: either (symmetric) cryptography exists unconditionally, or all $$\textsf{NP} $$ problems can be solved efficiently on the average. Motivated by the lack of progress on this seemingly very hard question, we initiate the investigation of weaker yet meaningful candidate win–win results of the following type: either there are fine-grained one-way functions (FGOWF), or non-trivial speedups can be obtained for all $$\textsf{NP} $$ problems on the average. FGOWFs only require a fixed polynomial gap (as opposed to superpolynomial) between the running time of the function and the running time of an inverter. We obtain three main results: Construction. We show that if there is an $$\textsf{NP} $$ language having a very strong form of average-case hardness, which we call block finding hardness, then FGOWF exist. We provide heuristic support for this very strong average-case hardness notion by showing that it holds for a random language. Then, we study whether weaker (and more natural) forms of average-case hardness could already suffice to obtain FGOWF and obtain two negative results: Separation I. We provide a strong oracle separation for the implication ( $$\exists $$ exponentially average-case hard $$\textsf{NP} $$ language $$\implies $$ $$\exists $$ FGOWF). Separation II. We provide a second strong negative result for an even weaker candidate win–win result. Namely, we rule out a relativizing proof for the implication ( $$\exists $$ exponentially average-case $$\textsf{NP} $$ hard language whose hardness amplifies optimally through parallel repetitions $$\implies $$ $$\exists $$ FGOWF). This separation forms the core technical contribution of our work.- 4 December 2024
- Published by Springer Nature in Journal of Cryptology
- Vol. 38 (1) , 1-70
Open AccessOn Building Fine-Grained One-Way Functions from Strong Average-Case Hardness
Constructing one-way functions from average-case hardness is a long-standing open problem. A positive result would exclude Pessiland (Impagliazzo ’95) and establish a highly desirable win–win situation: either (symmetric) cryptography exists unconditionally, or all $$\textsf{NP} $$ problems can be solved efficiently on the average. Motivated by the lack of progress on this seemingly very hard question, we initiate the investigation of weaker yet meaningful candidate win–win results of the following type: either there are fine-grained one-way functions (FGOWF), or non-trivial speedups can be obtained for all $$\textsf{NP} $$ problems on the average. FGOWFs only require a fixed polynomial gap (as opposed to superpolynomial) between the running time of the function and the running time of an inverter. We obtain three main results: Construction. We show that if there is an $$\textsf{NP} $$ language having a very strong form of average-case hardness, which we call block finding hardness, then FGOWF exist. We provide heuristic support for this very strong average-case hardness notion by showing that it holds for a random language. Then, we study whether weaker (and more natural) forms of average-case hardness could already suffice to obtain FGOWF and obtain two negative results: Separation I. We provide a strong oracle separation for the implication ( $$\exists $$ exponentially average-case hard $$\textsf{NP} $$ language $$\implies $$ $$\exists $$ FGOWF). Separation II. We provide a second strong negative result for an even weaker candidate win–win result. Namely, we rule out a relativizing proof for the implication ( $$\exists $$ exponentially average-case $$\textsf{NP} $$ hard language whose hardness amplifies optimally through parallel repetitions $$\implies $$ $$\exists $$ FGOWF). This separation forms the core technical contribution of our work. - 2 December 2024
- Published by Springer Nature
- p. 287-318
On Bounded Storage Key Agreement and One-Way Functions
- 2 December 2024
- Published by Springer Nature
- p. 287-318
On Bounded Storage Key Agreement and One-Way Functions
- 10 September 2024
- Published by Springer Nature
- p. 97-116
Instantiating the Hash-Then-Evaluate Paradigm: Strengthening PRFs, PCFs, and OPRFs
- 10 September 2024
- Published by Springer Nature
- p. 97-116
Instantiating the Hash-Then-Evaluate Paradigm: Strengthening PRFs, PCFs, and OPRFs
- Open Access
- 8 July 2024
- Published by International Association for Cryptologic Research in IACR Communications in Cryptology
- Vol. 1 (2)
Simple Watermarking Pseudorandom Functions from Extractable Pseudorandom Generators
Watermarking pseudorandom functions (PRF) allow an authority to embed an unforgeable and unremovable watermark into a PRF while preserving its functionality. In this work, we extend the work of Kim and Wu [Crypto'19] who gave a simple two-step construction of watermarking PRFs from a class of extractable PRFs satisfying several other properties – first construct a mark-embedding scheme, and then upgrade it to a message-embedding scheme. While the message-embedding scheme of Kim and Wu is based on complex homomorphic evaluation techniques, we observe that much simpler constructions can be obtained and from a wider range of assumptions, if we forego the strong requirement of security against the watermarking authority. Concretely, we introduce a new notion called extractable PRGs (xPRGs), from which extractable PRFs (without security against authorities) suitable for the Kim-Wu transformations can be simply obtained via the Goldreich-Goldwasser-Micali (GGM) construction. We provide simple constructions of xPRGs from a wide range of assumptions such as hardness of computational Diffie-Hellman (CDH) in the random oracle model, as well as LWE and RSA in the standard model.
- 8 July 2024
- Published by International Association for Cryptologic Research in IACR Communications in Cryptology
- Vol. 1 (2)
Open AccessSimple Watermarking Pseudorandom Functions from Extractable Pseudorandom Generators
Watermarking pseudorandom functions (PRF) allow an authority to embed an unforgeable and unremovable watermark into a PRF while preserving its functionality. In this work, we extend the work of Kim and Wu [Crypto'19] who gave a simple two-step construction of watermarking PRFs from a class of extractable PRFs satisfying several other properties – first construct a mark-embedding scheme, and then upgrade it to a message-embedding scheme. While the message-embedding scheme of Kim and Wu is based on complex homomorphic evaluation techniques, we observe that much simpler constructions can be obtained and from a wider range of assumptions, if we forego the strong requirement of security against the watermarking authority. Concretely, we introduce a new notion called extractable PRGs (xPRGs), from which extractable PRFs (without security against authorities) suitable for the Kim-Wu transformations can be simply obtained via the Goldreich-Goldwasser-Micali (GGM) construction. We provide simple constructions of xPRGs from a wide range of assumptions such as hardness of computational Diffie-Hellman (CDH) in the random oracle model, as well as LWE and RSA in the standard model.