Building Usable Witness Encryption
This work addresses the challenge of making witness encryption practical for applications like secure key management, though it appears incremental as it builds on existing multilinear map implementations.
The authors tackled the problem of implementing a usable witness encryption scheme by building on an open-source multilinear map implementation, resulting in the world's first ciphertext encoded with a candidate witness encryption scheme and encrypting a Bitcoin wallet key using a Sudoku puzzle.
Witness encryption using multilinear maps was first proposed in 2013, and has continued to evolve since. In this paper, we build on an open-source multilinear map implementation by Carmer and Malozemoff of the graded encoding scheme CLT13 with asymmetric modifications. Using this map, we created the world's first ciphertext encoded with a candidate witness encryption scheme. Finally, using a reduction from Sudoku to Exact Cover, we encrypted the private key to a Bitcoin wallet with 22,700 Satoshi using a Sudoku.