Subscribe to IACR Eprint feed
Updated: 10 hours 58 min ago

Efficient Oblivious Data Structures for Database Services on the Cloud

Fri, 12/22/2017 - 23:01
Database-as-a-service (DBaaS) allows the client to store and manage structured data on the cloud remotely. Despite its merits, DBaaS also brings significant privacy issues. Existing encryption techniques (e.g., SQL-aware encryption) can mitigate privacy concerns, but they still leak information through access patterns which are vulnerable to statistical inference attacks. Oblivious Random Access Machine (ORAM) can seal such leakages, but the recent studies showed significant challenges on the integration of ORAM into databases. Specifically, the direct usage of ORAM on databases is not only costly but also permits very limited query functionalities. We propose new oblivious data structures called Oblivious Matrix Structure (OMAT) and Oblivious Tree Structure (OTREE), which allow tree-based ORAM to be integrated into database systems in a more efficient manner with diverse query functionalities supported. OMAT provides special ORAM packaging strategies for table structures, which not only offers a significantly better performance but also enables a broad range of query types that may not be practical in existing frameworks. OTREE allows oblivious conditional queries to be deployed on tree-indexed databases more efficient than existing techniques. We fully implemented our proposed techniques and evaluated their performance on a real cloud database with various metrics, compared with state-of-the-art counterparts.

A High-Security Searchable Encryption Framework for Privacy-Critical Cloud Storage Services

Fri, 12/22/2017 - 23:00
Searchable encryption has received a significant attention from the research community with various constructions being proposed, each achieving asymptotically optimal complexity for specific metrics (e.g., search, update). Despite their elegancy, the recent attacks and deployment efforts have shown that the optimal asymptotic complexity might not always imply practical performance, especially if the application demands a high privacy. Hence, there is a significant need for searchable encryption frameworks that capture the recent attacks with actual deployments on cloud infrastructures to assess the practicality under realistic settings. In this article, we introduce a new Dynamic Searchable Symmetric Encryption (DSSE) framework called Incidence Matrix (IM)-DSSE, which achieves a high level of privacy, efficient search/update, and low client storage with actual deployments on real cloud settings. We harness an incidence matrix along with two hash tables to create an encrypted index, on which both search and update operations can be performed effectively with minimal information leakage. This simple set of data structures surprisingly offers a high level of DSSE security while at the same time achieving practical performance. Specifically, IM-DSSE achieves forward privacy, backward privacy and size-obliviousness properties simultaneously. We also create several DSSE variants, each offering different trade-offs (e.g., security, computation) that are suitable for different cloud applications and infrastructures. Our framework was fully-implemented and its performance was rigorously evaluated on a real cloud system (Amazon EC2). Our experimental results confirm that IM-DSSE is highly practical even when deployed on mobile phones with a large outsourced dataset. Finally, we have released our IM-DSSE framework as an open-source library for a wide development and adaptation.

Fast Quantum Algorithm for Solving Multivariate Quadratic Equations

Fri, 12/22/2017 - 19:11
In August 2015 the cryptographic world was shaken by a sudden and surprising announcement by the US National Security Agency (NSA) concerning plans to transition to post-quantum algorithms. Since this announcement post-quantum cryptography has become a topic of primary interest for several standardization bodies. The transition from the currently deployed public-key algorithms to post-quantum algorithms has been found to be challenging in many aspects. In particular the problem of evaluating the quantum-bit security of such post-quantum cryptosystems remains vastly open. Of course this question is of primarily concern in the process of standardizing the post-quantum cryptosystems. In this paper we consider the quantum security of the problem of solving a system of $m$ Boolean multivariate quadratic equations in $n$ variables (MQ$_2$); a central problem in post-quantum cryptography. When $n=m$, under a natural algebraic assumption, we present a Las-Vegas quantum algorithm solving MQ$_2$ that requires the evaluation of, on average, $O(2^{0.462n})$ quantum gates. To our knowledge this is the fastest algorithm for solving MQ$_2$.

Practical Quantum-Safe Voting from Lattices

Fri, 12/22/2017 - 17:12
We propose a lattice-based electronic voting scheme, EVOLVE (Electronic Voting from Lattices with Verification), which is conjectured to resist attacks by quantum computers. Our protocol involves a number of voting authorities so that vote privacy is maintained as long as at least one of the authorities is honest, while the integrity of the result is guaranteed even when all authorities collude. Furthermore, the result of the vote can be independently computed by any observer. At the core of the protocol is the utilization of a homomorphic commitment scheme with strategically orchestrated zero-knowledge proofs: voters use approximate but efficient “Fiat-Shamir with Aborts” proofs to show the validity of their vote, while the authorities use amortized exact proofs to show that the commitments are well-formed. We also present a novel efficient zero-knowledge proof that one of two lattice-based statements is true (so-called OR proof) and a new mechanism to control the size of the randomness when applying the homomorphism to commitments. We give concrete parameter choices to securely instantiate and evaluate the efficiency of our scheme. Our prototype implementation shows that the voters require 8 milliseconds to submit a vote of size about 20KB to each authority and it takes each authority 0.15 seconds per voter to create a proof that his vote was valid. The size of the vote share that each authority produces is approximately 15KB per voter, which we believe is well within the practical bounds for a large-scale election.

High-Precision Privacy-Preserving Real-Valued Function Evaluation

Fri, 12/22/2017 - 17:04
We propose a novel multi-party computation protocol for evaluating continuous real-valued functions with high numerical precision. Our method is based on approximations with Fourier series and uses at most two rounds of communication during the online phase. For the offline phase, we propose a trusted-dealer and honest-but-curious aided solution, respectively. We apply our algorithm to train a logistic regression classifier via a variant of Newton's method (known as IRLS) to compute unbalanced classification problems that detect rare events and cannot be solved using previously proposed privacy-preserving optimization algorithms (e.g., based on piecewise-linear approximations of the sigmoid function). Our protocol is efficient as it can be implemented using standard quadruple-precision floating point arithmetic. We report multiple experiments and provide a demo application that implements our algorithm for training a logistic regression model.

Provably secure compilation of side-channel countermeasures

Fri, 12/22/2017 - 17:03
Software-based countermeasures provide effective mitigation against side-channel attacks, often with minimal efficiency and deployment overheads. Their effectiveness is often amenable to rigorous analysis: specifically, several popular countermeasures can be formalized as information flow policies, and correct implementation of the countermeasures can be verified with state-of-the-art analysis and verification techniques. However, in absence of further justification, the guarantees only hold for the language (source, target, or intermediate representation) on which the analysis is performed. We consider the problem of preserving side-channel countermeasures by compilation, and present a general method for proving that compilation preserves software-based side-channel countermeasures. The crux of our method is the notion of 2-simulation, which adapts to our setting the notion of simulation from compiler verification. Using the Coq proof assistant, we verify the correctness of our method and of several representative instantiations.

Speed-ups and time-memory trade-offs for tuple lattice sieving

Fri, 12/22/2017 - 16:45
In this work we study speed-ups and time-space trade-offs for solving the shortest vector problem (SVP) on Euclidean lattices based on tuple lattice sieving. Our results extend and improve upon previous work of Bai-Laarhoven-Stehl{\'e} [ANTS'16] and Herold-Kirshanova [PKC'17], with better complexities for arbitrary tuple sizes and offering tunable time-memory trade-offs.The trade-offs we obtain stem from the generalization and combination of two algorithmic techniques: the configuration framework introduced by Herold-Kirshanova, and the spherical locality-sensitive filters of Becker-Ducas-Gama-Laarhoven [SODA'16]. When the available memory scales quasi-linearly with the list size, we show that with triple sieving we can solve SVP in dimension $n$ in time $2^{0.3588n + o(n)}$ and space $2^{0.1887n + o(n)}$, improving upon the previous best triple sieve time complexity of $2^{0.3717n + o(n)}$ of Herold-Kirshanova. Using more memory we obtain better asymptotic time complexities. For instance, we obtain a triple sieve requiring only $2^{0.3300n + o(n)}$ time and $2^{0.2075n + o(n)}$ memory to solve SVP in dimension $n$. This improves upon the best double Gauss sieve of Becker-Ducas-Gama-Laarhoven, which runs in $2^{0.3685n + o(n)}$ time when using the same amount of space.

Optimal Linear Secret Sharing Schemes for Graph Access Structures on Six Participants

Fri, 12/22/2017 - 16:23
We review the problem of finding the optimal information ratios of graph access structures on six participants. Study of such access structures were initiated by van Dijk [Des. Codes Cryptogr. 15 (1998), 301-321].Through a sequence of follow up works, exact values of optimal information ratios of nine access structures, out of 18 initially unsolved non-isomorphic ones, were determined. Very recently [O. Farras et al. Cryptology ePrint Archive: Report 2017/919], for each of the remained such cases, the known lower bound on the optimal information ratio of linear secret sharing schemes was improved, establishing the optimal information ratio of linear secret sharing schemes for two of them. Here, for each of the other seven cases, we provide a new upper bound on the optimal information ratio of linear secret sharing schemes; our improved upper bounds match the corresponding recently presented lower bounds. Improved upper bounds are achieved using decomposition techniques. As an additional contribution, we present a new decomposition technique, called $(\lambda,\omega)$-weighted decomposition, which is a generalization of all known decomposition techniques.

Integer Reconstruction Public-Key Encryption

Fri, 12/22/2017 - 16:20
In [AJPS17], Aggarwal, Joux, Prakash & Santha described an elegant public-key cryptosystem (AJPS-1) mimicking NTRU over the integers. This algorithm relies on the properties of Mersenne primes instead of polynomial rings. A later ePrint [BCGN17] by Beunardeau et al. revised AJPS-1’s initial security estimates. While lower than initially thought, the best known attack on AJPS-1 still seems to leave the defender with an exponential advantage over the attacker [dBDJdW17]. However, this lower exponential advantage implies enlarging AJPS-1’s parameters. This, plus the fact that AJPS-1 encodes only a single plaintext bit per ciphertext, made AJPS-1 impractical. In a recent update, Aggarwal et al. overcame this limitation by extending AJPS-1’s bandwidth. This variant (AJPS-ECC) modifies the definition of the public-key and relies on error-correcting codes. This paper presents a different high-bandwidth construction. By opposition to AJPS-ECC, we do not modify the public-key, avoid using errorcorrecting codes and use backtracking to decrypt. The new algorithm is orthogonal to AJPS-ECC as both mechanisms may be concurrently used in the same ciphertext and cumulate their bandwidth improvement effects. Alternatively, we can increase AJPS-ECC’s information rate by a factor of 26 for the parameters recommended in [AJPS17]. The obtained bandwidth improvement and the fact that encryption and decryption are reasonably efficient, make our scheme an interesting postquantum candidate.

Overdrive: Making SPDZ Great Again

Fri, 12/22/2017 - 16:20
SPDZ denotes a multiparty computation scheme in the preprocessing model based on somewhat homomorphic encryption (SHE) in the form of BGV. At CCS '16, Keller et al. presented MASCOT, a replacement of the preprocessing phase using oblivious transfer instead of SHE, improving by two orders of magnitude on the SPDZ implementation by Damgård et al. (ESORICS '13). In this work, we show that using SHE is faster than MASCOT in many aspects: - We present a protocol that uses semi-homomorphic (addition-only) encryption. For two parties, our BGV-based implementation is 6 times faster than MASCOT on a LAN and 20 times faster in a WAN setting. The latter is roughly the reduction in communication. - We show that using the proof of knowledge in the original work by Damgård et al. (Crypto '12) is more efficient in practice than the one used in the implementation mentioned above by about one order of magnitude. - We present an improvement to the verification of the aforementioned proof of knowledge that increases the performance with a growing number of parties, doubling it for 16 parties.

Quantum Meet-in-the-Middle Attacks: Applications to Generic Feistel Constructions

Fri, 12/22/2017 - 16:19
This paper shows that quantum computers can significantly speed-up a type of meet-in-the-middle attacks initiated by Demiric and Sel\c{c}uk (DS-MITM attacks), which is currently one of the most powerful cryptanalytic approaches in the classical setting against symmetric-key schemes. The quantum DS-MITM attacks are then demonstrated against 6 rounds of the generic Feistel construction supporting an $n$-bit key and an $n$-bit block, which was attacked by Guo et al.~in the classical setting with data, time, and memory complexities of $O(2^{3n/4})$. The complexities of our quantum attacks depend on the adversary's model and the number of qubits available to the adversary. When the adversary has an access to quantum computers for performing offline computations but online queries are made in a classical manner (so called Q1 model), the attack complexities are $O(2^{n/2})$ classical queries, $O(2^n/q)$ quantum computations by using about $q$ qubits. Those are balanced at $\tilde{O}(2^{n/2})$, which significantly improves the classical attack. Technically, we convert the quantum claw finding algorithm to be suitable in the Q1 model, and apply it to reduce the cost of finding a match in the MITM stage. The attack is then extended to the case that the adversary is further allowed to make superposition queries (so called Q2 model). The attack approach is drastically changed from one in the Q1 model; the attack is based on 3-round distinguishers with Simon's algorithm and then appends 3 rounds for key recovery. This can be solved by applying the combination of Simon's and Grover's algorithms recently proposed by Leander and May.

VerMI: Verification Tool for Masked Implementations

Fri, 12/22/2017 - 16:16
Masking is a widely used countermeasure against Side-Channel Attacks (SCA), but the implementation of these countermeasures is challenging. Experimental security evaluation requires special equipment, a considerable amount of time and extensive technical knowledge. So, to automate and to speed up this process, a formal verification can be performed to asses the security of a design. Multiple theoretical approaches and verification tools have been proposed in the literature. The majority of them are tailored for software implementations, not applicable to hardware since they do not take into account glitches. Existing hardware verification tools are limited either to combinational logic or to small designs due to the computational resources needed. In this work we present VerMI, a verification tool in the form of a logic simulator that checks the properties defined in Threshold Implementations to address the security of a hardware implementation for meaningful orders of security. The tool is designed so that any masking scheme can be evaluated. It accepts combinational and sequential logic and is able to analyze an entire cipher in short time. With the tool we have managed to spot a flaw in the round-based Keccak implementation by Gross et al., published in DSD 2017.

New (and Old) Proof Systems for Lattice Problems

Fri, 12/22/2017 - 16:08
We continue the study of statistical zero-knowledge (SZK) proofs, both interactive and noninteractive, for computational problems on point lattices. We are particularly interested in the problem GapSPP of approximating the $\varepsilon$-smoothing parameter (for some $\varepsilon < 1/2$) of an $n$-dimensional lattice. The smoothing parameter is a key quantity in the study of lattices, and GapSPP has been emerging as a core problem in lattice-based cryptography, e.g., in worst-case to average-case reductions. We show that GapSPP admits SZK proofs for *remarkably low* approximation factors, improving on prior work by up to roughly $\sqrt{n}$. Specifically: -- There is a *noninteractive* SZK proof for $O(\log(n) \sqrt{\log (1/\varepsilon)})$-approximate GapSPP. Moreover, for any negligible $\varepsilon$ and a larger approximation factor $\tilde{O}(\sqrt{n \log(1/\varepsilon)})$, there is such a proof with an *efficient prover*. -- There is an (interactive) SZK proof with an efficient prover for $O(\log n + \sqrt{\log(1/\varepsilon)/\log n})$-approximate coGapSPP. We show this by proving that $O(\log n)$-approximate GapSPP is in coNP. In addition, we give an (interactive) SZK proof with an efficient prover for approximating the lattice *covering radius* to within an $O(\sqrt{n})$ factor, improving upon the prior best factor of $\omega(\sqrt{n \log n})$.

Fast Garbling of Circuits over 3-Valued Logic

Fri, 12/22/2017 - 16:07
In the setting of secure computation, a set of parties wish to compute a joint function of their private inputs without revealing anything but the output. Garbled circuits, first introduced by Yao, are a central tool in the construction of protocols for secure computation (and other tasks like secure outsourced computation), and are the fastest known method for constant-round protocols. In this paper, we initiate a study of garbling multivalent-logic circuits, which are circuits whose wires may carry values from some finite/infinite set of values (rather than only True and False). In particular, we focus on the three-valued logic system of Kleene, in which the admissible values are True, False, and Unknown. This logic system is used in practice in SQL where some of the values may be missing. Thus, efficient constant-round secure computation of SQL over a distributed database requires the ability to efficiently garble circuits over 3-valued logic. However, as we show, the two natural (naive) methods of garbling 3-valued logic are very expensive. In this paper, we present a general approach for garbling three-valued logic, which is based on first encoding the 3-value logic into Boolean logic, then using standard garbling techniques, and final decoding back into 3-value logic. Interestingly, we find that the specific encoding chosen can have a significant impact on efficiency. Accordingly, the aim is to find Boolean encodings of 3-value logic that enable efficient Boolean garbling (i.e., minimize the number of AND gates). We also show that Boolean AND gates can be garbled at the same cost of garbling XOR gates in the 3-value logic setting. Thus, it is unlikely that an analogue of free-XOR exists for 3-value logic garbling (since this would imply free-AND in the Boolean setting).

Practical Cryptanalysis of a Public-key Encryption Scheme Based on Non-linear Indeterminate Equations at SAC 2017

Fri, 12/22/2017 - 16:06
Abstract. We investigate the security of a public-key encryption scheme, the Indeterminate Equation Cryptosystem (IEC), introduced by Akiyama, Goto, Okumura, Takagi, Nuida, and Hanaoka at SAC 2017 as postquantum cryptography. They gave two parameter sets (n,p, deg X) = (80,3,1) and (80,3,2). This paper gives practical key-recovery and message-recovery attacks against those parameter sets of IEC through lattice basis-reduction algorithm. We exploit the fact that $n = 80$ is composite and adopt the idea of Gentry’s attack against NTRU-Composite (EUROCRYPT2001) to this setting. The summary of our attacks follows: * for (n,p,deg X) = (80,3,1); we recover 84 private keys from 100 public keys in 30--40 seconds per key. * for (n,p,deg X) = (80,3,1); we recover partial information of all message from 100 ciphertexts in a second per ciphertext. * for (n,p,deg X) = (80,3,2); we recover partial information of all message from 100 ciphertexts in 30 seconds per ciphertext. Moreover, we also give message-recovery and distinguishing attacks against the parameter sets with prime n, say, n = 83. We exploit another subring to reduce the dimension of lattices in our lattice-based attacks and our attack succeed in the case of deg X = 2. * for (n,p,deg X) = (83,3,2), we recover 7 messages from 10 random ciphertexts within 61,000 seconds \approx 17 hours per ciphertext. * Even for larger n, we can find short vector from lattices to break the underlying assumption of IEC. In our experiment, we can found such vector within 330,000 seconds \approx 4 days for n = 113.

Generic Low-Latency Masking

Fri, 12/22/2017 - 15:47
In this work, we introduce a generalized concept for low-latency masking that is applicable to any implementation and protection order, and (in its extremest form) does not require on-the-fly randomness. The main idea of our approach is to avoid collisions of shared variables in nonlinear circuit parts, and to skip the share compression step. We show the feasibility of our approach on a full implementation of a one round unrolled Ascon variant and an AES S-box case study. We then discuss possible trade-offs to make our approach interesting for practical implementations. As a result we obtain a first-order masked AES S-box that is calculated in a single clock cycle with rather high implementation costs (17.8 kGE), and a two cycle variant requiring only 6.7 kGE. The side-channel resistance of our Ascon S-box designs up to order three are then verified using the formal analysis tool of [6]. Furthermore, we introduce a taint checking based verification approach that works specifically for our low-latency approach and allows faster verification which enables us to verify larger circuits like our low-latency AES S-box design.

Forward-Private Dynamic Searchable Symmetric Encryption with Efficient Search

Fri, 12/22/2017 - 15:43
Dynamic Searchable Symmetric Encryption (DSSE) allows to delegate keyword search and file update over an encrypted database via encrypted indexes, and therefore provides opportunities to mitigate the data privacy and utilization dilemma in cloud storage platforms. Despite its merits, recent works have shown that efficient DSSE schemes are vulnerable to statistical attacks due to the lack of forward-privacy, whereas forward-private DSSE schemes suffer from practicality concerns as a result of their extreme computation overhead. Due to significant practical impacts of statistical attacks, there is a critical need for new DSSE schemes that can achieve the forward-privacy in a more practical and efficient manner. We propose a new DSSE scheme that we refer to as Forward-private Sublinear DSSE (FS-DSSE). FS-DSSE harnesses special secure update strategies and a novel caching strategy to reduce the computation cost of repeated queries. Therefore, it achieves forward-privacy, sublinear search complexity, low end-to-end delay, and parallelization capability simultaneously. We fully implemented our proposed method and evaluated its performance on a real cloud platform. Our experimental evaluation results showed that the proposed scheme is highly secure and highly efficient compared with state-of-the-art DSSE techniques. Specifically, FS-DSSE is one to three magnitude of times faster than forward-secure DSSE counterparts.

Weak-Unforgeable Tags for Secure Supply Chain Management

Fri, 12/22/2017 - 15:42
Given the value of imported counterfeit and pirated goods, the need for secure supply chain management is pertinent. Maleki et al. (HOST 2017) propose a new management scheme based on RFID tags (with 2-3K bits NVM) which, if compared to other schemes, is competitive on several performance and security metrics. Its main idea is to have each RFID tag stores its reader events in its own NVM while moving through the supply chain. In order to bind a tag's identity to each event such that an adversary is not able to impersonate the tag's identity on another duplicate tag, a function with a weak form of unforgeability is needed. In this paper, we formally de ne this security property, present three constructions (MULTIPLY-ADD, ADD-XOR, and S-Box-CBC) having this security property, and show how to bound the probability of successful impersonation in concrete parameter settings. Finally, we compare our constructions with the light-weight hash function PHOTON used by Maleki et al. in terms of security and circuit area needed. We conclude that our ADD-XOR and S-Box-CBC constructions have approximately 1/4 - 1/3 of PHOTON's total circuit area (this also includes the control circuitry besides PHOTON) while maintaining an appropriate security level which takes care of economically motivated adversaries.

Off-line Digital Cash Schemes Providing Unlinkability, Anonymity and Change

Fri, 12/22/2017 - 15:38
Several ecash systems have been proposed in the last twenty years or so,each offering features similar to real cash. One feature which to date has not been provided is that of a payee giving change to a payer for an e-coin in an off-line setting. In this paper, we indicate how an off-line ecash system can solve the change-giving problem. In addition, our protocol offers the usual expected features of anonymity and unlinkability of the payer, but can reveal the identity of an individual who illegally tries to spend ecash twice.

Correlations Between (Nonlinear) Combiners of Input and Output of Random Functions and Permutations

Fri, 12/22/2017 - 15:37
Daeman and Rijmen had derived the distributions of correlations between linear combinations of the input and output of uniform random functions and uniform random permutations. We generalise their results by deriving the distributions of correlations between arbitrary combinations of the input and the output of uniform random functions and uniform random permutations.

Pages

IACR Eprint