Subscribe to IACR Eprint feed
Updated: 1 hour 53 min ago

Towards Practical Privacy-Preserving Genome-Wide Association Study

Wed, 01/02/2019 - 12:02
The deployment of Genome-wide association studies (GWASs) requires genomic information of a large population to produce reliable results. This raises significant privacy concerns, making people hesitate to contribute their genetic information to such studies. We propose two provably secure solutions to address this challenge: (1) a somewhat homomorphic encryption approach, and (2) a secure multiparty computation approach. Unlike previous work, our approach does not rely on adding noise to the input data, nor does it reveal any information about the patients. Our protocols calculate the $\chi^2$ statistic in a privacy-preserving manner, without revealing any information other than the significance of the statistic; hence not even the statistic value itself. We significantly increased the efficiency of our protocols by introducing a new masking technique to perform the secure comparison. Our implementations demonstrated that both approaches are efficient. The secure multiparty computation technique completes its execution in approximately 2~ms for data contributed by one million subjects.

XCLAIM: A Framework for Blockchain Interoperability

Wed, 01/02/2019 - 12:00
Building trustless cross-blockchain trading protocols is challenging. Centralized exchanges thus remain the preferred route to executing transfers across blockchains. However, these services require trust and therefore undermine the very nature of the blockchains on which they operate. To overcome this, several decentralized exchanges have recently emerged which offer support for atomic cross-chain swaps (ACCS). ACCS enable the trustless exchange of cryptocurrencies across blockchains, and are the only known mechanism to do so. However, ACCS suffer significant limitations; they are slow, inefficient and costly, meaning that they are rarely used in practice. We present XCLAIM: the first generic framework for achieving trustless and efficient cross-chain exchanges using cryptocurrency-backed assets (CbAs). XCLAIM offers protocols for issuing, transferring, swapping and redeeming CbAs securely in a non-interactive manner on existing blockchains. We instantiate XCLAIM between Bitcoin and Ethereum and evaluate our implementation; it costs less than USD 0.50 to issue an arbitrary amount of Bitcoin-backed tokens on Ethereum. We show XCLAIM is not only faster, but also significantly cheaper than atomic cross-chain swaps. Finally, XCLAIM is compatible with the majority of existing blockchains without modification, and enables several novel cryptocurrency applications, such as cross-chain payment channels and efficient multi-party swaps.

Privacy-Preserving Logistic Regression Training

Wed, 01/02/2019 - 10:37
Logistic regression is a popular technique used in machine learning to construct classification models. Since the construction of such models is based on computing with large datasets, it is an appealing idea to outsource this computation to a cloud service. The privacy-sensitive nature of the input data requires appropriate privacy preserving measures before outsourcing it. Homomorphic encryption enables one to compute on encrypted data directly, without decryption, and can be used to mitigate the privacy concerns raised by using a cloud service. In this paper, we propose an algorithm (and its implementation) to train a logistic regression model on a homomorphically encrypted dataset. The core of our algorithm consists of a new iterative method that can be seen as a simplified form of the fixed Hessian method, but with a much lower multiplicative complexity. We test the new method on two interesting real life applications: the first application is in medicine and constructs a model to predict the probability for a patient to have cancer, given genomic data as input; the second application is in finance and the model predicts the probability of a credit card transaction to be fraudulent. The method produces accurate results for both applications, comparable to running standard algorithms on plaintext data. This article introduces a new simple iterative algorithm to train a logistic regression model that is tailored to be applied on a homomorphically encrypted dataset. This algorithm can be used as a privacy-preserving technique to build a binary classification model and can be applied in a wide range of problems that can be modelled with logistic regression. Our implementation results show that our method can handle the large datasets used in logistic regression training.

Improved (Almost) Tightly-Secure Structure-Preserving Signatures

Mon, 12/31/2018 - 15:48
Structure Preserving Signatures (SPS) allow the signatures and the messages signed to be further encrypted while retaining the ability to be proven valid under zero-knowledge. In particular, SPS are tailored to have structure suitable for Groth-Sahai NIZK proofs. More precisely, the messages, signatures, and verification keys are required to be elements of groups that support efficient bilinear-pairings (bilinear groups), and the signature verification consists of just evaluating one or more bilinear-pairing product equations. Since Groth-Sahai NIZK proofs can (with zero-knowledge) prove the validity of such pairing product equations, it leads to interesting applications such as blind signatures, group signatures, traceable signatures, group encryption, and delegatable credential systems. In this paper, we further improve on the SPS scheme of Abe, Hofheinz, Nishimaki, Ohkubo and Pan (CRYPTO 2017) while maintaining only an $O(\lambda)$-factor security reduction loss to the SXDH assumption. In particular, we compress the size of the signatures by almost 40%, and reduce the number of pairing-product equations in the verifier from fifteen to seven. Recall that structure preserving signatures are used in applications by encrypting the messages and/or the signatures, and hence these optimizations are further amplified as proving pairing-product equations in Groth-Sahai NIZK system is not frugal. While our scheme uses an important novel technique introduced by Hofheinz (EuroCrypt 2017), i.e., structure-preserving adaptive partitioning, our approach to building the signature scheme is different and this leads to the optimizations mentioned. Thus we make progress towards an open problem stated by Abe et al (CRYPTO 2017) to design more compact SPS-es with smaller number of group elements.

Jevil's Encryption Systems

Mon, 12/31/2018 - 15:44
Imagine if, given a puzzle, you could encrypt a plaintext detailing the location of a prize reward such that they who solves the puzzle can use this solution to decrypt your prize information, without knowing the solution to the puzzle yourself. The Jevil family of encryption systems is a novel set of real-world encryption systems based on the promising foundation of witness encryption. The first Jevil encryption systems comprise of Pentomino, Sudoku and Nonogram-based encryption, allowing for the encryption of plaintext such that solving a Pentomino, Sudoku or Nonogram puzzle yields to decryption. Jevil encryption systems are shown to be correct, secure and to achieve high performance with modest overhead.

Fully Bideniable Interactive Encryption

Mon, 12/31/2018 - 08:14
While standard encryption guarantees secrecy of the encrypted plaintext only against an attacker that has no knowledge of the communicating parties’ keys and randomness of encryption, deniable encryption [Canetti et al., Crypto’96] provides the additional guarantee that the plaintext remains secret even in face of authoritative entities that attempt to coerce (or bribe) communicating parties to expose their internal states, including the plaintexts, keys and randomness. To achieve this guarantee, deniable encryption is equipped with a faking algorithm which allows parties to generate fake keys and randomness that make the ciphertext appear consistent with any plaintext of the parties’ choice. To date, only partial results were known: either deniability against coercing only the sender, or against coercing only the receiver [Sahai-Waters, STOC ‘14] or schemes satisfying weaker notions of deniability [O’Neil et al., Crypto ‘11]. In this paper we present the first fully bideniable interactive encryption scheme, thus resolving the 20-years-old open problem. Our scheme also satisfies an additional, incomparable to standard deniability, property called off-the-record deniability, which we introduce in this paper. This property guarantees that, even if the sender claims that one plaintext was used and the receiver claims a different one, the adversary has no way of figuring out who is lying - the sender, the receiver, or both. This is useful when parties don’t have means to agree on what fake plaintext to claim, or when one party defects against the other. Our protocol has three messages, which is optimal [Bendlin et al., Asiacrypt’11], and works in a CRS model. We assume subexponential indistinguishability obfuscation (iO) and one way functions.

Implementation-Level Corruptions in Distance Bounding -- Exhibiting Faults and Provably-Secure Fixes in the Electronic Payment Protocol PayPass --

Mon, 12/31/2018 - 08:12
In relay attacks,a man-in-the-middle attacker gains access to a service by relaying the messages between two legitimate parties. Distance-bounding protocols are a countermeasure to relay attacks, whereby a verifier measures the round-trip time in exchanges with a prover. Inspired by application-security definitions, we propose a new security model, OracleDB, distinguishing two prover-corruption types: black-box and white-box. We use this distinction to settle the long-lasting arguments about terrorist-fraud resistance, by showing that it is irrelevant in both the black-box and white-box corruption models. We then exhibit a security flaw in the PayPass protocol with relay protection, used in EMV contactless payments. We propose an extension to this industry-standard protocol, with only small modifications, and prove its security in our strongest adversary model. Finally, we exhibit a new generalised distance-fraud attack strategy that defeats the security claims of at least 12 existing distance-bounding protocols.

Structural Nonlinear Invariant Attacks on T-310: Attacking Arbitrary Boolean Functions

Mon, 12/31/2018 - 08:11
Recent papers show how to construct polynomial invariant attacks for block ciphers, however almost all such results are somewhat weak: invariants are simple and low degree and the Boolean functions tend by very simple if not degenerate. Is there a better more realistic attack, with invariants of higher degree and which is likely to work with stronger Boolean functions? In this paper we show that such attacks exist and can be constructed explicitly through on the one side, the study of Fundamental Equation of eprint/2018/807, and on the other side, a study of the space of Annihilators of any given Boolean function. Our approach is suitable for backdooring a block cipher in presence of an arbitrarily strong Boolean function not chosen by the attacker. The attack is constructed using excessively simple paper and pencil maths.

Universally Composable Accumulators

Mon, 12/31/2018 - 08:09
Accumulators, first introduced by Benaloh and de Mare (Eurocrypt 1993), are compact representations of arbitrarily large sets and can be used to prove claims of membership or non-membership about the underlying set. They are almost exclusively used as building blocks in real-world complex systems, including anonymous credentials, group signatures and, more recently, anonymous cryptocurrencies. Having rigorous security analysis for such systems is crucial for their adoption and safe use in the real world, but it can turn out to be extremely challenging given their complexity. In this work, we provide the first universally composable (UC) treatment of cryptographic accumulators. There are many different types of accumulators: some support additions, some support deletions and some support both; and, orthogonally, some support proofs of membership, some support proofs of non-membership, and some support both. Our UC definition covers all of these types of accumulators concisely in a single functionality, and captures the two basic security properties of accumulators: correctness and soundness. We then prove the equivalence of our UC definition to standard accumulator definitions. This implies that existing popular accumulator schemes, such as the RSA accumulator, already meet our UC definition, and that the security proofs of existing systems that leverage such accumulators can be significantly simplified. Finally, we use our UC definition to get simple proofs of security. We build an accumulator in a modular way out of two weaker accumulators (in the style of Baldimtsi et al. (Euro S&P 2017), and we give a simple proof of its UC security. We also show how to simplify the proofs of security of complex systems such as anonymous credentials using our UC definition.

Proof-of-Stake Sidechains

Mon, 12/31/2018 - 08:05
Sidechains have long been heralded as the key enabler of blockchain scalability and interoperability. However, no modeling of the concept or a provably secure construction has so far been attempted. We provide the first formal definition of what a sidechain system is and how assets can be moved between sidechains securely. We put forth a security definition that augments the known transaction ledger properties of persistence and liveness to hold across multiple ledgers and enhance them with a new ``firewall'' security property which safeguards each blockchain from its sidechains, limiting the impact of an otherwise catastrophic sidechain failure. We then provide a sidechain construction that is suitable for proof-of-stake (PoS) sidechain systems. As an exemplary concrete instantiation we present our construction for an epoch-based PoS system consistent with Ouroboros (Crypto~2017), the PoS blockchain protocol used in Cardano which is one of the largest pure PoS systems by market capitalisation, and we also comment how the construction can be adapted for other protocols such as Ouroboros Praos (Eurocrypt~2018), Ouroboros Genesis (CCS~2018), Snow White and Algorand. An important feature of our construction is {\em merged-staking} that prevents ``goldfinger'' attacks against a sidechain that is only carrying a small amount of stake. An important technique for pegging chains that we use in our construction is cross-chain certification which is facilitated by a novel cryptographic primitive we introduce called ad-hoc threshold multisignatures (ATMS) which may be of independent interest. We show how ATMS can be securely instantiated by regular and aggregate digital signatures as well as succinct arguments of knowledge such as STARKs and bulletproofs with varying degrees of storage efficiency.

Memory-Constrained Implementation of Lattice-based Encryption Scheme on the Standard Java Card Platform

Mon, 12/31/2018 - 08:05
Memory-constrained devices, including widely used smart cards, require resisting attacks by the quantum computers. Lattice-based encryption scheme possesses high efficiency and reliability which could run on small devices with limited storage capacity and computation resources such as IoT sensor nodes or smart cards. We present the first implementation of a lattice-based encryption scheme on the standard Java Card platform by combining number theoretic transform and improved Montgomery modular multiplication. The running time of decryption is nearly optimal (about 7 seconds for 128-bit security level). We also optimize discrete Ziggurat algorithm and Knuth-Yao algorithm to sample from prescribed probability distributions on the Java Card platform. More importantly, we indicate that polynomial multiplication can be performed on Java Card efficiently even if the long integers are not supported, which makes running more lattice-based cryptosystems on smart cards achievable.

Universally Composable Security: A New Paradigm for Cryptographic Protocols

Mon, 12/31/2018 - 00:35
We present a general framework for representing cryptographic protocols and analyzing their security. The framework allows specifying the security requirements of practically any cryptographic task in a unified and systematic way. Furthermore, in this framework the security of protocols is maintained under a general protocol composition operation, called universal composition. The proposed framework with its security-preserving composition property allow for modular design and analysis of complex cryptographic protocols from relatively simple building blocks. Moreover, within this framework, protocols are guaranteed to maintain their security within any context, even in the presence of an unbounded number of arbitrary protocol instances that run concurrently in an adversarially controlled manner. This is a useful guarantee, that allows arguing about the security of cryptographic protocols in complex and unpredictable environments such as modern communication networks.

Sum-of-Squares Meets Program Obfuscation, Revisited

Sun, 12/30/2018 - 23:41
We develop attacks on the security of variants of pseudo-random generators computed by quadratic polynomials. In particular we give a general condition for breaking the one-way property of mappings where every output is a quadratic polynomial (over the reals) of the input. As a corollary, we break the degree-2 candidates for security assumptions recently proposed for constructing indistinguishability obfuscation by Ananth, Jain and Sahai (ePrint 2018) and Agrawal (ePrint 2018). We present conjectures that would imply our attacks extend to a wider variety of instances, and in particular offer experimental evidence that they break assumption of Lin-Matt (ePrint 2018). Our algorithms use semidefinite programming, and in particular, results on low-rank recovery (Recht, Fazel, Parrilo 2007) and matrix completion (Gross 2009).

Fast Secure Comparison for Medium-Sized Integers and Its Application in Binarized Neural Networks

Sun, 12/30/2018 - 23:41
In 1994, Feige, Kilian, and Naor proposed a simple protocol for secure $3$-way comparison of integers $a$ and $b$ from the range $[0,2]$. Their observation is that for $p=7$, the Legendre symbol $(x | p)$ coincides with the sign of $x$ for $x=a-b\in[-2,2]$, thus reducing secure comparison to secure evaluation of the Legendre symbol. More recently, in 2011, Yu generalized this idea to handle secure comparisons for integers from substantially larger ranges $[0,d]$, essentially by searching for primes for which the Legendre symbol coincides with the sign function on $[-d,d]$. In this paper, we present new comparison protocols based on the Legendre symbol that additionally employ some form of error correction. We relax the prime search by requiring that the Legendre symbol encodes the sign function in a noisy fashion only. Practically, we use the majority vote over a window of $2k+1$ adjacent Legendre symbols, for small positive integers $k$. Our technique significantly increases the comparison range: e.g., for a modulus of $60$ bits, $d$ increases by a factor of $2.9$ (for $k=1$) and $5.4$ (for $k=2$) respectively. We give a practical method to find primes with suitable noisy encodings. We demonstrate the practical relevance of our comparison protocol by applying it in a secure neural network classifier for the MNIST dataset. Concretely, we discuss a secure multiparty computation based on the binarized multi-layer perceptron of Hubara et al., using our comparison for the second and third layers.

Setup-Free Secure Search on Encrypted Data: Faster and Post-Processing Free

Sun, 12/30/2018 - 23:41
We present a novel $\textit{secure search}$ protocol on data and queries encrypted with Fully Homomorphic Encryption (FHE). Our protocol enables organizations (client) to (1) securely upload an unsorted data array $x=(x[1],\ldots,x[n])$ to an untrusted honest-but-curious sever, where data may be uploaded over time and from multiple data-sources; and (2) securely issue repeated search queries $q$ for retrieving the first element $(i^*,x[i^*])$ satisfying an agreed matching criterion $i^* = \min\ \left\{ \left.i\in[n] \;\right\vert \mathsf{IsMatch}(x[i],q)=1 \right\}$, as well as fetching the next matching elements with further interaction. For security, the client encrypts the data and queries with FHE prior to uploading, and the server processes the ciphertexts to produce the result ciphertext for the client to decrypt. Our secure search protocol improves over the prior state-of-the-art for secure search on FHE encrypted data (Akavia, Feldman, Shaul (AFS), CCS'2018) in achieving: (1) $\textit{Post-processing free}$ protocol where the server produces a ciphertext for the correct search outcome with overwhelming success probability.This is in contrast to returning a list of candidates for the client to post-process, or suffering from a noticeable error probability, in AFS. Our post-processing freeness enables the server to use secure search as a sub-component in a larger computation without interaction with the client. (2) $\textit{Faster protocol:}$(a) Client time and communication bandwidth are improved by a $\log^2n/\log\log n$ factor. (b) Server evaluates a polynomial of degree linear in $\log n$ (compare to cubic in AFS), and overall number of multiplications improved by up to $\log n$ factor.(c) Employing only $\textrm{GF}(2)$ computations (compare to $\textrm{GF}(p)$ for $p \gg 2$ in AFS) to gain both further speedup and compatibility to all current FHE candidates. (3) $\textit{Order of magnitude speedup exhibited by extensive benchmarks}$ we executed on identical hardware for implementations of ours versus AFS's protocols. Additionally, like other FHE based solutions, out solution is setup-free: to outsource elements from the client to the server, no additional actions are performed on $x$ except for encrypting it element by element (each element bit by bit) and uploading the resulted ciphertexts to the server.

FACCT: FAst, Compact, and Constant-Time Discrete Gaussian Sampler over Integers

Sun, 12/30/2018 - 23:40
The discrete Gaussian sampler is one of the fundamental tools in implementing lattice-based cryptosystems. However, a naive discrete Gaussian sampling implementation suffers from side-channel vulnerabilities, and the existing countermeasures usually introduce significant overhead in either the running speed or the memory consumption. In this paper, we propose a fast, compact, and constant-time implementation of the binary sampling algorithm, originally introduced in the BLISS signature scheme. Our implementation adapts the Renyi divergence and the transcendental function polynomial approximation techniques. The efficiency of our scheme is independent of the standard deviation, and we show evidence that our implementations are either faster or more compact than several existing constant-time samplers. In addition, we show the performance of our implementation techniques applied to and integrated with two existing signature schemes: qTesla, and Falcon. On the other hand, the convolution theorems are typically adapted to sample from larger standard deviations, by combining samples with much smaller standard deviations. As an additional contribution, we show better parameters for the convolution theorems.

Key Assignment Scheme with Authenticated Encryption

Sun, 12/30/2018 - 23:40
The Key Assignment Scheme (KAS) is a well-studied cryptographic primitive used for hierarchical access control (HAC) in a multilevel organisation where the classes of people with higher privileges can access files of those with lower ones. Our first contribution is the formalization of a new cryptographic primitive, namely, KAS-AE that supports the aforementioned HAC solution with an additional authenticated encryption property. Next, we present three efficient KAS-AE schemes that solve the HAC and the associated authenticated encryption problem more efficiently -- both with respect to time and memory -- than the existing solutions that achieve it by executing KAS and AE separately. Our first KAS-AE construction is built by using the cryptographic primitive MLE (EUROCRYPT 2013) as a black box; the other two constructions (which are the most efficient ones) have been derived by cleverly tweaking the hash function FP (Indocrypt 2012) and the authenticated encryption scheme APE (FSE 2014). This high efficiency of our constructions is critically achieved by using two techniques: design of a mechanism for reverse decryption used for reduction of time complexity, and a novel key management scheme for optimizing storage requirements when organizational hierarchy forms an arbitrary access graph (instead of a linear graph). We observe that constructing a highly efficient KAS-AE scheme using primitives other than MLE, FP and APE is a non-trivial task. We leave it as an open problem. Finally, we provide a detailed comparison of all the KAS-AE schemes.

Certificate Transparency Using Blockchain

Sun, 12/30/2018 - 23:34
The security of web communication via the SSL/TLS protocols relies on safe distributions of public keys associated with web domains in the form of $\mathsf{X.509}$ certificates. Certificate authorities (CAs) are trusted third parties that issue these certificates. However, the CA ecosystem is fragile and prone to compromises. Starting with Google's Certificate Transparency project, a number of research works have recently looked at adding transparency for better CA accountability, effectively through public logs of all certificates issued by certification authorities, to augment the current $\mathsf{X.509}$ certificate validation process into SSL/TLS. In this paper, leveraging recent progress in blockchain technology, we propose a novel system, called $\mathsf{CTB} $, that makes it impossible for a CA to issue a certificate for a domain without obtaining consent from the domain owner. We further make progress to equip $\mathsf{CTB}$ with certificate revocation mechanism. We implement $\mathsf{CTB}$ using IBM's Hyperledger Fabric blockchain platform. $\mathsf{CTB}$'s smart contract, written in Go, is provided for complete reference.

Obscuro: A Bitcoin Mixer using Trusted Execution Environments

Sun, 12/30/2018 - 21:24
Bitcoin provides only pseudo-anonymous transactions, which can be exploited to link payers and payees – defeating the goal of anonymous payments. To thwart such attacks, several Bitcoin mixers have been proposed, with the objective of providing unlinkability between payers and payees. However, existing Bitcoin mixers can be regarded as either insecure or inefficient. We present Obscuro, a highly efficient and secure Bitcoin mixer that utilizes trusted execution environments (TEEs). With the TEE’s confidentiality and integrity guarantees for code and data, our mixer design ensures the correct mixing operations and the protection of sensitive data (i.e., private keys and mixing logs), ruling out coin theft and address linking attacks by a malicious service provider. Yet, the TEE-based implementation does not prevent the manipulation of inputs (e.g., deposit submissions, blockchain feeds) to the mixer, hence Obscuro is designed to overcome such limitations: it (1) offers an indirect deposit mechanism to prevent a malicious service provider from rejecting benign user deposits; and (2) scrutinizes blockchain feeds to prevent deposits from being mixed more than once (thus degrading anonymity) while being eclipsed from the main blockchain branch. In addition, Obscuro provides several unique anonymity features (e.g., minimum mixing set size guarantee, resistant to dropping user deposits) that are not available in existing centralized and decentralized mixers. Our prototype of Obscuro is built using Intel SGX and we demonstrate its effectiveness in Bitcoin Testnet. Our implementation mixes 1000 inputs in just 6.49 seconds, which vastly outperforms all of the existing decentralized mixers.


Sun, 12/30/2018 - 13:56
Nowadays, IT enabled service gain more attention due to easy to access resources from remote place. IT enabled services are extend their service to all kind of business and personal related applications like, e-commerce, e-business, e-transactions and e-healthcare etc.,. In India, e-healthcare system gains more attention in recent years due to its effectiveness. We have to consider information assurance is an important part of e-healthcare system, because maintaining of sensitive health records of individuals. Any information system is subject to two different issues, 1) information handling and 2) information assurance. An e-healthcare system has to provide necessary security factors without compromising information loss. Information access is one of the foremost issue for providing access rights to the legal users. In this paper, we have proposed a two factor authentication scheme using Elliptic Curve Cryptography with smart card. The proposed authentication is based on two-factor authentication with smart card and password, which provides high security with minimum computational cost. The proposed scheme generates new session key for every new session with fresh time stamp and nonce value. The proposed scheme needs minimum computation cost compared with the related authentication schemes using smart card


IACR Eprint