Vector databases deployed in untrusted environments face significant security risks. However, existing privacy-preserving similarity search methods often either overlook result integrity or perform poorly on high-dimensional data. We propose VEkNN, a probabilistically verifiable k-nearest neighbor framework for encrypted high-dimensional vectors, which achieves verifiability by constructing an LSH-based authentication index. VEkNN features a two-phase verification protocol: (1)completeness verification via pseudo-vector insertion and LSH bucket checking, and (2)correctness verification using order-preserving distance comparison and digital signatures. To demonstrate its practical applicability, we implement a web-based prototype that verifies query result integrity and detects server-side data tampering.