Subscribe to IACR Eprint feed
Updated: 9 hours 29 min ago

FPGA Cluster based high performance Cryptanalysis framework

Fri, 07/06/2018 - 19:18
In this paper a ‘FPGA cluster’ based framework for high performance Cryptanalysis has been proposed. The framework abstracts underlying networked FPGA cluster into a unified acceleration resource. It does so by implementing requested amount of computation kernels (cryptographic modules) and managing efficient distribution of the network band-width between the inter-FPGA and intra-FPGA computation kernels. Further agile methodology for developing such networked computation kernels with use of a high level language (Python) based HDL library and seamless integration with a user space crypt analysis application have been discussed. 40-bit partial key attack over AES256 has been demonstrated as a capability demonstration. Performance higher than clustered CPUs and GPUs at lower costs and power is reported.

Loamit: A Blockchain-based Residual Loanable-limit Query System

Fri, 07/06/2018 - 19:07
Currently, the blockchain technology is experiencing an exponential growth in the academia and industry. Blockchain may provide the fault-tolerance, tamper-resistance, credibility and privacy to users. In this paper, we propose a blockchain-based residual loanable-limit query system, called Loamit. Firstly, to the best of our knowledge, it is the first work to prevent that a client, who lacks the ability to repay, borrows an un-repayable amount of money from independent banks without releasing the personal privacy of client. Specifically, if a client wants to borrow a certain amount of money from a bank, then the bank can get the client's residual loanable-limit in the alliance of banks without knowing details of the client's previous loans and repayments. Secondly, most of data in Loamit is verifiable. Therefore, malicious banks can be checked out. Thirdly, Loamit is fault-tolerant since it may work smoothly as long as a certain number of banks are active and honest. Finally, we deploy the Loamit system on the Ethererum private blockchain and give the corresponding performance evaluation.

Issue, Trade, Redeem: Crossing Systems Bounds with Cryptocurrency-Backed Tokens

Fri, 07/06/2018 - 15:07
The ecosystem of cryptocurrencies has been steadily growing since the introduction of Bitcoin, the first decentralised digital currency. While the notion of trustless asset exchange lies at the core of most blockchain-based systems, existing cross-chain communication techniques expose limitations regarding security, performance, and usability. As a result, centralised liquidity providers remain the preferred way for cross-chain transactions. We systematise the notion of cryptocurrency-backed tokens, an approach towards trustless blockchain interoperability. We then propose a protocol for issuing, trading, and redeeming Bitcoin-backed tokens on Ethereum. Consequently, we provide an overview of system requirements, discuss open challenges regarding performance and security, and give an outlook on possible extensions. Our protocol, which requires no modifications to Bitcoin's consensus rules, can thereby be generalised to also support other cryptocurrencies.

Proofs of Replicated Storage Without Timing Assumptions

Fri, 07/06/2018 - 11:17
In this paper we provide a formal treatment of proof of replicated storage, a novel cryptographic primitive recently proposed in the context of a novel cryptocurrency, namely Filecoin. In a nutshell, proofs of replicated storage is a solution to the following problem: A user stores a file $m$ on $n$ different servers to ensure that the file will be available even if some of the servers fail. Using proof of retrievability, the user could check that every server is indeed storing the file. However, what if the servers collude and, in order to save on resources, decide to only store one copy of the file? A proof of replicated storage guarantees that, unless the server is indeed reserving the space necessary to store the $n$ copies of the file, the user will not accept the proof. While some candidate proofs of replicated storage have already been proposed, their soundness relies on timing assumptions i.e., the user must reject the proof if the prover does not reply within a certain time-bound. In this paper we provide the first construction of a proof of replication which does not rely on any timing assumptions.

Homomorphic Evaluation of Lattice-Based Symmetric Encryption Schemes

Fri, 07/06/2018 - 11:17
Optimizing performance of Fully Homomorphic Encryption (FHE) is nowadays an active trend of research in cryptography. One way of improvement is to use a hybrid construction with a classical symmetric encryption scheme to transfer encrypted data to the Cloud. This allows to reduce the bandwidth since the expansion factor of symmetric schemes (the ratio between the ciphertext and the plaintext length) is close to one, whereas for FHE schemes it is in the order of 1,000 to 1,000,000. However, such a construction requires the decryption circuit of the symmetric scheme to be easy to evaluate homomorphically. Several works have studied the cost of homomorphically evaluating classical block ciphers, and some recent works have suggested new homomorphic oriented constructions of block ciphers or stream ciphers. Since the multiplication gate of FHE schemes significantly increases the noise of the ciphertext, we cannot afford too many multiplication stages in the decryption circuit. Consequently, FHE-friendly symmetric encryption schemes have a decryption circuit with small multiplication depth. We aim at minimizing the cost of the homomorphic evaluation of the decryption of symmetric encryption schemes. To do so, we focus on schemes based on learning problems: Learning With Errors (LWE), Learning Parity with Noise (LPN) and Learning With Rounding (LWR). We show that they have lower multiplicative depth than usual block ciphers, and hence allow more FHE operations before a heavy bootstrapping becomes necessary. Moreover, some of them come with a security proof. Finally, we implement our schemes in HElib. Experimental evidence shows that they achieve lower amortized and total running time than previous performance from the literature: our schemes are from 10 to 10,000 more efficient for the time per bit and the total running time is also reduced by a factor between 20 to 10,000. Of independent interest, the security of our LWR-based scheme is related to LWE and we provide an efficient security proof that allows to take smaller parameters.

Side-Channel Analysis of SM2: A Late-Stage Featurization Case Study

Fri, 07/06/2018 - 10:16
SM2 is a public key cryptography suite originating from Chinese standards, including digital signatures and public key encryption. Ahead of schedule, code for this functionality was recently mainlined in OpenSSL, marked for the upcoming 1.1.1 release. We perform a security review of this implementation, uncovering various deficiencies ranging from traditional software quality issues to side-channel risks. To assess the latter, we carry out a side-channel security evaluation and discover that the implementation hits every pitfall seen for OpenSSL's ECDSA code in the past decade. We carry out remote timings, cache timings, and EM analysis, with accompanying empirical data to demonstrate secret information leakage during execution of both digital signature generation and public key decryption. Finally, we propose, implement, and empirically evaluate countermeasures.

Designing Efficient Dyadic Operations for Cryptographic Applications

Fri, 07/06/2018 - 10:00
Cryptographic primitives from coding theory are some of the most promising candidates for NIST's Post-Quantum Cryptography Standardization process. In this paper, we introduce a variety of techniques to improve operations on dyadic matrices, a particular type of symmetric matrices that appear in the automorphism group of certain linear codes. Besides the independent interest, these techniques find an immediate application in practice. In fact, one of the candidates for the Key Exchange functionality, called DAGS, makes use of quasi-dyadic matrices to provide compact keys for the scheme.

No-signaling Linear PCPs

Fri, 07/06/2018 - 09:59
In this paper, we give a no-signaling linear probabilistically checkable proof (PCP) system for P, i.e., a PCP system such that (1) the PCP oracle is a linear function and (2) the soundness holds against any (computational) no-signaling cheating prover, who answers each query according to a distribution that depends on the entire query set in a certain way. To the best of our knowledge, our construction is the first PCP system that satisfies these two properties simultaneously. As an application of our PCP system, we obtain a 2-message scheme for delegating computation by using a known transformation. Compared with existing 2-message delegation schemes based on standard cryptographic assumptions, our scheme requires preprocessing (which can be reused multiple times) but has a simpler structure and makes use of cheaper cryptographic primitives such as additive/multiplicative homomorphic encryption schemes.

Secure Oblivious Transfer from Semi-Commutative Masking

Fri, 07/06/2018 - 09:59
In this work we first define semi-commutative (invertible) masking structures which present a simple abstraction to capture the various examples of protocol design that are based on exponentiation-only style operations (such as discrete logarithm and isogeny based cryptography). We discuss two possible instantiations of our structure: The first is based on commutative group actions and captures both the action of exponentiation in the discrete logarithm setting and also the action of the class group of commutative endomorphism rings of elliptic curves, in the style of the CSIDH key-exchange protocol; the second is based on the semi-commutative action of isogenies of supersingular elliptic curves, in the style of the SIDH key-exchange protocol. We then design two oblivious transfer protocols using this structure and prove that they securely UC-realise the standard OT-functionality in the Random-Oracle-hybrid model against passive adversaries with static corruptions. This paper thus introduces the first oblivious transfer protocol based on supersingular isogenies that is proven secure in the UC framework.

A new perspective on the powers of two descent for discrete logarithms in finite fields

Fri, 07/06/2018 - 09:57
A new proof is given for the correctness of the powers of two descent method for computing discrete logarithms. The result is slightly stronger than the original work, but more importantly we provide a unified geometric argument, eliminating the need to analyse all possible subgroups of $\mathrm{PGL}_2(\mathbb{F}_q)$. Our approach sheds new light on the role of $\mathrm{PGL}_2$, in the hope to eventually lead to a complete proof that discrete logarithms can be computed in quasi-polynomial time in finite fields of fixed characteristic.

Pseudo Flawed-Smudging Generators and Their Application to Indistinguishability Obfuscation

Fri, 07/06/2018 - 09:55
We construct indistinguishability obfuscation from subexponentially secure Learning With Errors (LWE), bilinear maps, a constant-locality Pseudo Random Generator (PRG), and a new tool called Pseudo Flawed-smudging Generator (PFG). A PFG is an expanding function whose outputs $Y$ satisfy a weak form of pseudo randomness. Roughly speaking, for some polynomial bound $B$, and any $B$-bounded noise vector distribution $\chi$, it guarantees that for $e \gets \chi$, the distribution of $(e,\ Y + e)$ is indistinguishable from $(e', Y + e)$, where $e'$ is a fresh random sample from $\chi$ conditioned on agreeing with $e$ at a few, $o(\lambda)$, locations. In other words, $Y$ hides $e$ at all but a few locations. Our construction of indistinguishability obfuscation requires a PFG that is computable by a degree 2 polynomial over the integers and has polynomially bounded outputs. We finally propose a candidate of such PFGs and formalize an assumption under which it satisfies the requirements of our construction.

Hide The Modulus: A Secure Non-Interactive Fully Verifiable Delegation Scheme for Modular Exponentiations via CRT

Fri, 07/06/2018 - 09:48
Security protocols using public-key cryptography often requires large number of costly modular exponentiations (MEs). With the proliferation of resource-constrained (mobile) devices and advancements in cloud computing, delegation of such expensive computations to powerful server providers has gained lots of attention. In this paper, we address the problem of verifiably secure delegation of MEs using two servers, where at most one of which is assumed to be malicious (the OMTUP-model). We first show verifiability issues of two recent schemes: We show that a scheme from IndoCrypt 2016 does not offer full verifiability, and that a scheme for $n$ simultaneous MEs from AsiaCCS 2016 is verifiable only with a probability $0.5909$ instead of the author's claim with a probability $0.9955$ for $n=10$. Then, we propose the first non-interactive fully verifiable secure delegation scheme by hiding the modulus via Chinese Remainder Theorem (CRT). Our scheme improves also the computational efficiency of the previous schemes considerably. Hence, we provide a lightweight delegation enabling weak clients to securely and verifiably delegate MEs without any expensive local computation (neither online nor offline). The proposed scheme is highly useful for devices having (a) only ultra-lightweight memory, and (b) limited computational power (e.g. sensor nodes, RFID tags).

NOCUST - A Non-Custodial 2nd-Layer Financial Intermediary

Fri, 07/06/2018 - 09:39
Bitcoin is meant to offer a payment system where the users are custodians of their funds instead of entrusting a trusted financial institution. The limited transaction throughput of such permissionless blockchains, however, results for example in volatile transaction prices that hardly fit into traditional service level agreements required by professional institutions and cannot accommodate micro-transactions. We present a novel non-custodial 2nd-layer financial intermediary solution secure against double-spending that guarantees users control of funds through leveraging a smart contract enabled decentralized blockchain ledger as a means of dispute resolution. Two-party payment channels networks have been proposed as building blocks for trust-free payments that do not exhaust the resources of the blockchain; however, they bear multiple fundamental limitations. NOCUST is a specification for secure N-party payment hubs with improved transaction utility, cheaper operational costs and leaner user enrollment.

Membership Privacy for Fully Dynamic Group Signatures

Fri, 07/06/2018 - 09:38
Group signatures present a trade-off between the traditional goals of digital signatures and the signer's desire for privacy, allowing for the creation of unforgeable signatures in the name of a group which reveal nothing about the actual signer's identity beyond their group membership. Considering the desired properties formally opens up a possibility space of different security goals under various assumptions on trust placed in the designated entities of any scheme. Many models differ in their consideration of the variability of group membership as well, yet a formal treatment of the privacy of group membership status is lacking in all models, thus far. We address this issue, starting from the vantage point of the comprehensive model due to Bootle et al. (ACNS'16), who prove that any scheme secure in their model is also secure in the previous models. Their model allows for fully dynamic management of group membership by segmenting the scheme's lifetime into epochs during which group membership is static but between which users may join or leave the group. We extend the model of Bootle et al. by introducing formal notions of membership privacy. We then propose an efficient generic construction for a fully dynamic group signature scheme with membership privacy that is based on signatures with flexible public key (SFPK) and signatures on equivalence classes (SPSEQ). We instantiate the construction using a SFPK scheme based on the bilinear decisional Diffie-Hellman assumption and SPSEQ scheme by Fuchsbauer and Gay (PKC'18). The resulting scheme provides shorter signatures than existing schemes from standard assumption, while at the same time achieving stronger security guarantees.

Lower Bounds on Structure-Preserving Signatures for Bilateral Messages

Fri, 07/06/2018 - 09:37
Lower bounds for structure-preserving signature (SPS) schemes based on non-interactive assumptions have only been established in the case of unilateral messages, i.e. schemes signing tuples of group elements all from the same source group. In this paper, we consider the case of bilateral messages, consisting of elements from both source groups. We show that, for Type-III bilinear groups, SPS’s must consist of at least 6 group elements: many more than the 4 elements needed in the unilateral case, and optimal, as it matches a known upper bound from the literature. We also obtain the first non-trivial lower bounds for SPS’s in Type-II groups: a minimum of 4 group elements, whereas constructions with 3 group elements are known from interactive assumptions.

Function-Dependent Commitments for Verifiable Multi-Party Computation

Fri, 07/06/2018 - 09:31
In cloud computing, delegated computing raises the security issue of guaranteeing data authenticity during a remote computation. Existing solutions do not simultaneously provide fast correctness verification, strong security properties, and information-theoretic confidentiality. We introduce a novel approach, in the form of function-dependent commitments, that combines these strengths. We also provide an instantiation of function-dependent commitments for linear functions that is unconditionally, i.e. information-theoretically, hiding and relies on standard hardness assumptions. This powerful construction can for instance be used to build verifiable computing schemes providing information-theoretic confidentiality. As an example, we introduce a verifiable multi-party computation scheme for shared data providing public verifiability and unconditional privacy towards the servers and parties verifying the correctness of the result. Our scheme can be used to perform verifiable computations on secret shares while requiring only a single party to compute the audit data for verification. Furthermore, our verification procedure is asymptotically even more efficient than performing operations locally on the shared data. Thus, our solution improves the state of the art for authenticated computing, verifiable computing and multi-party computation.

BurnBox: Self-Revocable Encryption in a World Of Compelled Access

Fri, 07/06/2018 - 09:30
Dissidents, journalists, and others require technical means to protect their privacy in the face of compelled access to their digital devices (smartphones, laptops, tablets, etc.). For example, authorities increasingly force disclosure of all secrets, including passwords, to search devices upon national border crossings. We therefore present the design, implementation, and evaluation of a new system to help victims of compelled searches. Our system, called BurnBox, provides self-revocable encryption: the user can temporarily disable their access to specific files stored remotely, without revealing which files were revoked during compelled searches, even if the adversary also compromises the cloud storage service. They can later restore access. We formalize the threat model and provide a construction that uses an erasable index, secure erasure of keys, and standard cryptographic tools in order to provide security supported by our formal analysis. We report on a prototype implementation, which showcases the practicality of BurnBox.

Efficient Fully Homomorphic Encryption Scheme

Fri, 07/06/2018 - 09:30
Since Gentry discovered in 2009 the first fully homomorphic encryption scheme, the last few years have witnessed dramatic progress on designing more efficient homomorphic encryption schemes, and some of them have been implemented for applications. The main bottlenecks are in bootstrapping and large cipher expansion (the ratio of the size of ciphertexts to that of messages). Ducas and Micciancio (2015) show that homomorphic computation of one bit operation on LWE ciphers can be done in less than a second, which is then reduced by Chillotti et al. (2016, 2017) to 13ms. This paper presents a compact fully homomorphic encryption scheme that has the following features: (a) its cipher expansion is 6 with private-key encryption and 20 with public-key encryption; (b) all ciphertexts after any number (unbounded) of homomorphic bit operations have the same size and are always valid with the same error size; (c) its security is based on the LWE and RLWE problems (with binary secret keys) and the cost of breaking the scheme by the current approaches is at least $2^{160}$ bit operations. The scheme protects function privacy and provides a simple solution for secure two-party computation and zero knowledge proof of any language in NP.

Lattice-Based Dual Receiver Encryption and More

Tue, 07/03/2018 - 22:18
Dual receiver encryption (DRE), proposed by Diament et al. at ACM CCS 2004, is a special extension notion of public-key encryption, which enables two independent receivers to decrypt a ciphertext into a same plaintext. This primitive is quite useful in designing combined public key cryptosystems and denial of service attack-resilient protocols. Up till now, a series of DRE schemes are constructed from bilinear pairing groups and lattices. In this work, we introduce a construction of lattice-based DRE. Our scheme is indistinguishable against chosen-ciphertext attacks (IND-CCA) from the standard Learning with Errors (LWE) assumption with a public key of bit-size about $2nm\log q$, where $m$ and $q$ are small polynomials in $n$. Additionally, for the DRE notion in the identity-based setting, identity-based DRE (IB-DRE), we also give a lattice-based IB-DRE scheme that achieves chosen-plaintext and adaptively chosen identity security based on the LWE assumption with public parameter size about $(2\ell +1)nm\log q$, where $\ell$ is the bit-size of the identity in the scheme.

Tesseract: Real-Time Cryptocurrency Exchange using Trusted Hardware

Tue, 07/03/2018 - 19:11
We propose Tesseract, a secure real-time cryptocurrency exchange service. Existing centralized exchange designs are vulnerable to theft of funds, while decentralized exchanges cannot offer real-time cross-chain trades. All currently deployed exchanges are also vulnerable to frontrunning attacks. Tesseract overcomes these flaws and achieves a best-of-both-worlds design by using Intel SGX as a trusted execution environment. Furthermore, by running a consensus protocol among SGX-enabled servers, Tesseract mitigates denial-of-service attacks. Tesseract supports not only real-time cross-chain cryptocurrency trades, but also secure tokenization of assets pegged to cryptocurrencies. For instance, Tesseract-tokenized bitcoins can circulate on the Ethereum blockchain for use in smart contracts. We provide a reference implementation of Tesseract that supports Bitcoin, Ethereum, and similar cryptocurrencies.


IACR Eprint