12958677
A Construction for General and Efficient Oblivious Commitment Based Envelope Protocols
The notion of Oblivious Commitment Based Envelope (OCBE) was recently proposed; it enables attribute-based access control without revealing any information about the attributes. Previous OCBE protocols are designed by taking zero-knowledge proof protocols that prove a committed value satisfies some property and changing the protocols so that instead of one party proving to the other party, the two parties compute two keys that agree if and only if the committed value indeed satisfy the property. In this paper, we introduce a more general approach for designing OCBE protocols that uses zero-knowledge proof protocols in a black-box fashion. We present a construction such that given a zero-knowledge proof protocol that proves a committed value satisfies a predicate, we have an OCBE protocol for that predicate with constant additional cost. Compared with previous OCBE protocols, our construction is more general, more efficient, and has wide applicability.
9481657
Private collaborative forecasting and benchmarking
Suppose a number of hospitals in a geographic area want to learn how their own heart-surgery unit is doing compared with the others in terms of mortality rates, subsequent complications, or any other quality metric. Similarly, a number of small businesses might want to use their recent point-of-sales data to cooperatively forecast future demand and thus make more informed decisions about inventory, capacity, employment, etc. These are simple examples of cooperative benchmarking and (respectively) forecasting that would benefit all participants as well as the public at large, as they would make it possible for participants to avail themselves of more precise and reliable data collected from many sources, to assess their own local performance in comparison to global trends, and to avoid many of the inefficiencies that currently arise because of having less information available for their decision-making. And yet, in spite of all these advantages, cooperative benchmarking and forecasting typically do not take place, because of the participants' unwillingness to share their information with others. Their reluctance to share is quite rational, and is due to fears of embarrassment, lawsuits, weakening their negotiating position (e.g., in case of over-capacity), revealing corporate performance and strategies, etc. The development and deployment of <i>private</i> benchmarking and forecasting technologies would allow such collaborations to take place without revealing any participant's data to the others, reaping the benefits of collaboration while avoiding the drawbacks. Moreover, this kind of technology would empower smaller organizations who could then cooperatively base their decisions on a much broader information base, in a way that is today restricted to only the largest corporations. This paper is a step towards this goal, as it gives protocols for forecasting and benchmarking that reveal to the participants the desired answers yet do not reveal to any participant any other participant's private data. We consider several forecasting methods, including linear regression and time series techniques such as moving average and exponential smoothing. One of the novel parts of this work, that further distinguishes it from previous work in secure multi-party computation, is that it involves floating point arithmetic, in particular it provides protocols to securely and efficiently perform division.
7496680
Automated trust negotiation using cryptographic credentials
In automated trust negotiation (ATN), two parties exchange digitally signed credentials that contain attribute information to establish trust and make access control decisions. Because the information in question is often sensitive, credentials are protected according to access control policies. In traditional ATN, credentials are transmitted either in their entirety or not at all. This approach can at times fail unnecessarily, either because a cyclic dependency makes neither negotiator willing to reveal her credential before her opponent, because the opponent must be authorized for all attributes packaged together in a credential to receive any of them, or because it is necessary to fully disclose exact attribute values, rather than merely proving they satisfy some predicate (such as being over 21 years of age). Recently, several cryptographic credential schemes and associated protocols have been developed to address these and other problems. However, they can be used only as fragments of an ATN process. This paper introduces a framework for ATN in which the diverse credential schemes and protocols can be combined, integrated, and used as needed. A policy language is introduced that enables negotiators to specify authorization requirements that must be met by an opponent to receive various amounts of information about certified attributes and the credentials that contain it. The language also supports the use of uncertified attributes, allowing them to be required as part of policy satisfaction, and to place their (automatic) disclosure under policy control.
62613535
OACerts: Oblivious Attribute Certificates
We propose oblivious attribute certificates (OACerts), an attribute certificate scheme in which a certificate holder can select which attributes to use and how to use them. In particular, a user can use attribute values stored in an OACert obliviously, i.e., the user obtains a service if and only if the attribute values satisfy the policy of the service provider, yet the service provider learns nothing about these attribute values. This way, the service provider's access control policy is enforced in an oblivious fashion. To enable the oblivious access control using OACerts, we propose a new cryptographic primitive called oblivious commitment-based envelope (OCBE). In an OCBE scheme, Bob has an attribute value committed to Alice and Alice runs a protocol with Bob to send an envelope (encrypted message) to Bob such that: 1) Bob can open the envelope if and only if his committed attribute value satisfies a predicate chosen by Alice and 2) Alice learns nothing about Bob's attribute value. We develop provably secure and efficient OCBE protocols for the Pedersen commitment scheme and comparison predicates as well as logical combinations of them
16974710
Trust Negotiation with Hidden Credentials, Hidden Policies, and Policy Cycles
In an open environment such as the Internet, the decision to collaborate with a stranger (e.g., by granting access to a resource) is often based on the characteristics (rather than the identity) of the requester, via digital credentials: Access is granted if Alice’s credentials satisfy Bob’s access policy. The literature contains many examples where protecting the credentials and the access control policies is useful, and there are numerous protocols that achieve this. In many of these schemes, the server does not learn whether the client obtained access (e.g., to a message, or a service via an eticket). A consequence of this property is that the client can use all of her credentials without fear of “probing” attacks by the server, because the server cannot glean information about which credentials the client has (when this property is lacking, the literature uses a framework where the very use of a credential is subject to a policy specific to that credential). The main result of this paper is a protocol for negotiating trust between Alice and Bob without revealing either credentials or policies, when each credential has its own access policy associated with it (e.g., “a top-secret clearance credential can only be used when the other party is a government employee and has a top-secret clearance”). Our protocol carries out this privacy-preserving trust negotiation between Alice and Bob, while enforcing each credential’s policy (thereby protecting sensitive credentials). Note that there can be a deep nesting of dependencies between credential policies, and that there can be (possibly overlapping) policy cycles of these dependencies. Our result is not achieved through the routine use of standard techniques to implement, in this framework, one of the known strategies for trust negotiations (such as the “eager strategy”). Rather, this paper uses novel techniques to implement a non-standard trust negotiation strategy specifically suited to this framework (and in fact unusable outside of this framework, as will become clear). Our work is therefore Portions of this work were supported by Grants IIS-0325345, IIS0219560, IIS-0312357, and IIS-0242421 from the National Science Foundation, Contract N00014-02-1-0364 from the Office of Naval Research, by sponsors of the Center for Education and Research in Information Assurance and Security, and by Purdue Discovery Park’s e-enterprise Center. a substantial extension of the state-of-the-art in privacypreserving trust negotiations.
1305393
Universal Accumulators with Efficient Nonmembership Proofs
Based on the notion of accumulators, we propose a new cryptographic scheme called universal accumulators. This scheme enables one to commit to a set of values using a short accumulator and to efficiently compute a membership witness of any value that has been accumulated. Unlike traditional accumulators, this scheme also enables one to efficiently compute a nonmembership witness of any value that has not been accumulated. We give a construction for universal accumulators and prove its security based on the strong RSA assumption. We further present a construction for dynamic universal accumulators; this construction allows one to dynamically add and delete inputs with constant computational cost. Our construction directly builds upon Camenisch and Lysyanskaya's dynamic accumulator scheme. Universal accumulators can be seen as an extension to dynamic accumulators with support of nonmembership witness. We also give an efficient zero-knowledge proof protocol for proving that a committed value is not in the accumulator. Our dynamic universal accumulator construction enables efficient membership revocation in an anonymous fashion.
1613791
Relative risk and odds ratio: a data mining perspective
We are often interested to test whether a given cause has a given effect. If we cannot specify the nature of the factors involved, such tests are called model-free studies. There are two major strategies to demonstrate associations between risk factors (ie. patterns) and outcome phenotypes (ie. class labels). The first is that of prospective study designs, and the analysis is based on the concept of "relative risk": What fraction of the exposed (ie. has the pattern) or unexposed (ie. lacks the pattern) individuals have the phenotype (ie. the class label)? The second is that of retrospective designs, and the analysis is based on the concept of "odds ratio": The odds that a case has been exposed to a risk factor is compared to the odds for a case that has not been exposed. The efficient extraction of patterns that have good relative risk and/or odds ratio has not been previously studied in the data mining context. In this paper, we investigate such patterns. We show that this pattern space can be systematically stratified into plateaus of convex spaces based on their support levels. Exploiting convexity, we formulate a number of sound and complete algorithms to extract the most general and the most specific of such patterns at each support level. We compare these algorithms. We further demonstrate that the most efficient among these algorithms is able to mine these sophisticated patterns at a speed comparable to that of mining frequent closed patterns, which are patterns that satisfy considerably simpler conditions.
36212113
Independent triangles covering given vertices of a graph
Let G be a simple graph of order n, k a positive integer with n≥3k and X a set of any k vertices of G. We show that if the minimum degree G)≥(n + k)=2, then G contains k independent triangles covering all vertices of X ; and if the minimum degree (G)≥(n+2k)=2, then G contains k independent triangles such that each triangle contains exactly one vertex of X . The bounds on the minimum degree of G in above results are sharp. Some conjectures about independent triangles covering some given vertices are proposed.
42687859
An intrinsic evolvable and online adaptive evolvable fuzzy hardware scheme for packet switching network
Most published works usually focused on extrinsic evolvable hardware (EHW), and in some instances, intrinsic but offline adaptive EHW. In this paper, we describe an intrinsic evolvable and online adaptive EHW to solve packet switching problem. Based on the coding and evolution scheme, we refer to it as evolvable fuzzy hardware (EFH), an extension of our proposed evolvable fuzzy system (EFS) by Li and Lim (2003) and reconfigurable fuzzy inference chip (RFIC) by Cao et. al. EFH is a good framework for intrinsic evolvability and online adaptation.
899
Improved Squeaky Wheel Optimisation for Driver Scheduling
This paper presents a technique called Improved Squeaky Wheel Optimisation (ISWO) for driver scheduling problems. It improves the original Squeaky Wheel Optimisation's (SWO) effectiveness and execution speed by incorporating two additional steps of Selection and Mutation which implement evolution within a single solution. In the ISWO, a cycle of Analysis-Selection-Mutation-Prioritization-Construction continues until stopping conditions are reached. The Analysis step first computes the fitness of a current solution to identify troublesome components. The Selection step then discards these troublesome components probabilistically by using the fitness measure, and the Mutation step follows to further discard a small number of components at random. After the above steps, an input solution becomes partial and thus the resulting partial solution needs to be repaired. The repair is carried out by using the Prioritization step to first produce priorities that determine an order by which the following Construction step then schedules the remaining components. Therefore, the optimisation in the ISWO is achieved by solution disruption, iterative improvement and an iterative constructive repair process performed. Encouraging experimental results are reported.
14911022
FIRM: fuzzily integrated region matching for content-based image retrieval
We propose FIRM (Fuzzily Integrated Region Matching), an efficient and robust similarity measure for region-based image retrieval. Each image in our retrieval system is represented by a set of regions that are characterized by fuzzy sets. The FIRM measure, representing the overall similarity between two images, is defined as the similarity between two families of fuzzy sets. Compared with similarity measures based on individual regions and on all regions with crisp feature representations, our approach greatly reduces the influence of inaccurate segmentation. Experimental results based on a database of about 200,000 general-purpose images demonstrate improved accuracy, robustness, and high speed.