Elliptic Curve Cryptography from ACM, 2014, Part 2

	Elliptic Curve Cryptography ACM (2014) Part 2

In Issue Number 4 of the 2015 Newsletter, the editors offered publications of interest about Elliptic Curve Cryptography from IEEE sources in five parts.  This bibliography adds research work published by the Association for Computing Machinery (ACM) in 2014.

Tim Pruss, Priyank Kalla, Florian Enescu; Equivalence Verification of Large Galois Field Arithmetic Circuits using Word-Level Abstraction via Gröbner Bases; DAC '14 Proceedings of the 51st Annual Design Automation Conference, June 2014, Pages 1-6. Doi: 10.1145/2593069.2593134 Abstract: Custom arithmetic circuits designed over Galois fields F2k are prevalent in cryptography, where the field size k is very large (e.g. k = 571-bits). Equivalence checking of such large custom arithmetic circuits against baseline golden models is beyond the capabilities of contemporary techniques. This paper addresses the problem by deriving word-level canonical polynomial representations from gate-level circuits as Z = F (A) over F2k, where Z and A represent the output and input bit-vectors of the circuit, respectively. Using algebraic geometry, we show that the canonical polynomial abstraction can be derived by computing a Gröbner basis of a set of polynomials extracted from the circuit, using a specific elimination (abstraction) term order. By efficiently applying these concepts, we can derive the canonical abstraction in hierarchically designed, custom arithmetic circuits with up to 571-bit datapath, whereas contemporary techniques can verify only up to 163-bit circuits.
Keywords: Gröbner Bases, Hardware Verification, Word-Level Abstraction (ID#: 15-4524)
URL: http://doi.acm.org/10.1145/2593069.2593134

Lindsey N. Whitehurst, Todd R. Andel, J. Todd McDonald; Exploring Security in ZigBee Networks; CISR '14 Proceedings of the 9th Annual Cyber and Information Security Research Conference , April 2014, Pages 25-28. Doi: 10.1145/2602087.2602090 Abstract: ZigBee networks have become popular for their low cost, low power, and ease of implementation. The ZigBee protocol has particularly become prevalent for home automation and controlling devices such as door locks and garage door openers. Preventing attacks and reducing vulnerabilities is imperative in cases where there can be high financial losses due to poor security implementations. For systems where low power and cost are desirable, but security is a priority, the application developer must be extremely cautious in the design of their network. This paper surveys security issues and vulnerabilities in the ZigBee specification and current key management schemes proposed for these networks.
Keywords: 802.15.4, ZigBee, security, smart grid, wireless networks (ID#: 15-4525)
URL: http://doi.acm.org/10.1145/2602087.2602090

Julian Horsch, Konstantin Böttinger, Michael Weiß, Sascha Wessel, Frederic Stumpf; TrustID: Trustworthy Identities for Untrusted Mobile Devices; CODASPY '14 Proceedings of the 4th ACM Conference On Data And Application Security And Privacy, March 2014, Pages 281-288. Doi:  10.1145/2557547.2557593 Abstract: Identity theft has deep impacts in today's mobile ubiquitous environments. At the same time, digital identities are usually still protected by simple passwords or other insufficient security mechanisms. In this paper, we present the TrustID architecture and protocols to improve this situation. Our architecture utilizes a Secure Element (SE) to store multiple context-specific identities securely in a mobile device, e.g., a smartphone. We introduce protocols for securely deriving identities from a strong root identity into the SE inside the smartphone as well as for using the newly derived IDs. Both protocols do not require a trustworthy smartphone operating system or a Trusted Execution Environment. In order to achieve this, our concept includes a secure combined PIN entry mechanism for user authentication, which prevents attacks even on a malicious device. To show the feasibility of our approach, we implemented a prototype running on a Samsung Galaxy SIII smartphone utilizing a microSD card SE. The German identity card nPA is used as root identity to derive context-specific identities.
Keywords: android, combined pin entry, identity derivation, identity provider, mobile security, npa, secure element, smartphone (ID#: 15-4526)
URL: http://doi.acm.org/10.1145/2557547.2557593

Amir Herzberg, Haya Shulman, Bruno Crispo; Less is More: Cipher-Suite Negotiation for DNSSEC; ACSAC '14 Proceedings of the 30th Annual Computer Security Applications Conference, December 2014, Pages 346-355. Doi: 10.1145/2664243.2664283 Abstract: We propose a transport layer cipher-suite negotiation mechanism for DNSSEC standard, allowing name-servers to send responses containing only the keys and signatures that correspond to the cipher-suite option negotiated with the resolver, rather than sending all the signatures and keys (as is done currently).  As we show, a lack of cipher-suite negotiation, is one of the factors impeding deployment of DNSSEC, and also results in adoption of weak ciphers. Indeed, the vast majority of domains rely on RSA 1024-bit cryptography, which is already considered insecure. Furthermore, domains, that want better security, have to support a number of cryptographic ciphers. As a result, the DNSSEC responses are large and often fragmented, harming the DNS functionality, and causing inefficiency and vulnerabilities.  A cipher-suite negotiation mechanism reduces responses' sizes, and hence solves the interoperability problems with DNSSEC-signed responses, and prevents reflection and cache poisoning attacks.
Keywords: DNS interoperability, DNS security, DNSSEC, cipher suite negotiation (ID#: 15-4527)
URL:  http://doi.acm.org/10.1145/2664243.2664283

Raphael Spreitzer, Jörn-Marc Schmidt; Group-Signature Schemes on Constrained Devices: The Gap Between Theory and Practice; CS2 '14 Proceedings of the First Workshop on Cryptography and Security in Computing Systems, January 2014, Pages 31-36. Doi: 10.1145/2556315.2556321 Abstract: Group-signature schemes allow members within a predefined group to prove specific properties without revealing more information than necessary. Potential areas of application include electronic IDs (eIDs) and smartcards, i.e., resource-constrained environments. Though literature provides many theoretical proposals for group-signature schemes, practical evaluations regarding the applicability of such mechanisms in resource-constrained environments are missing. In this work, we investigate four different group-signature schemes in terms of mathematical operations, signature length, and the proposed revocation mechanisms. We also use the RELIC toolkit to implement the two most promising of the investigated group-signature schemes—one of which is going to be standardized in ISO/IEC 20008—for the AVR microcontroller. This allows us to give practical insights into the applicability of pairings on the AVR microcontroller in general and the applicability of group-signature schemes in particular on the very same. Contrary to the general recommendation of precomputing and storing pairing evaluations if possible, we observed that the evaluation of pairings might be faster than computations on cached pairings.
Keywords: ATmega128, AVR, group-signature schemes, pairing-based cryptography, type 1 pairings, type 3 pairings (ID#: 15-4528)
URL: http://doi.acm.org/10.1145/2556315.2556321

Lakshmi Kuppusamy, Jothi Rangasamy, Praveen Gauravaram; On Secure Outsourcing of Cryptographic Computations to Cloud; SCC '14 Proceedings of the 2nd International Workshop on Security in Cloud Computing, June 2014, Pages 63-68. Doi: 10.1145/2600075.2600085 Abstract: For the past few years, research works on the topic of secure outsourcing of cryptographic computations has drawn significant attention from academics in security and cryptology disciplines as well as information security practitioners. One main reason for this interest is their application for resource constrained devices such as RFID tags. While there has been significant progress in this domain since Hohenberger and Lysyanskaya have provided formal security notions for secure computation delegation, there are some interesting challenges that need to be solved that can be useful towards a wider deployment of cryptographic protocols that enable secure outsourcing of cryptographic computations. This position paper brings out these challenging problems with RFID technology as the use case together with our ideas, where applicable, that can provide a direction towards solving the problems.
Keywords: cryptography, public-key protocols, secrecy (ID#: 15-4529)
URL: http://doi.acm.org/10.1145/2600075.2600085

Kim Ramchen, Brent Waters; Fully Secure and Fast Signing from Obfuscation; CCS '14 Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, November 2014, Pages 659-673. Doi: 10.1145/2660267.2660306 Abstract: In this work we explore new techniques for building short signatures from obfuscation. Our goals are twofold. First, we would like to achieve short signatures with adaptive security proofs. Second, we would like to build signatures with fast signing, ideally significantly faster than comparable signatures that are not based on obfuscation. The goal here is to create an "imbalanced'' scheme where signing is fast at the expense of slower verification.  We develop new methods for achieving short and fully secure obfuscation-derived signatures. Our base signature scheme is built from punctured programming and makes a novel use of the "prefix technique" to guess a signature. We find that our initial scheme has slower performance than comparable algorithms (e.g. EC-DSA). We find that the underlying reason is that the underlying PRG is called ~l2 times for security parameter l. To address this issue we construct a more efficient scheme by adapting the Goldreich-Goldwasser-Micali [16] construction to form the basis for a new puncturable PRF. This puncturable PRF accepts variable-length inputs and has the property that evaluations on all prefixes of a message can be efficiently pipelined. Calls to the puncturable PRF by the signing algorithm therefore make fewer invocations of the underlying PRG, resulting in reduced signing costs.  We evaluate our puncturable PRF based signature schemes using a variety of cryptographic candidates for the underlying PRG. We show that the resulting performance on message signing is competitive with that of widely deployed signature schemes. 
Keywords: adaptive security, digital signature scheme, obfuscation, punctured programming (ID#: 15-4530)
URL: http://doi.acm.org/10.1145/2660267.2660306

Melissa Chase, Sarah Meiklejohn, Greg Zaverucha; Algebraic MACs and Keyed-Verification Anonymous Credentials; CCS '14 Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, November 2014, pages 1205-1216. Doi: 10.1145/2660267.2660328 Abstract: We consider the problem of constructing anonymous credentials for use in a setting where the issuer of credentials is also the verifier, or more generally where the issuer and verifier have a shared key. In this setting we can use message authentication codes (MACs) instead of public key signatures as the basis for the credential system.  To this end, we construct two algebraic MACs in prime-order groups, along with efficient protocols for issuing credentials, asserting possession of a credential, and proving statements about hidden attributes (e.g., the age of the credential owner). We prove the security of the first scheme in the generic group model, and prove the security of the second scheme\dash using a dual-system-based approach\dash under decisional Diffie-Hellman (DDH). Our MACs are of independent interest, as they are the only uf-cmva-secure MACs with efficient proofs of knowledge.  Finally, we compare the efficiency of our new systems to two existing constructions of anonymous credentials: U-Prove and Idemix. We show that the performance of the new schemes is competitive with U-Prove (which does not have multi-show unlinkability), and many times faster than Idemix.
Keywords: anonymity, anonymous credentials, mac (ID#: 15-4531)
URL:  http://doi.acm.org/10.1145/2660267.2660328

Gabriel Ghinita, Razvan Rughinis; An Efficient Privacy-Preserving System for Monitoring Mobile Users: Making Searchable Encryption Practical; CODASPY '14 Proceedings of the 4th ACM Conference on Data and Application Security and Privacy, March 2014, Pages 321-332. Doi: 10.1145/2557547.2557559 Abstract: Monitoring location updates from mobile users has important applications in several areas, ranging from public safety and national security to social networks and advertising. However, sensitive information can be derived from movement patterns, so protecting the privacy of mobile users is a major concern. Users may only be willing to disclose their locations when some condition is met, for instance in proximity of a disaster area, or when an event of interest occurs nearby. Currently, such functionality is achieved using searchable encryption. Such cryptographic primitives provide provable guarantees for privacy, and allow decryption only when the location satisfies some predicate. Nevertheless, they rely on expensive pairing-based cryptography (PBC), and direct application to the domain of location updates leads to impractical solutions.  We propose secure and efficient techniques for private processing of location updates that complement the use of PBC and lead to significant gains in performance by reducing the amount of required pairing operations. We also implement two optimizations that further improve performance: materialization of results to expensive mathematical operations, and parallelization. Extensive experimental results show that the proposed techniques significantly improve performance compared to the baseline, and reduce the searchable encryption overhead to a level that is practical in a computing environment with reasonable resources, such as the cloud.
Keywords: location privacy, pairing-based cryptography (ID#: 15-4532)
URL: http://doi.acm.org/10.1145/2557547.2557559

Rong Jin, Xianru Du, Zi Deng, Kai Zeng, Jing Xu; Practical Secret Key Agreement for Full-Duplex Near Field Communications; ASIA CCS '14 Proceedings of the 9th ACM Symposium On Information, Computer And Communications Security, June 2014, Pages 217-228.  Doi:  10.1145/2590296.2590327 Abstract: Near Field Communication (NFC) is a promising short distance radio communication technology for many useful applications. Although its communication range is short, NFC alone does not guarantee secure communication and is subject to security attacks, such as eavesdropping attack. Generating a shared key and using symmetric key cryptography to secure the communication between NFC devices is a feasible solution to prevent various attacks. However, conventional Diffie-Hellman key agreement protocol is not preferable for resource constrained NFC devices due to its extensive computational overhead and energy consumption. In this paper, we propose a practical, fast and energy-efficient key agreement scheme, called RIWA (Random bIts transmission with Waveform shAking), for NFC devices by exploiting its full-duplex capability. In RIWA, two devices send random bits to each other simultaneously without strict synchronization or perfect match of amplitude and phase. On the contrary, RIWA randomly introduces synchronization offset and mismatch of amplitude and phase for each bit transmission in order to prevent a passive attacker from determining the generated key. A shared bit can be established when two devices send different bits. We conduct theoretical analysis on the correctness and security strength of RIWA, and extensive simulations to evaluate its effectiveness. We build a testbed based on USRP software defined radio and conduct proof-of-concept experiments to evaluate RIWA in a real-world environment. It shows that RIWA achieves a high key generation rate about 26kbps and is immune to eavesdropping attack even when the attacker is within several centimeters away from the legitimate devices. RIWA is a practical, fast, energy-efficient, and secure key agreement scheme for resource-constrained NFC devices.
Keywords: USRP, energy efficient, near field communication, practical key agreement (ID#: 15-4533)
URL: http://doi.acm.org/10.1145/2590296.2590327

Benoît Libert, Marc Joye, Moti Yung; Born and Raised Distributively: Fully Distributed Non-Interactive Adaptively-Secure Threshold Signatures with Short Shares;  PODC '14 Proceedings of the 2014 ACM Symposium On Principles Of Distributed Computing, July 2014, Pages 303-312. Doi: 10.1145/2611462.2611498 Abstract: Threshold cryptography is a fundamental distributed computational paradigm for enhancing the availability and the security of cryptographic public-key schemes. It does it by dividing private keys into n shares handed out to distinct servers. In threshold signature schemes, a set of at least t+1 ≤ n servers is needed to produce a valid digital signature. Availability is assured by the fact that any subset of t+1 servers can produce a signature when authorized. At the same time, the scheme should remain robust (in the fault tolerance sense) and unforgeable (cryptographically) against up to t corrupted servers; i.e., it adds quorum control to traditional cryptographic services and introduces redundancy. Originally, most practical threshold signatures have a number of demerits: They have been analyzed in a static corruption model (where the set of corrupted servers is fixed at the very beginning of the attack), they require interaction, they assume a trusted dealer in the key generation phase (so that the system is not fully distributed), or they suffer from certain overheads in terms of storage (large share sizes). In this paper, we construct practical fully distributed (the private key is born distributed), non-interactive schemes---where the servers can compute their partial signatures without communication with other servers---with adaptive security (i.e., the adversary corrupts servers dynamically based on its full view of the history of the system). Our schemes are very efficient in terms of computation, communication, and scalable storage (with private key shares of size O(1), where certain solutions incur O(n) storage costs at each server). Unlike other adaptively secure schemes, our schemes are erasure-free (reliable erasure is a hard to assure and hard to administer property in actual systems).  To the best of our knowledge, such a fully distributed highly constrained scheme has been an open problem in the area. In particular, and of special interest, is the fact that Pedersen's traditional distributed key generation (DKG) protocol can be safely employed in the initial key generation phase when the system is born -- although it is well-known not to ensure uniformly distributed public keys. An advantage of this is that this protocol only takes one round optimistically (in the absence of faulty player).
Keywords: adaptive security, availability, distributed key generation, efficiency, erasure-free schemes, fault tolerance, fully distributed systems, non-interactivity, threshold signature schemes (ID#: 15-4534)
URL: http://doi.acm.org/10.1145/2611462.2611498

Tobias Oder, Thomas Pöppelmann, Tim Güneysu; Beyond ECDSA and RSA: Lattice-based Digital Signatures on Constrained Devices; DAC '14 Proceedings of the 51st Annual Design Automation Conference; June 2014, Pages 1-6. Doi: 10.1145/2593069.2593098 Abstract: All currently deployed asymmetric cryptography is broken with the advent of powerful quantum computers. We thus have to consider alternative solutions for systems with long-term security requirements (e.g., for long-lasting vehicular and avionic communication infrastructures). In this work we present an efficient implementation of BLISS, a recently proposed, post-quantum secure, and formally analyzed novel lattice-based signature scheme. We show that we can achieve a significant performance of 35.3 and 6 ms for signing and verification, respectively, at a 128-bit security level on an ARM Cortex-M4F microcontroller. This shows that lattice-based cryptography can be efficiently deployed on today's hardware and provides security solutions for many use cases that can even withstand future threats.
Keywords: (not provided) (ID#: 15-4535)
URL:  http://doi.acm.org/10.1145/2593069.2593098

Florian Bergsma, Benjamin Dowling, Florian Kohlar, Jörg Schwenk, Douglas Stebila; Multi-Ciphersuite Security of the Secure Shell (SSH) Protocol; CCS '14 Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, November 2014, Pages 369-381. Doi: 10.1145/2660267.2660286 Abstract: The Secure Shell (SSH) protocol is widely used to provide secure remote access to servers, making it among the most important security protocols on the Internet. We show that the signed-Diffie--Hellman SSH ciphersuites of the SSH protocol are secure: each is a secure authenticated and confidential channel establishment (ACCE) protocol, the same security definition now used to describe the security of Transport Layer Security (TLS) ciphersuites. While the ACCE definition suffices to describe the security of individual ciphersuites, it does not cover the case where parties use the same long-term key with many different ciphersuites: it is common in practice for the server to use the same signing key with both finite field and elliptic curve Diffie--Hellman, for example. While TLS is vulnerable to attack in this case, we show that SSH is secure even when the same signing key is used across multiple ciphersuites. We introduce a new generic multi-ciphersuite composition framework to achieve this result in a black-box way.
Keywords: authenticated and confidential channel establishment, cross-protocol security, key agility, multi-ciphersuite, secure shell (SSH) (ID#: 15-4536)
URL: http://doi.acm.org/10.1145/2660267.2660286

Koen Claessen, Michał H. Pałka; Splittable Pseudorandom Number Generators using Cryptographic Hashing; Haskell '13 Proceedings of the 2013 ACM SIGPLAN symposium on Haskell, January 2014, Pages 47-58. Doi: 10.1145/2578854.2503784 Abstract: We propose a new splittable pseudorandom number generator (PRNG) based on a cryptographic hash function. Splittable PRNGs, in contrast to linear PRNGs, allow the creation of two (seemingly) independent generators from a given random number generator. Splittable PRNGs are very useful for structuring purely functional programs, as they avoid the need for threading around state. We show that the currently known and used splittable PRNGs are either not efficient enough, have inherent flaws, or lack formal arguments about their randomness. In contrast, our proposed generator can be implemented efficiently, and comes with a formal statements and proofs that quantify how 'random' the results are that are generated. The provided proofs give strong randomness guarantees under assumptions commonly made in cryptography.
Keywords: haskell, provable security, splittable pseudorandom number generators (ID#: 15-4537)
URL:  http://doi.acm.org/10.1145/2578854.2503784

Junchao Wu, Qun Liu, Xiaofeng Liao; A Secure and Efficient Outsourceable Group Key Transfer Protocol in Cloud Computing; SCC '14 Proceedings of the 2nd International Workshop On Security In Cloud Computing, June 2014, Pages 43-50. Doi: 10.1145/2600075.2600079 Abstract: Cloud computing provides robust computational power, and the customer can economically access to large amount of computing resources with a "pay-per-use" utility service. It also brings forth new challenges for security when customers want to securely outsource the computation of cryptographic operations to the untrusted cloud servers. Though group key transfer is a quite common scientific and engineering task, it is difficult to implement the protocol among group members, if group members are computationally weaker players. Cloud computing provides an avenue for computationally weaker players. A novel system model, with two public cloud servers and a trusted key generation center (KGC), is proposed to address the issue of group key transfer. In order to protect the sensitive information of the customers from the public cloud's learning, we design a secure group key transfer protocol based on secret sharing in cloud computing, in which both KGC and weaker group members can delegate cloud servers to compute the interpolation polynomial and the group members are able to come up with a same key. Extensive theoretical analysis and experiment results are also given to validate the practicability of our protocol.
Keywords: cloud computing, group key transfer, interpolation polynomial, outsourcing, secret sharing (ID#: 15-4538)
URL: http://doi.acm.org/10.1145/2600075.2600079

Roland van Rijswijk-Deij, Anna Sperotto, Aiko Pras; DNSSEC and Its Potential for DDos Attacks: A Comprehensive Measurement Study;  IMC '14 Proceedings of the 2014 Conference on Internet Measurement Conference, November 2014, Pages 449-460. Doi: 10.1145/2663716.2663731 Abstract: Over the past five years we have witnessed the introduction of DNSSEC, a security extension to the DNS that relies on digital signatures. DNSSEC strengthens DNS by preventing attacks such as cache poisoning. However, a common argument against the deployment of DNSSEC is its potential for abuse in Distributed Denial of Service (DDoS) attacks, in particular reflection and amplification attacks. DNS responses for a DNSSEC-signed domain are typically larger than those for an unsigned domain, thus, it may seem that DNSSEC could actually worsen the problem of DNS-based DDoS attacks. The potential for abuse in DNSSEC-signed domains has, however, never been assessed on a large scale.  In this paper we establish ground truth around this open question. We perform a detailed measurement on a large dataset of DNSSEC-signed domains, covering 70% (2.5 million) of all signed domains in operation today, and compare the potential for amplification attacks to a representative sample of domains without DNSSEC. At first glance, the outcome of these measurements confirms that DNSSEC indeed worsens the DDoS phenomenon. Closer examination, however, gives a more nuanced picture. DNSSEC really only makes the situation worse for one particular query type (ANY), for which responses may be over 50 times larger than the original query (and in rare cases up to 179x). We also discuss a number of mitigation strategies that can have immediate impact for operators and suggest future research directions with regards to these mitigation strategies. 
Keywords: DDoS, DNS, DNSSEC, amplification attack, attack, denial of service, denial-of-service, measurements, reflection attack (ID#: 15-4539)
URL:  http://doi.acm.org/10.1145/2663716.2663731

Jeffrey Robinson, Brandon Dixon, Jeffrey Galloway; Montgomery Multiplication Using CUDA; ACM SE '14 Proceedings of the 2014 ACM Southeast Regional Conference, March 2014, Article No. 23. Doi: 10.1145/2638404.2638485 Abstract:  Modular multiplication is useful in many areas of number theory; the most well-known being cryptography. In order to encrypt or decrypt a document using either RSA or ECC encryption algorithms which perform long chains of multiplication modulo N. To factor large numbers many factoring algorithms have long multiplication chains modulo N, where N is a prime number. In our paper, we implement a highly optimized systolic Montgomery multiplication algorithm in order to provide high performance modular multiplications. We develop our algorithm using NVIDIAs general-purpose parallel programming model called CUDA (Compute Unified Device Architecture) for NVIDIA GPUs (Graphics Processing Units). Our implementation can perform up to 338.15 million multiplications per second using a GTX 660 and 475.66 using a GTX 670 with 256 bit numbers. While using 1024-bit numbers the GTX 660 can perform 20.15 million multiplications per second and the GTX 670 can perform 27.89 million multiplications per second. When using 2048-bit numbers, the GTX 660 can perform 4.96 million multiplications per second and the GTX 670 can perform 6.78 million multiplications per second. We also show that our version is faster than previous implemented multiprecision Montgomery multiplication algorithms, while also providing an intuitive data representation.
Keywords: CUDA, algorithms, concurrent processes, numerical methods, parallel computing (ID#: 15-4540)
URL: http://doi.acm.org/10.1145/2638404.2638485

Hongbo Liu, Hui Wang, Yingying Chen, Dayong Jia; Defending against Frequency-Based Attacks on Distributed Data Storage in Wireless Networks;  ACM Transactions on Sensor Networks (TOSN), Volume 10 Issue 3, April 2014, Article No. 49. Doi: 10.1145/2594774 Abstract: As wireless networks become more pervasive, the amount of the wireless data is rapidly increasing. One of the biggest challenges of wide adoption of distributed data storage is how to store these data securely. In this work, we study the frequency-based attack, a type of attack that is different from previously well-studied ones, that exploits additional adversary knowledge of domain values and/or their exact/approximate frequencies to crack the encrypted data. To cope with frequency-based attacks, the straightforward 1-to-1 substitution encryption functions are not sufficient. We propose a data encryption strategy based on 1-to-n substitution via dividing and emulating techniques to defend against the frequency-based attack, while enabling efficient query evaluation over encrypted data. We further develop two frameworks, incremental collection and clustered collection, which are used to defend against the global frequency-based attack when the knowledge of the global frequency in the network is not available. Built upon our basic encryption schemes, we derive two mechanisms, direct emulating and dual encryption, to handle updates on the data storage for energy-constrained sensor nodes and wireless devices. Our preliminary experiments with sensor nodes and extensive simulation results show that our data encryption strategy can achieve high security guarantee with low overhead.
Keywords: Frequency-based attack, secure distributed data storage, wireless networks (ID#: 15-4541)
URL:  http://doi.acm.org/10.1145/2594774 

Fabienne Eigner, Aniket Kate, Matteo Maffei, Francesca Pampaloni, Ivan Pryvalov; Differentially Private Data Aggregation with Optimal Utility; ACSAC '14 Proceedings of the 30th Annual Computer Security Applications Conference, December 2014, Pages 316-325. Doi: 10.1145/2664243.2664263 Abstract: Computing aggregate statistics about user data is of vital importance for a variety of services and systems, but this practice has been shown to seriously undermine the privacy of users. Differential privacy has proved to be an effective tool to sanitize queries over a database, and various cryptographic protocols have been recently proposed to enforce differential privacy in a distributed setting, e.g., statistical queries on sensitive data stored on the user's side. The widespread deployment of differential privacy techniques in real-life settings is, however, undermined by several limitations that existing constructions suffer from: they support only a limited class of queries, they pose a trade-off between privacy and utility of the query result, they are affected by the answer pollution problem, or they are inefficient. This paper presents PrivaDA, a novel design architecture for distributed differential privacy that leverages recent advances in secure multiparty computations on fixed and floating point arithmetic to overcome the previously mentioned limitations. In particular, PrivaDA supports a variety of perturbation mechanisms (e.g., the Laplace, discrete Laplace, and exponential mechanisms) and it constitutes the first generic technique to generate noise in a fully distributed manner while maintaining the optimal utility. Furthermore, PrivaDA does not suffer from the answer pollution problem. We demonstrate the efficiency of PrivaDA with a performance evaluation, and its expressiveness and flexibility by illustrating several application scenarios such as privacy-preserving web analytics.
Keywords:  (not provided) (ID#: 15-4542)
URL: http://doi.acm.org/10.1145/2664243.2664263

Haya Shulman; Pretty Bad Privacy: Pitfalls of DNS Encryption; WPES '14 Proceedings of the 13th Workshop on Privacy in the Electronic Society; November 2014, Pages 191-200. Doi: 10.1145/2665943.2665959 Abstract: As awareness for privacy of Domain Name System (DNS) is increasing, a number of mechanisms for encryption of DNS packets were proposed. We study the prominent defences, focusing on the privacy guarantees, interoperability with the DNS infrastructure, and the efficiency overhead. In particular:  •We explore dependencies in DNS and show techniques that utilise side channel leaks, due to transitive trust, allowing to infer information about the target domain in an encrypted DNS packet. •We examine common DNS servers configurations and show that the proposals are expected to encounter deployment obstacles with (at least) 38% of 50K-top Alexa domains and (at least) 12% of the top-level domains (TLDs), and will disrupt the DNS functionality and availability for clients. •We show that due to the non-interoperability with the caches, the proposals for end-to-end encryption may have a prohibitive traffic overhead on the name servers.  Our work indicates that further study may be required to adjust the proposals to stand up to their security guarantees, and to make them suitable for the common servers' configurations in the DNS infrastructure. Our study is based on collection and analysis of the DNS traffic of 50K-top Alexa domains and 568 TLDs.
Keywords: dns, dns caching, dns encryption, dns infrastructure, dns privacy, dns security, side channel attacks, transitive trust dependencies (ID#: 15-4543)
URL: http://doi.acm.org/10.1145/2665943.2665959

Boyang Wang, Yantian Hou, Ming Li, Haitao Wang, Hui Li; Maple: Scalable Multi-Dimensional Range Search over Encrypted Cloud Data with Tree-Based Index; ASIA CCS '14 Proceedings of the 9th ACM Symposium On Information, Computer And Communications Security, June 2014, Pages 111-122. Doi: 10.1145/2590296.2590305 Abstract: Cloud computing promises users massive scale outsourced data storage services with much lower costs than traditional methods. However, privacy concerns compel sensitive data to be stored on the cloud server in an encrypted form. This posts a great challenge for effectively utilizing cloud data, such as executing common SQL queries. A variety of searchable encryption techniques have been proposed to solve this issue; yet efficiency and scalability are still the two main obstacles for their adoptions in real-world datasets, which are multi-dimensional in general. In this paper, we propose a tree-based public-key Multi-Dimensional Range Searchable Encryption (MDRSE) to overcome the above limitations. Specifically, we first formally define the leakage function and security of a tree-based MDRSE. Then, by leveraging an existing predicate encryption in a novel way, our tree-based MDRSE efficiently indexes and searches over encrypted cloud data with multi-dimensional tree structures (i.e., R-trees). Moreover, our scheme is able to protect single-dimensional privacy while previous efficient solutions fail to achieve. Our scheme is selectively secure, and through extensive experimental evaluation on a large-scale real-world dataset, we show the efficiency and scalability of our scheme.
Keywords: encrypted cloud data, multiple dimension, range search, tree structures (ID#: 15-4544)
URL:  http://doi.acm.org/10.1145/2590296.2590305

Keita Emura, Akira Kanaoka, Satoshi Ohta, Takeshi Takahashi; Building Secure and Anonymous Communication Channel: Formal Model and Its Prototype Implementation; SAC '14 Proceedings of the 29th Annual ACM Symposium on Applied Computing, March 2014, Pages 1641-1648. Doi: 10.1145/2554850.2554879 Abstract: Various techniques need to be combined to realize anonymously authenticated communication. Cryptographic tools enable anonymous user authentication while anonymous communication protocols hide users' IP addresses from service providers. One simple approach for realizing anonymously authenticated communication is their simple combination. but this gives rise to another issue; how to build a secure channel. The current public key infrastructure cannot be used since the user's public key identifies the user. To cope with this issue, we propose a protocol that uses identity-based encryption for packet encryption without sacrificing anonymity, and group signature for anonymous user authentication. Communications in the protocol take place through proxy entities that conceal users' IP addresses from service providers. The underlying group signature is customized to meet our objective and improve its efficiency. We also introduce a proof-of-concept implementation to demonstrate the protocol's feasibility. We compare its performance to SSL communication and demonstrate its practicality, and conclude that the protocol realizes secure, anonymous, and authenticated communication between users and service providers with practical performance.
Keywords: anonymous authentication, anonymous communication, group signature, identity-based encryption, secure channel (ID#: 15-4545)
URL: http://doi.acm.org/10.1145/2554850.2554879  

Note:

Articles listed on these pages have been found on publicly available internet pages and are cited with links to those pages. Some of the information included herein has been reprinted with permission from the authors or data repositories. Direct any requests via Email to news@scienceofsecurity.net for removal of the links or modifications to specific citations. Please include the ID# of the specific citation in your correspondence.