Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [verifiability]

The tag has no usage guidance.

0
votes
0answers
40 views

ZK verifiable shuffle of ElGamal encryption with different public keys

I need a zero-knowledge proof of correctness of a shuffle of $k$ El-Gamal ciphertexts, but where the public key is different for each ciphertext. However, each public key can be generated from the ...
2
votes
1answer
44 views

Does this description of verifiable random functions seem accurate?

I've been thinking about verifiable random functions recently due to my interest in sortition (random selection of political officials). I wrote up this little paragraph below, and I'm wondering: Does ...
1
vote
1answer
46 views

Verification in Threshold RSA or Threshold Paillier

In the key generation of the threshold version of RSA or the threshold version of the Paillier cryptosystem (e.g. "Shoup - 2000 - Practical threshold signatures" or "Fouque et al. - 2000 - Sharing ...
4
votes
1answer
52 views

Lightweight primality certificates for untrusted DH parameters

Are there any light-weight techniques to generate primality certificates for custom Diffie-Hellman parameters that could be sent to the client to allow it to verify primality without needing to run ...
1
vote
2answers
72 views

Constraint about encrypted values

Let V = $[x_1,\ldots ,x_n]$ be a binary vector of length $n$, and let $E(V)$ be the entrywise encryption of this vector. Suppose I want to give to another player, $E(V)$, but also let him have the ...
-1
votes
1answer
129 views

Random number generator in a 2p2 Network

for my thesis I am trying to develop a system where nodes from a peer to peer network agree in generate a random number every tot seconds. I am stocked in this problem since almost 1 week anyone can ...
2
votes
0answers
219 views

Can Verifiable Random Functions be used to pick a random node from a pool?

Let's say that I have a decentralized system and I have a list of nodes published on a pubic log like a blockchain. I want a node A to be able to connect to another ...
2
votes
0answers
71 views

Are there any information-theoretically secure verifiable secret sharing protocols with t=n?

Disregarding matters such as efficiency and round complexity, can verifiable secret sharing be done in a way such that the secret cannot be decoded unless you have all n shares, and that this ...
3
votes
2answers
120 views

Why does the prover in an interactive proof run in exponential time with the space of the computation?

I'm currently trying to gain an understanding of verifiable computation and the strengths and weaknesses of past approaches. In particular, I've been watching the following YouTube video which talks ...
2
votes
4answers
151 views

Is it possible to verify and relay an encryption key with a trusted but transparent third party?

I'm wondering if it would be possible to implement this functionality with a trusted but transparent third party (maybe an Ethereum smart contract?): Bob has an encryption key. Alice has the ...
3
votes
1answer
176 views

zkSnarks - why isn't PCD more widely used?

I've been reading the paper Scalable Zero Knowledge from Cycles of Elliptic Curves, which elegantly solves (what seems to me) the main problem with zkSnarks; namely that performing non-trivial ...
3
votes
2answers
205 views

How can I prove the result of a long computation with a short string?

I have a simple program F (think of a cellular automaton) that, when executed in some input X, takes a while to complete and ...
4
votes
1answer
276 views

Proof of encrypted content

I would like to create a server that would verify a public/private key pair where the private key is encrypted with a key unknown to the server. The server should reject the keypair if the encrypted ...
2
votes
1answer
118 views

Verifiable computation on signed data

Consider the following setting. Alice receives a chunk of data from Victor, together with a cryptographic certificate of authenticity of some sort (eg hash signed with Victor’s private key). Bob ...
1
vote
1answer
76 views

how to efficiently prove the query result is empty?

Consider a simplified scenario. Suppose an untrusted server holds a set of data $A=\{ a_1,a_2,\cdots,a_n\}$. A client issues a query $b$ to the server and wants to decide if $b\in A$. The server ...
6
votes
1answer
581 views

What is the difference between signatures and VRF?

For example we have asymmetric signature scheme(RSA or ECC based) and VRF(also can be RSA/ECC based), both of them can be verified using public key of the signer/hasher and also are unique for each ...
5
votes
2answers
73 views

Swap information

Alice is trading information with Bob. Alice and Bob are in a Prisoner's Dilemma in that they'd prefer not sending their respective key while receiving each other's but would prefer an exchange taking ...
1
vote
1answer
132 views

Is there a way to verify an original author using encryption?

I feel like the title explains the problem fairly well. Is is possible to use encryption to verify a document's original author? In my case, I have a doc that I want to release online. Is there a way ...
0
votes
1answer
75 views

Verify membership of an item within a set while obscuring the number of elements in the set?

I'm wondering whether it is possible to achieve the following scenario: Say you have a set of names {Alice, Bob, Jake}. To verify that the name 'Bob' exists in the set, you can simply compare 'Bob' ...
5
votes
1answer
182 views

Only allow specific types of data to be transmitted via an end-to-end encryption service

I have a service that allows multiple parties to share domain-specific textual data. This data is also end-to-end encrypted. How can I be sure the sharing parties don't send non-domain-specific data, ...
3
votes
1answer
85 views

Public key verification schemes

I have a short question. Besides PKI, Web of Trust or secure out of band communication. Is there any other way to verify the public key of a communicating party? In other words, let's assume an ...
10
votes
3answers
338 views

Can a device prove the identity of its own code?

Say you have a computing system that has some functionality that is not in itself cryptographically secure, but you want to make sure is executed as specified, and, e.g. an adversary hasn't re-flashed ...
2
votes
1answer
162 views

Plausible Deniability in Schnorr

How does a dishonest verifier affect plausible deniability of the interactive Schnorr protocol?
1
vote
1answer
470 views

Quality test for an hardware source of randomness

Say that I developed an hardware source of randomness, which I would like to use to seed a cryptographically secure random number generator. How would I go about testing it? Are there standardized ...
9
votes
2answers
513 views

Universally verifiable random beacon

I am developing a network where potentially many many nodes (billions, in principle?) should be able to agree on a random number. I would really prefer to avoid $O(N^2)$ procedures where everyone ...
9
votes
1answer
671 views

Is there a formal language to define a cryptographic protocol?

I wanted to work on a personal project where I would attempt to identify the flaws in a cryptographic protocol. Now for that to work properly, the program should understand the syntax of protocol ...
4
votes
1answer
110 views

Why is cryptographic model not considered formal methods?

I have just started looking at different methods for analyzing the security of cryptographic protocols. According to my reading, there are two main approaches in this area. The first approach is so-...
23
votes
2answers
2k views

Formal verification in cryptography

I have seen in some places that people use formal verification and/or computer-aided verification for cryptography (tools like ProVerif, CryptoVerif, etc.). How do these approaches work?
5
votes
1answer
437 views

Simple application of verifiable random function?

I have been reading a little bit about verifiable random functions (e.g.). In the literature, these are described as "pseudo-random functions that provide a non-interactively verifiable proof for the ...
3
votes
1answer
131 views

How can I formally verify fuzzy commitment scheme based security protocol?

I am currently working on designing a security protocol which involves usage of fuzzy commitment schemes, for. eg Reed-Solomon codes which allows us to tolerate a certain level of error. I was ...
2
votes
1answer
424 views

How to calculate $v_k(s)$ in Quadratic Arithmetic Program?

In the paper Pinocchio: Nearly Practical Verifiable Computation, there are some polynomials $v_k(x)$, $w_k(x)$ and $y_k(x)$ representing the structure of there circuit. However, as in the "concrete ...
2
votes
1answer
234 views

Is succinct verification of an arbitrary data transformation theoretically possible? Is it feasible? How?

Given input string S, and transformation (i.e. computer program) T, is it possible to provide a succinct proof that another binary string S' is identical to the output T(S)? By "succinct", I ...
3
votes
1answer
361 views

Implementing forward secrecy in OpenPGP with public key authentication

I am trying to consider the feasibility of implementing an encrypted file sharing system, which both provides forward secrecy but also allows public key verification. I am stuck on the marriage ...
0
votes
0answers
211 views

arithmetic calculation problem to quadratic arithmetic program

I am reading the Pinocchio paper (verifiable computation): http://research.microsoft.com/pubs/180286/pinocchio.pdf The paper is rather hard for me. I am considering this calculation problem: $(c_1*...
1
vote
1answer
58 views

Figure 2 in the Verifiable Computation - Pinocchio

I am reading the Pinocchio paper (verifiable computation): http://research.microsoft.com/pubs/180286/pinocchio.pdf The paper is rather hard for me. For the Figure 2, I guess $v_1(x)$ should be $(r_6-...
1
vote
2answers
323 views

Zero knowledge of two factor

Here I overconfident in myself state that I can show, that n has two factors. This is not completely true, can possibly show $n$ is composite - prover generates RSA key with modulo $n$, and gives $e$ ...
0
votes
1answer
214 views

Blum primes [x=3(mod 4)] zero knowledge proof?

Lets say we have 2 primes, $p \equiv q \equiv 3 \pmod{4}$, and we make $n=p \times q$ public. I can, without revealing factors, show that $n$ has two prime factors. How can i zero knowledge prove ...
0
votes
1answer
83 views

Bit commitment, two blobs with same bit, without revealing it?

Suppose we have bit commitment scheme: $n=p*q$ and $t \in QNR_n$, with Jacobi $(\frac{t}{n})=1$ Commitment(P), random $x\in \mathbb{Z}_n$, $y=x^2t^b$, where $b$ is bit. Ok, suppose we have $y_1$ and ...
1
vote
1answer
233 views

HMAC tag to verify the key (verification in the reverse direction)

A quick question. Are there any problems with the following HMAC use-case: We have two entities ($A$ and $B$), both of them have a secret ($A$ has $S_0$ and $B$ has $S_1$) $A$ generates a random ...
2
votes
1answer
104 views

Feldman's VSSS: Showing the Correctness of shares that are Consistent

This is something with which I am struggling to get my head around. In Feldman's VSSS, I am aware that the Dealer broadcasts exponentials $a_{1},...,a_{t-1}$ of the secret $K$ and the coefficients ...
8
votes
1answer
336 views

Verifiable, Distributed Secret Santa Assignments

My family was planning a secret santa and I thought about how I might write a little web app to dole out these secret assignments. But the downsides to this approach are obvious: there's no way for ...
1
vote
1answer
877 views

Correctness vs Completeness

What is the conceptual difference between the definition of correctness and completeness in verifiable cryptographic protocols? They justify that if a statement is correct then the verification should ...
3
votes
2answers
267 views

Are formal methods used for cryptographic protocol design?

I decided to learn more about the application of formal methods to cryptographic protocols and found this interesting talk by Cathy Meadows at YouTube. After doing research about how people are using ...