# Miscellaneous

### From Wiki

##### KEA1: Knowledge of Exponent assumption

Definition: For any adversary *A* that takes input *q*,*g*,*g*^{a} and returns (*C*,*Y*)
with *Y* = *C*^{a}, there exists an “extractor” A, which given the same
inputs as *A* returns *c* such that *g*^{c} = *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

##### MQ: Multivariable Quadratic equations

Definition: Given a system of *m* quadratic polynomial equations in *n*
variables each,
find a solution 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 *x**H* = 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 to find such that *a*^{ − 1}*x**a* = *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 to find where such that *a*^{ − 1}*x**a* = *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 such that *y* = *b**x**b*^{ − 1} for some to find where *m* < *n* such that *a*'*x**a*'' = *y*.

Reductions: GenConjSP ≤_{P} 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 to determine whether or not *x* and *y* are conjugate, i.e., that there exists such that *a*^{ − 1}*x**a* = *y*.

Reductions: ConjDP ≤_{P} ConjSP

Algorithms:

Use in cryptography:

History:

References:

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

Definition: Given to determine whether or not for , and

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:

- 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, and be two tuples of elements of *B*. Find such that , 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 {*a*_{1},...,*a*_{r}} and let and be two tuples of elements of *B*. Find , as a word in {*a*_{1},...,*a*_{r}}, such that , 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 consisting of quadratic forms in *n* variables .
Given , is it possible (and how) to uniquely determine *W*?
For any subspace *L*' of the linear space *L* generated by . Let 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 be two invertible,
affine transformations over the vector space *F*^{n}. Denote *E*: = *G**F*(*q*^{n}) an extension field over *F* and
the bijection between this extension field and the corresponding vector space.
We have .

Now let for finite field elements the inner polynomial. This gives the public key

or more precisely

.

The HFE Decomposition problem is to find the secret key (*S*,*P*,*T*) for given public key .

Reductions: HFE-DP ≥_{P} 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 be two invertible,
affine transformations over the vector space *F*^{n}. Denote *E*: = *G**F*(*q*^{n}) an extension field over *F* and
the bijection between this extension field and the corresponding vector space.
We have .

Now let for finite field elements the inner polynomial. This gives the public key

or more precisely

.

The HFESP is, given , find such that is satisfied.

Reductions: HSE-DP ≥_{P} HSE-SP

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

Use in cryptography:

Note: See also the HFE-DP entry.

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 find a binary vector *x*
such that

.

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

where *p*_{i} is the *i*'th prime.

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

.

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 find disjoint subsets *I*,*J*,
not both empty, such that

.

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

##### AHA: Adaptive Hardness Assumptions

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 such that for every
*s*, it is hard to invert*f*_{s}(*r*) for a random*r*, even for an adversary that is granted access to an "inversion oracle" for*f*_{s'}for every . In other words, the function*f*_{s}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 such that for every
*s*,*G*_{s}is pseudo-random, even for an adversary that is granted access to an oracle that decides whether given*y*is in the range of*G*_{s'}for .

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 to find a polynomial
of degree at most *q* − 1
such that *f*(0) = *A*,*f*(*a*_{0}) = 0,*f*(*a*_{i}) = *C*_{i} for
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 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 *e*_{1},*e*_{2}, and a vector *v* in *V*, find a multiple *u* of *e*_{1} such that *v* − *u* is a multiple of *e*_{2}.

Reductions: CDH ≤_{P} VDP
given the Yoshida conditions for *V*,
CDH ≡_{P} 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 *r*^{2}, with generators *P*_{1},*P*_{2}, and an element *Q* in *G*, find a pair of integers (*a*,*b*) such that *Q* = *a**P*_{1} + *b**P*_{2}.

Reductions: DLP ≤_{P} 2-DL, VDP ≤_{P} 2-DL, 2-DL ≡_{P} 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.