Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data.

J. D. Tygar

dblp:t/JDTygar · also J. Doug Tygar · DBLP profile ↗
← Back
52ranked-venue papers
5as first author
0since 2021 · last 2017
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Security and privacy · 25Computer networks · 7Artificial intelligence and machine learning · 5Systems, architecture and hardware · 5 · 2 first-authorHuman-computer interaction and ubiquitous computing · 3Software engineering, systems software and programming languages · 2Databases, data management, data science and information retrieval · 2 · 2 first-authorGraphics, computer vision, multimedia, augmented reality and games · 2 · 1 first-authorTheory of computation · 2

Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.

Network and information security
22 papers
Security and privacy of machine learning · 40% Web and mobile security · 12% Cryptographic protocols and secure computation · 11%
Artificial intelligence
5 papers
Learning theory · 48% Trustworthy machine learning · 29% Deep learning architectures and training · 11%
Theoretical computer science
4 papers
Mathematical optimization · 68% Graph algorithms and graph theory · 26% Computational complexity · 4%

Topics — the 30 heaviest of 72, each with the papers that count most for it

TopicWeightPapersLastEvidence papers
Security and privacy of machine learning › adversarial attack
evasion attack
0.422016
Evasion and Hardening of Tree Ensemble Classifiers · ICML 2016
Query Strategies for Evading Convex-Inducing Classifiers · J. Mach. Learn. Res. 2012
Security and privacy of machine learning
adversarial attack
0.322016
Evasion and Hardening of Tree Ensemble Classifiers · ICML 2016
ANTIDOTE: understanding and defending against poisoning of anomaly detectors · Internet Measurement Conference 2009
Security and privacy of machine learning
adversarial robustness
0.212016
Evasion and Hardening of Tree Ensemble Classifiers · ICML 2016
Machine learning › Learning theory › margin-based learning
large margin classification
0.212014
Large-Margin Convex Polytope Machine · NIPS 2014
Mathematical optimization › continuous optimization
convex optimization
0.212014
Large-Margin Convex Polytope Machine · NIPS 2014
Cryptographic protocols and secure computation › key management
group key management
0.222011
Secure group key management using uni-directional proxy re-encryption schemes · INFOCOM 2011
ELK, A New Protocol for Efficient Large-Group Key Distribution · S&P 2001
Machine learning › Trustworthy machine learning › adversarial machine learning
evasion attack
0.112012
Query Strategies for Evading Convex-Inducing Classifiers · J. Mach. Learn. Res. 2012
Cryptographic primitives and cryptanalysis
proxy re-encryption
0.112011
Secure group key management using uni-directional proxy re-encryption schemes · INFOCOM 2011
Cryptographic primitives and cryptanalysis › public-key cryptography
public-key encryption
0.112011
Secure group key management using uni-directional proxy re-encryption schemes · INFOCOM 2011
Network security › intrusion detection and prevention › intrusion detection
anomaly detection
0.112009
ANTIDOTE: understanding and defending against poisoning of anomaly detectors · Internet Measurement Conference 2009
Usable security › authentication usability
authentication ceremony
0.112009
Conditioned-safe Ceremonies and a User Study of an Application to Web Authentication · NDSS 2009
Network security › intrusion detection and prevention
intrusion detection
0.112009
ANTIDOTE: understanding and defending against poisoning of anomaly detectors · Internet Measurement Conference 2009
Security and privacy of machine learning
poisoning attack
0.112009
ANTIDOTE: understanding and defending against poisoning of anomaly detectors · Internet Measurement Conference 2009
Web and mobile security
web authentication
0.112009
Conditioned-safe Ceremonies and a User Study of an Application to Web Authentication · NDSS 2009
Machine learning › Learning theory
classification
0.112007
Optimal ROC Curve for a Combination of Classifiers · NIPS 2007
Machine learning › Kernel, tree and ensemble methods
classifier combination
0.112007
Optimal ROC Curve for a Combination of Classifiers · NIPS 2007
Machine learning › Learning theory › classification
ROC analysis
0.112007
Optimal ROC Curve for a Combination of Classifiers · NIPS 2007
Web and mobile security › browser security
same-origin policy
0.112007
Dynamic pharming attacks and locked same-origin policies for web browsers · CCS 2007
Cryptographic protocols and secure computation › secure message transmission
stream authentication
0.122002
Expander Graphs for Digital Stream Authentication and Robust Overlay Networks · S&P 2002
Efficient Authentication and Signing of Multicast Streams over Lossy Channels · S&P 2000
Web and mobile security
phishing
0.112006
Why phishing works · CHI 2006
Authentication and access control › password security
password recovery
0.112005
Keyboard acoustic emanations revisited · CCS 2005
Authentication and access control
authentication
0.012004
Distillation Codes and Applications to DoS Resistant Multicast Authentication · NDSS 2004
Network security › attack strategy
denial-of-service attack
0.012004
Distillation Codes and Applications to DoS Resistant Multicast Authentication · NDSS 2004
Authentication and access control › authentication
multicast authentication
0.012004
Distillation Codes and Applications to DoS Resistant Multicast Authentication · NDSS 2004
Distributed systems › peer-to-peer systems
overlay networks
0.012002
Expander Graphs for Digital Stream Authentication and Robust Overlay Networks · S&P 2002
Graph algorithms and graph theory › expander graphs
expander constructions
0.012002
Expander Graphs for Digital Stream Authentication and Robust Overlay Networks · S&P 2002
Graph algorithms and graph theory
expander graphs
0.012002
Expander Graphs for Digital Stream Authentication and Robust Overlay Networks · S&P 2002
Internet architecture and protocols › multicast
secure multicast
0.012001
Efficient and Secure Source Authentication for Multicast · NDSS 2001
Internet of things and sensor networks
sensor network security
0.012001
SPINS: security protocols for sensor netowrks · MobiCom 2001
Network security › protocol security
source authentication
0.012001
Efficient and Secure Source Authentication for Multicast · NDSS 2001

Methods — techniques the papers use, named apart from their topics

symbolic prediction · 0.5mixed-integer linear programming · 0.5adversarial boosting · 0.5query strategy · 0.3statistical machine learning · 0.2large-margin learning · 0.2large margin learning · 0.2convex polytopes · 0.2convex polytope · 0.2proxy re-encryption · 0.1RSA · 0.1user study · 0.1x.509 certificates · 0.1provable security analysis · 0.1neyman-pearson lemma · 0.1expander graph construction · 0.1DNS rebinding · 0.1linear classification · 0.1
YearPublicationVenuePosition
2017 Organisational culture, procedural countermeasures, and employee security behaviour: A qualitative study
abstract
Purpose This paper provides new insights about security behaviour in selected US and Irish organisations by investigating how organisational culture and procedural security countermeasures tend to influence employee security actions. An increasing number of information security breaches in organisations presents a serious threat to the confidentiality of personal and commercially sensitive data. While recent research shows that humans are the weakest link in the security chain and the root cause of a great portion of security breaches, the extant security literature tends to focus on technical issues. Design/methodology/approach This paper builds on general deterrence theory and prior organisational culture literature. The methodology adapted for this study draws on the analytical grounded theory approach employing a constant comparative method. Findings This paper demonstrates that procedural security countermeasures and organisational culture tend to affect security behaviour in organisational settings. Research limitations/implications This paper fills the void in information security research and takes its place among the very few studies that focus on behavioural as opposed to technical issues. Practical implications This paper highlights the important role of procedural security countermeasures, information security awareness and organisational culture in managing illicit behaviour of employees. Originality/value This study extends general deterrence theory in a novel way by including information security awareness in the research model and by investigating both negative and positive behaviours.
Lena Yuryna Connolly, Michael Lang 0001, John Ng'ang'a Gathegi, J. D. Tygar
Inf. Comput. Secur.4
2016 Reviewer Integration and Performance Measurement for Malware Detection
Brad Miller 0002, Alex Kantchelian, Michael Carl Tschantz, Sadia Afroz 0001, Rekha Bachwani, Riyaz Faizullabhoy, Ling Huang 0001, Vaishaal Shankar, Tony Wu 0002, George Yiu, Anthony D. Joseph, J. D. Tygar
DIMVA12
2016 Evasion and Hardening of Tree Ensemble Classifiers
abstract
Classifier evasion consists in finding for a given instance x the “nearest” instance x’ such that the classifier predictions of x and x’ are different. We present two novel algorithms for systematically computing evasions for tree ensembles such as boosted trees and random forests. Our first algorithm uses a Mixed Integer Linear Program solver and finds the optimal evading instance under an expressive set of constraints. Our second algorithm trades off optimality for speed by using symbolic prediction, a novel algorithm for fast finite differences on tree ensembles. On a digit recognition task, we demonstrate that both gradient boosted trees and random forests are extremely susceptible to evasions. Finally, we harden a boosted tree model without loss of predictive accuracy by augmenting the training set of each boosting round with evading instances, a technique we call adversarial boosting.
Alex Kantchelian, J. D. Tygar, Anthony D. Joseph
ICML2
2015 Investigation of Employee Security Behaviour: A Grounded Theory Approach
Lena Yuryna Connolly, Michael Lang 0001, J. D. Tygar
SEC3
2014 Large-Margin Convex Polytope Machine
Alex Kantchelian, Michael Carl Tschantz, Ling Huang 0001, Peter L. Bartlett, Anthony D. Joseph, J. D. Tygar
NIPS6
2014 I Know Why You Went to the Clinic: Risks and Realization of HTTPS Traffic Analysis
Brad Miller 0002, Ling Huang 0001, Anthony D. Joseph, J. D. Tygar
Privacy Enhancing Technologies4
2014 Managing Employee Security Behaviour in Organisations: The Role of Cultural Factors and Individual Values
Lena Yuryna Connolly, Michael Lang 0001, J. D. Tygar
SEC3
2013 A low-bandwidth camera sensor platform with applications in smart camera networks
abstract
Smart camera networks have recently emerged as a new class of sensor network infrastructure that is capable of supporting high-power in-network signal processing and enabling a wide range of applications. In this article, we provide an exposition of our efforts to build a low-bandwidth wireless camera network platform, called CITRIC, and its applications in smart camera networks. The platform integrates a camera, a microphone, a frequency-scalable (up to 624 MHz) CPU, 16 MB FLASH, and 64 MB RAM onto a single device. The device then connects with a standard sensor network mote to form a wireless camera mote. With reasonably low power consumption and extensive algorithmic libraries running on a decent operating system that is easy to program, CITRIC is ideal for research and applications in distributed image and video processing. Its capabilities of in-network image processing also reduce communication requirements, which has been high in other existing camera networks with centralized processing. Furthermore, the mote easily integrates with other low-bandwidth sensor networks via the IEEE 802.15.4 protocol. To justify the utility of CITRIC, we present several representative applications. In particular, concrete research results will be demonstrated in two areas, namely, distributed coverage hole identification and distributed object recognition.
Phoebus Chen, Kirak Hong, Nikhil Naikal, S. Shankar Sastry, J. D. Tygar, Posu Yan, Allen Y. Yang, Lung-Chung Chang, Leon Lin, Edgar J. Lobaton, Songhwai Oh, Parvez Ahammad
ACM Trans. Sens. Networks5
2012 Query Strategies for Evading Convex-Inducing Classifiers
Blaine Nelson, Benjamin I. P. Rubinstein, Ling Huang 0001, Anthony D. Joseph, Steven J. Lee, Satish Rao, J. D. Tygar
J. Mach. Learn. Res.7
2011 Secure group key management using uni-directional proxy re-encryption schemes
abstract
The group key management is for a group manager to maintain a consistent group key for a dynamic group of members through a broadcast channel. In this paper we propose a group key management scheme based on a meta proxy re-encryption (PRE) scheme. In particular, we propose an RSA-based PRE scheme with special properties. It is the first RSA-based PRE scheme for group key management and has the desired properties of uni-directionality and multi-hop. In our group key management scheme, each group member holds just one secret auxiliary key and logN public auxiliary keys. The size of rekey messages for each group key update remains O(logN). Additionally, our scheme has some distinct features. Firstly, the size of the key update history is a constant O(N) no matter how many times of group key updates occur. Secondly, the computation time of computing the newest group key from the key update history is always O(logN) no matter how many group key updates are missed. This feature provides a practical solution for group key update when members go offline from time to time. Finally, the proposed scheme is immune to the collusion attack of other members.
Yi-Ruei Chen, J. D. Tygar, Wen-Guey Tzeng
INFOCOM2
2010 CAPTCHA Using Strangeness in Machine Translation
abstract
CAPTCHA is a technique that is used to prevent automatic programs from being able to acquire free e-mail or online service accounts. However, as many researchers have already reported, conventional CAPTCHA could be overcome by state-of-the-art malware since the capabilities of computers are approaching those of humans. Therefore, CAPTCHA should be based on even more advanced human-cognitive-processing abilities. We propose using the human ability of recognizing “strangeness” to achieve a new CAPTCHA. This paper focuses on strangeness in machine-translated sentences as an example, and proposes CAPTCHA using Strangeness in Sentences (SS-CAPTCHA), which detects malware by checking if users can distinguish natural sentences created by humans from machine-translated sentences. We discuss possible threats to SS-CAPTCHA and countermeasures against these threats. We also carried out basic experiments to confirm its usability by human users.
Takumi Yamamoto, J. D. Tygar, Masakatsu Nishigaki
AINA2
2010 The security of machine learning
abstract
Machine learning’s ability to rapidly evolve to changing and complex situations has helped it become a fundamental tool for computer security. That adaptability is also a vulnerability: attackers can exploit machine learning systems. We present a taxonomy identifying and analyzing attacks against machine learning systems. We show how these classes influence the costs for the attacker and defender, and we give a formal structure defining their interaction. We use our framework to survey and analyze the literature of attacks against machine learning systems. We also illustrate our taxonomy by showing how it can guide attacks against SpamBayes, a popular statistical spam filter. Finally, we discuss how our taxonomy suggests new lines of defenses.
Marco Barreno, Blaine Nelson, Anthony D. Joseph, J. D. Tygar
Mach. Learn.4
2010 Secure encrypted-data aggregation for wireless sensor networks
Shih-I Huang, Shiuh-Pyng Shieh, J. D. Tygar
Wirel. Networks3
2009 ANTIDOTE: understanding and defending against poisoning of anomaly detectors
abstract
Statistical machine learning techniques have recently garnered increased popularity as a means to improve network design and security. For intrusion detection, such methods build a model for normal behavior from training data and detect attacks as deviations from that model. This process invites adversaries to manipulate the training data so that the learned model fails to detect subsequent attacks.
Benjamin I. P. Rubinstein, Blaine Nelson, Ling Huang 0001, Anthony D. Joseph, Shing-hon Lau, Satish Rao, Nina Taft, J. D. Tygar
Internet Measurement Conference8
2009 Conditioned-safe Ceremonies and a User Study of an Application to Web Authentication
Chris Karlof, J. D. Tygar, David A. Wagner 0001
NDSS2
2009 Conditioned-safe ceremonies and a user study of an application to web authentication
abstract
No abstract available.
Chris Karlof, J. D. Tygar, David A. Wagner 0001
SOUPS2
2009 OSNP: Secure wireless authentication protocol using one-time key
Yu-Lun Huang, P. H. Lu, J. D. Tygar, Anthony D. Joseph
Comput. Secur.3
2009 Keyboard acoustic emanations revisited
abstract
We examine the problem of keyboard acoustic emanations. We present a novel attack taking as input a 10-minute sound recording of a user typing English text using a keyboard and recovering up to 96% of typed characters. There is no need for training recordings labeled with the corresponding clear text. A recognizer bootstrapped from a 10-minute sound recording can even recognize random text such as passwords: In our experiments, 90% of 5-character random passwords using only letters can be generated in fewer than 20 attempts by an adversary; 80% of 10-character passwords can be generated in fewer than 75 attempts by an adversary. In the attack, we use the statistical constraints of the underlying content, English language, to reconstruct text from sound recordings without knowing the corresponding clear text. The attack incorporates a combination of standard machine learning and speech recognition techniques, including cepstrum features, Hidden Markov Models, linear classification, and feedback-based incremental learning.
Li Zhuang, J. D. Tygar
ACM Trans. Inf. Syst. Secur.3
2008 A Power-Preserving Broadcast Protocol for WSNs with DoS Resistance
abstract
Broadcast presents a special challenge for wireless sensor networks (WSNs). In some situation such as time synchronization or building routing path, broadcasting messages must be securely transmitted to all nodes, but this process is subject to attack by adversaries. For example, an adversary may try to waste the battery power of intermediate nodes by forcing a compromised node to repeatedly rebroadcast, thus causing a denial-of-service (DoS) attack. One way to solve this problem is use only part of the nodes in the network as the intermediate nodes, limiting the effects of the attack. In this paper, we propose a novel broadcast protocol: broadcast power preserving (BOPP). In BOPP, a packet reception reliability metric of each network component is discovered. This reliability score gives the packet reception rate of each communication edge in the network. With the scoring metric, BOPP can judge the network reliability from time to time and adapt the network to provide maximum reliability while minimizing the energy cost. This enables the network to resist DoS attacks.
Chien-Chun Ni, Tien-Ruey Hsiang, J. D. Tygar
ICCCN3
2008 Evading Anomaly Detection through Variance Injection Attacks on PCA
Benjamin I. P. Rubinstein, Blaine Nelson, Ling Huang 0001, Anthony D. Joseph, Shing-hon Lau, Nina Taft, J. D. Tygar
RAID7
2007 Dynamic pharming attacks and locked same-origin policies for web browsers
abstract
We describe a new attack against web authentication, which we call dynamic pharming. Dynamic pharming works by hijacking DNS and sending the victim's browser malicious Javascript, which then exploits DNS rebinding vulnerabilities and the name-based same-origin policy to hijack a legitimate session after authentication has taken place. As a result, the attack works regardless of the authentication scheme used. Dynamic pharming enables the adversary to eavesdrop on sensitive content, forge transactions, sniff secondary passwords, etc. To counter dynamic pharming attacks, we propose two locked same-origin policies for web browsers. In contrast to the legacy same-origin policy, which regulates cross-object access control in browsers using domain names, the locked same-origin policies enforce access using servers' X.509 certificates and public keys. We show how our policies help two existing web authentication mechanisms, client-side SSL and SSL-only cookies, resist both pharming and stronger active attacks. Also, we present a deployability analysis of our policies based on a study of 14651 SSL domains. Our results suggest one of our policies can be deployed today and interoperate seamlessly with the vast majority of legacy web servers. For our other policy, we present a simple incrementally deployable opt-in mechanism for legacy servers using policy files, and show how web sites can use policy files to support self-signed and untrusted certificates, shared subdomain objects, and key updates.
Chris Karlof, Umesh Shankar, J. D. Tygar, David A. Wagner 0001
CCS3
2007 Optimal ROC Curve for a Combination of Classifiers
abstract
We present a new analysis for the combination of binary classifiers. We propose a theoretical framework based on the Neyman-Pearson lemma to analyze combinations of classifiers. In particular, we give a method for finding the optimal decision rule for a combination of classifiers and prove that it has the optimal ROC curve. We also show how our method generalizes and improves on previous work on combining classifiers and generating ROC curves.
Marco Barreno, Alvaro A. Cárdenas, J. D. Tygar
NIPS3
2006 Can machine learning be secure?
abstract
Machine learning systems offer unparalled flexibility in dealing with evolving input in a variety of applications, such as intrusion detection systems and spam e-mail filtering. However, machine learning algorithms themselves can be a target of attack by a malicious adversary. This paper provides a framework for answering the question, "Can machine learning be secure?" Novel contributions of this paper include a taxonomy of different types of attacks on machine learning techniques and systems, a variety of defenses against those attacks, a discussion of ideas that are important to security for machine learning, an analytical model giving a lower bound on attacker's work function, and a list of open problems.
Marco Barreno, Blaine Nelson, Russell Sears, Anthony D. Joseph, J. D. Tygar
AsiaCCS5
2006 Why phishing works
abstract
To build systems shielding users from fraudulent (or phishing) websites, designers need to know which attack strategies work and why. This paper provides the first empirical evidence about which malicious strategies are successful at deceiving general users. We first analyzed a large set of captured phishing attacks and developed a set of hypotheses about why these strategies might work. We then assessed these hypotheses with a usability study in which 22 participants were shown 20 web sites and asked to determine which ones were fraudulent. We found that 23% of the participants did not look at browser-based cues such as the address bar, status bar and the security indicators, leading to incorrect choices 40% of the time. We also found that some visual deception attacks can fool even the most sophisticated users. These results illustrate that standard security indicators are not effective for a substantial fraction of users, and suggest that alternative approaches are needed.
Rachna Dhamija, J. D. Tygar, Marti A. Hearst
CHI2
2005 Keyboard acoustic emanations revisited
abstract
We examine the problem of keyboard acoustic emanations. We present a novel attack taking as input a 10-minute sound recording of a user typing English text using a keyboard, and then recovering up to 96% of typed characters. There is no need for a labeled training recording. Moreover the recognizer bootstrapped this way can even recognize random text such as passwords: In our experiments, 90% of 5-character random passwords using only letters can be generated in fewer than 20 attempts by an adversary; 80% of 10-character passwords can be generated in fewer than 75 attempts. Our attack uses the statistical constraints of the underlying content, English language, to reconstruct text from sound recordings without any labeled training data. The attack uses a combination of standard machine learning and speech recognition techniques, including cepstrum features, Hidden Markov Models, linear classification, and feedback-based incremental learning.
Li Zhuang, J. D. Tygar
CCS3
2005 When Computer Security Crashes into Multimedia
abstract
Summary form only given. A casual glance on the Web, or in your local newspaper, quickly convinces a reader that the two of the hottest fields in computer science right now are computer security and multimedia. Unfortunately, these fields often seem at odds with each other. This talk takes two case studies and shows how the fields cause problems for each other. First, the author discusses how multimedia can cause problems for computer security. He shows how we are able to take recordings of a user typing at a keyboard and using only a generic $10 microphone and an assumption that the user is typing English, we can from the recording alone determine the text being typed with 96% accuracy. In fact, after training this system on English text, we can accurately recover passwords typed by the user. (This is joint work with L. Zhuang and F. Zhou (2005).) Second, he discusses how security can cause problems for multimedia. Taking the example of filtering for copyright protected content, the author discusses a variety of proposed schemes for restricting distribution of audio files. He concludes with an overview of other research areas where the fields computer security and multimedia jointly have significant contributions to make.
J. D. Tygar
ISM1
2005 The battle against phishing: Dynamic Security Skins
abstract
Phishing is a model problem for illustrating usability concerns of privacy and security because both system designers and attackers battle using user interfaces to guide (or misguide) users.We propose a new scheme, Dynamic Security Skins, that allows a remote web server to prove its identity in a way that is easy for a human user to verify and hard for an attacker to spoof. We describe the design of an extension to the Mozilla Firefox browser that implements this scheme.We present two novel interaction techniques to prevent spoofing. First, our browser extension provides a trusted window in the browser dedicated to username and password entry. We use a photographic image to create a trusted path between the user and this window to prevent spoofing of the window and of the text entry fields.Second, our scheme allows the remote server to generate a unique abstract image for each user and each transaction. This image creates a "skin" that automatically customizes the browser window or the user interface elements in the content of a remote web page. Our extension allows the user's browser to independently compute the image that it expects to receive from the server. To authenticate content from the server, the user can visually verify that the images match.We contrast our work with existing anti-phishing proposals. In contrast to other proposals, our scheme places a very low burden on the user in terms of effort, memory and time. To authenticate himself, the user has to recognize only one image and remember one low entropy password, no matter how many servers he wishes to interact with. To authenticate content from an authenticated server, the user only needs to perform one visual matching operation to compare two images. Furthermore, it places a high burden of effort on an attacker to spoof customized security indicators.
Rachna Dhamija, J. D. Tygar
SOUPS2
2004 Image Recognition CAPTCHAs
Monica Chew, J. D. Tygar
ISC2
2004 Distillation Codes and Applications to DoS Resistant Multicast Authentication
Chris Karlof, Naveen Sastry, Adrian Perrig, J. D. Tygar
NDSS5
2004 Side Effects Are Not Sufficient to Authenticate Software
Umesh Shankar, Monica Chew, J. D. Tygar
USENIX Security Symposium3
2002 Expander Graphs for Digital Stream Authentication and Robust Overlay Networks
abstract
We use expander graphs to provide efficient new constructions for two security applications: authentication of long digital streams over lossy networks and building scalable, robust overlay networks. Here is a summary of our contributions: (1) To authenticate long digital streams over lossy networks, we provide a construction with a provable lower bound on the ability to authenticate a packet - and that lower bound is independent of the size of the graph. To achieve this, we present an authentication expander graph with constant degree. (Previous work used authentication graphs but required graphs with degree linear in the number of vertices.) (2) To build efficient, robust, and scalable overlay networks, we provide a construction using undirected expander graphs with a provable lower bound on the ability of a broadcast message to successfully reach any receiver. This also gives us a new, more efficient solution to the decentralized certificate revocation problem.
Dawn Song, J. D. Tygar, David Zuckerman
S&P2
2002 SPINS: Security Protocols for Sensor Networks
Adrian Perrig, Robert Szewczyk, J. D. Tygar, Victor Wen, David E. Culler
Wirel. Networks3
2001 SAM: A Flexible and Secure Auction Architecture Using Trusted Hardware
abstract
Increasing numbers of economic transactions are conducted through on-line auctions. Nevertheless, most current auction implementations fail to address important security concerns. In particular, most auction systems force buyers and sellers to trust the auctioneer; alternative secure systems are inflexible and have a high computational and/or communication overhead. To overcome these limitations, we propose a secure auction marketplace (SAM) architecture, based on the recently available tool of high-performance, programmable secure coprocessors. Unlike previous schemes, this approach provides a general framework that can incorporate arbitrary auction schemes by using different evaluation programs, as well as provide complex security properties by using the secure coprocessor and our auction protocols. Our approach features strong security guarantees for the buyers and sellers without trusting the auctioneer, precise definition of the information disclosed during and after the auction, and high exibility to adapt to new types of auctions.
Adrian Perrig, Sean W. Smith, Dawn Song, J. D. Tygar
IPDPS4
2001 SPINS: security protocols for sensor netowrks
abstract
As sensor networks edge closer towards wide-spread deployment, security issues become a central concern. So far, much research has focused on making sensor networks feasible and useful, and has not concentrated on security.
Adrian Perrig, Robert Szewczyk, Victor Wen, David E. Culler, J. D. Tygar
MobiCom5
2001 Efficient and Secure Source Authentication for Multicast
Adrian Perrig, Ran Canetti, Dawn Song, J. D. Tygar
NDSS4
2001 ELK, A New Protocol for Efficient Large-Group Key Distribution
abstract
Secure media broadcast over the Internet poses unique security challenges. One problem is access control to a large number of subscribers in a public broadcast. A common solution is to encrypt the broadcast data and to disclose the decryption key to legitimate receivers only. However, how do we securely and efficiently establish a shared secret among the legitimate receivers? And most importantly, how can we efficiently update the group key securely if receivers join or leave? How can we provide reliability for key update messages in a way that scales up to large groups? Recent research makes substantial progress to address these challenges. Current schemes feature efficient key update mechanisms assuming that the key updates are communicated reliably to the receivers. In practice, however the principal impediment to achieve a scalable system is to distribute the key updates reliably to all receivers. We have designed and implemented ELK, a novel key distribution protocol, to address these challenges with the following features: ELK features perfectly reliable, super-efficient member joins; ELK uses smaller key update messages than previous protocols; ELK features a mechanism that allows short hint messages to be used for key recovery allowing a tradeoff of communication overhead with member computation; ELK proposes to append a small amount of key update information to data packets, such that the majority of receivers can recover from lost key update messages; and ELK allows to trade off security with communication overhead.
Adrian Perrig, Dawn Song, J. D. Tygar
S&P3
2000 Efficient Authentication and Signing of Multicast Streams over Lossy Channels
abstract
Multicast stream authentication and signing is an important and challenging problem. Applications include the continuous authentication of radio and TV Internet broadcasts, and authenticated data distribution by satellite. The main challenges are fourfold. First, authenticity must be guaranteed even when only the sender of the data is trusted. Second, the scheme needs to scale to potentially millions of receivers. Third, streamed media distribution can have high packet loss. Finally the system needs to be efficient to support fast packet rates. We propose two efficient schemes, TESLA and EMSS, for secure lossy multicast streams. TESLA (Timed Efficient Stream Loss-tolerant Authentication), offers sender authentication, strong loss robustness, high scalability and minimal overhead at the cost of loose initial time synchronization and slightly delayed authentication. EMSS (Efficient Multi-chained Stream Signature), provides nonrepudiation of origin, high loss resistance, and low overhead, at the cost of slightly delayed verification.
Adrian Perrig, Ran Canetti, J. D. Tygar, Dawn Song
S&P3
1999 Open Problems in Electronic Commerce
abstract
No abstract available.
J. D. Tygar
PODS1
1999 Why Johnny Can't Encrypt: A Usability Evaluation of PGP 5.0
Alma Whitten, J. D. Tygar
USENIX Security Symposium2
1998 Atomicity versus Anonymity: Distributed Transactions for Electronic Commerce
J. D. Tygar
VLDB1
1996 Atomicity in Electronic Commerce
abstract
Article Free Access Share on Atomicity in electronic commerce Author: J. D. Tygar Computer Science Department, Carnegie Mellon University, Pittsburgh, PA Computer Science Department, Carnegie Mellon University, Pittsburgh, PAView Profile Authors Info & Claims PODC '96: Proceedings of the fifteenth annual ACM symposium on Principles of distributed computingMay 1996 Pages 8–26https://doi.org/10.1145/248052.248054Online:01 May 1996Publication History 92citation932DownloadsMetricsTotal Citations92Total Downloads932Last 12 Months26Last 6 weeks7 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF
J. D. Tygar
PODC1
1996 A Model for Secure Protocols and Their Compositions
abstract
The paper develops a foundation for reasoning about protocol security. We adopt a model-based approach for defining protocol security properties. This allows us to describe security properties in greater detail and precision than previous frameworks. Our model allows us to reason about the security of protocols, and considers issues of beliefs of agents, time, and secrecy. We prove a composition theorem which allows us to state sufficient conditions on two secure protocols A and B such that they may be combined to form a new secure protocol C. Moreover, we give counter-examples to show that when the conditions are not met, the protocol C may not be secure.
Nevin Heintze, J. D. Tygar
IEEE Trans. Software Eng.2
1995 How are We Going to Pay for This? Fee-for-Service in Distributed Systems: Research and Policy Issues (Panel)
abstract
With the increasing array of information and services being supported by distributed computing, we face a new challenge: How do we handle charges? Providers of information will want to receive "royalties", providers of computing services will want to receive payment for use of the service, and providers of the network will want to receive payment for the transmission. At some point, the users of the provided services will have to pay for this. What do we need to do in designing our distributed computing systems to support some form of charge/payment? This paper discusses these issues.
Chris Clifton, Peter Gemmel, Ed Means, Matt J. Merges, J. D. Tygar
ICDCS5
1994 A model for secure protocols and their compositions
abstract
We give a formal model of protocol security. The model allows us to reason about the security of protocol, and considers issues of beliefs of agents, time, and secrecy. We prove a composition theorem which allows us to state sufficient conditions on two secure protocols A and B such that they may be combined to form a new secure protocol C. Moreover, we give counter-examples to show that when the conditions are not met, the protocol C may not be secure.>
Nevin Heintze, J. D. Tygar
S&P2
1994 Computability and Complexity of Ray Tracing
John H. Reif, J. D. Tygar, Akitoshi Yoshida
Discret. Comput. Geom.2
1993 Geometric characterization of series-parallel variable resistor networks
Randal E. Bryant, J. D. Tygar, Lawrence P. Huang
ISCAS2
1990 The Computability and Complexity of Optical Beam Tracing
abstract
The ray-tracing problem is considered for optical systems consisting of a set of refractive or reflective surfaces. It is assumed that the position and the tangent of the incident angle of the initial light ray are rational. The computability and complexity of the ray-tracing problems are investigated for various optical models. The results show that, depending on the optical model, ray tracing is sometimes undecidable, sometimes PSPACE-hard, and sometimes in PSPACE.>
John H. Reif, J. D. Tygar, Akitoshi Yoshida
FOCS2
1990 Miró: Visual Specification of Security
abstract
Miro is a set of languages and tools that support the visual specification of file system security. Two visual languages are presented: the instance language, which allows specification of file system access, and the constraint language, which allows specification of security policies. Miro visual languages and tools are used to specify security configurations. A visual language is one whose entities are graphical, such as boxes and arrows, specifying means stating independently of any implementation the desired properties of a system. Security means file system protection: ensuring that files are protected from unauthorized access and granting privileges to some users, but not others. Tools implemented and examples of how these languages can be applied to real security specification problems are described.>
Allan Heydon, Mark W. Maimone, J. D. Tygar, Jeannette M. Wing, Amy Moormann Zaremski
IEEE Trans. Software Eng.3
1988 Efficient Parallel Pseudorandom Number Generation
abstract
We present a parallel algorithm for pseudorandom number generation. Given a seed of $n^\varepsilon $ truly random bits for any $\varepsilon > 0$, our algorithm generates $n^c $ pseudorandom bits for any $c > 1$. This takes poly-log time using $n^{\varepsilon '} $ processors where $\varepsilon ' = k\varepsilon $ for some fixed small constant $k > 1$. We show that the pseudorandom bits output by our algorithm cannot be distinguished from truly random bits in parallel poly-log time using a polynomial number of processors with probability $\frac{1}{2} + {1 / {n^{O(1)} }}$ if the Multiplicative Inverse Problem almost always cannot be solved in ${\bf RNC}$. The proof is interesting and is quite different from previous proofs for sequential pseudorandom number generators. Our generator is fast and its output is provably as effective for ${\bf RNC}$ algorithms as truly random bits. Our generator passes all the statistical tests in Knuth [14]. Moreover, the existence of our generator has a number of central consequences for complexity theory. Given a randomized parallel algorithm $\mathcal{A}$ (over a wide class of machine models such as parallel RAMs and fixed connection networks) with time bound $T(n)$ and processor bound $P(n)$, we show that $\mathcal{A}$ can be simulated by a parallel algorithm with time bound $T(n) + O((\log n)(\log \log n))$, processor bound $P(n)n^{\varepsilon '} $, and only using $n^\varepsilon $ truly random bits for any $\varepsilon > 0$. Also, we show that if the Multiplicative Inverse Problem is almost always not in ${\bf RNC}$, the ${\bf RNC}$ is within the class of languages accepted by uniform poly-log depth circuits with unbounded fan-in and strictly subexponential size $ \cap _{\varepsilon > 0} 2^{n^\varepsilon } $ .
John H. Reif, J. D. Tygar
SIAM J. Comput.2
1987 How to Make Replicated Data Secure
Maurice Herlihy, J. D. Tygar
CRYPTO2
1985 Efficient Parallel Pseudo-Random Number Generation
John H. Reif, J. D. Tygar
CRYPTO2
1985 Efficient netlist comparison using hierarchy and randomization
abstract
Programs to compare the layout of ICs with their schematics have recently appeared. These programs have limited functionality and require large amounts of CPU time. We discuss the implementation of a fast [Ο(n(log n)2)] logic comparison algorithm which uses hierarchy and randomization. This algorithm handles swappable components without performance degradation and is extremely robust in the presence of input errors. We include experimental data.
J. D. Tygar, Ron Ellickson
DAC1