# Cryptanalysis of a Cayley Hash Function Based on
Affine Maps in one Variable over a Finite Field

Bianca Sosnovski  Department of Mathematics and Computer Science
Queensborough Community College, CUNY<EMAIL_ADDRESS>
###### Abstract.

Cayley hash functions are cryptographic hashes constructed from Cayley graphs
of groups. The hash function proposed by Shpilrain and Sosnovski (2016), based
on affine maps in one variable over a finite field, was proven insecure. This
paper shows that the variation proposed by Ghaffari and Mostaghim (2018) that
uses Shpilrain and Sosnovski’s hash is also insecure. We demonstrate its
security vulnerability by constructing collisions.

Keywords: Cryptography, hash functions, Cayley hash functions.

The author received support for this project provided by a PSC-CUNY grant,
jointly funded by the Professional Staff Congress and the City University of
New York.

##  1\. Introduction

Hash functions are an essential tool for cryptography. Today’s security of
much of our communication relies on cryptographic protocols that ensure
confidentiality, integrity and authentication, and many such protocols use
hash functions as building blocks. Hash functions are fundamental in
constructing cryptographic protocols, such as database indexing, data
compression, password storage, digital signatures, encryption schemes, and key
derivation systems.

However, not every hash function is good enough for cryptography.
Cryptographic hash functions are hash functions that satisfy desired security
properties such as preimage and collision resistance and may be used in
cryptographic applications.

Furthermore, many cryptosystems in use today are based on finite abelian
groups. Some cryptographic systems will be vulnerable to attacks once large
quantum computers are made possible. Though the current state of quantum
computing is still in its infancy, it is a step forward in the direction where
classical cryptography may be compromised. In [1], hash-based public-key
signatures are one of the classes of cryptographic systems that may resist
quantum attacks and require a standard cryptographic hash function.

Provably secure hash functions are hashes whose security is implied by the
assumption of the hardness of a mathematical problem. Examples of provable-
secure hash functions are the Cayley hash functions. Cayley hash functions are
families of hash functions constructed from Cayley graphs of the groups [13].
The security of Cayley hash functions would follow from the alleged hardness
of a mathematical problem related to the Cayley graph regarding a generating
set of the underlying group [4, 13]. Since Cayley hashes involve non-abelian
groups, it is a priori resistant to quantum attacks, and they may be good
candidates for post-quantum cryptography [8].

In 1991, Zémor introduced the first Cayley hash function that has as
generators the matrices

$\left(\begin{array}[]{cc}1&1\\\ 0&1\end{array}\right)\mbox{ and
}\left(\begin{array}[]{cc}1&0\\\ 1&1\end{array}\right)$

and its hash values are elements in $SL_{2}(\mathbb{F}_{p})$ for $p$ prime.

It was broken by Tillich and Zémor in 1994, who then proposed the hash
function whose generators

$\left(\begin{array}[]{cc}\alpha&1\\\ 1&0\end{array}\right)\mbox{ and
}\left(\begin{array}[]{cc}\alpha&\alpha+1\\\ 1&1\end{array}\right)$

with $\alpha$ as the root of an irreducible polynomial $p(x)$ of degree $n$ in
the ring of polynomials $\mathbf{F}_{2}[x]$, where $\mathbf{F}_{2}$ is the
field with two elements.The above matrices are generators of the Cayley graph
for the group $SL_{2}(\mathbb{F}_{2^{n}})$ with
$\mathbb{F}_{2^{n}}\approx\mathbf{F}_{2}[x]/(p(x))$ where $(p(x))$ is the
ideal generated by an irreducible polynomial $p(x)$.

The Tillich-Zémor hash function was broken in 2009 when Grassl et al. [7]
established a connection between the Tillich-Zémor function and maximal length
chains in the Euclidean algorithm for polynomials over the field with two
elements. Other instances of Cayley hashes based on expander graphs have been
proposed after Tillich-Zémor functions. Detailed discussions of Cayley hash
functions can be found in [11, 12, 13, 4]. These Cayley hashes also have been
proven insecure.

Though many instances of Cayley hash functions have been proved insecure, the
algorithms used to break Cayley hash functions target specific vulnerabilities
of each underlying group used and do not invalidate the generic scheme of
these functions. The factorization, representation and balance problems in
non-abelian groups still are potentially hard problems for general parameters
of Cayley hash functions. There are still Cayley hash functions that remain
unbroken (e.g., [2, 5, 19]).

It may seem a concerning scenario where many hashes have been proven insecure.
But this is also essential and encouraging in cryptography since it
demonstrates that the community invests a lot of time and energy in
cryptanalysis to ensure algorithms are evaluated and that new ones are
developed to sustain quantum attacks. The more researchers and scientists have
looked at these algorithms and they remain unbroken, the higher our level of
confidence in them.

This paper proves that the hash function proposed by Gaffari and Mustaghim [6]
is not collision-resistant, which uses the hash proposed by Shpilrain and
Sosnovski [16] that has been proven insecure by Monico [10]. To show that
Gaffari and Mustaghim’s is also insecure, we apply Monico’s algorithm to find
second-preimages for the Shpilrain-Sosnovski hash function to produce
collisions for the Gaffari and Mustaghim’s hash function.

The remainder of the paper is organized as follows. In Section 2, we recall
some basic definitions and properties of a cryptographic hash function.
Section 3 briefly describes the Shpilrain-Sosnovski hash and Gaffari-Mustaghim
hash. Section 4 presents a summary of the cryptanalysis of the Shpilrain and
Sosnovski’s hash function. In Section 5, we present our main results about the
security of the Gaffari and Mustaghim’s hash:

######  Theorem.

Ghaffari-Mostaghim hash is not collision-resistant.

##  2\. Preliminaries

Hash functions are used as compact representations, or digital fingerprints,
of data to provide message integrity.

######  Definition 1.

A hash function $h:\\{0,1\\}^{*}\longrightarrow\\{0,1\\}^{n}$ is an easy-to-
compute111Easy to compute or computationally feasible means polynomial time
and space or, in practice, with a certain number of machine operations to time
units [9]. function that converts a variable-length input into a fixed-length
output. A cryptographic hash function $h$ must satisfy at least one of the
following properties.

  * •

_Preimage resistance_ : Given a hash value $y$ for which a corresponding input
is not known, it is computationally infeasible (or hard) to find any input $x$
such that $y=h(x)$.

  * •

_Second-preimage resistance_ : Given an input $x_{1}$ it is computationally
infeasible to find another input $x_{2}$ where $x_{1}\neq x_{2}$ such that
$h(x_{1})=h(x_{2})$.

  * •

_Collision resistance_ : It is computationally infeasible to find any two
inputs $x_{1}$ and $x_{2}$ where $x_{1}\neq x_{2}$ such that
$h(x_{1})=h(x_{2})$.

A collision-resistance hash function is also second-preimage resistant.
Preimage resistance does not guarantee second-preimage resistance, and Second-
preimage resistance does not ensure preimage resistance [9].

It is well known that expander graphs are used to produce pseudorandom
behavior. This pseudorandom behavior is due to the rapid mixing of Markov
chains on expander graphs. The initial idea was to use groups whose Cayley
graphs concerning a set of generators are expander graphs to design collision-
resistant hash functions.

######  Definition 2.

Let $G$ be a finite group with a set of generators $\mathcal{S}$ that has the
same size as the text alphabet222In general, we can consider plaintexts as
strings of symbols from a text alphabet $\\{1,2,\ldots,k\\}$ for $k\geq 2$.
Conventionally, we use the text alphabet as $\\{0,1\\}$ for binary strings.
$\mathcal{A}$. Choose a function: $\pi:\mathcal{A}\to\mathcal{S}$ such that
$\pi$ defines a one-to-one correspondence between $\mathcal{A}$ and
$\mathcal{S}$. A _Cayley hash_ $h$ is a function whose hash value of the text
$x_{1}x_{2}\dots x_{k}$ is the group element $h(x_{1}x_{2}\dots
x_{k})=\pi(x_{1})\pi(x_{2})\dots\pi(x_{k})$.

For example, a Cayley hash has $A$ and $B$ as the generators of the underlying
group $G$ with the bit assignments $0\mapsto A$ and $1\mapsto B$. The bit
string 101011 is hashed to the group product $BABAB^{2}$.

In constructing hash functions from expander Cayley graphs, the input to the
hash function gives directions for walking around the graph (without
backtracking), and the hash output is the end vertex of the walk.

For the Cayley hashes described in this paper, the alphabet used corresponds
to $\\{0,1\\}$. One of the advantages of this design is that the computation
of the hash value can be easily parallelized due to the concatenation property
$\pi(xy)=\pi(x)\pi(y)$ for any texts $x$ and $y$ in $\\{0,1\\}^{*}$. Unlike
the SHA family of hash functions that hash blocks of input, this type of
function hashes each bit individually.

The security properties of Cayley hash functions are strongly related to the
hardness of mathematical problems.

Let $G$ be a group and $\mathcal{S}=\\{s_{1},\ldots s_{k}\\}\subset G$ be a
generating set of $G$. Let $L$ be polylogarithmic (small) in the size of $G$.

  * •

_Balance problem:_ Find an efficient algorithm that returns two words
$m_{1}\ldots m_{l}$ and $m^{\prime}_{1}\ldots m^{\prime}_{l^{\prime}}$ with
$l,l^{\prime}<L$, $m_{i},m^{\prime}_{i}\in\\{1,\ldots,k\\}$ that yield equal
products in $G$, that is,
$\prod\limits_{i=1}^{l}s_{m_{i}}=\prod\limits_{i=1}^{l^{\prime}}s_{m^{\prime}_{i}}$

  * •

_Representation problem:_ Find an efficient algorithm that returns a word
$m_{1}\ldots m_{l}$ with $l<L$, $m_{i}\in\\{1,\ldots,k\\}$ such that
$\prod\limits_{i=1}^{l}s_{m_{i}}=1$.

  * •

_Factorization problem:_ Find an efficient algorithm that given any element
$g\in G$ returns a word $m_{1}\ldots m_{l}$ with $l<L$,
$m_{i}\in\\{1,\ldots,k\\}$ such that $\prod\limits_{i=1}^{l}s_{m_{i}}=g$.

A Cayley hash function is collision-resistant if the balance problem is hard
in the underlying group. Suppose the representation problem is hard in the
group. In that case, the associated Cayley hash is second preimage resistant,
and it is preimage resistant if and only if the corresponding factorization
problem is hard in the group [11, 15].

Other requirements considered by Tillich and Zémor [20, 18] in the
construction of Cayley hash functions are that the Cayley graph of G with
generator set S has a large girth and small diameter.

##  3\. Cayley hash functions

###  3.1. The Shpilrain-Sosnovski hash function

In [16], the authors presented a Cayley hash function that uses linear
functions in one variable over $\mathbb{F}_{p}$ with composition operation.

The semigroup generated by $f(x)=ax+b$ and $g(x)=cx+d$ under composition is
isomorphic to the semigroup generated by

$A=\left(\begin{array}[]{cc}a&b\\\ 0&1\end{array}\right)\mbox{ and
}B=\left(\begin{array}[]{cc}c&d\\\ 0&1\end{array}\right)$

under matrix multiplication. Using results about the freeness of upper
triangular matrices by Cassaigne at al. [3], they showed that the semigroup of
linear functions over $\mathbb{Z}$ is free if the generators of the semigroup
do not commute and $a,c\geq 2$.

The functions $f_{0}(x)=2x+1\mod p$ and $f_{1}(x)=3x+1\mod p$ with $p>3$ are
considered the generators of the proposed hash function. The hash value is
obtained by first computing product $h(b_{1}b_{2}\cdots
b_{k})=f_{b_{1}}f_{b_{2}}\cdots f_{b_{k}}\pmod{p}$ where $b_{i}\in\\{0,1\\}$
for $1\leq i\leq k$. The corresponding product linear function is of the form
$\ell(x)=rx+s$ where $s,r\in\mathbb{Z}_{p}$, and the hash value is defined as
$H(b_{1}b_{2}\cdots b_{k})=(r+s,s)$.

The corresponding hash functions are very efficient. A bit string of length
$n$ can be hashed by performing at most $2n$ multiplications and about $2n$
additions in $\mathbb{F}_{p}$.

An advantage of this hash function is that the output bit strings have length
$2\log p$, while the Tillich-Zémor hash function outputs bit strings of length
$4\log p$. Concerning the security of the hash function, the authors recommend
that $p\approx 2^{512}$ or larger to prevent generic attacks. With this
recommended parameter $p$, there will be no collisions unless the length of at
least one of the colliding strings is at least 323. For a short input text
(323 bits or less), the authors recommend padding to extend its length to 512
bits. Subgroup attacks and attacks using elements of small orders can be
prevented by choosing $p$ such that $p=2q+1$ where $q$ is a “large” prime.

###  3.2. The Ghaffari-Mostaghim hash function

As discussed in [16], preimages can be easily computed for short messages in
the Shpilrain-Sosnovski hash, and the option suggested to avoid it is using
padding.

Ghaffari and Mostaghim use a similar idea introduced in [11] to modify the
linear hash function above. The functions $f_{0}(x)=2x+1\mod p$ and
$f_{1}(x)=3x+1\mod p$, where $p>3$ is a prime, are also considered as
generators in this Cayley hash. Let $H(m_{1}m_{2}\cdots
m_{l})=f_{m_{1}}f_{m_{2}}\cdots f_{m_{l}}\pmod{p}$ for $m=m_{1}m_{2}\cdots
m_{l}\in\\{0,1\\}^{*}$. Define the new function
$H_{2}(m)=H(m\parallel(H(m)\oplus c_{rnd}))$, where $c_{rnd}$ is a constant
bit string whose bits look random. $H_{2}$ is meant to be a more secure
version of $H$, especially for short messages, and also avoids the issue of
malleability.

To make the factorization problem harder, Ghaffari and Mostaghim [6] suggested
the following variation. Let $G$ the group generated by $f_{0}$ and $f_{1}$
over $\mathbb{Z}_{p}$, $t>1$ an integer and $g\in
G\setminus\\{e,f_{0},f_{1}\\}$, where $e$ is the identity element of $G$.

Define $\widehat{H}:\\{0,1\\}^{*}\to G$ by
$\widehat{H}(m)=\prod_{i=1}^{l}C_{i}$ where

$C_{i}=\begin{cases}f_{m_{i}}&\mbox{if }t\nmid i\\\ f_{m_{i}}g&\mbox{if }t\mid
i\end{cases}.$

Now define $\widehat{H}_{2}(m)=\widehat{H}(m\parallel(\widehat{H}(m)\oplus
c_{rnd}))$.

For an input bit string of length $l$, the computation of $\widehat{H}$
requires $\lfloor l/t\rfloor$ multiplications more than the original Cayley
hash function proposed by Shpilrain and Sosnovski, thus not affecting too much
the performance of the hash.

Ghaffari and Mostaghim showed that $\widehat{H}$ is at least as secure as the
Shpilrain-Sosnovski hash function $H$, and consequently, so is
$\widehat{H}_{2}$.

##  4\. Monico’s Algorithm

Monico [10] developed an attack that shows that the hash function is not
second-preimage resistant for inputs larger than about 1.9 MB for parameter
$p\approx 2^{256}$. In Monico’s method, the original bit string is not even
required, and having only a bound on its length suffices (preimage weakness).

In Monico’s attack, a hash value $(x,y)$ in $\mathbb{F}_{p}^{2}$ of a bit
string of known length $L$ is given and inverted to $(r,s)=(x-y,y)$. Since
$r=2^{a}3^{b}$ where $a$ is the number of zeros in the original bit string,
and $b$ is the number of ones (or vice-versa), then $L=a+b$. The values of $a$
and $b$ can be recovered with $O(L\log L)$ operations over $\mathbb{F}_{p}$ by
precomputing $L$ powers of $2$, sorting them out and then computing and
testing $r,3^{-1}r,3^{-2}r,\ldots$ until one of the values in the sequence
matches one of the precomputed powers of 2.

Let $n=min\\{a,b\\}$,

$Y=\left(\begin{array}[]{cc}r&s\\\ 0&1\end{array}\right)\mbox{ and
}U=\left(\begin{array}[]{cc}r&u\\\ 0&1\end{array}\right),$

where $U$ is a suitable matrix whose factorization in generators

$A=\left(\begin{array}[]{cc}2&1\\\ 0&1\end{array}\right)\mbox{ and
}B=\left(\begin{array}[]{cc}3&1\\\ 0&1\end{array}\right)$

is known and determined by the values of $a$ and $b$ found in the first step.

The attack aims to transform $U$ into $Y$ by replacing several of the leading
$AB$ factors of $U$ with $BA$. To do so, one must find
$\mathbf{x}\in\\{0,1\\}^{n}$ such that
$\displaystyle\sum_{j=0}^{n-1}x_{j}6^{j}\equiv t\pmod{p}$ where
$t=s-u\pmod{p}$ (for more details, see [10])

To provide a probabilistic algorithm to find such $\mathbf{x}$, Monico reduced
the problem to a dense instance of the Random Modular Subset Sum Problem
(RMSSP), which was considered by Lyubashevsky (2005). Heuristically, his
algorithm is expected to succeed as long as the original bit string had at
least $n$ zeros and $n$ ones for some $n\geq 2^{\sqrt{2\log_{2}p}}$. According
to Monico, the algorithm’s expected running time is $O(n^{2}\log n)$ with an
implied constant small enough to keep the attack practical for $p\approx
2^{256}$.

##  5\. Cryptanalysis of the Ghaffari-Mostaghim hash

This section uses Monico’s algorithm to produce collisions for the Ghaffari-
Mostaghim hash function

######  Lemma 1.

A collision for $\widehat{H}$ is also a collision for $\widehat{H}_{2}$.

###### Proof.

Suppose that $m$ and $m^{\prime}$ are two bit strings such that
$\widehat{H}(m)=\widehat{H}(m^{\prime})$.

$\begin{array}[]{ccc}\widehat{H}_{2}(m)&=&\widehat{H}\left(m\parallel(\widehat{H}(m)\oplus
c_{rnd})\right)\\\ &=&\widehat{H}(m)\widehat{H}(\widehat{H}(m)\oplus
c_{rnd})\\\
&=&\widehat{H}(m^{\prime})\widehat{H}(\widehat{H}(m^{\prime})\oplus
c_{rnd})\\\
&=&\widehat{H}\left(m^{\prime}\parallel(\widehat{H}(m^{\prime})\oplus
c_{rnd})\right)\\\ &=&\widehat{H}_{2}(m^{\prime})\end{array}$

∎

######  Lemma 2.

A collision for $H$ is also a collision for $H_{2}$.

###### Proof.

Similar to the proof in Lemma 1.

∎

######  Theorem 3.

Ghaffari-Mostaghim hash is not collision-resistant.

###### Proof.

Monico’s algorithm can find collisions for $\widehat{H}_{2}$.

Let $t>1$ and $g\in G$ as described in the construction of $\widehat{H}_{2}$.
We can use the algorithm to find a preimage for $g^{-1}$ under the hash $H$,
say $b^{\prime}$ such that $H(b^{\prime})=g^{-1}$.

Suppose that for a given bit string $m=m_{1}m_{2}\cdots m_{l_{1}}$, Monico’s
algorithm returns a bit string $m^{\prime}=m_{1}^{\prime}m_{2}^{\prime}\cdots
m_{l_{2}}^{\prime}$ such that $H(m)=H(m^{\prime})$ with $m\neq m^{\prime}$. We
insert $b^{\prime}$ into the bit strings $m$ and $m^{\prime}$ in the bit
positions multiple of $t+1$, obtaining the following

$m_{*}=m_{1}m_{2}\cdots m_{t}b^{\prime}\cdots m_{l_{1}}$
$m_{*}^{\prime}=m_{1}^{\prime}m_{2}^{\prime}\cdots
m_{t}^{\prime}b^{\prime}\cdots m_{l_{2}}^{\prime}$

We have that $m_{*}\neq m_{*}^{\prime}$ and they are collisions for
$\widehat{H}$ since

$\begin{array}[]{lll}\widehat{H}(m_{*})&=&\widehat{H}(m_{1}m_{2}\cdots
m_{t}b^{\prime}\cdots m_{l_{1}})\\\ &=&H(m_{1})H(m_{2})\cdots
H(m_{t})H(b^{\prime})\cdots H(m_{l_{1}})\\\ &=&f_{m_{1}}f_{m_{2}}\cdots
f_{m_{t}}gH(b^{\prime})\cdots f_{m_{l_{2}}}\\\ &=&f_{m_{1}}f_{m_{2}}\cdots
f_{m_{t}}gg^{-1}\cdots f_{m_{l_{1}}}\\\ &=&H(m)\end{array}$

$\begin{array}[]{lll}\widehat{H}(m_{*}^{\prime})&=&\widehat{H}(m_{1}^{\prime}m_{2}^{\prime}\cdots
m_{t}^{\prime}b^{\prime}\cdots m_{l_{2}}^{\prime})\\\
&=&H(m_{1}^{\prime})H(m_{2}^{\prime})\cdots
H(m_{t}^{\prime})H(b^{\prime})\cdots H(m_{l_{2}}^{\prime})\\\
&=&f_{m_{1}^{\prime}}f_{m_{2}^{\prime}}\cdots
f_{m_{t}^{\prime}}gH(b^{\prime})\cdots f_{m_{l_{2}}^{\prime}}\\\
&=&{}_{m_{1}^{\prime}}f_{m_{2}^{\prime}}\cdots f_{m_{t}^{\prime}}gg^{-1}\cdots
f_{m_{l_{2}}^{\prime}}\\\ &=&H(m^{\prime})\end{array}$

This shows that Monico’s algorithm produces collisions for $\widehat{H}$.
Therefore, $\widehat{H}_{2}$ is not collision-resistant by Lemma 1.

∎

##  6\. Conclusion

This paper proves that the variant proposed by Ghaffari and Mostaghim is
insecure. Our approach is to consider the mathematical structure of the design
of the hash and apply the algorithm that finds second preimages and collisions
for the Shpilrain and Sosnovski’s hash function.

The algorithms used to break Cayley hash functions target specific
vulnerabilities of each underlying group used and do not invalidate the
generic scheme of these functions. Petit and Quisquater [14, 15] suggested
that security might be recovered for the Cayley hash functions design by
introducing new generators.

Although many Cayley hash functions have been proven insecure, and their use
significantly compromises the security of computer systems, we learn from
prior vulnerabilities to develop more robust hash functions. It is essential
to research improvements and develop new designs for Cayley hash functions
that can sustain quantum attacks.

## References

  * [1] Bernstein, D.J.: Introduction to post-quantum cryptography. In: Bernstein, D.J., Buchmann, J., Dahmen, E. (eds) Post-Quantum Cryptography. Springer, Berlin, Heidelberg (2009), https://doi.org/10.1007/978-3-540-88702-7˙1
  * [2] Bromberg, L., Shpilrain, V., Vdovina, A.: Navigating in the Cayley graph of $SL_{2}(\mathbf{F}_{p})$ and applications to hashing. Semigroup Forum 94, pp. 314–324 (2017), https://doi.org/10.1007/s00233-015-9766-5
  * [3] Cassaigne, J., Harju, T., Karhumäki, J.: On the undecidability of freeness of matrix semigroups. International Journal of Algebra and Computation 09(03n04), pp. 295–305 (Jun 1999), http://dx.doi.org/10.1142/S0218196799000199
  * [4] Charles, D.X., Lauter, K.E., Goren, E.Z.: Cryptographic hash functions from expander graphs. Journal of Cryptology 22(1), pp. 93–113 (Jan 2009), https://doi.org/10.1007/s00145-007-9002-x
  * [5] Le Coz, C., Battarbee, C., Flores, R., Koberda, T., Kahrobaei, D.: Post-quantum hash functions using $\mathrm{SL}_{n}(\mathbb{F}_{p})$. (Jul 2022), https://doi.org/10.1142/S0218196799000199
  * [6] Ghaffari, M.H., Mostaghim, Z.: More secure version of a Cayley hash function. Groups Complexity Cryptology 10(1) (Apr 2018), http://dx.doi.org/10.1515/gcc-2018-0002
  * [7] Grassl, M., Ilić, I., Magliveras, S., Steinwandt, R.: Cryptanalysis of the Tillich-Zémor hash function. Journal of Cryptology 24(1), pp. 148–156 (Jan 2011), https://doi.org/10.1007/s00145-010-9063-0
  * [8] Jo, H., Yamasaki, Y.: LPS-type Ramanujan graphs. 2018 International Symposium on Information Theory and Its Applications (ISITA), pp. 399–403 (2018), https://doi.org/10.23919/ISITA.2018.8664284
  * [9] Menezes, A. J., van Oorscho, P. C., Vanstone, S. A.: Handbook of applied cryptography. CRC press (2001)
  * [10] Monico, C.: Cryptanalysis of a hash function and the modular subset sum problem. http://www.math.ttu.edu/~cmonico/research/linearhash.pdf (2019)
  * [11] Petit, C.: On graph-based cryptographic hash functions. Ph.D. thesis, Universit Catholique de Louvain (2009)
  * [12] Petit, C., Lauter, K., Quisquater, J.J.: Full cryptanalysis of LPS and Morgenstern hash functions. In: International Conference on Security and Cryptography for Networks. pp. 263–277. Springer (2008)
  * [13] Petit, C., Lauter, K.E., Quisquater, J.J.: Cayley hashes: A class of efficient graph-based hash functions. https://christophe.petit.web.ulb.be/files/Cayley.pdf (preprint 2007)
  * [14] Petit, C., Quisquater, J.J.: Preimages for the Tillich-Zémor hash function. In: Biryukov, A., Gong, G., Stinson, D.R. (eds.) Selected Areas in Cryptography. pp. 282–301. Springer Berlin Heidelberg, Berlin, Heidelberg (2011)
  * [15] Petit, C., Quisquater, J.J.: Rubik’s for cryptographers. Notices of the American Mathematical Society 60(6), pp. 733–739 (2013)
  * [16] Shpilrain, V., Sosnovski, B.: Compositions of linear functions and applications to hashing. Groups Complexity Cryptology 8(2) (Jan 2016), http://dx.doi.org/10.1515/gcc-2016-0016
  * [17] Tillich, J.P., Zémor, G.: Group-theoretic hash functions. In: Algebraic Coding: First French–Israeli Workshop. pp. 90–110. Springer (1994), https://doi.org/10.1007/3-540-57843-9
  * [18] Tillich, J.P., Zémor, G.: Hashing with ${SL}_{2}$. In: Desmedt, Y.G. (ed.) Advances in Cryptology — CRYPTO ’94. pp. 40–49. Springer Berlin Heidelberg, Berlin, Heidelberg (1994)
  * [19] Yuan, S.: (2016). Cryptographic hash functions from sequences of lifted Paley graphs. In: Kahrobaei, D., Cavallo, B. & Garber, G. (eds.), Algebra and Computer Science. AMS (2016), http://dx.doi.org/10.1090/conm/677/13629
  * [20] Zémor, G.: Hash functions and graphs with large girths. In: Davies, D.W. (ed.) Advances in Cryptology — EUROCRYPT ’91. pp. 508–511. Springer Berlin Heidelberg, Berlin, Heidelberg (1991)


# Matched Illumination Waveforms using Multi-Tone Sinusoidal Frequency
Modulation

###### Abstract

This paper explores the design of constant modulus Matched-Illumination (MI)
waveforms using the Multi-Tone Sinusoidal Frequency Modulation (MTSFM)
waveform model. MI waveforms are optimized for detecting targets in known
noise and clutter Power Spectral Densities (PSDs). There exist well-defined
information theoretic methods that describe the design of MI waveforms for a
myriad of target/noise/clutter models. However, these methods generally only
produce the magnitude square of the MI waveform’s spectrum. Additionally, the
waveform’s time-series is not guaranteed to be constant modulus. The MTSFM is
a constant modulus waveform model with a discrete set of design coefficients.
The coefficients are adjusted to synthesize constant modulus waveforms that
approximate the ideal MI waveform’s spectrum. Simulations demonstrate that the
MTSFM’s detection performance closely approximates an ideal MI waveform
spectrum and generally outperforms flat spectrum waveforms across a range of
transmit energies when the noise and clutter PSDs vary greatly across the
operational band.

Index Terms—  Matched-Illumination Waveform, Adaptive Waveform Design, Multi-
Tone Sinusoidal Frequency Modulation.

##  1 Introduction

A fundamental problem in radar system design is the choice of transmit
waveform and receiver processing for detecting targets of interest. There
exist well-defined information theoretic methods in the published literature
that describe how to design waveforms and receivers for optimal target
detection in given noise/clutter Power Spectral Densties (PSDs) [1, 2, 3, 4,
5, 6]. Using a transmit energy constraint, these methods detail the structure
of the magnitude square of the waveform’s spectrum, also known as the Energy
Spectral Density (ESD). Such waveform design methods have demonstrated clear
improvement in detection performance compared to waveforms with a flat ESD
such as the Linear Frequency Modulated (LFM) waveform [4, 5]. The improved
detection performance of these Matched Illumination (MI) waveforms over flat
spectrum waveforms is especially noticeable in scenarios where there is
limited available transmit energy and the noise/clutter PSDs vary widely in
magnitude across the operational band of frequencies [5].

While these MI waveform design techniques specify the optimal waveform’s ESD
shape, they do not directly specify how to synthesize the waveform time-series
that realizes that ESD shape. Since the optimization is over a finite band,
the resulting waveform time-series cannot be perfectly time-limited.
Additionally, it is generally desirable for waveforms to possess a constant
modulus to facilitate transmission on practical transmitter electronics, a
property that information theoretic MI waveform synthesis methods do not
guarantee. There have been a number of efforts to develop phase-retrieval
algorithms that synthesize a constant modulus waveform whose ESD closely
approximates the ideal MI waveform’s ESD [7, 8, 9].

Recently, the Multi-Tone Sinusoidal Frequency Modulated (MTSFM) waveform was
developed for use as an adaptive FM waveform model for cognitive radar and
sonar systems [10]. The MTSFM is a constant modulus waveform model with a
discrete set of parameters that can be adjusted to synthesize novel waveforms
with desirable characteristics. Previous work in [10, 11] demonstrated that
the MTSFM’s design coefficients can be finely tuned to produce waveforms with
specific Ambiguity Function (AF) and Auto-Correlation Function (ACF)
properties, a common focus area for adaptive waveform design [12, 13, 14, 15].
This paper explores applying the MTSFM waveform model to the MI waveform
design problem using the foundational methods developed by Kay in [4] for
point-like targets. Simulations demonstrate that the MTSFM’s detection
performance approaches that of the ideal MI waveform and generally outperforms
flat spectrum waveforms across a range of transmit energies when the
magnitudes of the noise and clutter PSDs vary substantially across the
operational band of frequencies.

##  2 Waveform Signal Model and the Optimal Detection Waveform Problem

This section describes the MI waveform design technique for point targets in
noise and clutter whose respective PSDs are known [4]. This section
additionally describes the MTSFM waveform model and how it can be adapted to
produce constant amplitude waveforms that approximate the ideal MI waveform’s
ESD. This paper assumes the waveform $s\left(t\right)$ with Fourier transform
$S\left(f\right)$ is basebanded and occupies a bandwidth $W$. The waveform is
defined over the time interval $-T/2\leq t\leq T/2$ with duration $T$ and
energy $E$ expressed as

$s\left(t\right)=\sqrt{\dfrac{E}{T}}\operatorname{rect}\left(t/T\right)e^{j\varphi\left(t\right)}$
(1)

where $\varphi\left(t\right)$ is the waveform’s instantaneous phase. The
waveform’s frequency modulation function $m\left(t\right)$ is expressed as

$m\left(t\right)=\dfrac{1}{2\pi}\dfrac{d\varphi\left(t\right)}{dt}.$ (2)

###  2.1 Designing Matched Illumination Waveforms

This paper uses the MI waveform model developed by Kay in [4] and is described
by the block diagram shown in Figure 1. The waveform $s\left(t\right)$ is
transmitted into the medium. The return signal is a combination of the return
from the target, clutter, and additive noise. The target is modeled as a point
reflector with impulse response $g\left(t\right)=A\delta\left(t\right)$ where
$\delta\left(t\right)$ is an impulse function and $A$ is a complex reflecting
parameter modeled as a complex normal distribution
$A\sim\mathcal{CN}\left(0,\sigma_{A}^{2}\right)$. This target model can be
readily generalized to include extended targets as was demonstrated in [2].
The noise $n\left(t\right)$ is modeled as a complex Gaussian random process
with PSD $P_{n}\left(f\right)$. The channel impulse response $h\left(t\right)$
is convolved with the transmit waveform producing the clutter signal
$c\left(t\right)=h\left(t\right)*s\left(t\right)$. Assuming the PSD of the
channel is a Gaussian random process with zero mean and PSD
$P_{h}\left(f\right)$, the PSD of the clutter can correspondingly be expressed
as $P_{c}\left(f\right)=|S\left(f\right)|^{2}P_{h}\left(f\right)$. As shown in
Figure 1, these terms combine to produce the return signal $x\left(t\right)$
expressed as

$x\left(t\right)=As\left(t\right)+h\left(t\right)*s\left(t\right)+n\left(t\right).$
(3)

Note that this model assumes the target and clutter are stationary and thus
this signal model does not contain Doppler shifted echo signals or clutter.
This was primarily utilized in [4] for simplicity in deriving the optimal
waveform/receiver configuration. However, this model also represents a worst
case scenario. Many radar/sonar systems exploit target Doppler in order to
separate the target’s echo signal from clutter. For stationary targets and
clutter this is not possible, and thus target detection performance is purely
dependant upon receiver design and shaping of the waveform’s ESD.

Kay [4] then used this model to derive the optimal Neyman-Pearson detector,
expressed in the frequency domain as

$\left|\sum_{-M/2}^{M/2}\dfrac{X\left(f_{m}\right)S^{*}\left(f_{m}\right)}{P_{h}\left(f_{m}\right)|S\left(f_{m}\right)|^{2}+P_{n}\left(f_{m}\right)}\right|^{2}>\gamma$
(4)

where $f_{m}=m/T$, $M=\lceil WT\rceil$, and $\gamma$ is the detection
threshold. The optimal receiver’s detection performance is determined by the
metric

$d^{2}=\sigma_{A}^{2}\int_{-W/2}^{W/2}\dfrac{|S\left(f\right)|^{2}}{P_{h}\left(f\right)|S\left(f\right)|^{2}+P_{n}\left(f\right)}df.$
(5)

The waveform is also constrained to possess finite energy across the
operational band of frequencies $W$

$E=\int_{W}|S\left(f\right)|^{2}df.$ (6)

The waveform that maximizes $d^{2}$ possesses the ESD

$E_{s}\left(f\right)=|S\left(f\right)|^{2}=\max\left(\dfrac{\sqrt{P_{n}\left(f\right)/\lambda}-P_{n}\left(f\right)}{P_{h}\left(f\right)},0\right)$
(7)

where the parameter $\lambda$ is found from the energy constraint in (6). This
involves solving the following expression

$\int_{W}\max\left(\dfrac{\sqrt{P_{n}\left(f\right)/\lambda}-P_{n}\left(f\right)}{P_{h}\left(f\right)},0\right)df=E.$
(8)

The value for $\lambda$ can be solved for numerically given
$P_{n}\left(f\right)$ and $P_{h}\left(f\right)$. Using the receiver in (5),
the Receiver Operating Characteristic (ROC) which relates the probability of
detection $P_{D}$ and the probability of false alarm $P_{FA}$ is completely
characterized using the detection metric defined in (5) and is expressed as
[4]

$P_{D}=P_{FA}^{\frac{1}{1+d^{2}}}.$ (9)

Setting $d^{2}=0$ results in the line of no discrimination ROC curve where
$P_{D}=P_{FA}$. As $d^{2}\to\infty$, the ROC curve approaches the perfect
detector. Maximizing the detection metric $d^{2}$ via the MI waveform
described by (7) and (8) and its corresponding receiver (4) will therefore
maximize the detection probability $P_{D}$ for a given fixed false alarm
probability $P_{FA}$. Thus, the detection metric $d^{2}$ in (5) is the primary
figure of merit this paper uses to evaluate MI waveform designs using the
model developed by Kay [4].

Fig. 1: Block diagram describing the target scene model. The received signal
at the target’s time-delay of arrival is a superposition of a scaled version
of the transmitted waveform $s\left(t\right)$ plus additive noise
$n\left(t\right)$ and clutter $c\left(t\right)$ from the target scene.

###  2.2 The MTSFM Waveform Model

The MTSFM waveform is realized by representing the modulation function as a
finite Fourier series expansion. While this paper focuses on modulation
functions composed solely of sine harmonics for simplicity, the model can be
readily generalized to include cosine harmonics as well. The MTSFM’s
modulation function is expressed as

$m\left(t\right)=\sum_{k=1}^{K}b_{k}\sin\left(\frac{2\pi kt}{T}\right).$ (10)

The corresponding phase modulation function is expressed as

$\varphi\left(t\right)=-\sum_{k=1}^{K}\beta_{k}\cos\left(\frac{2\pi
kt}{T}\right),$ (11)

where $\beta_{k}=\left(\frac{b_{k}T}{k}\right)$ are the waveform’s modulation
indices and serve as a discrete set of $K$ parameters that adapts the
waveform’s characteristics. Inserting (11) into (1) yields the MTSFM
waveform’s time-series.

The MTSFM waveform time-series can also be represented as a complex Fourier
series expressed as [10]

$s\left(t\right)=\sqrt{\frac{E}{T}}\operatorname{rect}\left(t/T\right)\sum_{m=-\infty}^{\infty}c_{m}e^{j\frac{2\pi
mt}{T}}$ (12)

where the Fourier series coefficients $c_{m}$ are the Modified Generalized
Bessel Functions (M-GBFs) [16] with integer order $m$ expressed as
$\mathcal{I}_{m}^{1:K}\left(\\{-j\beta_{k}\\}\right)$. The expansion in (12)
shows that the MTSFM belongs to the family of generalized multi-carrier
waveform models such as Orthogonal Frequency Division Multiplexing (OFDM)
[17]. A unique characteristic of the MTSFM model is that unlike standard OFDM
models with a generic set of coefficients $c_{m}$, the GBF coefficients of the
MTSFM model ensures the resulting waveform is constant modulus [10, 18]. The
spectrum of the MTSFM waveform is expressed as an orthonormal superposition of
frequency shifted $\operatorname{sinc}$ functions [10]

$S\left(f\right)=\sqrt{ET}\sum_{m=-\infty}^{\infty}\mathcal{I}_{m}^{1:K}\left(\\{-j\beta_{k}\\}\right)\operatorname{sinc}\left[\pi
T\left(f-\frac{m}{T}\right)\right].$ (13)

The design goal is to now use the MTSFM waveform model to approximate the
optimal ESD of the MI waveform design problem specified by (7) and (8).

###  2.3 The Design of MI Waveforms using the MTSFM Model

This section describes a heuristic structured phase retrieval method to design
a constant amplitude MTSFM waveform whose ESD $|S\left(f\right)|^{2}$ closely
approximates the ESD of the MI waveform defined in Section 2.1 denoted as
$|S_{o}\left(f\right)|^{2}$. The first step is to find
$|S_{o}\left(f\right)|^{2}$ using (7) and (8). Since the MI waveform design
method is concerned only with the ESD, the phase of the MI waveform’s spectrum
can be ignored and therefore $S_{o}\left(f\right)=|S_{o}\left(f\right)|$.
Discretizing $S_{o}\left(f\right)$, the generic OFDM coefficients $c_{m}$ can
be solved in matrix form via
$\underline{\mathbf{s_{o}}}=\mathbf{X}\mathbf{\underline{c}}$. Here,
$\underline{\mathbf{s_{o}}}$ is the discrete vector form of
$S_{o}\left(f\right)$, the vector $\underline{\mathbf{c}}$ represents the
generic OFDM coefficients $c_{m}$, and $\mathbf{X}$ is a matrix composed of
discretized frequency shifted versions of the $\operatorname{sinc}$ function
in (13) with frequency spacing $f_{m}=m/T$ as in (4). The frequency spacing
results in $\mathbf{X}$ being square and invertible. Thus a unique solution to
$c_{m}$ exists by solving
$\underline{\mathbf{s_{o}}}=\mathbf{X}\mathbf{\underline{c}}$ via
$\underline{\mathbf{c}}=\mathbf{X}^{-1}\underline{\mathbf{s_{o}}}$.

The resulting coefficients $c_{m}$ are generic OFDM coefficients and not
guaranteed to synthesize a constant modulus waveform. Therefore, synthesizing
a constant modulus MTSFM waveform that approximates $|S_{o}\left(f\right)|$
requires finding a M-GBF based fit to the coefficients $c_{m}$. While the
coefficients $c_{m}$ are real but not necessarily positive, the M-GBF
coefficients can be complex valued. Thus, the authors propose synthesizing a
MTSFM approximation to the ideal MI waveform by minimizing the following
distance metric between the magnitudes $|c_{m}|^{2}=c_{m}^{2}$ and
$|\mathcal{I}_{m}^{1:K}\left(\\{-j\beta_{k}\\}\right)|^{2}$

$\underset{\beta_{k}}{\text{min}}\text{~{}}F\left(\\{\beta_{k}\\}\right)=\|c_{m}^{2}-E|\mathcal{I}_{m}^{1:K}\left(\\{-j\beta_{k}\\}\right)|^{2}\|_{2}^{2}\\\
\text{~{}s.t.}\sum_{k}k\beta_{k}\in\left(1\pm\delta\right)\kappa.$ (14)

where $\kappa$ is the region of support of $c_{m}$ such that
$\sum_{m\in\kappa}c_{m}^{2}\cong E$ and the $\sum_{k}k\beta_{k}$ term loosely
approximates the M-GBF’s region of support [16]. Note that the $E$ term in
front of the M-GBF argument ensures proper scaling with $c_{m}^{2}$ since
$\sum_{m}c_{m}^{2}=E$ and
$\sum_{m}|\mathcal{I}_{m}^{1:K}\left(\\{-j\beta_{k}\\}\right)|^{2}=1$ [16].
The quartic objective function defined in (14) is loosely similar to those
defined in other generalized phase retrieval problems [19, 20]. The quartic
nature of this distance metric between $c_{m}^{2}$ and
$|\mathcal{I}_{m}^{1:K}\left(\\{-j\beta_{k}\\}\right)|^{2}$ coupled with the
highly oscillatory nature of the M-GBFs with varying arguments make the
objective function defined in (14) nonconvex. Such an objective function makes
it unlikely that common iterative methods will solve this problem without
special consideration to initialization. However, efforts in the literature
[21, 22] have demonstrated that heuristic methods work surprisingly well on
these nonconvex problems and produce useful results.

##  3 Two Illustrative Design Examples

The following simulations demonstrate the MTSFM-based fit to the MI waveform
problem. Figure 2 shows the noise and clutter PSDs for two scenarios as well
as the ideal MI waveforms for several energy values. These simlulations
utilize the same point target statistics ($\sigma_{A}^{2}=1$) and noise PSDs
while using different clutter PSDs. The noise PSD has a relatively broad
valley centered about DC. Noise only water-filling techniques commonly
utilized in MI waveform design would therefore emphasize most of the
waveform’s energy about DC. However, the clutter also heavily influences the
MI waveform’s ESD. The first scenario’s clutter PSD is oscillatory across most
of the operational band with a distinct peak at DC (i.e, the “clutter-peak”
case). The second scenario’s clutter PSD is largely flat across the
operational band with a distinct notch centered about DC (i.e, the “clutter-
notch” case). Using (7) and (8) produces MI waveforms whose ESDs vary roughly
20 dB across the operational band.

Fig. 2: Illustration of the noise/clutter PSDs and their corresponding MI
waveform ESDs for several energy values.

Figure 3 shows box-whisker plots of the detection metric $d^{2}$ of the MTSFMs
fitted to the ideal MI waveform ESDs across a range of energy values for both
scenarios shown in Figure 2. For each energy value, 1000 MTSFM waveforms each
with a different set of initial modulation indices $\beta_{k}$ were fit to the
ideal MI waveform’s ESD using (14) with $\delta=0.2$. The black circles denote
statistical outliers. Addtionally, the detection metric for an LFM waveform
with equal RMS bandwidth
$\beta_{rms}^{2}=\left(2\pi\right)^{2}/E\int_{W}f^{2}|S\left(f\right)|^{2}df$
to that of the MI and MTSFM waveforms is also shown for each energy value. For
the clutter-peak case, the MTSFMs outperform the LFM often for lower energies
but noticeably less so for higher energies. One potential explanation for this
result is that for higher energies, the MI waveform starts to resemble a flat
spectrum waveform. An analysis of the trials showed that the MTSFM tends to
better fit spectral shapes where there is notable variation across the
operational band. For the clutter-notch case every MTSFM outperformed the LFM
for energy values $E>1$. This is likely because the MI waveform’s ESD shapes
possess a distinct peak at DC, a spectral shape the MTSFM is much better
suited to fitting than the flat spectrum LFM.

Fig. 3: Box-whisker plots of the detection metric $d^{2}$ of 1000 MTSFM trials
for each energy value and the detection metrics for both the ideal MI
waveforms and LFM waveforms with equivalent RMS bandwidth for each energy
value.

##  4 Conclusion

This paper explored applying the MTSFM waveform model to the MI waveform
design problem for point-like targets using the model in [4]. The M-GBF
coefficients that describe the MTSFM are fit to a set of ideal OFDM
coefficients $c_{m}$ via the nonconvex distance metric in (14). Simulations
show that the MTSFM on average produces waveforms whose detection performance
tends to exceed that of spectrally flat waveforms when the ideal MI waveform’s
ESD varies substantially across the operational band. There are several future
avenues to pursue with this work. The most obvious is expanding this analysis
to extended targets with MTSFM waveforms whose modulation functions include
cosine and sine harmonics which produce a richer set of realizable spectral
shapes. Another avenue is refining the phase retrieval process using methods
from [21] to produce MTSFM waveforms whose ESDs more tightly fit the ideal MI
waveform’s ESD.

## References

  * [1] M. R. Bell,  “Information theory and radar waveform design,”  IEEE Transactions on Information Theory, vol. 39, no. 5, pp. 1578–1597, 1993.
  * [2] R. A. Romero, J. Bae, and N. A. Goodman,  “Theory and application of SNR and mutual information matched illumination waveforms,”  IEEE Transactions on Aerospace and Electronic Systems, vol. 47, no. 2, pp. 912–927, 2011.
  * [3] S. U. Pillai, H. S. Oh, D. C. Youla, and J. R. Guerci,  “Optimal transmit-receiver design in the presence of signal-dependent interference and channel noise,”  IEEE Transactions on Information Theory, vol. 46, no. 2, pp. 577–584, 2000.
  * [4] S. M. Kay,  “Optimal signal design for detection of Gaussian point targets in stationary Gaussian clutter/reverberation,”  IEEE Journal of Selected Topics in Signal Processing, vol. 1, no. 1, pp. 31–41, 2007.
  * [5] S. U. Pillai, D. C. Youla, H. S. Oh, and J. R. Guerci,  “Optimum transmit-receiver design in the presence of signal-dependent interference and channel noise,”  in Conference Record of the Thirty-Third Asilomar Conference on Signals, Systems, and Computers, 1999, vol. 2, pp. 870–875 vol.2.
  * [6] J. R. Guerci and S. U. Pillai,  “Theory and application of optimum transmit-receive radar,”  in Record of the IEEE 2000 International Radar Conference, 2000, pp. 705–710.
  * [7] L. K. Patton and B. D. Rigling,  “Phase retrieval for radar waveform optimization,”  IEEE Transactions on Aerospace and Electronic Systems, vol. 48, no. 4, pp. 3287–3302, 2012.
  * [8] S. U. Pillai, K. Y. Li, and H. Beyer,  “Reconstruction of constant envelope signals with given Fourier transform magnitude,”  in 2009 IEEE Radar Conference, 2009, pp. 1–4.
  * [9] J. Bae and N. A. Goodman,  “Evaluation of modulus-constrained matched illumination waveforms for target identification,”  in 2010 IEEE Radar Conference, 2010, pp. 871–876.
  * [10] D. A. Hague,  “Adaptive transmit waveform design using multitone sinusoidal frequency modulation,”  IEEE Transactions on Aerospace and Electronic Systems, vol. 57, no. 2, pp. 1274–1287, 2021.
  * [11] D. A. Hague,  “Target resolution properties of the multi-tone sinusoidal frequency modulated waveform,”  in 2018 IEEE Statistical Signal Processing Workshop (SSP), 2018, pp. 752–756.
  * [12] A. Aubry, A. De Maio, B. Jiang, and S. Zhang,  “Ambiguity function shaping for cognitive radar via complex quartic optimization,”  IEEE Transactions on Signal Processing, vol. 61, no. 22, pp. 5603–5619, Nov 2013.
  * [13] R. Zhou, Z. Zhao, and D. P. Palomar,  “Unified framework for minimax mimo transmit beampattern matching under waveform constraints,”  in 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), May 2019, pp. 4150–4154.
  * [14] L. Wu and D. P. Palomar,  “Sequence design for spectral shaping via minimization of regularized spectral level ratio,”  IEEE Transactions on Signal Processing, vol. 67, no. 18, pp. 4683–4695, Sep. 2019.
  * [15] A. Bose, N. Mohammadi, and M. Soltanalian,  “Designing signals with good correlation and distribution properties,”  in 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2018, pp. 4349–4353.
  * [16] G. Dattoli and A. Torre,  Theory and Applications of Generalized Bessel Functions,  Aracne Editrice, 1996.
  * [17] M. Bică and V. Koivunen,  “Generalized multicarrier radar: Models and performance,”  IEEE Transactions on Signal Processing, vol. 64, no. 17, pp. 4389–4402, 2016.
  * [18] D. A. Hague and J. R. Buck,  “An experimental evaluation of the generalized sinusoidal frequency modulated waveform for active sonar systems,”  The Journal of the Acoustical Society of America, vol. 145, no. 6, pp. 3741–3755, 2019.
  * [19] Ju Sun, Qing Qu, and John Wright,  “A geometric analysis of phase retrieval,”  Foundations of Computational Mathematics, vol. 18, no. 5, pp. 1131–1198, 2018.
  * [20] E. J. Candés, X. Li, and M. Soltanolkotabi,  “Phase retrieval via Wirtinger flow: Theory and algorithms,”  IEEE Transactions on Information Theory, vol. 61, no. 4, pp. 1985–2007, 2015.
  * [21] N. Vaswani,  “Nonconvex structured phase retrieval: A focus on provably correct approaches,”  IEEE Signal Processing Magazine, vol. 37, no. 5, pp. 67–77, 2020\.
  * [22] Y. Shechtman, Y. C. Eldar, O. Cohen, H. N. Chapman, J. Miao, and M. Segev,  “Phase retrieval with application to optical imaging: A contemporary overview,”  IEEE Signal Processing Magazine, vol. 32, no. 3, pp. 87–109, 2015\.