Blockchain Papers

Stéphane K. Lintner, Oscar P. Bruno

We deal with the general problem of scattering by open-arcs in\ntwo-dimensional space. We show that this problem can be solved by means of\ncertain second-kind integral equations of the form $\\tilde{N}\n\\tilde{S}[\\varphi] = f$, where $\\tilde{N}$ and $\\tilde{S}$ are first-kind\nintegral operators whose composition gives rise to a generalized Calder\\'on\nformula of the form $\\tilde{N} \\tilde{S} = \\tilde{J}_0^\\tau + \\tilde{K}$ in a\n{\\em weighted, periodized} Sobolev space. The $\\tilde{N} \\tilde{S}$ formulation\nprovides, for the first time, a second-kind integral equation for the open-arc\nscattering problem with Neumann boundary conditions. Numerical experiments show\nthat, for both the Dirichlet and Neumann boundary conditions, our second-kind\nintegral equations have spectra that are bounded away from zero and infinity as\n$k\\to \\infty$; to the authors' knowledge these are the first integral equations\nfor these problems that possess this desirable property. Our proofs rely on\nthree main elements: 1) Algebraic manipulations enabled by the presence of\nintegral weights; 2) Use of the classical result of continuity of the Ces\\`aro\noperator; and 3) Explicit characterization of the point spectrum of\n$\\tilde{J}^\\tau_0$, which, interestingly, can be decomposed into the union of a\ncountable set and an open set, both tightly clustered around -1/4. As shown in\na separate contribution, the new approach can be used to construct simple\nspectrally-accurate numerical solvers and, when used in conjunction with\nKrylov-subspace solvers such as GMRES, gives rise to dramatic reductions of\nKrylov-subspace iteration numbers vs. those required by other approaches.\n

Nivedita Datta

In many applications, the password is sent as cleartext to the server to be authenticated thus providing the eavesdropper with opportunity to steal valuable data. This paper presents a simple protocol based on zero knowledge proof by which the user can prove to the authentication server that he has the password without having to send the password to the server as either cleartext or in encrypted format. Thus the user can authenticate himself without having to actually reveal the password to the server. Also, another version of this protocol has been proposed which makes use of public key cryptography thus adding one more level of security to the protocol and enabling mutual authentication between the client & server.

Sylvain Heraud

CertiCrypt is a framework that enables the machine-checked construction and verification of cryptographic proofs in the Coq proof assistant. CertiCrypt instruments the code-based game-based approach to cryptographic proofs, and builds upon many areas, including probability and complexity theory, algebra, semantics of programming languages, and program optimizations. In this thesis, we illustrate the application of CertiCrypt on two examples: the Hashed ElGamal encryption scheme and zero-knowledge protocols. Like previous case studies in CertiCrypt, these examples demonstrate the feasibility of formalizing complex cryptographic proofs. However, using CertiCrypt requires a high level of expertise in Coq, and is time consuming. In order to ease the adoption of formal proofs by the cryptographic community, we develop a semi-automated tool, called EasyCrypt, for elaborating security proofs of cryptographic systems from proof sketches. Proof sketches are checked automatically using SMT solvers and automated theorem provers, and then compiled into verifiable proofs in the CertiCrypt framework. We illustrate the application of EasyCrypt with two examples: the Hashed ElGamal encryption system, and the Cramer-Shoup encryption system. Finally, we extend the language of CertiCrypt with a formalization of polytime functions.

Cándido Caballero‐Gil, Pino Caballero‐Gil, Jezabel Molina‐Gil

ABSTRACT A mobile ad hoc network (MANET) is a type of wireless network without any infrastructure, where nodes must adapt to the changing dynamic situations that result from their mobility. Because of the decentralization of nodes and the security needs of communications, management of MANETs must be self‐organized, which is a major research challenge. In order to cope with the intrinsic properties of MANETs, a new decentralized management system for MANETs called Self‐organizing Life Cycle Management (SLCM) is here fully described and evaluated. Regarding security, node authentication is the most critical component of access control in any network and, in particular, in MANETs. Broadcasting is also a fundamental data dissemination mechanism in these networks. Both aspects have received special attention when defining the proposed SLCM system. In particular, both a strong access control algorithm, based on the cryptographic paradigm of zero‐knowledge proofs, and a three‐step broadcast protocol are here defined. This work includes the performance evaluation of the scheme, and the obtained experimental results show that SLCM significantly improves both the quality and the security of life cycle management of self‐organized MANETs. Copyright © 2012 John Wiley & Sons, Ltd.

Atsuko Miyaji, Mohammad Shahriar Rahman

Privacy-preserving set operations are useful for many data mining algorithms as building tools. Protocols for privacy-preserving set operations have considered semi-honest and malicious adversarial models in cryptographic settings, whereby an adversary is assumed to follow or arbitrarily deviate from the protocol. Semi-honest model provides weak security requiring small amount of computation, on the other hand, malicious model provides strong security requiring expensive computations like homomorphic encryption. However, efficient computation of such set operations are desirable for practical implementations. In this paper, we build efficient and private set operations avoiding the use of expensive tools like homomorphic encryption, zero knowledge proof, and oblivious transfer. Our protocol is constructed in game-theoretic model. In other words, instead of being semi-honest or malicious, the parties are viewed as rational and are assumed (only) to act in their self-interest. We show that our protocol satisfies computational Nash equilibrium.

M. Sowmyavarshini, D. Palanikkumar, Gunjan Rathi

Cloud computing dynamically provides high quality cloudbased secure services and applications over the internet. The efficient sharing of secure cloud storage services (ESC) scheme which allows the upper-level user to share the secure cloud storage services with multiple lower-level users. In hierarchical identity-based architecture, the sender needs to encrypt a file only once and store only one copy of the corresponding ciphertext in a cloud. The lower-level user needs to decrypt a file which will increase the computational overhead, because the lower-level user does not perform any partial decipherment. In this paper, we propose a Trapdoor commitment scheme that enables a lower-level user to send a short trapdoor to the cloud service provider before retrieving files. This scheme allows the CSP to participate in the partial decipherment, so as to reduce computational overhead on the users without leaking any information about the plaintext. If a lower-level user wants to retrieve a file with limited bandwidth, CPU and memory, the trapdoor which will largely helps to reduce computational power.

Fred Powledge

Climate change—fears of it; predictions about it; proposed reactions to it; and in some cases, denials of it—is a momentous issue for humanity, and it promises to become even more important. However, despite its importance—and mountains of scientific research on the topic—real progress by those with the means to address climate change has been slow in coming. The warming climate, with its accompanying intense weather, rising seas, and wrenching changes in agriculture, human health, and ecosystems in general, is not a recent discovery. Scientists and policymakers have been talking about it for decades. Climate scientists have produced reams of information about the change that is upon us—some showing that the shift is well under way, some offering ideas about how to cope with it by mitigating its effects or by adapting to it. Scientists are starting to develop the tools necessary to discover links between global change and specific local events, such as floods and droughts. Much of the US-based research is directed at people who make political decisions: members of Congress, the president, state legislators, municipal officials. But whereas the flow of information from scientists has been copious, the response from policymakers, including those at the topmost positions in government, has been minuscule. Interest in preparing for climate change seems to have been superseded by concerns about the economy. But the problems of a changed climate march on (see National Research Council definitions box), and at some point, policymakers will have to deal with them. As far back as 1978, Congress passed the National Climate Program Act in response to a need “to assist in the understanding and response to natural and man-induced climate processes and their implications.” The legislation stated that “Congress finds and declares” that “an ability to anticipate natural and man-induced changes in climate would contribute to the soundness of policy decisions in the public and private sectors,” and that “the United States lacks a well-defined and coordinated program in climate-related research, monitoring, assessment of effects, and information utilization.” Today, after dozens of data-heavy reports on climate change, bolstered by the work of the Intergovernmental Panel on Climate Change (IPCC), the crisis remains unaddressed, in large part because the issue has become a partisan arguing point—increasingly so as a presidential election looms. In April 2011, the House of Representatives considered action stating that “Congress accepts the scientific findings… that climate change is occurring, is caused largely by human activities, and poses significant risks for public health and welfare.” The national legislators voted the proposition down 240 to 184, largely along party lines. Scientists who study climate change, then, are left with the following question: How do we communicate in a meaningful way with policymakers? Climate change, in the United States and elsewhere, covers most areas of the human experience. A report from the US National Research Council lists the following areas of concern: changes in the climate system; sea-level rise and its effects on the coastal environment; freshwater resources; ecosystems, ecosystem services, and biodiversity; agriculture and aquaculture; public health; cities and the “built environment”; transportation systems; energy systems; solar radiation management; national and human security; and climate policy. First of all, says Pamela A. Matson, an interdisciplinary earth scientist at Stanford University, scientists should not tell policymakers what to do. Matson chaired one of four expert panels charged by the US National Academies in 2009 with studying climate change and recommending responses to it. The panels—Limiting the Magnitude of Future Climate Change, Adapting to the Impacts of Climate Change, Informing an Effective Response to Climate Change, and Advancing the Science of Climate Change—each produced extensive reports. Together, these reports and a summary volume form a solid tutorial on the challenges facing the nation (see For more information). Matson headed the Advancing the Science of Climate Change panel. “We can't do much about politics,” said Matson in an interview, “other than to keep reminding people that there is a huge amount of evidence about climate change, its causes, and the risks associated with it. Decisionmakers of all sorts will need to decide if they want to take the risks and expose future generations to even greater risks, but scientists can do our best to provide the best and most clear information about those risks and uncertainties. We can also help by providing viable options for reducing those risks—options that make sense from social, economic, technical, and environmental perspectives. The Advancing report calls for more research designed to develop such options and thus support decisionmakers who want to respond to the risks of climate change by limiting it and adapting to it.” In practically all of the heavyweight studies of climate change, including those in the National Academies quartet, the panelists assumed that the federal government is the logical leader in climate policymaking, if only because climate does not respect local boundaries (or international ones either). But there are scant signs of leadership from federal officials, and there is active opposition to any climate action (or even the notion that climate change exists) among some national legislators. Progress at the federal level, says Peter Raven, cochair of the National Academies panel Informing Decisions and Actions, is missing. His panel recommended that the federal government create “comprehensive, robust, and credible information systems to inform climate choices and evaluate their effectiveness.” “My impression,” said Raven recently, “is that it hasn't happened. The United States is the only nation in the world where serious doubt is expressed about the scientific conclusion that the climate is warming rapidly and that human beings are the principal underlying factor. That kind of anti-intellectualism can only hurt as we try to maintain our standing in science and technology against some very stiff competition internationally.” Robert Fri, visiting scholar at Resources for the Future, chaired the Limiting the Magnitude of Future Climate Change panel, which recommended “a framework of national goals and policies” to limit greenhouse gases. Asked about the report's reception, he replied, “Policy attention has been focused on the economy recently. Not much has happened on the climate front as a result.” So the search for leadership has turned elsewhere—to local, state, and regional governments and private organizations. Several states have undertaken serious studies of climate change problems, many of them as a result of gubernatorial executive orders issued a few years ago, when climate change was considered less controversial. Some went a step further and set up commissions to recommend legislative action. The results of those efforts have been mixed; the economic crisis has sapped much of the climate change energy of local, as well as national, politicians. Arizona's Policy on Climate Change, instituted on 2 February 2010, under Governor Jan Brewer, seeks to reduce greenhouse gas emissions “while maintaining Arizona's economic growth and competitiveness.” Yet in the same executive order that established the policy, Brewer pulled her state out of a promising regional effort, the Western Climate Initiative, to limit the gases. The 15-member commission created by Brewer's executive order included representatives of electric power, manufacturing, and mining companies, but no scientists. Arctic sea ice reaches its annual minimum in September. The satellite images above show September Arctic sea ice in 1979 (upper panel), the first year these data were available, and in 2007 (lower panel). Source: US Global Change Research Program (www.globalchange.gov). For a free download of the National Academies 2009 expert panel reports and a summary volume, among other reports on climate, go to www.nap.edu. A 1990 law created the National Climate Assessment, which evaluates federal global research programs. The most recent assessment was in 2009; to see an outline of the forthcoming 2013 report, visit http://globalchange.gov/what-we-do/assessment. Information on climate research may be found through the US Global Change Research Program Web site, at http://globalchange.gov/. The Pew Center on Global Climate Change publishes the “Climate Change 101” series, available at www.pewclimate.org/globalwarming-basics/climate_change_101. For detailed state reports on plans and recommendations for adaptation, see Massachusetts's at www.mass.gov/eea/docs/eea/energy/cca/eea-climate-adaptation-report.pdf. For a critical look at America's willingness to adapt to climate change, see Robert Repetto's 2008 report for the Yale School of Forestry and Environmental Studies at http://environment.yale.edu/publication-series/climate_change/5790. The Colorado Climate Project created a blue-ribbon action panel in 2007 that, a year later, produced 70 recommendations for reducing greenhouse gas emissions and preparing for the coming changes. The panel's efforts appear to have been received favorably by policymakers. Texas, beset by wildfires in 2011 that some experts linked to climate change, has no state adaptation plan, according to a survey by the Pew Center on Global Climate Change. Texas leads the states in carbon dioxide emissions. In Connecticut, the Governor's Steering Committee on Climate Change says that it is “working with stakeholders” and “assessing the impacts of climate change.” However, the committee's Web site devotes approximately half of its space to thanking the company that designed its logo. Massachusetts has made a more strenuous effort. In September 2011, the state sent a report to its legislature in which the expected impacts were analyzed and suggestions were made for reactions to them. The proof of the pudding in Massachusetts, as in the nation as a whole, lies in what happens after the recommendations go to the policymakers. In the Bay State, that would include the office of Frank I. Smizik, the chair of the House Committee on Climate Change. Smizik believes that climate change is going to affect “every corner of our lives,” is already creating problems, and is “one of the most complex and interrelated problems we face. And that makes it even more of a challenge to confront.” In an interview, the legislator praised the state's framework report both for its “long-term and far-reaching strategies” and for the “small, incremental improvements we can make at little or no cost. This aspect of the report makes the necessary task of climate adaptation seem more feasible.” Does this mean that Massachusetts's policymakers will rush to enact laws to deal with the well-documented menace? “Ideally, the need to adapt to climate change will be taken seriously, and these strategies will be swiftly transformed into reality in Massachusetts,” said Smizik. “Realistically, it won't be that easy. My job as the Chair of the House Committee on Global Warming and Climate Change is to advocate for the strategies that I think are not only most effective but also the most politically feasible at this time. I could see some of the more short-term, cost-effective strategies making progress in the State House as legislative packages. Meanwhile, some strategies will be directly implemented by state agencies. “I feel these issues are very pressing and they warrant our immediate attention. But… the legislating and governing process takes time, with good reason. The release of this adaptation report is an important step for our state, but it's hard to say how quickly or slowly these adaptation measures will become law. The economic climate is such that legislators are very focused on job creation and the like, and environmental issues are often pushed to the back burner in this situation.” The state of Washington is another place where policymakers take climate change seriously. Hedia Adelsman is the director of the state's Department of Ecology. Her predecessor in that job was Christine Gregoire, who went on to become the state's attorney general and then governor. Adelsman credits Gregoire with helping move climate awareness into action. Also, the University of Washington produced an exhaustive examination of climate change and ways to react to it that has served as a vital resource for legislators and other policymakers. Within 50–100 years, 2400 miles of major roadway are projected to be inundated by sea-level rise in the Gulf Coast region. The map shows roadways at risk in the event of a sea-level rise of about 4 feet, which is within the range of projections for this region in this century under medium- and high-emissions scenarios. In total, 24 percent of interstate highway miles and 28 percent of secondary road miles in the Gulf Coast region are at elevations below 4 feet. Source: US Global Change Research Program (www.globalchange.gov). Even though Washington is more environmentally conscious than most other states, economic troubles have hampered action on the climate front. “The conversation is not as active as it used to be,” said Adelsman in an interview, “[for] a couple of reasons: One of them—no surprise—is all the budget problems that the state is facing. And when you talk about the impact of climate change, people really see it as in the future. And right now we have all these urgent problems facing us. Some of the impacts that would be due to climate change… people don't see as something that's happening now. They see it as happening a little bit more in the future. So they feel like they can get back to it later… But the communication continues. “It all depends on how you describe it,” she said. “If you are describing the problem as a water-availability issue—if we are going to face a major issue with water available for irrigation; for municipal, for our fish, the salmon—you get people to listen. If you talk about it as global warming, it's immediately, ‘go away.’ “It's kind of sad to not call it by what it is, but it's much easier to communicate with the public and with the policymaker if you put it in these terms.” Some, including the authors of the National Research Council's panel Advancing the Science of Climate Change, think that a likely source of federal leadership can come, with a few modifications, from an existing organization: the US Global Change Research Program (USGCRP), which was created in 1989 as a presidential initiative by George H. W. Bush. USGCRP coordinates and integrates the global change work of 13 agencies, from the US Department of Agriculture to the US Department of Defense to the US Environmental Protection Agency and the Smithsonian Institution. Thomas Armstrong, of the White House Office of Science and Technology Policy, is USGCRP's executive director. In an interview, he said that he certainly agreed with the panels' findings. “But the real challenge comes not when you recommend strategic changes but when you get down to the nuts and bolts of implementing programs.” One potential obstacle, he said, could come if 13 agencies, which together receive $2.8 billion in global change research funds, are asked not only to funnel their work through a single office—his—but are made to redirect their agencies' funding as well. “If we were to take this level of enterprise and now say that it is no longer just coordinated but actually run out of my office, with all the resources coming to my office, that would be a big change in our collective way of doing to say the said is the 13 agencies, and the 13 are The of 13 them and a of leadership of this I would be that in their we would be the and of 13 federal who their research and to 13 agencies' In we would be the USGCRP out of what makes this program so the Science in climate information to policymakers. one is the climate change who can of all science in the of some is the of of scientific which scientists by their as does the in of such as very out of out of very than out of and so deal with communication such as these and many there has a of or for a can be government agencies, such as the that produced the state action or state such as Hedia in and federal such as the USGCRP they can be such as the regional Climate Science that were established in 2009 by the US Department of the The are by the US and by one or more significant of communication is by private and the Pew Center on Global Climate Change, which has been to and information on climate Climate an of and a for natural systems in the face of climate change.” The which a large of for for adaptation, dozens of studies from The appear to be some in scientific information into the of those who already want to it in their program director at the Climate for the part of a regional program run by the National and says that it that are more with decisionmakers much to the in of decisions that may be to scientific for something more to We certainly people who are out scientific information to make decisions that help them deal with of these decisions to the that has the region for years and are vital to policymakers who deal with water does a of its when public and private including a to a are also for scientific about adaptation and a then, is on the that climate change is important. are who for one or climate or climate change as something they really need to more about into their it's because a to attention to of the US Department of the have been under orders now to make climate change part of their it's because an like their is to the impacts of climate, and they want to more so they can to address this it's because an or government has a climate impact that them into The is an of as is in the United States and for how are projected to become more A so that it is years would other year or more by the of the century under the Source: US Global Change Research Program (www.globalchange.gov). But on many other the science of climate change has a much was one of states that active in the issue of climate change State and a the on Global Climate Change and it with the problems of global warming, as well as with into ways to the and with the potential of carbon The commission for years and up with the of that time, the legislature to the commission to its State who was cochair of the now says that the effort. in the way of the scientific evidence and any for doing about a she said in an “We a from the with the of so They all up and to recommend of We a very large and it was so it was to Even with she said, that make it out of her at the As the climate that are to Source: US Global Change Research Program (www.globalchange.gov). says that opposition to progress from and such as the and who of the US are major of and “It was she said. “I could get an passed that that our state the impact of climate change and make recommendations as to policy changes and other even any to deal with I that we would be that climate change is an issue in will see little to no to address climate change the leadership is in This is we are the most in the to sea-level she said. In the state is for and has also and said, “We are one of the of greenhouse at in the than many that the state has to a of and has its carbon The for those measures was For climate change legislation to on its she said, “I we will need federal

Yanbin Sun, Lize Gu, Sihan Qing, Shihui Zheng · 5 authors

利用Cha-Cheon 的基于身份的签名方案提出了一个可证安全的基于身份的可验证加密签名(verifiablyencrypted signature,简称VES)方案,并利用该方案和基于身份的代理可验证加密签名(proxy verifiably encryptedsignature,简称PVES)方案提出了一个新颖的多元合同签署协议.信息交换过程中,原始签名者或代理签名者分别利用VES 或PVES 实现承诺消息的交换与认证,并未使用复杂的零知识证明系统,从而有效避免了大量运算.当争议发生时,可信第三方从VES 或PVES 中恢复出有效的合同签名,以保证签署者的公平性.安全性分析结果表明,协议满足不可否认性、时效性以及公平性.;Utilizing the Cha-Cheon’s identity-based signature scheme, a provably secure identity-based verifiably encrypted signature (VES) scheme is proposed. Utilizing the proposed scheme and identity-based proxy verifiably encrypted signature (PVES) scheme, a novel multiplex contract signing protocol is also proposed. The original signer or proxy signer uses VES or PVES to realize the interaction and certification of the commitment message in the information exchange process. The proposed scheme does not need the zero-knowledge proof and excessive computation. An optimized trusted third party who participates in the protocol extracts the formal signature from the VES or PVES only when problem occurs. The performance analysis results show that the scheme satisfies non-repudiation, timeliness and fairness.

Анатолій Кулага

The paper contains main concepts of the interactive proof theory and suggests zero-knowledge proof of Diffie–Hellman problem solution with bilinear maps.

B. Bruhn

Silicon as a mono-crystalline bulk semiconductor is today the predominant material in many integrated electronic and photovoltaic applications. This has not been the case in lighting technology, since due to its indirect bandgap nature bulk silicon is an inherently poor light emitter.With the discovery of efficient light emission from silicon nanostructures, great new interest arose and research in this area increased dramatically.However, despite more than two decades of research on silicon nanocrystals and nanowires, not all aspects of their light emission mechanisms and optical properties are well understood, yet.There is great potential for a range of applications, such as light conversion (phosphor substitute), emission (LEDs) and harvesting (solar cells), but for efficient implementation the underlying mechanisms have to be unveiled and understood.Investigation of single quantum emitters enable proper understanding and modeling of the nature and correlation of different optical, electrical and geometric properties.In large numbers, such sets of experiments ensure statistical significance. These two objectives can best be met when a large number of luminescing nanostructures are placed in a pattern that can easily be navigated with different measurement methods.This thesis presents a method for the (optional) simultaneous fabrication of luminescent zero- and one-dimensional silicon nanostructuresand deals with their structural and optical characterization.Nanometer-sized silicon walls are defined by electron beam lithography and plasma etching. Subsequent oxidation in the self-limiting regime reduces the size of the silicon core unevenly and passivates it with a thermal oxide layer.Depending on the oxidation time, nanowires, quantum dots or a mixture of both types of structures can be created.While electron microscopy yields structural information, different photoluminescence measurements, such as time-integrated and time-resolved imaging, spectral imaging, lifetime measurements and absorption and emission polarization measurements, are used to gain knowledge about optical properties and light emission mechanisms in single silicon nanocrystals.The fabrication method used in this thesis yields a large number of spatially separated luminescing quantum dots randomly distributed along a line, or a slightly smaller number that can be placed at well-defined coordinates. Single dot measurements can be performed even with an optical microscope and the pattern, in which the nanostructures are arranged, enables the experimenter to easily find the same individual dot in different measurements.Spectral measurements on the single dot level reveal information about processes that are involved in the photoluminescence of silicon nanoparticles and yield proof for the atomic-like quantized nature of energy levels in the conduction and valence band, as evidenced by narrow luminescence lines (~500 µeV) at low temperature. Analysis of the blinking sheds light on the charging mechanisms of oxide-capped Si-QDs and, by exposing exponential on- and off-time distributions instead of the frequently observed power law distributions, argues in favor of the absence of statistical aging. Experiments probing the emission intensity as a function of excitation power suggest that saturation is not achieved. Both absorption and emission of silicon nanocrystals contained in a one-dimensional silicon dioxide matrix are polarized to a high degree. Many of the results obtained in this work seem to strengthen the arguments that oxide-capped silicon quantum dots have universal properties, independently of the fabrication method, and that the greatest differences between individual nanocrystals are indeed caused by individual factors like local environment, shape and size (among others).

Pascal Weibel, Miriam Ender, Jerzy Madon, Annelies S. Zinkernagel · 5 authors

Introducing PCR products into plasmids vectors is key for molecular techniques. Ideally cloning vectors are easy to construct, modify and propagate, neither require advanced techniques nor special equipment or reagents and efficiently incorporate PCR products at close to zero empty vector background. We provide an easy to engineer self-made cloning vector, neither requiring sophisticated tools or techniques nor advanced cloning knowledge. Through recombination we obtained the pUC18ccdB vector, carrying the ccdB suicide gene within the pUC18 backbone. When SmaI cleaved (within the ccdB) vector was T4 ligated with small (0.2 kbp) and intermediate (1.3 to 2.2 kbp) blunt end PCR-products and transformed into E. coli, the amount of clones with incorporated PCR product was comparable to commercial PCR-cloning kits and at a close to zero PCR product negative background. In conclusion we present a simple, versatile and cheap approach to an efficient “home made ” PCR-cloning vector that allows integration of crude blunt end PCR products at close to zero background.

George Drosatos, Αιμιλία Τασίδου, Pavlos S. Efraimidis

No abstract is available for this record.

Prabhanjan Ananth, Raghav Bhaskar, Vipul Goyal, Vanishree Rao

The Fiat-Shamir paradigm was proposed as a way to remove interaction from 3-round proof of knowledge protocols and derive secure signature schemes. This generic transformation leads to very efficient schemes and has thus grown quite popular. However, this transformation is proven secure only in the random oracle model. In FOCS 2003, Goldwasser and Kalai showed that this transformation is provably insecure in the standard model by presenting a counterexample of a 3-round protocol, the Fiat-Shamir transformation of which is (although provably secure in the random oracle model) insecure in the standard model, thus showing that the random oracle is uninstantiable. In particular, for every hash function that is used to replace the random oracle, the resulting signature scheme is existentially forgeable. This result was shown by relying on the non-black-box techniques of Barak (FOCS 2001). An alternative to the Fiat-Shamir paradigm was proposed by Fischlin in Crypto 2005. Fischlin’s transformation can be applied to any so called 3-round “Fiat-Shamir proof of knowledge’ ’ and can be used to derive non-interactive zero-knowledge proofs of knowledge as well as signature schemes. An attractive property of this transformation is that it provides online extractability (i.e., the extractor works without having to rewind the prover). Fischlin remarks that in comparison to the Fiat-Shamir transformation, his construction tries to

Cătălin Hriţcu

In this thesis we present two new type systems for verifying the security of cryptographic protocol models expressed in a spi-calculus and, respectively, of protocol implementations expressed in a concurrent lambda calculus. In this thesis we present two new type systems for verifying the security of cryptographic protocol models expressed in a spi-calculus and, respectively, of protocol implementations expressed in a concurrent lambda calculus. The two type systems combine prior work on refinement types with union and intersection types and with the novel ability to reason statically about the disjointness of types. The increased expressivity enables the analysis of important protocol classes that were previously out of scope for the type-based analyses of cryptographic protocols. In particular, our type systems can statically analyze protocols that are based on zero-knowledge proofs, even in scenarios when certain protocol participants are compromised. The analysis is scalable and provides security proofs for an unbounded number of protocol executions. The two type systems come with mechanized proofs of correctness and efficient implementations.

Peter Schartner

When initializing cryptographic systems or running cryptographic protocols, the randomness of critical parameters, like keys or key components, is one of the most crucial aspects. But, randomly chosen parameters come with the intrinsic chance of duplicates, which finally may cause cryptographic systems including RSA, ElGamal and Zero-Knowledge proofs to become insecure. When concerning digital identifiers, we need uniqueness in order to correctly identify a specific action or object. Unfortunately we also need randomness here. Without randomness, actions become linkable to each other or to their initiator’s digital identity. So ideally the employed (cryptographic) parameters should fulfill two potentially conflicting requirements simultaneously: randomness and uniqueness. This article proposes an efficient mechanism to provide both attributes at the same time without highly constraining the first one and never violating the second one. After defining five requirements on random number generators and discussing related work, we will describe the core concept of the generation mechanism. Subsequently we will prove the postulated properties (security, randomness, uniqueness, efficiency and privacy protection) and present some application scenarios including system-wide unique parameters, cryptographic keys and components, identifiers and digital pseudonyms.

George Danezis, Markulf Kohlweiss, Benjamin Livshits, Alfredo Rial

Abstract. Nowadays, service providers gather fine-grained data about users to deliver personalized services, for example, through the use of third-party cookies or social network profiles. This poses a threat both to privacy, since the amount of information obtained is excessive for the purpose of customization, and authenticity, because those methods employed to gather data can be blocked and fooled. In this paper we propose privacy-preserving profiling techniques, in which users perform the profiling task locally, reveal to service providers the result and prove its correctness. We address how our approach applies to tasks of both classification and pattern recognition. For the former, we describe client-side profiling based on random forests, where users, based on certified input data representing their activity, resolve a random forest and reveal the classification result to service providers. For the latter, we show how to match a stream of user activity to a regular expression, or how to assign it a probability using a hidden Markov model. Our techniques, based on the use of zero-knowledge proofs, can be composed with other protocols as part of the certification of a larger computation. 1

Lingfeng Chen, Doan B. Hoang

Cloud computing is an emerging evolutionary computing model that provides highly scalable services over high-speed Internet on a pay-as-usage model. However, cloud-based solutions still have not been widely deployed in some sensitive areas, such as banking and healthcare. The lack of widespread development is related to users’ concern that their confidential data or privacy would leak out in the cloud’s outsourced environment. To address this problem, we propose a novel active data-centric framework to ultimately improve the transparency and accountability of actual usage of the users’ data in cloud. Our data-centric framework emphasizes “active” feature which packages the raw data with active properties that enforce data usage with active defending and protection capability. To achieve the active scheme, we devise the Triggerable Data File Structure (TDFS). Moreover, we employ the zero-knowledge proof scheme to verify the request’s identification without revealing any vital information. Our experimental outcomes demonstrate the efficiency, dependability, and scalability of our framework.

Marco LiCalzi, Andrea Collevecchio

Abstract. We study the probability that two or more agents can attain common knowledge of nontrivial events when the size of the state space grows large. We adopt the standard epistemic model where the knowledge of an agent is represented by a partition of the state space. Each agent is endowed with a partition generated by a random scheme consistent with his cognitive capacity. Assuming that agents ’ partitions are independently distributed, we prove that the asymptotic probability of nontrivial common knowledge undergoes a phase transition. Regardless of the number of agents, when their cognitive capacity is sufficiently large, the probability goes to one; and when it is small, it goes to zero. Our proofs rely on a graph-theoretic characterization of common knowledge that has independent interest.

Amang Sudarsono, Toru Nakanishi, Nobuo Funabiki

To enhance user privacy, anonymous credential systems allow the user to convince a verifier of the possession of a certificate issued by the issuing authority anonymously. The typical application is the privacy-enhancing electronic ID (eID). Although a previously proposed system achieves the constant complexity in the number of finite-set attributes of the user, it requires the use of RSA. In this paper, we propose a pairing-based anonymous credential system excluding RSA that achieves the constant complexity. The key idea of our proposal is the adoption of a pairing-based accumulator that outputs a constant-size value from a large set of input values. Using zero-knowledge proofs of pairing-based certificates and accumulators, any AND and OR relation can be proved with the constant complexity in the number of finite-set attributes. We implement the proposed system using the fast pairing library, compare the efficiency with the conventional systems, and show the practicality in a mobile eID application.

Melissa Chase, Markulf Kohlweiss, Anna Lysyanskaya, Sarah Meiklejohn

Depending on the application, malleability in cryptography can be viewed as either a flaw or — especially if sufficiently understood and restricted — a feature. In this vein, Chase, Kohlweiss, Lysyanskaya, and Meiklejohn recently defined malleable zero-knowledge proofs, and showed how to control the set of allowable transformations on proofs. As an application, they construct the first compact verifiable shuffle, in which one such controlled-malleable proof suffices to prove the correctness of an entire multi-step shuffle. Despite these initial steps, a number of natural open problems remain: (1) their construction of controlled-malleable proofs relies on the inherent malleability of Groth-Sahai proofs and is thus not based on generic primitives; (2) the classes of allowable transformations they can support are somewhat restrictive; and (3) their construction of a compactly verifiable shuffle has proof size O(N 2 + L) (where N is the number of votes and L is the number of mix authorities), whereas in theory such a proof could be of size O(N + L). In this paper, we address these open problems by providing a generic construction of controlledmalleable proofs using succinct non-interactive arguments of knowledge, or SNARGs for short. Our construction has the advantage that we can support a very general class of transformations (as we no longer rely on the transformations that Groth-Sahai proofs can support), and that we can use it to obtain a proof of size O(N + L) for the compactly verifiable shuffle.

Hubert Lacoin, François Simenhaus, Fabio, Lucio Toninelli

Let \mathcal D be a simply connected, smooth enough domain of \mathbb R^2 . For L>0 consider the continuous time, zero-temperature heat bath dynamics for the nearest-neighbor Ising model on \mathbb Z^2 with initial condition such that \sigma_x=-1 if x\in L\mathcal D and \sigma_x=+1 otherwise. It is conjectured [23] that, in the diffusive limit where space is rescaled by L , time by L^2 and L\to\infty , the boundary of the droplet of " - " spins follows a deterministic anisotropic curve-shortening flow, where the normal velocity at a point of its boundary is given by the local curvature times an explicit function of the local slope. The behavior should be similar at finite temperature T<T_c , with a different temperature-dependent anisotropy function. We prove this conjecture (at zero temperature) when \mathcal D is convex. Existence and regularity of the solution of the deterministic curve-shortening flow is not obvious a priori and is part of our result. To our knowledge, this is the first proof of mean curvature-type droplet shrinking for a model with genuine microscopic dynamics.

Sebastian Faust, Markulf Kohlweiss, Giorgia Azzurra Marson, Daniele Venturi

The Fiat-Shamir transform is a well studied paradigm for removing interaction from publiccoin protocols. We investigate whether the resulting non-interactive zero-knowledge (NIZK) proof systems also exhibit non-malleability properties that have up to now only been studied for NIZK proof systems in the common reference string model: first, we formally define simulation soundness and a weak form of simulation extraction in the random oracle model (ROM). Second, we show that in the ROM the Fiat-Shamir transform meets these properties under lenient conditions. A consequence of our result is that, in the ROM, we obtain truly efficient non malleable NIZK proof systems essentially for free. Our definitions are sufficient for instantiating the Naor-Yung paradigm for CCA2-secure encryption, as well as a generic construction for signature schemes from hard relations and simulation-extractable NIZK proof systems. These two constructions are interesting as the former preserves both the leakage resilience and key-dependent message security of the underlying CPA-secure encryption scheme, while the latter lifts the leakage resilience of the hard relation to the leakage resilience of the resulting signature scheme.

Olivier Blazy, David Pointcheval, Damien Vergnaud

No abstract is available for this record.

Mohammad Mahmoody, David Xiao

A Zero-Knowledge PCP (ZK-PCP) is a randomized PCP such that the view of any (perhaps cheating) efficient verifier can be efficiently simulated up to small statistical distance. Kilian, Petrank, and Tardos (STOC '97) constructed ZK-PCPs for all languages in NEXP. Ishai, Mahmoody, and Sahai (TCC '12), motivated by cryptographic applications, revisited the possibility of efficient ZK-PCPs for all of NP where the PCP is encoded as a polynomial-size circuit that given a query i returns the ith symbol of the PCP. Ishai et al showed that there is no efficient ZK-PCP for NP with a non-adaptive verifier, that prepares all of its PCP queries before seeing any answers, unless NP⊆coAM and the polynomial-time hierarchy collapses. The question of whether adaptive verification can lead to efficient ZK-PCPs for NP remained open. In this work, we resolve this question and show that any language or promise problem with efficient ZK-PCPs must be in SZK (the class of promise problems with a statistical zero-knowledge single prover proof system). Therefore, no NP-complete problem can have an efficient ZK-PCP unless NP⊆SZK (which also implies NP⊆coAM and the polynomial-time hierarchy collapses). We prove our result by reducing any promise problem with an efficient ZK-PCP to two instances of the Conditional Entropy Approximation problem defined and studied by Vadhan (FOCS'04) which is known to be complete for the class SZK.