An official website of the United States government
Logic encryption, a method to lock a circuit from unauthorized use unless the correct key is provided, is the most important technique in hardware IP protection. However, with the discovery of the SAT attack, all traditional logic encryption algorithms are broken. New algorithms after the SAT attack are all vulnerable to structural analysis unless a provable obfuscation is applied to the locked circuit. But there is no provable logic obfuscation available, in spite of some vague resorting to logic resynthesis. In this paper, we formulate and discuss a trilemma in logic encryption among locking robustness, structural security, and encryption efficiency, showing that pre-SAT approaches achieve only structural security and encryption efficiency, and post-SAT approaches achieve only locking robustness and encryption efficiency. There is also a dilemma between query complexity and error number in locking. We first develop a theory and solution to the dilemma in locking between query complexity and error number. Then, we provide a provable obfuscation solution to the dilemma between structural security and locking robustness. We finally present and discuss some results towards the resolution of the trilemma in logic encryption.
more »
« less
Comprehensive Anonymity Trilemma: User Coordination is not enough
Abstract For anonymous communication networks (ACNs), Das et al. recently confirmed a long-suspected trilemma result that ACNs cannot achieve strong anonymity, low latency overhead and low bandwidth overhead at the same time. Our paper emanates from the careful observation that their analysis does not include a relevant class of ACNs with what we call user coordination where users proactively work together towards improving their anonymity. We show that such protocols can achieve better anonymity than predicted by the above trilemma result. As the main contribution, we present a stronger impossibility result that includes all ACNs we are aware of. Along with our formal analysis, we provide intuitive interpretations and lessons learned. Finally, we demonstrate qualitatively stricter requirements for the Anytrust assumption (all but one protocol party is compromised) prevalent across ACNs.
more »
« less
- PAR ID:
- 10200543
- Date Published:
- Journal Name:
- Proceedings on Privacy Enhancing Technologies
- Volume:
- 2020
- Issue:
- 3
- ISSN:
- 2299-0984
- Page Range / eLocation ID:
- 356 to 383
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
This paper examines an existential threat to Tor— the increasing frequency at which websites apply discriminatory behavior to users who arrive via the anonymity network. Our main contribution is the introduction of Tor exit bridges. Exit bridges, constructed as short-lived virtual machines on cloud service providers, serve as alternative egress points for Tor and are designed to bypass server-side censorship. Due to the proliferation of managed cloud-based desktop services (e.g., Amazon Workspaces), there is already a surprisingly large fraction of web requests that originate in the cloud. Trivially disrupting exit bridges by blocking requests from the cloud would thus lead to significant collateral damage. Our experiments demonstrate that exit bridges effectively circumvent server-side blocking of Tor with low overhead. Ad- ditionally, we perform a cost-analysis of exit bridges and show that even a large-scale deployment can be done at low cost.more » « less
-
Federated learning enables users to collaboratively train a machine learning model over their private datasets. Secure aggregation protocols are employed to mitigate information leakage about the local datasets from user-submitted model updates. This setup, however, still leaks the user participation in training, which can also be sensitive. Protecting user anonymity is even more challenging in dynamic environments where users may (re)join or leave the training process at any point of time. This paper introduces AnoFel, the first framework to support private and anonymous dynamic participation in federated learning (FL). AnoFel leverages several cryptographic primitives, the concept of anonymity sets, differential privacy, and a public bulletin board to support anonymous user registration, as well as unlinkable and confidential model update submission. Our system allows dynamic participation, where users can join or leave at any time without needing any recovery protocol or interaction. To assess security, we formalize a notion for privacy and anonymity in FL, and formally prove that AnoFel satisfies this notion. To the best of our knowledge, our system is the first solution with provable anonymity guarantees. To assess efficiency, we provide a concrete implementation of AnoFel, and conduct experiments showing its ability to support learning applications scaling to a large number of clients. For a TinyImageNet classification task with 512 clients, the client setup to join is less than 3 sec, and the client runtime for each training iteration takes a total of 8 sec, where the added overhead of AnoFel is 46% of the total runtime. We also compare our system with prior work and demonstrate its practicality. AnoFel client runtime is up to 5x faster than Truex et al., despite the added anonymity guarantee and dynamic user joining in AnoFel. Compared to Bonawitz et al., AnoFel is only 2x slower for added support for privacy in output, dynamic user joining, and anonymity.more » « less
-
Tessaro, Stefano (Ed.)Onion routing is the most widely used approach to anonymous communication online. The idea is that Alice wraps her message to Bob in layers of encryption to form an “onion” and routes it through a series of intermediaries. Each intermediary’s job is to decrypt (“peel”) the onion it receives to obtain instructions for where to send it next. The intuition is that, by the time it gets to Bob, the onion will have mixed with so many other onions that its origin will be hard to trace even for an adversary that observes the entire network and controls a fraction of the participants, possibly including Bob. Despite its widespread use in practice, until now no onion routing protocol was known that simultaneously achieved, in the presence of an active adversary that observes all network traffic and controls a constant fraction of the participants, (a) anonymity; (b) fault-tolerance, where even if a few of the onions are dropped, the protocol still delivers the rest; and (c) reasonable communication and computational complexity as a function of the security parameter and the number of participants. In this paper, we give the first onion routing protocol that meets these goals: our protocol (a) achieves anonymity; (b) tolerates a polylogarithmic (in the security parameter) number of dropped onions and still delivers the rest; and (c) requires a polylogarithmic number of rounds and a polylogarithmic number of onions sent per participant per round. We also show that to achieve anonymity in a fault-tolerant fashion via onion routing, this number of onions and rounds is necessary. Of independent interest, our analysis introduces two new security properties of onion routing – mixing and equalizing – and we show that together they imply anonymity.more » « less
-
Internet blackouts are challenging environments for anonymity and censorship resistance. Existing popular anonymity networks (e.g., Freenet, I2P, Tor) rely on Internet connectivity to function, making them impracticable during such blackouts. In such a setting, mobile ad-hoc networks can provide connectivity, but prior communication protocols for ad-hoc networks are not designed for anonymity and attack resilience. We address this need by designing, implementing, and evaluating Moby, a blackout-resistant anonymity network for mobile devices. Moby provides end-to-end encryption, forward secrecy and sender-receiver anonymity. It features a bi-modal design of operation, using Internet connectivity when available and ad-hoc networks during blackouts. During periods of Internet connectivity, Moby functions as a regular messaging application and bootstraps information that is later used in the absence of Internet connectivity to achieve secure anonymous communications. Moby incorporates a model of trust based on users’ contact lists, and a trust establishment protocol that mitigates flooding attacks. We perform an empirically informed simulation-based study based on cellphone traces of 268,596 users over the span of a week for a large cellular provider to determine Moby’s feasibility and present our findings. Last, we implement and evaluate the Moby client as an Android app.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.2478/popets-2020-0056
