A Note on Centralizers of Involutions in Coxeter Groups
In this note, we give a remark on the structure of centralizers of involutions in Coxeter groups.
Source author record
Koji Nuida
Koji Nuida appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
ResearcherUnclaimed source record
Catalog footprint
What is connected
16works
11topics
4close collaborators
Research graph
See the researcher in context
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
16 published item(s)
preprint2022arXiv
An Improvement of a Key Exchange Protocol Relying on Polynomial Maps
Akiyama et al. (Int. J. Math. Indust., 2019) proposed a post-quantum key exchange protocol that is based on the hardness of solving a system of multivariate non-linear polynomial equations but has a design strategy different from ordinary multivariate cryptography. Their protocol has two versions, an original one and a modified one, where the modified one has a trade-off that its security is strengthened while it has non-zero error probability in establishing a common key. In fact, the evaluation in their paper suggests that the probability of failing to establish a common key by the modified protocol with the proposed parameter set is impractically high. In this paper, we improve the success probability of Akiyama et al.'s modified key exchange protocol significantly while keeping the security, by restricting each component of the correct common key from the whole of the coefficient field to its small subset. We give theoretical and experimental evaluations showing that our proposed parameter set for our protocol is expected to achieve both failure probability $2^{-120}$ and $128$-bit security level.
0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv
Communication-Efficient (Client-Aided) Secure Two-Party Protocols and Its Application
Secure multi-party computation (MPC) allows a set of parties to compute a function jointly while keeping their inputs private. Compared with the MPC based on garbled circuits,some recent research results show that MPC based on secret sharing (SS) works at a very high speed. Moreover, SS-based MPC can be easily vectorized and achieve higher throughput. In SS-based MPC, however, we need many communication rounds for computing concrete protocols like equality check, less-than comparison, etc. This property is not suited for large-latency environments like the Internet (or WAN). In this paper, we construct semi-honest secure communication-efficient two-party protocols. The core technique is Beaver triple extension, which is a new tool for treating multi-fan-in gates, and we also show how to use it efficiently. We mainly focus on reducing the number of communication rounds, and our protocols also succeed in reducing the number of communication bits (in most cases). As an example, we propose a less-than comparison protocol (under practical parameters) with three communication rounds. Moreover, the number of communication bits is also $38.4\%$ fewer. As a result, total online execution time is $56.1\%$ shorter than the previous work adopting the same settings. Although the computation costs of our protocols are more expensive than those of previous work, we confirm via experiments that such a disadvantage has small effects on the whole online performance in the typical WAN environments.
0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv
Polynomial Expressions of Carries in p-ary Arithmetics
It is known that any $n$-variable function on a finite prime field of characteristic $p$ can be expressed as a polynomial over the same field with at most $p^n$ monomials. However, it is not obvious to determine the polynomial for a given concrete function. In this paper, we study the concrete polynomial expressions of the carries in addition and multiplication of $p$-ary integers. For the case of addition, our result gives a new family of symmetric polynomials, which generalizes the known result for the binary case $p = 2$ where the carries are given by elementary symmetric polynomials. On the other hand, for the case of multiplication of $n$ single-digit integers, we give a simple formula of the polynomial expression for the carry to the next digit using the Bernoulli numbers, and show that it has only $(n+1)(p-1)/2 + 1$ monomials, which is significantly fewer than the worst-case number $p^n$ of monomials for general functions. We also discuss applications of our results to cryptographic computation on encrypted data.
0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv
A mathematical problem for security analysis of hash functions and pseudorandom generators
In this paper, we specify a class of mathematical problems, which we refer to as "Function Density Problems" (FDPs, in short), and point out novel connections of FDPs to the following two cryptographic topics; theoretical security evaluations of keyless hash functions (such as SHA-1), and constructions of provably secure pseudorandom generators (PRGs) with some enhanced security property introduced by Dubrov and Ishai [STOC 2006]. Our argument aims at proposing new theoretical frameworks for these topics (especially for the former) based on FDPs, rather than providing some concrete and practical results on the topics. We also give some examples of mathematical discussions on FDPs, which would be of independent interest from mathematical viewpoints. Finally, we discuss possible directions of future research on other cryptographic applications of FDPs and on mathematical studies on FDPs themselves.
0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv
On affine maps on non-compact convex sets and some characterizations of finite-dimensional solid ellipsoids
Convex geometry has recently attracted great attention as a framework to formulate general probabilistic theories. In this framework, convex sets and affine maps represent the state spaces of physical systems and the possible dynamics, respectively. In the first part of this paper, we present a result on separation of simplices and balls (up to affine equivalence) among all compact convex sets in two- and three-dimensional Euclidean spaces, which focuses on the set of extreme points and the action of affine transformations on it. Regarding the above-mentioned axiomatization of quantum physics, our result corresponds to the case of simplest (2-level) quantum system. We also discuss a possible extension to higher dimensions. In the second part, towards generalizations of the framework of general probabilistic theories and several existing results including ones in the first part from the case of compact and finite-dimensional physical systems as in most of the literatures to more general cases, we study some fundamental properties of convex sets and affine maps that are relevant to the above subject.
0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv
A characterization of finitely generated reflection subgroups of Coxeter groups orthogonal to a reflection
Given a reflection $r$ in a Coxeter group $W$ (possibly of infinite rank), we consider the subgroup of $W$ generated by the reflections in $W$ having (-1)-eigenvectors orthogonal to the (-1)-eigenvector of $r$. In this paper, we determine completely when this subgroup is finitely generated, by using preceding results on centralizers of reflections. This result provides a new and naturally constructed example of a family of non-finitely generated subgroups of finitely generated groups.
0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv
On centralizers of parabolic subgroups in Coxeter groups
Let $W$ be an arbitrary Coxeter group, possibly of infinite rank. We describe a decomposition of the centralizer $Z_W(W_I)$ of an arbitrary parabolic subgroup $W_I$ into the center of $W_I$, a Coxeter group and a subgroup defined by a 2-cell complex. Only information about finite parabolic subgroups is required in an explicit computation. Moreover, by using our description of $Z_W(W_I)$, we reveal a further strong property of the action of the third factor on the second factor, in particular on the finite irreducible components of the second factor.
0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv
On finite factors of centralizers of parabolic subgroups in Coxeter groups
It has been known that the centralizer $Z_W(W_I)$ of a parabolic subgroup $W_I$ of a Coxeter group $W$ is a split extension of a naturally defined reflection subgroup by a subgroup defined by a 2-cell complex $\mathcal{Y}$. In this paper, we study the structure of $Z_W(W_I)$ further and show that, if $I$ has no irreducible components of type $A_n$ with $2 \leq n < \infty$, then every element of finite irreducible components of the inner factor is fixed by a natural action of the fundamental group of $\mathcal{Y}$. This property has an application to the isomorphism problem in Coxeter groups.
0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv
Locally parabolic subgroups in Coxeter groups of arbitrary ranks
Despite the significance of the notion of parabolic closures in Coxeter groups of finite ranks, the parabolic closure is not guaranteed to exist as a parabolic subgroup in a general case. In this paper, first we give a concrete example to clarify that the parabolic closure of even an irreducible reflection subgroup of countable rank does not necessarily exist as a parabolic subgroup. Then we propose a generalized notion of "locally parabolic closure" by introducing a notion of "locally parabolic subgroups", which involves parabolic ones as a special case, and prove that the locally parabolic closure always exists as a locally parabolic subgroup. It is a subgroup of parabolic closure, and we give another example to show that the inclusion may be strict in general. Our result suggests that locally parabolic closure has more natural properties and provides more information than parabolic closure. We also give a result on maximal locally finite, locally parabolic subgroups in Coxeter groups, which generalizes a similar well-known fact on maximal finite parabolic subgroups.
0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv
Physical Equivalence of Pure States and Derivation of Qubit in General Probabilistic Theories
In this paper, we investigate a characterization of Quantum Mechanics by two physical principles based on general probabilistic theories. We first give the operationally motivated definition of the physical equivalence of states and consider the principle of the physical equivalence of pure states, which turns out to be equivalent to the symmetric structure of the state space. We further consider another principle of the decomposability with distinguishable pure states. We give classification theorems of the state spaces for each principle, and derive the Bloch ball in 2 and 3 dimensional systems by these principles.
0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv
Short collusion-secure fingerprint codes against three pirates
In this article, we propose a new construction of probabilistic collusion-secure fingerprint codes against up to three pirates and give a theoretical security evaluation. Our pirate tracing algorithm combines a scoring method analogous to Tardos codes (J. ACM, 2008) with an extension of parent search techniques of some preceding 2-secure codes. Numerical examples show that our code lengths are significantly shorter than (about 30% to 40% of) the shortest known c-secure codes by Nuida et al. (Des. Codes Cryptogr., 2009) with c = 3. Some preliminary proposal for improving efficiency of our tracing algorithm is also given.
0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv
A Characterization of Signed Graphs with Generalized Perfect Elimination Orderings
An important property of chordal graphs is that these graphs are characterized by existence of perfect elimination orderings on their vertex sets. In this paper, we generalize the notion of perfect elimination orderings to signed graphs, and give a characterization for graphs admitting such orderings, together with characterizations restricted to some subclasses and further properties of those graphs.
0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv
Distinguishability Measures and Entropies for General Probabilistic Theories
As a part of the construction of an information theory based on general probabilistic theories, we propose and investigate the several distinguishability measures and "entropies" in general probabilistic theories. As their applications, no-cloning theorems, information-disturbance theorems are reformulated, and a bound of the accessible informations is discussed in any general probabilistic theories, not resorting to quantum theory.
0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv
Optimal Observables for Minimum-Error State Discrimination in General Probabilistic Theories
General Probabilistic Theories provide the most general mathematical framework for the theory of probability in an operationally natural manner, and generalize classical and quantum theories. In this article, we study state-discrimination problems in general probabilistic theories using a Bayesian strategy. After re-formulation of the theories with mathematical rigor, we first prove that an optimal observable to discriminate any (finite) number of states always exists in the most general setting. Next, we revisit our recently proposed geometric approach for the problem and show that, for two-state discrimination, this approach is indeed effective in arbitrary dimensional cases. Moreover, our method reveals an operational meaning of Gudder's ``intrinsic metric'' by means of the optimal success probability, which turns out to be a generalization of the trace distance for quantum systems. As its by-product, an information-disturbance theorem in general probabilistic theories is derived, generalizing its well known quantum version.
0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv
Pattern occurrence in the dyadic expansion of square root of two and an analysis of pseudorandom number generators
Recently, designs of pseudorandom number generators (PRNGs) using integer-valued variants of logistic maps and their applications to some cryptographic schemes have been studied, due mostly to their ease of implementation and performance. However, it has been noted that this ease is reduced for some choices of the PRNGs accuracy parameters. In this article, we show that the distribution of such undesirable accuracy parameters is closely related to the occurrence of some patterns in the dyadic expansion of the square root of 2. We prove that for an arbitrary infinite binary word, the asymptotic occurrence rate of these patterns is bounded in terms of the asymptotic occurrence rate of zeroes. We also present examples of infinite binary words that tightly achieve the bounds. As a consequence, a classical conjecture on asymptotic evenness of occurrence of zeroes and ones in the dyadic expansion of the square root of 2 implies that the asymptotic rate of the undesirable accuracy parameters for the PRNGs is at least 1/6.
0 citations0 reviewsNo code linkedOpen access