Updated: 12 hours 16 min ago

### Reducing Multi-Secret Sharing Problem to Sharing a Single Secret Based on Cellular Automata

Wed, 07/05/2017 - 18:14
The aim of a secret sharing scheme is to share a secret among a group of participants in such a way that while authorized subsets of participants are able to recover the secret, non-authorized subsets of them obtain no information about it. Multi-secret sharing is the natural generalization of secret sharing for situations in which the simultaneous protection of more than one secret is required. However, there exist some secret sharing schemes for which there are no secure or efficient multi-secret sharing counterparts. In this paper, using cellular automata, an efficient general method is proposed to reduce the problem of sharing k secrets (all assigned with the same access structure and needed to be reconstructed at once) under a certain secret sharing scheme (S), to the problem of sharing one secret under S such that none of the properties of S are violated. Using the proposed approach, any secret sharing scheme can be converted to a multi-secret sharing scheme. We provide examples to show the applicability of the proposed approach.

### Integer Version of Ring-LWE and its Applications

Wed, 07/05/2017 - 18:13
In this work, we describe an integer version of ring-LWE over the polynomial rings and prove that its hardness is equivalent to one of the polynomial ring-LWE. Moreover, we also present a public key cryptosystem using this variant of the polynomial ring-LWE.

### On Trees, Chains and Fast Transactions in the Blockchain

Wed, 07/05/2017 - 11:06
A fundamental open problem in the area of blockchain protocols is whether the Bitcoin protocol is the only solution for building a secure transaction ledger. A recently proposed and widely considered alternative is the \GHOST protocol which, notably, was proposed to be at the core of Ethereum as well as other recent proposals for improved Bitcoin-like systems. % The \GHOST variant is touted as offering superior performance compared to Bitcoin (potentially offering block production speed up by a factor of more than 40) without a security loss. Motivated by this, in this work, we study from a provable security point of view the \GHOST protocol. We introduce a new formal framework for the analysis of blockchain protocols that relies on trees (rather than chains) and we showcase the power of the framework by providing a unified description of the \GHOST and Bitcoin protocols, the former of which we extract and formally describe. We then prove that \GHOST implements a robust transaction ledger'' (i.e., possesses liveness and persistence) and hence it is a provably secure alternative to Bitcoin; moreover, our bound for the liveness parameter is superior to that proven for the bitcoin backbone in line with the original expectation for \GHOST. Our proof follows a novel methodology for establishing that \GHOST is a robust transaction ledger compared to previous works, which may be of independent interest and can be applicable to other blockchain variants.

### Non-Interactive Provably Secure Attestations for Arbitrary RSA Prime

Wed, 07/05/2017 - 00:17
RSA public keys are central to many cryptographic applications; hence their validity is of primary concern to the scrupulous cryptographer. The most relevant properties of an RSA public key $(n, e)$ depend on the factors of $n$: are they properly generated primes? are they large enough? is $e$ co-prime with $\phi(n)$? etc. But of course, it is out of question to reveal $n$'s factors. Generic non-interactive zero-knowledge (NIZK) proofs can be used to prove such properties. However, generic NIZK proofs are not practical at all. For some very specific properties, specialized proofs exist but such \emph{ad hoc} proofs are naturally hard to generalize. This paper proposes a new type of general-purpose compact non-interactive proofs, called attestations, allowing the key generator to convince any third party that $n$ was properly generated. The proposed construction applies to any prime generation algorithm, and is provably secure in the Random Oracle Model. As a typical implementation instance, for a 138-bit security, verifying or generating an attestation requires $k=1024$ prime generations. For this instance, each processed message will later need to be signed or encrypted 14 times by the final users of the attested moduli.

### How to Keep a Secret: Leakage Deterring Public-key Cryptography

Tue, 07/04/2017 - 20:55
How is it possible to prevent the sharing of cryptographic functions? This question appears to be fundamentally hard to address since in this setting the owner of the key {\em is} the adversary: she wishes to share a program or device that (potentially only partly) implements her main cryptographic functionality. Given that she possesses the cryptographic key, it is impossible for her to be {\em prevented} from writing code or building a device that uses that key. She may though be {\em deterred} from doing so. We introduce {\em leakage-deterring} public-key cryptographic primitives to address this problem. Such primitives have the feature of enabling the embedding of owner-specific private data into the owner's public-key so that given access to {\em any} (even partially functional) implementation of the primitive, the recovery of the data can be facilitated. We formalize the notion of leakage-deterring in the context of encryption, signature, and identification and we provide efficient generic constructions that facilitate the recoverability of the hidden data while retaining privacy as long as no sharing takes place.