Blockchain Papers

Sankita Patel, Viren Patel, Devesh C. Jinwala

No abstract is available for this record.

Xiang Xie, Rui Xue, Minqian Wang

No abstract is available for this record.

Maheswara Rao Valluri

Authentication is a process by which an entity, which could be a person or intended computer, establishes its identity to another entity. In private and public computer networks including the Internet, authentication is commonly done through the use of logon passwords. Knowledge of the password is assumed to guarantee that the user is authentic. Internet business and many other transactions require a more stringent authentication process. The aim of this paper is to propose two authentication schemes based on general non-commutative rings. The key idea of the schemes is that for a given non-commutative ring; one can build polynomials on additive structure and takes them as underlying work structure. By doing so, one can implement authentication schemes, one of them being zero-knowledge interactive proofs of knowledge, on multiplicative structure of the ring. The security of the schemes is based on the intractability of the polynomial symmetrical decomposition problem over the given non-commutative ring.

Kai-Min Chung, Edward Lui, Mohammad Mahmoody, Rafael Pass

Goldreich and Oren (JoC’94) show that only trivial languages have 2-message zero-knowledge arguments. In this note we consider weaker, super-polynomial-time simulation (SPS), notions of zero-knowledge. We present barriers to using black-box reductions for demonstrating soundness of 2-message protocols with efficient prover strategies satisfying SPS zero-knowledge. More precisely, we show that assuming the existence of poly(T (n))-hard one-way functions, the following holds: • For sub-exponential (or smaller) T (·), polynomial-time black-box reductions cannot be used to prove soundness of 2-message T (·)-simulatable arguments based on any polynomialtime intractability assumption. This matches known 2-message quasi-polynomial-time simulatable arguments using a quasi-polynomial-time reduction (Pass’03), and 2-message exponential-time simulatable proofs using a polynomial-time reduction (Dwork-Naor’00, Pass’03). • poly(T (·))-time black-box reductions cannot be used to prove soundness of 2-message strong T (·)-simulatable (efficient prover) arguments based on any poly(T (·))-time intractability assumption; strong T (·)-simulatability means that the output of the simulator is indistinguishable also for poly(T (·))-size circuits. This matches known 3-message strong quasi-polynomial-time simulatable proofs (Blum’86, Canetti et al ’ 00).

Yibeltal Assefa, Yogan Pillay, Wim Van Damme

Sander Greenland and Charles Poole1 accept that P values are here to stay but recognize that some of their most common interpretations have problems. The casual view of the P value as posterior probability of the truth of the null hypothesis is false and not even close to valid under any reasonable model, yet this misunderstanding persists even in high-stakes settings (as discussed, for example, by Greenland in 2011).2 The formal view of the P value as a probability conditional on the null is mathematically correct but typically irrelevant to research goals (hence, the popularity of alternative—if wrong—interpretations). A Bayesian interpretation based on a spike-and-slab model makes little sense in applied contexts in epidemiology, political science, and other fields in which true effects are typically nonzero and bounded (thus violating both the “spike” and the “slab” parts of the model). I find Greenland and Poole’s1 perspective to be valuable: it is important to go beyond criticism and to understand what information is actually contained in a P value. These authors discuss some connections between P values and Bayesian posterior probabilities. I am not so optimistic about the practical value of these connections. Conditional on the continuing omnipresence of P values in applications, however, these are important results that should be generally understood. Greenland and Poole1 make two points. First, they describe how P values approximate posterior probabilities under prior distributions that contain little information relative to the data: This misuse [of P values] may be lessened by recognizing correct Bayesian interpretations. For example, under weak priors, 95% confidence intervals approximate 95% posterior probability intervals, one-sided P values approximate directional posterior probabilities, and point estimates approximate posterior medians. I used to think this way, too (see many examples in our books), but in recent years have moved to the position that I do not trust such direct posterior probabilities. Unfortunately, I think we cannot avoid informative priors if we wish to make reasonable unconditional probability statements. To put it another way, I agree with the mathematical truth of the quotation above, but I think it can mislead in practice because of serious problems with apparently noninformative or weak priors. Second, the main proposal made by Greenland and Poole is to interpret P values as bounds on posterior probabilities: [U]nder certain conditions, a one-sided P value for a prior median provides an approximate lower bound on the posterior probability that the point estimate is on the wrong side of that median. This is fine, but when sample sizes are moderate or small (as is common in epidemiology and social science), posterior probabilities will depend strongly on the prior distribution. Although I do not see much direct value in a lower bound, I am intrigued by Greenland and Poole’s1 point that “if one uses an informative prior to derive the posterior probability of the point estimate being in the wrong direction, P0/2 provides a reference point indicating how much the prior information influenced that posterior probability.” This connection could be useful to researchers working in an environment in which P values are central to communication of statistical results. In presenting my view of the limitations of Greenland and Poole’s1 points, I am leaning heavily on their own work, in particular on their emphasis that, in real problems, prior information is always available and is often strong enough to have an appreciable impact on inferences. Before explaining my position, I will briefly summarize how I view classical P values and my experiences. For more background, I recommend the discussion by Krantz3 of null hypothesis testing in psychology research. WHAT IS A P VALUE IN PRACTICE? The P value is a measure of discrepancy of the fit of a model or “null hypothesis” H to data y. Mathematically, it is defined as Pr(T(yrep)>T(y)|H), where yrep represents a hypothetical replication under the null hypothesis and T is a test statistic (ie, a summary of the data, perhaps tailored to be sensitive to departures of interest from the model). In a model with free parameters (a “composite null hypothesis”), the P value can depend on these parameters, and there are various ways to get around this, by plugging in point estimates, averaging over a posterior distribution, or adjusting for the estimation process. I do not go into these complexities further, bringing them up here only to make the point that the construction of P values is not always a simple or direct process. (Even something as simple as the classical chi-square test has complexities to be discovered; see the article by Perkins et al4). In theory, the P value is a continuous measure of evidence, but in practice it is typically trichotomized approximately into strong evidence, weak evidence, and no evidence (these can also be labeled highly significant, marginally significant, and not statistically significant at conventional levels), with cutoffs roughly at P = 0.01 and 0.10. One big practical problem with P values is that they cannot easily be compared. The difference between a highly significant P value and a clearly nonsignificant P value is itself not necessarily statistically significant. (Here, I am using “significant” to refer to the 5% level that is standard in statistical practice in much of biostatistics, epidemiology, social science, and many other areas of application.) Consider a simple example of two independent experiments with estimates (standard error) of 25 (10) and 10 (10). The first experiment is highly statistically significant (two and a half standard errors away from zero, corresponding to a normal-theory P value of about 0.01) while the second is not significant at all. Most disturbingly here, the difference is 15 (14), which is not close to significant. The naive (and common) approach of summarizing an experiment by a P value and then contrasting results based on significance levels, fails here, in implicitly giving the imprimatur of statistical significance on a comparison that could easily be explained by chance alone. As discussed by Gelman and Stern,5 this is not simply the well-known problem of arbitrary thresholds, the idea that a sharp cutoff at a 5% level, for example, misleadingly separates the P = 0.051 cases from P = 0.049. This is a more serious problem: even an apparently huge difference between clearly significant and clearly nonsignificant is not itself statistically significant. In short, the P value is itself a statistic and can be a noisy measure of evidence. This is a problem not just with P values but with any mathematically equivalent procedure, such as summarizing results by whether the 95% confidence interval includes zero. GOOD, MEDIOCRE, AND BAD P VALUES For all their problems, P values sometimes “work” to convey an important aspect of the relation of data to model. Other times, a P value sends a reasonable message but does not add anything beyond a simple confidence interval. In yet other situations, a P value can actively mislead. Before going on, I will give examples of each of these three scenarios. A P Value that Worked Several years ago, I was contacted by a person who suspected fraud in a local election.6 Partial counts had been released throughout the voting process and he thought the proportions for the various candidates looked suspiciously stable, as if they had been rigged to aim for a particular result. Excited to possibly be at the center of an explosive news story, I took a look at the data right away. After some preliminary graphs—which indeed showed stability of the vote proportions as they evolved during election day—I set up a hypothesis test comparing the variation in the data to what would be expected from independent binomial sampling. When applied to the entire data set (27 candidates running for six offices), the result was not statistically significant: there was no less (and, in fact, no more) variance than would be expected by chance alone. In addition, an analysis of the 27 separate chi-square statistics revealed no particular patterns. I was left to conclude that the election results were consistent with random voting (even though, in reality, voting was certainly not random—for example, married couples are likely to vote at the same time, and the sorts of people who vote in the middle of the day will differ from those who cast their ballots in the early morning or evening). I regretfully told my correspondent that he had no case. In this example, we cannot interpret a nonsignificant result as a claim that the null hypothesis was true or even as a claimed probability of its truth. Rather, nonsignificance revealed the data to be compatible with the null hypothesis; thus, my correspondent could not argue that the data indicated fraud. A P Value that Was Reasonable but Unnecessary It is common for a research project to culminate in the estimation of one or two parameters, with publication turning on a P value being less than a conventional level of significance. For example, in our study of the effects of redistricting in state legislatures (Gelman and King),7 the key parameters were interactions in regression models for partisan bias and electoral responsiveness. Although we did not actually report P values, we could have: what made our article complete was that our findings of interest were more than two standard errors from zero, thus reaching the P < 0.05 level. Had our significance level been much greater (eg, estimates that were four or more standard errors from zero), we would doubtless have broken up our analysis (eg, studying Democrats and Republicans separately) to broaden the set of claims that we could confidently assert. Conversely, had our regressions not reached statistical significance at the conventional level, we would have performed some sort of pooling or constraining of our model to arrive at some weaker assertion that reached the 5% level. (Just to be clear: we are not saying that we would have performed data dredging, fishing for significance; rather, we accept that sample size dictates how much we can learn with confidence; when data are weaker, it can be possible to find reliable patterns by averaging.) In any case, my point is that in this example it would have been just fine to summarize our results in this example via P values even though we did not happen to use that formulation. A Misleading P Value Finally, in many scenarios P values can distract or even mislead, either a nonsignificant result wrongly interpreted as a confidence statement in support of the null hypothesis or a significant P value that is taken as proof of an effect. A notorious example of the latter is the recent article by Bem,8 which reported statistically significant results from several experiments on extrasensory perception (ESP). At brief glance, it seems impressive to see multiple independent findings that are statistically significant (and combining the P values using classical rules would yield an even stronger result), but with enough effort it is possible to find statistical significance anywhere (see the report by Simmons et al9). The focus on P values seems to have both weakened that study (by encouraging the researcher to present only some of his data so as to draw attention away from nonsignificant results) and to have led reviewers to inappropriately view a low P value (indicating a misfit of the null hypothesis to data) as strong evidence in favor of a specific alternative hypothesis (ESP) rather than other, perhaps more scientifically plausible, alternatives such as measurement error and selection bias. PRIORS, POSTERIORS, AND P VALUES Now that I have established my credentials as a pragmatist who finds P values useful in some settings but not others, I want to discuss Greenland and Poole’s proposal to either interpret one-sided P values as probability statements under uniform priors (an idea they trace back to Gossett)10 or else to use one-sided P values as bounds on posterior probabilities (a result they trace back to Casella and Berger).11 The general problem I have with noninformatively derived Bayesian probabilities is that they tend to be too strong. At first, this may sound paradoxical, that a noninformative or weakly informative prior yields posteriors that are too forceful—and let me deepen the paradox by stating that a stronger, more informative prior will tend to yield weaker, more plausible posterior statements. How can it be that adding prior information weakens the posterior? It has to do with the sort of probability statements we are often interested in making. Here is an example from Gelman and Weakliem.12 A sociologist examining a publicly available survey discovered a pattern relating attractiveness of parents to the sexes of their children. He found that 56% of the children of the most attractive parents were girls, when compared with 48% of the children of the other parents, and the difference was statistically significant at P < 0.02. The assessments of attractiveness had been performed many years before these people had children, so the researcher felt he had support for a claim of an underlying biological connection between attractiveness and sex ratio. The original analysis by Kanazawa13 had multiple-comparisons issues, and after performing a regression analysis rather than selecting the most significant comparison, we get a P value closer to 0.2 rather than the stated 0.02. For the purposes of our present discussion, though, in which we are evaluating the connection between P values and posterior probabilities, it will not matter much which number we use. We shall go with P = 0.2 because it seems like a more reasonable analysis given the data. Let θ be the true (population) difference in sex ratios of attractive and less attractive parents. Then the data under discussion (with a two-sided P value of 0.2), combined with a uniform prior on θ, yield a 90% posterior probability that θ is positive. Do I believe this? No. Do I even consider this a reasonable data summary? No again. We can derive these “No” responses in three different ways: first, by looking directly at the evidence; second, by considering the prior; and third, by considering the implications for statistical practice if this sort of probability statement were computed routinely. First, a claimed 90% probability that θ > 0 seems too strong. Given that the P value (adjusted for multiple comparisons) was only 0.2—that is, a result that strong would occur a full 20% of the time just by chance alone, even with no true difference—it seems absurd to assign a 90% belief to the conclusion. I am not prepared to offer 9-to-1 odds on the basis of a pattern someone happened to see that could plausibly have occurred by chance alone, nor for that matter would I offer 99-to-1 odds based on the original claim of the 2% significance level. Second, the prior uniform distribution on θ seems much too weak. There is a large literature on sex ratios, with factors such as ethnicity, maternal age, and season of birth corresponding to difference in probability of girl birth of <0.5 percentage points. It is a priori implausible that sex-ratio differences corresponding to attractiveness are larger than for these other factors. Assigning an informative prior centered on zero shrinks the posterior toward zero, and the resulting posterior probability that θ > 0 moves to a more plausible value in the range of 60%, corresponding to the idea that the result is suggestive but not close to convincing. Third, consider what would happen if we routinely interpreted one-sided P values as posterior probabilities. In that case, an experimental result that is 1 standard error from zero—that is, exactly what one might expect from chance alone—would imply an 83% posterior probability that the true effect in the population has the same direction as the observed pattern in the data at hand. It does not make sense to me to claim 83% certainty—5-to-1 odds—based on data that not only could occur by chance alone but in fact represent an expected level of discrepancy. This system-level analysis accords with my criticism of the flat prior: as Greenland and Poole1 note in their article, the effects being studied in epidemiology are typically range from −1 to 1 on the logit scale; hence, analyses assuming broader priors will systematically overstate the probabilities of very large effects and will overstate the probability that an estimate from a small sample will agree in sign with the corresponding population quantity. Rather than relying on noninformative priors, I prefer the suggestion of Greenland and Poole1 to bound posterior probabilities using real prior information. I would prefer to perform my Bayesian inferences directly without using P values as in intermediate step, but given the ubiquity of P values in much applied work, I can see that it can be helpful for researchers to understand their connection to posterior probabilities under informative priors. SUMMARY Like many Bayesians, I have often represented classical confidence intervals as posterior probability intervals and interpreted one-sided P values as the posterior probability of a positive effect. These are valid conditional on the assumed noninformative prior but typically do not make sense as unconditional probability statements. As Sander Greenland has discussed in much of his work over the years, epidemiologists and applied scientists in general have knowledge of the sizes of plausible effects and biases. I believe that a direct interpretation of P values as posterior probabilities can be a useful start—if we recognize that such summaries systematically overestimate the strength of claims from any particular dataset. In this way, I am in agreement with Greenland and Poole’s interpretation of the one-sided P value as a lower bound of a posterior probability, although I am less convinced of the practical utility of this bound, given that the closeness of the bound depends on a combination of sample size and prior distribution. The default conclusion from a noninformative prior analysis will almost invariably put too much probability on extreme values. A vague prior distribution assigns much of its probability on values that are never going to be plausible, and this disturbs the posterior probabilities more than we tend to expect—something that we probably do not think about enough in our routine applications of standard statistical methods. Greenland and Poole1 perform a valuable service by opening up these calculations and placing them in an applied context.

Xiao Qiang Guo, Li Hong Li, Cui Ling Luo, Yi Shuo Shi

The Bit Commitment (BC) is an important basic agreement in cryptography . The concept was first proposed by the winner of the Turing Award in 1995 ManuelBlum. Bit commitment scheme can be used to build up zero knowledge proof, verified secret sharing, throwing coins etc agreement.Simultaneously and Oblivious Transfer together constitute the basis of secure multi-party computations. Both of them are hotspots in the field of information security. We investigated unconditional secure Quantum Bit Commitment (QBC) existence. And we constructed a new bit commitment model – double prover bit commitment. The Quantum Bit Commitment Protocol can be resistant to errors caused by noise.

Nivedita Datta

In many applications, when communicating with a host, we may or may not be concerned about the privacy of the data but are mainly concerned about the integrity of data being transmitted. This paper presents a simple algorithm based on zero knowledge proof by which the receiver can confirm the integrity of data without the sender having to send the digital signature of the message directly. Also, if the same document is sent across by the same user multiple times, this scheme results in different digital signature each time thus making it a practical one-time signature scheme.

Man Ho Au, Willy Susilo, Yi Mu, Sherman S. M. Chow

Dynamick-times anonymous authentication (k-TAA) schemes allow members of a group to be authenticated anonymously by application providers for a bounded number of times, where application providers can independently and dynamically grant or revoke access right to members in their own group. In this paper, we construct a dynamick-TAA scheme with space and time complexities ofO(log(k)) and a variant, in which the authentication protocol only requires constant time and space complexities at the cost ofO(k) -sized public key. We also describe some tradeoff issues between different system characteristics. We detail all the zero-knowledge proof-of-knowledge protocols involved and show that our construction is secure in the random oracle model under theq-strong Diffie-Hellman assumption andq-decisional Diffie-Hellman inversion assumption. We provide a proof-of-concept implementation, experiment on its performance, and show that our scheme is practical.

Kai-Min Chung, Rafael Pass, Karn Seth

The simulation paradigm, introduced by Goldwasser, Micali and Racko , is of fundamental importance to modern cryptography. In a breakthrough work from 2001, Barak (FOCS'01) introduced a novel non-black-box simulation technique. This technique enabled the construction of new cryptographic primitives, such as resettably-sound zero-knowledge arguments, that cannot be proven secure using just black-box simulation techniques. The work of Barak and its follow-ups, however, all require stronger cryptographic hardness assumptions than the minimal assumption of one-way functions: the work of Barak requires the existence of collision-resistant hash functions, and a very recent result by Bitansky and Paneth (FOCS'12) instead requires the existence of an Oblivious Transfer protocol. In this work, we show how to perform non-black-box simulation assuming just the existence of one-way functions. In particular, we demonstrate the existence of a constant-round resettably-sound zero-knowledge argument based only on the existence of one-way functions. Using this technique, we determine necessary and su cient assumptions for several other notions of resettable security of zero-knowledge proofs. An additional bene t of our approach is that it seemingly makes practical implementations of non-black-box zero-knowledge viable.

Dexin Yang, Baolin Xu, Bo Yang, Jianping Wang

In this paper, a novel biometric authentication scheme is proposed, which combines zero-knowledge proof, - protocols and bit commitment scheme. The remote server compares biometric template using committed values, this can keep privacy of user's biometrics. To the best knowledge of us, this is the first scheme which uses - protocols as a basic tool to implement biometric authentication. Compared with the previous schemes, this scheme has advantages as higher security, lower computation complexity and privacy keeping of biometric template.

Jannik Dreier, Jean‐Guillaume Dumas, Pascal Lafourcade

Auctions have a long history, having been recorded as early as 500 B.C. [Auction Theory, Academic Press, San Diego, USA, 2002]. Nowadays, electronic auctions have been a great success and are increasingly used in various applications, including high performance computing [Concurrency and Computatio n: Practice and Experience 14(13–15) (2002), 1507–1542]. Many cryptographic protocols have been proposed to address the various security requirements of these electronic transactions, in particular to ensure privacy. Brandt [International Journal of Information Security 5 (2006), 201–216] developed a protocol that computes the winner using homomorphic operations on a distributed ElGamal encryption of the bids. He claimed that it ensures full privacy of the bidders, i.e. no information apart from the winner and the winning price is leaked. We first show that this protocol – when using malleable interactive zero-knowledge proofs – is vulnerable to attacks by dishonest bidders. Such bidders can manipulate the publicly available data in a way that allows the seller to deduce all participants’ bids. We provide an efficient parallelized implementation of the protocol and the attack to show its practicality. Additionally we discuss some issues with verifiability as well as attacks on non-repudiation, fairness and the privacy of individual bidders exploiting authentication problems.

Chengdong Meng, Zhengyong Zhang, Rong Hu, Yongxiang Yang

DAA (Direct Anonymous Attestation) schemes are generally employed with the hardware of TPM to realize anonymous authentication. Basically, DAA schemes are based on group signatures. We propose a new DAA scheme based on a short group signature without encryption which departs from the traditional sign-encrypt-prove paradigm, only adopts an anonymous signature and non-interactive zero knowledge(NIZK) proofs. Compared to other DAA schemes at present, our scheme is approximately the most efficient and computational cost-saving with shorter signature length and easier signature generation. Our scheme also satisfies anonymity, trace ability and non-frame ability requirements.

José Bacelar Almeida, Manuel Barbosa, Endre Bangerter, Gilles Barthe · 6 authors

Developers building cryptography into security-sensitive applications face a daunting task. Not only must they understand the security guarantees delivered by the constructions they choose, they must also implement and combine them correctly and efficiently. Cryptographic compilers free developers from this task by turning high-level specifications of security goals into efficient implementations. Yet, trusting such tools is hard as they rely on complex mathematical machinery and claim security properties that are subtle and difficult to verify. In this paper we present ZKCrypt, an optimizing cryptographic compiler achieving an unprecedented level of assurance without sacrificing practicality for a comprehensive class of cryptographic protocols, known as Zero-Knowledge Proofs of Knowledge. The pipeline of ZKCrypt integrates purpose-built verified compilers and verifying compilers producing formal proofs in the CertiCrypt framework. By combining the guarantees delivered by each stage, ZKCrypt provides assurance that the output implementation securely realizes the abstract proof goal given as input. We report on the main characteristics of ZKCrypt, highlight new definitions and concepts at its foundations, and illustrate its applicability through a representative example of an anonymous credential system

Steven M Boker, Michael J. Wenger

In certain mathematical statistical circles, there appear to linger doubts about the soundness of latent variables, in particular common factors in factor models. In what follows we will show, to the best of our knowledge for the first time, that a common latent factor in a factor model can be conceived of as a genuine scientific construct obeying the usual formal criteria for such constructs. Following the discussion in Simon (1977, ch. 6 .6 ) it will be shown that a common factor in a factor model can be transformed into a network of regres­sion relationships between the manifest (observed) variables. Because this transformation is invertible, we end up with two strictly equiva­lent models; the factor model and a model without the factor. This shows that the latent factor in a factor model serves as a placeholder for a system of relationships between the manifest variables and thus obeys the most stringent criterion for valid scientific constructs (cf. Simon, 1977).In what follows, we present a complete constructive proof that the latent factor in a 1 -factor model can be transformed away, yielding a model composed of a network of regression relationships between the observed variables. Preliminary work in this direction can be found in a recent book by the first author that can be freely downloaded from internet (Molenaar, 2003). Also the paper by Rovine and Molenaar (2005) contains further elaborations. But in this chapter, we for 189 the first time present all steps in the proof in full detail and for the simplest possible situation, a 1 -factor model. Even though we take great care to explain the steps in the proof as clearly as possible, a lot is asked of the reader. We suppose that they have a working knowledge of structural equation model­ing, are acquainted with elementary matrix algebra, and are willing to work through some unfamiliar notions taken from time series anal­ysis. These efforts only can be asked if the returns are irresistible. And in our opinion the results presented in this chapter are quite revolutionary. For the first time a general technique, an invertible transformation, is presented with which one can remove latent vari­ables from a latent variable model without any loss of information. This makes explicit something basic about the scientific nature of la­tent variables: They are real and have solid groundings in the data. It turns out to be a matter of taste whether one wants to enter­tain a latent variable model, or instead, its equivalent representation without latent variables. Of course, latent variable models may be better interpretable (in our opinion, they almost always are) and we certainly do not want to advertise the unconditional use of our trans­formation technique. But a proof that latent variables, in particular common factors, can be reduced to functional relationships between manifest variables shows that these latent variables share all their for­mal and semantic qualities with other respectable scientific constructs like electromagnetic potential, entropy, and so forth. This is not only important from a philosophy of science point of view, but also for discussions about the status of well-known psychometrical constructs like reliability and validity (cf. Borsboom, Mellenbergh, & Heerden, 2003). Another implication of the proof to be given shortly is that all structural equation models can be shown to be nested. This par­ticular implication is not elaborated in this chapter, but details can be found in Rovine and Molenaar (2005) and in Molenaar (2003). To give one particular example, it can be shown that the latent growth curve model is nested under the latent simplex model (contra Rogosa & Willett, 1985; see also Mandys, Dolan, &; Molenaar, 1994). But the harvest is much bigger. If, as will be shown, it is possible to remove the factor from a 1 -factor model, then apparently it is possible to reduce the common latent dimension from one to zero. Because after the removal of the latent common factor (which defines the common one dimension in the initial 1 -factor model), there are no longer any common latent factors in the obtained equivalent model (hence the latent dimension in the latter model is zero). It is shown in Molenaar (2003) that this result holds in general. To illustrate, starting with a standard 2-factor model (where the two factors span up a two-dimensional common latent space), it is possible to transform this model to an equivalent model in which the common latent space is one-dimensional. Finally, the model obtained in the previous step can itself again be transformed into an equivalent model in which the common latent space is absent (zero-dimensional). This, of course, raises urgent questions about the proper definition of the dimension of a common latent space (like in statements such as “this psycho­logical test is indicative of two underlying dimensions”). There are additional important implications, although of a much more theo­retical nature. We mention only the direct relationship of the kind of result that we are about to prove with similar results obtained in mathematical system theory and statistical field theory (both of which are elaborated somewhat further in Molenaar, 2003). We hope and expect that sufficient reasons have been provided to carry on reading this chapter.

Kai-Min Chung, Huijia Lin, Rafael Pass

We present a constant-round concurrent zero-knowledge protocol for NP. Our protocol is sound against uniform polynomial-time attackers, and relies on the existence of families of collision-resistant hash functions, and a new (but in our eyes, natural) falsifiable intractability assumption: Roughly speaking, that Micali’s non-interactive CS-proofs are sound for languages in P.

S. Nangle-Smith

A short, 30cm, test section was used to study the effect of electrohydrodynamic (EHD) forces on flow redistribution in a horizontal, shell and tube heat exchanger subject to both boiling and condensation. The use of a short test section allows for a consistent flow pattern across the test section length which provides further insight into the true effect of EHD. It was found that the voltage polarity of the applied voltages influences the flow distribution. For the current geometry studied, it was found that positive polarity voltages tend to pull liquid away from heat transfer surface and that negative voltages tended to repel more liquid toward the heat transfer surface. Using this knowledge we were able to show that positive voltages were more effective for convective condensation heat transfer enhancement, whereas negative voltages were more effective for convective boiling heat transfer enhancement. A twofold enhancement of convective boiling heat transfer was achieved for positive voltages and a 4fold enhancement was achieved for negative voltages. Similar pressure drop penalties were seen for both cases, approximately twice that of the no EHD case. Furthermore, the effect of DC level, peak to peak voltage, frequency and duty cycle waveform parameters on convective boiling enhancement were studied to explore the range of controllability for the current set of flow parameters. It was found that these various waveform parameters can induce different flow patterns and consequently different heat transfer and pressure drop configurations. In general the heat transfer is enhanced by EHD, but different pressure drop penalties can be achieved for a given enhancement ratio using different waveforms. High heat transfer for relatively low pressure drop was achieved using either negative DC signals or 50%duty cycle pulse waveforms. In some cases the enhancement is quite little compared to the pressure drop, for example the zero DC level, varying peak to peak voltage data. It is suggested that in a system where the heat exchanger pressure drop due to EHD is more dominant than the system pressure drop, it may be possible to use EHD as a method of retarding the system rather than enhancing it thereby broadening the scope of controllability. Finally we showed the proof of concept of using DC EHD as a rapid control mechanism for the load conditions. Using -8kVDC the water side heat flux could be varied by approximately ±3.2 kW/m² within 5 seconds. As a comparison, the same experiment was repeated using the refrigerant flow rate to control the load. Response times were similar for both experiments and although the power required for the flow rate control was less, the minimal variability in flow parameters for the EHD control make it a more attractive method of load control.

Ketan Mulmuley

It is shown that black-box derandomization of polynomial identity testing (PIT) is essentially equivalent to derandomization of Noether's Normalization Lemma for explicit algebraic varieties, the problem that lies at the heart of the foundational classification problem of algebraic geometry. Specifically: (1) It is shown that in characteristic zero black-box derandomization of PIT for diagonal depth three circuits brings the problem of derandomizing Noether's Normalization Lemma, for the ring of invariants of any explicit linear action of a classical algebraic group of constant dimension, from EXPSPACE (where it is currently) to P. Next it is shown that assuming the Generalized Riemann Hypothesis (GRH), instead of the black-box derandomization hypothesis, brings the problem from EXPSPACE to quasi-PH, instead of P. Thus black-box derandomization of diagonal depth three circuits takes us farther than GRH here on the basis of the current knowledge. Variants of the main implication are also shown assuming, instead of the black-box derandomization hypothesis in characteristic zero, Boolean lower bounds for constant-depth threshold circuits or uniform Boolean conjectures, in conjunction with GRH. These results may explain in a unified way why proving lower bounds or derandomization results for constant-depth arithmetic circuits in characteristic zero or constant-depth Boolean threshold circuits, or proving uniform Boolean conjectures without relativizable proofs has turned out to be so hard, and also why GRH has turned out to be so hard from the complexity-theoretic perspective. Thus this investigation reveals that the foundational problems of Geometry (classification and GRH) and Complexity Theory (lower bounds and derandomization) share a common root difficulty that lies at the junction of these two fields. We refer to it as the GCT chasm. (2) It is shown that black-box derandomization of PIT in a strengthened form implies derandomization of Noether's Normalization Lemma in a strict form for any explicit algebraic variety. (3) Conversely, it is shown that derandomization of Noether's Normalization Lemma in a strict form for specific explicit varieties implies this strengthened form of black box derandomization of PIT and its various variants. (4) A unified geometric complexity theory (GCT) approach to derandomization and classification is formulated on the basis of this equivalence.

Vipul Goyal, Chen-Kuei Lee, Rafail Ostrovsky, Ivan Visconti

We propose the first black-box construction of non-malleable commitments according to the standard notion of non-malleability with respect to commitment. Our construction additionally only requires a constant number of rounds and is based only on (black-box use of) one-way functions. Prior to our work, no black-box construction of non-malleable commitments was known (except for relaxed notions of security) in any (polynomial) number of rounds based on any cryptographic assumption. This closes the wide gap existent between black-box and non-black-box constructions for the problem of non-malleable commitments. Our construction relies on (and can be seen as a generalization of) the recent non-malleable commitment scheme of Goyal (STOC 2011). We also show how to get black-box constructions for a host of other cryptographic primitives. We extend our construction to get constant-round concurrent non-malleable commitments, constant-round multi-party coin tossing, and non-malleable statistically hiding commitments (satisfying the notion of non-malleability with respect to opening). All of the mentioned results make only a black-box use of one-way functions. Our primary technical contribution is a novel way of implementing the proof of consistency typically required in the constructions of non-malleable commitments (and other related primitives). We do this by relying on ideas from the ``zero-knowledge from secure multi-party computation" paradigm of Ishai, Kushilevitz, Ostrovsky, and Sahai (STOC 2007). We extend in a novel way this ``computation in the head" paradigm (which can be though of as bringing powerful error-correcting codes into purely computational setting). To construct a non-malleable commitment scheme, we apply our computation in the head techniques to the recent (constant-round) construction of Goyal. Along the way, we also present a simplification of the construction of Goyal where a part of the protocol is implemented in an information theoretic manner. Such a simplification is crucial for getting a black-box construction. This is done by making use of pair wise-independent hash functions and strong randomness extractors. We show that our techniques have multiple applications, as elaborated in the paper. Hence, we believe our techniques might be useful in other settings in future.

Andrew Drucker

Given an instance of a hard decision problem, a limited goal is to compress that instance into a smaller, equivalent instance of a second problem. As one example, consider the problem where, given Boolean formulas $\psi^1, \ldots, \psi^t$, we must determine if at least one $\psi^j$ is satisfiable. An $\mathrm{OR}$-compression scheme for SAT is a polynomial-time reduction $R$ that maps $(\psi^1, \ldots, \psi^t)$ to a string $z$, such that $z$ lies in some “target” language $L'$ if and only if $\bigvee_j [\psi^j \in \mathrm{SAT}]$ holds. (Here, $L'$ can be arbitrarily complex.) AND-compression schemes are defined similarly. A compression scheme is strong if $|z|$ is polynomially bounded in $n = \max_j |\psi^j|$, independent of $t$. Strong compression for SAT seems unlikely. Work of Harnik and Naor [SIAM J. Comput., 39 (2010), pp. 1667--1713] and Bodlaender, Downey, Fellows, and Hermelin [J. Comput. System Sci., 75 (2009), pp. 423--434] showed that the infeasibility of strong OR-compression for SAT would show limits to instance compression for a large number of natural problems. Bodlaender et al. also showed that the infeasibility of strong AND-compression for SAT would have consequences for a different list of problems. Motivated by this, Fortnow and Santhanam [J. Comput. System Sci., 77 (2011), pp. 91--106] showed that if SAT is strongly OR-compressible, then $\mathsf{NP} \subseteq \mathsf{coNP/poly}$. Finding similar evidence against AND-compression was left as an open question. We provide such evidence: we show that strong AND- or OR-compression for SAT would imply nonuniform, statistical zero-knowledge proofs for SAT---an even stronger and more unlikely consequence than $\mathsf{NP} \subseteq \mathsf{coNP/poly}$. Our method applies against probabilistic compression schemes of sufficient “quality” with respect to the reliability and compression amount (allowing for tradeoff). This greatly strengthens the evidence given by Fortnow and Santhanam against probabilistic OR-compression for SAT. We also give variants of these results for the analogous task of quantum instance compression, in which a polynomial-time quantum reduction must output a quantum state that, in an appropriate sense, “preserves the answer” to the input instance. The central idea in our proofs is to exploit the information bottleneck in an AND-compression scheme for a language $L$ in order to fool a cheating prover in a proof system for $\overline{L}$. Our key technical tool is a new method to “disguise” information being fed into a compressive mapping; we believe this method may find other applications.

Helge Kragh

Ever since the famous Eddington-Dyson solar eclipse expedition in 1919, it has been known that massive bodies cause space (or rather space-time) to curve. This happens not only locally, in the vicinity of celestial bodies, but also on the largest possible global scale. Einstein's first cosmological model of 1917 represented the finite universe by the kind of 3D spherical space that had been familiar to mathematicians for more than half a century. According to Einstein, the constant curvature K and radius of curvature R were given by the average density ρ of matter in the universe by where G is Newton's gravitational constant. Although Einstein's model only survived to about 1930, curved space remained an element in most later cosmological models. The question to be decided by a combination of theory and observation was the size of the cosmic curvature, as expressed by the curvature constant k = R2K. In the Einstein universe, k = +1. The present consensus view, in part based on the inflationary scenario, is that we live in a flat or Euclidean space, corresponding to k = 0, which implies that the universe is infinite in extent. However, this is a view that can never be proved observationally, not even in principle. Whereas the reality of curved space belongs to the 20th century, as a mathematical hypothesis it was discussed many decades before Einstein. The first scientist who not only realized the possibility of a closed universe, but advocated it as a model of the real universe, is little known today. Few cosmologists have ever heard about the German astrophysicist Karl Friedrich Zöllner, who as early as 1872 argued that the universe is finite, in the sense that cosmic space is positively curved (Jaki 1969, Kragh 2012). Zöllner's remarkable cosmology based on non-Euclidean geometry deserves more than just a footnote in the annals of cosmological thought. Naturally, questions about the curvature of space could only be asked after the recognition, in the first half of the 19th century, that geometries other than Euclid's are possible. As early as about 1815, Karl Friedrich Gauss in Göttingen came to the conclusion that Euclidean geometry is not true by necessity but can be justified only empirically. According to an often repeated myth - but it is a myth - he attempted to test the validity of Euclidean geometry by measuring geodetically the sum of angles in a triangle extending between three mountain peaks in the state of Hanover (Breitenberger 1984). While Gauss anticipated non-Euclidean geometry, it was left to the Hungarian mathematician János Bolyai and, independently, his Russian colleague Nikolai Ivanovich Lobachevsky to establish geometrical systems different from the venerable one of Euclid. Of the two pioneers, Lobachevsky was the more empirically oriented. As he said in a paper of 1835, the truth of geometry “can only be verified, like all other laws of Nature, by experiment, such as astronomical observations” (Lobachevsky 1898). K F Zöllner, steel engraving from 1882. What Lobachevsky called “imaginary geometry” soon became known as hyperbolic geometry, characterized by a curvature constant k = −1 (and therefore an imaginary radius of curvature). Not only did he prove that in this kind of space the angle sum in a triangle always exceeds 180°, he also suggested that the geometry of physical space might be tested by considering stellar parallaxes. For example, while in Euclidean space the parallax of a star tends toward zero as its distance increases toward infinity, Lobachevsky showed that in hyperbolic space there is a minimum parallax for all stars irrespective of how far they are from the Earth. In his first paper on the new geometry, dating from 1829, he used a value of 1″.24 for the parallax of Sirius - three times as great as the real one - to conclude that space was flat to an approximation much closer than the error of measurement. Nonetheless, rather than concluding that space was Euclidean, he considered his calculations to be inconclusive. Perhaps, he speculated, a deviation from flat space would turn up in future measurements of much larger heavenly triangles. In a famous lecture of 1854, the young Göttingen mathematician Bernard Riemann completed and generalized the earlier ideas of Gauss, Lobachevsky and Bolyai. Emphasizing that curvature is an intrinsic property of space, he argued that although there is any number of possible geometries, there are only three that can represent physical space. These spaces of constant curvature correspond to the three values of the curvature constant, k = 0, ±1. Riemann paid particular attention to the case of a closed spherical space, pointing out that in such a space “we must distinguish between unboundedness and infinite extent.” A space of constant positive curvature “must necessarily be finite provided this curvature has ever so small a positive value” (Riemann 1873). A physicist as well as a mathematician, he speculated that the metrical structure of space on a microscopic scale might be of importance for the physics of atoms and molecules. On the other hand, he did not take an interest in the space of the astronomers. Questions about the global properties of space he dismissed as “idle questions”. Non-Euclidean geometry circulated slowly in the mathematical community, and even more slowly among physicists and astronomers. Only in the 1870s, in large measure due to popular lectures by Hermann von Helmholtz and William Clifford, did Riemann's ideas become generally known and seen as a vision of a possible geometrization of physics. Johann Karl Friedrich Zöllner (1834–1882) is today recognized for his contributions to astrophysics and, in particular, his pioneering work in astrophotometry (Koerber 1899, Hermann 1982). A skilled experimentalist and designer of instruments, in 1858 Zöllner invented an astrophotometer to measure the feeble light from stars and planets. In 1862 he moved to Leipzig, where he was appointed professor and established an astrophysical research programme, the first of its kind. In addition to his experimental work, he also made important studies of theoretical problems in astronomy and physics. These included electrodynamics, solar theory, sunspots and the theory of comets. In his Natur der Cometen from 1872 (figure 2) he developed an electrical theory of comets that for a period was widely admired. Title page of Zöllner's 1872 book on the nature of comets, including his proposal of a closed-space universe. Zöllner was a tireless advocate of Heinrich Weber's theory of electrodynamics based on a fundamental force law acting between hypothetical charged particles. Not only did Zöllner accept Weber's force law and associated atomistic theory, he also argued that it was of universal significance and valid for all terrestrial and cosmic phenomena. He suggested that it could be translated into a law of gravitation superior to Newton's, in the sense that the latter was merely a special case of Weber's. In Zöllner's extended version of Weber's theory, the interaction between two charged particles of opposite sign differed slightly, by a factor of 1.7 × 10−40, from the interaction between two particles of the same sign. Thus, a very small residual force would remain between two bodies, and this residual electric force he identified with the gravitational attraction (Zöllner 1882). In effect, he recognized the later so famous (and still unexplained) ratio between the gravitational and the electromagnetic interaction, given by the pure number Fgrav/Fem ≅ 10−40. Among other things, he used his electro-gravitational theory in an attempt to explain the anomalous motion of Mercury's perihelion, one of the major problems in astronomy until it was finally solved by Einstein. Natur der Cometen (Zöllner 1872) was a remarkable work in more than one sense. The major part of the 600-page book was not about comets, but instead a strange mixture of philosophy of science and unconstrained, chauvinistic charges of plagiarism. Zöllner's main targets were British scientists, including luminaries such as William Thomson and Charles Darwin, but he also attacked Helmholtz, one of the most powerful men in German science. The book aroused a storm of controversy and had the effect that Zöllner became increasingly marginalized as a scientist. Although much of the last decade of Zöllner's troubled life was occupied with philosophical speculations, spiritualism and endless controversies, he continued doing scientific work. Thus, he developed a theory of the origin of the Earth's magnetism according to which the magnetism was due to electrical currents in the fluid core of the Earth. Natur der Cometen included a chapter on “The Finitude of Matter in Infinite Space” in which Zöllner offered an original solution to Olbers' paradox in terms of a universe of constant positive curvature (Jaki 1969). In his systematic discussion of the finite versus the infinite in the universe, he assumed, for the sake of discussion, that there is only a finite amount of matter in the world. He then argued that in an unbounded (and therefore infinite) Euclidean space any finite amount of matter would evaporate and dissolve to zero density in an infinity of time. Given the actual existence of matter of non-zero density, he concluded that either is space finite or the universe has only existed for a limited period of time. Unwilling to accept the latter hypothesis, he suggested that Riemann's geometry might provide the key that would unravel the secrets of the universe and dissolve the problems of a materially finite universe: “It seems to me that any contradictions will disappear … if we ascribe to the constant curvature of space not the value zero but a positive value, however small … The assumption of a positive value of the spatial curvature measure involves us in no way in contradictions with the phenomena of the experienced world if only its value is taken to be sufficiently small.” In this way he made Olbers' paradox disappear without having to assume a limitation of either cosmic time or space. While he noted with satisfaction that energy conservation would apply to his finite material universe, he did not address the problem caused by the increase of entropy in a spatially finite but temporally infinite universe. Clearly inspired by Riemann, and happy to admit the inspiration, Zöllner further speculated that curved space was dynamically active, in the sense of determining the laws of Nature. Not even the divine force law of Weber was true a priori but somehow of cosmological origin, a speculation that bears some similarity to the later Mach's principle. And Zöllner went further than Riemann: whereas the Göttingen mathematician had declared that physics represented the “domain of another science”, the Leipzig astrophysicist maintained that the science of the physical world belonged entirely to the field of Riemann's investigations. Later in the century a few mathematicians attacked the problem of Mercury's anomalous precession by assuming space to be non-Euclidean. In 1885–1886 Wilhelm Killing and Carl Neumann derived orbits for Mercury moving in spherical space, and in 1902 Otto Liebmann did the same in the case of hyperbolic space. Zöllner's innovative cosmological speculations attracted some attention in German philosophical circles, but were ignored by most physicists and astronomers. Not only was cosmology considered a somewhat disreputable field that scarcely belonged to science, the idea of a closed space was also widely associated with the (even more disreputable) notion of a fourth space dimension. To understand the lack of scientific response to Zöllner's universe, one must take into account his controversial ideas of a fourth dimension as the site of spiritual phenomena (Zöllner 1880). In 1877, after meeting the chemist William Crookes in London, Zöllner turned wholeheartedly to spiritualism (Treitel 2004). Convinced of the reality behind spiritualist manifestations, he investigated them in great detail, attempting to integrate the spirits with both Weberian physics and his own highly unorthodox version of Christian theology. The first major result of his efforts in this area of unconventional research was an elaborate Transcendental Physics published in 1878 and translated into English two years later (Zöllner 1880). As Zöllner saw it, the project of a transcendental physics including both material and spiritual phenomena was but a natural extension of the astrophysical project of accommodating terrestrial and celestial phenomena within the same theoretical framework. It was a strictly scientific project. Not satisfied with simply accepting the spirits of deceased persons, as they appeared in séances, Zöllner argued that they were visitors from a hidden fourth dimension of space. During the last decades of the 19th century, beliefs of this kind were widespread; Zöllner only took them more seriously than most. It was sometimes contended that if our space is curved, it must be contained in a flat space of a higher dimension, in the same way that a 2D space is embedded in our 3D space. Although 4D “hyperspace” was often mixed up with ideas of non-Euclidean geometry, in reality there is no connection between them. William Clifford dismissed the connection as groundless, as did other mathematicians. A curved space does not need to be curved “in” another space. Zöllner's belief in a spiritual fourth dimension received inspiration from his knowledge of non-Euclidean geometry, which he sometimes used for purposes of illustration, but it did not depend on it. Nor did his claim of a fourth dimension rely exclusively on his belief in a spiritual world, for he held the claim even before his conversion to spiritualism. In a book of 1876 he argued that a fourth dimension was needed for epistemological reasons, in order to understand the symmetry between 3D objects, such as left- and right-handed gloves. The phenomenal objects in our 3D world must be “projections of objects in a space of four dimensions” (Zöllner 1876). He considered the insight to be of revolutionary importance to science as it heralded a change in the world view on a scale comparable to the one Copernicus had initiated. His colleagues in physics and astronomy were not immune to the fascination of the fourth dimension, but they rejected his interpretation of it. Zöllner was the only scientist in the 19th century who found it probable, and not merely possible, that space is curved in accordance with Riemann's geometry. He was also the only one to use the hypothesis to solve a cosmological problem, namely Olbers' paradox of the dark night sky. From the late 1870s, non-Euclidean geometry attracted increasing interest among mathematicians and philosophers and a few astronomers followed suit. One of them was the Irishman Robert Stawell Ball, Royal Astronomer of Ireland and from 1892 professor of astronomy and geometry in Cambridge. Without committing himself, he suggested that parallax investigations might show space to be non-Euclidean. Characteristically, his guarded preference for a closed cosmic space turned up in his popular publications only. In The High Heavens of 1893, he expressed sympathy with the hypothesis, vaguely suggesting that a finite universe was more satisfactory than the consensus view of an infinite space filled with stars. Another astronomer of distinction, the American Simon Newcomb, also dealt with the possibility of a closed-space universe, if only cautiously and apparently without believing in it. In the first edition of his classical text Popular Astronomy, he discussed whether the heat radiated by the Sun and stars would be lost forever. Noting that this would not be the case in a spherical universe, he nonetheless denied taking a Riemannian cosmic space seriously. It was “too speculative to admit of discussion” he said (Newcomb 1878). He followed up on the subject in correspondence with the philosopher-scientist Charles S Peirce, who was much more sympathetic to curved space. Indeed, for a decade Peirce defended the idea enthusiastically, suggesting various astronomical methods by means of which the curvature might be measured. Newcomb advised him to calm down: “The task of getting the scientific world to accept any proof that space is not homoloidal [flat] is hopeless, and you could have no other satisfaction than that of doing a work for posterity” (Eisele 1957). The most elaborate pre-relativistic attempt to link astronomy with non-Euclidean geometry appeared in 1900, in a paper by the 26-year-old German astrophysicist Karl Schwarzschild (published in translation in 1998). I cannot go into the substance of this work, except noting its main results concerning the possible curvature of space. In the case of a hyperbolic space, Schwarzschild found R > 4×106 AU, and for the closed space he estimated a lower bound of R > 108 AU. Although he saw no way to go beyond this rather indefinite conclusion, from a philosophically point of view he preferred a closed universe, which he thought was more “satisfying to reason” (Schwarzschild 1998). So did Einstein, 17 years later. A knot experiment Zöllner made with the American medium Henry Slade. The ends of the cord were sealed together, yet Slade's “spirits” tied several knots in the cord. To Zöllner (1880), it proved the reality of a fourth space dimension. Following up on Schwarzschild's analysis, Paul Harzer at the University of Kiel argued that the universe might well consist of a finite stellar system located in a larger spherical space. He estimated the size of the entire universe by the time it would take a ray of light to circumnavigate it. For this journey round the world, Harzer (1908) gave the figure 8700 years. Neither Schwarzschild nor Harzer seems to have been aware of Zöllner's earlier work, at the time long forgotten. Ever since Lobachevsky, non-Euclidean geometry was associated with astronomy and yet it was a subject most astronomers were to were for one of them that space was not considered part of science. The motion of celestial bodies was the of not the space in which the motion took Newcomb for the of astronomers he among both and to of space as an in To interest in the astronomical community, of space would have to be or for problems of astronomical on both While astronomers realized that the curvature of space was they also realized that the kind of bound for the curvature that measurements was to distinguish curved from flat space. Given this no that they saw no to the Euclidean space that had them so well in the space be curved, the curvature radius would be so large that for all purposes it was infinite - that space could be considered So Among the few problems of cosmological that might have astronomers to curved space was the question of whether space is finite or infinite in extent. The question might be seen as merely as it often but it had such as Olbers' only in one Zöllner's discussion of was the problem by that the stellar universe might be closed in accordance with Riemann's His solution to the most of Olbers' in terms of and saw no between the dark night and an infinity of stars. The main for the to the of space non-Euclidean was just they had no need for the

Amit Sahai

One of the most fundamental goals in cryptography is to design protocols that remain secure when adversarial participants can engage in arbitrary malicious behavior. In 1986, Goldreich, Micali, and Wigderson presented a powerful paradigm for designing such protocols: their approach reduced the task of designing secure protocols to designing protocols that only guarantee security against “honest-but-curious” participants. By making use of zero-knowledge proofs, the GMW paradigm enforces honest behavior without compromising secrecy. Over the past two decades, this approach has been the dominant paradigm for cryptographic protocol design, based on zero-knowledge protocols based on computational hardness assumptions. In this work, we describe a new general paradigm/protocol compiler for secure protocol design known as the IPS compiler, that departs considerably from the GMW framework, and provides a method for obtaining efficient protocols with information-theoretic security guarantees in settings where appropriate channels exist. This new approach also reduces the task of designing secure protocols to designing protocols that only guarantee security against honest-but-curious participants. However, the new approach avoids the use of zero-knowledge proofs, and instead makes use of multi-party protocols in a much simpler setting - where the majority of participants are completely honest (such multi-party protocols can exist with information-theoretic security guarantees without assuming any special channels). The IPS paradigm yields protocols that rely on Oblivious Transfer channels (OT) as a building block. This offers a number of advantages in generality and efficiency. In contrast to the GMW paradigm, by avoiding the use of zero-knowledge proofs, the IPS paradigm is able to treat all of its building blocks as “black boxes”. This allows improvement over previous results in the area of secure computation. In particular, the IPS compiler yields conceptually simpler and more efficient ways for basing unconditionally secure cryptography on OT and other noisy channels; more efficient protocols for generating a large number of OTs using a small number of OTs; and secure and efficient protocols which only make a blackbox use of cryptographic primitives or underlying algebraic structures in settings where no such protocols were known before.

Yan Zhu, Shanbiao Wang, Hongxin Hu, Gail‐Joon Ahn · 5 authors

A hybrid cloud is a cloud computing environment in which an organization provides and manages some internal resources and has others provided externally. However, this new environment could bring irretrievable losses to the clients due to a lack of integrity verification mechanism for distributed data outsourcing. To support scalable service and data migration, in this paper we address the construction of a collaborative integrity verification mechanism in hybrid clouds where we consider the existence of multiple cloud service providers to collaboratively store and maintain the clients' data. We propose a collaborative provable data possession scheme adopting the techniques of homomorphic verifiable responses and hash index hierarchy. In addition, we articulate the performance optimization mechanisms for our scheme and prove the security of our scheme based on multi-prover zero-knowledge proof system, which can satisfy the properties of completeness, knowledge soundness, and zero-knowledge. Our experiments also show that our proposed solution only incurs a small constant amount of communications overhead.

Jinguang Han, Willy Susilo, Yi Mu, Jun Yan

No abstract is available for this record.

Nan Guo, Tianhan Gao, Bin Zhang

It is important that during the execution of a business process built from composable Web services from multiple domains, the component service be able to verify the identity of the user to check it has the required permissions for accessing the services, while at the same time identity attributes need to be protected properly as they can be target of attacks. In such context, we propose a privacy-preserved multi-domain identity attributes verification model BPVrfy. It extends federate identity management with support for multiple identity verification policies and privacy enhancement. Identity attributes verification process is partitioned into three sub-procedures consisting of attribute provision, federation enrollment and attributes transfer, and then a series of protocols based on cryptographic schemes is proposed respectively. BPVrfy adopts Perdersen Commitment, Zero-Knowledge Proof of Knowledge, BGLS Aggregate Signature and Certificate-Based Signature (CBS) cryptographic schemes together to give a privacy-preserved federate identity attributes verification solution for multi-domain Web services-based business processes.