Higher order universal one-way hash functions from the subset sum assumption

Universal One-Way Hash Functions (UOWHFs) may be used in place of collision-resistant functions in many public-key cryptographic applications. At Asiacrypt 2004, Hong, Preneel and Lee introduced the stronger security notion of higher order UOWHFs to allow construction of long-input UOWHFs using the Merkle-Damgård domain extender. However, they did not provide any provably secure constructions for higher order UOWHFs. We show that the subset sum hash function is a kth order Universal One-Way Hash Function (hashing n bits to m < n bits) under the Subset Sum assumption for k = O(log m). Therefore we strengthen a previous result of Impagliazzo and Naor, who showed that the subset sum hash function is a UOWHF under the Subset Sum assumption. We believe our result is of theoretical interest; as far as we are aware, it is the first example of a natural and computationally efficient UOWHF which is also a provably secure higher order UOWHF under the same well-known cryptographic assumption, whereas this assumption does not seem sufficient to prove its collision-resistance. A consequence of our result is that one can apply the Merkle-Damgård extender to the subset sum compression function with ‘extension factor’ k+1, while losing (at most) about k bits of UOWHF security relative to the UOWHF security of the compression function. The method also leads to a saving of up to m log(k+1) bits in key length relative to the Shoup XOR-Mask domain extender applied to the subset sum compression function.

The subset sum problem in Keno modelling

Aspects of Keno modelling throughout the Australian states of Queensland, New South Wales and Victoria are discussed: the trivial Heads or Tails and the more interesting Keno Bonus, which leads to consideration of the subset sum problem. The most intricate structure is where Heads or Tails and Keno Bonus are combined, and here, the issue of independence arises. Closed expressions for expected return to player are presented in each case.

Towards a game theoretic authorisation model

Authorised users (insiders) are behind the majority of security incidents with high financial impacts. Because authorisation is the process of controlling users’ access to resources, improving authorisation techniques may mitigate the insider threat. Current approaches to authorisation suffer from the assumption that users will (can) not depart from the expected behaviour implicit in the authorisation policy. In reality however, users can and do depart from the canonical behaviour. This paper argues that the conflict of interest between insiders and authorisation mechanisms is analogous to the subset of problems formally studied in the field of game theory. It proposes a game theoretic authorisation model that can ensure users’ potential misuse of a resource is explicitly considered while making an authorisation decision. The resulting authorisation model is dynamic in the sense that its access decisions vary according to the changes in explicit factors that influence the cost of misuse for both the authorisation mechanism and the insider.

Aspects of Keno modelling

In two earlier papers, an intricate Jackpot structure and analysis of pseudo-random numbers for Keno in the Australian state of Queensland circa 2000 were described. Aspects of the work were also reported at an international conference . Since that time, many aspects of the game in Australia have changed. The present paper presents more up-to-date details of Keno throughout the states of Queensland, New South Wales and Victoria. A much simpler jackpot structure is now in place and this is described. Two add-ons or side-bets to the game are detailed: the trivial Heads or Tails and the more interesting Keno Bonus, which leads to consideration of the subset sum problem. The most intricate structure is where Heads or Tails and Keno Bonus are combined, and here, the issue of independence arises. Closed expressions for expected return to player (ERTP) are presented in all cases.

Is the sum more than the corporate entrepreneurship parts? the different effects of social capital on innovation, venturing, and renewal processes

Principal Topic Although corporate entrepreneurship is of vital importance for long-term firm survival and growth (Zahra and Covin, 1995), researchers still struggle with understanding how to manage corporate entrepreneurship activities. Corporate entrepreneurship consists of three parts: innovation, venturing, and renewal processes (Guth and Ginsberg, 1990). Innovation refers to the development of new products, venturing to the creation of new businesses, and renewal to redefining existing businesses (Sharma, and Chrisman, 1999; Verbeke et al., 2007). Although there are many studies focusing on one of these aspects (cf. Burgelman, 1985; Huff et al., 1992), it is very difficult to compare the outcomes of these studies due to differences in contexts, measures, and methodologies. This is a significant lack in our understanding of CE, as firms engage in all three aspects of CE, making it important to compare managerial and organizational antecedents of innovation, venturing and renewal processes. Because factors that may enhance venturing activities may simultaneously inhibit renewal activities. The limited studies that did empirically compare the individual dimensions (cf. Zahra, 1996; Zahra et al., 2000; Yiu and Lau, 2008; Yiu et al., 2007) generally failed to provide a systematic explanation for potential different effects of organizational antecedents on innovation, venturing, and renewal. With this study we aim to investigate the different effects of structural separation and social capital on corporate entrepreneurship activities. The access to existing and the development of new knowledge has been deemed of critical importance in CE-activities (Floyd and Wooldridge, 1999; Covin and Miles, 2007; Katila and Ahuja, 2002). Developing new knowledge can be facilitated by structurally separating corporate entrepreneurial units from mainstream units (cf. Burgelman, 1983; Hill and Rothaermel, 2003; O'Reilly and Tushman, 2004). Existing knowledge and resources are available through networks of social relationships, defined as social capital (Nahapiet and Ghoshal, 1998; Yiu and Lau, 2008). Although social capital has primarily been studied at the organizational level, it might be equally important at top management level (Belliveau et al., 1996). However, little is known about the joint effects of structural separation and integrative mechanisms to provide access to social capital on corporate entrepreneurship. Could these integrative mechanisms for example connect the separated units to facilitate both knowledge creation and sharing? Do these effects differ for innovation, venturing, and renewal processes? Are the effects different for organizational versus top management team integration mechanisms? Corporate entrepreneurship activities have for example been suggested to take place at different levels. Whereas innovation is suggested to be a more bottom-up process, strategic renewal is a more top-down process (Floyd and Lane, 2000; Volberda et al., 2001). Corporate venturing is also a more bottom-up process, but due to the greater required resource commitments relative to innovation, it ventures need to be approved by top management (Burgelman, 1983). As such we will explore the following key research question in this paper: How do social capital and structural separation on organizational and TMT level differentially influence innovation, venturing, and renewal processes? Methodology/Key Propositions We investigated our hypotheses on a final sample of 240 companies in a variety of industries in the Netherlands. All our measures were validated in previous studies. We targeted a second respondent in each firm to reduce problems with single-rater data (James et al., 1984). We separated the measurement of the independent and the dependent variables in two surveys to create a one-year time lag and reduce potential common method bias (Podsakoff et al., 2003). Results and Implications Consistent with our hypotheses, our results show that configurations of structural separation and integrative mechanisms have different effects on the three aspects of corporate entrepreneurship. Innovation was affected by organizational level mechanisms, renewal by integrative mechanisms on top management team level and venturing by mechanisms on both levels. Surprisingly, our results indicated that integrative mechanisms on top management team level had negative effects on corporate entrepreneurship activities. We believe this paper makes two significant contributions. First, we provide more insight in what the effects of ambidextrous organizational forms (i.e. combinations of differentiation and integration mechanisms) are on venturing, innovation and renewal processes. Our findings show that more valuable insights can be gained by comparing the individual parts of corporate entrepreneurship instead of focusing on the whole. Second, we deliver insights in how management can create a facilitative organizational context for these corporate entrepreneurship activities.

Validity of dietary questionnaires in Sri Lankan adults and the association of dietary intake with obesity

Traditionally, infectious diseases and under-nutrition have been considered major health problems in Sri Lanka with little attention paid to obesity and associated non-communicable diseases (NCDs). However, the recent Sri Lanka Diabetes and Cardiovascular Study (SLDCS) reported the epidemic level of obesity, diabetes and metabolic syndrome. Moreover, obesity-associated NCDs is the leading cause of death in Sri Lanka and there is an exponential increase in hospitalization due to NCDs adversely affecting the development of the country. Despite Sri Lanka having a very high prevalence of NCDs and associated mortality, little is known about the causative factors for this burden. It is widely believed that the global NCD epidemic is associated with recent lifestyle changes, especially dietary factors. In the absence of sufficient data on dietary habits in Sri Lanka, successful interventions to manage these serious health issues would not be possible. In view of the current situation the dietary survey was undertaken to assess the intakes of energy, macro-nutrients and selected other nutrients with respect to socio demographic characteristics and the nutritional status of Sri Lankan adults especially focusing on obesity. Another aim of this study was to develop and validate a culturally specific food frequency questionnaire (FFQ) to assess dietary risk factors of NCDs in Sri Lankan adults. Data were collected from a subset of the national SLDCS using a multi-stage, stratified, random sampling procedure (n=500). However, data collection in the SLDCS was affected by the prevailing civil war which resulted in no data being collected from Northern and Eastern provinces. To obtain a nationally representative sample, additional subjects (n=100) were later recruited from the two provinces using similar selection criteria. Ethical Approval for this study was obtained from the Ethical Review Committee, Faculty of Medicine, University of Colombo, Sri Lanka and informed consent was obtained from the subjects before data were collected. Dietary data were obtained using the 24-h Dietary Recall (24HDR) method. Subjects were asked to recall all foods and beverages, consumed over the previous 24-hour period. Respondents were probed for the types of foods and food preparation methods. For the FFQ validation study, a 7-day weight diet record (7-d WDR) was used as the reference method. All foods recorded in the 24 HDR were converted into grams and then intake of energy and nutrients were analysed using NutriSurvey 2007 (EBISpro, Germany) which was modified for Sri Lankan food recipes. Socio-demographic details and body weight perception were collected from interviewer-administrated questionnaire. BMI was calculated and overweight (BMI ≥23 kg.m-2), obesity (BMI ≥25 kg.m-2) and abdominal obesity (Men: WC ≥ 90 cm; Women: WC ≥ 80 cm) were categorized according to Asia-pacific anthropometric cut-offs. The SPSS v. 16 for Windows and Minitab v10 were used for statistical analysis purposes. From a total of 600 eligible subjects, 491 (81.8%) participated of whom 34.5% (n=169) were males. Subjects were well distributed among different socio-economic parameters. A total of 312 different food items were recorded and nutritionists grouped similar food items which resulted in a total of 178 items. After performing step-wise multiple regression, 93 foods explained 90% of the variance for total energy intake, carbohydrates, protein, total fat and dietary fibre. Finally, 90 food items and 12 photographs were selected. Seventy-seven subjects completed (response rate = 65%) the FFQ and 7-day WDR. Estimated mean energy intake (SD) from FFQ (1794±398 kcal) and 7DWR (1698±333 kcal, P<0.001) was significantly different due to a significant overestimation of carbohydrate (~10 g/d, P<0.001) and to some extent fat (~5 g/d, NS). Significant positive correlations were found between the FFQ and 7DWR for energy (r = 0.39), carbohydrate (r = 0.47), protein (r = 0.26), fat (r =0.17) and dietary fiber (r = 0.32). Bland-Altman graphs indicated fairly good agreement between methods with no relationship between bias and average intake of each nutrient examined. The findings from the nutrition survey showed on average, Sri Lankan adults consumed over 14 portions of starch/d; moreover, males consumed 5 more portions of cereal than females. Sri Lankan adults consumed on average 3.56 portions of added sugars/d. Moreover, mean daily intake of fruit (0.43) and vegetable (1.73) portions was well below minimum dietary recommendations (fruits 2 portions/d; vegetables 3 portions/d). The total fruit and vegetable intake was 2.16 portions/d. Daily consumption of meat or alternatives was 1.75 portions and the sum of meat and pulses was 2.78 portions/d. Starchy foods were consumed by all participants and over 88% met the minimum daily recommendations. Importantly, nearly 70% of adults exceeded the maximum daily recommendation for starch (11portions/d) and a considerable proportion consumed larger numbers of starch servings daily, particularly men. More than 12% of men consumed over 25 starch servings/d. In contrast to their starch consumption, participants reported very low intakes of other food groups. Only 11.6%, 2.1% and 3.5% of adults consumed the minimum daily recommended servings of vegetables, fruits, and fruits and vegetables combined, respectively. Six out of ten adult Sri Lankans sampled did not consume any fruits. Milk and dairy consumption was extremely low; over a third of the population did not consume any dairy products and less than 1% of adults consumed 2 portions of dairy/d. A quarter of Sri Lankans did not report consumption of meat and pulses. Regarding protein consumption, 36.2% attained the minimum Sri Lankan recommendation for protein; and significantly more men than women achieved the recommendation of ≥3 servings of meat or alternatives daily (men 42.6%, women 32.8%; P<0.05). Over 70% of energy was derived from carbohydrates (Male:72.8±6.4%, Female:73.9±6.7%), followed by fat (Male:19.9±6.1%, Female:18.5±5.7%) and proteins (Male:10.6±2.1%, Female:10.9±5.6%). The average intake of dietary fiber was 21.3 g/day and 16.3 g/day for males and females, respectively. There was a significant difference in nutritional intake related to ethnicities, areas of residence, education levels and BMI categories. Similarly, dietary diversity was significantly associated with several socio-economic parameters among Sri Lankan adults. Adults with BMI ≥25 kg.m-2 and abdominally obese Sri Lankan adults had the highest diet diversity values. Age-adjusted prevalence (95% confidence interval) of overweight, obesity, and abdominal obesity among Sri Lankan adults were 17.1% (13.8-20.7), 28.8% (24.8-33.1), and 30.8% (26.8-35.2), respectively. Men, compared with women, were less overweight, 14.2% (9.4-20.5) versus 18.5% (14.4-23.3), P = 0.03, less obese, 21.0% (14.9-27.7) versus 32.7% (27.6-38.2), P < .05; and less abdominally obese, 11.9% (7.4-17.8) versus 40.6% (35.1-46.2), P < .05. Although, prevalence of obesity has reached to epidemic level body weight misperception was common among Sri Lankan adults. Two-thirds of overweight males and 44.7% of females considered themselves as in "about right weight". Over one third of both male and female obese subjects perceived themselves as "about right weight" or "underweight". Nearly 32% of centrally obese men and women perceived that their waist circumference is about right. People who perceived overweight or very overweight (n = 154) only 63.6% tried to lose their body weight (n = 98), and quarter of adults seek advices from professionals (n = 39). A number of important conclusions can be drawn from this research project. Firstly, the newly developed FFQ is an acceptable tool for assessing the nutrient intake of Sri Lankans and will assist proper categorization of individuals by dietary exposure. Secondly, a substantial proportion of the Sri Lankan population does not consume a varied and balanced diet, which is suggestive of a close association between the nutrition-related NCDs in the country and unhealthy eating habits. Moreover, dietary diversity is positively associated with several socio-demographic characteristics and obesity among Sri Lankan adults. Lastly, although obesity is a major health issue among Sri Lankan adults, body weight misperception was common among underweight, healthy weight, overweight, and obese adults in Sri Lanka. Over 2/3 of overweight and 1/3 of obese Sri Lankan adults believe that they are in "right weight" or "under-weight" categories.

On the hardness of the sum of K mins problem

The sum of k mins protocol was proposed by Hopper and Blum as a protocol for secure human identification. The goal of the protocol is to let an unaided human securely authenticate to a remote server. The main ingredient of the protocol is the sum of k mins problem. The difficulty of solving this problem determines the security of the protocol. In this paper, we show that the sum of k mins problem is NP-Complete and W[1]-Hard. This latter notion relates to fixed parameter intractability. We also discuss the use of the sum of k mins protocol in resource-constrained devices.

Linear programming for large-scale Markov decision problems

We consider the problem of controlling a Markov decision process (MDP) with a large state space, so as to minimize average cost. Since it is intractable to compete with the optimal policy for large scale problems, we pursue the more modest goal of competing with a low-dimensional family of policies. We use the dual linear programming formulation of the MDP average cost problem, in which the variable is a stationary distribution over state-action pairs, and we consider a neighborhood of a low-dimensional subset of the set of stationary distributions (defined in terms of state-action features) as the comparison class. We propose a technique based on stochastic convex optimization and give bounds that show that the performance of our algorithm approaches the best achievable by any policy in the comparison class. Most importantly, this result depends on the size of the comparison class, but not on the size of the state space. Preliminary experiments show the effectiveness of the proposed algorithm in a queuing application.