Save the Date: Charles River Crypto Day at BU in two weeks (April 18)
Canetti, Ran
Dear Charles River Dwellers:
This is a heads-up that we will be having a Charles River Crypto Day on
April 18 (two weeks from today) at BU.
Stay tuned for more information!
The Organizers
(Daniel, Eran, Henry, Ran, Vinod, Yael)
Canetti, Ran
Dear All:
The next Charles River Crypto Day will take place on April 18 (next Friday)!
Details are below.
Please take a moment to fill out this succinct RSVP, to help us plan for lunch.
Best,
Daniel, Eran, Henry, Ran, Vinod, Yael
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Location: BU CCDS building (665 Commonwealth Ave), 17th Floor
Program: (see
here for updates):
9:30-10: Gathering and breakfast
10-11: Unambiguous SNARGs for P from LWE with applications to PPAD hardness
Cody Freitag, Northeastern
11-11:30: Break
11:30-12:30: Snake-eye Resistant PKE from LWE for Oblivious Message Retrieval and Robust Encryption
Thomas Liu, Yale
12:30-1:30: Lunch (provided)
1:30-2:30: Fine-Grained Complexity in a World without Cryptography
Josh Alman, Columbia
2:30-3: Break
3-4: Matt Green, TBA
Abstracts:
Unambiguous SNARGs for P from LWE with applications to PPAD hardness
We construct the first unambiguous succinct non-interactive arguments (SNARGs) for P and incrementally verifiable computation (IVC) for P from the polynomial hardness of learning with errors (LWE). Unambiguity guarantees that it is computationally hard to find two distinct accepting proofs for the same statement. As an application, we establish PPAD hardness based on the polynomial hardness of LWE combined with a widely believed complexity assumption. Central to our approach is a new notion of rate-1 witness-unambiguous batch arguments for NP, which we construct from the polynomial hardness of LWE. Based on joint work with Liyan Chen, Zhengzhong Jin, and Daniel Wichs.
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Snake-eye Resistant PKE from LWE for Oblivious Message Retrieval and Robust Encryption
In this work, we introduce snake-eye
resistance, a new
security property for public-key encryption (PKE). This property
ensures that a
ciphertext—potentially adversarially generated—cannot decrypt to
the same
plaintext under two different secret keys. Snake-eye resistance
is particularly
useful for (1) preventing spamming attacks in oblivious message
retrieval (OMR)
and (2) enabling efficient robust encryption schemes.
We first analyze the snake-eye resistance of lattice-based PKE
schemes. Our
study reveals that while Regev05 and PVW08 satisfy this
property, more
efficient, state-of-the-art schemes like Crystals-Kyber do not.
To bridge this
gap, we propose LWEmongrass, a new lattice-based PKE scheme that
is
provably snake-eye resistant under the standard LWE assumption
while
significantly improving efficiency over Regev05 and PVW08.
Applying LWEmongrass to OMR, we achieve a 12× speedup over
existing
spamming-attack-resistant OMR schemes (conjectured in LT22 and
proven in this
work), while maintaining provable security under the LWE
assumption.
Additionally, we establish that snake-eye resistance implies
robustness,
yielding the first robust lattice-based PKE scheme that avoids
the
inefficiencies of the KEM-DEM paradigm.
As a contribution of independent interest, we introduce two LWE
variants with
side information, which serve as key building blocks in our
security proofs and
enable reductions from standard LWE for relevant parameter
settings.
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Fine-Grained Complexity in a World without Cryptography
Abstract: The study of fine-grained cryptography has proliferated in recent years due to its allure of relying on weaker assumptions compared to standard cryptography. As fine-grained cryptography only requires polynomial gaps between the adversary and honest parties, it seems plausible to build primitives relying upon popular hardness assumptions about problems in P such as k-SUM or Zero-k-Clique. The ultimate hope is that fine-grained cryptography could still be viable even if all current cryptographic assumptions are false, such as if P=NP or if we live in Pessiland where one-way functions do not exist.
In this talk, we'll consider whether this approach is viable by studying fine-grained complexity when all standard cryptographic assumptions are false. I'll present two main results. First, I'll show that many candidate hardness assumptions for building fine-grained cryptography are no longer options in Pessiland, since many popular fine-grained complexity problems are easy to solve in the average-case when one-way functions do not exist. Second, I'll show that barriers for reductions in fine-grained complexity may be explained by problems in cryptography: finding faster algorithms for computing discrete logarithms is equivalent to designing average-case equivalence between k-SUM and some natural variants.
Based on joint work with Yizhi Huang and Kevin Yeo.
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Canetti, Ran
Dear All:
This is a friendly reminder that the next Charles River Crypto Day will take place this Friday, April 18 !
See the full program below.
If you havn't yet, please take a moment to fill out this succinct RSVP, to help us plan for lunch.
Best,
Daniel, Eran, Henry, Ran, Vinod, Yael
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Location: BU CCDS building (665 Commonwealth Ave), 17th Floor
Program:
9:30-10: Gathering and breakfast
10-11: Unambiguous SNARGs for P from LWE with applications to PPAD hardness
Cody Freitag, Northeastern
11-11:30: Break
11:30-12:30: Snake-eye Resistant PKE from LWE for Oblivious Message Retrieval and Robust Encryption
Zeyu (Thomas) Liu, Yale
12:30-1:30: Lunch (provided)
1:30-2:30: Fine-Grained Complexity in a World without Cryptography
Josh Alman, Columbia
2:30-3: Break
3-4: Matt Green, New adventures in applied secret-sharing
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Abstracts:
Unambiguous SNARGs for P from LWE with applications to PPAD hardness
Cody
Freitag, Northeastern
We construct the first unambiguous succinct non-interactive arguments (SNARGs) for P and incrementally verifiable computation (IVC) for P from the polynomial hardness of learning with errors (LWE). Unambiguity guarantees that it is computationally hard to find two distinct accepting proofs for the same statement. As an application, we establish PPAD hardness based on the polynomial hardness of LWE combined with a widely believed complexity assumption. Central to our approach is a new notion of rate-1 witness-unambiguous batch arguments for NP, which we construct from the polynomial hardness of LWE. Based on joint work with Liyan Chen, Zhengzhong Jin, and Daniel Wichs.
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Snake-eye Resistant PKE from LWE for Oblivious Message Retrieval and Robust Encryption
Zeyu (Thoma) Liu, Yale
In this work, we introduce snake-eye
resistance, a new security property for public-key encryption
(PKE). This property ensures that a ciphertext—potentially
adversarially generated—cannot decrypt to the same plaintext
under two different secret keys. Snake-eye resistance is
particularly useful for (1) preventing spamming attacks in
oblivious message retrieval (OMR) and (2) enabling efficient
robust encryption schemes.
We first analyze the snake-eye resistance of lattice-based PKE
schemes. Our study reveals that while Regev05 and PVW08 satisfy
this property, more efficient, state-of-the-art schemes like
Crystals-Kyber do not. To bridge this gap, we
propose LWEmongrass, a new lattice-based PKE scheme that is
provably snake-eye resistant under the standard LWE assumption
while significantly improving efficiency over Regev05 and PVW08.
Applying LWEmongrass to OMR, we achieve a 12× speedup over
existing spamming-attack-resistant OMR schemes (conjectured in
LT22 and proven in this work), while maintaining provable
security under the LWE assumption.
Additionally, we establish that snake-eye resistance implies
robustness, yielding the first robust lattice-based PKE scheme
that avoids the inefficiencies of the KEM-DEM paradigm.
As a contribution of independent interest, we introduce two LWE
variants with side information, which serve as key building
blocks in our security proofs and enable reductions from
standard LWE for relevant parameter settings.
This is a joint work with Katerina Sotiraki, Eran Tromer, and Yunhao Wang
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Fine-Grained Complexity in a World without
Cryptography
Josh Alman, Columbia
Abstract: The study of fine-grained cryptography has proliferated in recent years due to its allure of relying on weaker assumptions compared to standard cryptography. As fine-grained cryptography only requires polynomial gaps between the adversary and honest parties, it seems plausible to build primitives relying upon popular hardness assumptions about problems in P such as k-SUM or Zero-k-Clique. The ultimate hope is that fine-grained cryptography could still be viable even if all current cryptographic assumptions are false, such as if P=NP or if we live in Pessiland where one-way functions do not exist.
In this talk, we'll consider whether this approach is viable by studying fine-grained complexity when all standard cryptographic assumptions are false. I'll present two main results. First, I'll show that many candidate hardness assumptions for building fine-grained cryptography are no longer options in Pessiland, since many popular fine-grained complexity problems are easy to solve in the average-case when one-way functions do not exist. Second, I'll show that barriers for reductions in fine-grained complexity may be explained by problems in cryptography: finding faster algorithms for computing discrete logarithms is equivalent to designing average-case equivalence between k-SUM and some natural variants.
Based on joint work with Yizhi Huang and Kevin Yeo.
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
New adventures in applied secret-sharing
Matt Green, John Hopkins
Secret sharing is one of the oldest tools in the cryptographic toolbox. Aside from its well-known applications to MPC and threshold cryptography, secret sharing has a variety of uses in privacy-preserving protocols, such as threshold PSI, traitor tracing, and privacy-preserving analytics. In this talk I will revisit the properties of secret sharing and discuss use-cases for an "anonymity" property in secret sharing schemes. At a high level, this property ensures that an insufficient set of shares (i.e., a set of shares that does not satisfy the secret sharing scheme's access structure) enjoys stronger protections than simple privacy: an adversary should be unable to determine whether a given set of shares are even associated with the same secret, or the same dealer. I will then discuss practical applications of these schemes, including stalking detection for privacy-preserving location tags (e.g., Airtags), as well as improved privacy for threshold analytics. Finally I will discuss some of the practical and theoretical results around these constructions as well as several open questions.