Bitwise operations in FHE

Im reading about FHE and the libraries implementing it (SEAL, HELib). I saw that SEAL doesn’t support bitwise operations but I wondered if its theoretically feasible. For example, bitwise-ing XOR an encrypted value with itself, gets us an encrypted 0. Bitwise it with the not of itself to get an encrypted 1. Using shifts with the computed two I would then be able to extract the encrypted number. Shift right/left can be made using multiplication or division by (powers of) 2. But XOR-ing is the main problem. Is it theoretically possible under any FHE/HE scheme? What are the limitations? Thanks

Is there a name for X when X bitwise OR Y is Y?

I’m wondering if there is a mathematical or computer science term for a number X such that Y | X = Y? For example:

66536 | 1000 == 66536 

In this case, 1000 is the "insert name here" of 66536. Perhaps there is no name for this..? I’ve tried searching for "bitwise OR returns itself" and other such terms but without luck so far.

Thanks!

What’s wrong with my bitwise cyclic tag program?

I recently discovered self-modifying bitwise cyclic tag and started making a program that stimulates its behavior.

from console import clear  def SBCT(program):     index=0     t=0     while program:         clear()         print('Step %d:'%t)         print(program)         print(' '*index+'^')          h=int(program[index])         if h==0:             #deletes first program bit              program=program[1:]             if program:index%=len(program)         else:             #appends the appropriate bit if the first bit is one              index=(index+2)%len(program)             program+=int(program[0])*h*program[(index-1)%len(program)]         t+=1  word='1011110111' SBCT(word) 

It seems to match the behavior for the example string (defined here as word) given on the language’s page, as well as for smaller examples that I can tell. The issue is that it seems to mess up in the long-term for the given example. On the page it says the program terminates in 43074 steps but program doesn’t seem to terminate with my code. Since more steps weren’t provided for me to check against, I can’t tell how I made a mistake. Could somebody please point out where I’m going wrong if they see it?

find the bitwise and of a subarray closest to given number

It was a question i had been asked on an online assessment for a company please help me in this question-

Given an array,A of size N and an integer P , find the subarray B=A[i…j] such that i<=j , compute the bitwise value of subarray elements say K= B[i]&B[i+1]&..&B[j]. Output the minimum value of |K-P| among all values of K. size of array 1<=A.size<=100000 A[i] 0 to 10^8

i could only think of brute force.

k-partition the array so as to maximize ‘bit-wise and’ of sums(of elements in partitions)

We are given with an array and a number k.

We need to partition array into k parts so as to maximize ‘bit-wise and’ of sums(of elements in a partition).

Note that we need to find this maximum ‘bit-wise and’ value

For example:

Example 1:

Array: 30, 15, 26, 16, 21, 13, 25, 5, 27, 11

k: 3

Solution: We can partition array into {30, 15} {26, 16, 21, 13, 25} {5, 27, 11}

to get result as (30+15)&(26+16+21+13+25)&(5+27+11) i.e. 33.

where & represents ‘bit-wise and’ operation.

So answer is 33.

Let’s have a look on another example.

Example 2:

Array: 2, 0, 1, 2, 0

k: 1

Solution: Since k=1, array itself is the required partition. So result is (2+0+1+2+0) i.e. 5.

So answer is 5.

I have tried brute-force but it is a slow algorithm and takes too long to produce results. Time limit is 1 second. In brute force i tried all set of partitions and for each set find sum of elements in all partitions and then take bit-wise and of all of these sums. I am struggling to make an optimized solution.Please anyone help me out.

How to find all subarrays whose bitwise and lies in a given range?

Given an array A of integers,we are required to find subarrays ,the bitwise & of whose elements lie in a given range low to high where

low < min(A[0],A[1]....A[n-1])

and

high = min(A[0],A[1]..A[n-1])

i.e. Find all {i,j} such that low <= A[i]&A[i+1]&...&A[j] <=high

I have thought about this for a long time but can’t seem to come up with anything except the naive implementation of generating all subarrays.

Can there be an asymptotically better solution for this?

What effects does memory space have on bitwise shifts?

It is true that the bitwise left shift operation (shl) doubles the value of the integer being shifted. However, when constrained to a finite space, such as 8 bits for example, left shift will begin to push bits off the high-order word and will cause loss. What mathematical effect does this loss have on the number? Does it somehow cancel the doubling effect of the shift?

A related operation is the rotate left operation (rol), in which this loss does not occur.