Patent Description:
Various exemplary embodiments disclosed herein relate generally to efficient and masked decomposition of polynomials for lattice-based cryptography.

Recent significant advances in quantum computing have accelerated the research into post-quantum cryptography schemes: cryptographic algorithms which run on classical computers but are believed to be still secure even when faced with an adversary with access to a quantum computer. This demand is driven by interest from standardization bodies, such as the call for proposals for new public-key cryptography standards by the National Institute of Standards and Technology (NIST). The selection procedure for this new cryptographic standard has started and has further accelerated the research of post-quantum cryptography schemes.

There are various families of problems to instantiate these post-quantum cryptographic approaches. Constructions based on the hardness of lattice problems are considered to be promising candidates to become the next standard. A subset of approaches considered within this family are instantiations of the Learning With Errors (LWE) framework: the Ring-Learning With Errors problem. One of the leading lattice-based signature schemes is Dilithium which requires operations involving arithmetic with polynomials with integer coefficients. When implemented, the main computationally expensive operations are the arithmetic with polynomials. More precisely, computations are done in a ring <MAT>: the ring where polynomial coefficients are in <MAT> and the polynomial arithmetic is performed modulo a polynomial F.

A summary of various exemplary embodiments is presented below. Some simplifications and omissions may be made in the following summary, which is intended to highlight and introduce some aspects of the various exemplary embodiments, but not to limit the scope of the invention. Detailed descriptions of an exemplary embodiment adequate to allow those of ordinary skill in the art to make and use the inventive concepts will follow in later sections.

Various embodiments relate to a data processing system comprising instructions embodied in a non-transitory computer readable medium, the instructions for a cryptographic operation including a masked decomposition of a polynomial a having ns arithmetic shares into a high part a<NUM> and a low part a<NUM> for lattice-based cryptography in a processor, the instructions, including: performing a rounded Euclidian division of the polynomial a by a base α to compute t(·)A; extracting Boolean shares <MAT> from n low bits of t by performing an arithmetic share to Boolean share (A2B) conversion on t(·)A and performing an AND with ζ - <NUM>, where ζ = -α-<NUM> is a power of <NUM>; unmasking a<NUM> by combining Boolean shares of <MAT>; calculating arithmetic shares <MAT> of the low part a<NUM>; and performing a cryptographic function using a<NUM> and <MAT>. The system represents a solution to the problem of how to perform masked decomposition securely and efficiently for non power of <NUM> moduli.

Various embodiments are described, wherein performing a rounded Euclidian division of the polynomial a by a base α to compute t(·)A includes adding α/<NUM> to a(·)A and dividing by α.

Various embodiments are described, wherein performing a rounded Euclidian division of the polynomial a by a base a to compute t(·)A includes calculating: t(·)A = a(·)A + γ; and t(·)A = α-<NUM> × t(·)A - (q mod ζ), where γ = α/<NUM> and q is a prime modulus.

Various embodiments are described, wherein calculating arithmetic shares <MAT> of the low part a<NUM> includes: calculating u(·)A by subtracting a<NUM> from t(·)A and adding q mod ζ, where q is a prime modulus; and multiplying u(·)A by α and then subtracting α/<NUM>.

Further various embodiments relate to a data processing system comprising instructions embodied in a non-transitory computer readable medium, the instructions for a cryptographic operation including a masked decomposition of a polynomial a having ns arithmetic shares into a high part a<NUM> and a low part a<NUM> for lattice-based cryptography in a processor, the instructions, including: performing a rounded Euclidian division of the polynomial a by a base α to compute t(·)A; extracting Boolean shares <MAT> from n low bits of t by performing an arithmetic share to Boolean share (A2B) conversion on t(·)A and performing an AND with ζ - <NUM>, where ζ = -α-<NUM> is a power of <NUM>; unmasking a<NUM> by combining Boolean shares of <MAT>; calculating the Boolean shares <MAT> of the low part a<NUM>; and performing a cryptographic function using a<NUM> and <MAT>. The system represents an alternative solution to the problem of how to perform masked decomposition securely and efficiently for non power of <NUM> moduli.

Various embodiments are described, wherein performing a rounded Euclidian division of the polynomial a by a base a to compute t(·)A includes calculating: t(·)A = t(·)A + γ; and t(·)A = α-<NUM> × t(·)A - (q mod ζ), where γ = α/<NUM> and q is a prime modulus.

Various embodiments are described, wherein calculating the Boolean shares <MAT> of the low part a<NUM> includes: shifting t(·)B n bits to the right, where n is a number of bits in ζ; and calculating <MAT> where γ = α/<NUM> and q is a prime modulus.

Further various embodiments relate to a data processing system comprising instructions embodied in a non-transitory computer readable medium, the instructions for a cryptographic operation including a masked decomposition of a polynomial α having ns arithmetic shares into a high part a<NUM> and a low part a<NUM> for lattice-based cryptography in a processor, the instructions, including: performing a rounded Euclidian division of the polynomial a by a base α to compute t(·)A; extracting Boolean shares <MAT> from n low bits of t by performing an arithmetic share to Boolean share (A2B) conversion on t(·)A to produce t(·)B and performing a Boolean share to arithmetic share (B2A) conversion on t(·)B, where ζ = -α-<NUM>; unmasking a<NUM> by combining arithmetic shares of <MAT>; calculating the arithmetic shares <MAT> of the low part a<NUM>; and performing a cryptographic function using a<NUM> and <MAT>. The system represents another alternative solution to the problem of how to perform masked decomposition securely and efficiently for non power of <NUM> moduli.

Various embodiments are described, wherein calculating the arithmetic shares <MAT> of the low part a<NUM> includes: calculating u(·)A by subtracting a<NUM> from t(·)A and adding q mod ζ, where q is a prime modulus; and multiplying u(·)A by α and then subtracting α/<NUM>.

In order to better understand various exemplary embodiments, reference is made to the accompanying drawings, wherein:
<FIG> constitutes, in some respects, an abstraction and that the actual organization of the components of the device may be more complex than illustrated.

To facilitate understanding, identical reference numerals have been used to designate elements having substantially the same or similar structure and/or substantially the same or similar function.

The description and drawings illustrate the principles of the invention. It will thus be appreciated that those skilled in the art will be able to devise various arrangements that, although not explicitly described or shown herein, embody the principles of the invention and are included within its scope. Furthermore, all examples recited herein are principally intended expressly to be for pedagogical purposes to aid the reader in understanding the principles of the invention and the concepts contributed by the inventor(s) to furthering the art and are to be construed as being without limitation to such specifically recited examples and conditions. Additionally, the term, "or," as used herein, refers to a non-exclusive or (i.e., and/or), unless otherwise indicated (e.g., "or else" or "or in the alternative").

Some post-quantum cryptography schemes require a decomposition or a truncation-like operation of polynomial coefficients. For unprotected implementations, this can be straightforwardly realized via different algorithms, mainly involving an Euclidean division or a simple truncation for power of two base and modulus. One family of attacks, so-called side-channel analysis, exploits data dependencies in physical measurements of the target device (e.g., power consumption) to recover secret keys and can be thwarted with the help of masking the processed data. The decomposition operation requires protection since its input and outputs depend on the secret key. However, previous or straightforward techniques for masked decomposition introduce a significant performance overhead for non power of two base and modulus. In this disclosure, a new approach is presented to perform masked decomposition securely and efficiently for non power of <NUM> moduli.

The signing operation of a digital signature scheme generates a signature for a given message using a secret key. If this secret key was to be leaked, it would invalidate the security properties provided by the scheme. It has been shown that unprotected implementations of post-quantum signature schemes are vulnerable to implementation attacks, e.g., side-channel analysis. In particular, it was demonstrated that the secret key may be extracted from physical measurements of key-dependent parts in the signing operation.

For Dilithium, the key-dependent operations include the decomposition of polynomials in a base α. Concretely, for a coefficient <MAT>, the decompose operation computes the high part a<NUM> and the low part a<NUM> such that a mod q = a<NUM> × α + a<NUM> with <MAT>, except if <MAT> where a<NUM> is set to <NUM> and a<NUM> = (a mod q) - q, with <MAT>. The possible values for the decomposition base α are <MAT>and <MAT> Additionally, the parameter γ is defined such that α = <NUM>γ. While the decomposition operation is trivial in the unmasked case, a secure implementation of this digital signature scheme requires the integration of dedicated countermeasures for this step.

Masking is a common countermeasure to thwart side-channel analysis and has been utilized for various applications. Besides security, efficiency is also an important aspect when designing a masked algorithm. Important metrics for software implementations of masking are the number of operations and the number of fresh random elements required for the masking scheme.

The first masking approach for Dilithium was proposed in <NPL>, <NPL>). In Migliore, the decomposition operation for prime modulus is performed using multiple arithmetic additions modulus q over Boolean shares. It takes as input an arithmetic sharing of coefficients and produces Boolean-shared decompositions.

Similar lattice-based signature schemes to Dilithium include GLP and qTESLA. The first dedicated masking of GLP was presented in <NPL> <NPL>). GLP does not require a decomposition operation similar to the one needed for Dilithium. qTESLA only requires a rounding operation by a power of <NUM>. In <NPL>, <NPL>). , the authors extend on Barthe to mask the signature scheme qTESLA, but modify the original parameters of the scheme by changing the prime modulus to a power of two for simpler masking of the rounding operation.

Decomposition methods are disclosed herein that improves on the state-of-the-art enabling significantly more efficient implementations of post quantum cryptography (PQC) schemes requiring a decomposition operation with non power of <NUM> moduli. An example of such a PQC scheme is Dilithium that includes the decomposition of secret polynomial coefficients by the base α. The decomposition methods disclosed herein improves both the number of operations and the number of random elements required.

SecDecomposeOriginal (or Algorithm <NUM> Decompose in Migliore where the name is adapted for better readability) computes α<NUM> first as the division remainder of a by a and then ensures that α<NUM> is in the required range by the Decompose function specifications. The next step of SecDecomposeOriginal is to compute a<NUM> as <MAT>. The last step of the algorithm is to evaluate the specific case where a - a<NUM> = q - <NUM>. SecDecomposeOriginal begins by converting the input from arithmetic to Boolean shares and then exclusively operates on the Boolean shares.

SecDecomposeOriginal includes the following drawbacks. First, because the output a<NUM> of the decomposition function is the input to an addition, an implementation of Dilithium using SecDecomposeOriginal requires an additional B2A conversion in order to perform the addition efficiently or alternatively performs this addition on Boolean shares. Both options are not efficient because both a B2A conversion and an addition on Boolean shares are expensive operations. Second, in SecDecomposeOriginal the computation of a<NUM> and a<NUM> requires many calls to SecAdd (i.e., arithmetic addition over Boolean shares) which is a particularly expensive operation on Boolean shares. Third, in SecDecomposeOriginal almost half of the operations are used only to ensure the range on a<NUM> and to cater to the specific case where a - a<NUM> = q - <NUM> (in particular this part of the algorithm includes one call to SecAnd and two calls to SecAdd).

As a result, for NIST level <NUM> for one Dilithium signing iteration and d = <NUM>, SecDecomposeOriginal takes about <NUM> million operations and <NUM> million random bits. The proposed SecDecomposeA2Apow2 takes <NUM> million operations and <NUM> million random bits for the same task. For NIST level <NUM> taking into account the average number of signing iterations (= <NUM>) and for d = <NUM>, SecDecomposeOriginal takes <NUM> million operations and <NUM> million random bits. The proposed SecDecomposeA2Apow2 requires only <NUM> million operations and <NUM> million random bits in comparison.

The functions SecDecomposeA2Apow2 and SecDecomposeA2Bpow2 provide efficient decomposition when the opposite of the base's inverse is a power of two. The first function SecDecomposeA2Apow2 circumvents the first drawback of SecDecomposeOriginal by providing a<NUM> in arithmetic shares. The second function SecDecomposeA2Bpow2 provides a more efficient approach to SecDecomposeOriginal while still outputting a Boolean-shared a<NUM>, when this is needed for certain implementations. The function SecDecomposeA2Anotpow2 provides an efficient alternative for arbitrary decomposition bases (when the opposite of the base's inverse is not a power of <NUM>). All the functions make use of the observation that once a<NUM> is computed, a<NUM> may be unmasked because its value may be easily recovered from a public signature and the public key.

The improvements of the decomposition functions disclosed herein are based on computing a<NUM> first using a rounded up division by α. As opposed to SecDecomposeOriginal, which operates only on Boolean shares, this is efficiently performed on the input arithmetic shares of a by adding <MAT> and multiplying by the inverse of a modulus q. This allows for a conversion to Boolean shares much later and only when necessary.

The disclosed decomposition functions with rounded division also allows for the computation of the value of a<NUM> that does not require any corner case evaluation/correction and also results implicitly in the correct range for a<NUM> when it is computed from a and the computed a<NUM>. Functions SecDecomposeA2Apow2 and SecDecomposeA2Bpow2 require one A2B conversion to perform the following Λ operation efficiently. SecDecomposeA2Apow2 does not require any other expensive operation on arithmetic or Boolean shares. SecDecomposeA2Bpow2 requires a single addition on Boolean shares. SecDecomposeA2Anotpow2 performs an efficient decomposition for non power of <NUM> base and uses one A2B conversion and one B2A conversion.

The disclosed decomposition functions may be applied for arbitrary non power of <NUM> moduli q and arbitrary decomposition base α. Multiple decomposition function versions are provided: namely when -α-<NUM> is a power of two and when it is not. All masked operations on arithmetic shares are naturally performed modulus q. The annotation mod q shows where a modular reduction has to be performed for the unmasked versions of the algorithms. If an operation is not annotated, the reduction is either explicit or not required.

An application of the disclosed decomposition functions may include the signing process of Dilithium where the coefficients of a secret vector w are decomposed. Concretely, each coefficient <MAT> (with q = <NUM><NUM> - <NUM><NUM> + <NUM>) of w is decomposed into its high and low parts a<NUM> and a<NUM> such that a = a<NUM> × α + a<NUM>. The values of a<NUM> and a<NUM> are such that <MAT>, except if <MAT> where a<NUM> is set to <NUM> and a<NUM> = (a mod q) - q, with <MAT>. The possible values for the decomposition base α are <MAT> and <MAT>. Additionally, the parameter γ is defined such that α = <NUM>γ.

The coefficients of w must remain secret to ensure the security of the signature scheme. A common approach is to split up the sensitive values into Boolean or arithmetic shares. A Boolean or arithmetically masked variable x as x(·)B or x(·)A may be denoted respectively, with <MAT> or <MAT> respectively, (ns being the number of shares). Also note that for protected implementations, the input to the decomposition function is arithmetically shared (because it is the output of a multiplication).

The new disclosed decomposition functions SecDecomposeA2Apow2, SecDecomposeA2Bpow2, and SecDecomposeA2Anotpow2 will now be described.

The function SecDecomposeA2Apow2 is dedicated to the case where ζ = -α-<NUM> is a power of <NUM>. Let n be the number of bits in ζ. Below pseudocode is used to describe SecDecomposeA2Apow2. SecDecomposeA2Apow2 outputs a<NUM> in arithmetic shares and a<NUM> is unshared. The first step of SecDecomposeA2Apow2 is to compute a<NUM> as the rounded Euclidean division of a by α as illustrated in Lines <NUM>-<NUM>. The rounding is done to the nearest integer. This is achieved by first adding <MAT> in Line <NUM> and then dividing by α in Line <NUM>. Because the operations are performed on arithmetic shares modulus q the division by a may be performed very efficiently by multiplying with its multiplicative inverse α-<NUM> modulus q. Then, a<NUM> is extracted by α-<NUM> × t = α-<NUM> × (α × a<NUM> + a<NUM> + γ) = a<NUM> + ζ(-a<NUM> - γ). Then before extracting a<NUM> from α-<NUM> × t as the n low order bits in Line <NUM>, the low order bits of q need to be accounted for because the positive representation of a<NUM> + ζ(-a<NUM> - γ) is q + a<NUM> + ζ(-a<NUM> - γ). The influence of the n low order bits of q are removed by subtracting q mod ζ at Line <NUM>. Then, a<NUM> is extracted as the n low bits of t by performing an A2B conversion at Line <NUM>, an AND with ζ - <NUM> at Line <NUM>, and unmasking a<NUM> at Line <NUM> by recombining the Boolean shares. Next, at Line <NUM>, u is computed by subtracting a<NUM> and undoing the subtraction of q mod ζ, i.e.: <MAT> Lines <NUM> and <NUM> involve dividing u by α-<NUM> which is equivalent to multiplying by α, then subtracting γ to recover a<NUM>.

A function SecDecomposeA2Bpow2 illustrated in pseudocode below presents an alternative to the SecDecomposeA2Apow2 function when Boolean shares are required for the masking of a<NUM>. a<NUM> is unshared as in the SecDecomposeA2Apow2 function. First, the same rounded to nearest integer Euclidean division as in the SecDecomposeA2Apow2 function is used to extract a<NUM> at Lines <NUM>-<NUM>. Then all the previous operations performed on the arithmetic shares are replaced by Boolean operations that essentially perform the same operations. First, instead of subtracting (a<NUM> - <NUM>) and multiplying by a (SecDecomposeA2Apow2, Lines <NUM>-<NUM>), instead t is shifted by n bits to the right at line <NUM> that is equivalent to dividing by ζ or multiplying by α. Finally, the subtraction γ - t is is performed at Line <NUM> using t's two's complement.

A function SecDecomposeA2Anotpow2 is directed to cases where ζ is not a power of <NUM>. It essentially performs the same operations as SecDecomposeA2Apow2. However, in this case, the AND on Line <NUM> in SecDecomposeA2Apow2 cannot be performed to extract the bits of a<NUM> because ζ is not a power of <NUM>. Instead, a modular reduction using a B2A conversion modulus ζ is performed. At Line <NUM> <MAT> is extracted from t(·)B using a B2A function. Then at Line <NUM> a<NUM> is unmasked. Then Lines <NUM>-<NUM> are identical to those in SecDecomposeA2Apow2.

A description of auxiliary variables and functions used in the functions described herein is now provided.

The disclosed decomposition functions will now be compared to SecDecomposeOriginal. One of the disadvantages of using SecDecomposeOriginal is that it requires <NUM>ns random bits to mask constant public values. The fact that these values are masked also increases the number of operations because these masked values are inputs to additions over Boolean shares which are costly operations.

A comparison of the number of operations required for SecDecomposeA2Apow2 and SecDecomposeA2Bpow2 will now be made. Let ns be the number of Boolean or arithmetic shares, ω be the word length of the processor (usually <NUM> or <NUM> bit), and l = log ω - <NUM>. Additionally, define nƒ to be the number of operations for a function ƒ.

The number of operations required for the elementary functions are provided in Table <NUM> and the number of operations required for SecDecomposeA2Apow2, SecDecomposeA2Bpow2 and SecDecomposeOriginal are provided in Table <NUM>. The cost of the B2A conversion required for a<NUM> in Dilithium following SecDecomposeOriginal and SecDecomposeA2Bpow2 are not included.

Next, the number of random bits that need to be generated in the original algorithm versus the new decomposition functions are compared. SecDecomposeOriginal generates a lot of random bits to mask public values in order to perform masked additions straightforwardly. In SecDecomposeA2Apow2 no masking of public values is required and only SecDecomposeA2Bpow2 requires randomness to mask the constant public value γ + <NUM> to perform a masked addition.

The comparative results are summarized in Tables <NUM> and <NUM>. There, rƒ denotes the number of random bits for a function ƒ.

The calculations illustrated in Tables <NUM>-<NUM> illustrate that the disclosed decomposition functions reduce the number of operations and random bits needed to perform the decomposition function.

The countermeasures that result from using the implementation of the decomposition functions disclosed herein provide a technological advantage over the prior art that requires fewer calculations and the generation of fewer random bits than prior implementations. This will allow for lattice based post-quantum cryptography schemes to be implemented in more applications that have limited processing resources.

<FIG> illustrates an exemplary hardware diagram <NUM> for implementing masked polynomial decomposition by using the functions SecDecomposeA2Apow2, SecDecomposeA2Bpow2, and SecDecomposeA2Anotpow2. As illustrated, the device <NUM> includes a processor <NUM>, memory <NUM>, user interface <NUM>, network interface <NUM>, and storage <NUM> interconnected via one or more system buses <NUM>. It will be understood that <FIG> illustrates an exemplary hardware diagram for implementing masked polynomial decomposition by using the functions SecDecomposeA2Apow2, SecDecomposeA2Bpow2, and SecDecomposeA2Anotpow2.

The processor <NUM> may be any hardware device capable of executing instructions stored in memory <NUM> or storage <NUM> or otherwise processing data. As such, the processor may include a microprocessor, microcontroller, graphics processing unit (GPU), field programmable gate array (FPGA), application-specific integrated circuit (ASIC), or other similar devices. The processor may be implemented as a secure processor or may include both a secure processor and unsecure processor.

The memory <NUM> may include various memories such as, for example L1, L2, or L3 cache or system memory. As such, the memory <NUM> may include static random-access memory (SRAM), dynamic RAM (DRAM), flash memory, read only memory (ROM), or other similar memory devices.

The user interface <NUM> may include one or more devices for enabling communication with a user as needed. For example, the user interface <NUM> may include a display, a touch interface, a mouse, and/or a keyboard for receiving user commands. In some embodiments, the user interface <NUM> may include a command line interface or graphical user interface that may be presented to a remote terminal via the network interface <NUM>.

The network interface <NUM> may include one or more devices for enabling communication with other hardware devices. For example, the network interface <NUM> may include a network interface card (NIC) configured to communicate according to the Ethernet protocol or other communications protocols, including wireless protocols. Additionally, the network interface <NUM> may implement a TCP/IP stack for communication according to the TCP/IP protocols. Various alternative or additional hardware or configurations for the network interface <NUM> will be apparent.

The storage <NUM> may include one or more machine-readable storage media such as read-only memory (ROM), random-access memory (RAM), magnetic disk storage media, optical storage media, flash-memory devices, or similar storage media. In various embodiments, the storage <NUM> may store instructions for execution by the processor <NUM> or data upon with the processor <NUM> may operate. For example, the storage <NUM> may store a base operating system <NUM> for controlling various basic operations of the hardware <NUM>. The storage <NUM> may include instructions for implementing masked polynomial decomposition by using the functions SecDecomposeA2Apow2, SecDecomposeA2Bpow2, and SecDecomposeA2Anotpow2 described above.

It will be apparent that various information described as stored in the storage <NUM> may be additionally or alternatively stored in the memory <NUM>. In this respect, the memory <NUM> may also be considered to constitute a "storage device" and the storage <NUM> may be considered a "memory. " Various other arrangements will be apparent. Further, the memory <NUM> and storage <NUM> may both be considered to be "non-transitory machine-readable media. " As used herein, the term "non-transitory" will be understood to exclude transitory signals but to include all forms of storage, including both volatile and non-volatile memories.

While the host device <NUM> is shown as including one of each described component, the various components may be duplicated in various embodiments. For example, the processor <NUM> may include multiple microprocessors that are configured to independently execute the methods described herein or are configured to perform steps or subroutines of the methods described herein such that the multiple processors cooperate to achieve the functionality described herein. Further, where the device <NUM> is implemented in a cloud computing system, the various hardware components may belong to separate physical systems. For example, the processor <NUM> may include a first processor in a first server and a second processor in a second server.

As used herein, the term "non-transitory machine-readable storage medium" will be understood to exclude a transitory propagation signal but to include all forms of volatile and non-volatile memory. When software is implemented on a processor, the combination of software and processor becomes a single specific machine. Although the various embodiments have been described in detail, it should be understood that the invention is capable of other embodiments and its details are capable of modifications in various obvious respects.

Because the data processing implementing the present invention is, for the most part, composed of electronic components and circuits known to those skilled in the art, circuit details will not be explained in any greater extent than that considered necessary as illustrated above, for the understanding and appreciation of the underlying concepts of the present invention and in order not to obfuscate or distract from the teachings of the present invention.

Unless stated otherwise, terms such as "first" and "second" are used to arbitrarily distinguish between the elements such terms describe. Thus, these terms are not necessarily intended to indicate temporal or other prioritization of such elements.

Any combination of specific software running on a processor to implement the embodiments of the invention, constitute a specific dedicated machine.

Claim 1:
A data processing system comprising instructions embodied in a non-transitory computer readable medium, the instructions for a cryptographic operation including a masked decomposition of a polynomial a having ns arithmetic shares into a high part a<NUM> and a low part a<NUM> for lattice-based cryptography in a processor, the instructions, comprising:
performing a rounded Euclidian division of the polynomial a by a base α to compute t(·)A;
extracting Boolean shares <MAT> from n low bits of t by performing an arithmetic share to Boolean share (A2B) conversion on t(·)A and performing an AND with ζ - <NUM>, where ζ = -α-<NUM> is a power of <NUM>;
unmasking a<NUM> by combining Boolean shares of <MAT>;
calculating arithmetic shares <MAT> of the low part a<NUM>; and
performing a cryptographic function using a<NUM> and <MAT>.