MAYA-WG1: Design and Analysis of Primitives and Protocols
This working group focuses on the design and analysis of the two main ingredients of public-key cryptography: primitives (which are the basic tools of public-key cryptographers) and protocols (which describe how primitives can be used to achieve certain cryptographic goals).
Asymmetric cryptographic primitives, such as encryption and signatures, are the bedrock upon which modern cryptography is based. However, there are many settings where we need more than a plain asymmetric encryption or signature primitive and need to embed the primitives into a protocol. For instance, one way to achieve a secure electronic voting protocol is to use a so-called homomorphic asymmetric encryption scheme; one way to broadcast contents while avoiding piracy issues is to use a so-called traitor tracing asymmetric encryption scheme.
The goal of a protocol can be of technical nature, such as agreeing on a secret key for subsequent secure communication, secure identification of agents or reliable broadcast. But the goal can also be of more application-oriented nature, such as secure payment systems, fair exchange of information, secure electronic voting or secure auctions and contract bidding. Secure protocols must reach their goals despite attacks, even from agents who participate in the protocol.
Whereas in the past cryptographic protocols had to be designed by experts applying heuristic methods, the creation of cryptographic primitives and protocols is now becoming a well-defined science. The design process is now well established as consisting of first designing the primitive or protocol and then showing, by a computational reduction, that any adversary who can break the primitive or protocol in well-defined way can break some hard computational problem. This approach is often dubbed "provable security", to distinguish it from the ad-hoc notions of security which went before.
MAYA-WG2: Cryptanalysis and Mathematical FoundationsThe first requirement for an asymmetric scheme to be secure is the hardness of the underlying computational assumption. Many newly proposed schemes have been proven weak by cryptanalysts who designed algorithms to solve the supposedly hard computational problem. History has also shown that sometimes the underlying computational assumption is not properly identified by the designers, or the cryptographic instances of the underlying problem turn out to be easier than in the general case.
This working group is dedicated to the study of cryptanalytic techniques and algorithms, as well as the underlying mathematical objects used in asymmetric cryptography. This has significant impact on real-life cryptography since it is the state-of-the-art in cryptanalysis which dictates which cryptographic algorithms to use, how parameters should be chosen, and which key sizes should be selected.
The study includes but is not limited to: integer factorization, discrete logarithms, lattice basis reduction and its applications in cryptanalysis, computational assumptions arising in pairing-based cryptography (e.g., bilinear Diffie-Hellman), the RSA and strong RSA assumptions, etc. The aim is to develop new algorithms to solve such problems and/or to understand the relationships between problems. The algorithms will mainly be in the classical framework of Turing machines, but one may also consider quantum algorithms.An overview of these hard problems in cryptology gives the MAYA wiki on hard problems.