Encapsulating Secrets Using Lockable Obfuscation and a RMERS-Based Public Key Encryption

Abstract

Lockable obfuscation, a new primitive that occurs in cryptography, makes it possible to execute arbitrary polynomial-sized functions and recover a secret under specific equality conditions. More concretely, if the function executed over a specific input produces an output that matches an expected target value, here denoted by a, some secret string of bits s is exposed. Written in algebraic terms, if $f:\mathcal{X}\to \mathcal{A}$ has the property that for some $x,f\left(x\right)=a$, s is revealed. This work explores the possibility for safely decrypting ciphertexts, and based on the recovered plaintext’s equality to a stored message, to reveal some secret. Concretely, this work provides a review of existing, well-known public key encryption schemes and argues for the efficiency of a new one relying on the ratio Mersenne hypothesis (RMERS), which is to be used in conjunction with a lockable obfuscator. This work explores the advantage conferred by this scheme, especially in the minimization of the branching program’s number of levels that need to be obfuscated. The drawbacks of such schemes are also pointed out, given that they currently require the $\mathsf{LWE}$ evaluations level-per-level, one output bit at a time.

1. Introduction

Various tasks require the manipulation of highly sensitive cryptographic data. In most of the cases, such use cases include securing communication channels, signing financial transactions, or distributing cryptographic keys that may be used for encryption (symmetric or, depending on the scenario, for public key decryption, digital signing, etc.). These data must be well-protected by the hardware or software implementations against all types of attacks.

On a current basis, such sensitive pieces of information, as the aforementioned ones, are provided in either hardware or software implementations. Considering the first case, such a secret piece of data can be easily destroyed through a physical process: for instance, using physically unclonable functions [1] (abbreviated PUFs), whenever the hardware will be investigated, through most of the known side-channel means, the PUF will internally destroy the protected key.

However, carrying hardware devices may be a cumbersome task, depending on the task. For instance, it may easily fell prey to routine airport checks. This makes us further consider the case of software. For instance, people carry smartphones or laptops as part of their daily routine, and it is less likely that existing software on such devices to be well-scrutinized during standard security checks, as an example, as compared to hardware.

Our work focuses on the problem of protecting such sensitive data in several scenarios that we elaborate below, in the motivational subsection. In such cases, the usage of public key encryption may be insufficient. Namely, it is desirable to prevent a secret from being shared between two parties in order to mitigate the human factor: for instance, where one party (A) knows that whenever party (B) sends the message “START THE ACTION”, it will have to execute an operation. What is desirable to prevent are the risk factors: for instance, if A becomes corrupted or compromised, she may share this command with the adversary E. One step further ahead, E may encrypt the command and send it to A, pretending she is B. Thus, there may be need for authenticated encryption.

On the other hand, B may release a “black-box” software to A, which may indeed reveal such a command like “START THE ACTION”, but only whenever the evaluation of some function passes. For instance, the black-box may encapsulate some decryption key $\mathit{decK}$, while B sends a ciphertext that is to be decrypted under this embedded $\mathit{decK}$; whenever the decryption process under $\mathit{decK}$, of the ciphertext $\mathit{CT}$ sent by B produces some predefined value, such as “CORRECT”, the secret information is then released.

Before discussing several key motivational aspects, this work elaborates more on the method of realizing such “black-boxes”, from a mathematical, and then software-related point of view. Fortunately, there is no need to reinvent the wheel: at first sight, the existing range of cryptographic applications seem to match the need. A cryptographic mechanism, coined as virtual black-box obfuscation [2], is sufficient for this task. However, such virtual black-box obfuscation has been proven to be impossible for several simple tasks, and it may be generally more difficult to use it. However, the more recent literature propose the notion of lockable obfuscation [3,4], which is more akin to the simpler scenarios that are considered in this paper. Obfuscation itself has found practical examples in many areas of software engineering [5].

1.1. Motivational Aspects

Delegating trading capabilities: Wealthy individuals often delegate their savings designated for investments to professional traders; these traders are supposed to invest the financial assets as well as possible. In many circumstances, traders buy and sell stocks according to their own strategies, without asking for approval from the owners. However, things may change as the owners may want to give their approval for buying certain stocks of politically-sensitive companies, for instance. (See for instance the case of large telecom industry manufacturers.) In our somewhat related example, we consider an extremely volatile market—cryptocurrencies. Suppose a very busy but rich investor has already bought Ether, and stores the secret keys used to sign Ether transactions. Assume that Ether’s price is relatively stable for around 1 year (a fact that has been confirmed by the trading record of this cryptocurrency), and the investor does not want to reveal his secret key to the trader until Ether grows. Once this is the case, for example, if the price of Ether grows 10 times in one week, the investor decides to sell and will hand in the key to the trader. Then, in a matter of hours (thus, over a relatively short period), the trader will buy and make profit on behalf of his investor.

The problem above is broken down into several components in order to analyze it: (i) the investor wants to be in full control of buying/selling stocks; (ii) the fact that stocks are very volatile prevents the investor from making the decision of buying within a very short time (i.e., minutes); (iii) the investor, once he decides he wants to invest in a specific stock, wants to delegate his rights to the trader; and (iv) the investor can “commit” to his secret key and will reveal it only at a specific moment, with the trader being authorized to sell in a couple of hours, for instance.

Signing keys usually look pseudorandom and are hard to memorize. So, they must be stored somewhere, which makes this procedure prone to cyber attacks. On top of that, instead of rushing and sending a stored secret key to the trader, utilizing an insecure channel, the key can be stored in a lockable obfuscator, and once the sender sends a randomly looking but specially designated message having some well-defined properties, the key is revealed.

As it can be easily observed from the use case present above, speed is an important criteria when working within such a scenario. It will be of no help for the trader if he learns the secret key that is used to transact a month after. Henceforth, we need to ensure the sensitive data are efficiently recoverable in a short amount of time.

Decrypt and Reveal: Several ultimate military scenarios have to deal with situations where a “letter of last resort” is required to fire an intercontinental ballistic nuclear missile. In such case, orders are communicated directly to the commanders of submarines carrying such annihilation weapons. Most of the time, a short alphanumeric code is transmitted and it has to be used to fire a missile. Several questions arise regarding the authenticity of such code: Can it be sent in plain? What happens if someone knows it at any time (such as the submarine commander or one of the officers)? Can the commander use this code at his will? Can it be reproduced in case the commander defects? Can an external adversary that knows it mimic the process of sending it and “fool” the submarine staff?

Even without any credible information on the topic, it is less likely that such messages are sent in plain. Encryption may be the standard and current technique for dealing with such cases. However, human players are always an issue: how can we deal with someone who knows such keys and who provides them to adversaries. In such a case, can an adversary deliberately send a cable to be allegedly decrypted to a nuclear launch order and code?

1.2. Discussion: Using Symmetric or Public Key Encryption within the Black-Box?

Although it makes a lot of sense to protect sensitive variables until they really need to be released, as seen in the motivational aspects presented above, a pressing question that comes to mind is the following: what sort of check should the “black-box” perform in order to release the secret? As a general rule, the more complex the function to be run in the black-box, the more time will by taken to perform such an operation.

A first option will be to use a symmetric encryption algorithm within the black-box. (From a theoretical point of view, a one-way function is sufficient here, as it provides a symmetric encryption scheme for free. However, we use a symmetric cipher as it is a more practical and popular concept to work with.) If this is the case, then the sender must store the key used to send messages to the black-box. In terms of our examples, the investor must store this symmetric key somewhere, then use it to encrypt messages to the black-box. So, instead of storing a random looking Ether key, he will now store a random looking symmetric key. Although the last one may be shorter, it is still hard to memorize.

The second question: Is public key encryption providing any benefit here? What if the investor uses a public key? He will need to send a message encrypted under the public key. The gain is that such a message may be memorable, and independent from the secret key and from the secretly stored key used to sign Ether transactions.

Henceforth, for the case of an investor, it makes more sense to use a public key encryption scheme within the obfuscated black-box construction.

1.3. Preamble: Public Key Encryption

Public key encryption (PKE) is a method that allows two parties to communicate in the presence of an adversary without pre-sharing any cryptographic secret. (Though, it must be noted that standard public key encryption schemes are prone to man-in-the-middle or botnet-based attacks [6]. For instance, an eavesdropper that owns the communication channel with A and B may simply interact with A pretending to be B, and interact with B, pretending they are A.) (Known as key.)

The history behind public key cryptography is by now half a century old, and started from ingenious mathematical ideas to a scientific branch, rigorously modeled using game theory, allowing for the modeling of attacks run by very strong opponents (attackers).

Early schemes. The early cryptographic schemes were inspired by the Diffie–Hellman key exchange. It should be noted, that although the simple Diffie–Hellman key exchange (that we describe in Section 3.4) was proposed in the 1970s, it was not until the middle of the 1980s that the first Diffie–Hellman inspired public key encryption scheme was proposed. The underlying hard problem was related to the discrete-log assumption. Meanwhile, the very different RSA cryptosystem had been proposed, based on a completely different assumption: factoring. Both schemes are extremely popular, and have been standardized and adopted by practitioners.

An interesting Mersenne assumption. Aggarwal, Joux, Prakash, and Santha [7] put forward a set of novel assumptions based on the properties of low Hamming weight elements sampled from some group of order p, where p is a Mersenne prime. The first of their assumptions states that the ratio of two elements over ${\mathbb{Z}}_p$ that have a low Hamming weight is pseudorandom, which we call the $\mathsf{RMERS}$ assumption.

The other is, which we call the Mersenne Low Hamming Weight Combination Assumption, is very similar to the Learning Parity with Noise problem (LPN): the adversary is required to distinguish tuples $(A,A·S+E)$ from uniform ones, where S and E have Hamming weight h and A is a random elements over ${\mathbb{Z}}_p$. Based on those assumptions, the authors introduced an ingenious $\mathsf{PKE}$ scheme, for encrypting bit-by-bit, which is of great didactic importance through its simplicity. The practical performance of their first scheme is however, lame, as it encrypts a message bitwise, incurring ciphertexts proportional to the input length. A second scheme allows for the encryption of messages of multiple bits, through an error correcting code.

Those assumptions have been under scrutiny in the work of [8]. Later several other primitives have been developed based on those assumptions [9,10]. More recently, several primitives were built from related assumptions [11].

1.4. Preamble: Lockable Obfuscators

Obfuscation, as a computer science subject, deals with making programs unintelligible. Representing programs can be achieved in many forms, including PRAMs, Turing machines, or combinational logic circuits. These computational models are all equivalent in the runtime up to a polynomial factor.

Ideally, two obfuscated programs cannot be told apart, assuming they implement the same functionality. This intuition is captured formally within the notion of indistinguishability obfuscation [2].

While the notion of indistinguishability obfuscation is extremely complex, a more general notion exist, denoted virtual black-box obfuscation. This is impossible for all computable functions, but it turns out to be possible for something like point functions, or more recently, lockable functions [4].

A lockable function is defined as follows:

$$\begin{array}{c}\hfill f_y:\mathcal{X}\to \mathcal{Y},(y,s)\in {\mathcal{Y}}^2,f_y\left(x\right)=\left\{\begin{array}{c}\perp ,\mathrm{when}{f}_y\left(x\right)\ne y\hfill \\ s,\mathrm{when}{f}_y\left(x\right)=y\hfill \end{array}\right.\end{array}$$

(1)

Several lockable obfuscators were proposed, and they are also suitable for storing decryption keys, as advertised by some of their use cases. These make them a prime candidate for the applications we use.

2. This Work

This work’s contribution consists of a new, more efficient instantiation of a lockable obfuscation scheme, created on purpose for a specific public key encryption scheme working on Mersenne prime moduli.

As stated in Section 1, lockable obfuscation is a general paradigm that allows the user of an obfuscated (black-box) program to recover a secret value subject to the result of a computation given that $f\left(x\right)=\alpha$.

As may be hinted, this work needs the public key decryption to play the role of f, with the decryption key hidden in the obfuscator. The notion is guaranteed as long as y has sufficient min-entropy given the function f.

Thinking about software implementations and their performance, the decisive factor for constructing our lockable obfuscator is the branching program complexity of the decryption procedure.

The Main Observation

This paper analyses four of the publicly available and largely used standard public key encryption keys. First, several well-known candidates are quickly ruled out. During the process, the provided analysis is based on the textbook versions. (We avoid the PKCS standards because they have even worse efficiency and describing them does not serve to our purpose.) The main issue is the complexity of repeated modulo exponentiation of a large number.

A much simpler procedure is described in the LWE-based public key encryption scheme proposed by Regev. Although the scheme is inefficient as it encrypts bit-by-bit, it has an extremely simple decryption procedure, involving an inner product between the secret key and a ciphertext component.

However, the core observation made in this article is based on the decryption property of the Mersenne-based public key encryption scheme introduced in [7].

The main gain in working with Mersenne primes as moduli, namely $p=2^n-1$, with n itself a prime is the arithmetic: multiplying two elements modulo p induces a cyclic shift, in the following way:

$$a·b:=a·(2^{b_0}+2^{b_1}+\dots +2^{b_{log\left(n\right)}})$$

(2)

and each multiplication with a power of two induces the cyclic shift.

The obfuscator construction described in Section 5 is based on the reality that a decryption program is known at setup. We consider the relevant branching program, and encode the transition matrices that are used for program evaluation. There is a need to evaluate the input homomorphically over a ciphertext that encrypts the decryption key of the Mersenne-based public key. The interesting aspect is the branching program, which corresponds to the execution of one multiplication (up to $2n$ additions of n elements).

Thus being said, the scheme presented in this article is a custom-made lockable obfuscator. A pseudorandom generator is used to make sure that the decrypted value has sufficient min-entropy: instead of comparing a memorable value, we will compare a pseudorandom version of it with a random looking value.

3. Background Work

Notations related to algorithms: In this work, standard notations are used, and $\theta \in {\mathbb{N}}^{*}$ is considered as the security parameter of a an encryption algorithm (in close relation to its key length). An algorithm is implemented through a Turing machine, as a standard model of computations, and the inputs are given in their unary representation. $\mathrm{PPT}$ stands for “probabilistic polynomial-time”, as a function of the security parameter. An important distinction must be made between a deterministic and a randomized algorithm.

Notations for the mathematical part: For an integer $q\ge 2$, we denote this by ${\mathbb{Z}}_q$ the ring of integers modulo q, and we represent it as ${\mathbb{Z}}_q=(-q/2,q/2]$. The “index” set $\{1,\dots ,k\}$ is represented as $\left[k\right]$. A real-valued function ${\mathrm{N}}_{\mathrm{E}\mathrm{G}\mathrm{L}}$ is negligible if ${\mathrm{N}}_{\mathrm{E}\mathrm{G}\mathrm{L}}\in \mathcal{O}\left({\theta }^{-\omega \left(1\right)}\right)$. We state that an event occurs with overwhelming probability if its probability is $1-{\mathrm{N}}_{\mathrm{E}\mathrm{G}\mathrm{L}}$. The set of all negligible functions is written by ${\mathrm{N}}_{\mathrm{E}\mathrm{G}\mathrm{L}}$. A ordered list of n elements is written as $[a_1,\dots ,a_n]$.

Notations for Probability theory: Min-entropy and randomness extraction. The min-entropy of a random variable X is defined as $H_{\infty }\left(X\right):=-lo{g}_2\left(ma{x}_{x}Pr[X=x]\right)$. Let $\mathrm{SD}(X,Y)$ denote the statistical distance between two random variables X and Y. This work sometimes refers to the Leftover Hash Lemma (LHL) from [12,13].

Notations related to adversaries: Given a randomized algorithm $\mathcal{A}$, we denote the action of running $\mathcal{A}$ on input(s) $(1^{\theta },x_1,\dots )$ over uniform randomness term r and assigning the output(s) to $(y_1,\dots )$ by $\mathcal{A}(1^{\theta },x_1,\dots ;r)\to (y_1,\dots )$. To simulate that $\mathcal{A}$ is given oracle access to some procedure $\mathcal{O}$, we write ${\mathcal{A}}^{\mathcal{O}}$. For any finite set S, we denote its cardinality by $\left|S\right|$. We sample an element x from the uniform distribution over S by $x{\leftarrow }_{\$}S$. When another non-uniform distribution ${\chi }_S$ is used, we write $x{\leftarrow }_{\chi }S$.

3.1. Complexity Assumptions

The Learning With Errors Cryptographic Hypothesis. The Learning with Errors (LWE) (search version of the problem [14]) asks for the secret vector $\mathbf{s}$ over ${\mathbb{F}}_q^l$, given a polynomial-sized noisy vector of the form $\mathbf{A}·\mathbf{s}+\mathbf{e}$, where $\mathbf{A}$ represents a randomly sampled matrix over ${\mathbb{F}}_q^{k\times \ell }$, and $\mathbf{e}$ represents a small error term sampled using the Normal distribution represented as $\chi$. The decision version of the problem asks any $\mathrm{PPT}$ adversary to distinguish between the distribution of the LWE problem as opposed to the uniform distribution.

Ring-LWE. Lyubashevsky, Peikert, and Regev et al. [15] introduced the LWE version for polynomial rings. We assume that $R=\mathbb{Z}\left[x\right]/(x^n+1)$ for n a power of 2, while $R_q:=R/qR$, where q is a prime number constrained by $q=1mod2n$.

Definition 1

(Ring LWE). Assume that s is sampled from $R_q$ and denotes a secret. The adversary is given a polynomial number of samples that are all of the form $(a,a·s+e)$ with a sampled from ${\mathsf{R}}_q$ and $e{\leftarrow }_x{R}_q$, (exclusive), or all uniformly sampled over $R_q^2$. The decision ${\mathsf{RLWE}}_{q,\varphi ,\chi }$ states that some $\mathrm{PPT}$-bounded adversary cannot distinguish between the two settings with more than negligible advantage.

Mersenne Low Hamming Weight Ratio Hypothesis.

Definition 2

(Mersenne Ratio Hypothesis). Let $n\in {\mathbb{N}}^{*}$ be a prime number and let $p=2^n-1$ be a prime number. Let $h\in {\mathbb{N}}^{*}$ and let $W_h=\left\{x\right|x\in {\{0,1\}}^n\wedge {∥x∥}_2=h\}$ be the set of n bit integer having Hamming weight h. Let r be a random element over ${\mathbb{Z}}_p$. Let a and b be sampled uniformly at random from $W_h$. For any $\mathrm{PPT}$ adversary $\mathcal{A}$, its advantage in distinguishing between the following distributions:

$$|Pr[\mathcal{A}(1^n,(a·b^{-1})modp)\to 1]-Pr[\mathcal{A}(1^n,r)\to 1]|,$$

(3)

is negligible; all the operations are performed modulo p.

In the definition above, the adversary is given access to elements that are sampled either from the distribution $a·b^{-1}modp$ or from the uniform distribution, and it has to tell with sufficient advantage from which distribution the element has been sampled.

The decision variant of the Mersenne assumption is very similar to the Learning with Errors assumption.

3.2. Pairwise-Independent Hash Functions

This work assumes prior knowledge on the theory behind hash functions.

Definition 3.

Assume ${\mathcal{H}}_{\alpha }$ is a family of hash function. Each $\mathsf{H}\in \mathcal{H}$ has domain ${\{0,1\}}^{\ell }$ and range ${\{0,1\}}^{{\ell }^{\prime }}$. $\mathcal{H}$ is pairwise independent if the following condition holds:

$$Pr\left[h\left(x\right)=a\wedge h\left(y\right)=b\right]=\frac{1}{2^{2{\ell }^{\prime }}}$$

(4)

for all pairs input $(x,y)\in {\{0,1\}}^{2\ell }$ and output pairs $(a,b)\in {\{0,1\}}^{2{\ell }^{\prime }}$.

3.3. Pseudorandom Number Generators

A pseudorandom number generator ($\mathsf{PRNG}$, [16,17]) is in essence an algorithm that transforms a seed s, usually sampled from the uniform distribution into a (usually larger) output. The gist is that the output distribution should be indistinguishable to the uniform distribution over the co-domain.

Syntactically,

$$\mathsf{PRNG}\left(s\right)\to y,\forall s\in \mathcal{D}.$$

(5)

3.4. Public Key Encryption

Public key cryptography is the backbone used in implementing secure protocols over the Internet. Its roots originate in the public key exchange protocols proposed by Diffie and Hellman [18]. For the broad audience, we assume that Alice and Bob store each the secrets a and b; say both elements modulo some large prime p. Alice publishes $g^a$ while Bob reveals $g^b$; suppose these two quantities are published online. Then, both Alice and Bob learn $g^{ab}$ as ${\left(g^a\right)}^b$ modulo p for the case of Bob and ${\left(g^b\right)}^a$ modulo p for the case of Alice.

Once such a simple key exchange protocol was proposed, public key cryptography emerged. Researchers such as Taher El Gamal and Ronald Rivest, and Adi Shamir and Leonard Adleman observed that is easier to share secrets in a similar way to the exchange of the keys.

Definition 4

(Public key encryption). The following triple of algorithms represents a public key encryption scheme:

• A first step is meant to generate keys. The algorithm produces the public key $\mathsf{pk}$ and the secret key $\mathsf{sk}$. We make the convention the secret key is n bits long and the public key has $P\left(n\right)$ bits, where P is a polynomial.
• The encryption routine encrypts the message $\mathit{M}$ into the ciphertext $\mathit{CT}$ using only the public key $\mathsf{pk}$, without knowing the secret key $\mathsf{sk}$; this routine is denoted by $\mathsf{Enc}$.
• The decryption routine, can be seen as an inverse process with respect to the encryption routine: using the secret key $\mathsf{sk}$, the message $\mathit{M}$ is recovered from the ciphertext. This routine is denoted by $\mathsf{Dec}$.

The completeness of any public key encryption scheme is defined by the following equation:

$$\begin{array}{c}\hfill Pr\left[\mathit{KeyGen}\right(\alpha )\to (\mathsf{pk},\mathsf{sk})\wedge \mathsf{Dec}(\mathsf{sk},\mathsf{Enc}(\mathsf{pk},\mathit{M}))=\mathit{M}]\in 1-ϵ\left(\alpha \right)\end{array}$$

(6)

where $ϵ$ is the inverse of an exponential function.

The security of public key encryption is defined through game theory. The considered game includes an efficient adversary, and it interacts with an efficient benign entity:

Setup phase: The challenger chooses one well-formed pair of keys from the uniform distribution defined over the set of all possible key pairs. The public key is given to the adversary.

Challenge phase: The adversary chooses two messages of equal length, to be denoted as ${\mathit{M}}_0$ and ${\mathit{M}}_1$, and sends them to the challenger.

Encryption phase: One message out of the two, say message $m_b$, is selected and encrypted. Let the resulting ciphertext be ${\mathit{CT}}_b$, and let it be sent to the adversary.

Output phase: the adversary sends its output $b^{\prime }$, revealing if the message comes from $m_0$ or $m_1$.

The adversary wins the game, if:

$$\begin{array}{c}\hfill Pr\left[\mathrm{Adversary}(\mathsf{pk},{\mathit{CT}}_b,{\mathit{M}}_0,{\mathit{M}}_1)\to b^{\prime }\wedge b^{\prime }=b\right]=\frac{1}{2}+c\end{array}$$

(7)

where c is a noticeable quantity.

3.5. Fully-Homomorphic Encryption

The notion of a fully homomorphic encryption [19,20,21] permits its users to evaluate some function (represented as a circuit) over a ciphertext. The result can be decrypted under the secret key paired with the encryption key. The decryption reveals the function applied over the original input.

Definition 5

(Fully homomorphic encryption). Given one function $f:{\{0,1\}}^n\to \{0,1\}$ with n bits as input, consider a circuit class ${\mathcal{C}}_{n,d}$ with input length n, depth d that implements f. The following set of algorithms represent a fully homomorphic encryption scheme:

• A first step is meant to generate keys. The corresponding algorithm produces the public key $\mathsf{pk}$ and the secret key $\mathsf{sk}$. We make the convention that the secret key is n bits long and the public key has $P\left(n\right)$ bits, where P is a polynomial.
• The encryption routinely encrypts the message $\mathit{M}$ into the ciphertext $\mathit{CT}$ using only the public key $\mathsf{pk}$, without knowing the secret key $\mathsf{sk}$. Similarly to public key schemes, this step is denoted $\mathsf{Enc}$.
• The evaluation routine $\mathsf{Eval}$ transforms any ciphertext $\mathit{CT}$ into ${\mathit{CT}}^{\prime }$, by evaluating the circuit $C\in \mathcal{C}$ over $\mathit{CT}$, given access to the public key.
• The decryption routine can be seen as an inverse process with respect to the encryption routine: using the secret key $\mathsf{sk}$, the message $\mathit{M}$ is recovered from the ciphertext.

The correctness and security conditions similar to a public key encryption scheme are not discussed here.

3.6. Leveled Homomorphic Encryption

A leveled fully homomorphic encryption scheme is in essence a fully homomorphic encryption scheme in a setting where the user is limited in the number of computations he will make, up to some level. It will not be described here, as it has the same syntax like fully homomorphic encryption. Hence, such a cryptographic tool is more restrictive.

3.7. Lockable Obfuscators

3.7.1. Intuition

The main purpose of a lockable obfuscator is to receive some value x as input, apply a (hidden) function f on x, and compare the result $f\left(x\right)$ with some pre-computed and stored values y. Whenever $f\left(x\right)=y$, a value z is revealed. As proposed, the value z can be a multi-input value, or a binary one. The security notion requires an obfuscated program to hide f and y, as long as y has sufficient min-entropy, given f.

In this work, the function f that is considered to be obfuscated can be represented as a circuit having logarithmic depth in its input length—namely, $f\in \mathsf{L}/\mathsf{poly}$. We denote by $\mathrm{BP}$ its branching program representation, which has length L, input size ${\ell }_{in}$, and output size ${\ell }_{out}$; that is, $f:{\{0,1\}}^{{\ell }_{in}}\to {\{0,1\}}^{{\ell }_{out}}$. In his well-known paper, David Barrington proves that every function with its circuit representation belonging to complexity class ${\mathit{NC}}^1$ has a branching program representation having its size bounded by a polynomial function in the input’s size.

3.7.2. Formal Definition

The definition of a lockable obfuscator, introduced by Goyal, Koppula, and Waters in [3], is semantically equivalent to the notion computing and comparing obfuscators. The second notion has been introduced in [4], by Wichs and Zirdelis.

Definition 6

(Lockable obfuscation). Let $f:{\{0,1\}}^n\to {\{0,1\}}^m$ denote a function in ${\mathit{NC}}^1$ and let $x\in {\{0,1\}}^n$ and $y\in {\{0,1\}}^m$. A lockable obfuscator $\mathit{LockObf}$ with respect to $(f,y)$ and inputs x consists of the following algorithms:

$\mathit{LockObf}.\mathit{Setup}(1^{\theta },(f,y,s))$:

takes as input the branching program representation of f and some value y. Returns the lockable obfuscator $\mathit{LockObf}[f,y]$.

$\mathit{LockObf}.\mathsf{Eval}\left(x\right)$:

given some input x, the $\mathit{LockObf}[f,y]$ computes $f\left(x\right)$. If $f\left(x\right)=y$, then return s. Otherwise, return ⊥.

The security definition is denoted by the term virtual black-box security.

An obfuscator $\mathit{obf}$ for the distribution class $\mathcal{D}$ over a family of programs P satisfies distributional indistinguishability if there exists a (non-uniform) $\mathrm{PPT}$ simulator $\mathcal{S}$, such that for every distribution ensemble $D=\left\{D_{\theta }\right\}\in \mathcal{D}$, we have

$$(\mathit{obf}(1^{\theta },P),aux){\approx }_c(\mathcal{S}(1^{\theta },P.\mathit{prms}),aux),$$

(8)

where $(P,aux){\leftarrow }_{\$}{\mathcal{D}}_{\theta }$.

As a side remark, although the works of [3,4] have the same operational interface, their constructions differ.

4. Efficiency of Decryption in Extant Public Key Schemes

Public key encryption schemes are defined in Section 3.4. As elaborated in the introductory part, when coupling their decryption circuit with lockable obfuscation, it is important to bear in mind that we want decryption to be as efficient as possible. This is due to the fact that lockable obfuscation adds an important computational overhead on top of the decryption circuit.

In this part, the decryption operation of some of the most well-established public key encryption schemes are briefly analyzed, and also some of the novel ones targeting efficiency.

4.1. The Textbook RSA Public Key Encryption Scheme

RSA [22] is one of the most commonly used public key encryption schemes. The algorithm has been patented in [23].

$\mathbf{Key} \mathbf{Generation}:$

Sample two large and safe primes, p and q, and obtain their product N, which is denoted the RSA modulus. Sample an exponent e, such that $gcd(e,\varphi (N\left)\right)=1$. Publish $(N,e)$ as the public key, while $d=e^{-1}mod\varphi \left(N\right)$ is the decryption key.

$\mathbf{Encryption}:$

to encrypt, compute $c=m^{e}modN$.

$\mathbf{Decryption}:$

to decrypt, compute $c^{d}modN$.

It is well known that the textbook version of RSA is not secure. This happens as encrypting the same message twice results in identical ciphertext, making the scheme prone to frequency attacks. However, the scheme has been standardized and randomness has been introduced during the encryption procedure in order to counter such simple attacks.

4.2. The El-Gamal Public Key Encryption Scheme

The El-Gamal [24] encryption scheme is extremely simple, close to the original Diffie–Hellman key exchange, is suitable for didactic purposes, and has a randomized encryption procedure (it is semantically secure).

$\mathbf{Key} \mathbf{Generation}:$

Sample a safe prime $q=2·p+1$, where p is a prime and a generator g of order p. Sample a secret x over ${\mathbb{Z}}_p$ and publish $g^x$ as the public key, while x is kept secret.

$\mathbf{Encryption}:$

To encrypt, sample a random element $r\in {\mathbb{Z}}_p$ and release the following pair $\left(g^r,g^{r·x}\times \mathit{M}\right)$, where $\mathit{M}$ is the message to be encrypted.

$\mathbf{Decryption}:$

The decryptor proceeds by (1) an exponentiation over the ${\mathbb{Z}}_p$, namely $g^{r\times x}$, as x is known by the decryptor while $g^r$ is provided in the ciphertext; (2) an inversion that provides ${\left(g^{r\times x}\right)}^{-1}$ and (3) a multiplication of $m\times g^{r\times x}$ with ${\left(g^{r\times x}\right)}^{-1}$, which provides m.

As can be seen, the decryption operation provides three steps, which are all computationally expensive, as they involve exponentiation. The related standards of the scheme will not be detailed here, as it is beyond the purpose of this work.

4.3. Public Key Encryption from Learning with Errors

The Learning with Errors problem is recurrent in this work, as it forms the spinal chord of the lockable obfuscation scheme. Here, a simple public key encryption scheme described in [25] is exemplified.

$\mathbf{Secret} \mathbf{key}:$

Choose a vector $\mathbf{s}$ uniformly at random over ${\mathbb{Z}}_q^n$. Set it as the secret key.

$\mathbf{Public} \mathbf{key}:$

Sample m tuples $({\mathbf{a}}_i,{\mathbf{a}}_i^t·\mathbf{s}+e_i)$ from the Learning with Errors distribution under parameter regime q with Gaussian noise samples $e_i$.

$\mathbf{Encryption}:$

For each bit $\gamma$ within the bit decomposition of the message, choose a random subset S in the powerset of $\left[m\right]$ and set the ciphertext to be:

$$(a,b):=\left(\sum _{i\in S}{\mathbf{a}}_i,\gamma ·[q/2]+\sum _{i\in S}{b}_i\right)$$

(9)

$\mathbf{Decryption}:$

Compute $b-{\mathbf{a}}^t·\mathbf{s}$. If it is closer to 0 than $[q/2]$ return 0, otherwise 1.

It can be remarked that decryption is in fact a dot product multiplication of two vectors.

4.4. Public Key Encryption from the Mersenne Assumption

Remember the very simple way of encrypting a bit $\gamma$ in [7]:

$${(-1)}^{\gamma }·\left(a\times \frac{c}{d}+b\right),$$

(10)

where all elements $a,b,c,d$ over ${\mathbb{Z}}_p$ have a low Hamming weight. The public key consists of $\frac{c}{d}$ and the secret key is d. Decryption is performed by multiplying the ciphertext with d and determining whether the Hamming weight is small (plaintext is 0) or large (plaintext is 1).

$\mathbf{Secret} \mathbf{key}:$

Chose a Mersenne prime moduli p of the form $2^h-1$, where h is itself a prime number. Chose two elements c and d from the uniform distribution defined over ${\mathbb{Z}}_p$. Keep d secret.

$\mathbf{Public} \mathbf{key}:$

Publish $\frac{c}{d}$.

$\mathbf{Encryption}:$

Select two elements, a and b from ${\mathbb{Z}}_p$. To encrypt a bit $\gamma \in \{0,1\}$ release the ciphertext:

$${(-1)}^{\gamma }·\left(a\times \frac{c}{d}+b\right).$$

(11)

$\mathbf{Decryption}:$

Multiply ${(-1)}^{\gamma }·\left(a\times \frac{c}{d}+b\right)$ with d and check whether the resulting value is below $2h^2$ (i.e., $\gamma =0$) or above $p-2h^2$ ($\gamma =1$).

4.5. Discussion on Decryption Performance

Arguably, the two candidates that stand are the LWE-based encryption scheme, as well as the one based on the Mersenne assumption. This is because both RSA and ElGamal requires exponentiations mod N, which require repeated multiplications.

It is clear that the dot product between two vectors is a more complex operation to be supported, compared to a single multiplication of elements. The comparison parts count as the same.

Furthermore, the algebraic structure of the Mersenne assumption, namely the structure of the modulus p, makes it easier to implement, and this occurs faster on all software implementations that have been tested.

More concretely, for the envisioned obfuscation scheme considered, the structure of the branching program representing the function mattters the most. As a general rule, the lower the depth of the branching program, the more efficient the scheme.

5. Lockable Obfuscation for Mersenne-Based Public Key Encryption

The central result is presented in this section. To achieve it, we start from the lockable obfuscator presented in [3] (and concurrently by [4]) and adapt it to the decryption function we envision.

The most important aspect related to the scheme described in Section 4.4 is the arithmetic over Mersenne moduli. Namely, multiplying a and $2^z$ cyclically shifts the bits of x with z positions. To multiply and $a·b$, it is easier to decompose b into powers of 2 and shift the bits of a accordingly, than perform the addition and output.

In this paper, consider a function f that can be represented as one circuit with a logarithmic depth in its input length—namely, an ${\mathit{NC}}^1$ circuit. We write by $\mathrm{BP}$ the corresponding branching program representation, which has length L, input size ${\ell }_{in}$, and output size ${\ell }_{out}$, that is, $f:{\{0,1\}}^{{\ell }_{in}}\to {\{0,1\}}^{{\ell }_{out}}$.

5.1. Branching Program for Mersenne-Based PKE decryption

In this part, we figure out the depth of computing the decryption circuit for the Mersenne-based public key encryption scheme put forth in Section 4.4. It is clear that we will need to perform one multiplication and one comparison.

Luckily, the multiplication means shifting variables, and then performing an addition between the n elements. Clearly, the addition can be done in a tree-like structure, thus taking up to:

$$2·n·{log}_2\left(n\right)$$

(12)

steps, where $n={log}_2(p+1)$.

Clearly, such a program has logarithmic depth, making the size of the branching program polynom in the length of the input, using Barrington’s result. The problem that we consider is to decrypt a ciphertext encrypting a memorable passphrase that gives the decryptor the secret s. However, we are constrained by the fact that the passphrase must have sufficient min-entropy. Instead of storing the passphrase, we hash it and then apply a pseudorandom number generator over the hash’s output. The usage of the hash function is required since we need collision resistance. On the other hand, if we assume that the hash is pseudorandom, we will not need the $\mathsf{PRNG}$. We have two man strategies. To build an obfuscator for the circuit performing decryption, hash, and $\mathsf{PRNG}$, or to use leveled fully homomorphic encryption in conjunction with the universal circuit. We explore both cases and see that relying on the PKE in [7] is beneficial.

5.2. The Lockable Obfuscator for Mersenne-Based PKE

We provide a high-level overview and assume a black-box (read generic) utilization of a lockable obfuscator. Let ${\mathsf{Dec}}_d^i$ denote the decryption circuit outputting the $i^{\mathrm{th}}$ bit out of p for a [7] ciphertext. The lockable obfuscator has the following internal working:

Setup$(1^{\alpha },\mathit{M},s)$:

• Let ${\mathsf{Dec}}_d(·)$ be the circuit that computes the decryption in the scheme introduced in Section 4.4, where d is the secret key.
• Choose a pairwise independent hash function, $\mathsf{H}\in \mathcal{H}$.
• Choose a low depth pseudorandom generator $\mathsf{PRNG}$.
• Set $\mathsf{PRNG}\left(\mathsf{H}\left(\mathit{M}\right)\right)\to \beta \in {\{0,1\}}^{\delta }$.
• Build a circuit C that computes the circuit. (The operations to be run are decryption, hash and PRG evaluation.):

  $$C:=\mathsf{PRNG}\circ \mathsf{H}\circ {\mathsf{Dec}}_d(·),$$

  (13)
• Sample $\mathsf{FHE}.\mathit{Setup}\left(1^{\theta }\right)\to (\mathsf{pk},\mathsf{sk})$, a pair of public private fully homomorphic encryption keys. Build a fully homomorphic ciphertext $\widetilde{\mathit{CT}}$ that encrypts the binary representation of the circuit C in Equation (15).
• Build an obfuscator for the $\mathsf{LWE}$ decryption procedure:

  $$\mathit{LockObf}.\mathit{Setup}(1^{\theta },\mathsf{FHE}.{\mathsf{Dec}}_{\mathsf{sk}}(·),\mathsf{PRNG}\left(\mathsf{H}\left(\mathit{M}\right)\right),s)\to \mathit{LockObf}$$

  (14)

Evaluation($\mathit{M}$):

• Construct the universal circuit $U_{\mathit{M}}(·)$. A universal circuit is one that can evaluate any other circuit. In this case, we define $U_{\mathit{M}}\left(C(·)\right)$, for the circuit evaluating decryption over ${(-1)}^{\gamma }·(a·c/d+e)$.
• Homomorphicaly evaluate $U_{\mathit{M}}\left(\right)$ over the leveled homomorphic ciphertext $\widetilde{\mathit{CT}}$ and recovering one bit of the secret s if the $\mathit{M}$ is correct.

We see here that the obfuscated circuit depends on the leveled homomorphic encryption scheme. We can compare the the depth of the circuit computing leveled homomorphic decryption with the combined depth of the circuit computing $\mathsf{PRNG}\left(\mathsf{H}\left({\mathsf{Dec}}_d\right)\right)$.

Depth of C. We can see that the depth of performing the $\mathsf{FHE}$ decryption is similar to an inner product, which has depth that is linear in the input length. Given that an inner product is to be achieved and the inner product involves a tree of ${log}_2\left(n\right)$ additions, and each addition takes ${log}_2\left(q\right)$ bits to perform multiplication, the branching program will have $2^{2·({log}_2\left(n\right)+{log}_2\left(q\right))}$ states.

The second construction. On the other hand, we consider the following scheme (high-level, as we abstract out the implementation of the $\mathit{LockObf}$).

Setup$(1^{\alpha },\mathit{M},s)$:

• Let ${\mathsf{Dec}}_d(·)$ be the circuit that computes the decryption in the scheme introduced in Section 4.4, where d is the secret key.
• Choose a pairwise independent hash function, $\mathsf{H}\in \mathcal{H}$.
• Choose a low depth pseudorandom generator $\mathsf{PRNG}$.
• Set $\mathsf{PRNG}\left(\mathsf{H}\left(\mathit{M}\right)\right)\to \beta \in {\{0,1\}}^{\delta }$.
• Build a circuit C that computes the circuit (The operations to be run are decryption, hash, and PRG evaluation. ):

  $$C:=\mathsf{PRNG}\circ \mathsf{H}\circ {\mathsf{Dec}}_d(·),$$

  (15)
• Build an obfuscator for the $\mathsf{LWE}$ decryption procedure (and also equality testing):

  $$\mathit{LockObf}.\mathit{Setup}(1^{\theta },\mathsf{PRNG}\left({\mathsf{Dec}}_{\mathsf{sk}}(·)\right)),s)\to \mathit{LockObf}$$

  (16)

Evaluation($\mathit{M}$):

• Evaluate the lockable obfuscator on input $\mathit{M}$ and recover the secret bits of s.

5.3. Discussion

We obtain a lockable obfuscator for the decryption functionality within the Mersenne public key encryption scheme. If we get rid of the pairwise independent hash function ad rely only on the pseudo-randomness and (assumed) collision resistance of the $\mathsf{PRNG}$, we can obtain a circuit with a very low depth. For instance, one can consider $\mathsf{PRNGs}$ with extremely low depth, such as $\mathsf{PRNGs}$ in ${\mathit{NC}}^0$. Thus, we can obtain a much shallower circuit and an even more reduced $\mathit{LockObf}$ circuit.

Clearly, this second construction comes with a much shallower branching program, as the depth of the circuit is reduced compared to the previous one. It would be even more interesting to explore obtaining hash functions directly from the Mersenne Ratio assumption, and thus to further reduce the depth of the circuit to be obfuscated.

6. Conclusions

The current paper considers a problem of major importance for many practitioners: deploying sensitive data to potentially dishonest parties, and hiding them until a notification signaling a specific event is sent.

Given the questions about the receiver’s honesty, that it shall not know the sensitive data a priori (this makes public key encryption alone useless), we have seen that employing lockable obfuscation is a solution to be considered.

This work studied the decryption’s routine performance of several public key encryption schemes, and crafted a simplified lockable obfuscator by using a specific Mersenne Assumption-based public key encryption scheme.

Future Work

The current work can be extended in several directions. First, an implementation of the $\mathit{LockObf}$ obfuscator with respect to the PKE scheme using the $\mathsf{RMERS}$ hypothesis can be provided. Second, the obfuscator can be further improved, in order to minimize its number of levels. Third, several other PKE schemes can be considered for implementation. Fourth, the same technique can be applied to different other primitives.