#StackBounty: #complexity #db.databases #query-complexity #model-checking #finite-model-theory What is the impact of encodings of spars…

Bounty: 150

Some preliminaries first.
Consider a purely-relational structure (a.k.a. database) $mathfrak{A} = (A, R_1^{mathfrak{A}}, ldots, R_{|tau|}^{mathfrak{A}})$ over some finite signature $tau = { R_1, R_2, ldots, R_{|tau|} }$, where each relational symbol $R_i$ has an associated arity $mathsf{ar}(R_i)$. We assume that $A$ is ordered in some way, just for the sake of encodings.

There are two different ways to represent $mathfrak{A}$ in the memory: one way comes from finite model theory, the second one from database theory. Let me call them the matrix encoding and the list encoding and define $|mathfrak{A}|$ as the size of its encoding.

  1. In the matrix encoding the structure $mathfrak{A}$ is represented as $1^{|A|} cdot 0 cdot mathsf{enc}(R_1) cdot mathsf{enc}(R_2) cdot ldots cdot mathsf{enc}(R_{|tau|})$, where $mathsf{enc}(R_i)$ is an $|A|^{mathsf{ar}(R_i)}$ bit string, with the intended meaning that its $j$-th bit is 1 iff the $j$-th $mathsf{ar}(R_i)$-tuple of $A$ belongs to $R_k^{mathfrak{A}}$.
  2. In the list encoding we encode the structure $mathfrak{A}$ as $1^{|A|} cdot 0 cdot mathsf{enc}(R_1) cdot mathsf{enc}(R_2) cdot ldots cdot mathsf{enc}(R_{|tau|})$, but this time $mathsf{enc}(R_i)$ just lists all the tuples included in $R_i^{mathfrak{A}}$.

Hence, $|mathfrak{A}| approx |A| + Sigma_{i=1}^{|tau|} |A|^{mathsf{ar}(R_i)}$ in the matrix encoding, while $|mathfrak{A}| approx |A| + Sigma_{i=1}^{|tau|} mathsf{ar}(R_i) cdot |R_i^{mathfrak{A}}|$ in the list encoding.
Note that the difference between the encoding is when we have a symbol $S$ of high-arity, let’s say $n$ and there are only a few tuples in $S^{mathfrak{A}}$. Then in the list encoding we will have only a few tuples included, so the representation of $mathfrak{A}$ will be short, while in the matrix encoding we will store all the possible bits, no matter whether a tuple belongs to the relation $S^{mathfrak{A}}$ or not. This seems to be also crucial when we have queries with negation: the relation itself can be "small" but its complement can be "huge", but the complement is not stored directly.

Finally, here comes my question. Do you know any logic (or query language) $mathcal{L}$ for which the combined complexity of the model-checking problem (or query evaluation problem) differs (i.e. we have $mathfrak{A}$ and a formula $varphi$ as an input and we ask if $mathfrak{A} models varphi$ holds)? Of course the signature may differ for different structures. And we need to exploit negations and higher-arity relations somehow.


Get this bounty!!!

#StackBounty: #factoring #complexity #hardness-assumptions Hardness of iterated squaring in Pailler group

Bounty: 50

The (computational) problem of iterated squaring (IS) in the RSA group is defined as follows, where $leftarrow$ denotes sampling uniformly at random:

Input: $(N,x,T)$, where $N$ is the RSA modulus, $xleftarrowmathbb{Z}_N^*$, and $Tinmathbb{N}$ is the time parameter

Solution: $x^{2^T}bmod{N}$.

This problem can be traced back to [C+] and used by [RSW] for constructing time-lock puzzles. More recently, it has been used to build verifiable delay functions [P,W]. It is not hard to see that the problem is at most as hard as factoring $N$. My question concerns the analogous problem in the Paillier group (ISP, for short), as used in [LM] and defined as follows*:

Input: $(N,x,T)$, where $N$ is the RSA modulus, $x=v^Nbmod{N^2}$ for $vleftarrowmathbb{Z}_N^*$ and, $Tinmathbb{N}$ is the time parameter

Solution: $x^{2^T}bmod{N^2}$.

Question. Is the hardness of these problems related, i.e., whether they are reducible to one another.

Why should they be related? Intuitively speaking, the RSA group is embedded in the Pailler group and constitutes its component of unknown order (which is necessary for iterated squaring to be hard). More formally:
$$(mathbb{Z}_{N^2}^*,times)cong (mathbb{Z}_N^*,times)times(mathbb{Z}_N,+),$$
and since iterated squaring in the $(mathbb{Z}_N,+)$ component is easy (as it is a group of known order), one could conjecture that hardness of solving ISP boils down to solving IS.

However, I could not find a reduction in either direction. For instance, to reduce IS to ISP one could try the canonical embedding of $mathbb{Z}N^*$ in $mathbb{Z}{N^2}^$ defined as
$$xbmod{N}mapsto x^Nbmod{N}^2,$$
but this runs into the RSA problem when trying to map the solution back. In the other direction, one could try the canonical projection defined as
$$xbmod{N^2}mapsto xbmod{N},$$
but it is now not possible to lift the solution back to $mathbb{Z}_{N^2}^
$. Any ideas?

*Another way to define it would be as follows:

Input: $(N,x,T)$, where $N$ is the RSA modulus, $xleftarrowmathbb{Z}_{N^2}^*$, and $Tinmathbb{N}$ is the time parameter

Solution: $x^{2^T}bmod{N^2}$.

But it seems less natural than the formulation above.

References.

[C+]: Cai et al, Towards uncheatable benchmarks, CCC’93 (behind a paywall unfortunately)

[LM]: Lai and Malavolta Homomorphic Time-Lock Puzzles and Applications, Crypto’19

[P]: Pietzak, Simple verifiable delay functions, ITCS’19

[RSW]: Rivest, Shamir and Wagner, Time-lock puzzles and timed-release crypto, MIT Report

[W]: Wesolwski, Efficient verifiable delay functions, Eurocrypt’19


Get this bounty!!!

#StackBounty: #post-quantum-cryptography #lattice-crypto #complexity Can LWE be NP-hard?

Bounty: 150

Regev’s reduction shows that LWE is quantumly at least as hard as CVP with an approximation factor of $n/alpha$ for $0<alpha<1$. But I just watched this talk which said that if $sqrt{n/log n}$-CVP is shown to be NP-hard, then the polynomial hierarchy collapses.

This seems to imply that, if the polynomial hierarchy does not collapse, we could not hope to show that $n/alpha$-CVP is NP-hard, meaning that Regev’s reduction cannot show that a poly-time LWE algorithm implies $NPsubseteq BQP$. Is that true?

If so, is there some sort of no-go theorem the other way? That is, maybe we want to come up with a better reduction. But if $sqrt{n/log n}$-CVP could solve LWE, then we can’t hope to reduce LWE to $O(1)$-CVP or else we would show that $sqrt{n/log n}$-CVP is NP-hard, again collapsing the polynomial hierarchy. Is this also true? What is the maximum approximation factor of CVP that can still solve LWE?

(and of course, similar questions apply to the classical reduction).


Get this bounty!!!

#StackBounty: #python #algorithm #object-oriented #python-3.x #complexity Extending the extended Stable Marriage Problem using a Python…

Bounty: 50

As soon as I saw this open source paper, I thought that the best way to replicate their code would be using a python class. After having replicated and extended the paper arxiv link here entirely using a class, I saw this question here that uses loops.

I still think that when one sees the Stable Marriage Problem, an agent like solution comes to mind. I would like to ask the community whether my implementation is sound and pythonic.

The central point is a Persons class as per below. The idea is that all functionality: sending messages, receiving messages, maintaining ranking of other group preferences, storing partner, matching and divorcing is a single agent class.

Then, other code GitHub/BAFurtado/HISMP/main.py calls the class, generates the agents and applies the conditions.

The biggest advantage, I see, is the flexibility to adapt and change the class. Hence, I extended the instability problem with the possibility that any of the agents (belonging to either group: Male or Female) could actually be active messengers. I also included a self.j signal that informs me whether a given agent has successfully messaged all the members of the other group.

Would gladly listen to your opinions and suggestions.

EDITED: Answering the comment below, I include the main code which calls the class, generates groups and makes one run, below the Persons class.

""" Main class of the agents.
    Either Males or Females
    Already prepared to be either ACTIVE or PASSIVE agents (see accompanying paper at arXiv)
    """

import numpy as np


class Person:

    def __init__(self, name, active):
        self.id = name
        self.j = 0
        self.my_ranking = None
        self.my_partner = None
        self.my_energy = None
        self.status = active
        self.messaged = False

    def ranking(self, other_group):
        group = other_group.copy()
        np.random.shuffle(group)
        self.my_ranking = group

    def match(self, candidate):
        self.my_partner = candidate

    def divorce(self):
        self.my_partner = None

    def send_msg(self):
        if self.status == True:
            if self.my_partner == None:
                for i in range(self.j, len(self.my_ranking)):
                    result = self.my_ranking[self.j].receive_msg(self)
                    self.j += 1
                    if self.j == len(self.my_ranking):
                        self.messaged = True
                    if result == '+':
                        break

    def receive_msg(self, candidate):
        if self.my_partner is None:
            self.match(candidate)
            candidate.match(self)
            return '+'
        elif [i.id for i in self.my_ranking].index(candidate.id) < 
                [i.id for i in self.my_ranking].index(self.my_partner.id):
            self.my_partner.divorce()
            self.match(candidate)
            candidate.match(self)
            return '+'
        else:
            return '-'

    def energy(self):
        if self.my_partner is not None:
            self.my_energy = [i.id for i in self.my_ranking].index(self.my_partner.id) + 1
            return self.my_energy
        else:
            self.my_energy = len(self.my_ranking) + 1
            return self.my_energy


class Male(Person):
    pass


class Female(Person):
    pass

And here the main code:

""" Actual running of each repetition """

import numpy as np

from persons import Male, Female


def main(males, females):
    # Running algorithm
    # Shuffle
    np.random.shuffle(males)
    np.random.shuffle(females)
    # Personal Ranking
    [i.ranking(females) for i in males]
    [i.ranking(males) for i in females]

    singles = (max(0, len(males) - len(females)), max(0, len(females) - len(males)))
    # Messaging service
    # All active people have sent messages to everyone on the other group
    current = sum([1 for each in [males, females] for x in each if x.my_partner == None])
    not_msg = sum([1 for each in [males, females] for x in each if (x.status == True) and (x.my_partner == None)
                   and (x.messaged == False)])
    print('M, F theoretical singles: ', singles)
    print('All currently single: ', current)
    print('Not messaged: ', not_msg)

    while not_msg > 0:
        [x.send_msg() for x in males]
        [x.send_msg() for x in females]
        current = sum([1 for each in [males, females] for x in each if x.my_partner == None])
        not_msg = sum([1 for each in [males, females] for x in each if (x.status == True)
                       and (x.my_partner == None)
                       and (x.messaged == False)])
        print('Still single: ', current)
        print('Not messaged: ', not_msg)
        print('')

    return males, females


def gen_groups(group1, group2, alpha, beta=1):
    # Generate groups with a percentage (alpha) of active status (actively sends messages)
    m1, f1 = [], []
    for i in range(group1):
        m1.append(Male(i, np.random.choice([True, False], p=[beta, 1 - beta])))
    for j in range(group2):
        f1.append(Female(j, np.random.choice([True, False], p=[alpha, 1 - alpha])))
    return m1, f1


def calculate_energy(gr1, gr2, pp, homme, femme):
    res_f = np.mean([femme[i].energy() for i in range(len(femme))])
    res_m = np.mean([homme[i].energy() for i in range(len(homme))])
    with open('saved-data/energy.csv', 'a') as fl:
        fl.write('{};{};{};{};{}'.format(gr1, gr2, pp, res_m, res_f))
    return res_m, res_f


if __name__ == '__main__':
    g1 = 1000
    g2 = 1000
    p = 1
    m, f = gen_groups(g1, g2, p)
    m, f = main(m, f)
    # 3. Print Energy
print('Final mean energy males: {}, females: {}'.format(calculate_energy(g1, g2, p, m, f)))


Get this bounty!!!