Updated: 11 hours 5 min ago

Full-Hiding (Unbounded) Multi-Input Inner Product Functional Encryption from the $k$-Linear Assumption

Tue, 01/16/2018 - 09:19
This paper presents two non-generic and practically efficient private key multi-input functional encryption (MIFE) schemes for the multi-input version of the inner product functionality that are the first to achieve simultaneous message and function privacy, namely, the full-hiding security for a non-trivial multi-input functionality under well-studied cryptographic assumptions. Our MIFE schemes are built in bilinear groups of prime order, and their security is based on the standard $k$-Linear ($k$-LIN) assumption (along with the existence of semantically secure symmetric key encryption and pseudorandom functions). Our constructions support polynomial number of encryption slots (inputs) without incurring any super-polynomial loss in the security reduction. While the number of encryption slots in our first scheme is apriori bounded, our second scheme can withstand an arbitrary number of encryption slots. Prior to our work, there was no known MIFE scheme for a non-trivial functionality, even without function privacy, that can support an unbounded number of encryption slots without relying on any heavy-duty building block or little-understood cryptographic assumption.

A Simple Reduction from State Machine Replication to Binary Agreement in Partially Synchronous or Asynchronous Networks

Tue, 01/16/2018 - 09:19
The recent advent of blockchains has spurred a huge interest in the research and development of numerous cryptocurrencies as well as understanding the fundamental concepts that underly this technology. At the heart of this design is the classic state machine replication protocol in which a group of n machines (out of which f are Byzantine) want to agree on an ever-growing log of transactions. In this paper, we present a simple black box reduction from state machine replication (SMR) to the classical binary agreement (BA) protocol on top of a fully decentralized network. We consider both synchronous and partially synchronous/asynchronous settings for our reduction. We also present an algorithm for a reduction from BA to SMR, thus establishing an equivalence between the two. In each of these settings, we analyze our algorithms with respect to the required security properties. Although there is prior work that establishes these reductions, our solutions are simpler (at the cost of efficiency) and useful from a pedagogical point of view.

New Insights into Divide-and-Conquer Attacks on the Round-Reduced Keccak-MAC

Tue, 01/16/2018 - 09:11
Keccak is the final winner of SHA-3 competition and it can be used as message authentic codes as well. The basic and balanced divide-and-conquer attacks on Keccak-MAC were proposed by Dinur et al. at Eurocrypt 2015. The idea of cube attacks is used in the two attacks to divide key bits into small portions. In this paper, by carefully analysing the mappings used in Keccak-MAC, it is found that some cube variables could divide key bits into smaller portions and so better divide-and-conquer attacks are obtained. Furthermore, in order to evaluate the resistance of Keccak-MAC against divide-and-conquer attacks based on cubes, we theoretically analyse the lower bounds of the complexities of divide-and-conquer attacks. It is shown that the lower bounds of the complexities are still not better than those of the conditional cube tester proposed by Senyang Huang et al.. This indicates that Keccak-MAC can resist the divide-and-conquer attack better than the conditional cube tester. We hope that these techniques still could provide some new insights on the future cryptanalysis of Keccak.

Leakage-resilient Algebraic Manipulation Detection Codes with Optimal Parameters

Tue, 01/16/2018 - 09:10
Algebraic Manipulation Detection (AMD) codes [CDF+08] are keyless message authentication codes that protect messages against additive tampering by the adversary assuming that the adversary cannot “see" the codeword. For certain applications, it is unreasonable to assume that the adversary computes the added offset without any knowledge of the codeword c. Recently, Ahmadi and Safavi-Naini [AS13], and then Lin, Safavi-Naini, and Wang [LSW16] gave a construction of leakage-resilient AMD codes where the adversary has some partial information about the codeword before choosing added offset, and the scheme is secure even conditioned on this partial information. In this paper we show the bounds on the leakage rate r and the code rate k for leakage-resilient AMD codes. In particular we prove that 2r + k < 1 and for the weak case (security is averaged over a uniformly random message) r +k < 1. These bounds hold even if adversary is polynomial-time bounded, as long as we allow leakage function to be arbitrary. We present the constructions of AMD codes that (asymptotically) fulfill above bounds for almost full range of parameters r and k. This shows that above bounds and constructions are in-fact optimal. In the last section we show that if a leakage function is computationally bounded (we use Ideal Cipher Model) then it is possible to break these bounds.

Certifying RSA Public Keys with an Efficient NIZK

Tue, 01/16/2018 - 09:09
In many applications, it is important to verify that an RSA public key (N,e) specifies a permutation, in order to prevent attacks due to adversarially-generated public keys. We design and implement a simple and efficient noninteractive zero-knowledge protocol (in the random oracle model) for this task. The key feature of our protocol is compatibility with existing RSA implementations and standards. The protocol works for any choice of e. Applications concerned about adversarial key generation can just append our proof to the RSA public key without any other modifications to existing code or cryptographic libraries. Users need only perform a one-time verification of the proof to ensure that raising to the power e is a permutation of the integers modulo N. For typical parameter settings, the proof consists of nine integers modulo N; generating the proof and verifying it both require about nine modular exponentiations.

Post-Quantum Signcryption From Lattice-Based Signatures

Tue, 01/16/2018 - 09:02
In data security, the main objectives one tries to achieve are privacy, data integrity and authentication. In a public-key setting, privacy is reached through asymmetric encryption and both data integrity and authentication through signature. Meeting all the security objectives for data exchange requires to use a concatenation of those primitives in an encrypt-then-sign or sign-then-encrypt fashion. Signcryption aims at providing all the security requirements in one single primitive at a lower cost than using encryption and signature together. Most existing signcryption schemes are using ElGamal-based or pairing-based techniques and thus rely on the decisional Diffie-Hellman assumption. With the current growth of a quantum threat, we seek for post-quantum counterparts to a vast majority of public-key primitives. In this work, we propose a signcryption scheme based on the GLP signature inspired from a construction of Malone-Lee. It comes in two flavors, one integrating the usual lattice-based key exchange into GLP and the other merging the signature scheme with a RLWE encryption, which is more efficient, but outputs a larger signcryptext. Using the same set of operations as in existing constructions, our scheme can be implemented efficiently on various platforms, reusing optimized pieces of software or hardware presented in previous works.

High-Resolution EM Attacks Against Leakage-Resilient PRFs Explained - And An Improved Construction

Tue, 01/16/2018 - 09:01
Achieving side-channel resistance through Leakage Resilience (LR) is highly relevant for embedded devices where requirements of other countermeasures such as e.g. high quality random numbers are hard to guarantee. The main challenge of LR lays in the initialization of a secret pseudorandom state from a long-term key and public input. Leakage-Resilient Pseudo-Random Functions (LR-PRFs) aim at solving this by bounding side-channel leakage to non-exploitable levels through frequent re-keying. Medwed et al. recently presented an improved construction at ASIACRYPT 2016 which uses 'unknown-inputs' in addition to limited data complexity and correlated algorithmic noise from parallel S-boxes. However, a subsequent investigation uncovered a vulnerability to high-precision EM analysis on FPGA. In this paper, we follow up on the reasons why such attacks succeed on FPGAs. We find that in addition to the high spatial resolution, it is mainly the high temporal resolution which leads to the reduction of algorithmic noise from parallel S-boxes. While spatial resolution is less threatening for smaller technologies than the used FPGA, temporal resolution will likely remain an issue since balancing the timing behavior of signals in the nanosecond range seems infeasible today. Nonetheless, we present an improvement of the ASIACRYPT 2016 construction to effectively protect against EM attacks with such high spatial and high temporal resolution. We carefully introduce additional key entropy into the LR-PRF construction to achieve a high remaining security level even when implemented on FPGAs. With this improvement, we finally achieve side-channel secure LR-PRFs in a practical and simple way under verifiable empirical assumptions.

More Efficient (Almost) Tightly Secure Structure-Preserving Signatures

Tue, 01/16/2018 - 09:01
We provide a structure-preserving signature (SPS) scheme with an (almost) tight security reduction to a standard assumption. Compared to the state-of-the-art tightly secure SPS scheme of Abe et al. (CRYPTO 2017), our scheme has smaller signatures and public keys (of about $$56\%$$, resp. $$40\%$$ of the size of signatures and public keys in Abe et al.'s scheme), and a lower security loss (of $$O(\log Q)$$ instead of $$O(\lambda)$$, where $$\lambda$$ is the security parameter, and $$Q=poly(\lambda)$$ is the number of adversarial signature queries). While our scheme is still less compact than structure-preserving signature schemes \emph{without} tight security reduction, it significantly lowers the price to pay for a tight security reduction. In fact, when accounting for a non-tight security reduction with larger key (i.e., group) sizes, the computational efficiency of our scheme becomes at least comparable to that of non-tightly secure SPS schemes. Technically, we combine and refine recent existing works on tightly secure encryption and SPS schemes. Our technical novelties include a modular treatment (that develops an SPS scheme out of a basic message authentication code), and a refined hybrid argument that enables a lower security loss of $$O(\log Q)$$ (instead of $$O(\lambda)$$).

Crypt-DAC: Cryptographically Enforced Dynamic Access Control in the Cloud

Tue, 01/16/2018 - 00:32
Enabling cryptographically enforced access controls for data hosted in untrusted cloud is attractive for many users and organizations. However, designing efficient cryptographically enforced dynamic access control system in the cloud is still a chal- lenging issue. In this paper, we propose Crypt-DAC, a system that provides practical cryptographic enforcement of dynamic access control. Crypt-DAC revokes access permissions by delegating the cloud to update encrypted data. In Crypt-DAC, a file is encrypted by a symmetric key list which records a file key and a sequence of revocation keys. In each revocation, a dedicated administrator sends a new revocation key to the cloud and requests it to encrypt the file with a new layer of encryption and update the encrypted key list accordingly. Crypt-DAC proposes three key techniques to constrain the size of key list and encryption layers as revocations continuously happen. As a result, Crypt- DAC enforces dynamic access control that provides efficiency, as it does not require expensive decryption/re-encryption and uploading/re-uploading of large data at the administrator side, and security, as it immediately revokes access permissions. We use formalization framework and system implementation to demonstrate the security and efficiency of our construction.

Feasibility and Infeasibility of Secure Computation with Malicious PUFs

Mon, 01/15/2018 - 14:07
A recent line of work has explored the use of physically uncloneable functions (PUFs) for secure computation, with the goals of (1) achieving universal composability without additional setup, and/or (2) obtaining unconditional security (i.e., avoiding complexity-theoretic assumptions). Initial work assumed that all PUFs, even those created by an attacker, are honestly generated. Subsequently, researchers have investigated models in which an adversary can create malicious PUFs with arbitrary behavior. Researchers have considered both malicious PUFs that might be stateful, as well as malicious PUFs that can have arbitrary behavior but are guaranteed to be stateless. We settle the main open questions regarding secure computation in the malicious-PUF model: * We prove that unconditionally secure oblivious transfer is impossible, even in the stand-alone setting, if the adversary can construct (malicious) stateful PUFs. * If the attacker is limited to creating (malicious) stateless PUFs, then universally composable two-party computation is possible without computational assumptions.

Bitcoin as a Transaction Ledger: A Composable Treatment

Mon, 01/15/2018 - 05:55
Bitcoin is perhaps the most prominent example of a distributed cryptographic protocol that is extensively used in reality. Nonetheless, existing security proofs are property-based, and as such they do not support composition. In this work we put forth a universally composable treatment of the Bitcoin protocol. We specify the goal that Bitcoin aims to achieve as a ledger functionality in the (G)UC model of Canetti et al. (TCC'07). Our ledger functionality is weaker than the one recently proposed by Kiayias, Zhou, and Zikas (EUROCRYPT'16), but unlike the latter suggestion, which is arguably not implementable given the Bitcoin assumptions, we prove that the one proposed here is securely UC realized under standard assumptions by an appropriate abstraction of Bitcoin as a UC protocol. We further show how known property-based approaches can be cast as special instances of our treatment and how their underlying assumptions can be cast in (G)UC without restricting the environment or the adversary.

SPECTRE: A Fast and Scalable Cryptocurrency Protocol

Mon, 01/15/2018 - 05:20
A growing body of research on Bitcoin and other permissionless cryptocurrencies that utilize Nakamoto's blockchain has shown that they do not easily scale to process a high throughput of transactions, or to quickly approve individual transactions; blocks must be kept small, and their creation rates must be kept low in order to allow nodes to reach consensus securely. As of today, Bitcoin processes a mere 3-7 transactions per second, and transaction confirmation takes at least several minutes. We present SPECTRE, a new protocol for the consensus core of cryptocurrencies that remains secure even under high throughput and fast confirmation times. At any throughput, SPECTRE is resilient to attackers with up to 50\% of the computational power (up until the limit defined by network congestion and bandwidth constraints). SPECTRE can operate at high block creation rates, which implies that its transactions confirm in mere seconds (limited mostly by the round-trip-time in the network). Key to SPECTRE's achievements is the fact that it satisfies weaker properties than classic consensus requires. In the conventional paradigm, the order between any two transactions must be decided and agreed upon by all non-corrupt nodes. In contrast, SPECTRE only satisfies this with respect to transactions performed by honest users. We observe that in the context of money, two conflicting payments that are published concurrently could only have been created by a dishonest user, hence we can afford to delay the acceptance of such transactions without harming the usability of the system. Our framework formalizes this weaker set of requirements for a cryptocurrency's distributed ledger. We then provide a formal proof that SPECTRE satisfies these requirements.

Multi-Cast Key Distribution: Scalable, Dynamic and Provably Secure Construction

Mon, 01/15/2018 - 01:21
In this paper, we propose a two-round dynamic multi-cast key distribution (DMKD) protocol under the star topology with a central authentication server. Users can share a common session key without revealing any information of the session key to the server, and can join/leave to/from the group at any time even after establishing the session key. Our protocol is scalable because communication and computation costs of each user are independent from the number of users. Also, our protocol is still secure if either private key or session-specific randomness of a user is exposed. Furthermore, time-based backward secrecy is guaranteed by renewing the session key for every time period even if the session key is exposed. We introduce the first formal security definition for DMKD under the star topology in order to capture such strong exposure resilience and time-based backward secrecy. We prove that our protocol is secure in our security model in the standard model.

Study of Deep Learning Techniques for Side-Channel Analysis and Introduction to ASCAD Database

Sun, 01/14/2018 - 20:33

Optimizing Trees for Static Searchable Encryption

Sun, 01/14/2018 - 20:31
Searchable symmetric encryption (SSE) enables data owners to conduct searches over encrypted data stored by an untrusted server, retrieving only those encrypted files that match the search queries. Several recent schemes employ a server-side encrypted index in the form of a search tree where each node stores a bit vector denoting for each keyword whether any file in its subtree contains that keyword. Our work is motivated by the observation that the way data is distributed in such a search tree has a big impact on the cost of searches. For single-keyword queries, it impacts the number of different paths that must be followed to find all the matching files; for multi-keyword queries, the arrangement of the tree also impacts the number of nodes visited during the search on paths that do not lead to any satisfying data elements. We present three algorithms that improve the performance of SSE schemes based on tree indexes and prove that for cases where the search cost is high, the cost of our algorithms converges to the cost of the optimal tree. In our experiments, the resulting search trees outperform the arbitrary search trees used in previous works by a factor of up to two

Semantic Security Invariance under Variant Computational Assumptions

Sun, 01/14/2018 - 20:31
A game-based cryptographic proof is a relation that establishes equivalence between probabilistic sequences of actions by real and ideal world players. The author of a proof selects a hardness assumption system for their proof upon which to base their subsequent statements. In this paper, we prove the existence of proof-invariant transformations for varying hardness assumptions. We show that for two systems satisfying certain algebraic properties any proof in one system has an equivalent valid proof in the other. This validates Kurosawa’s remark about the existence of proof similarities. Our result implies a correspondence between the Learning With Errors (LWE) problems and both the Elliptic Curve Discrete Log problem (ECDLP) and the Discrete Logarithm (DLOG) problem. To illustrate this result, we provide a series of example transformations in the appendix. The concrete result of this paper is a prototype proof translation tool.

A Constructive Perspective on Signcryption Security

Sun, 01/14/2018 - 20:30
Signcryption is a public-key cryptographic primitive, originally introduced by Zheng (Crypto '97), that allows parties to establish secure communication without the need of prior key agreement. Instead, a party registers its public key at a certificate authority (CA), and only needs to retrieve the public key of the intended partner from the CA before being able to protect the communication. As suggested by the name, signcryption schemes provide both authenticity and confidentiality of sent messages and are motivated like their symmetric-key counterparts, i.e., authenticated-encryption schemes: better achievable performance compared to generic compositions of signature and encryption schemes, and a simpler interface to applications. Although introduced two decades ago, the question which security notions of signcryption are adequate in what applications has still not reached a fully satisfying answer, even for the basic ones. To address this question, we conduct a constructive analysis of this public-key primitive. Similar to previous constructive studies for other important primitives, this treatment allows to identify the natural goal that signcryption schemes should achieve and to formalize this goal in a composable language. More specifically, we capture the goal of signcryption as a gracefully-degrading secure network, which is basically a network of independent parties that allows secure communication between any two parties. However, when a party is compromised, its respective security guarantees are lost, while all guarantees for the remaining users stay unaffected. We show which security notions are sufficient to realize this kind of secure network from a certificate authority (or key registration resource) and insecure communication. As a finding of independent interest, our treatment shows that a weaker notion of the traditional insider security notion is actually sufficient. Last but not least, our study unveils that the graceful-degradation property is actually an essential feature of signcryption that separates it from alternative and more natural constructions that achieve a secure network from the same assumptions. This shows the vital importance of the insider security notion for signcryption and strongly supports, in contrast to the initial belief, the recent trend to consider the insider security notion as the standard notion for signcryption.

Attacks and Countermeasures for White-box Designs

Sun, 01/14/2018 - 20:28

Impossible Differential Cryptanalysis on Deoxys-BC-256

Sun, 01/14/2018 - 20:28
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.

The distinguishing attack on Speck, Simon, Simeck, HIGHT and LEA

Sun, 01/14/2018 - 20:27
The purpose of the work is to estimate the resistance of lightweight block ciphers Speck, Simon, Simeck, HIGHT, LEA to a distinguishing attack. (This attack is a form of cryptanalysis on data encrypted by a cipher that allows an attacker to distinguish the encrypted data from random data.) Modern lightweight block ciphers must be designed to be immune to such an attack. It turned out that Speck, Simon, HIGHT and LEA showed a sufficient resistance to the distinguishing attack, but Simeck with 48-bit block size and 96-bit key size was not immune to this attack.