Search

Imagine one or more non-colluding servers each holding a large public database, e.g., the repository of DNS entries. Clients would like to access entries in this database without disclosing their queries to the servers. Classical private information retrieval (PIR) schemes achieve polylogarithmic bandwidth per query, but require the server to perform linear computation per query, which is a significant barrier towards deployment. Several recent works showed, however, that by introducing a one-time, per-client, off-line preprocessing phase, an unbounded number of client queries can be subsequently served with sublinear online computation time per query (and the cost of the preprocessing can be amortized over the unboundedly many queries). Existing preprocessing PIR schemes (supporting unbounded queries), unfortunately, make undesirable tradeoffs to achieve sublinear online computation: they are either significantly non-optimal in online time or bandwidth, or require the servers to store a linear amount of state per client or even per query, or require polylogarithmically many non-colluding servers. We propose a novel 2-server preprocessing PIR scheme that achieves O~(n) online computation per query and O~(n) client storage, while preserving the polylogarithmic online bandwidth of classical PIR schemes. Both the online bandwidth and computation are optimal up to a poly-logarithmic factor. In our construction, each server stores only the original database and nothing extra, and each online query is served within a single round trip. Our construction relies on the standard LWE assumption. As an important stepping stone, we propose new, more generalized definitions for a cryptographic object called a Privately Puncturable Pseudorandom Set, and give novel constructions that depart significantly from prior approaches.

Starting with the two standard model of randomized communication complexity, we study the communication complexity of functions when the protocol has access to a defective source of randomness. Specifically, we consider both the public-randomness and private-randomness cases, while replacing the commonly postulated perfect randomness with distributions over 𝓁 bit strings that have min-entropy at least k ≤ 𝓁. We present general upper and lower bounds on the communication complexity in these cases, where the bounds are typically linear in 𝓁-k and also depend on the size of the fooling set for the function being computed and on its standard randomized complexity., LIPIcs, Vol. 200, 36th Computational Complexity Conference (CCC 2021), pages 14:1-14:10

We study the problem of discrete distribution testing in the two-party setting. For example, in the standard closeness testing problem, Alice and Bob each have $t$ samples from, respectively, distributions $a$ and $b$ over $[n]$, and they need to test whether $a=b$ or $a,b$ are $\epsilon$-far for some fixed $\epsilon>0$. This is in contrast to the well-studied one-party case, where the tester has unrestricted access to samples of both distributions, for which optimal bounds are known for a number of variations. Despite being a natural constraint in applications, the two-party setting has evaded attention so far. We address two fundamental aspects: 1) what is the communication complexity, and 2) can it be accomplished securely, without Alice and Bob learning extra information about each other's input. Besides closeness testing, we also study the independence testing problem, where Alice and Bob have $t$ samples from distributions $a$ and $b$ respectively, which may be correlated; the question is whether $a,b$ are independent of $\epsilon$-far from being independent. Our contribution is three-fold: 1) Communication: we show how to gain communication efficiency with more samples, beyond the information-theoretic bound on $t$. The gain is polynomially better than what one obtains by adapting standard algorithms. 2) Lower bounds: we prove tightness of our protocols for the closeness testing, and for the independence testing when the number of samples is unbounded. These lower bounds are of independent interest as these are the first 2-party communication lower bounds for testing problems. 3) Security: we define secure distribution testing and argue that it must leak at least some minimal information. We then provide secure versions of the above protocols with an overhead that is only polynomial in the security parameter.

In the search for post-quantum secure alternatives to RSA and ECC, lattice-based cryptography appears to be an attractive and efficient option. A particularly interesting lattice-based signature scheme is BLISS, offering key and signature sizes in the range of RSA moduli. A range of works on efficient implementations of BLISS is available, and the scheme has seen a first real-world adoption in strongSwan, an IPsec-based VPN suite. In contrast, the implementation-security aspects of BLISS, and lattice-based cryptography in general, are still largely unexplored.At CHES 2016, Groot Bruinderink et al. presented the first side-channel attack on BLISS, thus proving that this topic cannot be neglected. Nevertheless, their attack has some limitations. First, the technique is demonstrated via a proof-of-concept experiment that was not performed under realistic attack settings. Furthermore, the attack does not apply to BLISS-B, an improved variant of BLISS and also the default option in strongSwan. This problem also applies to later works on implementation security of BLISS.In this work, we solve both of the above problems. We present a new side-channel key-recovery algorithm against both the original BLISS and the BLISS-B variant. Our key-recovery algorithm draws on a wide array of techniques, including learning-parity with noise, integer programs, maximimum likelihood tests, and a lattice-basis reduction. With each application of a technique, we reveal additional information on the secret key culminating in a complete key recovery.Finally, we show that cache attacks on post-quantum cryptography are not only possible, but also practical. We mount an asynchronous cache attack on the production-grade BLISS-B implementation of strongSwan. The attack recovers the secret signing key after observing roughly 6000 signature generations.

This book constitutes the refereed proceedings of the 13th International Conference on Applied Cryptography and Network Security, ACNS 2015, held in New York, NY, USA, in June 2015. The 33 revised full papers included in this volume and presented together with 2 abstracts of invited talks, were carefully reviewed and selected from 157 submissions. They are organized in topical sections on secure computation: primitives and new models; public key cryptographic primitives; secure computation II: applications; anonymity and related applications; cryptanalysis and attacks (symmetric crypto); privacy and policy enforcement; authentication via eye tracking and proofs of proximity; malware analysis and side channel attacks; side channel countermeasures and tamper resistance/PUFs; and leakage resilience and pseudorandomness.

Zero-knowledge succinct non-interactive arguments (zk-SNARKs) rely on knowledge assumptions for their security. Meanwhile, as the complexity and scale of cryptographic systems continues to grow, the composition of secure protocols is of vital importance. The current gold standards of composable security, the Universal Composability and Constructive Cryptography frameworks cannot capture knowledge assumptions, as their core proofs of composition prohibit white-box extraction. In this paper, we present a formal model allowing the composition of knowledge assumptions. Despite showing impossibility for the general case, we demonstrate the model’s usefulness when limiting knowledge assumptions to few instances of protocols at a time. We finish by providing the first instance of a simultaneously succinct and composable zk-SNARK, by using existing results within our framework.

This paper closes the question of the possibility of two-round MPC protocols achieving different security guarantees with and without the availability of broadcast in any given round. Cohen et al. [CGZ20] study this question in the dishonest majority setting; we complete the picture by studying the honest majority setting. In the honest majority setting, given broadcast in both rounds, it is known that the strongest guarantee—guaranteed output delivery—is achievable [GLS15]. We show that, given broadcast in the first round only, guaranteed output delivery is still achievable. Given broadcast in the second round only, we give a new construction that achieves identifiable abort, and we show that fairness—and thus guaranteed output delivery—are not achievable in this setting. Finally, if only peer-to-peer channels are available, we show that the weakest guarantee—selective abort—is the only one achievable for corruption thresholds t> 1 and for t= 1 and n= 3. On the other hand, it is already known that selective abort can be achieved in these cases. In the remaining cases, i.e., t= 1 and n≥ 4, it is known [IKP10, IKKP15] that guaranteed output delivery (and thus all weaker guarantees) are possible.

Recent proposals for trusted hardware platforms, such as Intel SGX and the MIT Sanctum processor, offer compelling security features but lack formal guarantees. We introduce a verification methodology based on a trusted abstract platform (TAP), a formalization of idealized enclave platforms along with a parameterized adversary. We also formalize the notion of secure remote execution and present machine-checked proofs showing that the TAP satisfies the three key security properties that entail secure remote execution: integrity, confidentiality and secure measurement. We then present machine-checked proofs showing that SGX and Sanctum are refinements of the TAP under certain parameterizations of the adversary, demonstrating that these systems implement secure enclaves for the stated adversary models.

© 2017 author(s). We introduce the key reinstallation attack. This attack abuses design or implementation flaws in cryptographic protocols to reinstall an already-in-use key. This resets the key's associated parameters such as transmit nonces and receive replay counters. Several types of cryptographic Wi-Fi handshakes are affected by the attack. All protected Wi-Fi networks use the 4-way handshake to generate a fresh session key. So far, this 14-year-old handshake has remained free from attacks, and is even proven secure. However, we show that the 4-way handshake is vulnerable to a key reinstallation attack. Here, the adversary tricks a victim into reinstalling an already-in-use key. This is achieved by manipulating and replaying handshake messages. When reinstalling the key, associated parameters such as the incremental transmit packet number (nonce) and receive packet number (replay counter) are reset to their initial value. Our key reinstallation attack also breaks the PeerKey, group key, and Fast BSS Transition (FT) handshake. The impact depends on the handshake being attacked, and the data-confidentiality protocol in use. Simplified, against AES-CCMP an adversary can replay and decrypt (but not forge) packets. This makes it possible to hijack TCP streams and inject malicious data into them. Against WPATKIP and GCMP the impact is catastrophic: Packets can be replayed, decrypted, and forged. Because GCMP uses the same authentication key in both communication directions, it is especially affected. Finally, we confirmed our findings in practice, and found that every Wi-Fi device is vulnerable to some variant of our attacks. Notably, our attack is exceptionally devastating against Android 6.0: It forces the client into using a predictable all-zero encryption key. ispartof: pages:1313-1328 ispartof: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (CCS 2017) pages:1313-1328 ispartof: ACM SIGSAC Conference on Computer and Communications Security (CCS 2017) location:Dallas, TX date:30 Oct - 3 Nov 2017 status: published

© 2017 author(s). The functionality and security of all domain names are contingent upon their nameservers. When these nameservers, or requests to them, are compromised, all domains that rely on them are a.ected. In this paper, we study the exploitation of con.guration issues (typosquatting and outdated WHOIS records) and hardware errors (bitsquatting) to seize control over nameservers' requests to hijack domains.We perform a large-scale analysis of 10,000 popular nameserver domains, in which we map out existing abuse and vulnerable entities. We con.rm the capabilities of these attacks through realworld measurements. Overall, we. nd that over 12,000 domains are susceptible to near-immediate compromise, while 52.8M domains are being targeted by nameserver bitsquatters that respond with rogue IP addresses. Additionally, we determine that 1.28M domains are at risk of a denial-of-service attack by relying on an outdated nameserver. ispartof: pages:957-970 ispartof: CCS'17: PROCEEDINGS OF THE 2017 ACM SIGSAC CONFERENCE ON COMPUTER AND COMMUNICATIONS SECURITY pages:957-970 ispartof: 24th ACM-SIGSAC Conference on Computer and Communications Security (ACM CCS) location:Dallas, USA date:30 Oct - 3 Nov 2017 status: published

The development of positioning technologies has resulted in an increasing amount of mobility data being available. While bringing a lot of convenience to people's life, such availability also raises serious concerns about privacy. In this paper, we concentrate on one of the most sensitive information that can be inferred from mobility data, namely social relationships. We propose a novel social relation inference attack that relies on an advanced feature learning technique to automatically summarize users' mobility features. Compared to existing approaches, our attack is able to predict any two individuals' social relation, and it does not require the adversary to have any prior knowledge on existing social relations. These advantages significantly increase the applicability of our attack and the scope of the privacy assessment. Extensive experiments conducted on a large dataset demonstrate that our inference attack is effective, and achieves between 13% to 20% improvement over the best state-of-the-art scheme. We propose three defense mechanisms -- hiding, replacement and generalization -- and evaluate their effectiveness for mitigating the social link privacy risks stemming from mobility data sharing. Our experimental results show that both hiding and replacement mechanisms outperform generalization. Moreover, hiding and replacement achieve a comparable trade-off between utility and privacy, the former preserving better utility and the latter providing better privacy., Comment: ACM CCS 17

In [18] Cramer, Damgard and Schoenmakers (CDS) devise an OR-composition technique for \(\varSigma \)-protocols that allows to construct highly-efficient proofs for compound statements. Since then, such technique has found countless applications as building block for designing efficient protocols.

© Springer International Publishing Switzerland 2015. A straightforward way of constructing an n-bit pseudorandom function is to XOR two or more pseudorandom permutations: p1 ⊕... ⊕ pk. This XOR construction has gained broad attention over the last two decades. In this work, we revisit the security of this wellestablished construction. We consider the case where the underlying permutations are considered secret, as well as the case where these permutations are publicly available to the adversary. In the secret permutation setting, we present a simple reduction showing that the XOR construction achieves optimal 2 n security for all k ≥ 2, therewith improving a recent result of Cogliati et al. (FSE 2014). Regarding the public permutation setting, Mandal et al. (INDOCRYPT 2010) proved 2 2n/3 security for the case k = 2, but we point out the existence of a non-trivial flaw in the proof. We re-establish and generalize the claimed security bound for general k ≥ 2 using a different proof approach. ispartof: pages:619-634 ispartof: Lecture Notes in Computer Science vol:9092 pages:619-634 ispartof: 13th International Conference on Applied Cryptography and Network Security (ACNS 2015) location:Columbia University, New York date:2 Jun - 5 Jun 2015 status: published