Call for public-key-encryption software for benchmarking

eBATS (ECRYPT Benchmarking of Asymmetric Systems) is a competition for the most efficient public-key systems. eBATS measures public-key-encryption systems according to the following criteria: ``Time'' refers to time on real computers: cycles on a Pentium III 68a, cycles on a PowerPC G5, cycles on an Athlon 64 X2, etc. eBATS times each system on a wide variety of computers, ensuring direct comparability of all systems on whichever computers are of interest to the users. Tools to graph the results will be made available.

This page explains how cryptographers can submit implementations of public-key-encryption systems (RSA, McEliece, NTRU, etc.) to eBATS.

Introduction to the eBATS encrypting API

Formal submission requirements have been kept to a minimum. Your software has to be an encrypting BAT (Benchmarkable Asymmetric Tool), meaning that it supports the following three functions:

Don't want to handle arbitrary-length messages? No problem. Instead of implementing ciphertext and plaintext, you can implement shortciphertext and shortplaintext, and define the maximum length of a short plaintext. BATMAN, the eBATS benchmarking software, will automatically handle longer plaintexts using a stream cipher.

You can also provide additional functions that document additional features of your system:

Claims regarding these additional features do not have the same level of verifiability as the eBATS measurements of key size, encryption time, etc.; eBATS will nevertheless report these claims for public discussion.

The eBATS encrypting API is described below in more detail. There's a separate page on BATMAN; you will be able to download and use BATMAN before submission to check that your implementation works properly. There's also a separate page discussing security evaluations in more detail.

Files in an encrypting BAT

An encrypting BAT is a tar.gz file containing one directory. The directory contains a file sizes.h, any number of additional *.S, *.c, and *.cpp files implementing the eBATS encrypting API, and a file documentation.pdf with references and other comments for cryptographers.

The directory name is the BAT name followed by a dash and a version number: e.g., ronald-1 for a BAT named ronald, version 1. eBATS will rename BATs if there is a conflict in names.

The file sizes.h defines various macros discussed below: SECRETKEY_BYTES, PUBLICKEY_BYTES, ENCRYPTION_BYTES, and optionally SHORTPLAINTEXT_BYTES.

BATMAN will automatically decide whether the BAT is a C BAT, providing the eBATS API functions in C, or a C++ BAT, providing the eBATS API functions in C++. Either way, the BAT can call C functions in its *.c files and assembly-language functions in its *.S files. BATs written in other languages have to be compiled to C++, C, or assembly language.

Parametrized BATs

Some BATs allow parameters. For example, a typical RSA implementation allows a wide range of key sizes. On the other hand, some RSA implementations gain speed by focusing on particular key sizes.

The eBATS API can support BATs of either type. A parametrized BAT includes, in the same directory as sizes.h, a parameters file with several lines; each line specifies compilation options that select a particular parameter choice. A parameter choice is specified by BAT-specific macros, which are used by sizes.h etc., and by a PARAMETERS macro (without white space), which is used to identify parameters in the eBATS results.

For example, version 1 of the RONALD BAT has a 29-line parameters file starting

     -DMODULUS_BITS=768 -DPARAMETERS="768"
     -DMODULUS_BITS=832 -DPARAMETERS="832"
     -DMODULUS_BITS=896 -DPARAMETERS="896"
     -DMODULUS_BITS=960 -DPARAMETERS="960"
     -DMODULUS_BITS=1024 -DPARAMETERS="1024"
and continuing (in roughly geometric progression) until
     -DMODULUS_BITS=4096 -DPARAMETERS="4096"
The MODULUS_BITS macro controls PUBLICKEY_BYTES etc. through the lines
     #define MODULUS_BYTES (MODULUS_BITS / 8)
     #define PUBLICKEY_BYTES (MODULUS_BYTES)
in the sizes.h file. The PARAMETERS macro is printed in the eBATS measurements.

The parameters file can omit -DPARAMETERS=... if sizes.h defines PARAMETERS. For example, version 2 of the RONALD BAT has a 29-line parameters file starting

     -DMODULUS_BITS=768 
     -DMODULUS_BITS=832 
     -DMODULUS_BITS=896 
     -DMODULUS_BITS=960 
     -DMODULUS_BITS=1024 
and the following lines in sizes.h:
     #define XSTRINGIFY(N) #N
     #define STRINGIFY(N) XSTRINGIFY(N)
     #define PARAMETERS (STRINGIFY(MODULUS_BITS))

Tuned BATs

A BAT can contain several implementations of the same functions: e.g., a P4-tuned implementation, a G5-tuned implementation, etc. A tuned BAT includes, in the same directory as sizes.h, a tunings file with several lines; each line specifies compilation options that select a particular tuning. A tuning is specified by BAT-specific macros, which are used by sizes.h etc., and by a TUNING macro (without white space), which is used to identify tuning in the eBATS results.

BATMAN will automatically try each tuning and select the tuning where ciphertext runs most quickly. A BAT can define a TUNETARGET macro in sizes.h; in that case BATMAN will select the tuning where TUNETARGET() runs most quickly.

Any particular tuning is allowed to be unportable, failing to compile on most platforms. BATMAN will skip tunings that don't compile or that flunk some simple tests.

Generating random numbers

BATMAN sets up file descriptor 0 reading from a neverending source of hard-to-predict secret random bytes. BATs are free to assume this: the keypair function, for example, can obtain secret bytes using getchar().

Functions are permitted, but not encouraged, to generate randomness in other ways, such as by opening /dev/urandom. These functions won't be benchmarkable on systems that don't have /dev/urandom, and they won't be suitable for black-box regression testing.

Using hash functions

BATMAN provides a cryptographic hash function hash256 callable from a BAT as follows:
     const unsigned char m[...]; unsigned long long mlen;
     unsigned char h[32];
     hash256(h,m,mlen);
hash256 hashes bytes m[0], m[1], ..., m[mlen-1] and puts the output into h[0], h[1], ..., h[31]. Currently hash256 is implemented as SHA-256.

To simplify comparisons of public-key systems, eBATS recommends that BATs use hash256 for all necessary hashing. This is not a recommendation of SHA-256 for any purpose other than public-key benchmarking. Public-key systems may be able to gain speed and security by choosing different hash functions.

To the extent that eBATS considers security of public-key systems, it focuses on generic attacks, i.e., attacks that work with any hash function. Any security problems in SHA-256 are outside the scope of eBATS, although obviously they should be discussed elsewhere.

Using stream ciphers

BATMAN provides an additive stream cipher stream256 callable from a BAT as follows:
     const unsigned char m[...]; unsigned long long mlen;
     unsigned char c[...];
     const unsigned char k[32];
     const unsigned char n[8];
     stream256(c,m,mlen,k,n);
stream256 encrypts (or decrypts) bytes m[0], m[1], ..., m[mlen-1] and puts the output into c[0], c[1], ..., c[mlen-1]. It uses a 32-byte key k[0], k[1], ..., k[31] and an 8-byte nonce n[0], n[1], ..., n[7]. Currently stream256 is implemented as Salsa20.

To simplify comparisons of public-key systems, eBATS recommends that BATs use stream256 for all necessary stream generation. This is not a recommendation of Salsa20 for any purpose other than public-key benchmarking. Public-key systems may be able to gain speed and security by choosing different ciphers.

To the extent that eBATS considers security of public-key systems, it focuses on generic attacks, i.e., attacks that work with any stream cipher. Any security problems in Salsa20 are outside the scope of eBATS, although obviously they should be discussed elsewhere.


keypair: generate a new secret key and public key

An encrypting BAT must provide a keypair function callable as follows:
     #include "sizes.h"

     unsigned char sk[SECRETKEY_BYTES]; unsigned long long sklen;
     unsigned char pk[PUBLICKEY_BYTES]; unsigned long long pklen;

     keypair(sk,&sklen,pk,&pklen);
The keypair function generates a new secret key and a new public key. It puts the number of bytes of the secret key into sklen; puts the number of bytes of the public key into pklen; puts the secret key into sk[0], sk[1], ..., sk[sklen-1]; and puts the public key into pk[0], pk[1], ..., pk[pklen-1]. It then returns 0.

keypair guarantees that sklen is at most SECRETKEY_BYTES, and that pklen is at most PUBLICKEY_BYTES, so that the caller can allocate enough space.

If key generation is impossible for some reason (e.g., not enough memory), keypair returns a negative number, possibly after modifying sk[0], sk[1], etc. Current implementations should return -1; other return values with special meanings may be defined in the future.

ciphertext: encrypt a message using a public key

An encrypting BAT can provide a ciphertext function callable as follows:
     #include "sizes.h"

     const unsigned char pk[PUBLICKEY_BYTES]; unsigned long long pklen;
     const unsigned char m[...]; unsigned long long mlen;
     unsigned char c[...]; unsigned long long clen;

     ciphertext(c,&clen,m,mlen,pk,pklen);
The ciphertext function uses a public key pk[0], pk[1], ..., pk[pklen-1] to encrypt a message m[0], m[1], ..., m[mlen-1]. It puts the length of the encrypted message into clen and puts the encrypted message into c[0], c[1], ..., c[clen-1]. It then returns 0.

The ciphertext function guarantees that clen is at most mlen+ENCRYPTION_BYTES. The ENCRYPTION_BYTES macro is defined in sizes.h.

The ciphertext function is free to assume that the public key pk[0], pk[1], ..., pk[pklen-1] was generated by a successful call to the keypair function.

If encryption is impossible for some reason, ciphertext returns a negative number, possibly after modifying c[0], c[1], etc. Current implementations should return -1; other return values with special meanings may be defined in the future.

Implementors of the ciphertext function are warned that they should not go to extra effort to compress the message m. Higher-level applications should be presumed to compress messages before calling the ciphertext function; in particular, BATMAN uses random messages to make compression ineffective. On the other hand, the encrypted message c is longer than the original message m and might be compressible; any reduction of the encryption overhead will be visible in the eBATS measurements.

plaintext: decrypt a message using a secret key

An encrypting BAT can provide a plaintext function callable as follows:
     #include "sizes.h"

     const unsigned char sk[SECRETKEY_BYTES]; unsigned long long sklen;
     const unsigned char c[...]; unsigned long long clen;
     unsigned char m[...]; unsigned long long mlen;

     plaintext(m,&mlen,c,clen,sk,sklen);
The plaintext function uses a secret key sk[0], sk[1], ..., sk[sklen-1] to decrypt a ciphertext c[0], c[1], ..., c[clen-1]. The plaintext function puts the length of the decrypted message into mlen, puts the decrypted message into m[0], m[1], ..., m[mlen-1], and returns 0.

The plaintext function guarantees that mlen is at most clen.

The plaintext function is free to assume that the secret key sk[0], sk[1], ..., sk[sklen-1] was generated by a successful call to the secretkey function.

If decryption is impossible for some reason, plaintext returns a negative number, possibly after modifying m[0], m[1], etc. Current implementations should return -100 for invalid ciphertexts, and -1 for all other problems; other return values with special meanings may be defined in the future.

shortciphertext: encrypt a message using a public key

An encrypting BAT can provide a shortciphertext function callable as follows:
     #include "sizes.h"

     const unsigned char pk[PUBLICKEY_BYTES]; unsigned long long pklen;
     const unsigned char m[SHORTPLAINTEXT_BYTES]; unsigned long long mlen;
     unsigned char c[ENCRYPTION_BYTES]; unsigned long long clen;

     shortciphertext(c,&clen,m,mlen,pk,pklen);
The shortciphertext function uses a public key pk[0], pk[1], ..., pk[pklen-1] to encrypt a message m[0], m[1], ..., m[mlen-1]. It puts the length of the encrypted message into clen and puts the encrypted message into c[0], c[1], ..., c[clen-1]. It then returns 0.

The shortciphertext function is free to assume that mlen is at most SHORTPLAINTEXT_BYTES. The shortciphertext function guarantees that clen is exactly ENCRYPTION_BYTES. The SHORTPLAINTEXT_BYTES and ENCRYPTION_BYTES macros are defined in sizes.h.

The shortciphertext function is free to assume that the public key pk[0], pk[1], ..., pk[pklen-1] was generated by a successful call to the keypair function.

If encryption is impossible for some reason, shortciphertext returns a negative number, possibly after modifying c[0], c[1], etc. Current implementations should return -1; other return values with special meanings may be defined in the future.

Implementors of the shortciphertext function are warned that they should not go to extra effort to compress the message m. Higher-level applications should be presumed to compress messages before calling the shortciphertext function; in particular, BATMAN uses random messages to make compression ineffective. On the other hand, the encrypted message c is longer than the original message m and might be compressible; any reduction of the encryption overhead will be visible in the eBATS measurements.

BATMAN automatically builds ciphertext on top of shortciphertext as follows. Messages with at most SHORTPLAINTEXT_BYTES-1 bytes are simply encrypted with shortciphertext. A message with SHORTPLAINTEXT_BYTES or more bytes is handled as follows:

SHORTPLAINTEXT_BYTES must be at least 64. Criticisms of the speed and security of Salsa20 and SHA-256 are outside the scope of eBATS; eBATS focuses on public-key cryptography, not on stream ciphers and hash functions.

shortplaintext: decrypt a message using a secret key

An encrypting BAT can provide a shortplaintext function callable as follows:
     #include "sizes.h"

     const unsigned char sk[SECRETKEY_BYTES]; unsigned long long sklen;
     const unsigned char c[ENCRYPTION_BYTES]; unsigned long long clen;
     unsigned char m[SHORTPLAINTEXT_BYTES]; unsigned long long mlen;

     shortplaintext(m,&mlen,c,clen,sk,sklen);
The shortplaintext function uses a secret key sk[0], sk[1], ..., sk[sklen-1] to decrypt a ciphertext c[0], c[1], ..., c[clen-1]. The shortplaintext function puts the length of the decrypted message into mlen, puts the decrypted message into m[0], m[1], ..., m[mlen-1], and returns 0.

The shortplaintext function is free to assume that clen is exactly ENCRYPTION_BYTES. The shortplaintext function guarantees that mlen is at most SHORTPLAINTEXT_BYTES.

The shortplaintext function is free to assume that the secret key sk[0], sk[1], ..., sk[sklen-1] was generated by a successful call to the secretkey function.

If decryption is impossible for some reason, plaintext returns a negative number, possibly after modifying m[0], m[1], etc. Current implementations should return -100 for invalid ciphertexts, and -1 for all other problems; other return values with special meanings may be defined in the future.

BATMAN automatically builds plaintext on top of shortplaintext by reversing the construction of ciphertext from shortciphertext.


distinguishingchance: report effectiveness of best attack known

An encrypting BAT can provide a distinguishingchance function callable as follows:
     #include "sizes.h"

     double e;
     double s;
     double p = distinguishingchance(e,s);
The distinguishingchance function returns a number between 0 and 1, namely the ciphertext-distinguishing (IND-CPA) probability for an attacker spending e euros and s seconds against one public key. Here e and s are powers of 2 between 2^0 and 2^40.

The attacker is given a ciphertext obtained either by encrypting m0 or by encrypting m1, where m0 and m1 are messages of the same length. The attacker's goal is to guess, with probability at least 50%+p, whether the decryption is m0 or m1. The attacker is not required to carry out a passive attack; the attacker is presumed to be able to specify m0 and m1. The attacker is not required to use meaningful messages m0 and m1; any distinguished messages, no matter how random they look, are presumed to be a disaster. These presumptions are standard: without them, every application would need a separate analysis of the message space.

There is a separate page with more information on security evaluations.

multiplekeydistinguishingchance: report effectiveness of best attack known

An encrypting BAT can provide a multiplekeydistinguishingchance function callable as follows:
     #include "sizes.h"

     double e;
     double s;
     double k;
     double p = multiplekeydistinguishingchance(e,s,k);
The multiplekeydistinguishingchance function returns a number between 0 and 1, namely the ciphertext-distinguishing (IND-CPA) probability for an attacker spending e euros and s seconds against k public keys. Here e, s, and k are powers of 2 between 2^0 and 2^40.

The result of multiplekeydistinguishingchance can be larger than the result of distinguishingchance by a factor as large as k.

ccattacks: report extra effectiveness of chosen-ciphertext attacks

An encrypting BAT can provide a ccattacks function callable as follows:
     #include "sizes.h"

     int x = ccattacks();
The ccattacks function returns 100 if adaptive chosen-ciphertext attacks (IND-CCA2) are more effective than chosen-plaintext attacks. It returns 0 if adaptive chosen-ciphertext attacks are no more effective than chosen-plaintext attacks.

timingattacks: report extra effectiveness of timing attacks

An encrypting BAT can provide a timingattacks function callable as follows:
     #include "sizes.h"

     int x = timingattacks();
The timingattacks function returns 0 if the software does not leak any secret information through timing (variable time for branching, variable time for memory access, etc.): i.e., if the best attack known that sees timings is as difficult as the best attack known that does not see timings. It returns 100 if the software leaks secret information through timing.

copyrightclaims: report copyright claims

An encrypting BAT can provide a copyrightclaims function callable as follows:
     #include "sizes.h"

     int x = copyrightclaims();
The copyrightclaims function returns one of the following numbers: More numbers may be defined in the future.

No matter what the BAT's copyright status is, eBATS will publicly distribute copies of the BAT for benchmarking. The submitter must ensure before submission that publication is legal.

patentclaims: report patent claims

An encrypting BAT can provide a patentclaims function callable as follows:
     #include "sizes.h"

     int x = patentclaims();
The patentclaims function returns one of the following numbers: More numbers may be defined in the future.

No matter what the BAT's patent status is, eBATS will publicly distribute copies of the BAT for benchmarking.

Version

This is version 2006.06.16 of the call-encryption.html web page. This web page is in the public domain.