Abstract A major research area in discrete geometry is to consider the best way to partition the d -dimensional Euclidean space $$\mathbb {R}^d$$ R d under various quality criteria. In this paper we introduce a new type of space partitioning that is motivated by the problem of rounding noisy measurements from the continuous space $$\mathbb {R}^d$$ R d to a discrete subset of representative values. Specifically, we study partitions of $$\mathbb {R}^d$$ R d into bounded-size tiles colored by one of k colors, such that tiles of the same color have a distance of at least t from each other. Such tilings allow for error-resilient rounding, as two points of the same color and distance less than t from each other are guaranteed to belong to the same tile, and thus, to be rounded to the same point. The main problem we study in this paper is characterizing the achievable tradeoffs between the number of colors k and the distance t , for various dimensions d . On the qualitative side, we show that in $$\mathbb {R}^d$$ R d , using $$k=d+1$$ k = d + 1 colors is both sufficient and necessary to achieve $$t>0$$ t > 0 . On the quantitative side, we achieve numerous upper and lower bounds on t as a function of k . In particular, for $$d=3,4,8,24$$ d = 3 , 4 , 8 , 24 , we obtain sharp asymptotic bounds on t , as $$k \rightarrow \infty $$ k → ∞ . We obtain our results with a variety of techniques including isoperimetric inequalities, the Brunn-Minkowski theorem, sphere packing bounds, Bapat’s connector-free lemma, and Čech cohomology.

Abstract Feistel structures are an extensively researched type of cryptographic schemes. In this paper, we describe improved attacks on Feistel structures with more than 4 rounds. We achieve this by a new attack that combines the main benefits of meet-in-the-middle attacks (which can reduce the time complexity by comparing only half blocks in the middle) and dissection attacks (which can reduce the memory complexity but have to guess full blocks in the middle in order to perform independent attacks above and below it). For example, for a 7-round Feistel structure on n -bit inputs with seven independent round keys of n /2 bits each, a MITM attack can use ( $$2^{1.5n}$$ 2 1.5 n , $$2^{1.5n}$$ 2 1.5 n ) time and memory, while dissection requires ( $$2^{2n}$$ 2 2 n , $$2^{n}$$ 2 n ) time and memory. Our new attack requires only ( $$2^{1.5n}$$ 2 1.5 n , $$2^{n}$$ 2 n ) time and memory, using a few known plaintext/ciphertext pairs. When we are allowed to use more known plaintexts, we develop new techniques which rely on the existence of multi-collisions and differential properties deep in the structure in order to further reduce the memory complexity. Our new attacks are not just theoretical generic constructions—in fact, we can use them to reduce the memory complexity of the best known attacks on several concrete cryptosystems such as round-reduced CAST-128 (where we reduce the complexity from $$2^{111} $$ 2 111 to $$2^{64}$$ 2 64 ) and full DEAL-256 (where we reduce the complexity from $$2^{200}$$ 2 200 to $$2^{144}$$ 2 144 ), without affecting their time and data complexities. An extension of our techniques applies even to some non-Feistel structures—for example, in the case of FOX, we reduce the memory complexity of all the best known attacks by a factor of $$2^{16}$$ 2 16 .

Current adversarial attacks for multi-class classifiers choose potential adversarial target classes naively based on the classifier's confidence levels. We present a novel adversarial targeting method, \textit{MALT - Mesoscopic Almost Linearity Targeting}, based on local almost linearity assumptions. Our attack wins over the current state of the art AutoAttack on the standard benchmark datasets CIFAR-100 and Imagenet and for different robust models. In particular, our attack uses a \emph{five times faster} attack strategy than AutoAttack's while successfully matching AutoAttack's successes and attacking additional samples that were previously out of reach. We additionally prove formally and demonstrate empirically that our targeting method, although inspired by linear predictors, also applies to non-linear models.

Abstract Boomerang attacks are extensions of differential attacks that make it possible to combine two unrelated differential properties of the first and second part of a cryptosystem with probabilities p and q into a new differential-like property of the whole cryptosystem with probability $$p^2q^2$$ p 2 q 2 (since each one of the properties has to be satisfied twice). In this paper, we describe a new version of boomerang attacks which uses the counterintuitive idea of throwing out most of the data in order to force equalities between certain values on the ciphertext side. In certain cases, this creates a correlation between the four probabilistic events, which increases the probability of the combined property to $$p^2q$$ p 2 q and increases the signal-to-noise ratio of the resultant distinguisher. We call this variant a retracing boomerang attack since we make sure that the boomerang we throw follows the same path on its forward and backward directions. To demonstrate the power of the new technique, we apply it to the case of 5-round AES. This version of AES was repeatedly attacked by a large variety of techniques, but for twenty years its complexity had remained stuck at $$2^{32}$$ 2 32 . At Crypto’18, it was finally reduced to $$2^{24}$$ 2 24 (for full key recovery), and with our new technique, we can further reduce the complexity of full key recovery to the surprisingly low value of $$2^{16.5}$$ 2 16.5 (i.e., only 90, 000 encryption/decryption operations are required for a full key recovery). In addition to improving previous attacks, our new technique unveils a hidden relationship between boomerang attacks and two other cryptanalytic techniques, the yoyo game and the recently introduced mixture differentials.

In this paper, we introduce a novel side-channel attack for eavesdropping sound using an electro-optical sensor. We show how small vibrations of a hanging bulb (in response to sound hitting its surface), can be exploited by eavesdroppers to recover sound. We evaluate our method's performance in a realistic setup and show that our method can be used by eavesdroppers to recover songs from a target room containing the hanging light bulb.

A major research area in discrete geometry is to consider the best way to partition the $d$-dimensional Euclidean space $\mathbb{R}^d$ under various quality criteria. In this paper we introduce a new type of space partitioning that is motivated by the problem of rounding noisy measurements from the continuous space $\mathbb{R}^d$ to a discrete subset of representative values. Specifically, we study partitions of $\mathbb{R}^d$ into bounded-size tiles colored by one of $k$ colors, such that tiles of the same color have a distance of at least $t$ from each other. Such tilings allow for \emph{error-resilient} rounding, as two points of the same color and distance less than $t$ from each other are guaranteed to belong to the same tile, and thus, to be rounded to the same point. The main problem we study in this paper is characterizing the achievable tradeoffs between the number of colors $k$ and the distance $t$, for various dimensions $d$. On the qualitative side, we show that in $\mathbb{R}^d$, using $k=d+1$ colors is both sufficient and necessary to achieve $t>0$. On the quantitative side, we achieve numerous upper and lower bounds on $t$ as a function of $k$. In particular, for $d=3,4,8,24$, we obtain sharp asymptotic bounds on $t$, as $k \to \infty$. We obtain our results with a variety of techniques including isoperimetric inequalities, the Brunn-Minkowski theorem, sphere packing bounds, Bapat's connector-free lemma, and Čech cohomology.

The problem of online checkpointing is a classical problem with numerous applications that has been studied in various forms for almost 50 years. In the simplest version of this problem, a user has to maintain k memorized checkpoints during a long computation, where the only allowed operation is to move one of the checkpoints from its old time to the current time, and his goal is to keep the checkpoints as evenly spread out as possible at all times. Bringmann, Doerr, Neumann, and Sliacan studied this problem as a special case of an online/offline optimization problem in which the deviation from uniformity is measured by the natural discrepancy metric of the worst case ratio between real and ideal segment lengths. They showed this discrepancy is smaller than 1.59-o(1) for all k and smaller than ln 4-o(1)≈ 1.39 for the sparse subset of k ’s, which are powers of 2. In addition, they obtained upper bounds on the achievable discrepancy for some small values of k . In this article, we solve the main problems left open in the above-mentioned paper by proving that ln 4 is a tight upper and lower bound on the asymptotic discrepancy for all large k and by providing tight upper and lower bounds (in the form of provably optimal checkpointing algorithms, some of which are in fact better than those of Bringmann et al.) for all the small values of k ≤ 10. In the last part of the article, we describe some new applications of this online checkpointing problem.

In an "open skies" era in which drones fly among us, a new question arises: how can we tell whether a passing drone is being used by its operator for a legitimate purpose (e.g., delivering pizza) or an illegitimate purpose (e.g., taking a peek at a person showering in his/her own house)? Over the years, many methods have been suggested to detect the presence of a drone in a specific location, however since populated areas are no longer off limits for drone flights, the previously suggested methods for detecting a privacy invasion attack are irrelevant. In this paper, we present a new method that can detect whether a specific POI (point of interest) is being video streamed by a drone. We show that applying a periodic physical stimulus on a target/victim being video streamed by a drone causes a watermark to be added to the encrypted video traffic that is sent from the drone to its operator and how this watermark can be detected using interception. Based on this method, we present an algorithm for detecting a privacy invasion attack. We analyze the performance of our algorithm using four commercial drones (DJI Mavic Air, Parrot Bebop 2, DJI Spark, and DJI Mavic Pro). We show how our method can be used to (1) determine whether a detected FPV (first-person view) channel is being used to video stream a POI by a drone, and (2) locate a spying drone in space; we also demonstrate how the physical stimulus can be applied covertly. In addition, we present a classification algorithm that differentiates FPV transmissions from other suspicious radio transmissions. We implement this algorithm in a new invasion attack detection system which we evaluate in two use cases (when the victim is inside his/her house and when the victim is being tracked by a drone while driving his/her car); our evaluation shows that a privacy invasion attack can be detected by our system in about 2-3 seconds.

At CRYPTO'98, Bleichenbacher published his seminal paper which described a padding oracle attack against RSA implementations that follow the PKCS #1 v1.5 standard. Over the last twenty years researchers and implementors had spent a huge amount of effort in developing and deploying numerous mitigation techniques which were supposed to plug all the possible sources of Bleichenbacher-like leakages. However, as we show in this paper, most implementations are still vulnerable to several novel types of attack based on leakage from various microarchitectural side channels: Out of nine popular implementations of TLS that we tested, we were able to break the security of seven implementations with practical proof-of-concept attacks. We demonstrate the feasibility of using those Cache-like ATacks (CATs) to perform a downgrade attack against any TLS connection to a vulnerable server, using a BEAST-like Man in the Browser attack. The main difficulty we face is how to perform the thousands of oracle queries required before the browser's imposed timeout (which is 30 seconds for almost all browsers, with the exception of Firefox which can be tricked into extending this period). Due to its use of adaptive chosen ciphertext queries, the attack seems to be inherently sequential, but we describe a new way to parallelize Bleichenbacher-like padding attacks by exploiting any available number of TLS servers that share the same public key certificate. With this improvement, we can demonstrate the feasibility of a downgrade attack which could recover all the 2048 bits of the RSA plaintext (including the premaster secret value, which suffices to establish a secure connection) from five available TLS servers in under 30 seconds. This sequential-to-parallel transformation of such attacks can be of independent interest, speeding up and facilitating other side channel attacks on RSA implementations.

In the area of espionage between countries, an infiltration covert channel used to trigger a silent malware installed on a network of a critical organization (such as 911 services and missile launching facility) from the outside world is extremely dangerous to the target country's security. In order to prevent attackers from establishing such a channel, these organizations take various steps to secure their networks, to make the establishment of this type of covert channel very challenging and almost impractical to achieve; the current state of the art methods are very limited and ineffective. In this paper, we show that even a strong isolation technique, such as air-gapping the network, can be circumvented by using an organizational multifunction printer (MFP) to establish an infiltration covert channel in order to communicate with a malware installed on an isolated organization from the outside. We show how an attacker can leverage the light sensitivity of an MFP and use different light sources to infiltrate commands to the malware in the organization. We analyze the influence of light intensity, distance, transmission rate, ambient light, and wavelength on the covert channel. In addition we demonstrate the attack on a real organization using: 1) a laser attached to a tripod stand; 2) a laser carried by a drone; and 3) a hijacked smart bulb that is not even connected to the organization's network and is accessed and controlled by an attacker in a passing car. We prove that locating the scanner in an inner room inside an organization does not prevent an attacker from establishing the covert channel. We show how our covert channel can be established from a greater distance (900 m) and at a higher transmission rate of 200 bits/s than other methods used to infiltrate data to an organization, even using invisible light (covertly).

Today, about 10% of TLS connections are still using CBC-mode cipher suites, despite a long history of attacks and the availability of better options (e.g. AES-GCM). In this work, we present three new types of attack against four popular fully patched implementations of TLS (Amazon's s2n, GnuTLS, mbed TLS and wolfSSL) which elected to use "pseudo constant time" countermeasures against the Lucky 13 attack on CBC-mode. Our attacks combine several variants of the PRIME+PROBE cache timing technique with a new extension of the original Lucky 13 attack. They apply in a cross-VM attack setting and are capable of recovering most of the plaintext whilst requiring only a moderate number of TLS connections. Along the way, we uncovered additional serious (but easy to patch) bugs in all four of the TLS implementations that we studied; in three cases, these bugs lead to Lucky 13 style attacks that can be mounted remotely with no access to a shared cache. Our work shows that adopting pseudo constant time countermeasures is not sufficient to attain real security in TLS implementations in CBC mode.

The problem of online checkpointing is a classical problem with numerous applications which had been studied in various forms for almost 50 years. In the simplest version of this problem, a user has to maintain k memorized checkpoints during a long computation, where the only allowed operation is to move one of the checkpoints from its old time to the current time, and his goal is to keep the checkpoints as evenly spread out as possible at all times. At ICALP'13 Bringmann et al. studied this problem as a special case of an online/offline optimization problem in which the deviation from uniformity is measured by the natural discrepancy metric of the worst case ratio between real and ideal segment lengths. They showed this discrepancy is smaller than 1.59-o(1) for all k, and smaller than ln4-o(1)~~1.39 for the sparse subset of k's which are powers of 2. In addition, they obtained upper bounds on the achievable discrepancy for some small values of k. In this paper we solve the main problems left open in the ICALP'13 paper by proving that ln4 is a tight upper and lower bound on the asymptotic discrepancy for all large k, and by providing tight upper and lower bounds (in the form of provably optimal checkpointing algorithms, some of which are in fact better than those of Bringmann et al.) for all the small values of k <= 10.

Within the next few years, billions of IoT devices will densely populate our cities. In this paper we describe a new type of threat in which adjacent IoT devices will infect each other with a worm that will rapidly spread over large areas, provided that the density of compatible IoT devices exceeds a certain critical mass. In particular, we developed and verified such an infection using the popular Philips Hue smart lamps as a platform. The worm spreads by jumping directly from one lamp to its neighbors, using only their built-in ZigBee wireless connectivity and their physical proximity. The attack can start by plugging in a single infected bulb anywhere in the city, and then catastrophically spread everywhere within minutes. It enables the attacker to turn all the city lights on or off, to permanently brick them, or to exploit them in a massive DDOS attack. To demonstrate the risks involved, we use results from percolation theory to estimate the critical mass of installed devices for a typical city such as Paris whose area is about 105 square kilometers: The chain reaction will fizzle if there are fewer than about 15,000 randomly located smart lamps in the whole city, but will spread everywhere when the number exceeds this critical mass (which had almost certainly been surpassed already). To make such an attack possible, we had to find a way to remotely yank already installed lamps from their current networks, and to perform over-the-air firmware updates. We overcame the first problem by discovering and exploiting a major bug in the implementation of the Touchlink part of the ZigBee Light Link protocol, which is supposed to stop such attempts with a proximity test. To solve the second problem, we developed a new version of a side channel attack to extract the global AES-CCM key (for each device type) that Philips uses to encrypt and authenticate new firmware. We used only readily available equipment costing a few hundred dollars, and managed to find this key without seeing any actual updates. This demonstrates once again how difficult it is to get security right even for a large company that uses standard cryptographic techniques to protect a major product.

In this paper we consider the security aspects of Internet of Things (IoT) devices, which bridge the physical and virtual worlds. We propose a new taxonomy of attacks, which classifies them into four broad categories. The most interesting category (which we call functionality extension attacks) uses the designed functionality of the IoT device to achieve a totally different effect. To demonstrate this type of attack, we consider the case of smart lights (whose original functionality is just to control the color and intensity of the lights in a particular room) and show how to use them to achieve unrelated effects. In the first attack, we use smart lights as a covert LIFI communication system to exfiltrate data from a highly secure (or even fully airgapped) office building. We implemented the attack and were able to read the leaked data from a distance of over 100 meters using only cheap and readily available equipment. In another attack, we showed that an attacker can strobe the lights at a frequency which may trigger seizures in people suffering from photosensitive epilepsy (in the same way that rapidly flashing video games can cause such seizures). In our experiments, we have tested both high-end and lower-end smart light systems, ranging from an expensive Philips HUE system to a cheap system manufactured by LimitlessLED. In addition, we consider other weaknesses of the systems we tested, and propose feasible remedies for the problems we found.

Over the last 20 years, the privacy of most GSM phone conversations was protected by the A5/1 and A5/2 stream ciphers, which were repeatedly shown to be cryptographically weak. They are being replaced now by the new A5/3 and A5/4 algorithms, which are based on the block cipher KASUMI. In this paper we describe a new type of attack called a sandwich attack , and use it to construct a simple related-key distinguisher for 7 of the 8 rounds of KASUMI with an amazingly high probability of 2 −14 . By using this distinguisher and analyzing the single remaining round, we can derive the complete 128-bit key of the full KASUMI with a related-key attack which uses only 4 related keys, 2 26 data, 2 30 bytes of memory, and 2 32 time. These completely practical complexities were experimentally verified by performing the attack in less than two hours on a single-core of a PC. Interestingly, neither our technique nor any other published attack can break the original MISTY block cipher (on which KASUMI is based) significantly faster than exhaustive search. Our results thus indicate that the modifications made by ETSI’s SAGE group in moving from MISTY to KASUMI made it extremely weak when related-key attacks are allowed, but do not imply anything about its resistance to single-key attacks. Consequently, there is no indication that the way KASUMI is implemented in GSM and 3G networks is practically vulnerable in any realistic attack model.

The privacy of most GSM phone conversations is currently protected by the 20+ years old A5/1 and A5/2 stream ciphers, which were repeatedly shown to be cryptographically weak. They will soon be replaced by the new A5/3 (and the soon to be announced A5/4) algorithm based on the block cipher KASUMI, which is a modified version of MISTY. In this paper we describe a new type of attack called a sandwich attack, and use it to construct a simple distinguisher for 7 of the 8 rounds of KASUMI with an amazingly high probability of 2− 14. By using this distinguisher and analyzing the single remaining round, we can derive the complete 128 bit key of the full KASUMI by using only 4 related keys, 226 data, 230 bytes of memory, and 232 time. These complexities are so small that we have actually simulated the attack in less than two hours on a single PC, and experimentally verified its correctness and complexity. Interestingly, neither our technique nor any other published attack can break MISTY in less than the 2128 complexity of exhaustive search, which indicates that the changes made by ETSI’s SAGE group in moving from MISTY to KASUMI resulted in a much weaker cipher.

Side channel attacks are typically divided into two phases: In the collection phase the attacker tries to measure some physical property of the implementation, and in the analysis phase he tries to derive the cryptographic key from the measured information. The field is highly fragmented, since there are many types of leakage, and each one of them usually requires a different type of analysis. In this paper we formalize a general notion of leakage attacks on iterated cryptosystems, in which the attacker can collect (via physical probing, power measurement, or any other type of side channel) one bit of information about the intermediate state of the encryption after each round. Since bits computed during the early rounds can be usually represented by low degree multivariate polynomials in the plaintext and key bits, we can use the recently discovered cube attack as a generic analysis phase which can be applied in principle to any type of leaked data. However, the original cube attack requires extremely clean data, whereas the information provided by side channel attacks can be quite noisy. To address this problem, we develop in this paper a new type of robust cube attack, which can recover the key even when some of the leaked bits are unreliable. In particular, we show how to exploit trivial equations (of the form 0 = 0, which are plentiful but useless in standard cube attacks) in order to correct a fraction of measurement errors which can be arbitrarily close to 1. Finally, we demonstrate our approach by describing efficient leakage attacks on Serpent (requiring only 218 time for full key recovery when the leaked state bits are clean) and on AES (requiring 235 time in the same scenario), and show how to make them robust with a small additional complexity.

This paper proposes new chosen-message power-analysis attacks for public-key cryptosystems based on modular exponentiation, where specific input pairs are used to generate collisions between squaring operations at different locations in the two power traces. Unlike previous attacks of this kind, the new attack can be applied to all standard implementations of the exponentiation process, namely binary (left-to-right and right-to-left), m-ary, and sliding window methods. The proposed attack can also circumvent typical countermeasures, such as the Montgomery powering ladder and the double-add algorithm. The effectiveness of the attack is demonstrated in experiments with hardware and software implementations of RSA on an FPGA and a PowerPC processor, respectively. In addition to the new collision generation methods, a highly accurate waveform matching technique is introduced for detecting the collisions even when the recorded signals are noisy and there is a certain amount of clock jitter.

Side-channel attacks are used by cryptanalysts to compromise the implementation of secure systems. One very powerful class of side-channel attacks is power analysis, which tries to extract cryptographic keys and passwords by examining the power consumption of a device. We examine the applicability of this threat to electromagnetically coupled RFID tags. Compared to standard power analysis attacks, our attack is unique in that it requires no physical contact with the device under attack. Power analysis can be carried out even if both the tag and the attacker are passive and transmit no data, making the attack very hard to detect. As a proof of concept, we describe a password extraction attack on Class 1 Generation 1 EPC tags. We also show how the privacy of Class 1 Generation 2 tags can be compromised by this attack. Finally, we examine possible modifications to the tag and its RF front end which help protect against power analysis attacks.

In this paper we show how to construct noninteractive zero knowledge proofs for any NP statement under general (rather than number theoretic) assumptions, and how to enable polynomially many provers to give polynomially many such proofs based on a single random string. Our constructions can be used in cryptographic applications in which the prover is restricted to polynomial time.

In this paper we consider the difficulty of factoring multivariate polynomials F(z, y, z,...) modulo n.We consider in particular the case in which F is a product of two randomly chosen polynomials P and Q with algebraically specified coefficients, sample space, regardless of what may be known about its form.

In this paper, it is proven that when both randomization and interaction are allowed, the proofs that can be verified in polynomial time are exactly those proofs that can be generated with polynomial space.

A major open problem in the theory of multiprover protocols is to characterize the languages which can be accepted by fully parallelized protocols which achieve an exponentially low probability of cheating in a single round. The problem was motivated by the observation that the probability of cheating the n parallel executions of a multiprover protocol can be exponentially higher than the probability of cheating in n sequential executions of the same protocol. The problem is solved by proving that any language in NEXP-time has a fully parallelized multiprover protocol. By combining this result with a fully parallelized version of the protocol of M. Ben-Or et al. (ACM Symp. on Theory of Computing, 1988), a one-round perfect zero-knowledge protocol (under no cryptographic assumptions) can be obtained for every NEXPTIME language.>

The authors solve the two major open problems associated with noninteractive zero-knowledge proofs: how to enable polynomially many provers to prove in writing polynomially many theorems based on the basis of a single random string, and how to construct such proofs under general (rather than number-theoretic) assumptions. The constructions can be used in cryptographic applications in which the prover is restricted to polynomial time, and they are much simpler than earlier (and less capable) proposals.>

It is proved that, when both randomization and interaction are allowed, the proofs that can be verified in polynomial time are exactly those proofs that can be generated with polynomial space. The interactive proofs introduced use only public coins, are accepted with probability one when the prover is honest, require only logarithmic workspace when the verifier is given a two-way access to his or her random tape, and by the use of known techniques can be turned into zero-knowledge proofs under the sole assumption that one-way functions exist.>

A two party protocol in which party A uses one of several secret witnesses to an NP assertion is witness indistinguishable if party B cannot tell which witness A is actually using.The protocol is witness hiding if by the end of the protocol B cannot compute any new witness which he did not know before the protocol began.Witness hiding is a natural security requirement, and can replace zero knowledge in many cryptographic protocols.We prove two central results: 1.Unlike zero knowledge protocols, witness indistinguishablity is preserved under arbitrary composition of protocols, including parallel execution.2. If a statement has at least two independent witnesses, then any witness indistinguishable protocol for this statement is also witness hiding.part of the paper is devoted to showing that if a protocol is WI, and if w(z) contains at least two independent witnesses, then the protocol must be WH.The WH property is a natural property which is sufficient to guarantee overall security of many cryptographic schemes (nontransitivity of proofs of knowledge, unforgeable proofs of identity etc.).It is natural to compare the concept of WH to that of zero knowledge (ZK [15]).ZK guarantees that no information whatsoever leaks during the execution of

In this paper we consider the one-way function fg,N(X) = gX (modN), where N is a Blum integer.We prove that under the commonly assumed intractability of factoring Blum integers, almost all its bits are individually hard, and half of them are simultaneously hard.As a result, fg,N can be used in efficient pseudo-random bit generators and multi-bit commitment schemes, where messages can be drawn according to arbitrary probability distributions.

Planning is defined as the problem of synthesizing a desired behavior from given basic operations, and learning is defined as the dual problem of analyzing a given behavior to determine the unknown basic operations. Algorithms for solving these problems in the context of invertible operations on finite-state environments are developed. In addition to their obvious artificial intelligence applications, the algorithms can efficiently find the shortest way to solve Rubik's cube, test ping-pong protocols, and solve systems of equations over permutation groups.>

Abstract Consider a “sea” of M squares which contains (at some unknown location) a “battleship” of K squares. Both the sea and the battleship can assume any rectangular shape. Our goal is to find the battleship by probing at least one of its squares. In this paper we describe a deterministic strategy for this problem which is guaranteed to locate the battleship in at most c1 M/K probes, where c1 ≈︁ 3.065.

We propose a general polynomial time algorithm to find small integer solutions to systems of linear congruences. We use this algorithm to obtain two polynomial time algorithms for reconstructing the values of variables $x_1 , \cdots ,x_k $ when we are given some linear congruences relating them together with some bits obtained by truncating the binary expansions of the variables. The first algorithm reconstructs the variables when either the high order bits or the low order bits of the $x_i $ are known. It is essentially optimal in its use of information in the sense that it will solve most problems almost as soon as the variables become uniquely determined by their constraints. The second algorithm reconstructs the variables when an arbitrary window of consecutive bits of the variables is known. This algorithm will solve most problems when twice as much information as that necessary to uniquely determine the variables is available. Two cryptanalytic applications of the algorithms are given: predicting linear congruential generators whose outputs are truncated and breaking the simplest version of Blum’s protocol for exchanging secrets.

In this paper we extend the notion of zero knowledge proofs of membership (which reveal one bit of information) to zero knowledge proofs of knowledge (which reveal no information whatsoever). After formally defining this notion, we show its relevance to identification schemes, in which parties prove their identity by demonstrating their knowledge rather than by proving the validity of assertions. We describe a novel scheme which is provably secure if factoring is difficult and whose practical implementations are about two orders of magnitude faster than RSA-based identification schemes. In the last part of the paper we consider the question of sequential versus parallel executions of zero knowledge protocols, define a new notion of “transferable information”, and prove that the parallel version of our identification scheme (which is not known to be zero knowledge) is secure since it reveals no transferable information.

In this paper we prove a 3n upper and lower bound on the complexity of sorting on a n × n mesh connected parallel computer, and describe an exceptionally simple algorithm which sorts the array by alternately sorting its rows and columns log log n times.

In this paper we describe a polynomial time algorithm for computing the values of variables x1, … xk when some of their bits and some linear relationships between them are known. The algorithm is essentially optimal in its use of information in the sense that it can be applied as soon as the values of the xi become uniquely determined by the constraints. Its cryptanalytic significance is demonstrated by two applications: breaking linear congruential generators whose outputs are truncated, and breaking Blum's protocol for exchanging secrets.

This paper proposes a novel architecture for massively parallel systolic computers, which is based on results from lattice theory. In the proposed architecture, each processor is connected to four other processors via constant-lenght wires in an regular borderless pattern. The mapping of processes to processors is continuous, and the architecture guarantees exceptional load uniformity for rectangular process arrays of arbitrary sizes. In addition, no timesharing is ever required when the ration of processes to processors is smaller than 1//spl radic/5.

Electronic messages, documents and checks must be authenticated by digital signatures which are not forgeable even by their recipients. The RSA system can generate and verify such signatures, but each message requires hundreds of high precision modular multiplications which can be implemented efficiently only on special purpose hardware. In this paper we propose a new signature scheme which can be easily implemented in software on microprocessors: signature generation requires one modular multiplication and one modular division, signature verification requires three modular multiplications, and the key size is comparable to that of the RSA system. The new scheme is based on the quadratic equation m = s21 + ks22 (mod n), where m is the message, s1 and s2 are the signature, and k and n are the publicly known key. While we cannot prove that the security of the scheme is equivalent to factoring, all the known methods for solving this quadratic equation for arbitrary k require the extraction of square roots modulo n or the solution of similar problems which are at least as hard as factoring. A novel property of the new scheme is that legitimate users can choose k in such a way that they can sign messages even without knowing the factorization of n, and thus everyone can use the same modulus if no one knows its factorization.

Storage media such as digital optical discs, PROM's, or punched cards consist of a number of write-once bit positions (WIT's); each WIT initially contains a "0" that may later be irreversibly overwritten with a "r'. Rivest and Shamir have shown that such write-once memories (WOM's) can be reused very efficiently. Generalized WOM's are considered, in which the basic storage element has more than two possible states and the legal state transitions are described by an arbitrary directed acyclic graph. The capabilities of such memories depend on the depth of the graphs rather than on their size, and the decision problem associated with the generalized WOM's in NP-hard even for3-ary symbols rewritten several times or multiple values rewritten once.

The Merkle-Hellman cryptosystem is one of the two major public-key cryptosystems proposed so far. It is shown that the basic variant of this cryptosystem, in which the elements of the public key are modular multiples of a superincreasing sequence, is breakable in polynomial time.

The ability to “hide” one bit in trapdoor functions has recently gained much interest in cryptography research, and is of great importance in many transactions protocols. In this paper we study the cryptographic security of RSA bits. In particular, we show that unless the cryptanalyst can completely break the RSA encryption, any heuristic he uses to determine the least significant bit of the cleartext must have an error probability greater than 1/4—e A similar result is shown for Rabin's encryption scheme.

This paper shows how to generate from a short random seed a long sequence of pseudorandom numbers which is cryptogrgraphically strong in the sense that knowing some sequence elements cannot possibly help the cryptanalyst to determine other sequence elements.The method is based on the RSA cryptosystem, and it is the first published example of a pseudorandom sequence generator for which such a property has been formally proved.

The cryptographic security of the Merkle-Hellman cryptosystem has been a major open problem since 1976. In this paper we show that the basic variant of this cryptosystem, in which the elements of the public key are modular multiples of a superincreasing sequence, is breakable in polynomial time.

Storage media such as digital optical disks, PROMS, or paper tape consist of a number of “write-once” bit positions (wits); each wit initially contains a “0” that may later be irreversibly overwritten with a “I”. We demonstrate that such “write-once memories” (woms) can be “rewritten” to a surprising degree. For example, only 3 wits suffice to represent any 2-bit value in a way that can later be updated to represent any other 2-bit value. For large k, 1.29... k wits suffice to represent a k-bit value in a way that can be similarly updated. Most surprising, allowing t writes of a k-bit value requires only t + o(t) wits, for any fixed k. For fixed t, approximately k.t/log(t) wits are required as k → @@@@. An n-wit WOM is shown to have a “capacity” (i.e. k.t when writing a k-bit value t times) of up to n.log(n) bits.

In this paper we develop a general-purpose algorithm that can solve a number of NP-complete problems in time $T = O(2^{n/2} )$ and space $S = O(2^{n/4} )$. The algorithm can be generalized to a family of algorithms whose time and space complexities are related by $T \cdot S^2 = O(2^n )$. The problems it can handle are characterized by a few decomposition axioms; they include knapsack problems, exact satisfiability problems, set covering problems, etc. The new algorithm has considerable cryptanalytic significance, since it can break knapsack-based cryptosystems with up to $n = 100$ generators.

In 1978, Merkle and Hellman introduced a knapsack-based public-key cryptosystem, which received widespread attention. The two major open problems concerning this cryptosystem are: (i) Security: How difficult are the Merkle-Hellman knapsacks? (ii) Efficiency: Can the huge key size be reduced? In this paper we analyze the cryptographic security of knapsack problems with small keys, develop a new (non-enumerative)type of algorithm for solving them, and use the algorithm to show that under certain assumptions it is as difficult to find the hidden trapdoors in Merkle-Hellman knapsacks as it is to solve general knapsack problems.

A simplified version of the Merkle-Hellman public key cryptographic system is breakable. While their full-fledged system seems to be resistant to the cryptanalytic attack we propose, the result suggests some ways in which the security of their system can be enhanced.

In this paper we develop a general purpose algorithm that can solve a number of NP-complete problems in time T = O(2n/2) and space S = O(2n/4). The algorithm can be generalized to a family of algorithms whose time and space complexities are related by T·S2 = O(2n). The problems it can handle are characterized by a few decomposition axioms, and they include knapsack problems, exact satisfiability problems, set covering problems, etc. The new algorithm has a considerable cryptanalytic significance, since it can break the Merkle-Hellman public key cryptosystem whose recommended size is n = 100.

A recent trend in cryptographic systems is to base their encryption/decryption functions on NP-complete problems, and in particular on the knapsack problem. To analyze the security of these systems, we need a complexity theory which is less worst-case oriented and which takes into account the extra conditions imposed on the problems to make them cryptographically useful. In this paper we consider the two classes of one-to-one and onto knapsack systems, analyze the complexity of recognizing them and of solving their instances, introduce a new complexity measure (median complexity), and show that this complexity is inversely proportional to the density of the knapsack system. The tradeoff result is based on a fast probabilistic knapsack solving algorithm which is applicable only to one-to-one systems, and it indicates that knapsack-based cryptographic systems in which one can both encrypt and sign messages are relatively insecure. We end the paper with new results about the security of some specific knapsack systems.

The analysis of many processes modeled by directed graphs requires the selection of a subset of vertices which cut all the cycles in the graph. Reducing the size of such a cutset usually leads to a simpler and more efficient analysis, but the problem of finding minimum cutsets in general directed graphs is known to be $NP$-complete. In this paper we show that in reducible graphs (and thus in almost all the “practical” flowcharts of programs), minimum cutsets can be found in linear time. We further show that the linear algorithm can check its own applicability to a given graph, thus eliminating the need of prechecking (in nonlinear time) whether it is reducible or not. An immediate application of this result is in program verification systems based on Floyd’s inductive assertions method.

A very primitive version of Gotlieb’s timetable problem is shown to be NP-complete, and therefore all the common timetable problems are NP-complete. A polynomial time algorithm, in case all teachers are binary, is shown. The theorem that a meeting function always exists if all teachers and classes have no time constraints is proved. The multicommodity integral flow problem is shown to be NP-complete even if the number of commodities is two. This is true both in the directed and undirected cases.

In this paper we define a new type of fixedpoint of recursive definitions and investigate some of its properties. This optimal fixedpoint (which always uniquely exists) contains, in some sense, the maximal amount of “interesting” information which can be extracted from the recursive definition, and it may be strictly more defined than the program’s least fixedpoint. This fixedpoint can be the basis for assigning a new semantics to recursive programs.

A very primitive version of Gotlieb's timetable problem is shown to be NP-complete, and therefore all the common timetable problems are NP-complete. A polynomial time algorithm, in case all teachers are binary, is shown. The theorem that a meeting function always exists if all teachers and classes have no time constraints is proved. The multi-commodity integral flow problem is shown to be NP-complete even if the number of commodities is two. This is true both in the directed and undirected cases. Finally, the two commodity real flow problem in undirected graphs is shown to be solvable in polynomial time. The time bound is O(|v|2|E|).

In this paper a new fixedpoint approach towards the semantics of recursive programs is presented. The fixedpoint defined by a recursive program under this semantics contains, in some sense, the maximal amount of “interesting” information which can be extracted from the program. This optimal fixedpoint (which always uniquely exists) may be strictly more defined than the program's least fixedpoint. We consider both the theoretical and the computational aspects of the approach, as well as some techniques for proving properties of the optimal fixedpoint of a given recursive program.