Updated: 2 hours 36 min ago

### Lattice-Based Group Signatures and Zero-Knowledge Proofs of Automorphism Stability

Fri, 08/31/2018 - 23:29
We present a group signature scheme, based on the hardness of lattice problems, whose outputs are more than an order of magnitude smaller than the currently most efficient schemes in the literature. Since lattice-based schemes are also usually non-trivial to efficiently implement, we additionally provide the first experimental implementation of lattice-based group signatures demonstrating that our construction is indeed practical -- all operations take less than half a second on a standard laptop. A key component of our construction is a new zero-knowledge proof system for proving that a committed value belongs to a particular set of small size. The sets for which our proofs are applicable are exactly those that contain elements that remain stable under Galois automorphisms of the underlying cyclotomic number field of our lattice-based protocol. We believe that these proofs will find applications in other settings as well. The motivation of the new zero-knowledge proof in our construction is to allow the efficient use of the selectively-secure signature scheme (i.e. a signature scheme in which the adversary declares the forgery message before seeing the public key) of Agrawal et al. (Eurocrypt 2010) in constructions of lattice-based group signatures and other privacy protocols. For selectively-secure schemes to be meaningfully converted to standard signature schemes, it is crucial that the size of the message space is not too large. Using our zero-knowledge proofs, we can strategically pick small sets for which we can provide efficient zero-knowledge proofs of membership.

### PPP-Completeness with Connections to Cryptography

Fri, 08/31/2018 - 23:28
Polynomial Pigeonhole Principle (PPP) is an important subclass of TFNP with profound connections to the complexity of the fundamental cryptographic primitives: collision-resistant hash functions and one-way permutations. In contrast to most of the other subclasses of TFNP, no complete problem is known for PPP. Our work identifies the first PPP-complete problem without any circuit or Turing Machine given explicitly in the input, and thus we answer a longstanding open question from [Papadimitriou1994]. Specifically, we show that constrained-SIS (cSIS), a generalized version of the well-known Short Integer Solution problem (SIS) from lattice-based cryptography, is PPP-complete. In order to give intuition behind our reduction for constrained-SIS, we identify another PPP-complete problem with a circuit in the input but closely related to lattice problems. We call this problem BLICHFELDT and it is the computational problem associated with Blichfeldt's fundamental theorem in the theory of lattices. Building on the inherent connection of PPP with collision-resistant hash functions, we use our completeness result to construct the first natural hash function family that captures the hardness of all collision-resistant hash functions in a worst-case sense, i.e. it is natural and universal in the worst-case. The close resemblance of our hash function family with SIS, leads us to the first candidate collision-resistant hash function that is both natural and universal in an average-case sense. Finally, our results enrich our understanding of the connections between PPP, lattice problems and other concrete cryptographic assumptions, such as the discrete logarithm problem over general groups.

### Delegation of Decryption Rights with Revocability from Learning with Errors

Fri, 08/31/2018 - 23:27
The notion of decryption rights delegation was initially introduced by Blaze et al. in EUROCRYPT 1998. It, defined as \emph{proxy re-encryption}, allows a semi-trusted proxy to convert a ciphertext intended for a party to another ciphertext of the same plaintext, without knowledge of the underlying plaintext and decryption key. It has been explored to many real-world applications, e.g., encrypted email forwarding. However, the intrinsic all-or-nothing share feature of proxy re-encryption yields a limitation that the share cannot be revoked. This may hinder the scalability of its applications in practice. In this paper, for the first time, we define the concept of revocability in terms of decryption rights delegation. The novel concept enables data owner to revoke the shared decryption rights when needed. Inspired by the seminal lattice-based proxy re-encryption proposed in PKC 2014, we design a concrete lattice-based construction which satisfies the notion. In our construction, we make use of binary-tree structure to implement the revocation of decryption rights, so that the update of re-encryption key is reduced to $O(logN)$ (instead of $O(N)$), where $N$ is the maximum number of delegatee. Furthermore, the security of our scheme is based on the standard learning with errors problem, which could be reduced to the worst-case hard problems (such as GapSVP and SIVP) in the context of lattices. The scheme is chosen ciphertext secure in the standard model. As of independent interest, our scheme achieves both backward and forward security, which means that once a user is revoked after a time period $\mathbf{t}$, it cannot gain access to all encrypted files before and after $\mathbf{t}$.

### Verifiability of Helios Mixnet

Fri, 08/31/2018 - 12:33
We study game-based definitions of individual and universal verifiability by Smyth, Frink & Clarkson. We prove that building voting systems from El Gamal coupled with proofs of correct key generation suffices for individual verifiability. We also prove that it suffices for an aspect of universal verifiability. Thereby eliminating the expense of individual-verifiability proofs and simplifying universal-verifiability proofs for a class of encryption-based voting systems. We use the definitions of individual and universal verifiability to analyse the mixnet variant of Helios. Our analysis reveals that universal verifiability is not satisfied by implementations using the weak Fiat-Shamir transformation. Moreover, we prove that individual and universal verifiability are satisfied when statements are included in hashes (i.e., when using the Fiat-Shamir transformation, rather than the weak Fiat-Shamir transformation).

### Actively Secure OT-Extension from q-ary Linear Codes

Fri, 08/31/2018 - 08:24
We consider recent constructions of $1$-out-of-$N$ OT-extension from Kolesnikov and Kumaresan (CRYPTO 2013) and from Orrú et al. (CT-RSA 2017), based on binary error-correcting codes. We generalize their constructions such that $q$-ary codes can be used for any prime power $q$. This allows to reduce the number of base $1$-out-of-$2$ OT's that are needed to instantiate the construction for any value of $N$, at the cost of increasing the complexity of the remaining part of the protocol. We analyze these trade-offs in some concrete cases.

### Determining the Minimum Degree of an S-box

Thu, 08/30/2018 - 14:04
S-boxes are important building blocks in block ciphers. For secure design one should not choose an S-box that has low degree. In this work we consider minimum degree of an S-box which is the minimum value of the degree of the nonzero component functions of the S-box. For an S-box $F : {F_2}^n \rightarrow {F_2}^m$, there are $2^m - 1$ nonzero component functions, we show that there is a better way to determine the minimum degree of an S-box which does not require to check all the $2^m - 1$ component functions. To the best of our knowledge, this is the best algorithm for determining the minimum degree of an S-box in the literature.

### Laconic Function Evaluation and Applications

Wed, 08/29/2018 - 11:37
We introduce a new cryptographic primitive called laconic function evaluation (LFE). Using LFE, Alice can compress a large circuit $f$ into a small digest. Bob can encrypt some data $x$ under this digest in a way that enables Alice to recover $f(x)$ without learning anything else about Bob's data. For the scheme to be laconic, we require that the size of the digest, the run-time of the encryption algorithm and the size of the ciphertext should all be small, much smaller than the circuit-size of $f$. We construct an LFE scheme for general circuits under the learning with errors (LWE) assumption, where the above parameters only grow polynomially with the depth but not the size of the circuit. We then use LFE to construct secure 2-party and multi-party computation (2PC, MPC) protocols with novel properties: * We construct a 2-round 2PC protocol between Alice and Bob with respective inputs $x_A,x_B$ in which Alice learns the output $f(x_A,x_B)$ in the second round. This is the first such protocol which is "Bob-optimized", meaning that Alice does all the work while Bob's computation and the total communication of the protocol are smaller than the size of the circuit $f$ or even Alice's input $x_A$. In contrast, prior solutions based on fully homomorphic encryption are "Alice-optimized". * We construct an MPC protocol, which allows $N$ parties to securely evaluate a function $f(x_1,...,x_N)$ over their respective inputs, where the total amount of computation performed by the parties during the protocol execution is smaller than that of evaluating the function itself! Each party has to individually pre-process the circuit $f$ before the protocol starts and post-process the protocol transcript to recover the output after the protocol ends, and the cost of these steps is larger than the circuit size. However, this gives the first MPC where the computation performed by each party during the actual protocol execution, from the time the first protocol message is sent until the last protocol message is received, is smaller than the circuit size.

### Fast Secure Two-Party ECDSA Signing

Wed, 08/29/2018 - 03:28
ECDSA is a standard digital signature schemes that is widely used in TLS, Bitcoin and elsewhere. Unlike other schemes like RSA, Schnorr signatures and more, it is particularly hard to construct efficient threshold signature protocols for ECDSA (and DSA). As a result, the best-known protocols today for secure distributed ECDSA require running heavy zero-knowledge proofs and computing many large-modulus exponentiations for every signing operation. In this paper, we consider the specific case of two parties (and thus no honest majority) and construct a protocol that is approximately \textit{two orders of magnitude faster} than the previous best. Concretely, our protocol achieves good performance, with a single signing operation for curve P-256 taking approximately 37ms between two standard machine types in Azure (utilizing a single core only). Our protocol is proven secure under standard assumptions using a game-based definition. In addition, we prove security by simulation under a plausible yet non-standard assumption regarding Paillier.

### Computational problems in supersingular elliptic curve isogenies

Wed, 08/29/2018 - 02:17
We present an overview of supersingular isogeny cryptography and how it fits into the broad theme of post-quantum public key crypto. The paper also gives a brief tutorial of elliptic curve isogenies and the computational problems relevant for supersingular isogeny crypto. Supersingular isogeny crypto is attracting attention due to the fact that the best attacks, both classical and quantum, require exponential time. However, the underlying computational problems have not been sufficiently studied by quantum algorithm researchers, especially since there are significant mathematical preliminaries needed to fully understand isogeny crypto. The main goal of the paper is to advertise various related computational problems, and to explain the relationships between them, in a way that is accessible to experts in quantum algorithms. This is a post-peer-review, pre-copyedit version of an article to be published as a "perspective paper" in the journal Quantum Information Processing.

### On the security of the WOTS-PRF signature scheme

Tue, 08/28/2018 - 10:11
We identify a flaw in the security proof and a flaw in the concrete security analysis of the WOTS-PRF variant of the Winternitz one-time signature scheme, and discuss the implications to its concrete security.

### Do you need a Blockchain?

Tue, 08/28/2018 - 07:49
Blockchain is being praised as a technological innovation which allows to revolutionize how society trades and interacts. This reputation is in particular attributable to its properties of allowing mutually mistrusting entities to exchange financial value and interact without relying on a trusted third party. A blockchain moreover provides an integrity protected data storage and allows to provide process transparency. In this article we critically analyze whether a blockchain is indeed the appropriate technical solution for a particular application scenario. We differentiate between permissionless (e.g., Bitcoin/Ethereum) and permissioned (e.g. Hyperledger/Corda) blockchains and contrast their properties to those of a centrally managed database. We provide a structured methodology to determine the appropriate technical solution to solve a particular application problem. Given our methodology, we analyze in depth three use cases --- Supply Chain Management, Interbank and International Payments, and Decentralized Autonomous Organizations and conclude the article with an outlook for further opportunities.

### Improvements to the Linear Operations of LowMC: A Faster Picnic

Tue, 08/28/2018 - 05:19
Picnic is a practical approach to digital signatures where the security is primarily based on the existence of a one-way function, and the signature size strongly depends on the number of multiplications in the description of that one-way function. The highly parameterizable block cipher family LowMC has the most competitive properties with respect to this metric and is hence a standard choice. In this paper, we study various options for efficient implementations of LowMC in-depth. First, we investigate optimizations of the round key computation of LowMC independently of any implementation optimizations. By decomposing the round key computations based on the keys' effect on the S-box layer and general optimizations, we reduce runtime costs by up to 40% and furthermore reduce the size of the LowMC matrices by around 55% compared to the original Picnic implementation (CCS'17). Second, we propose a Feistel structure using smaller matrices completely replacing the remaining large matrix multiplication in LowMC's linear layer. With this approach, we achieve an operation count logarithmic in the block size but more importantly, improve over Picnic's constant-time matrix multiplication by 60% while retaining a constant-time algorithm. Furthermore, this technique also enables us to reduce the memory requirements for storing LowMC matrices by 60%.