Functional encryption for threshold functions (or fuzzy IBE) from lattices

Cryptosystems based on the hardness of lattice problems have recently acquired much importance due to their average-case to worst-case equivalence, their conjectured resistance to quantum cryptanalysis, their ease of implementation and increasing practicality, and, lately, their promising potential as a platform for constructing advanced functionalities. In this work, we construct “Fuzzy” Identity Based Encryption from the hardness of the Learning With Errors (LWE) problem. We note that for our parameters, the underlying lattice problems (such as gapSVP or SIVP) are assumed to be hard to approximate within supexponential factors for adversaries running in subexponential time. We give CPA and CCA secure variants of our construction, for small and large universes of attributes. All our constructions are secure against selective-identity attacks in the standard model. Our construction is made possible by observing certain special properties that secret sharing schemes need to satisfy in order to be useful for Fuzzy IBE. We also discuss some obstacles towards realizing lattice-based attribute-based encryption (ABE).

Testing threshold functions using implied minterm structure

A geometrical structure called the implied minterm structure (IMS) has been developed from the properties of minterms of a threshold function. The IMS is useful for the manual testing of linear separability of switching functions of up to six variables. This testing is done just by inspection of the plot of the function on the IMS.

Karnaugh map analysis and synthesis of threshold functions

A unate function can easily be identified on a Karnaugh map from the well-known property that it cons ist s only ofess en ti al prime implicante which intersect at a common implicant. The additional property that the plot of a unate function F(x, ... XII) on a Karnaugh map should possess in order that F may also be Ivrealizable (n';:; 6) has been found. It has been sh own that the I- realizability of a unate function F corresponds to the ' compac tness' of the plot of F. No resort to tho inequalities is made, and no pre-processing such as positivizing and ordering of the given function is required.

Enumeration of threshold functions of eight variables,

Bibliography: p. 58-59.

Major and minor threshold functions of six variables /

Issued also as thesis (M.S.) University of Illinois.

Time and Energy Complexity of Distributed Computation of a Class of Functions in Wireless Sensor Networks

We consider a scenario in which a wireless sensor network is formed by randomly deploying n sensors to measure some spatial function over a field, with the objective of computing a function of the measurements and communicating it to an operator station. We restrict ourselves to the class of type-threshold functions (as defined in the work of Giridhar and Kumar, 2005), of which max, min, and indicator functions are important examples: our discussions are couched in terms of the max function. We view the problem as one of message-passing distributed computation over a geometric random graph. The network is assumed to be synchronous, and the sensors synchronously measure values and then collaborate to compute and deliver the function computed with these values to the operator station. Computation algorithms differ in (1) the communication topology assumed and (2) the messages that the nodes need to exchange in order to carry out the computation. The focus of our paper is to establish (in probability) scaling laws for the time and energy complexity of the distributed function computation over random wireless networks, under the assumption of centralized contention-free scheduling of packet transmissions. First, without any constraint on the computation algorithm, we establish scaling laws for the computation time and energy expenditure for one-time maximum computation. We show that for an optimal algorithm, the computation time and energy expenditure scale, respectively, as Theta(radicn/log n) and Theta(n) asymptotically as the number of sensors n rarr infin. Second, we analyze the performance of three specific computation algorithms that may be used in specific practical situations, namely, the tree algorithm, multihop transmission, and the Ripple algorithm (a type of gossip algorithm), and obtain scaling laws for the computation time and energy expenditure as n rarr infin. In particular, we show that the computation time for these algorithms scales as Theta(radicn/lo- g n), Theta(n), and Theta(radicn log n), respectively, whereas the energy expended scales as , Theta(n), Theta(radicn/log n), and Theta(radicn log n), respectively. Finally, simulation results are provided to show that our analysis indeed captures the correct scaling. The simulations also yield estimates of the constant multipliers in the scaling laws. Our analyses throughout assume a centralized optimal scheduler, and hence, our results can be viewed as providing bounds for the performance with practical distributed schedulers.

Exotic dynamics in a firing rate model of neural tissue with threshold accommodation

Many of the equations describing the dynamics of neural systems are written in terms of firing rate functions, which themselves are often taken to be threshold functions of synaptic activity. Dating back to work by Hill in 1936 it has been recognized that more realistic models of neural tissue can be obtained with the introduction of state-dependent dynamic thresholds. In this paper we treat a specific phenomenological model of threshold accommodation that mimics many of the properties originally described by Hill. Importantly we explore the consequences of this dynamic threshold at the tissue level, by modifying a standard neural field model of Wilson-Cowan type. As in the case without threshold accommodation classical Mexican-Hat connectivity is shown to allow for the existence of spatially localized states (bumps) in both one and two dimensions. Importantly an analysis of bump stability in one dimension, using recent Evans function techniques, shows that bumps may undergo instabilities leading to the emergence of both breathers and traveling waves. Moreover, a similar analysis for traveling pulses leads to the conditions necessary to observe a stable traveling breather. In the regime where a bump solution does not exist direct numerical simulations show the possibility of self-replicating bumps via a form of bump splitting. Simulations in two space dimensions show analogous localized and traveling solutions to those seen in one dimension. Indeed dynamical behavior in this neural model appears reminiscent of that seen in other dissipative systems that support localized structures, and in particular those of coupled cubic complex Ginzburg-Landau equations. Further numerical explorations illustrate that the traveling pulses in this model exhibit particle like properties, similar to those of dispersive solitons observed in some three component reaction-diffusion systems. A preliminary account of this work first appeared in S Coombes and M R Owen, Bumps, breathers, and waves in a neural network with spike frequency adaptation, Physical Review Letters 94 (2005), 148102(1-4).

Asymmetric Ramsey Properties of Random Graphs Involving Cliques

Consider the following problem: Forgiven graphs G and F(1),..., F(k), find a coloring of the edges of G with k colors such that G does not contain F; in color i. Rodl and Rucinski studied this problem for the random graph G,,, in the symmetric case when k is fixed and F(1) = ... = F(k) = F. They proved that such a coloring exists asymptotically almost surely (a.a.s.) provided that p <= bn(-beta) for some constants b = b(F,k) and beta = beta(F). This result is essentially best possible because for p >= Bn(-beta), where B = B(F, k) is a large constant, such an edge-coloring does not exist. Kohayakawa and Kreuter conjectured a threshold function n(-beta(F1,..., Fk)) for arbitrary F(1), ..., F(k). In this article we address the case when F(1),..., F(k) are cliques of different sizes and propose an algorithm that a.a.s. finds a valid k-edge-coloring of G(n,p) with p <= bn(-beta) for some constant b = b(F(1),..., F(k)), where beta = beta(F(1),..., F(k)) as conjectured. With a few exceptions, this algorithm also works in the general symmetric case. We also show that there exists a constant B = B(F,,..., Fk) such that for p >= Bn(-beta) the random graph G(n,p) a.a.s. does not have a valid k-edge-coloring provided the so-called KLR-conjecture holds. (C) 2008 Wiley Periodicals, Inc. Random Struct. Alg., 34, 419-453, 2009

Contrast discrimination and pattern masking: contrast gain control with fixed additive noise

We studied the visual mechanisms that serve to encode spatial contrast at threshold and supra-threshold levels. In a 2AFC contrast-discrimination task, observers had to detect the presence of a vertical 1 cycle deg-1 test grating (of contrast dc) that was superimposed on a similar vertical 1 cycle deg-1 pedestal grating, whereas in pattern masking the test grating was accompanied by a very different masking grating (horizontal 1 cycle deg-1, or oblique 3 cycles deg-1). When expressed as threshold contrast (dc at 75% correct) versus mask contrast (c) our results confirm previous ones in showing a characteristic 'dipper function' for contrast discrimination but a smoothly increasing threshold for pattern masking. However, fresh insight is gained by analysing and modelling performance (p; percent correct) as a joint function of (c, dc) - the performance surface. In contrast discrimination, psychometric functions (p versus logdc) are markedly less steep when c is above threshold, but in pattern masking this reduction of slope did not occur. We explored a standard gain-control model with six free parameters. Three parameters control the contrast response of the detection mechanism and one parameter weights the mask contrast in the cross-channel suppression effect. We assume that signal-detection performance (d') is limited by additive noise of constant variance. Noise level and lapse rate are also fitted parameters of the model. We show that this model accounts very accurately for the whole performance surface in both types of masking, and thus explains the threshold functions and the pattern of variation in psychometric slopes. The cross-channel weight is about 0.20. The model shows that the mechanism response to contrast increment (dc) is linearised by the presence of pedestal contrasts but remains nonlinear in pattern masking.

Verifiable multi-secret sharing schemes for multiple threshold access structures

A multi-secret sharing scheme allows several secrets to be shared amongst a group of participants. In 2005, Shao and Cao developed a verifiable multi-secret sharing scheme where each participant’s share can be used several times which reduces the number of interactions between the dealer and the group members. In addition some secrets may require a higher security level than others involving the need for different threshold values. Recently Chan and Chang designed such a scheme but their construction only allows a single secret to be shared per threshold value. In this article we combine the previous two approaches to design a multiple time verifiable multi-secret sharing scheme where several secrets can be shared for each threshold value. Since the running time is an important factor for practical applications, we will provide a complexity comparison of our combined approach with respect to the previous schemes.

Ideal threshold schemes from orthogonal arrays

The work investigates the design of ideal threshold secret sharing in the context of cheating prevention. We showed that each orthogonal array is exactly a defining matrix of an ideal threshold scheme. To prevent cheating, defining matrices should be nonlinear so both the cheaters and honest participants have the same chance of guessing of the valid secret. The last part of the work shows how to construct nonlinear secret sharing based on orthogonal arrays.

An intentional class design model to engage first year students with threshold concepts using the academic discourse theories of Vygotsky and Laurillard

In the context of the first-year university classroom, this paper develops Vygotsky’s claim that ‘the relations between the higher mental functions were at one time real relations between people’. By taking the main horizontal and hierarchical levels of classroom discourse and dialogue (student-student, student-teacher, teacher-teacher) and marrying these with the possibilities opened up by Laurillard’s conversational framework, we argue that the learning challenge of a ‘troublesome’ threshold concept might be met by a carefully designed sequence of teaching events and experiences for first year students, and we provide a number of strategies that exploit each level of these ‘hierarchies of discourse’. We suggest that an analytical approach to classroom design that embodies these levels of discourse in sequenced dialogic methods could be used by teachers as a strategy to interrogate and adjust teaching-in-practice especially in the first year of university study.

Threshold photoproduction of charged pions on14N

Pion photoproduction processes14Ngs(gamma, pgr +)14C and14Ngs(gamma, pgr –)14O have been studied in the threshold region. These processes provide an excellent tool to study the corrections to soft pion theorems and Kroll-Ruderman limit as applied to nuclear processes. The agreement with the available experimental data for these processes is better with the empirical wave functions while the shell-model wave functions predict a much higher value. Detailed experimental studies of these reactions at threshold, it is shown, are expected to lead to a better understanding of the shell-model inputs and radial distributions in the 1p state. We thank Dr. S.C.K. Nair for a helpful discussion during the initial stages of this work. One of us (MVN) thanks Dr. J.M. Laget for sending some unpublished data on pion photoproduction. He is also thankful to Dr. J. Pasupathy and Dr. R. Rajaraman for their interest and encouragement.

Karnaugh map synthesis of multigate threshold networks

It has been shown in an earlier paper that I-realizability of a unate function F of up to six variables corresponds to ' compactness ' of the plot of F on a Karnaugh map. Here, an algorithm has been presented to synthesize on a Karnaugh map a non-threahold function of up to Bix variables with the minimum number of threshold gates connected in cascade. Incompletely specified functions can also be treated. No resort to inequalities is made and no pre-processing (such as positivizing and ordering) of the given switching function is required.

Photoelectron angular distributions from above threshold ionization of hydrogen atoms in strong laser fields

We apply a scattering theory of nonperturbative quantum electrodynamics to study the photoelectron angular distributions (PADs) of a hydrogen atom irradiated by linearly polarized laser light. The calculated PADs show main lobes and jetlike structure. Previous experimental studies reveal that in a set of above-threshold-ionization peaks when the absorbed-photon number increases by one, the jet number also increases by one. Our study confirms this experimental observation. Our calculations further predict that in some cases three more jets may appear with just one-more-photon absorption. With consideration of laser-frequency change, one less jet may also appear with one-more-photon absorption. The jetlike structure of PADs is due to the maxima of generalized phased Bessel functions, not an indication of the quantum number of photoelectron angular momentum states.