Updated: 18 hours 22 min ago

Detecting General Algebraic Manipulation Attacks

Sun, 08/12/2018 - 09:32
Algebraic manipulation detection codes are a class of error detecting codes which have found numerous applications in cryptography. In this paper we extend these codes to defeat general algebraic attacks - we call such codes general algebraic manipulation detection (GAMD) codes. Positive results are shown for the existence of GAMDs for the families of tampering functions corresponding to point additions and polynomial functions over a finite field. Compared to non-malleable codes, we demonstrate both positive and negative results regarding the existence of GAMDs for arbitrary families of tampering functions.

Goshawk: A Novel Efficient, Robust and Flexible Blockchain Protocol

Sat, 08/11/2018 - 12:16
Proof of Work (PoW), a fundamental blockchain protocol, has been widely applied and thoroughly testifed in various decentralized cryptocurrencies, due to its intriguing merits including trustworthy sustainability, robustness against sybil attack, delicate incentive-compatibility, and openness to any participant. Meanwhile, PoW-powered blockchains still su&#64256;er from poor efciency, potential selfsh mining, to-be-optimized fairness and extreme inconvenience of protocol upgrading. Therefore, it is of great interest to design new PoW-based blockchain protocol to address or relieve the above issues so as to make it more applicable and feasible. To do so, frstly we take advantage of the basic framework (i.e., two-layer chain structure) adopted in Bitcoin-NG which was introduced by Eyal et al. to extend the throughput of Bitcoin-derived blockchains signifcantly via blocks of a two-layer structure, inheriting the high throughput merit while ridding o&#64256; the vulnerability to the attack of microblock swamping in Bitcoin-NG as well as attaining a better fairness property, by presenting two-level mining mechanism and incorporating this mechanism into the two-layer chain structure. Furthermore, to tackle the selfsh mining issue, strengthen the robustness against the “51%” attack of PoW miners, and o&#64256;er the &#64258;exibility for future protocol updating e&#64256;ectively, we borrow the idea of ticket-voting mechanism from DASH and Decred, and combine it with our improved structure elaborately to build a novel efcient, robust and &#64258;exible blockchain protocol (named Goshawk). Last but not the least, this scheme has been implemented and deployed in the testnet of the public blockchain project Hcash for months, and has demonstrated its stability and high efciency with such real-world test.

Order-Revealing Encryption: New Constructions, Applications, and Lower Bounds

Sat, 08/11/2018 - 03:24
In the last few years, there has been significant interest in developing methods to search over encrypted data. In the case of range queries, a simple solution is to encrypt the contents of the database using an order-preserving encryption (OPE) scheme (i.e., an encryption scheme that supports comparisons over encrypted values). However, Naveed et al. (CCS 2015) recently showed that OPE-encrypted databases are extremely vulnerable to "inference attacks." In this work, we consider a related primitive called order-revealing encryption (ORE), which is a generalization of OPE that allows for stronger security. We begin by constructing a new ORE scheme for small message spaces which achieves the "best-possible" notion of security for ORE. Next, we introduce a "domain-extension" technique and apply it to our small-message-space ORE. While our domain-extension technique does incur a loss in security, the resulting ORE scheme we obtain is more secure than all existing (stateless and non-interactive) OPE and ORE schemes which are practical. All of our constructions rely only on symmetric primitives. As part of our analysis, we also give a tight lower bound for OPE and show that no efficient OPE scheme can satisfy best-possible security if the message space contains just three messages. Thus, achieving strong notions of security for even small message spaces requires moving beyond OPE. Finally, we examine the properties of our new ORE scheme and show how to use it to construct an efficient range query protocol that is robust against the inference attacks of Naveed et al. We also give a full implementation of our new ORE scheme, and show that not only is our scheme more secure than existing OPE schemes, it is also faster: encrypting a 32-bit integer requires just 55 microseconds, which is more than 65 times faster than existing OPE schemes.

Compact Energy and Delay-Aware Authentication

Thu, 08/09/2018 - 18:13
Authentication and integrity are fundamental security services that are critical for any viable system. However, some of the emerging systems (e.g., smart grids, aerial drones) are delay-sensitive, and therefore their safe and reliable operation requires delay-aware authentication mechanisms. Unfortunately, the current state-of-the-art authentication mechanisms either incur heavy computations or lack scalability for such large and distributed systems. Hence, there is a crucial need for digital signature schemes that can satisfy the requirements of delay-aware applications. In this paper, we propose a new digital signature scheme that we refer to as Compact Energy and Delay-aware Authentication (CEDA). In CEDA, signature generation and verification only require a small-constant number of multiplications and Pseudo Random Function (PRF) calls. Therefore, it achieves the lowest end-to-end delay among its counterparts. Our implementation results on an ARM processor and commodity hardware show that CEDA has the most efficient signature generation on both platforms, while offering a fast signature verification. Among its delay-aware counterparts, CEDA has a smaller private key with a constant-size signature. All these advantages are achieved with the cost of a larger public key. This is a highly favorable trade-off for applications wherein the verifier is not memory-limited. We open-sourced our implementation of CEDA to enable its broad testing and adaptation.

Threshold Partially-Oblivious PRFs with Applications to Key Management

Thu, 08/09/2018 - 12:11
An Oblivious PRF (OPRF) is a protocol between a server holding a key to a PRF and a user holding an input. At the end of the interaction, the user learns the output of the OPRF on its input and nothing else. The server learns nothing, including nothing about the user's input or the function's output. OPRFs have found many applications in multiple areas of cryptography. Everspaugh et al. (Usenix 2015) introduced Partially Oblivious PRF (pOPRF) in which the OPRF accepts an additional non-secret input that can be chosen by the server itself, and showed applications in the setting of password hardening protocols. We further investigate pOPRFs showing new constructions, including distributed multi-server schemes, and new applications. We build simple pOPRFs from regular OPRFs, in particular obtaining very efficient DH-based pOPRFs, and provide (n,t)-threshold implementation of such schemes. We apply these schemes to build Oblivious Key Management Systems (KMS) as a much more secure alternative to traditional wrapping-based KMS. The new system hides keys and object identifiers from the KMS, offers unconditional security for key transport, enables forward security, provides key verifiability, reduces storage, and more. Further, we show how to provide all these features in a distributed threshold implementation that additionally protects the service against server compromise. Finally, we extend the scheme to a threshold Oblivious KMS with updatable encryption so that upon the periodic change of OPRF keys by the server, an efficient update procedure allows a client of the KMS service to non-interactively update all its encrypted data to be decryptable only by the new key. Our techniques improve on the efficiency and security of several recent works on updatable encryption from Crypto and Eurocrypt. We report on an implementation of the above schemes and their performance, showing their practicality and readiness for use in real-world systems. In particular, our pOPRF constructions achieve speeds of over an order of magnitude relative to previous pOPRF schemes.

Data Oblivious Genome Variants Search on Intel SGX

Thu, 08/09/2018 - 12:10
We show how to build a practical, private data oblivious genome variants search using Intel SGX. More precisely, we consider the problem posed in Track 2 of the iDash Privacy and Security Workshop 2017 competition, which was to search for variants with high $\chi^{2}$ statistic among certain genetic data over two populations. The winning solution of this iDash competition (developed by Carpov and Tortech) is extremely efficient, but not memory oblivious, which potentially made it vulnerable to a whole host of memory- and cache-based side channel attacks on SGX. In this paper, we adapt a framework in which we can exactly quantify this leakage. We provide a memory oblivious implementation with reasonable information leakage at the cost of some efficiency. Our solution is roughly an order of magnitude slower than the non-memory oblivious implementation, but still practical and much more efficient than naive memory-oblivious solutions--it solves the iDash problem in approximately 5 minutes. In order to do this, we develop novel definitions and models for oblivious dictionary merging, which may be of independent theoretical interest.

An Optimal Distributed Discrete Log Protocol with Applications to Homomorphic Secret Sharing

Thu, 08/09/2018 - 12:10
The distributed discrete logarithm (DDL) problem was introduced by Boyle et al. at CRYPTO 2016. A protocol solving this problem was the main tool used in the share conversion procedure of their homomorphic secret sharing (HSS) scheme which allows non-interactive evaluation of branching programs among two parties over shares of secret inputs. Let $g$ be a generator of a multiplicative group $\mathbb{G}$. Given a random group element $g^{x}$ and an unknown integer $b \in [-M,M]$ for a small $M$, two parties $A$ and $B$ (that cannot communicate) successfully solve DDL if $A(g^{x}) - B(g^{x+b}) = b$. Otherwise, the parties err. In the DDL protocol of Boyle et al., $A$ and $B$ run in time $T$ and have error probability that is roughly linear in $M/T$. Since it has a significant impact on the HSS scheme's performance, a major open problem raised by Boyle et al. was to reduce the error probability as a function of $T$. In this paper we devise a new DDL protocol that substantially reduces the error probability to $O(M \cdot T^{-2})$. Our new protocol improves the asymptotic evaluation time complexity of the HSS scheme by Boyle et al. on branching programs of size $S$ from $O(S^2)$ to $O(S^{3/2})$. We further show that our protocol is optimal up to a constant factor for all relevant cryptographic group families, unless one can solve the discrete logarithm problem in a \emph{short} interval of length $R$ in time $o(\sqrt{R})$. Our DDL protocol is based on a new type of random walk that is composed of several iterations in which the expected step length gradually increases. We believe that this random walk is of independent interest and will find additional applications.

Supersingular Isogeny Diffie-Hellman Authenticated Key Exchange

Thu, 08/09/2018 - 12:09
We propose two authenticated key exchange protocols from supersingular isogenies. Our protocols are the first post-quantum one-round Diffie-Hellman type authenticated key exchange ones in the following points: one is secure under the quantum random oracle model and the other resists against maximum exposure where a non-trivial combination of secret keys is revealed. The security of the former and the latter is proven under an isogeny version of the decisional and gap Diffie-Hellman assumption, respectively. We also propose a new approach for invalidating the Galbraith-Vercauteren attack for the gap problem.

Towards Lightweight Cryptographic Primitives with Built-in Fault-Detection

Thu, 08/09/2018 - 12:08
We introduce a novel approach for designing symmetric ciphers to resist fault injection. The approach is fairly generic and applies to round functions of block ciphers, cryptographic permutations and stream ciphers. We showcase our method with a new permutation called FRIT and perform fault analysis on a simulated hardware and actual software implementation. We present performance results for software and hardware implementations with and without the fault detection mechanism. On a Cortex-M4 platform the overhead of the countermeasure in cycles is 83%. The penalty on resources for hardware implementations depends on the hardware and can be as low as 56%.

A $k$-out-of-$n$ Ring Signature with Flexible Participation for Signers

Thu, 08/09/2018 - 12:08
A $k$-out-of-$n$ ring signature is a kind of anonymous signature that can be performed by any member in a group. This signature allows the creation of valid signatures if and only if actual signers more than or equal to $k$ sign the message among $n$ possible signers. In this paper, we present a new $k$-out-of-$n$ ring signature. Our signature has a remarkable property: When the signature is updated from $k$-out-of-$n$ to $(k+\alpha)$-out-of-$n$, the previous signers do not need to sign a message again. Our scheme can reuse'' the old signature, whereas the previous schemes revoke it and create a signature from scratch. We call this property {{flexibility}}'' and formalize it rigorously. Our signature scheme has a multiple ring structure, each ring of which is based on $1$-out-of-$n$ ring signature. The structure of our scheme is completely different from that of conventional schemes, such as a secret-sharing type. The signers' keys are mostly independent of each user, thanks to a part of keys which use a special hash function. We give the results of provable security for our scheme.

DiSE: Distributed Symmetric-key Encryption

Thu, 08/09/2018 - 12:07
Threshold cryptography provides a mechanism for protecting secret keys by sharing them among multiple parties, who then jointly perform cryptographic operations. An attacker who corrupts upto a threshold number of parties cannot recover the secrets or violate security. Prior works in this space have mostly focused on definitions and constructions for public-key cryptography and digital signatures, and thus do not capture the security concerns and efficiency challenges of symmetric-key based applications which commonly use long-term (unprotected) master keys to protect data at rest, authenticate clients on enterprise networks, and secure data and payments on IoT devices. We put forth the first formal treatment for distributed symmetric-key encryption, proposing new notions of correctness, privacy and authenticity in presence of malicious attackers. We provide strong and intuitive game-based definitions that are easy to understand and yield efficient constructions. We propose a generic construction of threshold authenticated encryption based on any distributed pseudorandom function (DPRF). When instantiated with the two different DPRF constructions proposed by Naor, Pinkas and Reingold (Eurocrypt 1999) and our enhanced versions, we obtain several efficient constructions meeting different security definitions. We implement these variants and provide extensive performance comparisons. Our most efficient instantiation uses only symmetric-key primitives and achieves a throughput of upto 1 million encryptions/decryptions per seconds, or alternatively a sub-millisecond latency with upto 18 participating parties.

Towards Key-Dependent Integral and Impossible Differential Distinguishers on 5-Round AES

Thu, 08/09/2018 - 12:01
Reduced-round AES has been a popular underlying primitive to design new cryptographic schemes and thus its security including distinguishing properties deserves more attention. At Crypto'16, a key-dependent integral distinguisher on 5-round AES was put forward, which opened up a new direction to take more insights into the distinguishing properties of AES. After that, two key-dependent impossible differential (ID) distinguishers on 5-round AES were proposed at FSE'16 and CT-RSA'18, respectively. It is strange that the current key-dependent integral distinguisher requires significantly higher complexities than the key-dependent ID distinguishers, even though they are constructed with the same property of MixColumns ($2^{128} \gg 2^{98.2}$). Proposers of the 5-round key-dependent distinguishers claimed that the corresponding integral and ID distinguishers can only work under chosen-ciphertext and chosen-plaintext settings, respectively, which is very different from the situations of traditional key-independent distinguishers. In this paper, we first construct a novel key-dependent integral distinguisher on 5-round AES with $2^{96}$ chosen plaintexts, which is much better than the previous key-dependent integral distinguisher that requires the full codebook proposed at Crypto'16. Secondly, we show that both distinguishers are valid under either chosen-plaintext setting or chosen-ciphertext setting, which is different from the claims of previous cryptanalysis. However, under different settings, complexities of key-dependent integral distinguishers are very different while those of the key-dependent ID distinguishers are almost the same. We analyze the reasons for it.

Round5: Compact and Fast Post-Quantum Public-Key Encryption

Thu, 08/09/2018 - 11:27
Standardization bodies such as NIST and ETSI are currently seeking quantum resistant alternatives to vulnerable RSA and elliptic curve-based public-key algorithms. In this context, we present Round5, a lattice-based cryptosystem providing a key encapsulation mechanism and a public-key encryption scheme. Round5 is based on the General Learning with Rounding problem, unifying non-ring and ring lattice rounding problems into one. Usage of rounding combined with a tight analysis leads to significantly reduced bandwidth and randomness requirements. Round5's reliance on prime-order cyclotomic rings offers a large design space allowing fine-grained parameter optimization. The use of sparse-ternary secret keys improves performance and significantly reduces decryption failure rates at minimal additional cost. The use of error-correcting codes further improves the latter. Round5 parameters have been carefully optimized for bandwidth, while the design facilitates efficient implementation. As a result, Round5 has leading performance characteristics among all NIST post-quantum candidates, and at the same time attains conservative security levels that fully fit NIST's security categories. Round5's schemes share common building blocks, simplifying (security and operational) analysis and code review. Finally, Round5 proposes various approaches of refreshing the system public parameter $\textbf{A}$, which efficiently prevent precomputation and back-door attacks.

Dronecrypt - An Efficient Cryptographic Framework for Small Aerial Drones

Thu, 08/09/2018 - 05:05
Aerial drones are becoming an integral part of application domains including but not limited to, military operations, package delivery, construction, monitoring and search/rescue operations. It is critical to ensure the cyber security of networked aerial drone systems in these applications. Standard cryptographic services can be deployed to provide basic security services; however, they have been shown to be inefficient in terms of energy and time consumption, especially for small aerial drones with resource-limited processors. Therefore, there is a significant need for an efficient cryptographic framework that can meet the requirements of small aerial drones. We propose an improved cryptographic framework for small aerial drones, which offers significant energy efficiency and speed advantages over standard cryptographic techniques. (i) We create (to the best of our knowledge) the first optimized public key infrastructure (PKI) based framework for small aerial drones, which provides energy efficient techniques by harnessing special precomputation methods and optimized elliptic curves. (ii) We also integrate recent light-weight symmetric primitives into our PKI techniques to provide a full-fledged cryptographic framework. (iii) We implemented standard counterparts and our proposed techniques on an actual small aerial drone (Crazyflie 2.0), and provided an in-depth energy analysis. Our experiments showed that our improved cryptographic framework achieves up to 35$\times$ lower energy consumption than its standard counterpart.

Impossible Differential Cryptanalysis on Deoxys-BC-256

Wed, 08/08/2018 - 06:19
Deoxys is a third-round candidate of the CAESAR competition. This paper presents the first impossible differential cryptanalysis of Deoxys-BC-256 which is used in Deoxys as an internal tweakable block cipher. First, we find a 4.5-round ID characteristic by utilizing a miss-in-the-middle-approach. We then present several cryptanalyses based upon the 4.5 rounds distinguisher against round-reduced Deoxys-BC-256 in both single-key and related-key settings. Our contributions include impossible differential attacks on up to 8-rounds Deoxys-BC-256 in the tweak-key model which is, to the best of our knowledge, the first independent investigation of the security of Deoxys-BC-256 in the single-key model. Our attack reaches 9 rounds in the related-key related-tweak model which has a slightly higher data complexity than the best previous results obtained by a rectangle attack presented at FSE 2018 but requires a lower memory complexity with an equal time complexity.

HydRand: Practical Continuous Distributed Randomness

Wed, 08/08/2018 - 06:02
A reliable source of randomness is not only an essential building block in various cryptographic, security, and distributed systems protocols, but also plays an integral part in the design of many new blockchain proposals. Consequently, the topic of publicly-verifiable, bias-resistant and unpredictable randomness has recently enjoyed increased attention in a variety of scientific contributions, as well as projects from the industry. In particular random beacon protocols, which are aimed at continuous operation, can be a vital component for many current Proof-of-Stake based distributed ledger proposals. We improve upon existing random beacon approaches by introducing HydRand, a novel distributed protocol based on publicly-verifiable secret sharing (PVSS) to ensure unpredictability, bias-resistance, and public-verifiability of a continuous sequence of random beacon values. Furthermore, HydRand is able to provide guaranteed output delivery of randomness at regular and predictable intervals in the presence of adversarial behavior and does not rely on a trusted dealer for the initial setup. In comparison to existing PVSS based approaches which achieve similar properties, our solution improves scalability by lowering the communication complexity from $\mathcal{O}(n^3)$ to $\mathcal{O}(n^2)$. Furthermore, we are the first to present a detailed comparison of recently described schemes and protocols that can be used for implementing random beacons.

AUDIT: Practical Accountability of Secret Processes

Wed, 08/08/2018 - 03:45
The US federal court system is exploring ways to improve the accountability of electronic surveillance, an opaque process often involving cases sealed from public view and tech companies subject to gag orders against informing surveilled users. One judge has proposed publicly releasing some metadata about each case on a paper cover sheet as a way to balance the competing goals of (1) secrecy, so the target of an investigation does not discover and sabotage it, and (2) accountability, to assure the public that surveillance powers are not misused or abused. Inspired by the courts' accountability challenge, we illustrate how accountability and secrecy are simultaneously achievable when modern cryptography is brought to bear. Our system improves configurability while preserving secrecy, offering new tradeoffs potentially more palatable to the risk-averse court system. Judges, law enforcement, and companies publish commitments to surveillance actions, argue in zero-knowledge that their behavior is consistent, and compute aggregate surveillance statistics by multi-party computation (MPC). We demonstrate that these primitives perform efficiently at the scale of the federal judiciary. To do so, we implement a hierarchical form of MPC that mirrors the hierarchy of the court system. We also develop statements in succinct zero-knowledge (SNARKs) whose specificity can be tuned to calibrate the amount of information released. All told, our proposal not only offers the court system a flexible range of options for enhancing accountability in the face of necessary secrecy, but also yields a general framework for accountability in a broader class of "secret information processes."

Security notions for cloud storage and deduplication

Tue, 08/07/2018 - 12:29
Cloud storage is in widespread use by individuals and enterprises but introduces a wide array of attack vectors. A basic step for users is to encrypt their data, but it is not obvious what precise security properties are required for encryption. Furthermore, cloud storage providers often use techniques such as data deduplication for improving efficiency which restricts the application of semantically-secure encryption. Generic security goals and attack models have thus far proved elusive: primitives are considered in isolation and protocols are often proved secure under ad hoc models for restricted classes of adversaries. We provide a generic syntax for storage systems that allows us to formally model natural security notions for cloud storage and deduplication. We define security notions for confidentiality and integrity in encrypted cloud storage and determine relations between these notions. We show how to build cloud storage systems that satisfy our defined security notions using generic cryptographic components.

Practical Order-Revealing Encryption with Limited Leakage

Mon, 08/06/2018 - 22:12
In an order-preserving encryption scheme, the encryption algorithm produces ciphertexts that preserve the order of their plaintexts. Order-preserving encryption schemes have been studied intensely in the last decade, and yet not much is known about the security of these schemes. Very recently, Boneh et al. (Eurocrypt 2015) introduced a generalization of order-preserving encryption, called order-revealing encryption, and presented a construction which achieves this notion with best-possible security. Because their construction relies on multilinear maps, it is too impractical for most applications and therefore remains a theoretical result. In this work, we build efficiently implementable order-revealing encryption from pseudorandom functions. We present the first efficient order-revealing encryption scheme which achieves a simulation-based security notion with respect to a leakage function that precisely quantifies what is leaked by the scheme. In fact, ciphertexts in our scheme are only about 1.6 times longer than their plaintexts. Moreover, we show how composing our construction with existing order-preserving encryption schemes results in order-revealing encryption that is strictly more secure than all preceding order-preserving encryption schemes.

Multi-Collision Resistance: A Paradigm for Keyless Hash Functions

Mon, 08/06/2018 - 12:45
We introduce a new notion of multi-collision resistance for keyless hash functions. This is a natural relaxation of collision resistance where it is hard to find multiple inputs with the same hash in the following sense. The number of colliding inputs that a polynomial-time non-uniform adversary can find is not much larger than its advice. We discuss potential candidates for this notion and study its applications. Assuming the existence of such hash functions, we resolve the long-standing question of the round complexity of zero knowledge protocols --- we construct a 3-message zero knowledge argument against arbitrary polynomial-size non-uniform adversaries. We also improve the round complexity in several other central applications, including a 3-message succinct argument of knowledge for NP, a 4-message zero-knowledge proof, and a 5-message public-coin zero-knowledge argument. Our techniques can also be applied in the keyed setting, where we match the round complexity of known protocols while relaxing the underlying assumption from collision-resistance to keyed multi-collision resistance. The core technical contribution behind our results is a domain extension transformation from multi-collision-resistant hash functions for a fixed input length to ones with an arbitrary input length and a local opening property. The transformation is based on a combination of classical domain extension techniques, together with new information-theoretic tools. In particular, we define and construct a new variant of list-recoverable codes, which may be of independent interest.