The Experts below are selected from a list of 87036 Experts worldwide ranked by ideXlab platform
Chaoping Xing - One of the best experts on this subject based on the ideXlab platform.
-
optimal algebraic manipulation detection codes in the Constant Error model
Theory of Cryptography Conference, 2015Co-Authors: Ronald Cramer, Carles Padro, Chaoping XingAbstract:Algebraic manipulation detection (AMD) codes, introduced at EUROCRYPT 2008, may, in some sense, be viewed as keyless combinatorial authentication codes that provide security in the presence of an oblivious, algebraic attacker. Its original applications included robust fuzzy extractors, secure message transmission and robust secret sharing. In recent years, however, a rather diverse array of additional applications in cryptography has emerged. In this paper we consider, for the first time, the regime of arbitrary positive Constant Error probability e in combination with unbounded cardinality M of the message space. There are several applications where this model makes sense. Adapting a known bound to this regime, it follows that the binary length ρ of the tag satisfies ρ ≥ loglogM + Ω e (1). In this paper, we shall call AMD codes meeting this lower bound optimal. Known constructions, notably a construction based on dedicated polynomial evaluation codes, are a multiplicative factor 2 off from being optimal. By a generic enhancement using Error-correcting codes, these parameters can be further improved but remain suboptimal. Reaching optimality efficiently turns out to be surprisingly nontrivial. We propose a novel constructive method based on symmetries of codes. This leads to an explicit construction based on certain BCH codes that improves the parameters of the polynomial construction and to an efficient randomized construction of optimal AMD codes based on certain quasi-cyclic codes. In all our results, the Error probability e can be chosen as an arbitrarily small positive real number.
-
optimal algebraic manipulation detection codes in the Constant Error model
2014Co-Authors: Ronald Cramer, Carles Padro, Chaoping XingAbstract:Algebraic manipulation detection (AMD) codes, introduced at EUROCRYPT 2008, may, in some sense, be viewed as keyless combinatorial authentication codes that provide security in the presence of an oblivious, algebraic attacker. Its original applications included robust fuzzy extractors, secure message transmission and robust secret sharing. In recent years, however, a rather diverse array of additional applications in cryptography has emerged. In this paper we consider, for the first time, the regime of arbitrary positive Constant Error probability e in combination with unbounded cardinality M of the message space. There are several applications where this model makes sense. Adapting a known bound to this regime, it follows that the binary length ρ of the tag satisfies ρ ≥ log logM +Ωe(1). In this paper, we shall call AMD codes meeting this lower bound optimal. Known constructions, notably a construction based on dedicated polynomial evaluation codes, are a multiplicative factor 2 off from being optimal. By a generic enhancement using Error-correcting codes, these parameters can be further improved but remain suboptimal. Reaching optimality efficiently turns out to be surprisingly nontrivial. Owing to our refinement of the mathematical perspective on AMD codes, which focuses on symmetries of codes, we propose novel constructive principles. This leads to an explicit construction based on certain BCH codes that improves the parameters of the polynomial construction and to an efficient randomized construction of optimal AMD codes based on certain quasi-cyclic codes. In all our results, the Error probability e can be chosen as an arbitrarily small positive real number.
Guy Bresler - One of the best experts on this subject based on the ideXlab platform.
-
the two user gaussian interference channel a deterministic view
arXiv: Information Theory, 2008Co-Authors: Guy Bresler, David TseAbstract:This paper explores the two-user Gaussian interference channel through the lens of a natural deterministic channel model. The main result is that the deterministic channel uniformly approximates the Gaussian channel, the capacity regions differing by a universal Constant. The problem of finding the capacity of the Gaussian channel to within a Constant Error is therefore reduced to that of finding the capacity of the far simpler deterministic channel. Thus, the paper provides an alternative derivation of the recent Constant gap capacity characterization of Etkin, Tse, and Wang. Additionally, the deterministic model gives significant insight towards the Gaussian channel.
-
the two user gaussian interference channel a deterministic view
European Transactions on Telecommunications, 2008Co-Authors: Guy BreslerAbstract:SUMMARY This paper explores the two-user Gaussian interference channel through the lens of a natural deterministic channel model. The main result is that the deterministic channel uniformly approximates the Gaussian channel, the capacity regions differing by a universal Constant. The problem of finding the capacity of the Gaussian channel to within a Constant Error is therefore reduced to that of finding the capacity of the far simpler deterministic channel. Thus, the paper provides an alternative derivation of the recent Constant gap capacity characterisation of Etkin, Tse and Wang. Additionally, the deterministic model gives significant insight towards the Gaussian channel. Copyright © 2008 John Wiley & Sons, Ltd.
Ronald Cramer - One of the best experts on this subject based on the ideXlab platform.
-
optimal algebraic manipulation detection codes in the Constant Error model
Theory of Cryptography Conference, 2015Co-Authors: Ronald Cramer, Carles Padro, Chaoping XingAbstract:Algebraic manipulation detection (AMD) codes, introduced at EUROCRYPT 2008, may, in some sense, be viewed as keyless combinatorial authentication codes that provide security in the presence of an oblivious, algebraic attacker. Its original applications included robust fuzzy extractors, secure message transmission and robust secret sharing. In recent years, however, a rather diverse array of additional applications in cryptography has emerged. In this paper we consider, for the first time, the regime of arbitrary positive Constant Error probability e in combination with unbounded cardinality M of the message space. There are several applications where this model makes sense. Adapting a known bound to this regime, it follows that the binary length ρ of the tag satisfies ρ ≥ loglogM + Ω e (1). In this paper, we shall call AMD codes meeting this lower bound optimal. Known constructions, notably a construction based on dedicated polynomial evaluation codes, are a multiplicative factor 2 off from being optimal. By a generic enhancement using Error-correcting codes, these parameters can be further improved but remain suboptimal. Reaching optimality efficiently turns out to be surprisingly nontrivial. We propose a novel constructive method based on symmetries of codes. This leads to an explicit construction based on certain BCH codes that improves the parameters of the polynomial construction and to an efficient randomized construction of optimal AMD codes based on certain quasi-cyclic codes. In all our results, the Error probability e can be chosen as an arbitrarily small positive real number.
-
optimal algebraic manipulation detection codes in the Constant Error model
2014Co-Authors: Ronald Cramer, Carles Padro, Chaoping XingAbstract:Algebraic manipulation detection (AMD) codes, introduced at EUROCRYPT 2008, may, in some sense, be viewed as keyless combinatorial authentication codes that provide security in the presence of an oblivious, algebraic attacker. Its original applications included robust fuzzy extractors, secure message transmission and robust secret sharing. In recent years, however, a rather diverse array of additional applications in cryptography has emerged. In this paper we consider, for the first time, the regime of arbitrary positive Constant Error probability e in combination with unbounded cardinality M of the message space. There are several applications where this model makes sense. Adapting a known bound to this regime, it follows that the binary length ρ of the tag satisfies ρ ≥ log logM +Ωe(1). In this paper, we shall call AMD codes meeting this lower bound optimal. Known constructions, notably a construction based on dedicated polynomial evaluation codes, are a multiplicative factor 2 off from being optimal. By a generic enhancement using Error-correcting codes, these parameters can be further improved but remain suboptimal. Reaching optimality efficiently turns out to be surprisingly nontrivial. Owing to our refinement of the mathematical perspective on AMD codes, which focuses on symmetries of codes, we propose novel constructive principles. This leads to an explicit construction based on certain BCH codes that improves the parameters of the polynomial construction and to an efficient randomized construction of optimal AMD codes based on certain quasi-cyclic codes. In all our results, the Error probability e can be chosen as an arbitrarily small positive real number.
John Watrous - One of the best experts on this subject based on the ideXlab platform.
-
fast parallel circuits for the quantum fourier transform
Foundations of Computer Science, 2000Co-Authors: Richard Cleve, John WatrousAbstract:We give new bounds on the circuit complexity of the quantum Fourier transform (QFT). We give an upper bound of O(log n+log log(1//spl epsiv/)) on the circuit depth for computing an approximation of the QFT with respect to the modulus 2/sup n/ with Error bounded by /spl epsiv/. Thus, even for exponentially small Error, our circuits have depth O(log n). The best previous depth bound was O(n), even for approximations with Constant Error. Moreover, our circuits have size O(n log(n//spl epsiv/)). As an application of this depth bound, we show that P. Shor's (1997) factoring algorithm may be based on quantum circuits with depth only O(log n) and polynomial size, in combination with classical polynomial-time pre- and postprocessing. Next, we prove an /spl Omega/(log n) lower bound on the depth complexity of approximations of the QFT with Constant Error. This implies that the above upper bound is asymptotically tight (for a reasonable range of values of /spl epsiv/). We also give an upper bound of O(n(log n)/sup 2/ log log n) on the circuit size of the exact QFT modulo 2/sup n/, for which the best previous bound was O(n/sup 2/). Finally, based on our circuits for the QFT with power-of-2 moduli, we show that the QFT with respect to an arbitrary modulus m can be approximated with accuracy /spl epsiv/ with circuits of depth O((log log m)(log log 1//spl epsiv/)) and size polynomial in log m+log(1//spl epsiv/).
-
fast parallel circuits for the quantum fourier transform
arXiv: Quantum Physics, 2000Co-Authors: Richard Cleve, John WatrousAbstract:We give new bounds on the circuit complexity of the quantum Fourier transform (QFT). We give an upper bound of O(log n + log log (1/epsilon)) on the circuit depth for computing an approximation of the QFT with respect to the modulus 2^n with Error bounded by epsilon. Thus, even for exponentially small Error, our circuits have depth O(log n). The best previous depth bound was O(n), even for approximations with Constant Error. Moreover, our circuits have size O(n log (n/epsilon)). We also give an upper bound of O(n (log n)^2 log log n) on the circuit size of the exact QFT modulo 2^n, for which the best previous bound was O(n^2). As an application of the above depth bound, we show that Shor's factoring algorithm may be based on quantum circuits with depth only O(log n) and polynomial-size, in combination with classical polynomial-time pre- and post-processing. In the language of computational complexity, this implies that factoring is in the complexity class ZPP^BQNC, where BQNC is the class of problems computable with bounded-Error probability by quantum circuits with poly-logarithmic depth and polynomial size. Finally, we prove an Omega(log n) lower bound on the depth complexity of approximations of the QFT with Constant Error. This implies that the above upper bound is asymptotically optimal (for a reasonable range of values of epsilon).
Ryoichi Nagatomi - One of the best experts on this subject based on the ideXlab platform.
-
position of compression garment around the knee affects healthy adults knee joint position sense acuity
Human Movement Science, 2019Co-Authors: Li Yin Zhang, Janos Negyesi, Tibor Hortobagyi, Takeshi Okuyama, Mami Tanaka, Ryoichi NagatomiAbstract:Abstract Athletes use compression garments (CGs) to improve sport performance, accelerate rehabilitation from knee injuries or to enhance joint position sense (JPS). The position of CGs around the knee may affect knee JPS but the data is inconsistent. The purpose of the present study was to determine the effects of CG position on healthy adults’ knee joint position sense acuity. In a counterbalanced, single-blinded study, 16 healthy young adults (8 female, age: 25.5 y) performed an active knee joint position-matching task with and without (CON) a below-knee (BK), above-knee (AK), or whole-knee (WK) CG in a randomized order on the dominant (CompDom) or the non-dominant leg (CompNon-Dom). We also determined the magnitude of tissue compression by measuring anatomical thigh and calf cross sectional area (CSA) in standing using magnetic resonance imaging (MRI). Subjects had less absolute repositioning Error (magnitude of Error) in BK compared with CON condition. On the other hand, the analysis of the direction of Error (Constant Error) revealed that in each condition subjects tended to underestimate the target position (AK, BK and CON: 75%; WK: 94%). In WK condition there was a significantly larger negative Error (−2.7 ± 3.4) as compared with CON (−1.6 ± 3.7) condition. There also was less variable Error, in WK compared to BK and CON conditions, indicating less variability in their position sense using a WK CG, regardless of the underestimation. CG reduced thigh CSA by 4.5 cm2 or 3% and calf CSA by Δ1.3 cm2 or 1%. The position of CG relative to the knee modifies knee JPS. The findings helps us better understand how the application of a WK CG may support athletic activities.
