International Association
for Cryptologic Research

In this paper, we propose a practical signature scheme based on the alternating trilinear form equivalence problem. Our scheme is inspired from the Goldreich-Micali-Wigderson's zero-knowledge protocol for graph isomorphism, and can be served as an alternative candidate for the NIST's post-quantum digital signatures. First, we present theoretical evidences to support its security, especially in the post-quantum cryptography context. The evidences are drawn from several research lines, including hidden subgroup problems, multivariate cryptography, cryptography based on group actions, the quantum random oracle model, and recent advances on isomorphism problems for algebraic structures in algorithms and complexity. Second, we demonstrate its potential for practical uses. Based on algorithm studies, we propose concrete parameter choices, and then implement a prototype. One concrete scheme achieves 128 bit security with public key size ~4100 bytes, signature size ~6800 bytes, and running times (key generation, sign, verify) ~0.8ms on a common laptop computer.

In order to evaluate a privileged cryptographic primitive, say decrypt a ciphertext or check a signature, an endpoint needs to know the raw key material, the algorithm including all parameters, and the ciphertext/signature. For example, JWT contains an algorithm field that dictates how it should be verified. This seemingly innocuous design has led to countless broken implementations and vulnerabilities, including the infamous "alg: None". While the security community likes to pick on JWT, we show that JWT is not the only system that succumbs to what we call in-band protocol negotiation attacks. We display a showcase of old and new attacks in widely deployed standards and systems, including AWS S3 Crypto SDK (CVE-2020-8912), AWS Encryption SDK and AWS KMS (under embargo). We show that not only the algorithm field can cause problems, but even a mundane detail such as the ciphertext format can also lead to weaknesses. We found that the root cause of these vulnerabilities is a failure to answer this basic question: what is a key? Many systems, standards, or libraries consider a key consisting of only the raw secret material. A secret key material, however, is usually not enough to instantiate a protocol, forcing people to store other parameters in the ciphertext, i.e., doing in-band protocol negotiation. We present how Google uses Tink to ensure that even software that has not been reviewed by cryptography engineers will not be vulnerable to this class of attack.

Private Set Intersection Cardinality (PSI-CA) allows two parties, each holding a set of items, to learn the size of the intersection of those sets without revealing any additional information. To the best of our knowledge, this work presents the first protocol that allows one of the parties to delegate PSI-CA computation to untrusted servers. At the heart of our delegated PSI-CA protocol is a new oblivious distributed key PRF (Odk-PRF) abstraction, which may be of independent interest. We explore in detail how to use our delegated PSI-CA protocol to perform privacy-preserving contact tracing. It has been estimated that a significant percentage of a given population would need to use a contact tracing app to stop a disease’s spread. Prior privacy-preserving contact tracing systems, however, impose heavy bandwidth or computational demands on client devices. These demands present an economic disincentive to participate for end users who may be billed per MB by their mobile data plan or for users who want to save battery life. We propose Catalic (ContAct TrAcing for LIghtweight Clients), a new contact tracing system that minimizes bandwidth cost and computation workload on client devices. By applying our new delegated PSI-CA protocol, Catalic shifts most of the client-side computation of contact tracing to untrusted servers, and potentially saves each user hundreds of megabytes of mobile data per day while preserving privacy.