Strict Standards: Declaration of APCBagOStuff::delete() should be compatible with BagOStuff::delete($key,$time = 0) in /usr/share/mediawiki1.7/includes/BagOStuff.php on line 499
Miscellaneous - Wiki

# Miscellaneous

##### KEA1: Knowledge of Exponent assumption

Definition: For any adversary A that takes input q,g,ga and returns (C,Y) with Y = Ca, there exists an “extractor” A, which given the same inputs as A returns c such that gc = C.

Reductions:

Algorithms:

Use in cryptography: In the tractable Rational map Crytosystem. (Huh???)

References:

• Ivan Damgård: Towards Practical Public Key Systems Secure Against Chosen Ciphertext Attacks. CRYPTO 1991: 445-456
• Mihir Bellare, Adriana Palacio: The Knowledge-of-Exponent Assumptions and 3-Round Zero-Knowledge Protocols. CRYPTO 2004: 273-289

Definition: Given a system of m quadratic polynomial equations in n variables each, $\{y_1=p_1(x_1,\ldots,p_n),\ldots,y_m=p_m(x_1,\ldots,x_n)\}$ find a solution $x \in \mathbb{F}^n$ is in general an NP-problem.

Reductions:

Algorithms: Linearization or Gröbner basis.[1]

Use in cryptography:

References:

• Antoine Joux, Sébastian Kunz-Jaques, Frédéric Muller and Pierre-Michel Ricordel:Cryptanalysis of the Tractable Rational Map Crytosystem. PKC 2005 , vol. 3386, pp. 258-274.
• Jaques Patarin: Hidden Field Equations (HFE) and Isomorphism of Polynomials (IP): Two new Families of Asymmetric Algorithms. Proceedins of EUROCRYPT 1996, pp. 33-48.

##### CF: Given-weight codeword finding

Definition: Given a n x k binary linear code C and the corresponding n x (n-k) parity check matrix H, find a vector x such that xH = 0 and x has weight w.

Reductions:

Algorithms:

Use in cryptography: McEliece public key cryptosystem (finding the shortest codeword).

References:

• E.R. Berlekamp, R.J. McEliece and H.C.A. Van Tilborg, On the inherent intractability of certain coding problems. IEEE Trans. Inform. Theory, IT-24(3):384-386, 1978
• F. Chabaud, On the security of Some Cryptosystems Based on Error-correcting Codes, EUROCRYPT 1994, Springer, LCNS 959, 131-139

##### ConjSP: Braid group conjugacy search problem

Definition: Given $x, y \in B_{n}$ to find $a \in B_n$ such that a − 1xa = y.

Reductions:

Algorithms:

Use in cryptography:

History: This is an old problem in computational group theory.

References:

• K.H. Ko, S.J. Lee, J.H. Cheon, J.W. Han, J.S. Kang, C. Park, 'New public-key cryptosystem using Braid groups,' CRYPTO 2000, LNCS 1880, 166-183, 2000

##### GenConjSP: Generalised braid group conjugacy search problem

Definition: Given $x, y \in B_{n}$ to find $a \in B_m$ where $m \le n$ such that a − 1xa = y.

Reductions:

Algorithms:

Use in cryptography: Public-key cryptosystem due to Ko, Lee, Cheon, Han, Kang and Park.

History:

References:

• K.H. Ko, S.J. Lee, J.H. Cheon, J.W. Han, J.S. Kang, C. Park, 'New public-key cryptosystem using Braid groups,' CRYPTO 2000, LNCS 1880, 166-183, 2000

##### ConjDecomP: Braid group conjugacy decomposition problem

Definition: Given $x, y \in B_{n}$ such that y = bxb − 1 for some $b \in B_n$ to find $a', a'' \in B_m$ where m < n such that a'xa'' = y.

Reductions: GenConjSPP ConjSP

Algorithms:

Use in cryptography:

History:

References:

• K.H. Ko, S.J. Lee, J.H. Cheon, J.W. Han, J.S. Kang, C. Park, 'New public-key cryptosystem using Braid groups,' CRYPTO 2000, LNCS 1880, 166-183, 2000

##### ConjDP: Braid group conjugacy decision problem

Definition: Given $x, y \in B_{n}$ to determine whether or not x and y are conjugate, i.e., that there exists $a \in B_n$ such that a − 1xa = y.

Reductions: ConjDPP ConjSP

Algorithms:

Use in cryptography:

History:

References:

• K.H. Ko, S.J. Lee, J.H. Cheon, J.W. Han, J.S. Kang, C. Park, 'New public-key cryptosystem using Braid groups,' CRYPTO 2000, LNCS 1880, 166-183, 2000

##### DHCP: Braid group decisional Diffie-Hellman-type conjugacy problem

Definition: Given $a,w_{l}^{-1}aw_{l}, w_{u}^{-1}aw_{u}$ to determine whether or not $x_{u}^{-1}x_{l}^{-1}ax_{l}x_{u}=w_{u}^{-1}w_{l}^{-1}aw_{l}w_{u}$ for $a \in B_{n}$, $x_{l}, w_{l} \in B_{l}$ and $x_{u}, w_{u} \in B_{u}$

Reductions:

Algorithms: For some parameters an attack in the R. Gennaro, D. Micciancio paper is proposed.

Use in cryptography: Public-key cryptosystem, pseudorandom number generator, pseudorandom synthesizer

History:

References:

• K.H. Ko, S.J. Lee, J.H. Cheon, J.W. Han, J.S. Kang, C. Park, 'New public-key cryptosystem using Braid groups,' CRYPTO 2000, LNCS 1880, 166-183, 2000
• E. Lee, S.J. Lee, S.G. Hahn, 'Pseudorandomness from Braid groups' CRYPTO 2001, LNCS 2139, 486—502, 2001
• R. Gennaro, D. Micciancio, 'Cryptanalysis of a Pseudorandom Generator based on Braid groups' EUROCRYPT 2002, LNCS 2332, 1—13, 2002
• E. Lee 'Right-Invariance: A Property for Probabilistic Analysis of Cryptography based on infinite groups,' ASIACRYPT 2004, LNCS 3329, 103—118, 2004

##### ConjSearch: (multiple simlutaneous) Braid group conjugacy search problem

Definition: Let B be a braid group, $\bar{g}=(g_1,...,g_k)$ and $\bar{h}=(h_1,...,h_k)$ be two tuples of elements of B. Find $x \in B$ such that $\bar{h}=x^{-1}\bar{g}x$, given that such an x exists.

Reductions:

Algorithms:

Use in cryptography:

History:

References:

• A. Myasnikov, V. Shpilrain, A. Ushakov, 'Random Subgroups of Braid Groups: An approach to cryptanalysis of a Braid group based on cryptographic protocol', PKC 2006, LNCS 3958, 302—314, 2006

##### SubConjSearch: subgroup restricted Braid group conjugacy search problem

Definition: Let B be a braid group, and A a subgroup of B generated by some {a1,...,ar} and let $\bar{g}=(g_1,...,g_k)$ and $\bar{h}=(h_1,...,h_k)$ be two tuples of elements of B. Find $x \in A$, as a word in {a1,...,ar}, such that $\bar{h}=x^{-1}\bar{g}x$, given that such an x exists.

Reductions:

Algorithms: No known polynomial-time solution, some suggestion that it may be solved efficiently by a deterministic algorithm for some inputs (see references).

Use in cryptography: Anshel- Anshel- Goldfeld key exchange protocol (AAG)

History:

References:

• A. Myasnikov, V. Shpilrain, A. Ushakov, 'Random Subgroups of Braid Groups: An approach to cryptanalysis of a Braid group based on cryptographic protocol', PKC 2006, LNCS 3958, 302—314, 2006.
• J. Gonzalez-Meneses, 'Improving an algorithm to solve Multiple simultaneous conjugacy problems in Braid groups', Contemp. Math., Amer. Math. Soc. 372 (2005), 35—42.
• S.J. Lee, E. Lee 'Potential weaknesses of the Commutator Key Agreement Protocol based on Braid groups', EUROCRYPT 2002, LNCS 2332, 14—28, (2002)
• I. Anshel, M. Anshel, D. Goldfield, 'An algebraic method for public-key cryptography,' Math. Res. Lett. 6 (1999), 287—291.

##### LINPOLY : A linear algebra problem on polynomials

Definition: Let W be a linear space of dimension $\leq n$ consisting of quadratic forms in n variables $X_1, \ldots, X_n$. Given $V=\sum_{1\leq i\leq n} X_iW$, is it possible (and how) to uniquely determine W? For any subspace L' of the linear space L generated by $X_1, \ldots, X_n$. Let $(V:L')\gets {r \in K[X_1, \ldots, X_n]: r L' \subseteq V}$ where K is a finite field. Conjecture: For randomly chosen W, the probability ρ that (V:L) = W are very close to 1, when n > 2.

Algorithms:

Use in cryptography:

References:

• Dingfeng Ye and Kwok-Yan Lam and Zong-Duo Dai, Cryptanalysis of "2 R" Schemes, CRYPTO 1999, pp. 315-325.

##### HFE-DP: Hidden Field Equations Decomposition Problem

Definition: Let F be a finite field of order q and $S,T\in Aff^{-1}$ be two invertible, affine transformations over the vector space Fn. Denote E: = GF(qn) an extension field over F and $\phi : F^n \rightarrow E$ the bijection between this extension field and the corresponding vector space. We have $\phi^{-1}(\phi(a))=a \forall a \in F^n$.

Now let $P(X) := \sum_{i,j < D, q^i+q^j < D} C_i,jX^{q^i+q^j} + \sum_{q^i < D} B_iX^{q^i} + A$ for finite field elements $C_{i,j}, B_i, A \in E$ the inner polynomial. This gives the public key

$\mathcal{P}(x) := T \circ P \circ S(x)$

or more precisely

$\mathcal{P}(x) := T \circ \phi^{-1} \circ P \circ \phi \circ S(x)$.

The HFE Decomposition problem is to find the secret key (S,P,T) for given public key $\mathcal{P}$.

Reductions: HFE-DPP HFE-SP

Algorithms: Linearization or Gröbner basis.[2]

Note: For plain HFE, the problem has been solved by Kipnis and Shamir. See also the HFE-SP entry.

Use in cryptography:

It is the basis of the HFE crypto system.

References:

• Jaques Patarin: Hidden Field Equations (HFE) and Isomorphism of Polynomials (IP): Two new Families of Asymmetric Algorithms. Proceedins of EUROCRYPT 1996, pp. 33-48.
• A. Kipnis and A. Shamir: Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization, Proceedings of CRYPTO 1999.

##### HFE-SP: Hidden Field Equations Solving Problem

Definition: Let F be a finite field of order q and $S,T\in Aff^{-1}$ be two invertible, affine transformations over the vector space Fn. Denote E: = GF(qn) an extension field over F and $\phi : F^n \rightarrow E$ the bijection between this extension field and the corresponding vector space. We have $\phi^{-1}(\phi(a))=a \forall a \in F^n$.

Now let $P(X) := \sum_{i,j < D, q^i+q^j < D} C_i,jX^{q^i+q^j} + \sum_{q^i < D} B_iX^{q^i} + A$ for finite field elements $C_{i,j}, B_i, A \in E$ the inner polynomial. This gives the public key

$\mathcal{P}(x) := T \circ P \circ S(x)$

or more precisely

$\mathcal{P}(x) := T \circ \phi^{-1} \circ P \circ \phi \circ S(x)$.

The HFESP is, given $y \in F^n$, find $x\in F^n$ such that $y=\mathcal{P}(x)$ is satisfied.

Reductions: HSE-DPP HSE-SP

Algorithms: Linearization or Gröbner basis.[3]

Use in cryptography:

References:

• Jaques Patarin: Hidden Field Equations (HFE) and Isomorphism of Polynomials (IP): Two new Families of Asymmetric Algorithms. Proceedings of EUROCRYPT 1996, pp. 33-48.

##### MKS: Multiplicative Knap Sack

Definition: Given positive integers p,c,n and a set $\{v_i \}\in \{1,...,p-1\}^n$ find a binary vector x such that

$c = \prod_{i=1}^n v_i^{x_i} \mod p$.

Reductions:

Algorithms:

Use in cryptography: Naccache and Stern propose a trapdoor one-way permutation by letting p a large prime, n the largest integer such that

$p > \prod_{i=1}^n p_i$ where pi is the i'th prime.

The trapdoor s < p − 1 is a random integer coprime to p − 1, the set {vi} is computed by

$v_i = p_i^{1/s} \mod p$.

References:

• David Naccache and Jacques Stern: A New Public-Key Cryptosystem. Proceedings of EUROCRYPT 1997, pp. 27-36.

##### BP: Balance Problem

Definition: Given a group G and a set $\{v_i \}\in G^n$ find disjoint subsets I,J, not both empty, such that

$\bigodot_{i\in I} v_i = \bigodot_{j\in J} v_j$.

Reductions:

Algorithms:

Use in cryptography: Incremental hashing

References:

• Mihir Bellare and Daniele Micciancio: A New Paradigm for Collision-Free Hashing: Incrementality at Reduced Costs. Proceedings of EUROCRYPT 1997, pp. 163-192.

##### BDD: Bounded distance decoding

We consider adaptive strengthenings of standard general hardness assumptions, such as the existence of one-way functions and pseudorandom generators.

• A collection of adaptive 1-1 one-way functions is a family of 1-1 functions $F_n=\{f_s:\{0,1\}^n\mapsto\{0,1\}^n\}$ such that for every s, it is hard to invert fs(r) for a random r, even for an adversary that is granted access to an "inversion oracle" for fs' for every $s'\neq s$. In other words, the function fs is one-way, even with access to an oracle that invert all the other functions in the family.
• A sf collection of adaptive pseudo-random generators is a family of 1-1 functions $G_n=\{G_s:\{0,1\}^n\mapsto\{0,1\}^n\}$ such that for every s, Gs is pseudo-random, even for an adversary that is granted access to an oracle that decides whether given y is in the range of Gs' for $s'\neq s$.

References: Omkant Pandey, Rafael Pass, Vinod Vaikuntanathan, Adaptive One-Way Functions and Applications, CRYPTO 2008, Springer LNCS 5157, 57-74

##### SPI: Sparse Polynomial Interpolation

Definition: Given $A, a_0, \dots, a_k, C_1, \dots, C_k \in \mathbb{F}_q$ to find a polynomial $f(x) \in \mathbb{F}_q[x]$ of degree at most q − 1 such that f(0) = A,f(a0) = 0,f(ai) = Ci for $1 \le i \le k$ and f(x) − A has coefficients in {0,1}.

Reductions:

Algorithms:

Use in cryptography: Identification scheme.

References:

• W. D. Banks, D. Lieman, I. E. Shparlinski, An identification scheme based on sparse polynomials, PKC 2000, Springer LNCS 1751, 2000, 68-74.

##### SPP: Self-Power Problem

Definition: Given a prime p and $c \equiv x^x$ modulo p, find x.

Reductions:

Algorithms:

Use in cryptography: If you can do this, you can forge signatures for variations 2 and 4 of the ElGamal Signature Scheme (in the numbering specified in Section 11.5(i) of the Handbook of Applied Cryptography).

References:

• Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone. The Handbook of Applied Cryptography, CRC Press, 1996.
• Antal Balog, Kevin A. Broughan, Igor E. Shparlinski. On the Number of Solutions of Exponential Congruences. Acta Arithmetica, Vol. 148 (2011), pp. 93-103.
• Matthew Friedrichsen, Brian Larson, and Emily McDowell. Structure and Statistics of the Self-Power Map, Rose-Hulman Undergraduate Mathematics Journal, Vol. 11, Issue 2, 2010.

##### VDP: Vector Decomposition Problem

Definition: Given a two-dimensional vector space V over a finite field, with basis e1,e2, and a vector v in V, find a multiple u of e1 such that vu is a multiple of e2.

Reductions: CDHP VDP given the Yoshida conditions for V, CDHP VDP given a distortion eigenvector basis for V.

Algorithms:

Use in cryptography: Inseparable Multiplex Transmission scheme (e.g. watermarking), VDP signature scheme (an ElGamal type signature scheme for two-dimensional vector spaces), public key encryption using a trapdoor VDP

References:

• M. Yoshida. Inseparable multiplex transmission using the pairing on elliptic curves and its application to watermarking. In Fourth Conference on Algebraic Geometry, Number Theory, Coding Theory and Cryptography. Graduate School of Mathematical Sciences, University of Tokyo, 2003.
• Iwan Duursma and Negar Kiyavash. The vector decomposition problem for elliptic and hyperelliptic curves. J. Ramanujan Math. Soc., 20(1):59{76, 2005.
• Iwan M. Duursma and SeungKook Park, ElGamal type signature schemes for n-dimensional vector spaces, Cryptology ePrint Archive: Report 2006/312.
• Steven D. Galbraith and Eric R. Verheul, An Analysis of the Vector Decomposition Problem, In Public Key Cryptography – PKC 2008, Lecture Notes in Computer Science, 2008, Volume 4939/2008, 308-327.

##### 2-DL: 2-generalized Discrete Logarithm Problem

Definition: Given a group G of exponent r and order r2, with generators P1,P2, and an element Q in G, find a pair of integers (a,b) such that Q = aP1 + bP2.

Reductions: DLPP 2-DL, VDPP 2-DL, 2-DLP DLP given a distortion eigenvector basis for G.

Algorithms:

Use in cryptography:

References:

• Steven D. Galbraith and Eric R. Verheul, An Analysis of the Vector Decomposition Problem, In Public Key Cryptography – PKC 2008, Lecture Notes in Computer Science, 2008, Volume 4939/2008, 308-327.