archistar-smc-js

This is a short overview of the current status and development history of the archistar-smc-js secret sharing library.

Current Status

We currently implement very simple versions of Rabin's, Shamir's, and Krawczyk's (using Salsa20 for symmetric encryption) secret sharing algorithms.

How to build

To build archistar-smc-js, you need Node.js. After an npm install, a simple grunt (or grunt noasm for the handwritten version) should suffice. The resulting archistar.js (or archistar.noasm.js) can then be found in the dist directory.

Benchmarks can be run with grunt bench on the CLI or (assuming the necessary files have been generated by grunt or grunt noasm) in any modern browser by opening test.html or test.noasm.html in any modern browser, also to be found in the dist directory.

How to use

The archistar-smc-js library can be used both in the browser via <script> tag (where it exports an archistarJS module) and in NodeJS. An example is given below:

engine = new (require('./archistar.js')).<algorithm>.Configuration(n, k);
encoded = engine.encode(<Uint8Array>);
decoded = engine.decode(encoded);

Currently supported algorithms are rabin_ids, shamir_pss, and krawczyk.

WebAssembly

It is planned to also ship a WebAssembly version in the near future.

History

Development started from a blank slate, but with the archistar-smc (written in Java) already in place. Most of the new JavaScript code could easily adapted be from the existing Java code.

Initial results

Performance, was quite disappointing at first:

(4/3)	Encode	Decode
Shamir	123 kB/s	2335 kB/s
Krawczyk	2867 kB/s	2662 kB/s
Rabin	5530 kB/s	5325 kB/s

(Taken on a Core2 Duo E8400 @ 3.00GHz running Ubuntu 16.4 and Node.js 4.2.6)

Optimizations that have yielded major performance improvements in the Java version have had almost no impact in JavaScript.

For comparison, here are the numbers for the Java version on the same machine:

(4/3)	Encode	Decode
Shamir	22212 kB/s	21950 kB/s
Krawczyk	67147 kB/s	38935 kB/s
Rabin	169256 kB/s	58264 kB/s

asm.js

The usual way to achieve competitive performance on JavaScript platforms is by making use of asm.js. This means writing code in C/C++ and using emscripten to compile it down to a very restricted subset of JavaScript that can be executed very efficiently by modern JavaScript VMs. It is claimed that with this approach, performance almost equal to native code can be achieved. We have found this to be true in our case.

The necessary C code is a straightforward translation of the already existing code, as can be seen from a comparison with the Java version (that also parallelizes the execution):

IntStream.range(0, n).parallel().forEach(
  x -> {
    int[] mul = mulTables[x];
    byte[] out = output[x];
    for (int i = k - 1; i < data.length; i += k) {
      int res = data[i] & 0xff;
      for (int y = 1; y < k; y++) {
        res = GF256.add(data[i - y] & 0xff, mul[res]);
      }
      out[i / k] = (byte) res;
    }
    if (data.length % k != 0) {
      int res = data[data.length - 1] & 0xff;
      for (int y = data.length - 2; y >= data.length - data.length % k; y--) {
        res = GF256.add(data[y] & 0xff, mul[res]);
      }
      out[data.length / k] = (byte) res;
    }
  }
);

for (size_t x = 0; x < n; x++) {
  uint8_t * out = out_a[x];
  uint8_t * mult = multables[x];
  for (size_t i = k - 1; i < len; i += k) {
  	uint8_t res = in[i];
  for (size_t y = 1; y < k; y++) {
  	res = in[i - y] ^ mult[res];
  }
  out[i/k] = res;
  }
  if (len % k != 0) {
  	uint8_t res = in[len - 1];
  	for (size_t y = len - 2; y >= len - len % k; y--) {
  		res = in[y] ^ mult[res];
  	}
  	out[len/k] = res;
  }
}

Because we do not need most of what emscripten does over and above merely compiling the code (such as providing a runtime for the compiled code), we decided that we could write the necessary support code ourselves, include the compiled code directly, and therefore not have emscripten as a build dependency.

The files (secret.c and salsa20.c) were compiled to asm.js skeletons with

emcc src/secret.c -o t.js -s ONLY_MY_CODE=1 -s EXPORTED_FUNCTIONS="['_RabinEncode','_RabinDecode']" -s STRICT=1 -O3
emcc src/salsa20.c -o s.js -s ONLY_MY_CODE=1 -s EXPORTED_FUNCTIONS="['_Salsa20']" -s STRICT=1 -O3

The result was then - together with the necessary code to set up the asm.js heap - inserted into rabin_ids.js and salsa20.js.

Shamir was not implemented in asm.js. It is only used for sharing the keys in Krawczyk, and for such small files, performance benefit would be negative because of the overhead of the asm.js heap. (For data of size 4kB, the asm versions of Rabin and Krawczyk are on average an order of magnitude slower than the handwritten noasm versions)

Current Performance

(4/3)	Encode	Decode
Shamir noasm	6595 kB/s	28180 kB/s
Krawczyk noasm	5202 kB/s	4956 kB/s
Krawczyk asm	38994 kB/s	36987 kB/s
Rabin noasm	33628 kB/s	23388 kB/s
Rabin asm	67175 kB/s	61071 kB/s

Note that after several rewrites, even the handwritten JavaScript versions are much faster now, with the exception of Krawczyk, which is due to Salsa20 noasm still being slow.

Licence

© 2016-2018 AIT Austrian Institute of Technology
Licensed under the EUPL