Updated: 3 hours 19 min ago

### Ouroboros Crypsinous: Privacy-Preserving Proof-of-Stake

Wed, 11/28/2018 - 22:55
We present Ouroboros Crypsinous, the first privacy-preserving proof-of-stake (PoS) blockchain protocol. To model its security we give a thorough treatment of private ledgers in the universal composition (UC) setting that might be of independent interest. To prove our protocol secure against adaptive attacks, which are particularly critical in the PoS setting, we introduce a new coin evolution technique that relies on a SNARKs mechanism and key-private forward secure encryption. The latter primitive---and the associated construction---can be of independent interest. We stress that existing approaches to private blockchains, such as the proof-of-work-based Zerocash are analyzed only against static corruptions.

### A CCA-secure collusion-resistant Identity-based Proxy Re-encryption Scheme

Wed, 11/28/2018 - 22:32
Cloud storage enables its users to store confidential information as encrypted files in the cloud. A cloud user (say Alice) can share her encrypted files with another user (say Bob) by availing proxy re-encryption services of the cloud. Proxy Re-Encryption (PRE) is a cryptographic primitive that allows transformation of ciphertexts from Alice to Bob via a semi-trusted proxy, who should not learn anything about the shared message. Typically, the re-encryption rights are enabled only for a bounded, fixed time and malicious parties may want to decrypt or learn messages encrypted for Alice, even beyond that time. The basic security notion of PRE assumes the proxy (cloud) is semi-trusted, which is seemingly insufficient in practical applications. The proxy may want to collude with Bob to obtain the private keys of Alice for later use. Such an attack is called collusion attack, allowing colluders to illegally access all encrypted information of Alice in the cloud. Hence, achieving collusion resistance is indispensable to real-world scenarios. Realizing collusion-resistant PRE has been an interesting problem in the ID-based setting. To this end, several attempts have been made to construct a collusion-resistant IB-PRE scheme and we discuss their properties and weaknesses in this paper. We also present a new collusion-resistant IB-PRE scheme that meets the adaptive CCA security under the decisional bilinear Diffie-Hellman hardness assumption and its variant in the random oracle model.

### Applications of H-Technique: Revisiting Symmetric Key Security Analysis

Wed, 11/28/2018 - 22:31
The Coefficients H Technique (also called H-technique), by Patarin, is a tool to obtain upper bound on the distinguishing advantage. The tool is known for providing quite simpler and tight bound proofs as compared to some other well-known tools such as Game-playing technique and Random Systems methodology. In this paper, we aim to provide a brief survey on the H-technique. The survey is in three parts: First, we redevelop the necessary nomenclatures and tools required to study the security of symmetric key designs. Second, we give a full description of the H-technique and show that it can provide optimal bounds on the distinguishing advantage. Third, we give simpler proofs for some popular symmetric key designs, across different paradigms, using the H-technique.

### On Kilian's Randomization of Multilinear Map Encodings

Wed, 11/28/2018 - 22:30
Indistinguishability obfuscation constructions based on matrix branching programs generally proceed in two steps: first apply Kilian's randomization of the matrix product computation, and then encode the matrices using a multilinear map scheme. In this paper we observe that by applying Kilian's randomization after encoding, the complexity of the best attacks is significantly increased for CLT13. This implies that much smaller parameters can be used, which improves the efficiency of the constructions by several orders of magnitude. As an application, we describe the first concrete implementation of non-interactive Diffie-Hellman key exchange secure against existing attacks. Key exchange was originally the most straightforward application of multilinear maps; however it was quickly broken for the three known families of multilinear maps (GGH13, CLT13 and GGH15). Here we describe the first implementation of key exchange based on CLT13 that is resistant against the Cheon et al. attack. For N=4 users and a medium (62 bits) level of security, our implementation requires 8 GB of public parameters, and a few minutes for the derivation of a shared key. Without Kilian's randomization of encodings our construction would be completely unpractical, as it would require more than 100 TB of public parameters.

### Direct Anonymous Attestation with Optimal TPM Signing Efficiency

Wed, 11/28/2018 - 22:29
Direct Anonymous Attestation (DAA) is an anonymous signature scheme, which is designed to allow the Trusted Platform Module (TPM), a small chip embedded in a host computer, to attest to the state of the host system, while preserving the privacy of the user. DAA provides two signature modes: fully anonymous signatures and pseudonymous signatures. To generate a DAA signature, the calculations are divided between the TPM and the host. One goal for designing new DAA schemes is to reduce the signing burden on the TPM as much as possible, since the TPM has only limited resources when compared to the host and the computational overhead of the TPM dominates the whole signing performance. In an optimal DAA scheme, the signing workload on the TPM will be no more than that required for a normal signature. DAA has developed about fifteen years, but no scheme has achieved this optimal signing efficiency for both signature modes. In this paper, we propose the first DAA scheme which achieves this optimal TPM signing efficiency for both signature modes. In particular, the TPM takes only a single exponentiation in a prime-order group when generating a DAA signature. Additionally, this single exponentiation can be precomputed, which enables our scheme to achieve fast online signing time. Our DAA scheme is provably secure under the DDH, DBDH and q-SDH assumptions in the Universally Composable (UC) security model. Our scheme can be implemented using the existing TPM 2.0 commands, and thus is compatible with the TPM 2.0 specification. There are three important use cases for DAA: quoting platform configuration register values, certifying a key and signing a message. We have implemented and benchmarked the commands needed for these use cases on an Infineon TPM 2.0 chip. Based on these benchmark results, our scheme is about twice as fast as the existing DAA schemes supported by TPM 2.0 in terms of signing efficiency. In addition, our DAA scheme supports selective attribute disclosure, which can satisfy more application requirements. We also extend our DAA scheme to support signature-based revocation and to guarantee privacy against subverted TPMs. The two extended DAA schemes keep the TPM signing efficiency optimal for both signature modes, and outperform existing related schemes in terms of signing performance.

### Freestyle, a randomized version of ChaCha for resisting offline brute-force and dictionary attacks

Wed, 11/28/2018 - 22:26
This paper introduces Freestyle, a randomized, and variable round version of the ChaCha cipher. Freestyle demonstrates the concept of hash based halting condition, where a decryption attempt with an incorrect key is likely to take longer time to halt. This makes it resistant to key-guessing attacks i.e. brute-force and dictionary based attacks. Freestyle uses a novel approach for ciphertext randomization by using random number of rounds for each block of message, where the exact number of rounds are unknown to the receiver in advance. Due to its inherent random behavior, Freestyle provides the possibility of generating up to $2^{256}$ different ciphertexts for a given key, nonce, and message; thus resisting key and nonce reuse attacks. This also makes cryptanalysis through known-plaintext, chosen-plaintext, and chosen-ciphertext attacks difficult in practice. Freestyle is highly customizable, which makes it suitable for both low-powered devices as well as security-critical applications. It is ideal for: (i) applications that favor ciphertext randomization and resistance to key-guessing and key reuse attacks; and (ii) situations where ciphertext is in full control of an adversary for carrying out an offline key-guessing attack.

### Lightweight AE and HASH in a Single Round Function

Wed, 11/28/2018 - 22:23
To deal with message streams, which is required by many symmetric cryptographic functionalities (MAC, AE, HASH), we propose a lightweight round function called Thin Sponge. We give a framework to construct all these functionalities (MAC, AE, and HASH) using the same Thin Sponge round function. Besides the common security assumptions behind traditional symmetric algorithms, the security of our schemes depends on the hardness of problems to find collisions of some states. We give a class of constructions of Thin Sponge, which is improvement of the round function of Trivium and ACORN. We give simple criteria for determining parameters. According to these criteria, we give an example, which achieves all functionalities in a single round function and hence can be realized by the same hardware. Our algorithm is also efficient in software.

### Verifying liquidity of Bitcoin contracts

Wed, 11/28/2018 - 22:16
A landmark security property of smart contracts is liquidity: in a non-liquid contract, it may happen that some funds remain frozen. The relevance of this issue is witnessed by a recent liquidity attack to the Ethereum Parity Wallet, which has frozen 160M USD within the contract, making this sum unredeemable by any user. We address the problem of verifying liquidity of Bitcoin contracts. Focussing on itML, a contracts DSL with a computationally sound compiler to Bitcoin, we study various notions of liquidity. Our main result is that liquidity of BitML contracts is decidable, in all the proposed variants. To prove this, we first transform the infinite-state semantics of BitML into a finite-state one, which focusses on the behaviour of any given set of contracts, abstracting the moves of the context. With respect to the chosen contracts, this abstraction in sound and complete. Our decision procedure for liquidity is then based on model-checking the finite space of states of the abstraction. The computational soundness of the BitML compiler allows to lift this result from the symbolic to the computational level: if our decision procedure establishes that a contract is liquid, then it will be such also under a computational adversary, and vice versa.

### From Keys to Databases -- Real-World Applications of Secure Multi-Party Computation

Wed, 11/28/2018 - 08:44
We discuss the widely increasing range of applications of a cryptographic technique called Multi-Party Computation. For many decades this was perceived to be of purely theoretical interest, but now it has started to find application in a number of use cases. We highly in this paper a number of these, ranging from securing small high value items such as cryptographic keys, through to securing an entire database.

### Privacy-Preserving Multibiometric Authentication in Cloud with Untrusted Database Providers

Wed, 11/28/2018 - 06:36
This paper introduces a secure and privacy-preserving mechanism for biometric-based user authentication in a distributed manner. The design combines three modalities (face, iris and fingerprint) according to user’s performance strength parameters (False Acceptance and False Rejection Rates). We use a user-specific weighted score level fusion strategy to determine the final multimodal result. The stored unimodal templates are held by distinct database providers that can be malicious. Privacy regulations recognize biometric data as sensitive, hence their handling and storage in an untrusted environment with third parties are challenging. Therefore, we utilize Multi- Party Computation to enhance security among authentication stages. In contrast to the existing research, the novelty of this approach lies in performing multimodal authentication without storing private information in a single database, nor transferring the calculation results to any third party. The proposed protocol is analyzed to assess its usability, security and efficiency (execution time is less than a second under the studied scenario).

### Blockwise $p$-Tampering Attacks on Cryptographic Primitives, Extractors, and Learners

Tue, 11/27/2018 - 14:52
Austrin, Chung, Mahmoody, Pass and Seth (Crypto'14) studied the notion of bitwise $p$-tampering attacks over randomized algorithms in which an efficient virus' gets to control each bit of the randomness with independent probability $p$ in an online way. The work of Austrin et al. showed how to break certain privacy primitives' (e.g., encryption, commitments, etc.) through bitwise $p$-tampering, by giving a bitwise $p$-tampering biasing attack for increasing the average $E[f(U_n)]$ of any efficient function $f \colon \{0,1\}^n \to [-1,+1]$ by $\Omega(p \cdot Var[f(U_n)])$ where $Var[f(U_n)]$ is the variance of $f(U_n)$. In this work, we revisit and extend the bitwise tampering model of Austrin et al. to blockwise setting, where blocks of randomness becomes tamperable with independent probability $p$. Our main result is an efficient blockwise $p$-tampering attack to bias the average $E[f(X)]$ of any efficient function $f$ mapping arbitrary $X$ to $[-1,+1]$ by $\Omega(p \cdot Var[f(X)])$ regardless of how $X$ is partitioned into individually tamperable blocks $X=(X_1,\dots,X_n)$. Relying on previous works, our main biasing attack immediately implies efficient attacks against the privacy primitives as well as seedless multi-source extractors, in a model where the attacker gets to tamper with each block (or source) of the randomness with independent probability $p$. Further, we show how to increase the classification error of deterministic learners in the so called targeted poisoning' attack model under Valiant's adversarial noise. In this model, an attacker has a target' test data $d$ in mind and wishes to increase the error of classifying $d$ while she gets to tamper with each training example with independent probability $p$ an in an online way.

### From FE Combiners to Secure MPC and Back

Tue, 11/27/2018 - 14:10
Functional encryption (FE) has incredible applications towards computing on encrypted data. However, constructing the most general form of this primitive has remained elusive. Although some candidate constructions exist, they rely on nonstandard assumptions, and thus, their security has been questioned. An FE combiner attempts to make use of these candidates while minimizing the trust placed on any individual FE candidate. Informally, an FE combiner takes in a set of FE candidates and outputs a secure FE scheme if at least one of the candidates is secure. Another fundamental area in cryptography is secure multi-party computation (MPC), which has been extensively studied for several decades. In this work, we initiate a formal study of the relationship between functional encryption (FE) combiners and secure multi-party computation (MPC). In particular, we show implications in both directions between these primitives. As a consequence of these implications, we obtain the following main results. 1) A two round semi-honest MPC protocol in the plain model secure against up to (n-1) corruptions with communication complexity proportional only to the depth of the circuit being computed assuming LWE. Prior two round protocols that achieved this communication complexity required a common reference string. 2) A functional encryption combiner based on pseudorandom generators (PRGs) in NC^1. Such PRGs can be instantiated from assumptions such as DDH and LWE. Previous constructions of FE combiners were known only from the learning with errors assumption. Using this result, we build a universal construction of functional encryption: an explicit construction of functional encryption based only on the assumptions that functional encryption exists and PRGs in NC^1.

### Actively Secure Garbled Circuits with Constant Communication Overhead in the Plain Model

Sun, 11/25/2018 - 02:02
We consider the problem of constant-round secure two-party computation in the presence of active (malicious) adversaries. We present the first protocol that has only a constant multiplicative communication overhead compared to Yao's protocol for passive adversaries, and can be implemented in the plain model by only making a black-box use of (parallel) oblivious transfer and a pseudo-random generator. This improves over the polylogarithmic overhead of the previous best protocol. A similar result could previously be obtained only in an amortized setting, using preprocessing, or by assuming bit-oblivious-transfer as an ideal primitive that has a constant cost. We present two variants of this result, one which is aimed at minimizing the number of oblivious transfers and another which is aimed at optimizing concrete efficiency. Our protocols are based on a novel combination of previous techniques together with a new efficient protocol to certify that pairs of strings transmitted via oblivious transfer satisfy a global relation. Settling for security with correlated abort'', the concrete communication complexity of the second variant of our protocol can beat the best previous protocols with the same kind of security even for realistic values of the circuit size and the security parameter. This variant is particularly attractive in the offline-online setting, where the online cost is dominated by a single evaluation of an authenticated garbled circuit, and can also be made non-interactive using the Fiat-Shamir heuristic.

### Regular Lossy Functions and Their Applications in Leakage-Resilient Cryptography

Sat, 11/24/2018 - 04:59
In STOC 2008, Peikert and Waters introduced a powerful primitive called lossy trapdoor functions (LTFs). In a nutshell, LTFs are functions that behave in one of two modes. In the normal mode, functions are injective and invertible with a trapdoor. In the lossy mode, functions statistically lose information about their inputs. Moreover, the two modes are computationally indistinguishable. In this work, we put forward a relaxation of LTFs, namely, regular lossy functions (RLFs). Compared to LTFs, the functions in the normal mode are not required to be efficiently invertible or even unnecessary to be injective. Instead, they could also be lossy, but in a regular manner. We also put forward richer abstractions of RLFs, namely all-but-one regular lossy functions (ABO-RLFs) and one-time regular lossy filters (OT-RLFs). We show that (ABO)-RLFs admit efficient constructions from both a variety of number- theoretic assumptions and hash proof system (HPS) for subset membership problems satisfying natural algebraic properties. Thanks to the relaxations on functionality, the constructions enjoy much compact key size and better computational efficiency than that of (ABO)-LTFs. We demonstrate the utility of RLFs and their extensions in the leakage-resilient cryptography. As a special case of RLFs, lossy functions imply leakage-resilient injective one-way functions with optimal leakage rate $1 - o(1)$. ABO-RLFs (or OT-RLFs) immediately imply leakage-resilient one-time message authentication code (MAC) with optimal leakage rate $1 - o(1)$. ABO-RLFs together with HPS give rise to leakage-resilient chosen-ciphertext (CCA) secure key encapsulation mechanisms (KEM) (this approach extends naturally to the identity-based setting). Combining the construction of ABO-RLFs from HPS, this gives the first leakage-resilient CCA-secure public-key encryption (PKE) with optimal leakage rate based solely on HPS, and thus goes beyond the barrier posed by Dodis et al. (Asiacrypt 2010). Our construction also applies to the identity-based setting, yielding LR-CCA secure IB-KEM with higher leakage rate than previous works.

### Computing Discrete Logarithms in an Interval

Fri, 11/23/2018 - 15:01
The discrete logarithm problem in an interval of size $N$ in a group $G$ is: Given $g, h \in G$ and an integer $N$ to find an integer $0 \le n \le N$, if it exists, such that $h = g^n$. Previously the best low-storage algorithm to solve this problem was the van Oorschot and Wiener version of the Pollard kangaroo method. The heuristic average case running time of this method is $(2 + o(1)) \sqrt{N}$ group operations. We present two new low-storage algorithms for the discrete logarithm problem in an interval of size $N$. The first algorithm is based on the Pollard kangaroo method, but uses 4 kangaroos instead of the usual two. We explain why this algorithm has heuristic average case expected running time of $(1.715 + o(1)) \sqrt{N}$ group operations. The second algorithm is based on the Gaudry-Schost algorithm and the ideas of our first algorithm. We explain why this algorithm has heuristic average case expected running time of $(1.661 + o(1)) \sqrt{N}$ group operations. We give experimental results that show that the methods do work close to that predicted by the theoretical analysis. This is a revised version since the published paper that contains a corrected proof of Theorem 6 (the statement of Theorem 6 is unchanged). We thank Ravi Montenegro for pointing out the errors.

### David & Goliath Oblivious Affine Function Evaluation - Asymptotically Optimal Building Blocks for Universally Composable Two-Party Computation from a Single Untrusted Stateful Tamper-Proof Hardware Token

Fri, 11/23/2018 - 14:08
In a seminal work, Katz (Eurocrypt 2007) showed that parties being able to issue tamper-proof hardware can implement universally composable secure computation without a trusted setup. Our contribution to the line of research initiated by Katz is a construction for general, information-theoretically secure, universally composable two-party computation based on a single stateful tamper-proof token. We provide protocols for multiple one-time memories, multiple commitments in both directions, and also bidirectional oblivious transfer. From this, general secure two-party computation (and even one-time programs) can be implemented by known techniques. Moreover, our protocols have asymptotically optimal communication complexity. The central part of our work is a construction for oblivious affine function evaluation (OAFE), which can be seen as a generalization of the oblivious transfer primitive: Parametrized by a finite field F and a dimension k, the OAFE primitive allows a designated sender to choose an affine function f:F->F^k, such that hidden from the sender a designated receiver can learn f(x) for exactly one input x in F of his choice. All our abovementioned results build upon this primitive and it may also be of particular interest for the construction of garbled arithmetic circuits.

### CSIDH: An Efficient Post-Quantum Commutative Group Action

Fri, 11/23/2018 - 09:28
We propose an efficient commutative group action suitable for non-interactive key exchange in a post-quantum setting. Our construction follows the layout of the Couveignes-Rostovtsev-Stolbunov cryptosystem, but we apply it to supersingular elliptic curves defined over a large prime field $\mathbb F_p$, rather than to ordinary elliptic curves. The Diffie-Hellman scheme resulting from the group action allows for public-key validation at very little cost, runs reasonably fast in practice, and has public keys of only 64 bytes at a conjectured AES-128 security level, matching NIST's post-quantum security category I.

### Adaptively Secure and Succinct Functional Encryption: Improving Security and Efficiency, Simultaneously

Wed, 11/21/2018 - 02:23
Functional encryption (FE) is advanced encryption that enables us to issue functional decryption keys where functions are hardwired. When we decrypt a ciphertext of a message $m$ by a functional decryption key where a function $f$ is hardwired, we can obtain $f(m)$ and nothing else. We say FE is selectively or adaptively secure when target messages are chosen at the beginning or after function queries are sent, respectively. In the setting of weakly-selective setting, function queries are also chosen at the beginning. We say FE is single-key/collusion-resistant when it is secure against adversaries that are given only-one/polynomially-many functional decryption keys, respectively. We say FE is sublinearly-succinct/succinct when the running time of an encryption algorithm is sublinear/poly-logarithmic in the function description size, respectively. In this study, we propose adaptively secure, collusion-resistant, and succinct (we call fully-equipped'') PKFE schemes for circuits. More specifically, we propose a generic transformation from weakly-selectively secure, single-key, and sublinearly-succinct PKFE for circuits into fully-equipped PKFE for circuits. We assume only the existence of weakly-selectively secure, single-key, and sublinearly-succinct PKFE for circuits. That is, our transformation relies on \emph{neither} concrete assumptions such as learning with errors \emph{nor} indistinguishability obfuscation. This is the first generic construction of fully-equipped PKFE that does not rely on indistinguishability obfuscation. As side-benefits of our results, we obtain the following primitives from weakly-selectively, single-key, and sublinearly-succinct PKFE for circuits: (1) laconic oblivious transfer (2) succinct garbling scheme for Turing machines (3) selectively secure, collusion-resistant, and succinct PKFE for Turing machines (4) low-overhead adaptively secure traitor tracing (5) key-dependent-message secure and leakage-resilient public-key encryption. We also obtain a semi-generic transformation from simulation-based adaptively secure garbling schemes into adaptively indistinguishable garbling schemes whose online complexity does not depend on the output length.

### New Automatic Search Tool for Impossible Differentials and Zero-Correlation Linear Approximations

Tue, 11/20/2018 - 22:13
Impossible differential and zero-correlation linear cryptanalysis are two of the most powerful cryptanalysis methods in the field of symmetric key cryptography. There are several automatic tools to search such trails for ciphers with S-boxes. These tools focus on the properties of linear layers, and idealize the underlying S-boxes, i.e., assume any input and output difference pairs are possible. In reality, such S-box never exists, and the possible output differences with any fixed input difference can be at most half of the entire space. Hence, some of the possible differential trails under the ideal world become impossible in reality, possibly resulting in impossible differential trails for more rounds. In this paper, we firstly take the differential and linear properties of non-linear components such as S-box into consideration and propose a new automatic tool to search impossible differential trails for ciphers with S-box. We then generalize the tool to modulo addition, and apply it to ARX ciphers. To demonstrate the usefulness of the tool, we apply it to HIGHT, SHACAL-2, LEA, LBlock. As a result, it improves the best existing results of each cipher.

### Tighter Security Proofs for GPV-IBE in the Quantum Random Oracle Model

Tue, 11/20/2018 - 06:43
In (STOC, 2008), Gentry, Peikert, and Vaikuntanathan proposed the first identity-based encryption (GPV-IBE) scheme based on a post-quantum assumption, namely, the learning with errors (LWE) assumption. Since their proof was only made in the random oracle model (ROM) instead of the quantum random oracle model (QROM), it remained unclear whether the scheme was truly post-quantum or not. In (CRYPTO, 2012), Zhandry developed new techniques to be used in the QROM and proved the security of GPV-IBE in the QROM, hence answering in the affirmative that GPV-IBE is indeed post-quantum. However, since the general technique developed by Zhandry incurred a large reduction loss, there was a wide gap between the concrete efficiency and security level provided by GPV-IBE in the ROM and QROM. Furthermore, regardless of being in the ROM or QROM, GPV-IBE is not known to have a tight reduction in the multi-challenge setting. Considering that in the real-world an adversary can obtain many ciphertexts, it is desirable to have a security proof that does not degrade with the number of challenge ciphertext. In this paper, we provide a much tighter proof for the GPV-IBE in the QROM in the single-challenge setting. In addition, we also show that a slight variant of the GPV-IBE has an almost tight reduction in the multi-challenge setting both in the ROM and QROM, where the reduction loss is independent of the number of challenge ciphertext. Our proof departs from the traditional partitioning technique and resembles the approach used in the public key encryption scheme of Cramer and Shoup (CRYPTO, 1998). Our proof strategy allows the reduction algorithm to program the random oracle the same way for all identities and naturally fits the QROM setting where an adversary may query a superposition of all identities in one random oracle query. Notably, our proofs are much simpler than the one by Zhandry and conceptually much easier to follow for cryptographers not familiar with quantum computation. Although at a high level, the techniques used for the single and multi-challenge setting are similar, the technical details are quite different. For the multi-challenge setting, we rely on the Katz-Wang technique (CCS, 2003) to overcome some obstacles regarding the leftover hash lemma.