We show that it is possible to encode any communication protocol between two parties so that the protocol succeeds even if a (1/4 - epsilon) fraction of all symbols transmitted by the parties are corrupted adversarial...
详细信息
ISBN:
(纸本)9781450306911
We show that it is possible to encode any communication protocol between two parties so that the protocol succeeds even if a (1/4 - epsilon) fraction of all symbols transmitted by the parties are corrupted adversarially, at a cost of increasing the communication in the protocol by a constant factor (the constant depends on epsilon). This encoding uses a constant sized alphabet. This improves on an earlier result of Schulman, who showed how to recover when the fraction of errors is bounded by 1/240. We also show how to simulate an arbitrary protocol with a protocol using the binary alphabet, a constant factor increase in communication and tolerating a (1/8 - epsilon) fraction of errors.
Let S-n(lambda) be the set of all permutations over the multiset [GRAPHICS] where n = m lambda. A frequency permutation array (FPA) of minimum distance d is a subset of S-n(lambda) in which every two elements have dis...
详细信息
ISBN:
(纸本)9781457705953
Let S-n(lambda) be the set of all permutations over the multiset [GRAPHICS] where n = m lambda. A frequency permutation array (FPA) of minimum distance d is a subset of S-n(lambda) in which every two elements have distance at least d. FPAs have many applications related to error correcting codes. In coding theory, the Gilbert- Varshamov bound and the spherepacking bound are derived from the size of balls of certain radii. We propose two efficient algorithms that compute the ball size of frequency permutations under Chebyshev distance. Both methods extend previous known results. The first one runs in O((()(2d lambda)2.376)(d lambda) log n) time and O((()(2d lambda)2)(d lambda)) space. The second one runs in O ((()(2d lambda)()(d lambda) (d lambda+lambda))(lambda)n/lambda) time and O((2d lambda)(d lambda)) space. For small constants lambda and d, both are efficient in time and use constant storage space.
In this paper we present a new 5-pass identification scheme with asymptotic cheating probability 1/2 based on the syndrome decoding problem. Our protocol is related to the Stern identification scheme but has a reduced...
详细信息
ISBN:
(纸本)9781457704376
In this paper we present a new 5-pass identification scheme with asymptotic cheating probability 1/2 based on the syndrome decoding problem. Our protocol is related to the Stern identification scheme but has a reduced communication cost compared to previous code-based zeroknowledge schemes, moreover our scheme permits to obtain a very low size of public key and secret key. The contribution of this paper is twofold, first we propose a variation on the Stern authentication scheme which permits to decrease asymptotically the cheating probability to 1/2 rather than 2/3 (and very close to 1/2 in practice) but with less communication. Our solution is based on deriving new challenges from the secret key through cyclic shifts of the initial public key syndrome;a new proof of soundness for this case is given Secondly we propose a new way to deal with hashed commitments in zero-knowledge schemes based on Stern's scheme, so that in terms of communication, on the average, only one hash value is sent rather than two or three. Overall our new scheme has the good features of having a zero-knowledge security proof based on well known hard problem of coding theory, a small size of secret and public key (a few hundred bits), a small calculation complexity, for an overall communication cost of 19kb for authentication (for a 2(16) security) and a signature of size of 93kb (11.5kB) (for security 2(80)), an improvement of 40% compared to previous schemes based on coding theory.
Sidon sequences and their generalizations have found during the years and especially recently various applications in coding theory. One of the most important applications of these sequences is in the connection of sy...
详细信息
ISBN:
(纸本)9781457705953
Sidon sequences and their generalizations have found during the years and especially recently various applications in coding theory. One of the most important applications of these sequences is in the connection of synchronization patterns. A few constructions of two-dimensional synchronization patterns are based on these sequences. In this paper we present sufficient conditions that a two-dimensional synchronization pattern can be transformed into a Sidon sequence. We also present a new construction for Sidon sequences over an alphabet of size q(q - 1), where q is a power of a prime.
Factor graphs are graphical models with origins in coding theory. The sum-product, the max-product, and the min-sum algorithms, which operate by message passing on a factor graph, subsume a great variety of algorithms...
详细信息
ISBN:
(纸本)9781457705953
Factor graphs are graphical models with origins in coding theory. The sum-product, the max-product, and the min-sum algorithms, which operate by message passing on a factor graph, subsume a great variety of algorithms in coding, signal processing, and artificial intelligence. This paper aims at extending the field of possible applications of factor graphs to Lagrangian and Hamiltonian dynamics. The starting point is the principle of least action (more precisely, the principle of stationary action). The resulting factor graphs require a new message-passing algorithm that we call the stationary-sum algorithm. As it turns out, some of the properties of this algorithm are equivalent to Liouville's theorem. Moreover, duality results for factor graphs allow to easily derive Noether's theorem. We also discuss connections and differences to Kalman filtering.
With magnetic storage devices already achieving storage densities of up to 400 Gigabits per square inch (Gb/in²), the state of the art is rapidly approaching theoretical limits (dictated by thermal stability conc...
详细信息
With magnetic storage devices already achieving storage densities of up to 400 Gigabits per square inch (Gb/in²), the state of the art is rapidly approaching theoretical limits (dictated by thermal stability concerns). Hence, there is an effort in the industry to develop alternative magnetic storage technologies. Two-dimensional magnetic recording (TDMR) is one such candidate technology. In contrast to other technologies (e.g. heat-assisted magnetic recording [1], bit-patterned media [2]) which rely on significant changes being made to the recording medium, TDMR relies on the use of traditional recording media, while relying on signal processing to make improvements in the recording density. Though advantageous due to the fact that no drastic re-engineering of media is required, there are significant challenges that need to be addressed in order to make TDMR a viable candidate for next-generation recording systems. The main challenges involved in TDMR arise due to (i) the small bit-area, along with an aggressive write/read process, which leads to a large amount of noise, and (ii) the two-dimensional nature of the recording process – so far not encountered in today's systems. Thus, a gamut of 2D signal processing algorithms need be developed for the compensation of errors occurring due to the aggressive write/read processes. In this dissertation, we present some of the work done with regard to the signal processing tasks involved in TDMR. In particular, we describe our work on (i) channel modelling, (ii) detection strategies, and (iii) error-correction coding strategies targetted at TDMR.
The paper devoted to implementation of the public key algorithm based on directed algebraic graphs over finite commutative ring K and their symmetries. First we expand the key space K n of graph based encryption algor...
详细信息
The paper devoted to implementation of the public key algorithm based on directed algebraic graphs over finite commutative ring K and their symmetries. First we expand the key space K n of graph based encryption algorithm in such way that arbitrary chosen plaintext can be converted to arbitrary chosen ciphertext. Second, we conjugate chosen encryption map, which is a composition of several “elementary” cubical polynomial automorphisms of a free module K n with special invertible affine transformation of K n . Finally we compute symbolically corresponding cubic public map g of K n onto K n . We evaluate time for the generation of g , time of execution of public map, number of monomial expression in the list of corresponding public rules.
A new scheme of quantum key distribution （QKD） using frequency and time coding is proposed, in which the security is based on the frequency-time uncertainty relation. In this scheme, the binary information sequence ...
详细信息
A new scheme of quantum key distribution （QKD） using frequency and time coding is proposed, in which the security is based on the frequency-time uncertainty relation. In this scheme, the binary information sequence is encoded randomly on either the centrM frequency or the time delay of the optical pulse at the sender. The central frequency of the single photon pulse is set as w1 for bit 0 and set as w2 for bit 1 when frequency coding is selected. However, the single photon pulse is not delayed for bit 0 and is delayed in τ for 1 when time coding is selected. At the receiver, either the frequency or the time delay of the pulse is measured randomly, and the final key is obtained after basis comparison, data reconciliation and privacy amplification. With the proposed method, the effect of the noise in the fiber channel and environment on the QKD system can be reduced effectively.
暂无评论