In both the commercial and defense sectors a compelling need is emerging for highly dynamic, yet risk optimized, sharing of information across traditional organizational boundaries. Risk optimal decisions to disseminate mission critical tactical intelligence information to the pertinent actors in a timely manner is critical for a mission's success. In this paper1, we argue that traditionally decision support mechanisms for information sharing (such as Multi-Level Security (MLS)) besides being rigid and situation agnostic, do not offer explanations and diagnostics for non-shareability. This paper exploits rich security metadata and semantic knowledgebase that captures domain specific concepts and relationships to build a logic for risk optimized information sharing. We show that the proposed approach is: (i) flexible: e.g., sensitivity of tactical information decays with space, time and external events, (ii) situation-aware: e.g., encodes need-to-know based access control policies, and more importantly (iii) supports explanations for non-shareability; these explanations in conjunction with rich security metadata and domain ontology allows a sender to intelligently transform information (e.g., downgrade information, say, by deleting participant list in a meeting) with the goal of making transformed information shareable with the recipient. In this paper, we will describe an architecture for secure information sharing using a publicly available hybrid semantic reasoner and present several illustrative examples that highlight the benefits of our proposal over traditional approaches.

Role-based provisioning has been adopted as a standard component in leading Identity Management products due to its low administration cost. However, the cost of adjusting existing roles to entitlements from newly deployed applications is usually very high. In this paper, a learning-based approach to automate the provisioning process is proposed and its effectiveness is verified by real provisioning data. Specific learning issues related to provisioning are identified and relevant solutions are presented.

In both the commercial and defence sectors a compelling need is emerging for the rapid, yet secure, dissemination of information across traditional organisational boundaries. In this paper we present a novel trust management paradigm for securing pan-organisational information flows that aims to address the threat of information leakage. Our trust management system is built around an economic model and a trust-based encryption primitive wherein: (i) entities purchase a key from a Trust Authority (TA) which is bound to a voluntarily reported trust score r, (ii) information flows are encrypted such that a flow tagged with a recipient trust score R can be decrypted by the recipient only if it possesses the key corresponding to a voluntarily reported score r < = R, (iii) the economic model (the price of keys) is set such that a dishonest entity wishing to maximise information leakage is incentivised to report an honest trust score r to the TA. This paper makes two important contributions. First, we quantify fundamental tradeoffs on information flow rate, information leakage rate and error in estimating recipient trust score R. Second, we present a suite of encryption schemes that realise our trust-based encryption primitive and identify computation and communication tradeoffs between them.

In the early days a policy was a set of simple rules with a clear intuitive motivation that could be formalised to good effect. However the world is now much more complex. Subtle risk decisions may often need to be made and people are not always adept at expressing rationale for what they do. Previous research has demonstrated that Genetic Programming can be used to infer statements of policies from examples of decisions made [1]. This allows a policy that may not formally have been documented to be discovered automatically, or an underlying set of requirements to be extracted by interpreting user decisions to posed ldquowhat ifrdquo scenarios. This study compares the performance of three different approaches in using genetic programming to infer security policies from decision examples made, namely symbolic regression, IF-THEN rules inference and fuzzy membership functions inference. The fuzzy membership functions inference approach is found to have the best performance in terms of accuracy. Also, the fuzzification and de-fuzzification methods are found to be strongly correlated; incompatibility between them can have strong negative impact to the performance.

In the early days a policy was a set of simple rules with a clear intuitive motivation that could be formalised to good effect. However the world is becoming much more complex. Subtle risk decisions may often need to be made and people are not always adept at expressing rationale for what they do. In this paper we investigate how policies can be inferred automatically using Genetic Programming (GP) from examples of decisions made. This allows us to discover a policy that may not formally have been documented, or else extract an underlying set of requirements by interpreting user decisions to posed "what if" scenarios. Three proof of concept experiments on MLS Bell-LaPadula, Budgetised MLS and Fuzzy MLS policies have been carried out. The results show this approach is promising.

Recently, risk-based information trading has emerged as a new paradigm for securely sharing information across traditional organizational boundaries. In this paradigm, the risk of sharing information between organizations is characterized using expected losses (due, for example, to (un)intended information disclosure) and billed to a recipient. However, within risk-based information trading systems, quantifying the risks associated with sharing information is a non-trivial task, particularly when risk calculations depend on a number of factors. In this paper we introduce a data-centric metadata framework that extends risk-based information trading approaches by allowing one or more domains to exchange sensitive information based on metadata evaluated against internal risk assessments of the domains. We present a use case of our metadata framework using a coalition military scenario, wherein information flows can be controlled and regulated by our framework whilst allowing sufficiently high-quality tactical information to be disseminated.

With the increasing need to securely share information, current access control systems are proving too in flexible and difficult to adapt. Recent work on risk-based access control systems has shown promise at resolving the inadequacies of traditional access control systems, and promise to increase information sharing and security. We consider some of the core open problems in risk-based access control systems, namely where and how much risk to take. We propose the use of market mechanisms to determine an organization's risk tolerance and allocation. We show that with the correct incentives, an employee will make optimal choices for the organization. We also comment on how the market can be used to ensure employees behave honestly and detect those who are malicious. Through simulations, we empirically show the advantage of risk-based access control systems and market mechanisms at increasing information sharing and security.

Hardware manufacturers are increasingly outsourcing their IC fabrication work overseas due to their much lower cost structure. This poses a significant security risk for ICs used for critical military and business applications. Attackers can exploit this loss of control to substitute Trojan ICs for genuine ones or insert a Trojan circuit into the design or mask used for fabrication. We show that a technique borrowed from side-channel cryptanalysis can be used to mitigate this problem. Our approach uses noise modeling to construct a set of fingerprints/or an IC family utilizing side- channel information such as power, temperature, and electromagnetic (EM) profiles. The set of fingerprints can be developed using a few ICs from a batch and only these ICs would have to be invasively tested to ensure that they were all authentic. The remaining ICs are verified using statistical tests against the fingerprints. We describe the theoretical framework and present preliminary experimental results to show that this approach is viable by presenting results obtained by using power simulations performed on representative circuits with several different Trojan circuitry. These results show that Trojans that are 3-4 orders of magnitude smaller than the main circuit can be detected by signal processing techniques. While scaling our technique to detect even smaller Trojans in complex ICs with tens or hundreds of millions of transistors would require certain modifications to the IC design process, our results provide a starting point to address this important problem.

This paper presents a new model for, or rather a new way of thinking about adaptive, risk-based access control. Our basic premise is that there is always inherent uncertainty and risk in access control decisions that is best addressed in an explicit way. We illustrate this concept by showing how the rationale of the well-known, Bell-Lapadula model based, multi-level security (MLS) access control model could be used to develop a risk-adaptive access control model. This new model is more like a fuzzy logic control system than a traditional access control system and hence the name "fuzzy MLS". The long version of this paper is published as an IBM Research Report.

In this paper, we introduce a new class of side-channel attacks called partitioning attacks. We have successfully launched a version of the attack on several implementations of COMP128, the popular GSM authentication algorithm that has been deployed by different service providers in several types of SIM cards, to retrieve the 128 bit key using as few as 8 chosen plaintexts. We show how partitioning attacks can be used effectively to attack implementations that have been equipped with ad hoc and inadequate countermeasures against side-channel attacks. Such ad hoc countermeasures are systemic in implementations of cryptographic algorithms, such as COMP128, which require the use of large tables since there has been a mistaken belief that sound countermeasures require more resources than are available. To address this problem, we describe a new resource-efficient countermeasure for protecting table lookups in cryptographic implementations and justify its correctness rigorously.

Given two n × n Boolean matrices A and B, their Boolean Product Witness Matrix (BPWM) is an n × n integer matrix W with wij = some k such that aik = bkj = 1, (1 ≤ i, j, k ≤ n) and wij = 0 if no such k exists. The best known algorithms to date for solving the BPWM problem have a worst-case complexity of O(nω log n), where O(nω) is the time required to multiply two n × n integer matrices. The theoretically best known value of ω is 2.376, but is higher for algorithms that are practical to implement for reasonable problem sizes. In this paper, we present a relatively simple and practical randomized algorithm for solving the BPWM problem. The expected completion time of our algorithms is O(n2 log n) for a large class of Boolean matrices, including but not limited to all mutually-independent matrices. We show that the probability of the algorithm requiring more than O(n2 log n) is vanishingly small for most input Boolean matrices, irrespective of the density of 1's or 0's in them.

This paper proposes a compact and fast hybrid signature scheme that can be used to solve the problem of packet source authentication for multicast. This scheme can be viewed as an improvement to off-line/on-line signature schemes, in that the signature size overhead is much smaller. Since this is a generic technique, it should have applications to several other practical problems as well.

In this paper, we study the notion of completeness under random reductions and explore how that depends on the type and success probability of the reduction. We obtain absolute separations between completeness notions under various random reductions and between random reductions and deterministic reductions. These separations are obtained in appropriately high complexity classes where these questions do not have contradictory relativizations. Our results show that the notion of completeness under random reductions is sensitive tovery smallchanges in success probability, since we can separate completeness under reductions with very small differ- ences in success probability. We also obtain optimal separations between completeness under various deterministic reductions and random reductions.

The research presented in this paper is motivated by the some new results on the complexity of the unique satisfiability problem, USAT. These results, which are shown for the first time in the paper, are: if USAT ≡ , then D = co-D and PH collapses. if USAT ∈ co-D, then PH collapses. if USAT has OR, then PH collapses.

In this paper, we investigate the power of randomness to save a query to an NP-complete set. We show that the PSAT ∥ [k] ≤pm-complete language randomly reduces to a language in PSAT ∥ [k − 1] with a one-sided error probability of 1/⌈k/2⌉ or a two sided-error probability of 1/(k+1). Furthermore, we prove that these probability bounds are tight; i.e., they cannot be improved by 1/poly, unless PH collapses. We also obtain tight performance bounds for randomized reductions between nearby classes in the Boolean and bounded query hierarchies. These bounds provide probability thresholds for completeness under randomized reductions in these classes. Using these thresholds, we show that certain languages in the Boolean hierarchy which are not ≤pm-complete in some relativized worlds, nevertheless inherit many of the hardness properties associated with the ≤pm-complete languages. Finally, we explore the relationship between randomization and functions that are computable using bounded queries to SAT. For any function h(n) = O(log n), we show that there is a function f computable using h(n) nonadaptive queries to SAT, which cannot be computed correctly with probability 1/2 + 1/poly by any randomized machine which makes less than h(n) adaptive queries to any oracle, unless PH collapses.

In this paper, we precisely characterize the randomness complexity of the unique element isolation problem, a crucial step in the $RNC$ algorithm for perfect matching by Mulmuley, Vazirani, and Vazirani [Combinatorica, 7 (1987), pp. 105–113] and in several other applications. Given a set S and an unknown family $\mathcal{F} \subseteq 2^{S}$ with $|\mathcal{F}| \leq Z$, we present a scheme for assigning polynomially bounded weights to the elements of S using only $O(\log Z + \log |S|)$ random bits, such that the minimum weight set in $\mathcal{F}$ is unique with high probability. This generalizes the solution of Mulmuley, Vazirani, and Vazirani, who use $O(S \log S)$ bits, independent of Z. We also provide a matching lower bound for the randomness complexity of this problem. The new weight assignment scheme yields a randomness-efficient $RNC^{2}$ algorithm for perfect matching which uses $O(\log Z + \log n)$ random bits, where Z is any given upper bound on the number of perfect matchings in the input graph. This generalizes the result of Grigoriev and Karpinski [Proc. IEEE Symposium on Foundations of computer Science, 1987, pp. 166–172], who present an $NC^{3}$ algorithm when Z is polynomial and improves the running time in this case. The worst-case randomness complexity of our algorithm is $O(n \log (m/n))$ random bits improving on the previous bound of $O(m \log n)$. Our scheme also gives randomness-efficient solutions for several problems where unique element isolation is used, such as $RNC$ algorithms for variants of matching and basic problems on linear matroids. We obtain a randomness-efficient random reduction from SAT to USAT, the language of uniquely satisfiable formulas, which can be derandomized in the case of languages in Few P to yield new proofs of the results Few $P \subseteq \oplus P$ and Few $P \subseteq C_{=} P$.

Article Improved algorithms via approximations of probability distributions (extended abstract) Share on Authors: Suresh Chari Dept. of Computer Science, Cornell University, Ithaca NY Dept. of Computer Science, Cornell University, Ithaca NYView Profile , Pankaj Rohatgi Thompson Consumer Electronics, Los Angeles, CA Thompson Consumer Electronics, Los Angeles, CAView Profile , Aravind Srinivasan DIMACS Center, Rutgers University, Piscataway, NJ, and School of Mathematics, The Institute for Advanced Study, Princeton, NJ DIMACS Center, Rutgers University, Piscataway, NJ, and School of Mathematics, The Institute for Advanced Study, Princeton, NJView Profile Authors Info & Claims STOC '94: Proceedings of the twenty-sixth annual ACM symposium on Theory of ComputingMay 1994 Pages 584–592https://doi.org/10.1145/195058.195411Published:23 May 1994 9citation251DownloadsMetricsTotal Citations9Total Downloads251Last 12 Months2Last 6 weeks0 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 SiteGet Access

The Random Oracle Hypothesis, attributed to Bennett and Gill, essentially states that the relationships between complexity classes which hold for almost all relativized worlds must also hold in the unrelativized case. Although this paper is not the first to provide a counterexample to the Random Oracle Hypothesis, it does provide a most compelling counterexample by showing that for almost all oracles A, IPA ≠ PSPACEA. If the Random Oracle Hypothesis were true, it would contradict Shamir's result that IP = PSPACE. In fact, it is shown that for almost all oracles A, co-NPA ⫋ IPA. These results extend to the multiprover proof systems of Ben-Or, Goldwasser, Killian, and Wigderson. In addition, this paper shows that the Random Oracle Hypothesis is sensitive to small changes in the definition. A class IPP, similar to IP, is defined. Surprisingly, the IPP = PSPACE result holds for all oracle worlds.

In this paper, we precisely characterize the randomness complexity of the unique element isolation problem, a crucial step in the RNC algorithm for perfect matching due to Mulmuleg, Va.zirani @ Vazirani and in several other applications.Given a set S and an unknown family F ~2s with \F~< Z, we present a scheme to assign polynomially bounded weights to the elements of S using onlg O(log Z + log ISI) random bits, such that the minimum weight set in F is unique with high probability.This generalizes and improves the results of Mulmuley, Vazirani & Va.zirani who give a scheme which uses 0(S log S) random bits independent of Z.We also prove a matching lower bound for the randomness complezitp of this problem.OUT generalization gives a randomness-e ficient RNC2 algorithm for perfect matching which uses O(log Z -t-log n) random bits where Z is any given upper bound on the number of perfect matchings in the given graph.This improves and generalizes the results of Grigoriev & Karpinski who present an NC3 algorithm when Z is polynomially bounded.The