Blockchain Papers

Shafi Goldwasser

Theoretical computer science has found fertile ground in many areas of mathematics. The approach has been to consider classical problems through the prism of computational complexity, where the number of basic computational steps taken to solve a problem is the crucial qualitative parameter. This new approach has led to a sequence of advances, in setting and solving new mathematical challenges as well as in harnessing discrete mathematics to the task of solving real-world problems. In this talk, I will survey the development of modern cryptography -- the mathematics behind secret communications and protocols -- in this light. I will describe the complexity theoretic foundations underlying the cryptographic tasks of encryption, pseudo-randomness number generators and functions, zero knowledge interactive proofs, and multi-party secure protocols. I will attempt to highlight the paradigms and proof techniques which unify these foundations, and which have made their way into the mainstream of complexity theory.

Joel N. Hirschhorn, David Altshuler

Over the last 15 yr, genes responsible for hundreds of inherited human diseases have been identified, enabling clinical diagnosis and the potential for therapeutic intervention. Until very recently, however, success has been limited to so-called monogenic disorders, diseases in which mutation of a single gene is both necessary and sufficient to cause disease in any given individual. Because such mutations are strictly co-inherited with disease, it is possible to use linkage analysis to identify their chromosomal location by analyzing which of a genome-wide set of markers segregates with disease in families. Genes contained within such linked regions become positional “candidates” and are next examined for mutations in affected individuals. For any such candidate gene, proof of causality typically depends on two additional lines of evidence. First, the putative causal changes should be found only in affected individuals. Second, one hopes for a “smoking gun”—that the disease-associated mutations are obviously deleterious to protein function (due to truncation or deletion of a coding region or alteration of a highly conserved residue). Success is typically declared when these criteria are all satisfied: the putative disease gene 1) is located in a chromosomal region that co-segregates with disease in affected families, 2) contains multiple independent mutations that are perfectly associated with disease status in the families, and 3) whose characteristics obviously alter protein function. Most common diseases are strongly influenced by inheritance, but, to date, relatively few genes have been identified that are responsible for familial clustering of these diseases. Success has been elusive because common diseases are almost all complex disorders, where multiple genes and environmental factors collaborate to cause disease. Because no single gene segregates tightly with disease, it has proven very difficult to confidently localize putative disease genes to chromosomal locations. For this reason, optimistic gene hunters have leapt directly to the latter stage of examining candidate genes for mutations that show association to disease. Typically, however, these candidate genes are based on a biological hypothesis, rather than chromosomal position relative to a linkage study. Association studies can, in theory, succeed where linkage fails, because association can offer much greater statistical power (1), thus providing a rationale for circumventing linkage analysis. But several problems bedevil such association studies. First, it is expected that the causal mutations are neither necessary nor sufficient to cause disease. That is, some people will have the mutation but not disease, and others will have disease without a causal mutation of that gene. Because of this imperfect correlation, association studies must compare the frequencies of a putative causal mutation in individuals with disease and in appropriate controls. If the mutation is found at a statistically significant higher frequency in affected individuals, the mutation is said to be associated with disease. However, determining appropriate thresholds of significance is challenging because the a priori likelihood that any given candidate gene plays a role in disease is unknown, but certainly low (in following up a solid linkage peak, one at least begins with the knowledge that one or more genes in the region is responsible for the disease). In addition, these more subtle genetic risk factors need not be premature stop codons or protein truncation mutants. Rather, they may be innocuous to the scientist’s eye and yet cause disease by altering the in vivo regulation, expression, stability, activity, or interactions of the encoded protein. Because of these and other difficulties (see, for example, Ref. 2), it is important that association studies be performed and scrutinized carefully, especially when different investigators reach different conclusions as to whether mutations or genetic variation in a gene is associated with disease. Here, we discuss the relevant points in light of a report in this issue questioning the relationship of mutations in the MC4R gene and severe obesity (3). Most association studies have focused on a common genetic variation: by convention, common genetic variants (or polymorphisms) are those for which two or more alleles each exist in 1% or more of the population at large. There are many practical advantages to studying common variants. Because they are present at high frequency, common variants can be discovered in any modest sized group of individuals. This facilitates cataloging of common variants. Over the last 3 yr, millions of common human sequence variants have been identified and placed in databases (4). Moreover, because strong correlations are typically observed between neighboring variants (linkage disequilibrium), most common variations in the genome can be tested for a role in disease using a subset of carefully chosen “tag” single nucleotide polymorphisms (see Ref. 5 and references therein). Finally, testing common variants for association to disease is technically straightforward. The frequencies of each variant can be accurately estimated in modest sized collections of patients with and without the disease. Of course, there is no reason to presume that the mutations responsible for common diseases will themselves be common. Certainly, many rare monogenic disorders are due to a heterogeneous collection of variants that are individually very rare. In thinking about the allele spectrum of common diseases, it is important to consider both the overall characteristics of human genetic variation and the particular evolutionary features of each disease (6). The characteristic features of human genetic variation have been well described (see Ref. 4 and references therein). Numerically, rare variants outnumber common variants, but the vast majority of variant alleles in the population (heterozygosity) are attributable to the small number of common variants. Thus, for disease phenotypes that had a neutral effect on human evolutionary fitness, the spectrum of alleles causing disease should resemble this overall pattern—most of the genetic burden of disease in the population will be due to common variants. In contrast, where disease was disadvantageous from an evolutionary perspective (e.g. diseases that are lethal in childhood), rare variants will predominate, because variants that lower reproductive fitness generally do not drift up to high frequency. Finally, disease phenotypes that experienced balancing selection (e.g. sickle cell disease, where disease is balanced by resistance to malaria in carriers) or that may even have been evolutionarily advantageous (as has been proposed for obesity under the thrifty gene hypothesis) should be due to variants that are even more common than those found throughout the genome as a whole. Given the speculative nature of such evolutionary hypotheses, as well as the experience from rare monogenic disorders, there has been great attention to the importance of studying rare genetic variants for a role in common disease (see, for example, Ref. 6). However, studying rare variants introduces important methodological challenges. First, investigators must discover the variants in each of their populations, often by directly resequencing affected individuals. Moreover, because they are rare, much larger samples must be examined before an accurate estimate of frequency can be obtained for the comparison of cases and controls. In making such comparisons, it is critical that controls be scrutinized for variation in the exact same manner as cases, because resequencing only of cases leads to a significant problem called ascertainment bias. In brief, sequencing a large group of individuals will nearly always identify a particular collection of vanishingly rare variants (including missense variants) that will be absent from any second collection of individuals that is tested. Thus, finding a few rare, apparently deleterious mutations in affected individuals does not signify a role in disease, unless controls have been examined with the same intensity as have cases, and the preferential presence of variants in affected individuals is strong and statistically convincing. In fact, the statistical analysis of rare variation almost always requires that collections of different rare variants be considered as a group, because no individual variant is sufficiently common to permit an accurate assessment of its frequency in realistically sized disease or control populations. It is important that the grouping of rare variants not be done post hoc in a subjective (and, therefore, potentially biased) manner. Rather, the grouping must be on the basis of obvious sequence characteristics (e.g. all missense variants, all nonsense and frameshift mutations, etc.), or on the basis of a valid functional assay. To avoid a biased assignment of functional importance to variants identified in affected individuals, such a functional assay should be developed and validated independently of the results of association analysis. Despite these additional challenges, association testing of rare and common variants is fundamentally similar. Once a relevant common variant —or group of rare variants—is identified, the frequency of variants must be rigorously compared in affected individuals and in controls. The choice of a threshold for declaring a significant association has been a matter of some debate. The P value for differences in frequencies between affected individuals and controls reflects the likelihood of observing an association by chance if the true frequency were the same in both groups. This obviously is not equivalent, however, to the likelihood that the experimenter’s hypothesis of association is in error, because this latter calculation requires knowledge of the a priori probability that the variant in question was associated with disease. In most such studies, this prior probability is extremely low—there are hundreds of candidate genes, each of which contains a hundred or more commonly varying sites; moreover, many causal genes will not be obvious candidates, and the entire genome contains 10 million common variants and many more rare variants. In this Bayesian framework, the P values for most association studies are not low enough to meet a conservative threshold for declaring significance that minimizes type 1 errors (false positive studies). Thus, a single report of association is almost always inadequate to prove causation. Rather, replication, preferably in multiple independent studies, is required. However, consistent replication of associations has been difficult to achieve. Indeed, a review of associations between common variants and disease found that the vast majority of such associations have not been consistently reproduced (2). The possible reasons for the inconsistency include false positives due to type 1 error, false positives due to population stratification, false negatives due to lack of power in potential replication studies, and true differences between study populations (e.g. different phenotypes, or different environmental or genetic modifiers). These explanations probably all contribute to the lack of reproducibility and are relevant to both studies of individual common variants and of grouped rare variants. However, to interpret an association that has not been consistently replicated, it is important to try to distinguish which of these explanations is truly relevant to that particular association. Lack of power for true associations with modest effects can clearly contribute to inconsistent replication. For example, several studies failed to detect an association of the Pro12Ala variant with type 2 diabetes and concluded that no such role was likely to exist. In fact, this PPARG variant has a much lower relative risk (1.25-fold) than was initially estimated, and consequently many studies were underpowered to detect the true effect of the allele on diabetes risk (7). To assess power, then, the range of genetic effects that are consistent with the negative data should be compared with the genetic effect estimated by considering all of the previous studies together. In this context, Jacobson et al. (3) report in this journal their failure to replicate the previously described association of rare functional variants in the MC4R gene with morbid human obesity. MC4R was originally implicated in obesity by mouse studies (see, for example, Ref. 8); two groups then independently identified severely obese individuals (one in each study) with a frameshift mutation in the MC4R gene (9, 10). Several additional studies subsequently found at least 34 additional missense or frameshift mutations in MC4R in obese individuals, but no functional missense variants were identified in control individuals who were resequenced (see Refs. 18–24 in Ref. 3). It is worth noting that there are three somewhat common missense variants that are present at approximately equal frequencies in obese and nonobese individuals (Val103Ile, Thr112Met, and Ile251Leu). These variants have been distinguished from the putative functional variants because they do not affect MC4R function in in vitro tests (11, 12). If these common variants were included in statistical analysis, they would swamp out any signal due to the rarer, apparently functional mutations. Thus, the statistical arguments in favor of association rely critically on the relevance of the in vitro assay used to assess protein function. In total, at least 34 putative functional MC4R mutations have been identified in 1187 obese individuals (2.9% frequency) as compared with zero in 827 controls. Nearly all of the obese individuals who were found to carry mutations are either severely morbidly obese [body mass index (BMI),50] or had onset of obesity in childhood or early adolescence. However, some carriers and relatives were identified who also carry MC4R mutations but have less severe phenotypes (12). These findings led to the hypothesis that mutations in MC4R might be a common cause of morbid obesity (12). It was the intent of Jacobson et al. (3) to test this hypothesis. To study the role of MC4R mutations in obesity, they resequenced the MC4R gene in over 200 obese white subjects and 47 obese black subjects, plus a similar number of controls. None of the previously described putative functional variants were identified. Three new missense variants were identified, each in one black control (Ile102Thr, Phe202Leu, and Asn240Ser). Unfortunately, no functional evaluation of these variants was performed. In addition, one frameshift mutation leading to a predicted premature termination codon was discovered in an obese white female. The authors interpret these data as failing to replicate the previous findings of a high rate of MC4R mutations in obese individuals. To evaluate whether the authors have failed to replicate the previous finding, or have simply asked a different question, we consider below each of the main possible explanations for the failure to replicate: false negative study (inadequate power), a falsely positive original report, and true differences between study populations. Jacobson et al. (3) state that they can strongly reject the hypothesis that mutations in MC4R account for 4% of cases of obesity, with 80–85% power in blacks and greater than 99.9% power in whites. These arguments are based on not having observed any of the previously reported functional variants. However, the spectrum of variants that can affect MC4R function is apparently quite diverse (few or none of the functional variants have been identified independently in separate studies), so the expectation should be that most functional variants in MC4R would be novel. Indeed, Jacobson et al. (3) did discover one such variant (the frameshift mutation, although they did not test it for function in vitro). Thus, a more appropriate interpretation of their data is that they identified one apparently functional mutation in approximately 200 unrelated obese white individuals and 47 obese black individuals. Furthermore, 4% is the highest estimate of MC4R mutations in the literature (12). A more appropriate figure to test would be 2.9% (the estimate from all available data), and even this value may be too high because some of the rare missense changes identified in obese individuals do not impair function in vitro (see Ref. 12) and, thus, may not represent functional MC4R mutations. What range of frequencies of MC4R mutations could be consistent with the data in Jacobson et al. (3)? Given the observation of one mutation in 200 individuals, the 95% confidence interval for the frequency of MC4R mutations is quite wide; values from 0.12–2.75% are all consistent with the data. Even if the data from blacks and whites are pooled, the 95% confidence interval extends from 0.1–2.2%; the data from blacks alone are actually consistent with mutation frequencies as high as 7% in this population. If power is set at a more conservative 80%, the data can reject frequencies of mutations greater than 1.5% in whites, 3.3% in blacks, and 1.2% in the pooled sample. Although the confidence intervals are wide, the data are apparently inconsistent with the 2.9% frequency of mutations found in previous studies. Thus, additional explanations are required other than inadequate power of the current study. The second possibility is that the previous studies were false positives: all of the functional variants were found in the obese individuals by chance or due to a biased selection of which variants were considered functional. However, this explanation also seems unlikely. The P value for finding 34 functional variants in 1187 obese individuals but no functional variants in 827 controls is under 10−6. In addition, many of the variants are obviously deleterious, and there is no reason to suspect that the functional assay is biased. Thus, one must consider the possibility that the authors of the present study may have asked a different question than that posed before, specifically that the populations used in previous studies and the populations used in Jacobson et al. (3) are in some way fundamentally different from each other. The possibility of differences in populations seems quite plausible if one compares the characteristics of the populations used in previous studies with those of the obese individuals in this most recent study. In previous studies, almost all MC4R carriers were found among severely obese individuals (BMI, >50) and/or individuals with early-onset obesity (usually in childhood). By contrast, only 42% of the white individuals in the study by Jacobson et al. (3) had early-onset obesity (childhood or adolescence), and less than 10% had a BMI greater than 50. If one only considers these approximately 100 subjects in the study, there is no longer 80% power to reject a mutation frequency of 2.9%, although the estimate of the frequency (now 1% rather than 0.5%) is still much lower than the 2.9% estimated by previous studies. However, a potentially more important conclusion is suggested from these data: Jacobson et al. (3) observe no MC4R mutations in 100 individuals with a BMI under 50 and onset of obesity in adulthood. Indeed, the only other studies to examine populations not selected or enriched for severe or early-onset obesity also failed to find mutations in MC4R despite screening 90 individuals (13, 14). This suggests that although MC4R mutation might be a rare (2–3%) but significant cause of early-onset or severe obesity, it is likely to be a less common cause of obesity in the general population. This could be explained (post hoc) by invoking the possible selective disadvantage of relatively penetrant alleles that cause severe, early-onset obesity (where rare MC4R mutations are observed) compared with the less easily predicted evolutionary history of the more common form of the disease. How can one reconcile this apparent absence of MC4R mutations in cases of less severe obesity with the fact that some relatives of severely affected probands carry MC4R mutations but have milder obesity (12)? Shouldn’t some of these relatives have turned up in the studies of “typical” obesity? The answer probably lies in the fact that there are many, many more people with typical obesity than there are relatives of MC4R carriers. This theory predicts that if one studied people with mild obesity who had a relative with severe or early-onset obesity, it would be possible to enrich for carriers of MC4R mutations. This dichotomy is reminiscent of the situation for BRCA1 and breast cancer, where mutations are found at appreciable frequencies in highly familial cases, early-onset cases, or women with multiple cancers. Where family members of such women are tested, carriers with later onset breast cancer (or no cancer at all) are found at appreciable when more typical cases of breast cancer are BRCA1 mutations are found at much lower the current study many of the important in association studies of genetic variants and disease. is because prior of true association are low and, thus, all genetic associations a high of failure to replicate can be due to many possible explanations false positive studies and type 1 Lack of power to modest effects and different phenotypes of patients in different collections can both contribute to apparent among studies. Moreover, genetic variants both rare and common are to a role in most diseases, but their relative in any given are to Given the of resequencing and the of grouping rare variants and an of the hypothesis is even for candidate rare variants such as are found in MC4R will no a great about and the in which human can be by severe genetic rare variants also out to much of the population burden of disease is an important question that will for some to mass

Yong-Sork Her, 容碩 許, Kouichi Sakurai, 幸一 櫻井 · 5 authors

The voting plays important roles in a democratic country. Due to the problems of the existed voting m ethod, the new voting methods, electronic voting system, have been developing using the computer net work and cryptographic techniques. Many electronic voting schemes have been introduced for secure electronic voting systems. In this paper, we propose the secure electronic voting for absentee e-voting system. The absentee voting plays the important percentage in the existing voting system. But, the abs entee vote can not look forward to the security because of transmit by mail. The absentee does not kno w whether one’s voting is exactly counted or not. In this paper, we propose the absentee e-voting syste m based on security, completeness and verifiability. We use r-th residue cryptography for homomorphi c encryption, ZKIP (Zero-Knowledge interactive proofs), RSA algorithm. Also, we propose the ne w method of tallying for multi-candidate. The goals of out voting system are the absentee vot ing based on privacy, universal verifiability, reuseability and multi-candidate.

Yong-Sork Her, 容碩 許, キョ, ヨウソク, Kouichi Sakurai · 6 authors

In this paper, we propose the absentee e-voting system based on security, completeness and verifiability. We use r-th residue cryptography for homomorphic encryption, ZKIP (Zero-Knowledge interactive proofs), RSA algorithm for the secure absentee e-voting.

Hirotada Kobayashi

This paper introduces quantum analogues of non-interactive perfect and statistical zero-knowledge proof systems. Similar to the classical cases, it is shown that sharing randomness or entanglement is necessary for non-trivial protocols of non-interactive quantum perfect and statistical zero-knowledge. It is also shown that, with sharing EPR pairs a priori, the class of languages having one-sided bounded error non-interactive quantum perfect zero-knowledge proof systems has a natural complete problem. Non-triviality of such a proof system is based on the fact proved in this paper that the Graph Non-Automorphism problem, which is not known in BQP, can be reduced to our complete problem. Our results may be the first non-trivial quantum zero-knowledge proofs secure even against dishonest quantum verifiers, since our protocols are non-interactive, and thus the zero-knowledge property does not depend on whether the verifier in the protocol is honest or not. A restricted version of our complete problem derives a natural complete problem for BQP.

John Watrous

In this paper we propose a definition for (honest verifier) quantum statistical zero-knowledge interactive proof systems and study the resulting complexity class, which we denote QSZK. We prove several facts regarding this class that establish close connections between classical statistical zero-knowledge and our definition for quantum statistical zero-knowledge, and give some insight regarding the effect of this zero-knowledge restriction on quantum interactive proof systems.

Michael O’Donnell

In this paper we examine the role of Identification Protocols in the field of Cryptography. Firstly, the rationale behind the need for Identification Protocols is discussed. Secondly, we examine, in detail, challenge-response protocols, based upon zero-knowledge proofs, that form a subset of Identification Protocols in general. Thirdly, the mathematical tools necessary for the understanding of how these protocols work is given. Finally, we discuss four main Identification Protocols: Fiat-Shamir, Feige-Fiat-Shamir, Schnorr and Guillou- Quisquater. This discussion includes the theory, practical examples and the security aspects of each protocol.

Hervé Sibert, Patrick Dehornoy, Marc Girault

Abstract. Artin’s braid groups currently provide a promising background for cryptographical applications, since the first cryptosystems using braids were introduced in [2, 3, 18] (see also [22]). A variety of key agreement protocols based on braids have been described, but few authentication or signature schemes have been proposed so far. We introduce three authentication schemes based on braids, two of them being zero-knowledge interactive proofs of knowledge. Then we discuss their possible implementations, involving normal forms or an alternative braid algorithm, called handle reduction, which can achieve good efficiency under specific requirements. 1.

Masayuki Abe, Ronald Cramer, Serge Fehr

Abstract. A commitment multiplication proof, CMP for short, allows a player who is committed to secrets s, s ′ and s ′ ′ = s · s ′ , to prove, without revealing s, s ′ or s ′ ′ , that indeed s ′ ′ = ss ′. CMP is an important building block for secure general multi-party computation as well as threshold cryptography. In the standard cryptographic model, a CMP is typically done interactively using zero-knowledge protocols. In the random oracle model it can be done non-interactively by removing interaction using the Fiat-Shamir heuristic. An alternative non-interactive solution in the distributed setting, where at most a certain fraction of the verifiers are malicious, was presented in [1] for Pedersen’s discrete log based commitment scheme. This CMP essentially consists ofa few invocations ofPedersen’s verifiable secret sharing scheme (VSS) and is secure in the standard model. In the first part ofthis paper, we improve that CMP by arguing that a building block used in its construction in fact already constitutes a CMP. This not only leads to a simplified exposition, but also saves on the required number ofinvocations ofPedersen’s VSS. Next we show how to construct non-interactive proofs of partial knowledge [8] in this distributed setting. This allows for instance to prove non-interactively the knowledge of ℓ out of m given secrets, without revealing which ones. We also show how to construct efficient non-interactive zero-knowledge proofs for circuit satisfiability in the distributed setting. In the second part, we investigate generalizations to other homomorphic commitment schemes, and show that on the negative side, Pedersen’s VSS cannot be generalized to arbitrary (black-box) homomorphic commitment schemes, while on the positive side, commitment schemes based on q-one-way-group-homomorphism [7], which cover wide range ofcurrently used schemes, suffice. 1

Ivan Damgård, Eiichiro Fujisaki

No abstract is available for this record.

Matthew Lepinski

Goldreich and Krawczyk proved that there do not exist 3-round black-box zero-knowledge proofs or arguments for languages outside BPP. In 1998, Hada and Tanaka used non-standard assumptions to provide a 3-round zero-knowledge argument for every language in NP which was not black-box zero-knowledge. We present a non-black-box simulatable 3-round zero-knowledge proof system for NP, which is secure even when the prover has unbounded computational resources. However, we require a non-standard assumption (similar to those used by Hada and Tanaka) in order to prove our protocol is zero-knowledge. Additionally, we provide a proof of knowledge framework in which to view this type of non-standard assumption. In this thesis, I designed and implemented a compiler which performs optimizations that reduce the number of low-level floating point operations necessary for a specific task; this involves the optimization of chains of floating point operations as well as the implementation of a "fixed" point data type that allows some floating point operations to simulated with integer arithmetic. The source language of the compiler is a subset of C, and the destination language is assembly language for a micro-floating point CPU. An instruction-level simulator of the CPU was written to allow testing of the code. A series of test pieces of codes was compiled, both with and without optimization, to determine how effective these optimizations were.

Jörg Rothe

In this tutorial, selected topics of cryptology and of computational complexity theory are presented. We give a brief overview of the history and the foundations of classical cryptography, and then move on to modern public-key cryptography. Particular attention is paid to cryptographic protocols and the problem of constructing the key components of such protocols such as one-way functions. A function is one-way if it is easy to compute, but hard to invert. We discuss the notion of one-way functions both in a cryptographic and in a complexity-theoretic setting. We also consider interactive proof systems and present some interesting zero-knowledge protocols. In a zero-knowledge protocol one party can convince the other party of knowing some secret information without disclosing any bit of this information. Motivated by these protocols, we survey some complexity-theoretic results on interactive proof systems and related complexity classes.

Ivan Damgård, Jesper Buus Nielsen

Canetti and Fischlin have recently proposed the security notion <em>universal composability</em> for commitment schemes and provided two examples. This new notion is very strong. It guarantees that security is maintained even when an unbounded number of copies of the scheme are running concurrently, also it guarantees non-malleability, resilience to selective decommitment, and security against adaptive adversaries. Both of their schemes uses Theta(k) bits to commit to one bit and can be based on the existence of trapdoor commitments and non-malleable encryption.<br /> <br />We present new universally composable commitment schemes based on the Paillier cryptosystem and the Okamoto-Uchiyama cryptosystem. The schemes are efficient: to commit to k bits, they use a constant number of modular exponentiations and communicates O(k) bits. Furthermore the scheme can be instantiated in either perfectly hiding or perfectly binding versions. These are the first schemes to show that constant expansion factor, perfect hiding, and perfect binding can be obtained for universally composable commitments.<br /> <br />We also show how the schemes can be applied to do efficient zero-knowledge proofs of knowledge that are universally composable.

Ronald Cramer, Victor Shoup

We present several new and fairly practical public-key encryption schemes and prove them secure against adaptive chosen ciphertext attack. One scheme is based on Paillier's Decision Composite Residuosity (DCR) assumption, while another is based in the classical Quadratic Residuosity (QR) assumption. The analysis is in the standard cryptographic model, i.e., the security of our schemes does not rely on the Random Oracle model.<br /> <br />We also introduce the notion of a universal hash proof system. Essentially, this is a special kind of non-interactive zero-knowledge proof system for an NP language. We do not show that universal hash proof systems exist for all NP languages, but we do show how to construct very efficient universal hash proof systems for a general class of group-theoretic language membership problems.<br /> <br />Given an efficient universal hash proof system for a language with certain natural cryptographic indistinguishability properties, we show how to construct an efficient public-key encryption schemes secure against adaptive chosen ciphertext attack in the standard model. Our construction only uses the universal hash proof system as a primitive: no other primitives are required, although even more efficient encryption schemes can be obtained by using hash functions with appropriate collision-resistance properties. We show how to construct efficient universal hash proof systems for languages related to the DCR and QR assumptions. From these we get corresponding public-key encryption schemes that are secure under these assumptions. We also show that the Cramer-Shoup encryption scheme (which up until now was the only practical encryption scheme that could be proved secure against adaptive chosen ciphertext attack under a reasonable assumption, namely, the Decision Diffie-Hellman assumption) is also a special case of our general theory.

WR Simons

No abstract is available for this record.

Committee for Proprietary Medicinal Products (CPMP)

A number of recent applications have led to CPMP discussions concerning the interpretation of superiority, noninferiority and equivalence trials. These issues are covered in ICH E9 (Statistical Principles for Clinical Trials). There is further relevant material in the Step 2 draft of ICH E10 (Choice of Control Group) and in the CPMP Note for Guidance on the Investigation of Bioavailability and Bioequivalence. However, the guidelines do not address some specific difficulties that have arisen in practice. In broad terms, these difficulties relate to switching from one design objective to another at the time of analysis. The types of trials in question are those designed to compare a new product with an active comparator. The objective may be to demonstrate: the superiority of the new product the noninferiority of the new product or the equivalence of the two products. When the results of the trial become available, they may suggest an alternative interpretation. Thus the results of a superiority trial may only appear to be sufficient to support noninferiority, while the results of a noninferiority trial may appear to support superiority. Alternatively, the results of an equivalence trial may appear to support a tighter range of equivalence. A satisfactory approach to this subject requires an understanding of confidence intervals and the manner in which they capture the results of the trial and indicate the conclusions that can be drawn from them. Such an understanding also leads to an appreciation of why power calculations are of relatively little interest when a trial is complete. For simplicity, this paper addresses the issues of superiority, noninferiority and equivalence from the perspective of an efficacy trial with a single primary variable. Some comments on other situations are made in Section VI. It is assumed throughout this document that switching the objective of a trial does not lead to any change in the selection or definition of the primary variable. A superiority trial is designed to detect a difference between treatments. The first step of the analysis is usually a test of statistical significance to evaluate whether the results of the trial are consistent with the assumption of there being no difference in the clinical effect of the two treatments. In a trial of good quality, the degree of statistical significance (P value) indicates the probability that the observed difference, or a larger one, could have arisen by chance assuming that no difference really existed. The smaller this probability is, the more implausible is the assumption that there really is no difference between the treatments. Once it is accepted that the assumption of ‘no difference’ is untenable, it then becomes important to estimate the size of the difference in order to assess whether the effect is clinically relevant. This has two aspects. First there is the best estimate of the size of the difference between treatments (point estimate). For normally distributed data this is usually taken as the observed difference between the mean values on each. Next, there is the range of values of the true difference that are plausible in the light of the results of the trial (confidence interval). It is clear that this range should not include zero since the possibility of a zero difference has already been rejected as unreasonable. The method of constructing confidence intervals generally ensures that this is so, provided it corresponds to the choice of significance test. Thus the following two statements are usually equivalent: The two-sided 95% confidence interval for the difference between the means excludes zero. The two means are statistically significantly different at the 5% level (P < 0.05) two-sided. The above text addresses the situation where the difference between two mean values is the statistic of interest and a zero difference represents no effect. In practice a number of other summary statistics are used for the evaluation of differences between treatments, for example the odds ratio for proportions or the ratio of geometric means in bio-equivalence studies. (The latter arises from the logarithmic transformation used for bioavailability data.) In such cases the same principles apply but ‘no difference’ may be represented by a value other than zero – a value of 1 in both the examples quoted here. In these cases it is the position of the confidence interval for the test statistic relative to this ‘no difference’ value that is of interest. When significance tests are carried out in practice, precise numerical values of probabilities are usually quoted, for example P = 0.032, because this is more informative than P < 0.05. This allows judgement to be based more precisely on the extent of the disagreement between the null hypothesis and the observed data rather than on the approximations implied by using cut-off points of 0.05, 0.01 and 0.001. However, confidence intervals have to be associated with a specific probability value (coverage probability) and this is nearly always taken as 95% (0.95). When a difference is statistically significant at a more extreme level, e.g. P = 0.002, the two-sided 95% confidence interval will exclude zero by a wider margin. Figure 1 illustrates these points. Relationship between significance tests and confidence intervals. Whether the observed difference is indeed clinically relevant is a matter of judgement. In contrast to an equivalence or noninferiority trial where clinical relevance is addressed through the prestudy choice of Δ (see II.2 and II.3), in a superiority trial clinical relevance requires separate consideration: a statistically significant difference may not be clinically relevant. The difference taken as the basis of the power calculation in a superiority trial cannot be assumed to provide a suitable value. Note that in Figure 1, and throughout the rest of the document, it is assumed that values to the right of zero correspond to a better response on the new treatment so that values to the left are worse, i.e. better on the control treatment. An equivalence trial is designed to confirm the absence of a meaningful difference between treatments. In this case it is more informative to conduct the analysis by means of the calculation and examination of the confidence interval although there are closely related methods using significance test procedures. (See also II.3.) A margin of clinical equivalence (Δ) is chosen by defining the largest difference that is clinically acceptable, so that a difference bigger than this would matter in practice. There are well-recognized difficulties associated with this task which will not be discussed in any detail here. If the two treatments are to be declared equivalent, then the two-sided 95% confidence interval – which defines the range of plausible differences between the two treatments – should lie entirely within the interval −Δ to + Δ, see Figure 2. There are situations in which the equivalence margins may be chosen asymmetrically with respect to zero. Confidence interval approach to analysis of equivalence trial. In the case of bioequivalence studies a coverage probability of 90% for the confidence interval has become the accepted standard when evaluating whether the average values of the pharmacokinetic parameters of two formulations are sufficiently close. Clinical equivalence trials, with two-sided 95% confidence intervals, may be carried out when conventional bio-equivalence trials are impossible, for example in the case of a generic inhaled or topically applied product. In Phase III drug development, noninferiority trials are more common than equivalence trials. In these we wish to show that a new treatment is no less effective than an existing treatment – it may be more effective or it may have a similar effect. Again a confidence interval approach is the most straightforward way of performing the analysis but now we are only interested in a possible difference in one direction. Hence the two-sided 95% confidence interval should lie entirely to the right of the value −Δ, see Figure 3. Non-inferiority trials are sometimes mistakenly referred to, and designed as, equivalence trials. This distinction is important and can be a source of confusion. Confidence interval approach to analysis of non-inferiority trial. Note also that by using the closely related significance testing procedures referred to in II.2, it is possible to calculate a P value associated with the null hypothesis of inferiority. This is a valuable further aid to assessing the strength of the evidence in favour of noninferiority. It will be assumed throughout this document that two-sided 95% confidence intervals are to be used for all clinical trials whatever their objective. Among other benefits, this preserves consistency between significance testing and subsequent estimation. It is also consistent with the guidance provided in the ICH E9 Note for Guidance. If one-sided intervals are used, then they should be used with a coverage probability of 97.5%. In the special case of bioequivalence studies, two-sided 90% confidence intervals have been established as the norm as recommended, for example, in the CPMP Note for Guidance on the Investigation of Bioavailability and Bioequivalence. A conclusion of equivalence or noninferiority clearly depends upon the value of Δ chosen as the maximum acceptable difference. It is always possible to choose a value of Δ which leads to a conclusion of equivalence or noninferiority if it is chosen after the data have been inspected. Since the choice of Δ is generally a difficult one, there is ample room for bias here, however, well intentioned the researcher may be. Plausible arguments may often be advanced for a retrospective choice. In the design of equivalence and noninferiority trials, this reason (amongst others) makes it necessary for the choice of Δ, and the reasoning behind the choice, to be set down in advance by the researcher in the study protocol. The corresponding coverage probability for the confidence interval (usually 95%) should also be chosen at this time. (See Section IV.2 for how these requirements apply when objectives are changed.) The question of how to choose an appropriate Δ will be addressed in a subsequent CPMP Points to Consider. Pre-definition of a trial as a superiority trial, an equivalence trial or a noninferiority trial is necessary for numerous reasons including the following: to ensure that comparator treatments, doses, patient populations and endpoints are appropriate (see ICH E10) to allow sample size estimates to be based on the correct power calculations to ensure that equivalence and noninferiority criteria are predefined to permit appropriate analysis plans to be described in the protocol to ensure that the trial has sufficient sensitivity to achieve its objectives (see ICH E10) If the objective of a trial is switched from superiority to noninferiority, or vice versa, these aspects may lead to greater difficulty than the interpretation of significance tests and confidence intervals. The only switching which is likely to have any practical relevance is switching between superiority and noninferiority. The place of equivalence trials is so specific that they stand alone. If the 95% confidence interval for the treatment effect not only lies entirely above −Δ but also above zero then there is evidence of superiority in terms of statistical significance at the 5% level (P < 0.05). See Figure 4. In this case it is acceptable to calculate the P value associated with a test of superiority and to evaluate whether this is sufficiently small to reject convincingly the hypothesis of no difference. There is no multiplicity argument that affects this interpretation because, in statistical terms, it corresponds to a simple closed test procedure. Usually this demonstration of a benefit is sufficient on its own, provided the safety profiles of the new agent and the comparator are similar. When there is an increase in adverse events, however, it is important to estimate the size of the effect to evaluate whether it is sufficient in clinical terms to outweigh the adverse effects. Non-inferiority to superiority. There are a number of other factors that might be affected by this changed objective. If the comparator was suitable for a demonstration of noninferiority, then there should be well-controlled data to show that it is an effective treatment. Hence, for proof of efficacy, a clear demonstration of superiority to the comparator in terms of statistical significance should be acceptable. Non-inferiority trials are generally large because of their need to exclude the possibility of a small degree of inferiority of a new agent relative to an active control. However if the new agent is actually superior to control by a small amount, then the power to show its noninferiority is increased. Demonstrating the small amount of superiority to control might in principle require the planning of an even larger trial. When the trial is completed, however, the results provided by the confidence interval supply a concrete assessment of the precision actually achieved, superseding any calculations of power carried out before the trial was undertaken. Since the comparator in a noninferiority trial must be an effective agent, any superiority to that agent should carry the implication of acceptable superiority to no treatment (placebo). For this reason the size of the additional clinical benefit demonstrated is not likely to be relevant to a claim of efficacy except in relation to any increase in adverse effects and hence relative risk/benefit. However, when the proposed licence includes a claim of superiority to the comparator, the size of the additional benefit should be discussed in clinical terms. In a superiority trial the full analysis set, based on the ITT (intention-to-treat) principle, is the analysis set of choice, with appropriate support provided by the PP (per protocol) analysis set. In a noninferiority trial, the full analysis set and the PP analysis set have equal importance and their use should lead to similar conclusions for a robust interpretation. A switch of objective would require this difference of emphasis to be recognized. More details of the relative importance of these two analysis sets in superiority and noninferiority trials can be found in the ICH E9 Note for guidance. A trial to show equivalence or noninferiority must show a high degree of consistency with protocolled plans if it is to be reliable. Deviations from the inclusion criteria, from the intended treatment regimen, from the schedule, manner and precision of taking measurements, and so on, all tend to reduce the sensitivity of a trial and to make a conclusion of ‘no difference’ more likely, even when the deviations are of an unsystematic or random nature. The size of the bias associated with these and other departures from the protocol is generally unknown and may render such a trial uninterpretable. Failure to show a difference between two treatments can also arise when both treatments are inefficacious, perhaps as a result of being inappropriately administered. This problem does not affect superiority trials to the same extent because the demonstration of a difference is itself validation of the sensitivity of the trial. The estimate of the size of the effect may however, be similarly affected. For these reasons, switching from noninferiority to superiority is likely to carry with it a greater degree of confidence in the conclusion. Switching the objective of a trial from noninferiority to superiority is feasible provided: The trial has been properly designed and carried out in accordance with the strict requirements of a noninferiority trial. Actual P values for superiority are presented to allow independent assessment of the strength of the evidence. Analysis according to the intention-to-treat principle is given greatest emphasis. If a superiority trial fails to detect a significant difference between treatments, there may be interest in the lesser objective of establishing noninferiority. If the results of the superiority trial are summarized by means of a 95% confidence interval for the treatment difference, the lower end of that confidence interval provides a quantitative estimate of the minimum estimated effect of the new treatment relative to the comparator. When the study protocol an acceptable, margin −Δ for noninferiority, the objective less a noninferiority margin would appear only to make in trials with noninferiority as an However, in any superiority trial where noninferiority may be an acceptable for it is to a noninferiority margin in the protocol in order to the difficulties that can arise from such it is also to design to the possible need to that the study sufficient sensitivity to detect the drug effects of interest (see It is important to that there are of where noninferiority to an active control is to be acceptable as the or evidence of efficacy, and trials are to In trials where there is no noninferiority such a has to be after the and in situations this will not be It is likely that the will have to be after the results have been and there may be little basis for an objective choice of margin. there does not appear to be a statistical multiplicity related to this switch of that does not the difficulties associated with the definition of A number of other issues require A comparator chosen for a demonstration of superiority may not be acceptable for a conclusion of noninferiority. In order for it to be acceptable, it will be necessary to that there are data from good superiority trials consistent evidence that the comparator is an effective treatment with and establishing the size of its effect relative to no treatment. There should also be a basis for that the same degree of efficacy would be in the trial. For example, the patient and the endpoints should be similar. These issues are covered in ICH in the results provided by the confidence interval supply a concrete assessment of the precision actually by a clinical trial, superseding any calculations of power carried out before the trial was undertaken. The position of the lower end of the confidence interval relative to the of noninferiority provides the for noninferiority. In a superiority trial the full analysis set, based on the ITT (intention-to-treat) principle, is the analysis set of choice, with appropriate support provided by the PP (per protocol) analysis set. In a noninferiority trial the full analysis set and the PP analysis set have equal importance and their use should lead to similar conclusions for a robust interpretation. A switch of objective would require this difference of emphasis to be recognized. More details of the relative importance of these two analysis sets in superiority and noninferiority trials can be found in the ICH E9 Note for Guidance. A trial to show equivalence or noninferiority must show a high degree of consistency with protocolled plans if it is to be reliable. Deviations from the inclusion criteria, from the intended treatment regimen, from the schedule, manner and precision of taking measurements, and so on, all tend to reduce the sensitivity of a trial and to make a conclusion of ‘no difference’ more likely, even when the deviations are of an unsystematic or random nature. The size of the bias associated with these and other departures from the protocol is generally unknown and may render such a trial uninterpretable. Failure to show a difference between two treatments can also arise when both treatments are inefficacious, perhaps as a result of being inappropriately administered. This problem does not affect superiority trials to the same extent because the demonstration of a difference is itself validation of the sensitivity of the trial. For these reasons, switching from superiority to noninferiority is likely to carry with it a lesser degree of confidence in the It will be necessary to to the sensitivity of the trial by or that the control treatment is its efficacy the trial with trials which demonstrated the efficacy of the control agent in of and of of and data that are at to those in the trials similar results from the full analysis set and PP analysis set. Switching the objective of a trial from superiority to noninferiority may be feasible provided: The noninferiority margin with respect to the control treatment was predefined or can be (The latter is likely to difficult and to be to cases where there is a accepted value for Analysis according to the intention-to-treat principle and PP confidence intervals and P values for the null hypothesis of similar The trial was properly designed and carried out in accordance with the strict requirements of a noninferiority trial (see ICH E9 and The sensitivity of the trial is high to ensure that it is of relevant differences if they There is or evidence that the control treatment is its level of A further related that has arisen in with equivalence and noninferiority trials to the equivalence margins when the trial is complete. that a bioequivalence trial a 90% confidence interval for the relative bioavailability of a new that from to we only that the relative bioavailability lies between the conventional of and because these the predefined equivalence can we that it lies between and The interval based on the data is the appropriate one to Hence, if the changed to this study would have satisfactory There is no question of a selection However, if the trial in a confidence interval from to then a change of equivalence margins to would not be acceptable because of the conclusion that the equivalence margin was chosen to the These apply to the 95% confidence intervals used for clinical equivalence and for noninferiority. The confidence interval based on the results of the trial is always the best summary of the It is the choice of equivalence margin that is subject to This should be chosen on the basis of and not chosen to the This Points to has been from the perspective of an efficacy trial active with a single primary variable. In practice some studies have more than one primary and most studies have respect to switching of these requires separate in the of the specific drug development, separate conclusions superiority or noninferiority for in judgement whether the trial as a has established the superiority or noninferiority of the new treatment will upon the requirements for that clinical and the of results all relevant The covered in these Points to can also be applied to specific safety when these have been as endpoints of a trial to compare active In practice the of switching objectives is not relevant to trials, even where noninferiority to is a valuable i.e. for safety The problem of switching objectives can be by a trial in the that both noninferiority and superiority are of value. In this case all the issues in this document should be addressed In the statistical analysis should be using an appropriate from noninferiority to superiority. The interpretation of superiority trials as noninferiority trials and vice is best by the results as a confidence interval for the difference between the test treatment and control. There is no problem associated with the use of this confidence interval as a basis for of interpretation. For a and trial, there are difficulties with the change from noninferiority to superiority that cannot be addressed by appropriate analysis. However, there are more difficulties associated with the switch from superiority to noninferiority because of the possible need to a basis and on, a margin of equivalence after the and because of the difficulties of noninferiority trials. There are for the design of a superiority trial in which noninferiority might be an acceptable When the results with respect to alternative of the equivalence margins the problem from to switch to wider acceptable that equivalence margins may be in this

Oded Goldreich

In this chapter we discuss pseudorandom generators. Loosely speaking, these are efficient deterministic programs that expand short, randomly selected seeds into much longer “pseudorandom” bit sequences (see illustration in Figure 3.1). Pseudorandom sequences are defined as computationally indistinguishable from truly random sequences by efficient algorithms. Hence the notion of computational indistinguishability (i.e., indistinguishability by efficient procedures) plays a pivotal role in our discussion. Furthermore, the notion of computational indistinguishability plays a key role also in subsequent chapters, in particular in the discussions of secure encryption, zero-knowledge proofs, and cryptographic protocols. The theory of pseudorandomness is also applied to functions, resulting in the notion of pseudorandom functions, which is a useful tool for many cryptographic applications. In addition to definitions of pseudorandom distributions, pseudorandom generators, and pseudorandom functions, this chapter contains constructions of pseudorandom generators (and pseudorandom functions) based on various types of one-way functions. In particular, very simple and efficient pseudorandom generators are constructed based on the existence of one-way permutations. We highlight the hybrid technique , which plays a central role in many of the proofs. (For the first use and further discussion of this technique, see Section 3.2.3.) Organization . Basic discussions, definitions, and constructions of pseudorandom generators appear in Sections 3.1–3.4: We start with a motivating discussion (Section 3.1), proceed with a general definition of computational indistinguishability (Section 3.2) next present and discuss definitions of pseudorandom generators (Section 3.3), and finally present some simple constructions (Section 3.4). More general constructions are discussed in Section 3.5.

Josef Pieprzyk, Thomas Hardjono, Jennifer Seberry

Summary A summary is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content.

Olivier Baudron, Pierre-Alain Fouque, David Pointcheval, Jacques Stern · 5 authors

The aim of electronic voting schemes is to provide a set of protocols that allow voters to cast ballots while a group of authorities collect the votes and output the final tally. In this paper we describe a practical multi-candidate election scheme that guarantees privacy of voters, public verifiability, and robustness against a coalition of malicious authorities. Furthermore, we address the problem of receipt-freeness and incoercibility of voters. Our new scheme is based on the Paillier cryptosystem and on some related zero-knowledge proof techniques. The voting schemes are very practical and can be efficiently implemented in a real system.

Joe Kilian, Erez Petrank, Ransom Richardson

A proof is concurrent zero-knowledge if it remains zero-knowledge when many copies of the proof are run in an asynchronous environment, such as the Internet. It is known that zero-knowledge is not necessarily preserved in such an environment. Designing concurrent zero-knowledge proofs is a fundamental issue in the study of zero-knowledge since known zero-knowledge protocols cannot be run in a realistic modern computing environment. In this paper we present a concurrent zero-knowledge proof systems for all languages in NP. Currently, the proof system we present is the only known proof system that retains the zero-knowledge property when copies of the proof are allowed to run in an asynchronous environment. Our proof system has $\tilde{O}(\log^2 k)$ rounds (for a security parameter $k$), which is almost optimal, as it is shown by Canetti Kilian Petrank and Rosen that black-box concurrent zero-knowledge requires $\tildeΩ(\log k)$ rounds. Canetti, Goldreich, Goldwasser and Micali introduced the notion of {\em resettable} zero-knowledge, and modified an earlier version of our proof system to obtain the first resettable zero-knowledge proof system. This protocol requires $k^{θ(1)}$ rounds. We note that their technique also applies to our current proof system, yielding a resettable zero-knowledge proof for NP with $\tilde{O}(\log^2 k)$ rounds.

Joe Kilian, Erez Petrank, Charles Rackoff

We consider zero knowledge interactive proofs in a richer, more realistic communication environment. In this setting, one may simultaneously engage in many interactive proofs, and these proofs may take place in an asynchronous fashion. It is known that zero-knowledge is not necessarily preserved in such an environment; we show that for a large class of protocols, it cannot be preserved. Any 4 round (computational) zero-knowledge interactive proof (or argument) for a non-trivial language L is not black-box simulatable in the asynchronous setting.

Anthony Trewavas, Christopher J. Leaver

No abstract is available for this record.

Anton Štiglić

No abstract is available for this record.

Gilbert H. Daniels

Appropriate therapy for amiodarone-induced thyrotoxicosis (AIT) requires a diagnostic precision that may be difficult to achieve (1). Individual cases are rarely straight forward. On June 14, 1999, a 71-yr-old man was hospitalized with a 1-week history of exertional shortness of breath, foot swelling, and feeling poorly. In 1982, he was hospitalized with congestive heart failure and atrial fibrillation, attributed to myocarditis. In 1985, atrial fibrillation recurred and responded to chronic quinidine therapy. In early 1996, quinidine was stopped, followed by paroxysmal and then persistent atrial fibrillation with congestive heart failure (ejection fraction, 20–25%). Amiodarone (200 mg/day) and coumadin were prescribed. In May 1996, his serum TSH was 0.9 μU/mL. In September 1996, he suffered an acute myocardial infarction and underwent angioplasty of stenoses of the left anterior descending and diagonal coronary arteries. He remained in normal sinus rhythm; coumadin was discontinued. Amiodarone was discontinued in 1997 but successfully restarted in March 1998 when atrial fibrillation recurred (TSH 2.3μ U/mL). Atrial fibrillation recurred and persisted, and amiodarone was discontinued in September 1998, 9 months before admission. On admission (June 1999) he was in atrial fibrillation with a ventricular response of 180. His blood pressure was 90 systolic. He had mild proptosis (left greater than right), lid retraction, neck vein distension, and a slightly enlarged (20–25 g) thyroid. Although bilateral pleural effusions were present on the chest x-ray, interstitial edema was absent. A myocardial infarction was ruled out. His ventricular response was difficult to control despite escalating doses of β-blockers. Laboratory studies are summarized in Table 1. Laboratory data Normal range: T4, 4.5–10.9 μg/dL; free T4 index, 4.5–10.9; T3 RIA, 60–180 ng/dL; TSH, 0.5–5.0 μU/mL. Free T4, 0.7–1.5 (ng/dl); TSI, 0–129%; TBII, 0–9.9%; urine iodide, 42–350 μg/L. Laboratory data Normal range: T4, 4.5–10.9 μg/dL; free T4 index, 4.5–10.9; T3 RIA, 60–180 ng/dL; TSH, 0.5–5.0 μU/mL. Free T4, 0.7–1.5 (ng/dl); TSI, 0–129%; TBII, 0–9.9%; urine iodide, 42–350 μg/L. His 20-min 99m pertechnetate uptake was low at 0.19% (normal range, 0.5–3.75). AIT was diagnosed, possibly secondary to Graves’ disease. He was begun on methimazole (10 mg, po, tid), prednisone (40 mg, po, daily), iopanoic acid (500 mg, po, bid), metoprolol (200 mg, 4 id), and heparin, coumadin, and verapamil in doses up to 120 mg, tid. At the time of discharge his heart rate was 100–120. He was discharged on June 23, 1999, on methimazole (10 mg, po, tid), prednisone (40 mg, po, daily), iopanoic acid (500 mg, po, bid), lopressor (75 mg, 4 id), verapamil (20 mg, tid), lasix (20 mg, po, qd), and coumadin. Prednisone was discontinued after June 24. On July 2, he was in atrial fibrillation with a ventricular response of 104–108; his blood pressure was 90/60. He had lost 12 lbs since his hospital admission and noted less exertional shortness of breath. Mild proptosis, left greater than right, was noted (Hürthle exophthalmometer: left, 20 mm; right, 19 mm). TSH-binding inhibitory immunoglobulin titers (TBIIs) had been completed and were weakly positive. Graves’ disease was considered likely. On July 22, his pulse was 120 (AF). His dyspnea was unchanged, but he had a single episode of angina relieved by nitroglycerine. He noted increased fatigue and heat sensitivity. Methimazole was increased to 20 mg three times daily. Iopanoic acid was continued. On August 6, his radial pulse was 116–120. His ventricular rate on electrocardiogram was 139, increased compared with his previous electrocardiogram, and worsening ST segment depression was present. Although his dyspnea was stable, edema had increased to the mid-calf. His cardiologist considered hospital admission, but careful outpatient observation was the final recommendation. On August 17, thyroidectomy was recommended, in part, based on a serum T4 of 25.9 μg/dL, although his serum T3 had fallen to 140 ng/mL. A bilateral thyroidectomy was performed on September 10 without incident or complications. Pathological examination revealed an enlarged thyroid gland (right lobe, 5 × 2.5 × 1.5 cm; left lobe, 4.5 × 2.5 × 3 cm), but no weight was recorded. The final pathology report read: “Enlarged thyroid with fibrosis and mild chronic inflammation. There is no evidence of malignancy.” We asked to have the pathological material re-assessed. An addendum was reported: “The thyroid is diffusely affected with the lesions described as follows. Approximately half of the areas contained islands of dilated thyroid follicles that were lined by attenuated follicular epithelial cells. These islands are separated by areas of collapsed thyroid follicles admixed with fibrosis and prominent vasculature. Nonspecific findings including histocytes and eosinophilic bodies were present. These changes are consistent with those described in amiodarone-associated thyrotoxicosis” (2). Subsequent hypothyroidism was treated with levothyroxine. In December 1999, he remained in atrial fibrillation, but his ventricular response was 60. Amiodarone is an iodinated benzofuran derivative that is approved for the therapy of life-threatening recurrent ventricular arrhythmias (3) but is also used to treat angina, paroxysmal supraventricular tachycardia, and atrial fibrillation and to maintain normal sinus rhythm after cardioversion for atrial fibrillation (4). Amiodarone contains 75 mg iodine per 200-mg tablet and releases∼ 10% of the iodine as free iodide daily (5). Amiodarone is highly lipophilic and is concentrated in adipose tissue, cardiac and skeletal muscle, as well as the thyroid (6). With prolonged use, amiodarone has an elimination half-life as long as 100 days (6) Amiodarone effects on thyroid function result from iodine release and intrinsic drug properties (7). Pharmacologic iodide administration to euthyroid individuals with intrinsically normal thyroid glands results in transient inhibition of thyroid hormone synthesis and release, decreased thyroidal iodide trapping, and enhanced T4 (3,3′,5,5′ tetraiodothyronine) rather than T3 (3,3′,5 triiodothyronine) production by the thyroid, so-called autoregulatory functions (8). The net effect is a slight serum TSH increase that occasionally exceeds the normal range (9, 10). With chronically higher iodide intake, the prevalence of Hashimoto’s thyroiditis increases in genetically susceptible human and animal populations (11–13). In addition, pharmacologic iodide administration may precipitate hypothyroidism in patients with Hashimoto’s thyroiditis (14). Approximately 6% of patients receiving amiodarone develop iodine-induced hypothyroidism; the prevalence is higher in areas of iodine sufficiency and lower in iodine-deficient areas (15). Hypothyroidism may develop as soon as 2 weeks and as long as 39 weeks after starting amiodarone (7). Iodide supplementation in iodine-deficient endemic goiter populations triggers epidemics of hyperthyroidism in a minority of the population, the so-called Jod-Basedow phenomenon (16). Eighty-five percent of these hyperthyroid patients have nodular goiters. Autonomous areas within the nodular thyroid gland overproduce thyroid hormone when exposed to excess substrate (iodide) but are relatively impervious to the autoregulatory effects of iodine (17). However, some hyperthyroid patients have diffuse thyroidal uptake suggestive of Graves’ disease (18). As in the Hashimoto’s thyroiditis example above, excess iodide seems to trigger or facilitate an immunological attack on the thyroid (19). Additionally, borderline iodine-deficient patients with Graves’ disease in remission commonly relapse after adding 500 μg iodide daily (20), an amount comparable with the daily iodide intake in many iodide-sufficient areas. Pharmacologic doses of iodide may also precipitate hyperthyroidism in euthyroid individuals with nodular thyroid glands in iodine-sufficient regions (21). Case reports (22) and the amiodarone experience suggest that iodine excess may also precipitate Graves’ hyperthyroidism in iodine-sufficient areas, but this conclusion is uncertain. Amiodarone also has powerful effects on thyroid hormone metabolism (7). Amiodarone inhibits the peripheral conversion of T4 to T3 and may inhibit T3 receptor binding and action (23–25). In euthyroid individuals, T4 and free T4 concentrations increase by 42% due to decreased T4 clearance (7). Reverse T3 (3,3′5′ triiodothyronine) concentration rises by 172%. Efficacy and toxicity of amiodarone may be proportional to reverse T3 concentration (26). Serum T3 concentrations initially decline by 20–25%, subsequently an average 16% below baseline, but may be frankly low in some patients (7, 27). Serum TSH rises, occasionally out of the normal range, but with chronic administration generally remains in the normal to high normal range. It is uncertain whether TSH elevation in the 10–20 μU/mL range represents peripheral subclinical hypothyroidism or is a pituitary specific effect of amiodarone. Some authors accept subnormal serum TSH concentrations with normal T3 concentrations as compatible with the euthyroid state. However, I interpret these findings as evidence of amiodarone-induced subclinical hyperthyroidism. The 24-h radioiodine uptake decreases to low levels (<4%) in euthyroid individuals taking amiodarone (28). This is to be expected because 15 mg inorganic iodide daily, after a loading dose of 30 mg, decreases mean 24-h radioiodine uptake to less than 2% after 12 days (10). When added to antithyroid drugs, amiodarone facilitates the treatment of severe hyperthyroidism (29), by inhibiting T4 to T3 conversion, thyroid hormone release, and possibly T3 receptor binding and action. Unfortunately, 3% of patients exposed to amiodarone develop hyperthyroidism (30), with a higher prevalence in iodine-deficient regions (15). AIT may have a male predominance (31), reflecting the higher cardiovascular disease prevalence in men. Hyperthyroidism may occur 4 months to 3 yr after initiating therapy or after drug withdrawal (28) and is not related to cumulative drug dosage (7). Knowledge of three distinct types of AIT is required to understand this case (1, 30). Amiodarone-induced toxic nodular goiter, a form of iodine-induced thyrotoxicosis, was described in Europe where large nodular goiters are more prevalent than in the United States. Despite antithyroid drug therapy, some patients demonstrated refractory hyperthyroidism (28). The addition of perchlorate to antithyroid drugs decreased the time to euthyroidism in uncontrolled trials (32, 33). Perchlorate inhibits the thyroidal iodide trap and permits the back diffusion of free (nonorganified) iodide from the thyroid gland, so-called perchlorate “discharge” (34). Doses of perchlorate higher than 1.5 g per day may cause aplastic anemia, whereas doses of 1 g per day used in these studies are apparently safe. Emergency thyroidectomy was required in some patients, a courageous approach in these critically ill patients. The mechanism of refractory hyperthyroidism is uncertain. Thyroidal iodine stores are much higher in hyperthyroid compared with euthyroid patients receiving amiodarone (34A ). The expanded iodide pool is invoked to explain refractory hyperthyroidism, because antithyroid drugs prevent thyroid hormone synthesis but not hormone release. However, pharmacologic iodide inhibits thyroid hormone release from autonomous nodular thyroid glands when new hormone production is blocked by antithyroid drugs (35). Although amiodarone was often discontinued at the onset of thyrotoxicosis, a continued high iodide environment persisted due to its long half-life. A second group of patients treated with amiodarone developed Graves’ hyperthyroidism characterized by diffuse thyroid enlargement, a prolonged course, and the presence of thyroid autoantibodies (30). T-cell populations specific for Graves’ disease have been demonstated as well (36). Most authors infer that “latent” Graves’ disease was made overt by an iodine-stimulated immune attack on the thyroid. Proof of this assumption requires specific markers for genetic Graves’ disease. Toxic nodular goiter and Graves’ disease comprise Type I AIT, hyperthyroidism in patients with preexisting or “latent” thyroid disease. Type II AIT is a form of “destructive thyroiditis” (37), which develops in patients with baseline normal thyroid glands. Hyperthyroidism is due to release of stored thyroid hormone. The thyroid is usually nontender, but pain may occur. The sedimentation rate is generally within normal limits. Amiodarone, its metabolites, and intrathyroidal iodide have all been implicated in cellular toxicity, however, amiodarone is also toxic to cells that do not incorporate iodine (38, 39). Hyperthyroidism lasts for 1–3 months, until thyroid hormone stores are depleted, but resolves more quickly after glucocorticoid therapy. Transient and rarely permanent hypothyroidism may ensue, but the prevalence is uncertain (37). Subacute lymphocytic thyroiditis (“silent thyroiditis”) and subacute granulomatous thyroiditis (“painful subacute thyroiditis”, de Quervain’s thyroiditis) are worthy of study as other examples of destructive thyroiditis that follow a similar course (40). Hyperthyroidism with a nil 24-h radioiodine uptake is often followed by hypothyroidism. Subacute lymphocytic thyroiditis is an autoimmune disorder with a predilection for the postpartum period (postpartum thyroiditis). Thyroid autoantibodies are generally present, diffuse lymphocytic infiltration is found on biopsy, and permanent hypothyroidism occurs in a significant minority of patients. Subacute granulomatous thyroiditis is characterized by intense thyroid pain, a very high sedimentation rate, severe thyroid follicle disruption, and multinucleate giant cells. Permanent hypothyroidism is rare (41). Amiodarone-induced destructive thyroiditis seems not to be an autoimmune disorder because antithyroid antibodies are generally absent. Hypothyroidism, when it occurs, is usually transient. Although limited numbers of such thyroids have been examined, follicular disruption, zones of fibrosis, and mild inflammatory changes are usually present, but dense lymphocytic infiltration and multinucleated giant cells are usually absent (2, 38). Type II AIT was diagnosed on histological examination of our patient’s thyroid gland; hyperplastic changes of Graves’ disease were absent. Type II is the most common variety of AIT in our clinic. Type I AIT is more common in Europe; the geographic differences likely reflect the higher iodine intake in the United States. Many patients with AIT II demonstrate minimal transient hyperthyroidism, diagnosed by fully suppressed TSH alone (personal observation). Permanent hypothyroidism is rare, even when amiodarone is continued (personal observation). Some episodes of Type II AIT may represent subacute lymphocytic thyroiditis precipitated by amiodarone (42). Occasional patients develop repeated cycles of hypothyroidism, followed by hyperthyroidism (43) Appropriate therapy of AIT requires a clear distinction between Type I and Type II AIT. How can this be accomplished (Table 2)? AIT-differential diagnosis and therapy Based on European experience (see text). AIT-differential diagnosis and therapy Based on European experience (see text). Given the high iodine content of amiodarone, a nil 24-h radioiodine uptake might be expected in all patients taking this drug. However, detectable or normal 24-h radioiodine uptake is found in 80% of patients with amiodarone-associated hypothyroidism in Europe (44). Furthermore, in Europe type I AIT is accompanied by low, normal, or high 24-h radioiodine uptake, a possible consequence of baseline borderline low iodide intake (45, 46). The radioiodine uptake is near zero in all patients with Type II AIT. A normal or high radioiodine uptake effectively excludes Type II AIT, however, a nil uptake cannot distinguish between Type I or Type II. All patients with Type I and Type II AIT seen in our Thyroid Clinic have a near nil uptake. Systemic radiodine studies of Type I AIT are needed in the United States. If confirmed, our observations suggest that 24-h radioiodine uptakes are superfluous in AIT in the United States. A low (0.19%) 20-min 99m pertechnetate uptake was measured in our patient. In contrast to the 24-h radioiodine uptake, this test can be performed while receiving antithyroid drugs, allowing therapy to begin immediately. Thyroid ultrasonography may allow us to discriminate between Type I and Type II AIT. Thyroid nodules are easily diagnosed by ultrasound and in their toxic nodular goiter is effectively However, destructive thyroiditis may with a nodular thyroid Thyroid ultrasound with can thyroid blood Type I AIT with Graves’ disease has normal or increased blood whereas Type II AIT a with decreased In patients with Type I from Type II AIT Many studies on thyroid nodules but not When ultrasonography in patients with AIT, thyroid gland studies be Thyroid as the but experience in iodine-sufficient areas such as the United be before it can be fully other studies antibodies are present in at of patients with Graves’ hyperthyroidism and are generally absent in AIT II. antibodies and are considered specific for Graves’ disease. When thyroid autoantibodies are no can be were found in our Graves’ disease. Serum is a that and T-cell is in Type II AIT and normal to at most slightly in Type in Type II AIT are and in Type I AIT I are However, have seen low concentrations in patients with Type II AIT, reflecting of was not measured in our patient. T3 is a of Graves’ hyperthyroidism. The of serum T3 to T4 concentration is a that can be in Graves’ hyperthyroidism from destructive when radioiodine uptakes cannot be In of patients with Graves’ hyperthyroidism had a T3 to T4 greater than whereas of those with “destructive thyroiditis” and 6% of euthyroid individuals were in this range This has not been in AIT. A low is to be because amiodarone inhibits T4 to T3 conversion, however, a high AIT patients receiving amiodarone have a mean T3 to T4 of whereas AIT patients have a mean of 12 (7). of I and II AIT have not been patient’s T3 to T4 of the diagnosis of Graves’ hyperthyroidism. Type I AIT with Graves’ disease and Type II AIT present with a normal to diffusely enlarged thyroid. or a thyroid Graves’ disease. However, pharmacologic doses of iodide mg/day) thyroidal blood in Graves’ disease and a may within days of iodide administration (personal In our thyroid was to Graves’ hyperthyroidism was diagnosed based on findings and TBII, although this to be We not an ultrasound or in our studies that in might have been The of is uncertain because pathological changes in Type II AIT are often Table 2 the therapy of I and II AIT. of toxic nodular goiter methimazole or perchlorate may be With prolonged hyperthyroidism, or continued amiodarone be considered The of radioiodine therapy in patients with normal or high 24-h radioiodine uptake is uncertain. Type I AIT due to Graves’ disease is treated in a similar 12 patients with Type I AIT (10 with toxic nodular goiters and 2 with Graves’ were treated with a of methimazole and perchlorate All normal free T3 concentrations by 4 weeks A diagnosis of Graves’ hyperthyroidism was made in our patient. Methimazole was and iopanoic acid was added to hormone release and inhibit T4 to T3 conversion, functions also by amiodarone. The 24-h urine iodide was perchlorate was not It is to amiodarone for weeks after starting antithyroid drugs in Type I AIT patients, but this is of Although amiodarone serum half-life is the of T4 to T3 inhibition after drug is Hyperthyroidism in Type II AIT is but some patients critically ill with cardiovascular therapy the hyperthyroidism of Type II AIT and may be treated 12 Type II AIT patients with prednisone (40 mg/day) for with a 3 Free T3 and after an average of and In our many patients euthyroid after weeks of However, hyperthyroidism then prednisone be A response to glucocorticoid therapy is an in difficult a diagnosis seems therapy at Type I and Type II AIT including when from and antibodies often days to weeks to was ill on admission. Amiodarone had been discontinued. Although Graves’ disease was the diagnosis based on his methimazole and iopanoic were all prescribed. When the results prednisone was discontinued. The was attributed to iopanoic acid but may have been due to prednisone therapy. In a course of prednisone therapy have been and might have been A for was made when the was When for the was but the and his a The diagnosis was in and therapy with antithyroid drugs might have been In more with a diagnostic approach might have been amiodarone be discontinued in all cases of When the cardiac amiodarone in AIT but therapy for weeks after starting antithyroid Many authors amiodarone in Type II AIT, however, this is the diagnosis is cases of Type II are had been amiodarone for 9 months, Type II thyroid before starting The drug is usually begun in an or by without for thyroid disease. However, a approach be to a history of autoimmune thyroid disease and serum TSH and antithyroid These studies might be in amiodarone-associated hypothyroidism and possibly allow of “latent” Graves’ disease. Thyroid ultrasound patients with nodular thyroid glands at for AIT but its might be more in Europe where AIT I is more AIT to our Although clear are diagnosis and therapy for an may be studies in the United and in AIT are or 99m pertechnetate uptake is but may be superfluous in the United States. Although in some this case the that with AIT.