International Association
for Cryptologic Research

In this work, we are concerned with the hardening of post-quantum key encapsulation mechanisms (KEM) against side-channel attacks, with a focus on the comparison operation required for the Fujisaki-Okamoto (FO) transform. We identify critical vulnerabilities in two proposals for masked comparison and successfully attack the masked comparison algorithms from TCHES 2018 and TCHES 2020. To do so, we use first-order side-channel attacks and show that the advertised security properties do not hold. Additionally, we break the higher-order secured masked comparison from TCHES 2020 using a collision attack, which does not require side-channel information. To enable implementers to spot such flaws in the implementation or underlying algorithms, we propose a framework that is designed to test the re-encryption step of the FO transform for information leakage. Our framework relies on a specifically parametrized $t$-test and would have identified the previously mentioned flaws in the masked comparison. Our framework can be used to test both the comparison itself and the full decapsulation implementation.

ForkAE is a family of authenticated encryption (AE) schemes using a forkcipher as a building block. ForkAE was published in Asiacrypt'19 and is a second-round candidate in the NIST lightweight cryptography process. ForkAE comes in several modes of operation: SAEF, PAEF, and rPAEF. SAEF is optimized for authenticated encryption of short messages and processes the message blocks in a sequential and online manner. SAEF requires a smaller internal state than its parallel sibling PAEF and is better fitted for devices with smaller footprint. At SAC 2020 it was shown that SAEF is also an online nonce misuse-resistant AE (OAE) and hence offers enhanced security against adversaries that make blockwise adaptive encryption queries. It has remained an open question if SAEF resists attacks against blockwise adaptive decryption adversaries, or more generally when the decrypted plaintext is released before the verification (RUP).

RUP security is a particularly relevant security target for lightweight (LW) implementations of AE schemes on memory-constrained devices or devices with stringent real-time requirements. Surprisingly, very few NIST lightweight AEAD candidates come with any provable guarantees against RUP. In this work, we show that the SAEF mode of operation of the ForkAE family comes with integrity guarantees in the RUP setting. The RUP integrity (INT-RUP) property was defined by Andreeva et~al.~in Asiacrypt'14. Our INT-RUP proof is conducted using the coefficient H technique and it shows that, without any modifications, SAEF is INT-RUP secure up to the birthday bound, i.e., up to $2^{n/2}$ processed data blocks, where $n$ is the block size of the forkcipher. The implication of our work is that SAEF is indeed RUP secure in the sense that the release of unverified plaintexts will not impact its ciphertext integrity.

Universal Composability Summer Intern Beavercreek, Ohio Riverside Research’s Trusted and Resilient Systems research group is conducting cutting edge research in applying formal methods for system security analysis. This innovative research will help transform how we design and build high assurance, complex systems. We are seeking a motivated researcher (ideally in a PhD program) who has experience with the Universal Composability framework to join our team for the summer and help us tackle some interesting and challenging problems. The individual who fills this role will work with top researchers in secure system design and cryptography to explore the art of the possible in analyzing complex systems using Universal Composability. All positions with Riverside Research require U.S. citizenship. Job Duties: • Conduct literature reviews • Scope and define challenging research problems in the area of Universal Composability • Conduct research with a small, dynamic team • Publish results in a top security conference • Other duties as assigned Required Qualifications: • U.S. Citizenship • Enrolled in a degree seeking program (ideally PhD) in fields such as Computer Science, Computer Engineering, Electrical Engineering, Mathematics • Previous experience with Universal Composability • Ability to work independently and with a team • Superior written and verbal communications skills Desired Qualifications: • Previous publications using Universal Composability (especially if applied to systems beyond traditional cryptographic protocols) • Understanding of Open Architecture systems Riverside Research strives to be one of America's premier providers of independent, trusted technical and scientific expertise. We continue to add experienced and technically astute staff who are highly motivated to help our DoD and Intelligence Community (IC) customers deliver world class programs. As a not-for-profit, technology-oriented defense company, we believe service to customers and s

Closing date for applications:

Contact: Eileen Norton, Sr. Recruiter, Riverside Research, enorton@riversideresearch.org Dr. Michael Clark, Associate Director, Trusted and Resilient Systems, Riverside Research Open Innovation Center, IACR Member

More information: https://boards.greenhouse.io/riversideresearch/jobs/4347155003

The Zcash Foundation is a 501(c)(3) nonprofit, public charity that builds and supports privacy infrastructure for the public good. We work on strengthening financial privacy with technology, focused on the Zcash protocol and blockchain.

We’re looking for someone who is as excited as we are about building private financial infrastructure for the public good, and we take that task very seriously.

The role as a cryptography engineer within the core Zcash Foundation team will be responsible for building cryptographic protocols as well as distributed systems. The ideal candidate embodies the Foundation’s values, while fully aligning with its mission and goals.

Engineers at the Zcash Foundation are responsible for implementing the core Zcash protocol, maintaining deployed software, fixing bugs, and identifying improvements to the protocol for the future. Other duties include writing about our work and interfacing with external stakeholders such as those who use our software and interoperable implementations of the Zcash protocol. The position reports to the Zcash Foundation’s engineering manager.

Zcash Foundation Core Engineering Projects: Currently the engineering team is working on Zebra, an independent implementation of the Zcash protocol written in Rust, and soon we will dedicate resources to building out Zcash wallet functionality.

Closing date for applications:

Contact: Submit application here: https://docs.google.com/forms/d/e/1FAIpQLSelpDkmqjgVgiTfVFukB9TbIoIExWxVDHn0VvnSboO4nJIN1A/viewform

More information: https://www.zfnd.org/blog/open-position-cryptography-engineer/

The Cryptanalysis Taskforce at Nanyang Technological University in Singapore led by Prof. Jian Guo is seeking for candidates to fill 3 Post-doctoral Research Fellow (or Senior Research Fellows with more than 5 years post PhD research experience) positions on symmetric-key cryptography, including but not limited to the following sub-areas:

• tool aided cryptanalysis, such as MILP, CP, STP, and SAT
• machine learning aided cryptanalysis and designs
• privacy-preserving friendly symmetric-key designs
• quantum cryptanalysis
• theory and proof
• cryptanalysis against SHA-2, SHA-3, and AES

Established in 2014, the Cryptanalysis Taskforce is a group dedicated for cutting edge research in symmetric-key cryptography. Since then, the team has been active in both publications in and services for IACR. It has done quite some cryptanalysis work on various important targets such as SHA-3, AES, function graph, TBC designs etc, and continues its works in the areas mentioned above, with strong funding support from the university and government agencies in Singapore. We offer competitive salary package with extremely low tax, as well as excellent environment dedicating for research in Singapore. The contract will be initially for 1 year, and has the possibility to be extended. Candidates are expected to have proven record of publications in IACR conferences. Interested candidates are to send their CV and 2 reference letters to Jian Guo. Review of applicants will start immediately until the positions are filled. More information about the Cryptanalysis Taskforce research group can be found via http://team.crypto.sg

Closing date for applications:

Contact: Asst Prof. Jian Guo, guojian@ntu.edu.sg

More information: http://team.crypto.sg

Job Title Embedded Cryptography Expert- QUALCOMM (France) Post Date October 2020 Company - Division Qualcomm Technologies, Inc. - CDMA Technology Job Area Engineering - Security Location France – Sophia Antipolis Job Overview: In this position you will perform tasks like these: • Define HW crypto security requirements (Functional, Performance, Security level) • Define HW/SW partitioning to address next challenge in cryptography (PQC, Crypto Agility) • Define and architect Crypto HW IP blocks that contributes to the overall SoC Security ArchitectureArchitecture and design of state-of-the-art mechanisms thwarting physical attacks • Monitor evaluation of crypto IP resistance and robustness • Competitive analysis of security IPs and features • Investigate future/roadmap security related technologies • Participation to academic conference and industrial/research security working group

Closing date for applications:

Contact: avial@qti.qualcomm.com

More information: https://qualcomm.wd5.myworkdayjobs.com/External/job/Sophia-Antipolis/Crypto-Expert---Sophia-Antipolis--France_3004178

Advanced Encryption Standard used with Galois Counter Mode, mode of operation is one of the the most secure modes to use the AES. This paper represents an overview of the AES modes focusing the AES-GCM mode and its particularities. Moreover, after a detailed analysis of the possibility of enhancement for the encryption and authentication phase, a method of generating custom encryption schemes based on GF($2^8$) irreducible polynomials different from the standard polynomial used by the AES-GCM mode is provided. Besides the polynomial customization, the solution proposed in this paper offers the possibility to determine, for each polynomial, the constants that can be used in order to keep all the security properties of the algorithm. Using this customization method, allows changing the encryption schemes over a period of time without interfering with the process, bringing a major improvement from the security point of view by avoiding pattern creation. Furthermore, this paper sets the grounds for implementing authentication enhancement using a similar method to determine the polynomials that can be used instead of the default authentication polynomial, without changing the algorithm strength at all.

The progress on constructing quantum computers and the ongoing standardization of post-quantum cryptography (PQC) have led to the development and refinement of promising new digital signature schemes and key encapsulation mechanisms (KEM). Especially lattice-based schemes have gained some popularity in the research community, presumably due to acceptable key, ciphertext, and signature sizes as well as good performance results and cryptographic strength. However, in some practical applications like smart cards, it is also crucial to secure cryptographic implementations against side-channel and fault attacks. In this work, we analyze the so-called redundant number representation (RNR) that can be used to counter side-channel attacks. We show how to avoid security issues with the RNR due to unexpected de-randomization and we apply it to the Kyber KEM and show that the RNR has a very low overhead. We then verify the RNR methodology by practical experiments, using the non-specific t-test methodology and the ChipWhisperer platform. Furthermore, we present a novel countermeasure against fault attacks based on the Chinese remainder theorem (CRT). On an ARM Cortex-M4, our implementation of the RNR and fault countermeasure offers better performance than masking and redundant calculation. Our methods thus have the potential to expand the toolbox of a defender implementing lattice-based cryptography with protection against two common physical attacks.

Having shared access to high-quality random numbers is essential in many important applications. Yet, existing constructions of distributed random beacons still have limitations such as imperfect security guarantees, strong setup or network assumptions, or high costs. In this paper, we present SPURT, an efficient distributed randomness beacon protocol that does not require any trusted or expensive setup and is secure against a malicious adversary that controls up to one-third of the nodes in a partially synchronous network. We formally prove that each output of SPURT is unpredictable, bias-resistant, and publicly verifiable. SPURT has an amortized total communication cost of O(\lambda n^2) per beacon output in the fault-free case and O(\lambda n^2\log n + n^3) in the worst case. We implement SPURT and evaluate it using a network of up to 128 nodes running in geographically distributed AWS instances. Our evaluation shows that SPURT has practical computation and bandwidth costs and can produce beacon outputs every second for a network of 64 nodes, and every 3 seconds for a network of 128 nodes.

A major concern in training and releasing machine learning models is to what extent the model contains sensitive information that the data holders do not want to reveal. Property inference attacks consider an adversary who has access to the trained model and tries to extract some global statistics of the training data. In this work, we study property inference in scenarios where the adversary can maliciously control part of the training data (poisoning data) with the goal of increasing the leakage.

Previous work on poisoning attacks focused on trying to decrease the accuracy of models either on the whole population or on specific sub-populations or instances. Here, for the first time, we study poisoning attacks where the goal of the adversary is to increase the information leakage of the model. Our findings suggest that poisoning attacks can boost the information leakage significantly and should be considered as a stronger threat model in sensitive applications where some of the data sources may be malicious.

We first describe our property inference poisoning attack that allows the adversary to learn the prevalence in the training data of any property it chooses: it chooses the property to attack, then submits input data according to a poisoned distribution, and finally uses black box queries (label-only queries) on the trained model to determine the frequency of the chosen property. We theoretically prove that our attack can always succeed as long as the learning algorithm used has good generalization properties.

We then verify effectiveness of our attack by experimentally evaluating it on two datasets: a Census dataset and the Enron email dataset. In the first case we show that classifiers that recognizes whether an individual has high income (Census data) also leak information about the race and gender ratios of the underlying dataset. In the second case, we show classifiers trained to detect spam emails (Enron data) can also reveal the fraction of emails which show negative sentiment (according to a sentiment analysis algorithm); note that the sentiment is not a feature in the training dataset, but rather some feature that the adversary chooses and can be derived from the existing features (in this case the words). Finally, we add an additional feature to each dataset that is chosen at random, independent of the other features, and show that the classifiers can also be made to leak statistics about this feature; this shows that the attack can target features completely uncorrelated with the original training task. We were able to achieve above $90\%$ attack accuracy with $9-10\%$ poisoning in all of these experiments.

We consider image sets of $d$-uniform maps of finite fields. We present a lower bound on the image size of such maps and study their preimage distribution, by extending methods used for planar maps. We apply the results to study $d$-uniform Dembowsi-Ostrom polynomials. Further, we focus on a particularly interesting case of APN maps on binary fields $\F_{2^n}$. For these maps our lower bound coincides with previous bounds. We show that APN maps fulfilling the lower bound have a very special preimage distribution. We observe that for an even $n$ the image sets of several well-studied families of APN maps are minimal. In particular, for $n$ even, a Dembowski-Ostrom polynomial of form $f(x) =f'(x^3)$ is APN if and only if $f$ is almost-3-to-1, that is when its image set is minimal. Also, any almost-3-to-1 component-wise plateaued map is necessarily APN, if $n$ is even. For $n$ odd, we believe that the lower bound is not sharp. For $n$ odd, we present APN Dembowski-Ostrom polynomials of form $f'(x^3)$ on $\F_{2^n}$ with image sizes $ 2^{n-1}$ and $5\cdot 2^{n-3}$.

We present results connecting the image sets of special APN maps with their Walsh spectrum. Especially, we show that a large class of APN maps has the classical Walsh spectrum. Finally, we present upper bounds on the image size of APN maps. In particular, we show that the image set of a non-bijective almost bent map contains at most $2^n-2^{(n-1)/2}$ elements.

The prefix-free security of a cascade function based on a $c$-bit compression function $f$ is reduced to the $q$-query PRF security of $f$ with a tightness gap $\ell q$ where $q$ represents the maximum number of queries to the cascade and $\ell$ represents the length of the longest query. A two-stage proof for this reduction was first given by Bellare et al. in FOCS-96 for an adaptive distinguisher, and later a similar two-stage reduction was proved in CRYPTO-14 by Gazi et al. for a non-adaptive distinguisher.

In this paper we prove a direct single-stage reduction with a tightness gap of $\sigma$ (the total length of all queries). This is an improvement over existing reductions whenever the lengths of queries vary widely. In the case of non-adaptive prefix-free security, we also show a reduction proof which reduces PRF advantage of the cascade to two terms -- (i) a $q$-query PRF security of $f$ with a tightness gap of $q$ (without a factor of $\ell$) and (ii) a single query PRF security of $f$ with a tightness gap of $\sigma$. We further extend to a more general finer reduction to multiple terms over different limits on the queries to $f$. All these reductions can be easily extended to a multiuser setup. In particular, we reduce multiuser prefix-free PRF security of the cascade to a single user $q_{\max}$-query PRF security of $f$ with a tightness gap $\overline{\sigma}$ (the total length of all queries to all users), where $q_{\max}$ is the maximum number of queries allowed to any user. We have shown similar improved bounds (with respect to query complexity) for non-adaptive multiuser PRF security. In addition to immediate applications to multiuser security of HMAC and NMAC, our improved analysis has the following useful applications:

1. We show that the multiuser non-adaptive PRF security of the cascade does not degrade even if $f$ assures a weaker non-adaptive PRF security advantage.

2. The PRF security of single-keyed NMAC and Envelope MAC can be reduced to the non-adaptive multiuser prefix-free PRF security of the cascade construction and hence all improved reductions are applicable to these constructions. As a result, the constants ipad and opad used in HMAC are redundant. Moreover, the existing PRB assumption on $f$ can be replaced by a simple regular property for the constant-free HMAC.

Standard hybrid encryption schemes based on the KEM-DEM framework are hard to implement efficiently in a distributed manner whilst maintaining the CCA security property of the scheme. This is because the DEM needs to be decrypted under the key encapsulated by the KEM, before the whole ciphertext is declared valid. In this paper we present a new variant of the KEM-DEM framework, closely related to Tag-KEMs, which sidesteps this issue. We then present a post-quantum KEM for this framework based on Learning-with-Rounding, which is designed specifically to have fast distributed decryption. Our combined construction of a hybrid encryption scheme with Learning-with-Rounding based KEM, called Gladius, is closely related to the NIST Round 3 candidate called Saber. Finally, we give a prototype distributed implementation that achieves a decapsulation time of 4.99 seconds for three parties.

Timed-release encryption (TRE) is a prominent distributed way for sending messages to the future. Beyond its applications to e- voting and auctions, TRE can be easily generalized to a threshold information escrow (TIE) service, where a user can encrypt her message to any condition instead of just expiration of time as in TRE. Nevertheless, TRE and by extension TIE realized using threshold es- crow agents is vulnerable to premature, selective, and undetectable unlocking of messages through collusion among curious agents offering the service. This work presents a novel provably secure TIE scheme where any collusion attempt among the escrow agents offering the service towards premature decryption results in penalization through a loss of cryptocurrency and getting banned from the system. The proposed collusion-deterrent escrow (CDE) scheme intro- duces a novel incentive-penalty mechanism using a user-induced in- formation asymmetry among the agents such that they stay honest until the user-specified condition for decryption is met. In particular, each agent makes an escrow deposit before the start of the protocol such that the cryptocurrency deposit amount is transferred back to the agent when the condition specified by the user is met or can be transferred by anyone who holds the secret key corresponding to the public key of the protocol instance. CDE offers information escrow as a service and ensures that whenever the agents collude to decrypt the user data before the condition is met, there would be at least one whistle-blower agent who can withdraw/transfer the deposits of all other agents thereby penalizing them. We analyse the CDE protocol and model collusion as a game induced among rational agents offering the service and show in game-theoretic terms that the agents do not collude at equilibrium. We also present a prototype implementation of the CDE protocol and demonstrate its efficiency towards use in practice. We find this work to be an important step towards weakening the strong non-collusion assumptions across multi-party computation applications.

Credit and debit-card payments are typically authenticated with PINs. Once entered into a terminal, the PIN is sent as an encrypted \emph{PIN block} across a payments network to the destination bank, which decrypts and verifies the PIN block. Each node in the payments network routes the PIN block to the next node by decrypting the block with its own key, and then re-encrypting the PIN block with the next node's key; nodes establish shared secret keys with their neighbors to do so. This decrypt-then-encrypt operation over PIN blocks is known as \emph{PIN translation}, and it is currently performed in Hardware Security Modules (HSMs) to avoid possible PIN exposure. However, HSMs incur heavy acquisition and operational expenses. Introduced at EUROCRYPT'98, proxy re-encryption (PRE) is a cryptographic primitive which can re-encrypt without exposing sensitive data. We perform an extensive study of PRE as applied to PIN translation, and show through formalization, security analysis, and an implementation study that PRE is a practical alternative to HSMs. With PRE, we eliminate the need for HSMs during re-encryption of a PIN, thus greatly reducing the number of HSMs needed by each participant in the payments ecosystem. Along the way we conduct practice-oriented PRE research, with novel theoretical contributions to resolve issues in comparing so-called honest re-encryption to chosen-ciphertext PRE security, and a new efficient PRE scheme achieving a type of chosen-ciphertext security.

Despite a growing body of work on leakage-abuse attacks for encrypted databases, attacks on practical response-hiding constructions are yet to appear. Response-hiding constructions are superior in that they nullify access-pattern based attacks by revealing only the search token and the result size of each query. Response-hiding schemes are vulnerable to existing volume attacks, which are, however, based on strong assumptions such as the uniform query assumption or the dense database assumption. More crucially, these attacks only apply to schemes that cannot be deployed in practice (ones with quadratic storage and increased leakage) while practical response-hiding schemes (Demertzis et al. [SIGMOD’16] and Faber et al. [ESORICS’15]) have linear storage and less leakage. Due to these shortcomings, the value of existing volume attacks on response-hiding schemes is unclear.

In this work, we close the aforementioned gap by introducing a parametrized leakage-abuse attack that applies to practical response-hiding structured encryption schemes. The use of non-parametric estimation techniques makes our attack agnostic to both the data and the query distribution. At the very core of our technique lies the newly defined concept of a counting function with respect to a range scheme. We propose a two-phase framework to approximate the counting function for any range scheme. By simply switching one counting function for another, i.e., the so-called “parameter” of our modular attack, an adversary can attack different encrypted range schemes. We propose a constrained optimization formulation for the attack algorithm that is based on the counting functions. We demonstrate the effectiveness of our leakage-abuse attack on synthetic and real-world data under various scenarios.

In this article, we propose a new public key cryptosystem, called \textbf{NAB}. The most important features of NAB are that its security strength is no easier than the security issues of the NTRU cryptosystem~\cite{Hoffstein96} and the encryption/decryption process is very fast compared to the previous public key cryptosystems RSA~\cite{Rivest78amethod}, Elgamal~\cite{ElGamal85}, NTRU~\cite{Hoffstein96}. Since the NTRU cryptosystem~\cite{Hoffstein96} is still not known to be breakable using quantum computers, NAB is also the same. In addition, the expansion of the ciphertext is barely greater than the plaintext and the ratio of the bit-size of the ciphertext to the bit-size of the plaintext can be reduced to just over one. We suggest that NAB is an alternative to RSA~\cite{Rivest78amethod}, Elgamal~\cite{ElGamal85} and NTRU~\cite{Hoffstein96} cryptosystems.

In many cases, machine learning and privacy are perceived to be at odds. Privacy concerns are especially relevant when the involved data are sensitive. This paper deals with the privacy-preserving inference of deep neural networks. We report on first experiments with a new library implementing a variant of the TFHE fully homomorphic encryption scheme. The underlying key technology is the programmable bootstrapping. It enables the homomorphic evaluation of any function of a ciphertext, with a controlled level of noise. Our results indicate for the first time that deep neural networks are now within the reach of fully homomorphic encryption. Importantly, in contrast to prior works, our framework does not necessitate re-training the model.

Until now, there are two different methods to compute 4-GLV decompositions on the elliptic curves over $\mathbb{F}_{p^2}$ which are quadratic twists and possess a “restricted” endomorphism $\psi$ satisfying $\psi^{2}+1=0$. They are Longa and Sica's twofold Cornacchia-type algorithm (ASIACRYPT 2012) and Benjamin Smith's method--ready-made short bases (AMS 2015). In this paper, we first extend Smith's method from the case of quadratic twists to the case of quartic or sextic twists and give ready-made short bases for 4-GLV decompositions on these high degree twisted curves. After our supplements, Smith's method can be used to compute 4-GLV decompositions on more elliptic curves. Secondly, we focus on exploring more potential of Longa and Sica's algorithm, which is an elaborate iterated Cornacchia algorithm that can compute short bases for 4-GLV decompositions. The algorithm consists of two sub-algorithms, the first one in the ring of integers $\mathbb{Z}$ and the second one in the Gaussian integer ring $\mathbb{Z}[i]$. We observe that $\Z[i]$ in the second sub-algorithm can be replaced by another Euclidean domain $\mathbb{Z}[\omega]$ $(\omega=\frac{-1+\sqrt{-3}}{2})$. As a consequence, we design a new twofold Cornacchia-type algorithm with a theoretic upper bound of output $C\cdot n^{1/4}$, where $C=\frac{3+\sqrt{3}}{2}\sqrt{1+|r|+|s|}$ with small values $r, s$ given by the curve. The new twofold algorithm can be used to compute $4$-GLV decompositions on two classes of curves. First it gives a new and unified method to compute all $4$-GLV decompositions on $j$-invariant $0$ elliptic curves over $\mathbb{F}_{p^2}$. We exploit the fact that this family of curves must have an endomorphism $\phi$ satisfying $\phi^{2}+\phi+1=0$ (and hence $\mathbb{Z}[\phi]=\mathbb{Z}[\omega]$). Of the two previous methods on this class of elliptic curves, the first one was proposed by Hu, Longa and Xu in 2012 (Designs, Codes and Cryptography) but is applicable only to curves which are twists of degree $6$ and possess a “restricted” endomorphism $\psi$ satisfying $\psi^{4}-\psi^{2}+1=0$, the second one follows from the the work of Longa and Sica (ASIACRYPT 2012) and is applicable only to curves with a “restricted” endomorphism $\psi$ satisfying $\psi^{2}+1=0$. Second it can be used to compute the $4$-GLV decomposition on the Jacobian of the hyperelliptic curve defined as $\mathcal{C}/\mathbb{F}_{p}:y^{2}=x^{6}+ax^{3}+b$, which has an endomorphism $\phi$ with the characteristic equation $\phi^2+\phi+1=0$ (hence $\Z[\phi]=\Z[\omega]$).

Many privacy-preserving protocols employ a primitive that allows a sender to "flag" a message to a recipient's public key, such that only the recipient (who possesses the corresponding secret key) can detect that the message is intended for their use. Examples of such protocols include anonymous messaging, privacy-preserving payments, and anonymous tracing. A limitation of the existing techniques is that recipients cannot easily outsource the detection of messages to a remote server, without revealing to the server the exact set of matching messages. In this work we propose a new class of cryptographic primitives called fuzzy message detection schemes. These schemes allow a recipient to derive a specialized message detection key that can identify correct messages, while also incorrectly identifying non-matching messages with a specific and chosen false positive rate $p$. This allows recipients to outsource detection work to an untrustworthy server, without revealing precisely which messages belong to the receiver. We show how to construct these schemes under a variety of assumptions; describe several applications of the new technique; and show that our schemes are efficient enough to use in real applications.