There has been a surge in interactions between cryptography and several areas of computing and information sciences, most notably with computational learning theory, the theory of error-correcting codes, and data structures. The links between cryptography and these fields are deep and far-reaching. Developing these connections has enabled new hardness results for learning, advances in fully homomorphic encryption, efficient secure two-party and multi-party computation protocols, and methods for protecting cryptographic implementations from physical attacks. The workshop aims to bring together researchers from computer science, electrical engineering, and mathematics to foster further collaboration, with the goal of enabling new applications and settling open questions:
1. Cryptography and Learning Theory: At the heart of cryptography is unlearnability. Classes of concepts that are hard to learn can be used as hard problems on which to base cryptography. As a classic example, a cryptographically secure pseudorandom function can be considered as a class of functions that is “maximally unlearnable” from queries. Recently, the conjectured intractability of learning with errors (LWE) has found exciting applications in cryptography, most notably to constructing fully homomorphic encryption and other types of encryption and signature schemes with special properties. On the negative side, constructions of pseudorandom functions were used to establish limitations on the existence of efficient learning algorithms and natural techniques for proving circuit lower bounds. What other open problems in cryptography can be addressed by drawing from problems that have resisted learning? What other barriers in learning theory (more broadly, in computational complexity theory) can be obtained from positive results in cryptography?
2. Cryptography and Coding Theory: Error-correcting codes have been heavily used in cryptography since the 1970s. Their early applications include secret sharing, randomness extraction, secure multiparty computation, and hard-core bits for one-way functions. In recent years, much attention has been given to error-correcting codes with special properties that are motivated by cryptographic applications. For instance, secure multi-party computation can be based on error-correcting codes with a certain “multiplicative” property, and private information retrieval on codes with local decoders. The goal of protecting cryptographic implementations from physical leakage and tampering recently gave rise to several new types of codes, such as algebraic manipulation detection codes and non-malleable codes, which offer the “best possible security” against powerful attacks that go beyond the limits of classical error-correction. Other types of non-classical codes, such as interactive coding schemes, turned out to have unexpected connections with cryptography. What other problems in cryptography can benefit from these types of specialized codes? How far are we from their optimal constructions? Which other kinds of codes can be useful in cryptography?
3. Cryptography and Data Structures: The trend towards outsourcing larger amounts of data gives rise to new security threats and places new demands on the performance of cryptographic algorithms. But securely working with data at scale requires techniques that have not traditionally been used in provably secure cryptography. Recent successes in building primitives like oblivious, searchable encryption and proofs of retrievability have crucially made use of the theory of data structures, but a significant gap between cryptography and more advanced data structures remains. Under what circumstances can the above primitives be made more efficient using better data structures? For instance, data structures can be specialized for specific ranges of data sizes and deployment scenarios, or to optimize certain operations over others. More generally, what other cryptographic primitives for securely outsourcing data could benefit from a well-informed application of the broad and deep theory of data structures? What barriers on the efficiency of cryptographic primitives arise from lower bounds or open questions in the theory of data structures?
Next: Call for Participation
Workshop Index
DIMACS Homepage