cryptographic Research Projects

Pairing-Based Cryptography

Recently, what are known as “pairings” on elliptic curves have been a very active area of research in cryptography. A pairing is a function that maps a pair of points on an elliptic curve into a finite field. Their unique properties have enabled many new cryptographic protocols that had not previously been feasible.

In particular, identity-based encryption (IBE) is a pairing-based scheme that has received considerable attention. IBE uses some form of a person (or entity’s) identification to generate a public key. This could be an email address, for instance. An IBE scheme allows a sender to encrypt a message without needing a receiver’s public key to have been certified and distributed for subsequent use. Such a scenario is quite useful if the pre-distribution of public keys is impractical. Besides IBE, there are a number of other applications of pairing-based cryptography. These include many other identity-based cryptosystems (including signature schemes), key establishment schemes, functional and attribute-based encryption, and privacy-enhancing techniques, such as the use of anonymous credentials.

In 2008, NIST held a workshop on pairing-based cryptography. While the workshop showed that there was interest in pairing-based schemes, a common understanding was that further study was needed before NIST approved any such schemes. Starting in 2011, members of the Cryptographic Technology Group have conducted an extensive study on pairing-based cryptographic schemes. This included topics such as: the construction of pairing-friendly elliptic curves, a survey of pairing-based cryptographic schemes, implementation efficiency with respect to the required security, standard activities involving pairing-based schemes, use cases and practical implications. This work was summarized in a technical report, presented in the first quarter of 2012. The report was published in the NIST Journal of Research (http://dx.doi.org/10.6028/jres.120.002). At the NIST Cryptography for Emerging Technologies and Applications (CETA) Workshop in November 2011, there was a public call for feedback on potential use cases.

Pairing operations appear to be important tools for various cryptographic schemes used in cloud computing and privacy enhancing environments. Besides IBE, other demanding applications have also motivated the continuation of this study. Short signatures and broadcast encryption are examples of such applications.

Contacts:
pairings@nist.gov

Dr. Dustin Moody (301) 975-8136 dustin.moody@nist.gov

Dr. Lily Chen (301) 975-6974 lily.chen@nist.gov

Back to Top of Page

---

Privacy Enhancing Cryptography Project

The privacy-enhancing cryptography project seeks to promote the use of communication protocols that do not reveal unneeded private information of the communicating parties. There are many technical challenges in doing this, as it is typically hard to separate private data from general data (e.g. to convert a third-party-signed date-of-birth certificate into a certificate indicating that a person is of voting age). Zero-knowledge (ZK) proof techniques and their variants can be used to accomplish this for a large class of assertions. These techniques allow one party to prove to another party that a given statement is true, without conveying any additional information apart from the fact that the statement is indeed true. However, even though many such ZK protocols are practical, adoption by industry is slow. CSD’s CTG is also following the progress of emerging technologies, such as fully homomorphic encryption (FHE). FHE could potentially solve a large class of problems by allowing computation on encrypted data without decryption. CTG has also shown that the NIST Randomness Beacon (discussed below) can be used as a primitive in secure multi-party computation, such as sealed-bid online auctions, in which losing bids are never opened.

Team members continue to work in collaboration with the National Strategy for Trusted Identities in Cyberspace (NSTIC) program and the Federal Cloud Credential Exchange (FCCX) project. In this context, CTG has served as evaluators and in technical support roles. Information about NSTIC and FCCX is available at http://www.nist.gov/nstic/.

Current communication security standards are primarily designed for two-party communication. CTG believes that future protocols, such as those for identification, commercial transactions, and social media, will necessitate standards for three-party communications (e.g., two parties involved in a commercial transaction and a third party that serves as an enabler of some aspects of the transaction). This is particularly important if standards are to provide privacy protection. CTG has developed some basic protocols for this purpose. One such protocol allows for privacy-preserving identification with the aid of a mediator. In this protocol, the issuer of an assertion, such as “John Smith is an employee of the Department of Commerce,” does not need to know who the consumer of the assertion is, yet it can encrypt the assertion with a key only known to that consumer (i.e. the mediator cannot see the unencrypted assertion).

Contact:
Dr. Rene Peralta
(301) 975-8702
peralta@nist.gov

Back to Top of Page

---

Circuit Complexity

Any function can be described as a circuit with operations modulo 2. If the circuit only contains additions, then the function is linear. Nonlinearity, which is fundamental to cryptographic applications, can only be achieved by the use of multiplications. The standard description of the AES S-Box, which is the nonlinearity component for AES, is that it does inversion in the field of 256 elements. The field's standard measure of nonlinearity of a function F is the Hamming distance of the spectrum of F to the closest linear spectrum. A different measure of nonlinearity is simply the number of multiplications necessary and sufficient to compute the function. This measure is called "multiplicative complexity". Minimizing the number of multiplications as a first step in Boolean circuit optimization is a powerful tool. Research has led to a vast reduction in the number of gates and/or the depth of many circuits used in cryptography. These include a circuit of depth 16 and size 128 for the AES S-Box, as well as reduced size/depth circuits for high-speed cryptography in characteristic 2. Additionally, circuits with a small number of multiplications can be used to significantly improve the communication complexity of secure multiparty computations, as well as the size of non-interactive zero-knowledge proofs of knowledge.

Contact:
Dr. Rene Peralta
(301) 975-8702
rene.peralta@nist.gov

Back to Top of Page

---